RU2408167C1 - METHOD OF RELIABLE DISTRIBUTION OF SYNCHRONOUS FRAME (BEACONS) IN WIRELESS LOCAL mesh-NETWORK - Google Patents

Abstract

FIELD: information technologies.

SUBSTANCE: method of reliable distribution of synchronous frames (beacons) in wireless local mesh-network from collisions with other frames based on modification of delay time count procedure in standard method of multiple access with listening of carrier and prevention of collisions of CSMA/CA and on distribution of information on planned duration of beacons transfer with application of specially invented information elements.

EFFECT: improved reliability of transfer of beacons necessary for operation of many mechanisms of mesh-networks, increased efficiency of using wireless channels in mesh-networks, and reduced time of distribution of network information in network.

5 cl, 1 dwg

Description

Field of Invention

Basic information about the role of sync frames (beacons) and the method of their distribution in wireless local mesh networks

A wireless mesh network is a network of stations that supports automatic topology recognition and dynamic route building. We call direct packet forwarding between stations a step. Then the network is called n-step, if the minimum number of steps necessary to transfer the frame between the devices farthest from each other in the network is n. We also introduce the concept of an h-step neighborhood of a network station as the set of other stations located no more than h steps from a given station.

In general, a mesh network is multi-step: n> 1, i.e. Direct transmission between some stations is not possible, and for the transmission of each data packet between these stations, several transfers of this packet using intermediate stations are required.

The most common wireless LAN mesh specification today is the IEEE 802.11s [l] specification. The networks she describes are called Wi-Fi Mesh.

In Wi-Fi Mesh networks, as in many other networks with distributed control, it is necessary to coordinate the work of stations for coordinated decision-making and the work of many mechanisms of the physical and data link layer. To coordinate their work, the stations regularly exchange special packages, which in Russian-language literature are called synchro-frames [2] or beacons [3] (English beacon - “beacon”). All stations of the mesh network participate in the beacon distribution, informing each other about the supported services and operating modes. In addition, many network mechanisms, for example, energy saving and channel reservation mechanisms, include in their bicons their service information - the so-called information elements. By exchanging bicons, stations exchange information elements included in them. Therefore, beacons are containers for information elements of many network mechanisms, and the operation of these mechanisms is impossible without reliable regular distribution of beacons by each station of the Wi-Fi Mesh network.

Basics of Beacon Distribution in Wireless Mesh Networks

In Wi-Fi Mesh networks, a mechanism based on the Carrier Sense Multiple Access with Collision Avoidance (CSMA / CA) method is used to access the channel. Carrier frequency detection means that each station in the network is listening on a channel (medium). If he is busy, i.e. Since another station transmits data, the station waits until the channel is free. To prevent collisions (simultaneous transmission by several stations within the radius of each other's audibility), or rather, to reduce their likelihood, before transmitting data to a free environment, the station postpones the transmission for some time. To do this, she randomly selects an integer number of time slots σ from a certain time interval and initializes a deferral counter. Further, if the medium turns out to be free during the time slot σ, then the counter value decreases by one. If another station starts transmitting, then the counter value is frozen for the transmission time plus the time interval called Distribution Interframe Space (DIFS) if the transmission was successful, or the Extended Interframe Space (EIFS) time interval if there was a collision during the transmission. The numerical value of the constants DIFS and EIFS are determined by the specification [4]. When the counter value is zero, the station starts transmitting data.

The operating time of stations of the Wi-Fi Mesh network is divided into the so-called beacon intervals. The time point that marks the beginning of each beacon interval is called the Target Beacon Transmission Time (TBTT). At every moment, the TBTT mesh station plans to transmit its beacon. As described above, in order to access the medium, the station listens for the medium in anticipation. If at time TBTT, when the station planned to start transmitting its beacon, the medium was busy, this station postpones the transmission of the beacon. The station starts transmitting the planned beacon after the expiration of the Point Interframe Space (PIFS) interval after the medium is free. The value of the PIFS constant is also determined by the IEEE 802.11 specification [4], so that PIFS <DIFS <EIFS.

Let us designate a randomly chosen mesh station as station X, and another arbitrarily selected mesh station as station Y. Since the PIFS interval is shorter than the DIFS interval, mesh station X planning to transmit a beacon gets access to the medium earlier than station Y planning to transmit frames data or other frames other than beacon and adjacent to station X, i.e. perceiving channel occupation equally with it. Therefore, the described method of sending beacons provides a lower probability of their collision with data frames and other control frames than the probability of a collision of data frames and other control frames with each other.

To further increase the reliability of beacon transmission (beacon protection) in the Wi-Fi Mesh network, it is necessary to prevent collisions between the beacons themselves, both for neighboring devices and devices that are 2 steps apart (i.e., not direct neighbors, but having common neighbors). A known method for resolving beacon collisions disclosed in the patent (publication number CN 101155101 (A), publication date 2008-04-02, application number CN 20061159674 20060930, Inventors: NA SHAN [CN]; KAI YANG [CN], Applicant: HUAWEI TECH CO LTD [CN]) and described in the IEEE 802.11s specification [1] under the name Mesh Beacon Collision Avoidance (MBCA). It consists of two components: exchange of mesh-stations with special information elements of Beacon Timing Element and an algorithm for selecting a new TBTT value, which each of the mesh-stations performs if necessary.

Let us describe the MVSA method in more detail. Each mesh station stores a list of stations located in a 2-step neighborhood (immediate neighbors, as well as neighbors of these immediate neighbors), and corresponding to them: a) the time when the beacon was last received from the neighboring station, i.e. its TWTT, and b) the duration of the beacon interval of this neighboring station, based on which the mesh station in question can calculate the approximate time of TBTT transmission of the next beacon by each station from a 2-step neighborhood.

Each mesh station includes this information related to its immediate neighbors in its beacon in the form of a Beacon Timing Element information element in order, firstly, to inform its neighboring stations of the successful receipt of their beacon and, secondly, to equip the stations that have just joined the network with a map of the location of the beacons so that these stations can select their TWT so that their beacons do not overlap in time with the beacons of other devices. If the beacon received from station X does not contain the beacon transmitted by station Y, then the latter may conclude that its beacon has collided. If collisions of beacon Y according to the information of one or several neighbors of station Y are repeated, this station may decide to change its TBTT in order to avoid collisions of its beacon in the future.

However, sending out information about the start time and frequency of transmission of beacon neighbors is not enough to eliminate collisions of beacons, since you still need to know the duration of the beacon transmission, which for each station can vary from beacon to beacon independently. In the current version of the IEEE 802.11s specification [1], this issue is solved as follows: a restriction is imposed on the maximum duration of beacon transmission in L _B microseconds, and all stations in the network consider that the duration of beacon transmission of all other stations is exactly L _B. This circumstance is a significant drawback of the known MBCA method, since the value of L _B is difficult to determine. Moreover, the value of this quantity, applicable in all possible cases, cannot be determined: a small value of L _B significantly limits the amount of network information sent using beacons, and a large value of L _B often leads to channel downtime, since the time taken to transmit the beacon , in most cases is significantly less than L _B.

Despite the fact that when accessing the channel, the transmission of beacons has a higher priority than the transmission of any data frames and other control frames (as described above), collisions of beacons with data frames are still possible and, moreover, very likely if called hidden stations, which is a characteristic feature of mesh networks.

To solve this problem, the following recommendation was introduced in the latest version of the IEEE 802.11s specification [1]: all mesh stations that support the Beacon Timing Element information element should refrain from starting transmission of frames other than beacons if this transmission intersects in time with the moment of TBTT (the planned start of the beacon transfer) to any station from a 2-step neighborhood, as indicated in the Beacon Timing Element information element received from any of the neighboring stations. Mesh stations can resume delayed transmissions after a time L _B after the corresponding TBTT moment.

As already noted, the IEEE 802.11s specification [1] does not offer a way to assign a value of L _B , which is assumed to be fixed (which in itself is a drawback). In addition, the value of this value, applicable in all possible cases, does not exist.

Finally, specification [1] does not describe how to implement the above recommendation to abstain from starting transmission if it crosses in time with the TBTT of neighboring stations. There is a known method used in the frequency spreading method (FHSS) [4], according to which a station, which needs to refrain from transmitting frames until a certain point in time t, counts the time slots of the delay time to zero and remains in this state until time t. When the moment t arrives, the station starts transmitting. This method has a significant drawback: if there are several stations that had to refrain from transmitting, then at time t they will start transmitting at the same time, a collision will occur, and only then, performing standard CSMA / CA procedures, the stations will be able to transmit their frames.

There is another method for sending beacons in a mesh network, different from the method described in the IEEE 802.11s specification and disclosed in the patent (publication number US 2007014269 (A1), publication date 2007-01-18, application number US 20060424235 20060615, Inventors: SHERMAN ITAY [IL]; KANGUDE SHANTANU [US], Applicant: TEXAS INSTRUMENTS INC). The basic idea is that all stations in the network support a single time scale, i.e. for all stations in the network, the TBTT time instants coincide, and the stations send their beacons indented from the TBTT moments that they choose so that the beacons of neighboring stations do not overlap in time. However, this method has significant drawbacks: firstly, it does not solve the problem of hidden stations and does not protect beacons from collisions with data frames of other stations; secondly, it requires maintaining a uniform time throughout the network, which severely limits the scalability of the network.

Another method for distributing bicons in a mesh network is also known in the patent (publication number CN 1013 26779 (A), publication date 2008-12-17, application number CN 20068046472 20061207, Inventors: LIUYANG YANG [US]; BAHAREH SADEGHI [US ], Applicant: INTEL CORP [US]). This method does not require maintaining a single time in the network, unlike the method (patent publication number US 2007014269 (A1)), but has the following drawback: it does not solve the problems of hidden stations and does not protect beacons from collisions with data frames of other stations.

Another method for distributing bicons in a mesh network is also known in the patent (publication number KR 20080052034 (A), publication date 2008-06-11, application number KR 20060124024 20061207, Inventors: JEON BUT IN [KR]; KIM YEON SOO [ KR]; KOH YOUN SUK [KR], Applicant: KT CORP [KR]). However, this method has the following disadvantage: it is applicable only in sensor networks with centralized control, i.e. networks that use a special coordinator device to organize their work.

Another method for distributing bicons in a mesh network is also known in the patent (publication number US 2007064671 (A1), publication date 2007-03-22, application number US 20060516669 20060907, Inventors: KIM JAE-HOON [KR]; LEE JIN- HOON [KR]; CHOI YOUNG-GON [KR]; KIM JUNG-HO [KR]). However, this method has the following drawback: it is applicable only in networks in which a special time interval has been allocated for the transmission of beacons, in which the transmission of data frames is prohibited.

This patent application proposes an alternative method for reliable distribution of beacons in a wireless local mesh network, which differs from the known methods and eliminates the described disadvantages.

The proposed method for reliable distribution of sync frames (bit) in a wireless local mesh network

A method is proposed for reliable distribution of sync frames (bicons) in a wireless local mesh network, which supports automatic topology recognition, in the general case multi-step, and dynamic route building in self-organization mode. This method prevents collisions of beacons with other IEEE 802.11 control frames as well as data frames. The basis of the proposed method are: suspension of the current process of counting the delay when transmitting a data frame, a group of data frames or a control frame other than a beacon; the resumption of the previously delayed delay countdown when transmitting a data frame, a group of data frames or a control frame other than a beacon after the transmission duration of the current beacon resulting from the distribution of previous beacon has expired; the limitation of the number of frames transmitted in the group of frames when resetting the counter of the reverse delay and sending out, with the help of beacons, information about the planned times of the beginning of transmission and the duration of the transmission of its subsequent beacons.

Consider a mesh station that plans to transmit a data frame, a group of data frames, or a control frame other than a beacon. A method of pausing the current delay countdown process when transmitting a data frame, a group of data frames or a control frame other than a beacon is as follows:

a) Each time a transmission is completed, i.e. each time a channel is released and after a DIFS or EIFS time has elapsed (if the transmission just completed was successful or unsuccessful, respectively), each station estimates the minimum time, we denote it by t _nb remaining to the nearest TBTT moment among all stations located in h -step neighborhood of this station (h> 1).

b) Next, the station calculates a value of T ₁ equal to the sum of the remaining delay time and the total duration of one attempt to transmit a frame, including the necessary exchange of service frames and the necessary inter-frame intervals. If a transmission of a group of frames is planned, then T _{1 is} calculated for the first frame from the group, as if it were transmitted as a single frame.

c) The station compares the values of t _nb and T ₁ , and if T ₁ > t _nb , the mesh station suspends the delay countdown. Otherwise, the countdown continues.

If the channel is busy during the countdown, the algorithm is repeated from step a). In the case of transmission of a single frame, when the counter is reset, the station sends a frame.

A method for resuming a previously delayed delay countdown when transmitting a data frame, a group of data frames or a control frame other than a beacon after the transmission duration of the current beacon resulting from sending previous beacon has expired is as follows. Let d _b be the duration of beacon transmission by some station Y at the nearest TBTT moment. Station X, which has suspended the delay time to allow the beacon to be transmitted to station Y, resumes this countdown after the time d _b counted from the TBTT of station Y, after completing the preliminary steps a) -c) of the suspension method described above.

A method of limiting the number of frames transmitted in a group of frames when resetting the counter of the inverse delay is as follows. In the case of a transmission of a group of frames, when the counter is reset to zero, the station estimates the transmission duration of the entire group of n frames (we denote it by T _n ), including the necessary exchange of service frames and the necessary inter-frame intervals, and if T _n > t _nb , the station is limited to transmitting such a number frames m <n such that T _m ≤t _nb ; after this transmission, the station normally selects a new delay time, as prescribed by the CSMA / CA method.

The described operations require knowledge of the durations of the planned beacon transfers d _b for all stations in the h-step neighborhood. Therefore, as well as to increase the efficiency of the known MBCA method for resolving collisions of beacons, a method for collecting and using d _b values for all stations in an h-step neighborhood is further proposed.

The proposed method is based on the assumption that, although the duration of the beacon transmission varies from beacon to beacon, each station plans to transmit each beacon for several beacon intervals, i.e. pre-estimates the amount of information that it is going to send in each of the following bicons. Thus, each station also plans the duration of the transmission of these beacons several beacon intervals ahead.

The method of sending information about the planned transmission start times and transmission durations of subsequent beacons of this station using the bicons of this station, i.e. A method for notifying mesh stations located in an h-step neighborhood from a given station about the transmission start times and the transmission durations of its beacons consists in the following:

- the station regularly includes in its bicon an information element containing: a) information about the times of the start of transmission of its subsequent J beacons, as well as their durations; b) a number, we denote it by TTL, the value of which is equal to h;

- if the TTL number in the received information element is greater than zero, the mesh station includes this information element in its closest beacon, decreasing the TTL value by one and eliminating the outdated information about the transmission of the beacon by the station that initiated this information element;

As a result of such an exchange of information elements, each mesh station is aware of the values of d _b for all stations located in an h-step neighborhood from the sending station of the information element.

Figure 1 shows an example in which stations B and C are hidden from each other due to an obstacle between them, and at the same time they have a common neighboring station - station A. Station C is located in the radio reception area of station A, but outside the zone radio reception of station B, so stations B and C determine the channel occupancy in different ways. If station C starts transmitting, for example, a data frame, then station A will determine the environment as busy, but station B will consider it free. If during the transmission of a data frame by station C for station B the TBTT moment arrives, it will listen to the medium and, considering it free, after a while the PIFS will start transmitting the beacon. However, the transmission of the data frame by station C will not allow station A to receive this beacon: there will be a collision of the beacon of the data frame from station C.

Bibliography

[1] IEEE P802.11s / D3.0. Draft STANDARD for Information Technology - Telecommunications and information exchange between systems - Local and metropolitan area networks - Specific requirements - Part 11: Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) specifications Amendment: Mesh Networking [Electronic resource] / IEEE Standards Activities Department. - [USA]: IEEE, 2009.

[2] S.Yu. Sharov, A.A.Safonov. Features of the transmission of sync frames in IEEE 802.11s mesh networks. // Conference "Information Technologies and Systems", Zvenigorod, 2008, pp. 44-49.

[3] V. M. Vishnevsky, A. I. Lyakhov, A. A. Safonov. Study of the effectiveness of synchronization mechanisms in wireless personal networks with a complex structure. // Information Technologies and Computing Systems, 3/2008, pp. 63-77.

[4] IEEE Std 802.11 - 2007, Revision of IEEE Std 802.11 - 1999. IEEE Std 802.11 - 2007, IEEE Standard for Information Technology - Telecommunications and information exchange between systems - Local and metropolitan area network - Specific requirements - Part 11: Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) specifications. IEEE Computer Society, June 2007.

Claims (5)

1. A method for reliable distribution of sync frames (bicons) in a wireless local mesh network that supports automatic topology recognition, in general multi-step, and dynamic route building in self-organization mode, which helps to prevent collisions of beacons with other control frames of IEEE 802.11 protocol, as well as data frames, different
a method for pausing the current delay countdown process when transmitting a data frame, a group of data frames or a control frame other than a beacon;
a method for resuming a previously delayed delay countdown when transmitting a data frame, a group of data frames or a control frame other than a beacon after the transmission duration of the current beacon resulting from the distribution of previous beacon has expired;
a method for limiting the number of frames transmitted in a group of frames when resetting the counter of the inverse delay;
the method of sending information using the beacon of this station to the mesh network about the planned transmission start times and transmission durations of subsequent beacons of this station; 2. The method according to claim 1, wherein the method of pausing the current delay countdown process when transmitting a data frame, a group of data frames, or a control frame other than a beacon, consists of the following operations:
each station estimates the minimum time t _nb remaining to the nearest TBTT moment among all stations located in the h-step neighborhood of this station, each time the channel is released and after the DIFS or EIFS time has elapsed (if the transmission just completed was respectively successful or unsuccessful);
the stations calculate the value of T ₁ as the sum of the remaining delay time and the total duration of one attempt to transmit a frame, including the necessary exchange of service frames and the necessary inter-frame intervals; if the stations plan to transmit a group of frames, then the value of T _{1 is} calculated for the first frame from the group, as if it was transmitted as a single frame;
the stations compare the values of t _nb and T ₁ and, if T ₁ > t _nb , the mesh stations suspend the countdown of the delay time, otherwise, continue to count. 3. The method according to claim 1, wherein the method for resuming a previously delayed countdown of a delay in transmitting a data frame, a group of data frames or a control frame other than a beacon after the transmission duration of the current beacon resulting from sending previous beacon has expired, station X, suspend the time delay to allow the transfer Beacon station Y, the count resumes after a time d _b, equal to the transmission duration of the Beacon station Y in the next TBTT and the time frame of reference Pipeline from that moment; 4. The method according to claim 1, in which the method of limiting the number of frames transmitted in a group of frames when zeroing the counter back delay consists of the following operations:
stations evaluate the duration T _{n of the} transmission of the entire group of n frames, including the necessary exchange of overhead frames and the necessary inter-frame intervals;
stations are limited to transmitting such a number of frames m <n such that T _m ≤t _nb if T _n > t _nb ,
stations in the usual way (as prescribed by the CSMA / CA method) select a new delay time after transmitting the number of frames defined above. 5. The method according to claim 1, in which the method of sending information using the beacon of the given station of the mesh network about the planned transmission start times and transmission durations of subsequent beacons of this station consists of the following operations:
Stations regularly include in their bicons information elements containing information on the transmission start times for their subsequent J bicons, the durations of these bicons, and also the number of TTLs whose value is equal to h;
mesh stations include this information element in their closest beacons if the number of TTLs in the received information element is greater than zero, while decreasing the TTL value by one and eliminating the outdated information about the transmission of beacons by the station that initiated this information element.