Fairness-based message transmission in a wireless network

Priority claim This application is a US provisional patent application No. 61 / 949,842 filed on March 7, 2014, and a US non-provisional patent filed on March 4, 2015, the entire contents of which are clearly incorporated by reference. It claims the priority of Application No. 14 / 638,815.

The present disclosure generally relates to impartiality-based message transmission in wireless networks.

As a result of technological advances, computing devices have become smaller and more powerful. A variety of portable personal computing devices are extant, including wireless computing devices such as portable wireless phones, personal digital assistants (PDAs), and paging devices that are small, lightweight, and easily carried by users. More specifically, portable wireless phones such as cellular phones, Internet Protocol (IP) phones can communicate voice and data packets over wireless networks. In addition, many such wireless phones include other types of devices embedded within them. For example, wireless phones can also include digital still cameras, digital video cameras, digital recorders, and audio file players. Also, such wireless phones can process executable instructions, including software applications such as web browser applications that can be used to access the Internet. Therefore, these wireless phones may include high computing power.

A wireless mesh network can be formed by wireless phones and other wireless devices for communicating data between wireless devices without the control of a central node (eg, an access point) or server. For example, the Institute of Electrical and Electronics Engineers (IEEE) 802.11s is a standardized set of wireless mesh network communication protocols. In 802.11s, stations within a wireless mesh network (eg, wireless devices) may receive messages addressed to multiple stations, such as multicast and broadcast messages. To propagate the message throughout the wireless mesh network, each station receives the message and sends it to a neighboring station (eg, a station within a one-hop range) (eg, forwards it). Forwarding messages at each station adds traffic and overhead to the wireless mesh network. One proposed alternative includes topology-based transmission and stochastic transfer methods. However, topology awareness Maintaining awareness) incurs additional overhead as the network topology is updated whenever the location of any station changes. In addition, stochastic forwarding reduces the reliability of message reception. Moreover, the proposed alternative does not take into account the relative power consumption of each station. For example, in some topologies, one station may be responsible for rebroadcasting most of the message, resulting in disproportionately high power consumption in one station and relatively few in others. It consumes power and rebroadcasts only a few of the messages.

<p num="0005"> Improves power consumption-related fairness and reduces message propagation-related power consumption at each station in the wireless network compared to 11s wireless mesh networks. Rather than each station sending (for example, forwarding) an incoming message, such as a multicast or broadcast transmission, each station decides whether to send the message based on an analysis of the station-specific neighbor list. First, the source of the message (for example, the first station) identifies the message from stations that are close to the first station, such as one or more stations within a hop range of the first station. Send with your neighbor list. When the message is a multicast transmission, the neighbor list can be a multicast-specific neighbor list. A station's multicast-specific neighbor list can include less than all of the station's neighbors. When the second station receives the message and the first neighbor list, the second station puts the first neighbor list within one hop range of the second station's neighbors (for example, the second station). Compare with its own neighbor list (for example, a second neighbor list) that identifies one or more stations. The second neighbor list identifies at least one station that is not identified by the first neighbor list (for example, at least one station is outside the range of the first station but within the range of the second station. If the second station determines that there is), the second station sends a message and a second neighbor list. Each station identified by the first neighbor list is also identified by the second neighbor list (for example, each station within one hop range of the second station is also within one hop range of the first station). If the second station determines that, the transmission of the message at the second station is suppressed. In this way, the second station does not consume the power to send the message when each of its neighbors is identified by the first neighbor list received with the message. The second station is where each neighboring station is the first, as indicated by the first neighbor list.</p><p num="0006"> Fairness associated with power consumption can be facilitated through the use of random countdowns prior to sending messages. For example, a second station and a third station may receive a message and a first neighbor list from the first station. The second and third stations each initiate a countdown from a station-specific randomly selected countdown value in response to their decision to send a message (eg, based on neighbor list analysis). obtain. When the countdown is completed at the second station before the third station, the second station may send a message and a second neighbor list (eg, station-specific neighbor list) (eg, forward or forward). May be rebroadcast). For example, a second station may rebroadcast a message with a second neighbor list instead of a first neighbor list. The third station may receive a message and a second neighbor list from the second station before the countdown at the third station is completed. The third station may suppress the transmission of messages based on a comparison between the second neighbor list and the third neighbor list generated by the third station. For example, if each station identified by the third neighbor list is also identified by the second neighbor list, and if no other message is pending transmission / forwarding, the third station will stop counting down. You can do it. Each station may randomly select a station-specific countdown value or pseudo-randomly, and each station may contribute to the transmission of a message or save power by suppressing transmission at random (eg, fair). ) You will be able to have a chance.</p><p num="0007"> In addition, the second station can monitor the number of messages (and neighbor lists) received from a particular station (eg, a third station) during a particular time period. The number of messages received from the third station can indicate the level of contribution of the third station to message propagation in the wireless network, and if the number of messages is low (eg, below the threshold), it is wireless. It can be the basis for removing a third station from the network. For example, a second station can decide whether to send a network key to a particular station based on the number of messages. By suppressing the transmission of network keys, if a particular station does not contribute sufficiently to message propagation, as indicated by the number of messages received by the second station, then the second station (eg, specific) Stations can effectively remove (eg, eliminate) certain stations from the wireless network because they cannot send encrypted messages or decrypt incoming messages.</p><p num="0008"> In certain aspects, the method comprises generating a first neighbor list at the first station of the wireless network. The neighbor list may identify one or more stations within a particular range of the first station. The method comprises sending a first message, including a first neighbor list, to a second station on the wireless network.</p><p num="0009"> In another particular aspect, the device comprises a processor and memory attached to the processor. The memory stores instructions that can be executed by the processor to perform operations, including generating a first neighbor list at the first station of the wireless network. The first neighbor list identifies one or more stations within a particular range of the first station. The operation further includes sending a first message containing a neighbor list to a second station on the wireless network.</p><p num="0010"> In another particular aspect, the device comprises means for generating a first neighbor list at a first station in a wireless network. The first neighbor list identifies one or more stations within a particular range of the first station. The device further includes means for transmitting a first message, including a first neighbor list, to a second station on the wireless network.</p><p num="0011"> In another particular aspect, a non-transitory computer-readable medium comprises an instruction to cause the processor to generate a neighbor list at the first station of the wireless network when executed by the processor. The neighbor list identifies one or more stations within a particular range of the first station. The instruction also causes the processor to send a message containing a neighbor list to a second station on the wireless network.</p><p num="0012"> One advantage provided by at least one of the disclosed implementations is the reduced power consumption associated with message propagation at stations in the wireless network compared to wireless mesh networks operating according to the IEEE 802.11s standard. is there. For example, when selective transmission of received messages based on neighbor list analysis (eg, forwarding) allows a station to suppress sending messages (for example, when a neighboring station has already received the message). There are, therefore, as compared with each station to forward a particular message in the wireless mesh network, electricity in one or more stations force consumption is reduced. In addition, fairness associated with power consumption can be promoted through the use of countdowns from random or pseudo-random values selected at each of the stations, by which each station saves power or or It is possible to have a "fair" chance to contribute to message propagation. Other aspects, advantages, and features of the disclosure will become apparent after consideration of the entire application, including the following sections, namely, a brief description of the drawings, embodiments for carrying out the invention, and claims. Let's go.</p>

<figref num="1">FIG. 5 is a diagram of a particular aspect of a system including a wireless network that supports selective transmission of messages and station-specific neighbor lists.</figref><figref num="2">It is a figure which shows the additional transmission of a message and a station-specific neighbor list in the system of FIG.</figref><figref num="3">FIG. 5 is a diagram of a first exemplary example of message and station-specific neighbor list transmission in a wireless network.</figref><figref num="4">FIG. 5 is a diagram of a second exemplary example of message and station specific neighbor list transmission in a wireless network.</figref><figref num="5">It is a flow chart of an exemplary method of transmitting a message and a neighbor list in a wireless network.</figref><figref num="6">It is a flow chart of an exemplary method of selectively transmitting a message and a neighbor list in a wireless network.</figref><figref num="7">It is a flow chart of an exemplary method of selectively removing a station from a wireless network based on the number of messages received during a particular time period.</figref><figref num="8">FIG. 5 is a diagram of a wireless device capable of operating to support various aspects of one or more methods, systems, devices, and / or computer-readable media disclosed herein.</figref>

Specific embodiments of the present disclosure will be described below with reference to the drawings. In the description, common features are specified by common reference numbers throughout the drawings.

With reference to FIG. 1, a particular exemplary embodiment of System 100 is shown, including a wireless network that supports selective transmission of messages and station-specific neighbor lists. System 100 includes a first station (STA_1) 104, a second station (STA_2) 106, a third station (STA_3) 108, a fourth station (STA_4) 110, and a fifth station (STA_5). ) 112 and a wireless network 102 including a sixth station (STA_6) 114.

Stations 104-114 may form a group of stations configured to perform wireless communication between stations. For example, a group of stations (eg, stations 104-114) may be configured to perform wireless communication over one or more wireless channels. A group of stations can form a peer-to-peer wireless network. In some implementations, a group of stations may include or correspond to a group of data pathways (eg, a group of stations that share a particular service). In other implementations, groups of stations may include or accommodate different, infrastructure-free ad hoc wireless networks. In certain implementations, the wireless network 102 may be a social wireless mesh network ("social wi-fi mesh"). In another particular implementation, the wireless network 102 may operate according to one or more standards, such as the Institute of Electrical and Electronics Engineers (IEEE) 802.11 standard. As used herein, the wireless network 102 can support transmission according to the IEEE 802.11s standard, as an exemplary non-limiting example. Moreover, in some implementations, one or more stations in a group of stations may be part of or included in other networks. For example, one or more of stations 104-114 may correspond to or be included in a Neighbor Aware Network (NAN).

Each of stations 104-114 may be a wireless communication device configured to transmit data and / or receive data from other wireless communication devices within the wireless network 102. For example, stations 104-114 are a processor (eg, central processing unit (CPU), digital signal processor (DSP), network processing unit (NPU), etc.), memory (eg, for example), as described further with reference to FIG. , Random access memory (RAM), read-only memory (ROM), etc.), and / or wireless interfaces configured to send and receive data over wireless networks. Each of stations 104-114 may, as a non-limiting example, be configured to operate in accordance with the IEEE 802.11s standard. In other implementations, stations 104-114 may be configured to operate according to other standards, such as one or more IEEE 802.11 standards, one or more Wi-Fi Alliance standards, or a combination thereof. ..

The first station 104 may be configured to generate a message 120 addressed to a plurality of stations in the wireless network 102. In certain implementations, message 120 may be a broadcast message (eg, it can be addressed to each other station on wireless network 102). In other implementations, message 120 may be a multicast message (eg, it can be addressed to a subset of other stations in wireless network 102). In certain implementations, message 120 may include a unique identifier, such as one or more bits that are encoded in message 120 and not in other messages. For example, message 120 may include a first identifier 124. The first station 104 may also be configured to generate a first neighbor list (List_1) 130. The first neighbor list 130 can identify "neighboring" stations of the first station (eg, one or more stations within a hop range of 150). The one-hop range 150 shown in FIG. 1 is for convenience only and is not limiting. In certain implementations, the one-hop range 150 may be circular and may be centered on the first station 104.

In certain implementations, message 120 may be a multicast message and the first neighbor list 130 may be a multicast-specific neighbor list (for example, indicating multiple neighbors to which multicast message 120 is addressed). be able to). Each of stations 104-114 can determine neighboring stations according to the IEEE 802.11s standard, for example by beacon or probe request / response message. As an addition or alternative, neighboring stations can determine using a lightweight neighbor discovery mechanism. The first station 104 is described herein as producing message 120 (eg, the source or "outgoing" station of message 120), but in other implementations, stations 106-114. Our different stations can generate message 120. In addition, each of the other stations 106-114 may generate its own neighbor list (eg, neighbor lists 132-140).

The first station 104 can send the message 120 and the first neighbor list 130 to neighboring stations. In certain implementations, the first neighbor list 130 may be encoded with the message 120. In an alternative implementation, the first neighbor list 130 may be attached to message 120. Each of the neighboring stations will receive message 120 and the first neighbor list 130, as further described herein with reference to FIG. 2, and is based on a station-specific analysis of the first neighbor list 130. Message 120 may be configured to be selectively sent (eg, forwarded).

During operation, the first station 104 can generate message 120 and first neighbor list 130. The first neighbor list 130 may identify the second station 106, the third station 108, and the sixth station 114 as neighbors of the first station 104. In a particular implementation, the first neighbor list 130 may identify the first station 104 as the source. The first station 104 may send a message 120 containing the first neighbor list 130 and the first identifier 124 to the second station 106, the third station 108, and the sixth station 114. Stations 106, 108, and 114 can receive messages 120 and the first neighbor list 130, and of their own neighbor list and the first neighbor list 130, as described further with reference to FIG. Based on the comparison, each may decide whether to send or suppress (eg, not send) message 120.

The downstream station receives the first neighbor list 130 because the "downstream" station (eg, stations 106-114) of the source (eg, the first station 104) receives the first neighbor list 130. Message 120 may be selectively sent or suppressed based on. Therefore, a station can save power by suppressing (eg, not transmitting) message 120 when neighboring stations are expected to receive message 120 from different stations. Reducing power consumption, the wireless network 102 has two non-limiting examples of transmission aggregation, such as content sharing and / or streaming or information sharing (eg, in a large event) between distributed sensor nodes. It may be possible to support a target application.

FIG. 2 shows the additional transmission of message 120 and station-specific neighbor list in system 100 of FIG. For example, FIG. 2 shows the transmission (eg, forwarding) of message 120 across multiple stations within the wireless network 102.

As described with reference to FIG. 1, each of stations 106-114 may receive message 120, including the first neighbor list 130, from the first station 104. Stations 106-114 may selectively send or suppress (eg, not send) message 120 to neighboring stations based on a comparison between the station-specific neighbor list and the first neighbor list 130. Can be configured. The arrangement of stations 104-114 and the one-hop ranges 152 and 154 in FIG. 2 is for illustration purposes only and is not limiting. For example, stations 104-114 may be arranged in any way within the wireless network 102, and the one-hop ranges 152 and 154 may be circular and centered on their respective stations.

For example, the second station 106 selectively selects message 120 based on a comparison between the first neighbor list 130 and the second neighbor list (List_2) 132 generated by the second station 106. It can be configured to send. For illustration purposes, the second station 106 can compare the stations identified by the second neighbor list 132 with the stations identified by the first neighbor list 130. For example, each neighbor list uses a station identifier, such as a media access control (MAC) address or other station identifier, to identify the station. If each station identified by the second neighbor list 132 is also identified by the first neighbor list 130 (ie, the second neighbor list 132 is a subset of the first neighbor list 130), then the second station 106 may decide to suppress message 120 (eg, neither send nor forward) and discard message 120 without sending it (eg, clear it). Therefore, message suppression may include deciding not to send the message and deleting or deleting the message. According to the first neighbor list 130, each neighbor of the second station 106 is expected (or has) received message 120 from the first station 104, so the second station 106 is expected to receive message 120. Can be decided not to send. However, if at least one station identified by the second neighbor list 132 (eg, the fourth station 110) is not identified by the first neighbor list 130, then the second station 106 will have at least one station message. You may decide to send (eg, forward) message 120 as you expect (or will) receive 120. The second station 106 may also transmit a second neighbor list 132. For example, the second station 106 may send message 120 and the second neighbor list 132 (for example, the second station 106 may send the second neighbor list 13 instead of the first neighbor list 130). Message 120 with 2 can be rebroadcast). Neighboring stations that have received the forwarded message 120 from the second station 106, including the second neighbor list 132, may likewise decide whether to send or suppress the message 120.

In certain implementations, the second station 106 may be configured to suppress the transmission of the message 120 based on the first identifier 124 contained in the message 120. For example, the second station 106 may include a buffer 168 configured to store the message identifier. The second station 106 can store in buffer 168 an identifier corresponding to any message sent by the second station 106 during a period of time. For example, multiple identifiers corresponding to multiple messages may be stored in buffer 168. The time period can be selected based on the size of buffer 168, the expiration time of the identifier, or other factors. In some implementations, the time period may be determined based on the end-to-end delay of wireless network 102. The second station 106 may be configured to suppress transmission of message 120 (eg, to determine not to transmit) if a particular identifier for message 120 is stored in buffer 168. For example, if message 120 was previously sent by the second station 106, buffer 168 can store the first identifier 124, and the second station 106, buffer 168 remembers the first identifier 124. You may decide not to send (eg, forward) an additional copy of message 120 based on what you are doing. The determination that a particular unique identifier is stored in the buffer may be faster than comparing the first neighbor list 130 and the second neighbor list 132, and may consume less power. Therefore, the station can decide whether to forward message 120 prior to comparing neighbor lists and / or instead using buffer 168.

The various operations, examples, and implementations described herein are described with reference to a second station 106. This is for convenience and is not limited. For example, each of the other stations 104 and 108-114 may operate similarly to the second station 106, as described herein.

To promote fairness in wireless network 102 (for example, to prevent a particular station from forwarding or rebroadcasting more messages than others and consuming more power), the station 104-114 may be configured to count down from the station-specific countdown value prior to sending message 120. For illustration purposes, the second station 106 may be configured to initiate a countdown from the countdown value 142 in response to the decision to send message 120. For example, the second station 106 may include counters, timers, or other counting or timing logic configured to generate a countdown value 142 and to perform a countdown from a countdown value 142.

In certain implementations, the second station 106 generates a countdown value 142 by randomly selecting a countdown value 142 from a range between zero and a maximum latency (MWT) value such as the MWT value 146. can do. In one example, the MWT value 146 may be pre-generated and stored in the second station 106 and may be the same for each of stations 104-114. Therefore, the countdown value may be a random value between zero and the MWT value 146, or a pseudo-random value. In response to the countdown reaching zero, the second station 106 may send (eg, forward) a message 120 containing a second neighbor list 132. The start of the countdown is described as occurring after deciding whether to send the message 120, but in other implementations the start of the countdown and the decision to send the message 120 send or suppress the message 120. It may occur in any order prior to.

The countdown at the station can be stopped based on the receipt of one or more additional messages. For example, after deciding to send message 120, the second station 106 may initiate a countdown from the countdown value 142, as described above. During the countdown (eg, before the countdown reaches zero), the second station 106 may receive additional messages. For example, the second station 106 may receive additional messages and a third neighbor list from stations within the one-hop range 152 of the second station 106. In a non-limiting example, the second station 106 may receive a second message 122 containing a third neighbor list (List_3) 134 and a second identifier 126 from the third station 108. The second identifier 126 may be the same as the first identifier 124 contained in the message 120 (for example, the second message 122 may be the message 120 transferred or rebroadcast from the third station 108. Good). The second station 106 can compare the second neighbor list 132 with the third neighbor list 134, as described above. In response to determining that each station identified by the second neighbor list 132 is also identified by the third neighbor list 134, the second station 106 may decide not to send the message 120. This decision can occur before the countdown reaches zero, or when the countdown reaches zero. The second station 106 may stop the countdown if no other message is pending transmission / transfer at the second station 106. However, if one or more messages are pending sending / forwarding, the countdown may continue. Therefore, each device can implement a single countdown for all group-addressed messages.

In certain implementations, the second station 106 can perform a separate countdown for each message with a different identifier. For example, if the second identifier 126 contained in the second message 122 is different from the first identifier 124 contained in the message 120, station 106 processes the second message 122 as described above. Can (including initiating a second countdown from a second value). In an alternative implementation, the second station 106 may perform a single countdown (eg, using a single timer) for multiple messages. As a non-limiting example, the second message 122 may differ from message 120. The second identifier 126 can be different from the first identifier 124. The second station 106 may be configured to determine if at least one station identified by the second neighbor list 132 is not identified by the third neighbor list 134. In response to determining that at least one station is not identified by the third neighbor list 134, the second station 106 decides to send a second message 122 when the second countdown is complete. Good. For example, when the countdown reaches zero, the second station 106 can send both message 120 and message 122. The second neighbor list 132 may be encoded or attached to each of the transfer copies of message 120 and the second message 122, as described above. Therefore, a single countdown can be used to send multiple messages (eg, messages with different identifiers).

In certain implementations, the MWT value 146 may be determined separately for each station and may differ for one or more of stations 104-114. For example, the second station 106 may be configured to determine the MWT value 146 based on the number of neighboring stations of the second station 106. As mentioned herein, the Degree (A) function returns the number of neighboring stations in argument A (eg, a particular station). In this implementation, the second station 106 may be configured to use the Degree () function to determine the number of its neighbors and to determine the MWT value 146 based on the reciprocal of the result. .. Therefore, the MWT value 146 can be inversely proportional to the number of stations adjacent to the second station 106 (eg, the number of stations identified by the second neighbor list 132). Determining the MWT value 146 based on the number of neighboring stations can reduce the overall power consumption of the wireless network 102. For example, a station within a hop range of many stations may have a lower MWT value than a station within the range of a few stations, sending a message (and reaching a larger number of neighbors). ) May be more probable, which reduces the total number of stations sending messages and the overall power consumption associated with message propagation.

In certain implementations, the MWT value 146 can be determined based on whether a particular station is a "new" member of wireless network 102 (eg, recently joined). For example, the second station 106 determines a lower value for the MWT value 146 (for example, a value lower than the MWT values of other stations) when the second station 106 first joins the wireless network 102. It may be configured as follows. Therefore, the second station 106 may be more likely to transmit a received message, such as message 120, when the second station 106 first joins the wireless network 102. Determining a lower MWT value for the "new" station allows the "new" station to announce their presence to other stations within the wireless network 102. In addition, fairness can be increased by having the second station 106 first contribute to the transfer of messages within the wireless network 102.

As an addition or alternative, the second station 106 can generate a countdown value 142 by selecting a countdown value 142 from the range between the minimum wait time (mWT) value 148 and the MWT value. The mWT value 148 can be determined based on the received signal strength of message 120. For example, the second station 106 may be configured to determine the received signal strength indication (RSSI) 160 for the message 120 received from the first station 104. The second station 106 may be further configured to select a countdown value 142 from the range between the mWT value 148 and the MWT value 146 in response to RSSI 160 exceeding the threshold. In certain implementations, the mWT value 148 may be a pre-generated value greater than zero and the same for each of stations 104-114. Alternatively, the mWT value 148 may be determined separately by stations 104-114 based on the station-specific RSSI 160. Choosing a countdown value 142 from the range between mWT value 148 and MWT value 146 rather than from the range between zero and MWT value 146 reduces the likelihood that a particular station will send message 120. For example, RSSI160 can be higher when a particular station is near the source of message 120 (eg, first station 104). Therefore, a reduced likelihood of transmission based on a high RSSI allows stations located near the source of the message to remain silent longer. By doing so, stations located near the source are likely to be within one hop of a few additional stations that are not within the source's range, which can increase efficiency in dense wireless networks.

In a particular implementation, the second station 106 generates a countdown value 142 by selecting a countdown value 142 from a range between the mWT value 148 and the MWT value 146, based on the channel power of message 120. be able to. For example, the second station 106 may be configured to determine the receive channel power indication (RCPI) 162 for message 120 received from the first station 104. The second station 106 may be further configured to select a countdown value 142 from a range between the mWT value 148 and the MWT value 146 in response to RCPI 162 exceeding the threshold. In certain implementations, the mWT value 148 may be a pre-generated value greater than zero and the same for each of stations 104-114. Alternatively, the mWT value 148 may be individually determined by stations 104-114 based on station-specific RCPI. The choice of countdown value 142 based on RCPI can provide benefits similar to those described above in dense wireless networks.

As an addition or alternative, the second station 106 may be configured to determine if a particular time interval 144 has elapsed. The particular time interval 144 does not have to be randomly selected and does not depend on the countdown from the random or pseudo-randomly selected countdown value 142 described above. The second station 106 is configured to monitor the number of messages sent during a particular time interval 144 and to determine if at least one message was sent during a particular time interval 144. Good. In response to determining that zero messages have been sent during a particular time interval 144, the second station 106 may send a received message, such as message 120, and a second neighbor list 132. In certain implementations, the second station 106 may be an edge station or a border station (eg, a station located at the edge of wireless network 102). The presence of the wireless network 102 can be signaled to the "external" station by sending a message 120 containing a second neighbor list 132. In addition, if you send message 120 (including the second neighbor list 132) when no message has been sent during a particular time interval 144, then the edge or border station (for example, by sending message 120) ) You can be sure that you are involved in message transfer. After a particular time interval 144 has elapsed, the process described above may be repeated for each subsequent time interval.

In a particular implementation, each station may be configured to decide whether to remove a station from wireless network 102 based on the station's contribution. For example, the sixth station 114 may be configured to monitor the number of messages received from the fifth station 112 over a period of time. The sixth station 114 can maintain the number of messages received from the fifth station 112 and the transmission count 164 of the fifth neighbor list 138 during that time period. The sixth station 114 may be further configured to determine whether to transmit the network key 166 to the fifth station 112 based on the count 164. For example, network key 166 can be used by stations 104-114 to encrypt a message prior to sending it, or to decrypt an incoming message. When the sixth station 114 receives the network key 166 from another station, the sixth station 114 may decide whether to transmit the network key 166 to the fifth station 112. The sixth station 114 may send the network key 166 to the fifth station 112 in response to determining that the number of messages (eg, count 164) exceeds the threshold. The threshold may represent the desired minimum contribution level of each station to message propagation in wireless network 102.

The sixth station 114 may suppress the transmission of the network key 166 to the fifth station 112 in response to determining that the number of messages (eg, count 164) does not exceed the threshold. Suppressing the transmission of the network key 166 causes the fifth station 112 to encrypt the message without the network key and to send or decrypt the received message, so the wireless network 102 to the fifth station 112 It can be effectively deleted. In an alternative implementation, the sixth station 114 may decide whether to send the network key 166 to the fifth station 112 based on whether the score corresponding to the fifth station 112 exceeds the threshold score. it can. The score may be at least partially based on the number of messages received from the fifth station 112. Scores are other scoring criteria corresponding to station 112, such as proximity to source, network seniority, length of time in wireless network 102, historical transmission data, and other factors. Can also be based on.

During operation, the second station 106, the third station 108, and the sixth station 114 may receive the message 120 and the first neighbor list 130 from the first station 104, respectively, and the first neighbor. Based on Listing 130, you can decide whether to send (for example, forward or rebroadcast) message 120. For example, stations 106, 108, and 114 can compare their own neighbor list with the first neighbor list 130, as described above. In the example shown in FIG. 2, each of stations 106, 108, and 114 is at least one identified by a second neighbor list 132, a third neighbor list 134, or a sixth neighbor list (List_6) 140, respectively. It determines that one station is not identified by the first neighbor list 130. In response, stations 106, 108, and 114 may decide to send message 120 and may initiate a station-specific countdown from a randomly generated countdown value.

In the first time, the second station 106 may complete the countdown. In response to completing the countdown, the second station 106 sends message 120 and the second neighbor list 132 to the third station 108, the fourth station 110, and the first station 104 (eg, the first station 104). It may be transmitted to a neighboring station) within the 1-hop range 152 of the 2 stations 106. Since the first station 104 has already transmitted the message 120, the first station 104 may discard the message 120. In the second time following the first time, the sixth station 114 may complete the countdown. The sixth station 114 puts the message 120 and the sixth neighbor list 140 within the third station 108, the fifth station 112, and the first station 104 (eg, within one hop range 154 of the sixth station 114). You may send it to a nearby station). Since the first station 104 has already transmitted the message 120, the first station 104 may discard the message 120.

The third station 108 may receive the second neighbor list 132 and the sixth neighbor list 140 (with the transmission of the message 120) from the second station 106 and the sixth station 114, respectively. The third station 108 can compare the third neighbor list 134 with the second neighbor list 132, the sixth neighbor list 140, or a combination thereof. In response to determining that each station identified by the third neighbor list 134 is also identified by the second neighbor list 132, the sixth neighbor list 140, or a combination thereof, the third station 108 May suppress the transmission of message 120. In some implementations, the decision to suppress transmission can be made when the countdown reaches zero. In other implementations, the decision to suppress transmission can be made before the countdown reaches zero (eg, prior to completion). In addition, the third station 108 may stop the countdown prior to completion if no other message is pending transmission / transfer at the third station 108. In an alternative implementation, the third station 108 may complete the countdown prior to the second station 106 and the sixth station 114, sending a second message 122 and a third neighbor list 134 to neighboring stations. You can do it. In this implementation, the second station 106 may suppress the transmission of the message 120 based on the comparison between the second neighbor list 132 and the third neighbor list 134, and the sixth station 114 may suppress the transmission of the message 120. The transmission of message 120 may be suppressed based on a comparison between the sixth neighbor list 140 and the third neighbor list 134.

Each station contributes to message propagation by using a randomly generated countdown value (for example, a randomly selected value from one or more ranges) or a countdown from a pseudo-randomly selected countdown value. You may have the opportunity to save power by doing so or by suppressing the transmission of messages. In this way, each station has a random or pseudo-random chance to send an incoming message, thus facilitating fairness between stations in the wireless network 102. Therefore, the maximum power consumption of each station related to message propagation can be reduced fairly.

FIG. 3 shows a timing diagram 300 of a first exemplary example of message and station specific neighbor list transmission in a wireless network. Timing diagram 300 shows communication between three stations in the wireless network, such as stations 104 to 108 in FIGS. 1 to 2. In the example of FIG. 3, the stations are such that the second station (STA_2) 106 and the third station (STA_3) 108 are adjacent to the first station (STA_1) 104, and the third neighbor list (List_3). 134 can be arranged to be a subset of the second neighbor list (List_2) 132.

At the first time (t1), the second station 106 and the third station 108 each receive a message and a first neighbor list (List_1) 130 from the first station 104. The first neighbor list 130 may identify the second station 106 and the third station 108 as neighbors of the first station 104. The second station 106 may determine that at least one station identified by the second neighbor list 132 is not identified by the first neighbor list 130, as described with reference to FIG. The countdown may be started at station 106 of. Further, the third station 108 may determine that at least one station identified by the third neighbor list 134 is not identified by the first neighbor list 130, as described with reference to FIG. The countdown may be started at the third station 108.

At the second time (t2), the countdown at the second station 106 reaches zero. Therefore, in the example of timing diagram 300, the countdown value generated by the second station 106 (eg, a random / pseudo-random value selected from one or more ranges) was generated by the third station 108. Lower than the countdown value. In response to completing the countdown, the second station 106 sends a message and a second neighbor list 132 (eg, forwards or rebroadcasts) to its neighbors. In a particular implementation, the second station 106 can be a neighbor of the third station 108.

At the third time (t3), the third station 108 receives the message and the second neighbor list 132 from the second station 106 and compares the third neighbor list 134 with the second neighbor list 132. .. Each station identified by the third neighbor list 134 (as explained above) is also a neighbor of the second neighbor list 132 (for example, each neighbor of the third station 108 is also a neighbor of the second station 106). ) Or in response to determining that it is also identified by the first neighbor list 130, the third station 108 sends / forwards any other message, as described with reference to FIG. Stop the countdown (when not on hold) and suppress the sending of messages. The comparison between the first neighbor list 130 and the third neighbor list 134 is described as occurring at time t1, but in another implementation the comparison may occur at time t3 and at times t1 and t3. It may happen.

FIG. 4 shows a timing diagram 400 of a second exemplary example of message and station specific neighbor list transmission in a wireless network. Timing FIG. 400 shows communication between three stations in a wireless network, such as stations 104-108 of FIGS. 1-2. In the example of FIG. 4, the stations are such that the second station (STA_2) 106 and the third station (STA_3) 108 are adjacent to the first station (STA_1) 104, and the second neighbor list (List_2). 132 may be arranged to identify at least one station that is not identified by the third neighbor list (List_3) 134. The example of FIG. 4 also differs from the example of FIG. 3 in that the third station 108 produces a lower countdown value than the second station 106.

At the first time (t1), the second station 106 and the third station 108 operate as described with reference to the first time (t1) of FIG. At the second time (t2), the countdown at the third station 108 reaches zero. In response to completing the countdown, the third station 108 sends a message and a third neighbor list 134 to its neighbors (eg, forwards or rebroadcasts). In a particular implementation, the second station 106 can be a neighbor of the third station 108.

At the third time (t3), the second station 106 receives the message and the third neighbor list 134 from the third station 108 and compares the second neighbor list 132 with the third neighbor list 134. .. At least one station identified by the second neighbor list 132 is the third neighbor list 134 (for example, at least one neighbor of the second station 106 is not a neighbor of the third station 108) or the first The second station 106 continues the countdown in response to the determination by the neighbor list 130 that it is not identified (as explained above). The comparison between the first neighbor list 130 and the second neighbor list 132 is described as occurring at time t1, but in another implementation the comparison may occur at time t3 and at times t1 and t3. It may happen.

At the fourth time (t4), the countdown at the second station 106 reaches zero. In response to completing the countdown, the second station 106 sends a message and a second neighbor list 132 to its neighbors.

Referring to FIG. 5, an exemplary method of sending a message and a neighbor list in a wireless network is described and is specified by 500. Method 500 can be implemented using stations 104-114 and the wireless network may include or correspond to the wireless network 102 of FIGS. 1-2.

Method 500 may include, at 502, the step of generating a first neighbor list at the first station of the wireless network. For example, the first neighbor list may include or correspond to the first neighbor list 130, and the first station may include or correspond to the first station 104 of FIG. .. The first neighbor list may identify one or more stations within a particular range of the first station. In certain implementations, the particular range is the one-hop range of the first station, such as the one-hop range 150 in FIG.

Method 500 may further include in 504 a step of transmitting a first message, including a first neighbor list, to a second station on the wireless network. For example, the first message may include or correspond to message 120, and the second station may include or correspond to the second station 106 of FIG. In certain implementations, the first neighbor list may be encoded in the message. As an addition or alternative, the first message may include a multicast message. In certain implementations, the neighbor list may be a multicast-specific neighbor list. The multicast-specific neighbor list may include a subset of stations within a particular range of the first station. In another particular implementation, the first message may include a broadcast message. As an addition or alternative, the message may include a unique identifier, such as the first identifier 124 in FIG. In another particular implementation, the second station may be identified in the first neighbor list. Alternatively, the second station may not be identified in the first neighbor list.

Method 500 may allow the first station to send messages and neighbor lists to the station for use in selective transmission (eg, forwarding) of messages.

With reference to FIG. 6, an exemplary method of selectively transmitting messages and neighbor lists in a wireless network is described and is specified at 600. Method 600 can be implemented using stations 104-114 and the wireless network may include or correspond to the wireless network 102 of FIGS. 1-2.

Method 600 may include in 602 a step of receiving a message from a first station in the wireless network to a second station in the wireless network, including a first neighbor list. For example, the first station may include or correspond to the first station 104, the second station may include or correspond to the second station 106, and the message is a message. It may include or correspond to 120, and the first neighbor list may include or correspond to the first neighbor list 130 of FIGS. 1-2. In certain implementations, method 600 may be performed after method 500 of FIG. 5, and the received message may have a different identifier than the first message described with reference to FIG.

Method 600 selectively sends a copy of the message and the second neighbor list to another station on the wireless network in 604, based on a comparison between the first neighbor list and the second neighbor list. Can be further included. The second neighbor list can be generated by the second station. For example, the second neighbor list may include or correspond to the second neighbor list 132 of FIGS. 1-2. In certain implementations, the first neighbor list can identify one or more stations within a hop range of the first station, and the second neighbor list is one of the second stations. It can identify one or more stations within the hop range.

In certain implementations, the second station compares the first neighbor list to the second neighbor list, and at least one station identified by the second neighbor list is not identified by the first neighbor list. You can judge whether or not. The second station may suppress the transmission of copies of the message in response to determining that each station identified by the second neighbor list is also identified by the first neighbor list (eg, transmission). You may decide not to do so). As an addition or alternative, in response to the second station determining that the second station has already sent another message with the same unique identifier as the message over a period of time, a copy of the message Transmission may be suppressed (for example, it may be decided not to transmit). In a particular implementation, the second station can store an identifier corresponding to each message sent by the second station during the time period in a buffer such as buffer 168 of FIG. The duration of the time period can be determined based on the end-to-end delay of the wireless network. For example, the duration of the time period can be determined based on the end-to-end delay of the wireless network 102 of FIGS. 1-2.

As an addition or alternative, the second station was generated in the second station in response to determining that at least one station identified by the second neighbor list is not identified by the first neighbor list. A countdown from a specific value can be initiated. In certain implementations, the second station can generate a particular value by randomly selecting a particular value from the range between the zero value and the maximum latency (MWT) value. For example, referring to FIG. 2, the second station 106 can generate a countdown value 142 by randomly selecting a countdown value 142 from the range between zero and the MWT value 146. The second station may send a copy of the message containing the second neighbor list in response to the countdown reaching zero. For example, referring to FIG. 2, the second station 106 can initiate a countdown with a countdown value 142, and in response to the countdown reaching zero, a message containing the second neighbor list 132. You can send (for example, transfer) 120. In certain implementations, the MWT value may be the same for each station in the wireless network.

As an addition or alternative, the second station may receive a second message and a third neighbor list from the third station in the wireless network prior to the countdown reaching zero. For example, referring to FIG. 2, the second station 106 may receive a second message 122 including a third neighbor list 134 from the third station 108. The second station may determine that the first and second messages have the same identifier. For example, the second station 106 may receive the second message 122 and determine that the first identifier 124 and the second identifier 126 are the same. The second station may determine if at least one station identified by the second neighbor list is not identified by the third neighbor list, in response to the countdown reaching zero, and the second. A copy of the second message and a second neighbor list may be sent, provided that at least one station identified by the neighbor list is determined not to be identified by the third neighbor list. For example, the second station 106 may send message 120 (eg, a copy of the message received from the first station 104). As an addition or alternative, the second station may receive a second message and a third neighbor list from the third station in the wireless network prior to the countdown reaching zero. The second message and the message can have the same unique identifier. For example, the first identifier 124 and the second identifier 126 may be the same. The second station can determine if at least one station identified by the second neighbor list is not identified by the third neighbor list, and the second station is identified by the second neighbor list. In response to each station determining that it is also identified by the third neighbor list, it may decide not to send a copy of the second message. The second station has a second message before the countdown reaches zero, or when the countdown reaches zero. You may decide not to send a pee. In certain implementations, the second station may stop the countdown prior to completion when no other message is pending transmission / transfer.

In another particular implementation, the second station can determine the number of stations identified by the second neighbor list and determine the MWT value based on the number of stations. For example, an MWT value, such as the MWT value 146 in Figure 2, can be inversely proportional to the number of stations.

In another particular implementation, the second station determines the received signal strength indicator (RSSI) for the message and responds to the RSSI exceeding the threshold with a minimum latency (mWT) value and a maximum latency. A specific value can be randomly selected from the range between the (MWT) value. For example, referring to FIG. 2, the second station 106 randomly selects a countdown value 142 from the range between the mWT value 148 and the MWT value 146 in response to RSSI 160 exceeding the threshold. A countdown value of 142 can be generated. In certain implementations, the mWT value may be greater than zero and may be the same for each station in the wireless network. Alternatively, the second station can determine the mWT value based on RSSI. As an addition or alternative, the second station can determine the receive channel power indication (RCPI) for the message, from the range between the mWT and MWT values in response to the RCPI exceeding the threshold. Specific values may be randomly selected. For example, referring to FIG. 2, the second station 106 randomly selects a countdown value 142 from the range between the mWT value 148 and the MWT value 146 in response to RCPI 162 exceeding the threshold. A countdown value of 142 can be generated. In certain implementations, the second station can determine the mWT value based on RCPI.

In another particular implementation, the second station can determine if the second station has sent at least one message during a particular time interval. For example, referring to FIG. 2, the second station 106 can determine if at least one message was sent during a particular time interval 144. The second station may send a message containing the second neighbor list in response to determining that the second station has not sent at least one message during a particular time interval.

Method 600 may allow selective transmission or suppression of messages at stations within a wireless network.

With reference to FIG. 7, an exemplary method of selectively deleting stations in a wireless network is described and is designated by 700. Method 700 can be implemented using stations 104-114 and the wireless network may include or correspond to the wireless network 102 of FIGS. 1-2.

Method 700 may include, at 702, monitoring the number of messages received from the first station of the wireless network to the second station of the wireless network over a period of time. For example, referring to FIG. 2, the sixth station 114 can monitor the count 164 of the number of messages received from the fifth station 112.

Method 700 may further include in 704 the step of deciding whether to send the network key to the first station based on the number of messages. For example, referring to FIG. 2, the sixth station 114 can determine whether to transmit the network key 166 to the fifth station 112 based on the count 164. In a particular implementation, each message received from the first station may include a neighbor list corresponding to the first station. In another particular implementation, the second station may decide to send the network key to the first station in response to the number of messages exceeding the threshold. As an addition or alternative, the second station may decide to send the network key to the first station in response to the score corresponding to the second station exceeding the threshold. Scores can be based on the number of messages, or at least partially based on other scoring criteria, as described with reference to Figure 2. As an addition or alternative, the second station may suppress the transmission of the network key to the first station in response to the number of messages not exceeding the threshold (eg, it may decide not to send). ).

Method 700 may allow the first station to selectively remove the second station from the wireless network by selectively transmitting a network key based on the number of messages received from the second station. ..

With reference to FIG. 8, certain exemplary embodiments of wireless communication devices are shown, all designated by 800. Device 800 includes a processor 810, such as a digital signal processor, coupled to memory 832. In an exemplary implementation, device 800, or its components, may correspond to stations 104-114 of FIGS. 1-2, or components thereof.

Processor 810 may be configured to execute software stored in memory 832 (eg, a program consisting of one or more instructions 868). As an addition or alternative, processor 810 may be configured to implement one or more instructions stored in the memory of a wireless interface 840 (eg, an IEEE 802.11 interface). For example, wireless interface 840 may be configured to operate according to the IEEE 802.11s standard. In a particular implementation, processor 810 may be configured to operate according to one or more of the methods of FIGS. 5-7. For example, processor 810 may include message transmission logic 864 to perform one or more of the methods of FIGS. 5-7. Processor 810 may also be configured to generate and store neighbor lists 870 for device 800. In an exemplary implementation, the neighbor list 870 can identify one or more neighbors of device 800 in the wireless network 102 of FIGS. 1-2.

Wireless interface 840 may be coupled to processor 810 and antenna 842. For example, wireless interface 840 may be coupled to antenna 842 via transceiver 846, just as wireless data received via antenna 842 may be provided to processor 810.

The coder / decoder (codec) 834 can also be coupled to the processor 810. Speaker 836 and microphone 838 may be coupled to codec 834. The display controller 826 may be coupled to the processor 810 and the display device 828. In certain implementations, the processor 810, display controller 826, memory 832, codec 834, and wireless interface 840 are included within a system-in-package or system-on-chip device 822. In certain implementations, the input device 830 and power supply 844 are coupled to the system-on-chip device 822. Moreover, in a particular implementation, the display device 828, the input device 830, the speaker 836, the microphone 838, the antenna 842, and the power supply 844 are outside the system-on-chip device 822, as shown in FIG. However, each of the display device 828, input device 830, speaker 836, microphone 838, antenna 842, and power supply 844 is in one or more components of the system-on-chip device 822, such as one or more interfaces and controllers. Can be combined.

In connection with the implementations described, the first apparatus comprises means for generating a first neighbor list in a first station of a wireless network, wherein the first neighbor list is a first. Identify one or more stations within a particular range of stations. For example, the means to generate are stations 104-114 of FIGS. 1-21, wireless interface 840 of FIG. 8, processor 810 programmed to execute instruction 868, message transmission logic 864, first of the wireless network. Can include other devices, circuits, modules, or instructions, or any combination thereof for generating a neighbor list in a station.

The first device also includes means for transmitting a first message containing the first neighbor list to a second station on the wireless network. For example, the means for transmitting are stations 104 to 114 in FIGS. 1 to 2, wireless interface 840 in FIG. 8, processor 810 programmed to execute instruction 868, message transmission logic 864, and a message including a neighbor list. Can include other devices, circuits, modules, or instructions, or any combination thereof for transmitting to a second station in the wireless network.

In connection with the implementation described, the second device includes means for receiving a message and a first neighbor list from the first station of the wireless network at the second station of the wireless network. For example, the means for receiving are stations 104 to 114 in FIGS. 1 to 2, wireless interface 840 in FIG. 8, processor 810 programmed to execute instruction 868, message transmission logic 864, and a second wireless network. Can include other devices, circuits, modules, or instructions, or any combination thereof for receiving messages and first neighbor lists from the first station of the wireless network at the station.

The second device is a means for selectively transmitting a message and a second neighbor list to another station in the wireless network based on a comparison between the first neighbor list and the second neighbor list. Also included, where the second neighbor list is generated by the second station. For example, the means for selective transmission are stations 104 to 114 in FIGS. 1 to 2, wireless interface 840 in FIG. 8, processor 810 programmed to execute instruction 868, message transmission logic 864, first. Other devices, circuits, modules, or other devices, circuits, modules, or for selectively sending messages and the second neighbor list to another station in the wireless network, based on a comparison between the neighbor list and the second neighbor list. It may include instructions, or any combination thereof.

In connection with the implementation described, the third device provides a means for monitoring the number of messages received from the first station of the wireless network to the second station of the wireless network over a period of time. Including. For example, the means for monitoring are stations 104-114 in Figures 1 and 2, wireless interface 840 in Figure 8, processor 810 programmed to execute instruction 868, message transmission logic 864, and during a period of time. , Other devices, circuits, modules, or instructions for monitoring the number of messages received from the first station of the wireless network to the second station of the wireless network, or any combination thereof.

The third device also includes means for deciding whether to send the network key to the first station based on the number of messages. For example, the means for determining are based on stations 104-114 in FIGS. 1-21, wireless interface 840 in FIG. 8, processor 810 programmed to execute instruction 868, message sending logic 864, and number of messages. It may include other devices, circuits, modules, or instructions, or any combination thereof for deciding whether to send a network key to a second station.

Those skilled in the art will further perform various exemplary logical blocks, configurations, modules, circuits, and algorithm steps described in connection with the implementations disclosed herein by electronic hardware, processors. It will be appreciated that it may be implemented as computer software, or a combination of both. Various exemplary components, blocks, configurations, modules, circuits, and steps are generally described above in terms of their functionality. Whether such functionality is implemented as hardware or processor executable instructions depends on the specific application and design constraints imposed on the entire system. Those skilled in the art may implement the described functionality in various ways for each particular application, but decisions on such implementation should be construed as causing deviations from the scope of this disclosure. Absent.

The steps of the method or algorithm described in connection with the disclosure herein may be implemented directly in hardware, in a software module executed by a processor, or in combination of the two. Software modules include random access memory (RAM), flash memory, read-only memory (ROM), programmable read-only memory (PROM), erasable programmable read-only memory (EPROM), and electrically erasable programmable read-only memory. (EEPROM), register, hard disk, removable disk, compact disk read-only memory (CD-ROM), or any other form of non-short-term (eg, non-temporary) storage medium known in the art. You may. An exemplary storage medium is coupled to the processor so that the processor can read information from and write information to the storage medium. Alternatively, the storage medium may be integrated with the processor. Processors and storage media can reside within application specific integrated circuits (ASICs). The ASIC can reside within the computing device or user terminal. Alternatively, the processor and storage medium can exist as separate components within the computing device or user terminal.

The above description is provided to allow those skilled in the art to make or use the disclosed implementations. Various modifications to these implementations will be readily apparent to those of skill in the art and the principles defined herein may apply to other implementations without departing from the scope of the present disclosure. is there. Therefore, the present disclosure is not limited to the implementations shown herein, but should be given the widest possible range consistent with the principles and novel features defined by the claims below.

100 systems 102 Wireless network 104 First station (STA_1), station 106 Second station (STA_2), station 108 Third station (STA_3), station 110 4th station (STA_4), station 112 5th station (STA_5), station 114 6th station (STA_6), station 120 messages 122 Second message 124 First identifier 126 Second identifier 130 First Neighbor List (List_1) 132 Neighbor list, second neighbor list (List_2) 134 Neighbor List, Third Neighbor List (List_3) 136 Neighbor List 138 Neighbor List, Fifth Neighbor List 140 Neighbor List, 6th Neighbor List (List_6) 142 countdown value 144 hour intervals 146 MWT value 148 Minimum wait time (mWT) value 150 1 hop range 152 1 hop range 154 1 hop range 160 Received signal strength indication (RSSI) 162 Receive Channel Power Instruction (RCPI) 164 count 166 Network key 168 buffer 800 devices 810 processor 822 System on Chip Device 826 display controller 828 display device 830 input device 832 memory 834 Coda / Decoder (Codec) 836 speaker 838 microphone 840 wireless interface 842 antenna 844 power supply 846 transceiver 864 Message sending logic 868 instructions 870 Neighbor List