Method and system for data collision avoidance in a wireless communications system

[0001] This application is related to co-pending U.S. patent application Ser. No. 10/027,444 entitled “Resume Message Protocol For A Wireless Communications System,” invented by Robert G. McFarland, Justin C. Thomas, and Stephen E. Enke, said application being filed concurrently herewith and incorporated by reference herein in its entirety.

[0002] The invention relates to communications, and more particularly, to a method and apparatus for minimizing or avoiding the simultaneous transmission of data by multiple data sources over a single-channel, wireless communications system.

[0003] Single-channel wireless communications networks are relatively simple to operate and provide an efficient method for a finite number of participants to exchange data. A common network structure is to permit one participant, or node, to establish a link over the channel to communicate with another participant, or node. Several data packets, separated by brief breaks, may be exchanged between the two nodes until one of the nodes sends a packet including the command to terminate the link. Another node may then attempt to establish another link. This arrangement is currently being used to communicate STANAG 5066 data over a single-channel wireless HF network.

[0004] The sequential arrangement of establishing links between nodes is satisfactory when none of the nodes in the wireless network are sending a high volume of information, or if there are few nodes in the network. With the addition of a higher volume of information and/or a increased number of nodes, it is likely that multiple nodes will wish to establish links at the same time. It may be difficult to determine which node should establish the next link over the channel when the previous link is terminated.

[0005] Another problem encountered in known wireless networks is the timing of the attempts by non-linked nodes to establish new links. Nodes in known wireless networks are configured to attempt to establish a new link over the channel as soon as no activity on the channel is detected. However, as explained above, each link includes non-terminating breaks between data packets. An attempt by a node to establish a new link based on the non-terminating breaks included in the current link causes multiple nodes to transmit data simultaneously. This situation, known as a collision of data, causes data loss in the current link and continuously frustrates nodes that are attempting to establish a link over the channel.

[0006] It is therefore an object of the invention to provide a method for coordinating establishment of data links over a single-channel wireless network.

[0007] It is another object of the invention to prevent the collision of data over a wireless network.

[0008] It is still another object of the invention to allow for the inclusion of nodes in a wireless network that may not possess the necessary means to be subject to any coordination measures imposed on the other nodes in the network.

[0009] A feature of the invention is the reduced occurrence of data collision.

[0010] Another feature of the invention is the ordered determination of the establishment of data links over the channel.

[0011] An advantage of the invention is the reduced occurrence of data collision.

[0012] Another advantage of the invention is the establishment of data links in an orderly fashion.

[0013] The invention provides a method of transmitting data over a single-channel wireless network having a plurality of nodes. According to the invention, a first link is established between two of the nodes and data is transmitted therebetween. A break in transmission between the two nodes is listened for, and a first predetermined time interval is waited if a break in transmission between two nodes occurs. A second predetermined time interval is established if the first predetermined time interval lapses with no detected transmission over the channel. The second predetermined time interval is divided into a plurality of slots, and each node randomly selects one of the slots. One of the nodes establishes a second link if that node has selected a slot earlier in time than slots selected by the remainder of the nodes.

[0014] The invention also provides a single-channel, wireless network. The network includes a plurality of nodes capable of receiving and transmitting data across the network A single link between two of the plurality of nodes can be established at any time. Each link includes a plurality of sequential data packets separated by non-terminating breaks in transmission. Each node includes a listening structure that substantially continuously monitors communications on the channel and initiates a contention interval when no communication has been detected on the channel for a first predetermined time. The contention interval is divided into a predetermined number of slots. A selection structure randomly selects one of the predetermined number of slots. The node that has selected a slot that is earlier in time than slots selected by other nodes is permitted to establish a link.

[0015] The invention further provides a method of avoiding the simultaneous transmission of data from a plurality of data sources over a single wireless channel, wherein each data source is operationally connected to a means for wireless communication over the network. The method includes: establishing a first wireless link between first and second data sources selected from the plurality of data sources and transmitting data therebetween; listening, via the wireless communication means, for a break in transmission between the first and second data sources; waiting for a first predetermined time interval if a break in transmission between the first and second data sources occurs; establishing a second predetermined time interval if the first predetermined time interval lapses with no detected transmission over the channel; dividing the second predetermined time interval into a plurality of slots, wherein each data source randomly selects one of the slots, wherein the wireless communication means operationally connected to one of the plurality of data sources establishes a second link if said one of the plurality of data sources has selected a slot earlier in time than slots selected by the remainder of the data sources.

[0016] The invention further provides a method of transmitting data over a single-channel wireless multi-node network. A first link is established between first and second nodes selected from the plurality of nodes, and data is transmitted therebetween. A link termination message is listened for, and a predetermined time interval is established when the link termination message is detected. The predetermined time interval is divided into a plurality of slots, wherein each node randomly selects one of the slots. One of the nodes establishes a second link if that node has selected a slot earlier in time than slots selected by the remainder of the nodes.

[0029] Turning now to the drawings, in which like reference numbers designate like components, an embodiment of the invention is schematically shown in FIG. 1. A wireless communications network 10 includes a plurality of nodes, which are identified by the letters A, B, C, . . . n. Each node includes a computer 12, which may include a processor, memory, a display, and other components. Computer 12 also includes software that controls the transmission and reception of data, such as HF Messenger™, manufactured by Rockwell Collins, Inc. of Cedar Rapids, Iowa. Computer 12 may be considered a data source, or may be operationally connected to an external data source (not shown).

[0030] Computer 12 is connected to a wireless communications module 14, which includes a modem 16. Modem 16 converts data from computer 12 into a commonly accepted communications format and converts information in the communications format into a format useable by computer 12. The output of modem 16 is sent to a radio 18, which, through antenna 20, transmits and receives data over a wireless network. In the present invention, the radios in all nodes A, B, C, . . . n transmit over a single channel. A node, such as node A for example, attempts to establish a link with another node, such as node B, if it detects no data being transmitted over the channel. FIG. 2 schematically depicts a link 22 between node A and node B. Link 22 includes individual data packets 24 transmitted between the two nodes, with breaks 26 between the packets. Because nodes in known single-channel wireless communications networks will attempt to transmit data when any break 26 in link 22 is detected, link 22 is constantly interrupted, and a loss in data transmission integrity is encountered.

[0031] FIG. 3 depicts a method 30 for reducing interruptions in data links in a single-channel wireless network according to the invention. In step 32, each node is programmed to listen on the channel for any transmitting activity. In step 34, each node detects whether there is any activity on the channel. If there is activity on the channel, each node is programmed to return to step 32 and continue to listen. If the channel is idle, a predetermined interval is initiated in step 36. This predetermined interval is termed the Listen Before Transmitting (LBT) interval. The LBT interval is set to last longer than the longest break between packets in a link. If, in step 38, transmission activity is detected on the channel, the nodes are programmed to return to a listening state (step 32) after resetting the LBT interval to zero. If no transmission activity is detected on the channel for the duration of the LBT interval (step 40), it is safe to assume that the existing link has terminated. This process is graphically shown in FIG. 4, where successive LBT intervals are identified with reference numerals 50a–e. When a break 26 is detected between packets 24 in link 22, each node initiates LBT interval 50. However, when a successive packet 24 is detected, LBT interval 50 is reset, as shown by the dashed lines 52a–d on LBT intervals 50a–d, and each node continues to listen for another break. When LBT interval 50e expires at time 52e without activity being detected on the channel, it can then be assumed that link 22 has indeed terminated, and that it is safe for any node to attempt to establish another link.

[0032] Returning to FIG. 3, at step 42 each node on the network initiates or establishes a contention interval 54 having a predetermined length. As shown in FIGS. 4 and 5, contention interval 54 is divided into a predetermined number of slots 56. In step 44 (FIG. 3), each node randomly selects one of the slots and waits until its selected slot to begin transmitting to establish a link. The node that has randomly selected the earliest slot has permission to transmit first (step 48), and all other nodes return to the beginning of the method (step 49). For example, if three nodes randomly select slots 3, 4, and 7 respectively (FIG. 5), the node that selected slot 3, which in this instance is the ‘winning’ slot because it is the first occurring selected slot, will begin establishing a link before the other two nodes are scheduled to do so, and those other nodes must again wait (according to method 30) until that link is terminated to again attempt to establish a link. By using method 30, the likelihood of conflicting transmissions on a single wireless channel is significantly reduced.

[0033] The invention may be arranged such that all nodes select a slot even if some of the nodes do not have a message to send. In such an arrangement, the node obtaining a winning slot and having a message to send will be the first to attempt to establish a link.

[0034] The number of slots 56 must be large enough to ensure a low probability of two or more nodes randomly selecting the same winning slot but not so large as to cause large delay times. It does not matter if two or more nodes choose the same non-winning slot because the node choosing the winning slot will always begin transmitting first. The following formula can be used to determine the number of slots (Equation 1):
P=[(n/(s^n))*(((s−1)^(n−1))+((s−2)^(n−1))+((s−3)^(n−1))+ . . . +((1)^(n−1)))]
where P is the probability that one and only one node picks the winning slot, n is the number of nodes and s is the number of slots. FIG. 6 is a table that can be used as a guide to choosing the number of slots. As can be seen, if a high probability (such as 0.9) of a single winning slot is desired, a higher number of slots are required to be established. The more nodes that wish to establish a link over the channel, more slots are necessary. It has been found, in some experiments, that setting the number of slots 56 to sixteen is acceptable.

[0035] The duration of each slot must be set so that a transmission that starts at the beginning of a slot can be detected at all nodes before the beginning of the next slot. If substantial interference is anticipated to be encountered on the channel, or if encryption schemes must be employed to detect a signal on the channel, the slot duration must be adjusted accordingly. Under said circumstances, a slot duration of 6 seconds has been found to be adequate.

[0036] There may be circumstances in which all nodes that are able to participate in the network are not known in advance. As shown in FIG. 7, a reserved slot R may be reserved for such a node. Slot R is not available to the other nodes during the random slot selection process. When a contention interval begins, the node assigned to reserved slot R will begin transmitting during the first slot. The slots randomly selected by the remaining nodes are “bumped back” to accommodate reserved slot R. The inclusion of one or more reserved slots permits systems that are not programmed to participate in the random slot selection process to still participate in the wireless network.

[0037] FIG. 8 shows the inclusion of priority slots 58, which may include a primary slot P and a secondary slot S. Primary slot P may be defined and used if a node in the network (a primary node) should take precedence over other nodes. Establishing primary slot P for the primary node ensures that communications from the primary node will be transmitted at the beginning of the contention interval prior to communications from other nodes. Secondary slot S may also be established if it is desired to have communications from a specific node take precedence over communications from all other nodes (except the primary node). Additional priority slots may be included as desired. FIG. 9 schematically depicts a contention interval in which three reserved slots R1, R2, R3 as well as primary and secondary slots P, S are established. Nodes that are not defined as corresponding to the reserved slots or the primary or secondary slots compete for the sixth through the sixteenth slots and are allowed to establish a link only if the channel is clear during the first five slots.

[0038] Because only two nodes at a time can use the channel, it is possible that a data source using a node may wait for an undesirable amount of time to successfully obtain a winning slot so that it can communicate with a desired node. FIG. 10 shows a method 60 that may be used to redirect the communications of a data source if its node has not obtained a winning slot. In step 62, a predetermined time interval, termed a Listen Before Send (LBS) interval, may be defined based on the needs of the data source. The data source, through a first node, competes for a contention interval slot according to method 30 shown in FIG. 2. If the first node obtains a winning slot (step 64) prior to the expiration of the LBS interval, then in step 66 the first node establishes a communications link over the channel to communicate with the desired node (a second node). If the first node does not obtain a winning slot and the LBS interval has not yet expired (step 68) the first node continues to compete for a winning contention interval slot according to step 30. If the LBS interval expires before a winning contention interval slot is obtained, it is then determined in step 70 whether the data source needs to communicate with a node other than the second node. If so, the method returns to step 62 and the node attempts to communicate with the node other than the second node.

[0039] If the LBS interval is set to a large value, the data source will wait until it wins a contention interval and then send its data. If the LBS interval is set to a small value (or to zero), the data source will attempt to send data to a different node if the channel is busy. In many instances, the channel will still be busy. It is possible that the data source may find that it is currently linked with and receiving data from the node to which it now desires to send data, and under these circumstances would be allowed to do so. The value of the LBS interval set for each node depends on the type of data traffic expected at that node. If a node normally uses one destination node for all send and receive messages, then the LBS interval should be set to a very large value. On the other hand, if a node normally sends and receives data from many different destination nodes, then the LBS interval should be set to a relatively small value to increase the probability of (1) connecting with a node to which it was already linked, and (2) delivering data to desired nodes.

[0040] The invention may be varied in other ways while keeping with the spirit of the invention. For example, it may be possible to identify the last packet in a link as it is transmitted across the network. Such a packet is shown at 24t in FIG. 11 and may be termed a link termination packet. If link termination packet 24t is detected, all nodes on the network may safely assume that there will be no more packets 24 in link 22, and a contention interval 54 may be initiated by the nodes as soon as the link termination packet is no longer detected. This variation of the invention does not initiate an LBT interval after the end of link termination packet 24t. It is further possible to vary the invention by eliminating the use of LBT intervals, and relying instead on the detection of a link termination packet to signal the end of a link. Such a method is shown at 80 in FIG. 12. It can be seen that step 82, in which nodes detect a link termination packet, replaces steps 34, 36, 38 and 40 of the embodiment of the invention shown in FIG. 3.

[0041] An advantage of the invention is that many nodes may use a single wireless communications channel in an orderly fashion.

[0042] Another advantage is that an established link between two nodes is not interrupted by other nodes attempting to transmit information.

[0043] Still another advantage is that nodes not programmed to participate in the random slot selection may still, through the use of reserved slots, participate in the wireless network.

[0044] Yet another advantage is that the invention may be used to provide an equal chance for every participating node to obtain a winning slot. However, the invention is flexible enough to include priority slots, if desired, to ensure that certain nodes will given a first chance to communicate over the channel.

[0045] Still another advantage is that nodes may be programmed to attempt to communicate with other nodes, through the use of the LBS interval.

[0046] While the invention has been disclosed in its preferred form, the specific embodiments thereof as disclosed and illustrated herein are not to be considered in a limiting sense as numerous variations are possible. The subject matter of the invention includes all novel and non-obvious combinations and subcombinations of the various elements, features, functions and/or properties disclosed herein. No single feature, function, element or property of the disclosed embodiments is essential to all of the disclosed inventions. Similarly, where the claims recite “a” or “a first” element or the equivalent thereof, such claims should be understood to include incorporation of one or more such elements, neither requiring nor excluding two or more such elements.

[0047] It is believed that the following claims particularly point out certain combinations and subcombinations that are directed to the disclosed inventions and are novel and non-obvious. Inventions embodied in other combinations and subcombinations of features, functions, elements and/or properties may be claimed through amendment of the present claims or presentation of new claims in this or a related application. Such amended or new claims, whether they are directed to a different invention or directed to the same invention, whether different, broader, narrower or equal in scope to the original claims, are also regarded as included within the subject matter of the invention of the present disclosure.