Multiplex communications – Channel assignment techniques – Carrier sense multiple access
Reexamination Certificate
2002-08-26
2004-09-14
Jung, Min (Department: 2665)
Multiplex communications
Channel assignment techniques
Carrier sense multiple access
C370S461000
Reexamination Certificate
active
06791997
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to the scheduling of transmissions without collisions in ad hoc networks in which routers can move and have both hosts and networks attached to them.
BACKGROUND OF THE INVENTION
Many medium-access control (MAC) protocols have been developed for wireless networks. The carrier-sense multiple access (CSMA) protocol was the first to be used in multihop packet-radio networks. A limitation of CSMA in multihop networks is that sources hidden from one another cannot detect their transmissions, which degrades CSMA's performance to that of the pure ALOHA protocol. Many MAC protocols have been proposed and implemented to solve the hidden-terminal problems of CSMA. The throughput of CSMA protocols is very good, as long as the multiple transmitters within range of the same receivers can sense one another's transmissions. Unfortunately, “hidden terminal” problems degrade the performance of CSMA substantially, because carrier sensing cannot prevent collisions in that case.
The busy tone multiple access (BTMA) protocol (F. A. Tobagi and L. Kleinrock, “Packet switching in radio channels: Part II—the hidden terminal problem in carrier sense multiple-access modes and the busy-tone solution,” IEEE Trans. Commun., vol. COM-23, no. 12, pp. 1417-1433, 1975.) was the first proposal to combat the hidden-terminal problems of CSMA. BTMA is designed for station-based networks and divides the channel into a message channel and the busy-tone channel. The base station transmits a busy-tone signal on the busy-tone channel as long as it senses carrier on the data channel. Because the base station is in line of sight of all terminals, each terminal can sense the busy-tone channel to determine the state of the data channel. The limitations of BTMA are the use of a separate channel to convey the state of the data channel, the need for the receiver to transmit the busy tone while detecting carrier in the data channel, and the difficulty of detecting the busy-tone signal in a narrow-band channel.
A receiver initiated busy-tone multiple access protocol for packet-radio networks has also been proposed (C. Wu and V. O. K. Li, “Receiver-initiated busy-tone multiple access in packet radio networks,” ACM SIGCOMM 87 Workshop: Frontiers in Computer Communications Technology, Stowe, Vt., USA, 11-13 August 1987). In this scheme, the sender transmits a request-to-send (RTS) to the receiver, before sending a data packet. When the receiver obtains a correct RTS, it transmits a busy tone in a separate channel to alert other sources that they should back off. The correct source is always notified that it can proceed with transmission of the data packet. The limitations of this scheme are that it still requires a separate busy-tone channel and full-duplex operation at the receiver.
Several protocols have been proposed based on different types of “collision-avoidance ” handshakes done with small control packets and meant to avoid data collisions when sources of data packets cannot hear one another. The collision-avoidance approach in the prior art follows the basic philosophy first introduced by Tobagi and Kleinrock in the Split-Channel Reservation Multiple Access (SRMA) protocol (F. A. Tobagi and L. Kleinrock, “Packet switching in radio channels: Part III—polling and (dynamic) split-channel reservation multiple access,” IEEE Trans. Commun., vol. COM-24, no. 8, pp. 832-845, 1976). In SRMA, and most subsequent collision-avoidance protocols, a sender node sends a request-to-send (RTS) packet to the intended receiver, either sensing the channel before sending the RTS or not sensing the channel before the RTS transmission. A receiver that hears a clean RTS responds with a clear-to-send (CTS), and the sender can send a data packet after hearing a clean CTS.
U.S. Pat. No. 5,319,641 assigned to Echelon Systems Corp. discloses a method to improve CSMA p-persistent protocols by introducing a random waiting time that stations must wait listening to the channel once they have packets to send. The method disclosed does not work in networks with hidden terminals.
U.S. Pat. No. 4,661,902 assigned to Apple Computer, Inc. discloses a method that amounts to an implementation of SRMA over a single channel in which stations use carrier sensing before sending RTSs.
MACA (P. Karn, “MACH—a new channel access method for packet radio,” in ARRL/CRRL Amateur Radio 9th Computer Networking Conference, pp. 134-40, ARRL, 1990) includes a technique that amounts to SRMA running over a single channel in which a request-to-send (RTS) packet is sent without carrier sensing. There is no description of how to support packet trains.
U.S. Pat. No. 5,231,634 assigned to Proxim, Inc. discloses a method that also applies SRMA's basic approach over a single channel. The RTS specifies the length of the impending data packet.
U.S. Pat. No. 5,502,724 assigned to International Business Machines Corporation discloses a method that extends the collision avoidance handshake to allow for multiple data packets to flow among a pair of communicating stations. A station that intends to establish a connection with a second station senses the channel. If the channel is idle, it sends a connection request (CR) packet to the intended receiver station. The CR specifies the number of data packets that the connection includes. The intended receiver sends a connection confirm (CC) packet to the sending station; the CC also specifies the number of packet in the connection. After the exchange of correct CR and CC packets the sending station may send one or multiple data packets and the receiving station may send an acknowledgment packet specifying which data packets were received correctly. To end the connection, the sending station sends a disconnect request (DR) and the receiving station issues a disconnect confirm (DC). Stations that receive a CR packet back off for an amount of time that is long enough for the advertised number of data packets to be sent to the receiver. After receiving a CR or CC, a station can attempt to access the channel when a timer proportional to the number of packets to be sent in the connection expire, or when it receives a DR or DC packet. The limitation with the method disclosed in U.S. Pat. No. 5,502,724 is that the method cannot ensure collision-fee transmissions of data packets, even with the transmission of CC packets by the receiver. The need for feedback from the receiver to its neighbors on a packet-by-packet basis was demonstrated by Fullmer and Garcia-Luna-Aceves (C. L. Fullmer and J. J. Garcia Luna-Aceves, “Solutions to Hidden Terminal Problems in Wireless Networks”, Proc. ACM SIGCOMM 97, Cannes, France, Sep. 14-18, 1997). Because the CC packet sent by the receiver may collide with another packet at a neighbor of a receiver, the CC packet does not provide sufficient feedback to hidden nodes; furthermore, the need for feedback packets to be longer than request packets was also demonstrated by Fullmer and Garcia-Luna-Aceves (C. L. Fullmer and J. J. Garcia-Luna-Aceves, “Floor Acquisition Multiple Access (FAMA) for Packet-Radio Networks,” Proc. ACM SIGCOMM 95, Cambridge, Mass., Aug. 28-Sep. 1, 1995). In addition, even though the disclosed method makes reference to broadcast packets sent to all the neighbors of a station, it provides no provisions to ensure that broadcast or multicast packets are received without interference by all the neighbors of a sending station.
U.S. Pat. No. 5,721,725 assigned to Xerox Corp. discloses a method similar to SRMA, and describes it to be an improvement over MACH. The method disclosed extends MACH by specifying in the RTS packets the desired data rate for data packets and allowing sender and receiver to negotiate the transmission data rate. This method fails to guarantee collision free transmissions in networks with hidden terminals because no provisions are made on the length of the CTS being longer than the length of any RTS to ensure that collisions of RTSs and CTSs are detected by hidden stations.
DFWMAC IEEE802.11 (K. C. Chen, “Medium Access Control o
Beyer David
Garcia-Luna-Aceves Jose J.
Darby & Darby PC
Gaffney Matthew M.
Jung Min
LandOfFree
System and method for collision-free transmission scheduling... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and method for collision-free transmission scheduling..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for collision-free transmission scheduling... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3225290