Multiplex communications – Channel assignment techniques – Combining or distributing information via time channels...
Reexamination Certificate
2000-05-15
2003-04-29
Le, Thanh Cong (Department: 2684)
Multiplex communications
Channel assignment techniques
Combining or distributing information via time channels...
C370S447000, C370S448000
Reexamination Certificate
active
06556582
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to packet radio networks and, more particularly, to improved techniques for multiple access collision avoidance (MACA) in mobile multi-hop packet radio networks.
BACKGROUND OF THE INVENTION
Wireless data communication is often required in an environment where communications infrastructure, such as base stations or a wired backbone network, does not exist or is uneconomical or impractical to use. For example, in military or emergency environments, adequate infrastructure often does not exist in necessary locations and constructing such an infrastructure would be either impractical or uneconomical for the short-term use that is often required. Mobile multi-hop wireless networks have, therefore, been developed to provide wireless data communications in such environments.
In a conventional mobile wireless multi-hop network, each wireless node acts as a packet router that relays packets to other nodes in the network over an air interface link without routing the packets through any portion of a conventional cellular network, such as the wired backbone network, base station controllers, or base stations. Each wireless node, however, is limited in the distance over which it can reliably transmit, with transmission ranges of between a few feet and hundreds of feet being typical. Therefore, in communication environments that span large areas or have significant radio interference, packets transmitted from a sending node must often be hopped over multiple nodes in the wireless network to reach a destination. For such a multi-hop wireless network to perform effectively, all nodes must, therefore, be prepared to route packets on behalf of other nodes.
One problem in the routing of packets between nodes in a conventional multi-hop wireless network is commonly called the “hidden terminal” problem.
FIG. 1
is a diagram of routing that illustrates this problem in such a conventional multi-hop wireless network. The illustrative network includes three nodes
120
,
125
, and
130
that communicate with one another. As shown, each node (
120
,
125
, and
130
) has an effective radio range delineated by dotted lines
105
,
110
and
115
, respectively. Since the radio range of Node
120
(dotted line
105
) encompasses Node
125
, Node
120
is able to communicate with Node
125
. Node
120
, however, is not within radio range of Node
130
and, therefore, cannot directly communicate with Node
130
. Likewise, Node
130
can communicate with Node
125
, but cannot communicate with Node
120
.
To communicate with Node
130
, Node
120
routes its packets through Node
125
and vice versa. In this case, Node
125
relays the packets to nodes
120
and
130
. If both Nodes
120
and
130
route packets through Node
125
, however, packet “collisions” may occur at Node
125
. Packet collisions are particularly likely when Nodes
120
and
130
attempt to send packets to Node
125
simultaneously. If a collision occurs, Node
125
refuses further packets from either Node
120
or Node
130
. If this happens, both nodes
120
and
130
will keep attempting to re-transmit their packets to Node
125
. This results in further collisions. In a multi-hop network that has many intervening hops between a sending node and a receiving node, packet collision can be a very significant problem that will cause a large loss in throughput.
Multiple access collision avoidance (MACA) is a common technique used to deal with the problem of packet collision. This technique uses a Request-to-Send/Clear-to-Send/data/Acknowledgment (RTS/CTS/data/ACK) messaging exchange to prevent packet collision.
FIG. 2
is a diagram illustrating Conventional MACA. Using this technique, Node
120
first sends a Request-to-Send (RTS) packet [
205
] to Node
125
before transmitting any data packets. If the wireless channel is idle at Node
125
, then Node
125
sends a Clear-to-Send (CTS) packet [
210
] to Node
120
. In response to the CTS packet, Node
120
sends data packets [
215
] to Node
125
. Since Node
130
is within the effective radio range of Node
125
, Node
130
also receives the CTS packet designated for Node
120
. Node
130
, thus, knows that Node
125
is busy receiving a packet from Node
120
and, therefore, waits for a period of time to attempt to send a transmission. Node
125
marks the end of the MACA sequence by Acknowledging (ACK) [
220
] receipt of the packet from Node
120
. Again, since Node
130
is within the radio range of Node
125
, Node
130
also receives the ACK packet intended for Node
120
. Node
130
, therefore, recognizes that Node
120
has finished sending data and Node
130
sends its own RTS packet [
225
] to Node
125
.
The conventional MACA technique shown in
FIG. 2
, however, has a number of fundamental problems. One problem is that the conventional RTS/CTS messaging scheme does not always prevent nodes from attempting to communicate with other nodes that are already busy. For example, a node may have moved into a transmission area after RTS/CTS packets were exchanged between two nodes. In another example, a node may have been busy performing another task when the RTS/CTS control packets were exchanged between two other nodes. In a further example, there may be collisions on a channel reserved for RTS/CTS control packets, such that a node did not “hear” the same control packets that a sender and receiver “heard.”
When a node “misses” a RTS/CTS exchange between two other nodes, it may subsequently attempt to send a packet to one of the nodes by sending an RTS packet. If the destination node is already busy receiving a packet, the destination node ignores the RTS. Receiving no response to the RTS, the sending node typically waits a short time and then sends another RTS. Since the destination node may still be busy receiving a packet, the destination node fails to respond with a CTS. In a wireless multi-hop network, every node keeps track of its link state with every other neighboring node. Therefore, after repeated attempts to contact a destination, the sending node updates its link state information to indicate that a problem exists with its link to the particular destination node. The updated link state information thus gives the sending node an inaccurate account of the actual quality of the link state. This can cause rapid changes of link state called “link flapping” as the destination node alternates between “busy” and “non-busy.” Missing the RTS/CTS exchange can, therefore, have a negative impact on link metric calculations, which can further affect the topology of the network and the quality of service used for packet transmission.
Another problem relating to the conventional MACA technique is its inability to provide quality of service and priority mechanisms (QoS/priority) that reserve channel or radio resources to ensure high quality data transfer or expedited packet routing. Quality of service and priority mechanisms are conventionally implemented in wireless multi-hop systems, but these mechanisms typically perform packet-type specific processing in the network layer that resides above the physical radio layer. These conventional QoS/priority mechanisms are disadvantageous in that, though they may place packets into appropriate low or high quality/priority queues at intermediate hops along the source-to-destination path, the packets still use radio resources (e.g., bandwidth, receiver power, etc.) regardless of the packets' quality of service or priority type. With non-priority or low quality of service type packets using some bandwidth, necessary bandwidth may not be available to ensure quick delivery of high priority type packets. Also, a given node within the source-to-destination path may not have sufficient power or processing resources to route packets other then high QoS/priority type packets.
Numerous time-based methods have been suggested for giving higher priority traffic quicker access to radio resources, such as, for example, short back-off timers.
BBNT Solutions LLC
Cong Le Thanh
Suchyta Leonard Charles
Trinh Tan
Weixel James K.
LandOfFree
Systems and methods for collision avoidance in mobile... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Systems and methods for collision avoidance in mobile..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Systems and methods for collision avoidance in mobile... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3089484