Multiplex communications – Channel assignment techniques – Arbitration for access to a channel
Reexamination Certificate
2001-11-09
2003-12-16
Chin, Wellington (Department: 2664)
Multiplex communications
Channel assignment techniques
Arbitration for access to a channel
C370S461000
Reexamination Certificate
active
06665311
ABSTRACT:
BACKGROUND
(1) Technical Field
The present invention relates to the field of computer networking, and more particularly to techniques for adaptive bandwidth reservation in wireless ad-hoc networks.
(2) Discussion
Research in QoS enabled medium access control protocols (MACs) for ad-hoc network is still in its infancy. However, with increasing interest in wireless networks, and the increasing need to create networks, or portions of networks, that are mobile and less reliant on physical wiring, research in the wireless arena is growing rapidly.
Two major areas of importance in wireless network communications are unicast and broadcast communications. Unicast transmissions are considered those transmissions in which a unique transmitter sends a signal to a unique receiver for that signal. Broadcast transmissions, on the other hand, are considered those transmissions in which a single transmitter sends a signal to multiple receivers.
In the literature, many articles have appeared discussing various aspects of unicast and broadcast wireless network communications. Several examples of these articles are provided herein for reference.
In Z. Tang, and J. Garcia-Luna Aceves, ‘A protocol for topology-dependent transmission scheduling in wireless networks,’ in
Proc. IEEE Wireless Commun. And Netw. Conf.
1999 (
WCNC
'99), September 1999, for example, the authors present a synchronous MAC that supports both unicast and broadcast reservations. Their signaling scheme provides for signaling minislots inside data slots. This forces nodes that contend for a specific data slot to do so specifically in a minislot corresponding to the data slot for which they wish to contend. Unfortunately, there is a drawback in that this signaling scheme has an adverse effect on throughput, especially when a network is heavily loaded; that is, when many data slots are already reserved and few are left available, contention for open slots will be very heavy, since the signaling bandwidth is limited to the small amount taken from the data slots.
Time division multiple access (TDMA)—based techniques for broadcast scheduling have also been presented, falling under two general categories: topology independent and topology dependent. In topology independent scheduling protocols, nodes transmit in a number of slots in every frame. The slots in which a node can transmit are assigned (according to a unique code) such that the node can send at least one collision-free packet to every neighbor in each frame. The main limitations of the topology independent scheduling protocols are: (i) the sender is uncertain about which of its neighbors received its transmission in a particular slot (therefore, the sender has to transmit the same packet in multiple slots in a frame); and (ii) the number of slots must be greater than the number of nodes in the two-hop neighborhood. This constraint on the frame length limits the scalability of these protocols. Topology dependent protocols, on the other hand, compute a transmission schedule so that each node can send unicast or broadcast transmissions in a reserved slot with a very low probability of collisions. The reservation mechanism itself is contention-based, i.e., nodes contend among each other in order to reserve a slot. Moreover, these schedules have to be dynamic to increase the channel utilization by spatial reuse of the slots. Also, nodes may have to re-compute/update their schedules to adapt to topological changes in a mobile ad hoc network.
Two recent efforts separated the signaling transmissions and the data transmissions in a distributed protocol. The first is from C. Zhu, and S. Corson, ‘A five phase reservation protocol (FPRP) for mobile ad-hoc networks,’ in
Proc. IEEE INFOCOM
1998, April 1998, called the Five-Phase Reservation Protocol (FPRP), that performs both broadcast scheduling and channel access functions. In FPRP, reservation signaling precedes the actual data portion of a frame and the nodes can contend for a data slot only in the corresponding set of reservation slots. In this way, the protocol is not scalable in the number of data slots available. Additionally, the protocol does not adapt to mobility. The authors themselves note that in the presence of mobility, their protocol would have to be run periodically, which makes its usefulness questionable.
In Z. Tang, and J. Garcia-Luna Aceves, ‘A protocol for topology-dependent transmission scheduling in wireless networks,’ in
Proc. IEEE Wireless Commun. And Netw. Conf.
1999 (
WCNC
'99), September 1999, the Collision-Avoidance Time Allocation (CATA) protocol is proposed. CATA is designed to support unicast reservations apart from broadcast reservations. In contrast to FPRP, slot reservation in CATA is done within the slot itself. However, CATA has a severe drawback in that contention bandwidth is reduced with successful reservations. Additionally, this rather simple signaling scheme for broadcast reservations can result in deadlocks if we assume half-duplex radios. A deadlock is said to occur if two conflicting broadcasts are scheduled in the same slot and the senders do not realize this conflict. The possibility of deadlocks is identified in these references and solutions which allow nodes to detect this situation are outlined, but the downside of the solutions provided is that data packets are lost until the deadlock goes undetected. Deadlocks can arise quite often in ad hoc networks, for e.g. when every node in the neighborhood has a broadcast packet to send at the same time following a topology change.
Despite these advances in wireless network communications, much improvement is still needed. In order to overcome the limitations discussed above, it is desirable to provide a technique in which signaling bandwidth is independent of data bandwidth, and therefore contention of new reservations is independent of the loading of the network. Furthermore, it is desirable to provide a technique by which nodes can use a successful contention mini-slot in order to reserve more than one data slot, depending e.g. on their queue sizes. Finally, it is also desirable to provide a technique that incorporates an acknowledgment mechanism in order to ensure reservation reliability and that facilitates both unicast and broadcast network traffic.
(3) References
[1] C. Zhu, and S. Corson, ‘A five phase reservation protocol (FPRP) for mobile ad-hoc networks,’ in
Proc. IEEE INFOCOM
1998, April 1998.
[2] Z. Tang, and J. Garcia-Luna Aceves, ‘A protocol for topology-dependent transmission scheduling in wireless networks,’ in
Proc. IEEE Wireless Commun. And Netw. Conf.
1999 (
WCNC
'99), September 1999.
[3] I. Chlamtac, A. Farago, and H. Zhang, ‘Time-spread multiple access (TSMA) protocols for multihop mobile radio networks,’
IEEE/ACM Trans. Netw.,
pp. 804-12, December 1997.
[4] J. Ju, and V. Li, ‘TDMA scheduling design of multihop packet radio networks based on latin squares,’
IEEE J. Selct. Areas Commun,
pp. 1345-52, August 1999.
[5] Z. Tang, and J. Garcia-Luna Aceves, ‘Hop reservation multiple access (HRMA) for ad-hoc networks,’ in
Proc. IEEE INFOCOM
'99, March 1999.
SUMMARY
An apparatus, a method, and a computer program product for effective communication routing of unicast and broadcast data traffic in wireless ad-hoc networks are presented. The routing technique separates the signaling and data transmission portions of a data frame such that the length of the signaling portion is independent of the length of the data portion. In the signaling portion, reservations are able to be performed and confirmed, while the data portion also includes a reservation confirmation portion which allows reservations made in during the signaling portion of the frame to be confirmed immediately prior to transmission of the data. In addition, the present invention also provides a mechanism for dynamically adjusting reservations.
REFERENCES:
patent: 5654968 (1997-08-01), Smiroldo
patent: 5677909 (1997-10-01), Heide
patent: 6577613 (2003-06-01), Ramanathan
patent: WO
Kondylis George
Kozat Ulas
Marina Mahesh
Ryu Bong K.
Chin Wellington
HRL Laboratories LLC
Schultz William
Tope-McKay & Associates
LandOfFree
Method and apparatus for adaptive bandwidth reservation in... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for adaptive bandwidth reservation in..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for adaptive bandwidth reservation in... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3148924