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

• US 6,665,311 B2
• Filed: 11/09/2001
• Issued: 12/16/2003
• Est. Priority Date: 11/09/2000
• Status: Expired due to Fees

• Current Assignee: HRL Laboratories LLC (The Boeing Co.)
• Original Assignee: HRL Laboratories LLC (The Boeing Co.)
• Inventors: Kondylis, George, Kozat, Ulas, Marina, Mahesh, Ryu, Bong K.
• Primary Examiner(s): Chin, Wellington
• Assistant Examiner(s): SCHULTZ, WILLIAM C
• Application Number:
  US10/007,321
• Publication Number:
  US 20030012176A1
• Time in Patent Office: 767 Days
• Field of Search: 370/336, 370/337, 370/345, 370/347, 370/348, 370/468, 370/230, 370/321, 370/322, 370/324, 370/326, 370/458, 370/459, 370/461, 370/462
• US Class Current: 370/462
• CPC Class Codes: H04W 28/16 Central resource management; Negotiation of resources or communication parameters, e.g. negotiating bandwidth or QoS [Quality of Service]
• CPC Class Codes: H04W 28/26 Resource reservation
• CPC Class Codes: H04W 72/20 Control channels or signalling for resource management
• CPC Class Codes: H04W 74/0816 with collision avoidance
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks

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.

Claims

1. 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:

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.

2. A transmitting apparatus for adaptive bandwidth reservation in wireless ad-hoc networks as set forth in claim 1, further comprising a database stored in the memory for indicating whether a data slot is reserved for transmission.

3. A transmitting apparatus for adaptive bandwidth reservation in wireless ad-hoc networks as set forth in claim 1, wherein the request to send data includes an identifier for an intended recipient apparatus and a transmission data length.

4. A transmitting apparatus for adaptive bandwidth reservation in wireless ad-hoc networks as set forth in claim 3, wherein the means for receiving a (not) clear to send signal is configured to receive a (not) clear to send signal including the identifier for an intended recipient apparatus as transmitted by the request to send, and the transmission data length available for the transmission.

5. A transmitting apparatus for adaptive bandwidth reservation in wireless ad-hoc networks as set forth in claim 4, further comprising means, operating in the data processing system in correspondence to each minislot triplet, for determining whether to transmit data based on a comparison between the transmission data length and the transmission data length available for the transmission.

6. 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:

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.

7. A receiving apparatus for adaptive bandwidth reservation in wireless ad-hoc networks as set forth in claim 6, further comprising a database stored in the memory for indicating whether a data slot is free for reception, reserved for reception, or free for transmission.

8. A receiving apparatus for adaptive bandwidth reservation in wireless ad-hoc networks as set forth in claim 6, wherein the means for receiving a request to send data is configured to receive requests to send data that include an identifier for an intended recipient apparatus and a transmission data length.

9. A receiving apparatus for adaptive bandwidth reservation in wireless ad-hoc networks as set forth in claim 8, wherein the means for receiving a (not) clear to send signal is configured to receive a (not) clear to send signal including the identifier for an intended recipient apparatus as transmitted by the request to send, and the transmission data length available for the transmission.

10. 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.

11. A transmitting and receiving apparatus for adaptive bandwidth reservation in wireless ad-hoc networks as set forth in claim 10, further comprising a database stored in the memory for indicating whether a data slot is reserved for transmission, free for reception, reserved for reception, or free for transmission.

12. A transmitting and receiving apparatus for adaptive bandwidth reservation in wireless ad-hoc networks as set forth in claim 10, wherein the request to send data includes an identifier for an intended recipient apparatus and a transmission data length wherein the means for receiving a request to send data is configured to receive requests to send data that include an identifier for an intended recipient apparatus and a transmission data length.

13. A transmitting and receiving apparatus for adaptive bandwidth reservation in wireless ad-hoc networks as set forth in claim 12, wherein the (not) clear to send signal includes the identifier for an intended recipient apparatus as transmitted by the request to send, and wherein the means for receiving a (not) clear to send signal is configured to receive a (not) clear to send signal including the identifier for an intended recipient apparatus as transmitted by the request to send, and the transmission data length available for the transmission.

14. A transmitting and receiving apparatus for adaptive bandwidth reservation in wireless ad-hoc networks as set forth in claim 13, further comprising means, operating in the data processing system in correspondence to each minislot triplet, for determining whether to transmit data based on a comparison between the transmission data length and the transmission data length available for the transmission.

15. 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.

16. 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.