A system and method employing algorithms and protocols for optimizing carrier sense multiple access (CSMA) protocols in wireless networks

(Background of the Invention) The present invention relates to an algorithm and a method for adopting an algorithm and a protocol for operating a carrier sense multiple access (CSMA / CA) protocol having collision avoidance in a wireless communication network. More specifically, the present invention provides systems for providing enhanced CSMA / CA that improve channel availability and quality of service (QoS) in wireless communication networks, such as ad-hoc wireless communication networks. Regarding the method. This application claims benefits under 35U.SCSec.119 (e) for US Provisional Patent Application No. 60 / 324,277 filed on September 25, 2001, the full contents of which are cited herein. Be incorporated.

(Explanation of Related Technologies) In 1987, Apple (R) (Apple) for Wired LAN based on Send / Clear Requests to Send (RTS / CTS) Exchanges (called "AppleTalk"). U.S. Pat. No. 4,661,902 has been granted for the CSMA protocol, the contents of which are incorporated herein by reference. CSMA allows multiple devices to share a common resource (ie, the same physical cable). Such a system is extremely effective when communication takes the form of a burst of packets rather than a constant flow of data such as time division multiplexing (TDM) voice.

In 1991, Proxim was awarded US Pat. No. 5,231,634 entitled "Media Access Protocol for Wireless LANs", the entire contents of which are incorporated here by reference, which is the wireless local area. Describes an enhanced Carrier Sense Multiple Access (CSMA / CA) protocol with collision avoidance for networks (LANs). This protocol specifically raises the issue of hidden terminals that exist in wireless networks, where not all terminals know each other's existence and the transmissions they make. The protocol also includes attempts to elicit access fairness so that terminals closest to each other do not monopolize the radio link.

The ITT HMT system described in US Pat. No. 5,943,322 to Mayor, the entire contents of which are incorporated herein by reference, but also an enhanced CSMA including RTS / CTS as defined by Apple. Use the form / CA. However, the HMT system is a significant advance in several ways over the protocols described in the Proxim patent. In particular, HMT systems are highly mobile devices self-forming / self. Healing) Designed for use by networks, where simple RTS / CTS is inadequate as described below. The HMT system also introduces the concept of three data channels with one common hold channel to optimize the use of radio frequency (RF) spectra. Proxim protocols do not do this, probably because of the many potential disruptions limited by the low mobility of terminals in wireless LANs and the lack of free space propagation. That is, wifi is typically placed inside a building, where walls create a natural obstacle to RF propagation. However, this assumption is not rational in a highly mobile outdoor environment.

Proxim protocol also uses RTS / CTS and data packet switching on a common channel. According to this process, other terminals cannot use radio resources, while exchanges are occurring or during the back-off period they define, which is radio. The result is extremely low efficiency of resources. As mentioned above, the HMT system employs a mechanism with a single shared hold channel on which all RTS / CTS communications occur, and three data channels are used for the actual delivery of data. Will be done. As part of the RTS / CTS exchange, terminals agree to use one data channel. Thus, while a single pair of terminals is transmitting data packets on one data channel, other terminals can respond through the hold channel to set up packet switching on another data channel. As a result, the overall efficiency with respect to packets sent per second is higher.

The HMT system works well for its intended purpose, but it is designed for military applications, where all terminals are all others (ie, all notified networks). I knew about. However, it would be beneficial to adopt these technologies in networks where each terminal does not necessarily have information about each other's terminals. Therefore, there is a need for an improved CSMA / CA protocol suitable for use in such networks.

(Summary of Invention) Therefore, an object of the present invention is to provide an enhanced CSMA / CA protocol suitable for use in an ad hoc wireless communication network.

Another object of the present invention provides systems and methods for achieving enhanced CSMA / CA that improve channel availability and quality of service (QoS) in wireless communication networks, such as ad hoc wireless communication networks. That is.

These and other objectives are essentially achieved by systems and methods for establishing channels that allow communication between nodes in a communication network, such as wireless ad hoc communication networks. This system and method determines the average time length of a message data packet being communicated between nodes in a communication network and sends the message data packet to a destination node to send a message sent by the sending node. The time length of the request to request authorization (clearance) to send, and the clear to send the message sent by the destination node to the sending node to show the authorization to send the message data packet. Performs the operation of determining the time length of clear). This system and method also provides several data communication channels based on the relationship between the average time length of message data packets and the time length of requests to send messages and the time length of clears to send messages. Establish. More specifically, this system and method divides the average time length of a message data packet by the sum of the time length of a request to send a message and the time length of a clear to send a message. Establish a number of data communication channels equal to the integer value determined based on. The system and method also broadcast data indicating the number of data communication channels to the node.

These and other objectives are further essentially achieved by providing a system and method for controlling a node in the communication network to send a data packet to a destination node in the communication network, and if the node. If the destination node decides that it has not yet received the data packet, it puts it in one place in the queue to retransmit based on the format of the information contained in the data packet, and that place is , Indicates the duration of delay before a node attempts to resend a data packet to a destination node. This duration is shorter when the information contains audio data than when the information does not include audio data. Also, while a data packet is in the queue, this system and method controls a node to refrain from sending other data packets to a destination node, while a node sends another data packet to another destination. Allow to send to the node.

(Detailed Description of Preferred Examples) The following describes a network that has an extremely large number of terminals and can employ HMT technology in an extremely large commercial application servicing an extremely large area. By doing so, this network is entitled "Ad Hoc Peer-to-Peer Mobile Wireless Access System Interfaceing PSTN and Cellular Networks" filed June 29, 2001. The entire content adopts some structural changes to the basic HMT system as described in US Patent Application Sequence No. 09 / 897,790, which is incorporated herein by reference.

FIG. 1 is a block diagram showing an example of this type of ad hoc packet-switched wireless communication network 100 that employs an embodiment of the present invention. In particular, the network 100 includes a plurality of mobile wireless user terminals 102-1 to 102-n (generally referred to as a node 102 or a mobile node 102), and more than one to provide the node 102 with access to the fixed network 104. Can include, but is not required, a fixed network 104 with access points 106-1, 106-2, ... 106-n (commonly referred to as node 106 or access point 106). Fixed network 104 provides network nodes with access to other networks such as other ad hoc networks, public switched telephone networks (PSTNs) and the Internet, for example, core local access networks (LANs), and a plurality. Servers and gateways router) can be included. Network 100 may further include multiple fixed routers 107-1 to 107-n (commonly referred to as node 107 or fixed router 107) for routing data packets between other nodes 102, 106 or 107. You can. For this discussion, it is noted that the nodes mentioned above can be collectively referred to as "nodes 102, 106 and 107" or simply "nodes".

As will be appreciated by those skilled in the art, nodes 102, 106 and 107 may communicate directly with each other or act as routers or multiple routers for packets sent between the nodes 102, 106, one or more of them. Alternatively, it can be communicated via 107, to US Patent Application No. 09 / 897,790 cited above, and to a "shared parallel data channel with a separate reserved channel" filed on March 22, 2001. It is described in US Patent Application No. 09 / 815,157 entitled "Time Separation Protocol for Ad Hoc, Peer-to-Peer Wireless Networks with Coordinated Channel Access", and the entire contents of both applications are incorporated herein by reference. Each node 102, 106 and 107 shown in FIG. 1 can communicate through a plurality of data channels as well as a network hold channel. These channels are not limited to any particular architecture or configuration as long as each node has the ability to access the channel. Moreover, these channels are present on any communication medium, such as wire, fiber optics, or radio (through space), and any suitable transmission protocol may be employed.

As shown in FIG. 2, each node 102, 106 and 107 includes at least one transceiver 108, which is coupled to the antenna 110 and produces a signal, such as a packetized signal under the control of controller 112, at node 102, 106 or It can be received and transmitted to and from 107. The packetized data signal can include, for example, voice data or packetized control signals including multimedia information and node update information.

Each node 102, 106 and 107 further includes memory such as random access memory (RAM), which can store routing information, among other things, about itself and other nodes in network 100. Nodes 102, 106 and 107 periodically transfer their respective routing information to each other via the broadcasting mechanism, which is called routing advertisement or routing table information, for example, when a new node enters network 100 or into network 100. Exchange when existing nodes move.

As further shown in FIG. 2, some nodes, in particular the mobile node 102, are hosts 116 consisting of any number of devices, such as notebook computer terminals, mobile phone units, mobile data units, or any other suitable device. Can be included. The telephone subscriber device host 116 can optionally include suitable hardware and software to carry out transmission control protocol (TCP) and user datagram protocol (UDP). Further, the telephone subscriber device host 116 includes a driver for providing an interface between the telephone subscriber device host 116 and the transceiver 108, in addition to a display device for providing a user display. Each node 102, 106 and 107 also includes suitable hardware and software for carrying out Internet Protocol (IP) and Address Resolution Protocol (AR P), the purpose of which is readily understood by those skilled in the art. Appropriate hardware and software can also be included to carry out Transmission Control Protocol (TCP) and User Datagram Protocol (UDP).

As described above, the nodes 102, 106 and 107 can communicate through a plurality of data channels as well as the hold channel. These channels are not limited to any particular architecture or configuration as long as each node 102, 106 and 107 has the ability to access these channels. These channels can be present on any communication medium such as wire, fiber optics, or radio (through space), and any suitable transmission protocol can be employed.

When one node, eg, node 102-1, wants to send a message to another node, eg 102-2, node 102-1 goes to node 102-2 and the other nodes 102 and 106. Send an RTS (Request-to-Send) message to node 102-2 to notify the intent to hold one of the available data channels. This transmitting node 102-1 then receives a CTS (Clear-To-Send) message from the destination node 102-2 if the destination node 102-2 receives the RTS message. The transmitting node 102-1 then transmits the data in the form of a packet. The transmitting node 102-1 then receives an acknowledgment message (ACK) sent from the receiving node 102-2 if the receiving node receives the data packet. FIG. 3 shows a timeline of messages transmitted and received by transmitting node 102-1 when transmitting node 102-1 transmits a data packet. Further details of the RTS / CTS exchange and data packet transmission will be described with reference to FIG.

As shown in Figure 4, the RTS message is sent by node 102-1 over the hold channel. When node 102, 106 or 107 is not engaged in sending or receiving messages on one of the data channels, the receiver is tuned to the reserved channel. However, when node 102, 106 or 107 is involved in sending or receiving a message on one of the data channels, the receiver tunes to the data channel instead of the reserved channel. As a result, each node 102, 106 and 107 continuously monitors the pending channel on one of the data channels when the receiver is not sending or receiving messages on one of the data channels.

Upon receiving an RTS from node 102-1 on the hold channel, node 102-2 responds to node 102-1 with a CTS message on the hold channel, assuming that the data channel is available. Upon receiving the CTS message, node 102-1 then sends an informational message to node 102-2 on the available data channel, eg, data channel 1. Because the channel access request is sent on a separate pending channel, another node 102, 106 or 107 sends the RTS message immediately after the previous RTS / CTS exchange is complete, without waiting for the subsequent informational message to complete. You can.

For example, further, as shown in Figure 4, if node 102-3 wants to send a message to node 102-4, node 102-3 will send a CTS message from node 102-2 to node 102-1. Later, the RTS message can be sent on the pending channel regardless of whether the informational message being sent from node 102-1 to node 102-2 is still being sent on data channel 1. Node 102-4 then responds to node 102-3 with a CTS message, which then sends an informational message over another available data channel, such as data channel 2. As shown in FIG. 4, the information message sent from node 102-3 to node 102-4 on data channel 2 is transmitted at the same time as the information message sent from node 102-1 to node 102-2 on data channel 1. Can be done. Messages from node 102-3 to node 102-4 are essentially free of delays resulting from the transmission of long messages (ie, long in time duration) sent from node 102-1 to node 102-2. Is sent by. Further details of RTS / CTS exchange and channel allocation can be found in Eric A. of 09 / 705,588, entitled "Methods and Devices for Coordinating Channel Access to Shared Parallel Data Channels," filed November 3, 2000. US patent application by White Hill et al., And October 11, 2001, entitled "Systems and Methods for Efficient Bidirectional Ranged to Determine the Location of Radio Nodes in Communication Networks," 09 / 973,799. It is described in US patent applications such as Eric A. Whitehill of the United States, and the entire contents of both applications are incorporated herein by reference.

As described above, Network 100 employs a methodology that recognizes a direct correlation between the number of data channels and the average size of data packets. In particular, if the average size of the data packet (meaning the average length of transmission time) is smaller, the size of the RTS / CTS combination (the duration of the combined time for the RTS / CTS exchange) As you approach (meaning), the number of data channels that the reserved channel can efficiently support decreases. Conversely, as the average size of data packets increases with respect to the RTS / CTS combination, the number of data channels that can be supported increases. As mentioned above, FIGS. 3 and 4 show an example of the relationship between RTS and CTS message size (duration of transmission time) and average size data packets, and the average size. It is a figure which shows an example of the number of RTS / CTS which occurs in the time required to send a data packet. As can be seen from these figures, when all message data packets are small, the network 100 tends toward packet congestion, and when all data packets are large, it tends toward data or payload congestion. Head.

In Apple, Proxim and HMT systems, the number of data channels was fixed. This number is 1 for Apple and Proxim systems. There are three data channels for the HMT system.

In contrast, this network 100 has a capacity between 1 and n for the number of data channels (where n is the length of time to send a message data packet of average size, Represents an integer value divided by the time to perform an RTS + CTS message exchange). For this purposes, the length of time to send an average size message data packet is expressed in bytes, and the length of time to perform an RTS + CTS exchange is also expressed in bytes. It should be noted that the transmission rate on the hold channel on which the RTS / CTS message exchange occurs is typically lower than the transmission rate on the data channel on which the data packet is transmitted. However, this is taken into account for the purposes of this example when expressing the time length of a message as the number of bytes. For example, if the average size of a message data packet is 1200 bytes (meaning that the duration of the transmission time is equal to the length of time required to send 1200 bytes on the data channel, which is short, "time length". If the length of the RTS + CTS message exchange is 200 bytes (the duration of the transmission time to perform the RTS / CTS exchange on the pending channel is the slower transmission rate of the pending channel). When modified to take into account, it means that it is equivalent to the length of time required to send 200 bytes over the hold channel, which is called the "time length" of RTS and CTS messages) n is equal to 6. .. Similarly, if the average size (time length) of the message data packet is 1500 bytes and the time length of the RTS + CTS exchange is 200 bytes, then n is equal to 7. The actual number of data channels used is a system parameter broadcast between nodes 102, 106 and 107. However, it should also be noted that the amount of RF spectrum available may limit the choices somewhat less than the ideal number. U.S. Patent Application No. 09/897, cited above, As described in No. 790, the Mobile Internet Switching Center (MiSC) in Network 100 can analyze the packets sent by nodes 102, 106 and 107 and determine the average packet size, similar to LAP106. Can include software to make. This allows network 100 to dynamically change the number of channels it is using in almost real time.

(System recognition in RTS / CTS) In a network 100 according to an embodiment of the present invention, a common hold channel shared by all nodes 102, 106 and 107 allows the network 100 to perform system-level configuration, coordination and preparation. When idle, all nodes 102, 106 and 107 are listening to the pending channel. The main reason is that when an application wants to send a packet, it measures the level of utilization and makes it ready to receive the packet from another node 102, 106 and 107. By partitioning a small amount of bandwidth on the hold channel, nodes 102, 106 and 107 can share information related to all of them, as mentioned above. An example of this information is the number of data channels in use. The other is the location of the data channel, if the available spectra are not adjacent. Information about the identity and behavior of Network 100 can be broadcast from MiSC / IAP so that all nodes 102, 106 and 107 can work together in the most efficient and effective way. This commonly known information is expected to assist in the overall efficiency of Network 100 in some additional areas as well.

(Intelligent Random Backoff and Conformable Random Backoff) The Proxim system statistically randomizes the time slots so that all nodes 102, 106 and 107 have equal chances of being next in the queue. Adopt random back off to increase the fairness of access based on allocation. For packet data systems, this is a simple and concise solution. However, the network 100 according to the embodiments of the present invention also provides quality of service (QOS) capabilities that enable real-time services, both voice and traditional data services. In such a network 100, all terminals (eg, mobile node 102) are made equal or essentially equal, but not all packets. Therefore, a different mode of random backoff system is needed so that voice packets that cannot tolerate waiting (ie, delay) are not unreasonably disturbed. Therefore, the implementation of the network 100 according to the embodiment of the present invention is as follows.

To send a packet when the Link Layer of a node (eg, mobile node 102) receives a response from media access control (MAC) that it failed to send the packet. Controller 112 on the attempting node will put the packet, for example, in the retransmission queue in memory 114 on that node. There are many possible reasons for failure, but the most common is RTS collisions.

When a packet is in the retransmission queue, two events occur on the node trying to send. The first is that the destination of the packet is blocked. Therefore, controller 112 on that node will queue any other packet to its destination. This allows the node to continue sending data packets to other destinations on other data channels, waiting a reasonable amount of time to attempt to retransmit to the blocked destination. Second, the amount of time the node will wait depends on the format of the packets being sent. In simple terms, it will wait shorter for low latency QOS packets (like voice packets) and longer for best effort data packets. The methodology at Network 100 is extended on the basic algorithm by using the performance measurements that the network takes to fine-tune the back off algorithm, and manually or automatically by Network 100 for backoff. Allows to be formed into.

Although only a few exemplary embodiments of the invention have been described in detail above, one of ordinary skill in the art will appreciate that many modifications can be made to the exemplary embodiments without departing from the novel teachings and advantages of the invention. It will be easy to understand.

These and other objectives, advantages and novel features of the invention will be more easily understood from the detailed description below when read with the accompanying drawings.<figref num="1">It is a block diagram of an example of an ad hoc wireless communication network including a plurality of nodes adopting the embodiment of the present invention.</figref><figref num="2">It is a block diagram of an example of a wireless node as shown in FIG.</figref><figref num="3">It is a timing diagram which shows an example of the transmission sent and received by a node in the network shown in FIG. 1 when a node sends a data packet to another node.</figref><figref num="4">FIG. 5 is a timing diagram showing an example of a hold channel between nodes in the network shown in FIG. 1 and a transmission occurring on a plurality of data channels.</figref>