US 6,665,311 B2Granted

Method and apparatus for adaptive bandwidth reservation in wireless ad-hoc networks

AssigneeHRL Laboratories, LLC

InventorsGeorge Kondylis, Bong K. Ryu, Mahesh Marina, Ulas Kozat

Life of this patent

Estimating the term…

Loading patent…

Abstract

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.

Claims16

Dependent claims

a. means for generating data to transmit via a wireless channel in a TDMA frame, where the TDMA frame is divided into a signaling portion and a data portion, with the signaling portion comprising signaling slots, with each signaling slot comprising a minislot triplet including a request to send minislot, a (not) clear to send minislot, and a confirmation minislot, and with the data portion comprising data slots, with each data slot including a receive beacon portion, a data portion, and an acknowledgement portion;
and
b. means, operating in correspondence to each minislot triplet, for:
(1) determining a data slot from a set of slots available for transmission in which a reservation is desired;
(2) transmitting a request to send data in the request to send data slot, with the request to send corresponding to a data slot in which a reservation is desired;
(3) receiving, as a result of transmitting the request to send data, a (not) clear to send signal indicating whether the data slot is available for sending data, and for determining whether the (not) clear to send signal indicates a clear to send status, a not clear to send status, or a collision;
(4) means for operating the means for transmitting a request to send data again for the next minislot triplet when either a not clear to send status or a collision is received;
and
(5) means for indicating that the data slot is reserved for transmission when a clear to send signal is received and for sending a confirmation signal in the confirmation signal minislot and for transmitting data in the reserved data slot.

6 more elements

a. means for receiving data via a wireless channel in a TDMA frame, where the TDMA frame is divided into a signaling portion and a data portion, with the signaling portion comprising signaling slots, with each signaling slot comprising a minislot triplet including a request to send minislot, a (not) clear to send minislot, and a confirmation minislot, and with the data portion comprising data slots, with each data slot including a receive beacon portion, a data portion, and an acknowledgement portion;
b. means for receiving a request to send data in a data slot and determining whether the present apparatus is the intended receiver of the data, and whether the whether the data slot in which data is requested to be sent is a slot in which the present apparatus is free to receive and:
(1) when the present apparatus is the intended receiver, and the data slot in which data is requested to be sent is a slot in which the present apparatus is free to receive and when the slot is one in which the apparatus is free to receive, issuing a clear to send signal in the (not) clear to send minislot and awaiting for receipt of a confirmation in the confirmation minislot;
and
(2) when the present apparatus is the intended receiver, and the data slot in which data is requested to be sent is a slot in which the present apparatus is free to receive and when the slot is not one in which the apparatus is free to receive, remaining silent in the (not) clear to send minislot;
(3) when the present apparatus is not the intended receiver, checking whether the requesting slot is reserved for reception, and
(i) when the slot is reserved for reception, issuing a not clear to send signal in the (not) clear to send slot;
and
(ii) when the slot is not reserved for reception, remaining silent in the (not) clear to send slot and awaiting receipt of a confirmation in the confirmation minislot, and marking the slot free for transmission;
and
c. means for inserting a not clear to send signal in the (not) clear to send slot when a collision is detected.

8 more elements

A transmitting and receiving apparatus for adaptive bandwidth reservation in wireless ad-hoc networks, the apparatus comprising a data processing system including a wireless communication interface for transmitting and receiving wireless communication signals coupled with a processor and a memory coupled with the processor for storing data and programs, the data processing system further comprising:

a. means for generating data to transmit and receive via a wireless channel in a TDMA frame, where the TDMA frame is divided into a signaling portion and a data portion, with the signaling portion comprising signaling slots, with each signaling slot comprising a minislot triplet including a request to send minislot, a (not) clear to send minislot, and a confirmation minislot, and with the data portion comprising data slots, with each data slot including a receive beacon portion, a data portion, and an acknowledgement portion;
and
b. a transmitting portion comprising means, operating in correspondence to each minislot triplet, for:
i. determining a data slot from a set of slots available for transmission in which a reservation is desired;
ii. transmitting a request to send data in the request to send data slot, with the request to send corresponding to a data slot in which a reservation is desired;
iii. receiving, as a result of transmitting the request to send data, a (not) clear to send signal indicating whether the data slot is available for sending data, and for determining whether the (not) clear to send signal indicates a clear to send status, a not clear to send status, or a collision;
iv. means for operating the means for transmitting a request to send data again for the next minislot triplet when either a not clear to send status or a collision is received;
and
v. means for indicating that the data slot is reserved for transmission when a clear to send signal is received and for sending a confirmation signal in the confirmation signal minislot and for transmitting data in the reserved data slot;
and
c. a receiving portion comprising means for receiving a request to send data in a data slot and determining whether the present apparatus is the intended receiver of the data, and whether the whether the data slot in which data is requested to be sent is a slot in which the present apparatus is free to receive and:
i. when the present apparatus is the intended receiver, and the data slot in which data is requested to be sent is a slot in which the present apparatus is free to receive and when the slot is one in which the apparatus is free to receive, issuing a clear to send signal in the (not) clear to send minislot and awaiting for receipt of a confirmation in the confirmation minislot;
and
ii. when the present apparatus is the intended receiver, and the data slot in which data is requested to be sent is a slot in which the present apparatus is free to receive and when the slot is not one in which the apparatus is free to receive, remaining silent in the (not) clear to send minislot;
iii. when the present apparatus is not the intended receiver, checking whether the requesting slot is reserved for reception, and
(1) when the slot is reserved for reception, issuing a not clear to send signal in the (not) clear to send slot;
and
(2) when the slot is not reserved for reception, remaining silent in the (not) clear to send slot and awaiting receipt of a confirmation in the confirmation minislot, and marking the slot free for transmission;
and
iv. means for inserting a not clear to send signal in the (not) clear to send slot when a collision is detected.

17 more elements

A transmitting apparatus for adaptive bandwidth reservation in wireless ad-hoc networks, the apparatus comprising a data processing system including a wireless communication interface for transmitting and receiving wireless communication signals coupled with a processor and a memory coupled with the processor for storing data and programs, the data processing system further comprising means for generating data to transmit via a wireless channel in a TDMA frame, where the TDMA frame is divided into a signaling portion and a data portion, with the signaling portion comprising a plurality of m request minislots, a negative acknowledgement minislot, and a confirmation minislot, and with the comprising data slots, each data slot including a probe minislot, a request minislot, a negative acknowledgement minislot, a jam minislot, a confirm minislot, a propagate minislot, and a data sub-portion;

and means, operating in correspondence with each frame:
i. in the reservation portion for performing an original reservation by:
(A) sending requests to broadcast signals to neighboring apparatus, in k randomly selected request minislots of the m request minislots, where k<m;
(B) receiving negative acknowledgements, and when a negative acknowledgement is received, awaiting the reservation portion of the next frame to attempt reservation again;
and
(C) sending a reservation confirmation when no negative acknowledgement is received and indicating that the slot is reserved for broadcast transmission in the slot table;
and when the slot is reserved for broadcast transmission,
ii. in the data portion, in each data slot reserved by the apparatus for broadcast transmission, for performing a reservation check by:
(A) randomly selecting either the probe minislot or the request minislot and transmitting a request to broadcast in the selected minislot;
(B) detecting whether a request to broadcast from another apparatus exists in either the probe minislot or the request minislot or whether there is a collision in the probe minislot or the request minislot, and:
a. when there is a request to broadcast from another apparatus exists in either the probe minislot or the request minislot or when there is a collision in the probe minislot or the request minislot, transmitting a negative acknowledgement in the negative acknowledgement minislot and marking the current data slot as free to receive;
b. when there is no request to broadcast from another apparatus exists in either the probe minislot or the request minislot or when there is a collision in the probe minislot or the request minislot, transmitting a confirmation in the confirmation minislot and awaiting a propagate signal in the propagate minislot, and:
i. when a propagate signal or a collision is received in the propagate minislot, sending data in the data sub-portion of the data slot;
and
ii. when a propagate signal or a collision is not received in the propagate minislot, marking the current data slot as free to receive.

12 more elements

A receiving apparatus for adaptive bandwidth reservation in wireless ad-hoc networks, the apparatus comprising a data processing system including a wireless communication interface for transmitting and receiving wireless communication signals coupled with a processor and a memory coupled with the processor for storing data and programs, the data processing system further comprising means for generating data to transmit via a wireless channel in a TDMA frame, where the TDMA frame is divided into a signaling portion and a data portion, with the signaling portion comprising a plurality of m request minislots, a negative acknowledgement minislot, and a confirmation minislot, and with the comprising data slots, each data slot including a probe minislot, a request minislot, a negative acknowledgement minislot, a jam minislot, a confirm minislot, a propagate minislot, and a data sub-portion;

and means, operating in correspondence with each frame:
i. in the signaling portion, in each of the m request minislots, for detecting a collision or reservation conflict in the request minislot, and:
(A) when a collision or reservation conflict is detected, transmitting a negative acknowledgement in the negative acknowledgement minislot and remaining silent in the confirmation minislot;
and
(B) when no collision or reservation conflict is detected, marking the slot as reserved for broadcast reception and remaining silent in the negative acknowledgement and confirmation minislots;
and
ii. in the data portion, in each data slot, for performing a reservation check by:
(A) detecting whether a collision or reservation conflict exists in either the probe minislot or the request minislot, and:
a. if a collision or reservation conflict exists in either the probe minislot or the request minislot, transmitting a negative acknowledgement in the negative acknowledgement minislot and remaining silent in the jam minislot;
b. if no collision or reservation conflict exists in either the probe minislot or the request minislot, remaining silent in the negative acknowledgement minislot and transmitting a jam signal in the jam minislot;
and
(B) awaiting the reception of a confirmation signal in the confirmation slot, and:
a. if no confirmation signal is received in the confirmation minislot, marking the current data slot as free to receive and remaining silent in the propagate minislot and ignoring data in the data sub-portion;
and
b. if a confirmation signal is received in the confirmation minislot, transmitting a propagation signal in the propagate minislot and receiving data in the data sub-portion from the transmitting apparatus.

12 more elements

Dependencies are inferred from the claim text.

Facts

Application: 10/007,321Filed 9 Nov 2001 · us provisional application
Priority: 9 Nov 2000
Published: US 2003/0012176 A116 Jan 2003
Granted: 16 Dec 2003
Term ends: Not estimatedThe source records don’t support an estimate.

Classification6 codes

H04W 28/16
Network traffic management; Network resource management: central resource management; Negotiation of resources or communication parameters, e.g.…
H04W 28/26
Central resource management; Negotiation of resources or communication parameters, e.g. negotiating bandwidth or QoS [Quality of Service]:…
H04W 72/20
Local resource management: control channels or signalling for resource management
H04W 74/0816
Using carrier sensing, e.g. carrier sense multiple access [CSMA]: with collision avoidance