Method and apparatus for multicasting real-time variable bit-rate traffic in wireless Ad-Hoc networks

• US 6,621,805 B1
• Filed: 08/03/2000
• Issued: 09/16/2003
• Est. Priority Date: 10/25/1999
• Status: Expired due to Term

• Current Assignee: HRL Laboratories LLC A Limited Liability Company of Delaware
• Original Assignee: HRL Laboratories LLC (The Boeing Co.)
• Inventors: Dao, Son, Kondylis, George D., Krishnamurthy, Srikanth V.
• Primary Examiner(s): Hsu, Alpus H.
• Assistant Examiner(s): Qureshi, Afsar M.
• Application Number:
  US09/631,485
• Time in Patent Office: 1,139 Days
• Field of Search: 370/329, 370/331, 370/335, 370/342, 370/344, 370/349, 370/347, 370/445, 370/320, 370/321, 370/336, 370/337, 370/395.21, 370/395.2, 370/395.4, 370/395.43, 370/389, 455/445-455, 455/446, 455/500, 455/502, 455/503, 455/507, 455/524, 455/525
• US Class Current: 370/329
• CPC Class Codes: H04L 47/15 in relation to multipoint traffic arrangements for broadcast or multicast in data networks H04L12/18
• CPC Class Codes: H04L 47/2416 Real-time traffic
• CPC Class Codes: H04L 47/283 in response to processing delays, e.g. caused by jitter or round trip time [RTT]
• CPC Class Codes: H04L 47/70 Admission control; Resource allocation
• CPC Class Codes: H04L 47/724 at intermediate nodes, e.g. resource reservation protocol [RSVP]
• CPC Class Codes: H04L 47/783 Distributed allocation of resources, e.g. bandwidth brokers
• CPC Class Codes: H04L 47/801 Real time traffic
• CPC Class Codes: H04L 47/806 Broadcast or multicast traffic
• CPC Class Codes: H04L 47/824 Applicable to portable or mobile terminals
• CPC Class Codes: H04W 28/10 Flow control between communication endpoints
• CPC Class Codes: H04W 28/26 Resource reservation
• CPC Class Codes: H04W 4/00 Services specially adapted for wireless communication networks; Facilities therefor
• CPC Class Codes: H04W 74/04 Scheduled access hybrid access H04W74/02
• CPC Class Codes: H04W 8/04 Registration at HLR or HSS [Home Subscriber Server]
• CPC Class Codes: H04W 8/22 Processing or transfer of terminal data, e.g. status or physical capabilities
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks

Abstract

A real-time multicast scheduler method and apparatus is presented, to facilitate multicasting of real-time variable bit rate data in wireless ad-hoc networks. Variable bit rate traffic cannot tolerate delay jitter. However, a small amount of packet losses may be tolerable. In order to ensure the provisioning of a desired level of quality of service, bandwidth is reserved on the multicast structure. A goal of the real-time multicast scheduler is to avoid packet collisions and to facilitate color re-use, where “color” is defined as a channel selected as a combination of time-division multiple access, frequency-division multiple access, and code-division multiple access schemes. The real-time multicast scheduler provides a self-healing network which corrects for disconnections caused by node movement and nodes moving out of range of each other, while accounting for colors already assigned for data transmission in order to prevent packet collisions.

Claims

1. A method for bandwidth reservation for real-time traffic in a wireless ad-hoc network including a plurality of nodes transmitting and receiving data via a plurality of colors, with the transmitting and receiving of the data being performed periodically with a data period 2, wherein each one of the plurality of nodes has a connection state selected from the group consisting of connected and disconnected, wherein the plurality of nodes includes a communication origin node from which a data transmission occurs, and wherein each node has a super-frame including a transmitting frame for transmitting packets and a receiving frame for receiving packets, with the transmitting packets having a transmit sequence within the transmitting frame and the receiving packets having a receiving sequence within the receiving frame, with a frame position F defining the position of transmitting frame in the super-frame, a set of transmit colors in which the node is currently transmitting, a set of colors in which the node is currently receiving, a set of usable colors, and a set of unusable colors, wherein the nodes which a particular node receives from are identified as the parents of the particular node, with the particular node identified as the child of the parent nodes, and wherein a transmitting frame of a parent node is the receiving frame of its child node, and wherein the method comprising the steps of:

a. periodically transmitting a disconnected maintenance packet from each disconnected node, with each disconnected maintenance packet including the disconnected maintenance packet transmitting node ID, the node IDs of the parent nodes from which disconnected node seeks to receive, the frame position F of the disconnected maintenance packet transmitting node, the colors in which the disconnected maintenance packet transmitting disconnected node seeks to receive, and the receiving sequence for the disconnected maintenance packet transmitting node;

b. periodically transmitting a connected maintenance packet from each connected node, with each connected maintenance packet including the node ID of the connected maintenance packet transmitting node, the node IDs of the parent nodes from which connected node is currently receiving, the frame position of the node transmitting the connected maintenance packet, the colors in which the connected maintenance packet transmitting node receives, the receiving sequence for the maintenance packet transmitting node, a set of the usable colors in which the connected node may transmit, and a set of unusable colors in which the connected node is prohibited from transmitting;

c. receiving, at each particular node of the plurality of nodes, the maintenance packets from all nodes within a transmission range of the particular node;

d. using the maintenance packets received at each particular node to update the set of usable colors and the set of unusable colors for the particular node, where the set of usable colors for the particular node is defined as the complement of the set of unusable colors, and where the set of unusable colors of a first node N0 having transmit frame position F0 includes color c0 if there is at least one node Nj within transmit range of node N0, having a receive frame position of F0, such that node Nj is not a child of node N0, where node Nj receives in color c0 from a parent node Ni, and where $\mathrm{SIR}<br><br>\text{\hspace{1em}<br><br>}<br><br>\left(N_j\right)=\frac{G_{\mathrm{ij}}}{\underset{k\ne <br><br>i}{\overset{\text{\hspace{1em}<br><br>}}{\sum <br><br>}}<br><br>\text{\hspace{1em}<br><br>}<br><br>G_{\mathrm{kj}}+G_{0<br><br>j}}<<br><br>{\mathrm{\gamma <br><br>}}_1,$

 

for a preset γ

₁, such that γ

₁>

γ

, where;

k represents an index over all of the nodes having transmit frame positions of F0 and transmit color C0;

G_ij represents the transmission power loss between the parent node Ni and node Nj;

G_kj represents the transmission power loss between a given node having an index k and transmit frame position F0, and node Nj;

G_0j represents the transmission power loss between node N0 and node Nj;

γ

represents the threshold SIR for a transmission, below which a transmission cannot take place; and

γ

₁ represents a preset SIR level greater than γ and

chosen to decrease the probability of SIR(Nj)<

γ

; and

e. reserving colors c0 and establishing data connections for connected and disconnected nodes Na, where a node Na can reserve color ca for receiving from a neighboring node Nc if node Na has receive frame Fc, and if node Nc can transmit in color ca as determined in step d, and if the SIR of node Na satisfies the equation;

$\mathrm{SIR}<br><br>\text{\hspace{1em}<br><br>}<br><br>\left(N_a\right)=\frac{G_{\mathrm{ca}}}{\underset{k\ne <br><br>c}{\overset{\text{\hspace{1em}<br><br>}}{\sum <br><br>}}<br><br>\text{\hspace{1em}<br><br>}<br><br>G_{\mathrm{ka}}}><br><br>{\mathrm{\gamma <br><br>}}_2,$

 

for some preset γ

₂, such that γ

₂>

γ

, where;

k represents an index over all of the nodes having transmit frame positions of Fc and transmit color ca;

G_ca represents the transmission power loss between node Nc and node Na;

G_ka represents the transmission power loss between a given node having an index k and a frame position Fc, and node Na;

γ

represents the threshold SIR for a transmission, below which a transmission cannot take place; and

γ

₂ represents a preset SIR level greater than γ and

chosen to decrease the probability of SIR(Na)<

γ

; and

f. periodically repeating steps a through e to update the ad-hoc network.

2. A method for bandwidth reservation for real-time traffic in a wireless ad-hoc network as set forth in claim 1, wherein the colors are channels developed from combinations selected from the group consisting of TDMA, CDMA, and FDMA schemes.

3. A wireless ad-hoc network developed and maintained by the method of claim 2.

4. A wireless ad-hoc network including a plurality of nodes transmitting and receiving data via a plurality of colors, with the transmitting and receiving of the data being performed periodically with a data period p, wherein each one of the plurality of nodes has a connection state selected from the group consisting of connected, disconnected, and temporarily disconnected, wherein the plurality of nodes includes a communication origin node from which a data transmission occurs, and wherein each node has a frame position fp with respect to the origin node, a set of transmit colors in which the node is currently transmitting, a color in which the node is currently receiving, a set of usable colors, and a set of unusable colors, wherein the node which a particular node receives from is identified as the parent of the particular node, with the particular node identified as the child of the parent node, said wireless ad-hoc network developed and maintained by the method of claim 2.

5. A wireless ad-hoc network developed and maintained by the method of claim 1.

6. A wireless ad-hoc network including a plurality of nodes transmitting and receiving data via a plurality of colors, with the transmitting and receiving of the data being performed periodically with a data period p, wherein each one of the plurality of nodes has a connection state selected from the group consisting of connected, disconnected, and temporarily disconnected, wherein the plurality of nodes includes a communication origin node from which a data transmission occurs, and wherein each node has a frame position fp with respect to the origin node, a set of transmit colors in which the node is currently transmitting, a color in which the node is currently receiving, a set of usable colors, and a set of unusable colors, wherein the node which a particular node receives from is identified as the parent of the particular node, with the particular node identified as the child of the parent node, said wireless ad-hoc network developed and maintained by the method of claim 1.

7. A method for bandwidth reservation for real-time traffic in a wireless ad-hoc network including the steps of:

a. providing a plurality of nodes transmitting and receiving data via a plurality of colors, with the transmitting and receiving of the data being performed periodically with a data period p, wherein each one of the plurality of nodes has a connection state selected from the group consisting of connected, disconnected, and temporarily disconnected, wherein the plurality of nodes includes a communication origin node from which a data transmission occurs, and wherein each node has a frame position fp with respect to the origin node, a set of transmit colors in which the node is currently transmitting, a color in which the node is currently receiving, a set of usable colors, and a set of unusable colors, wherein the node which a particular node receives from is identified as the parent of the particular node, with the particular node identified as the child of the parent node;

b. periodically transmitting a disconnected maintenance packet from each disconnected node, with each disconnected maintenance packet including the disconnected maintenance packet transmitting node ID, the node ID of a parent node from which the disconnected node seeks to receive, the frame position fp of the disconnected maintenance transmitting node, and the color in which the disconnected maintenance packet transmitting disconnected node seeks to receive;

c. periodically transmitting a connected maintenance packet from each connected node, with each connected maintenance packet including the node ID of the connected maintenance packet transmitting node, the node ID of the parent node from which connected node is currently receiving, the frame position fp of the node transmitting the connected maintenance packet, the color in which the connected maintenance packet transmitting node receives, a set of the usable colors in which the connected node may transmit, and a set of unusable colors in which the connected node is prohibited from transmitting;

d. receiving, at each particular node of the plurality of nodes, the maintenance packets from all nodes within a transmission range of the particular node;

e. using the maintenance packets received at each particular node to update the set of usable colors and the set of unusable colors for the particular node, where the set of usable colors for the particular node is defined as the complement of the set of unusable colors, and where the set of unusable colors of a first node N0 having transmit frame position F0 includes color c0 if there is at least one node Nj within transmit range of node N0, having a receive frame position of F0, such that node Nj is not a child of node N0, where node Nj receives in color c0 from a parent node Ni, and where $\mathrm{SIR}<br><br>\text{\hspace{1em}<br><br>}<br><br>\left(N_j\right)=\frac{G_{\mathrm{ij}}}{\underset{k\ne <br><br>l}{\overset{\text{\hspace{1em}<br><br>}}{\sum <br><br>}}<br><br>\text{\hspace{1em}<br><br>}<br><br>G_{\mathrm{kj}}+G_{0<br><br>j}}<<br><br>{\mathrm{\gamma <br><br>}}_1,$

 

for a preset γ

₁, such that γ

₁>

γ

, where;

k represents an index over all of the nodes having transmit frame positions of F0 and transmit color C0;

G_ij represents the transmission power loss between the parent node Ni and node Nj;

G_kj represents the transmission power loss between a given node having an index k and transmit frame position F0, and node Nj;

G_0j represents the transmission power loss between node N0 and node Nj;

γ

represents the threshold SIR for a transmission, below which a transmission cannot take place; and

γ

₁ represents a preset SIR level greater than γ and

chosen to decrease the probability of SIR(Nj)<

γ

; and

f. reserving colors c0 and establishing data connections for connected and disconnected nodes Na, where a node Na can reserve color ca for receiving from a neighboring node Nc if node Na has receive frame Fc, and if node Nc can transmit in color ca as determined in step d, and if the SIR of node Na satisfies the equation;

$\mathrm{SIR}<br><br>\text{\hspace{1em}<br><br>}<br><br>\left(N_a\right)=\frac{G_{\mathrm{ca}}}{\underset{k\ne <br><br>c}{\overset{\text{\hspace{1em}<br><br>}}{\sum <br><br>}}<br><br>\text{\hspace{1em}<br><br>}<br><br>G_{\mathrm{ka}}}><br><br>{\mathrm{\gamma <br><br>}}_2,$

 

for some preset γ

₂, such that γ

₂>

γ

, where;

k represents an index over all of the nodes having transmit frame positions of Fc and transmit color Ca;

G_ca represents the transmission power loss between node Nc and node Na;

G_ka represents the transmission power loss between a given node having an index k and a frame position Fc, and node Na;

γ

represents the threshold SIR for a transmission, below which a transmission cannot take place; and

γ

₂ represents a preset SIR level greater than γ and

chosen to decrease the probability of SIR(Na)<

γ

; and

g. periodically repeating steps a through f to update the ad-hoc network.

8. A method for bandwidth reservation for real-time traffic in a wireless ad-hoc network as set forth in claim 7, wherein the colors are channels developed from combinations selected from the group consisting of TDMA, CDMA, and FDMA schemes.

9. A wireless ad-hoc network developed and maintained by the method of claim 8.

10. A wireless ad-hoc network developed and maintained by the method of claim 7.

11. A method for bandwidth reservation for real-time traffic in a wireless ad-hoc network including a plurality of nodes transmitting and receiving data via a plurality of colors, with the transmitting and receiving of the data being performed periodically with a data period 2, wherein each one of the plurality of nodes has a connection state selected from the group consisting of connected and disconnected, wherein the plurality of nodes includes a communication origin node from which a data transmission occurs, and wherein each node has a super-frame including a transmitting frame for transmitting packets and a receiving frame for receiving packets, with the transmitting packets having a transmit sequence within the transmitting frame and the receiving packets having a receiving sequence within the receiving frame, with a frame position F defining the position of transmitting frame in the super-frame, a set of transmit colors in which the node is currently transmitting, a set of colors in which the node is currently receiving, a set of usable colors, and a set of unusable colors, wherein the nodes which a particular node receives from are identified as the parents of the particular node, with the particular node identified as the child of the parent nodes, and wherein a transmitting frame of a parent node is the receiving frame of its child node, and wherein the method comprising the steps of:

a. periodically transmitting a disconnected maintenance packet from each disconnected node, with each disconnected maintenance packet including the disconnected maintenance packet transmitting node ID, the node IDs of the parent nodes from which disconnected node seeks to receive, the frame position F of the disconnected maintenance packet transmitting node, the colors in which the disconnected maintenance packet transmitting disconnected node seeks to receive, and the receiving sequence for the disconnected maintenance packet transmitting node;

b. periodically transmitting a connected maintenance packet from each connected node, with each connected maintenance packet including the node ID of the connected maintenance packet transmitting node, the node IDs of the parent nodes from which connected node is currently receiving, the frame position of the node transmitting the connected maintenance packet, the colors in which the connected maintenance packet transmitting node receives, the receiving sequence for the maintenance packet transmitting node, a set of the usable colors in which the connected node may transmit, and a set of unusable colors in which the connected node is prohibited from transmitting;

c. receiving, at each particular node of the plurality of nodes, the maintenance packets from all nodes within a transmission range of the particular node;

d. using the maintenance packets received at each particular node to update the set of usable colors and the set of unusable colors for the particular node, where the set of usable colors for the particular node is defined as the complement of the set of unusable colors, and where the set of unusable colors of a first node N0 having transmit frame position F0 includes color c0 if there is at least one node Nj within transmit range of node N0, having a receive frame position of F0, such that node Nj is not a child of node N0, where node N₀ receives in color c0; and

e. reserving colors c0 and establishing data connections for connected and disconnected nodes Na, where a node Na can reserve color ca for receiving from a neighboring node Nc if node Na has receive frame Fc, and if node Nc can transmit in color c0 as determined in step d, and if the SIR of node Na satisfies the equation;

$\mathrm{SIR}<br><br>\text{\hspace{1em}<br><br>}<br><br>\left(N_a\right)=\frac{G_{\mathrm{ca}}}{\underset{k\ne <br><br>c}{\overset{\text{\hspace{1em}<br><br>}}{\sum <br><br>}}<br><br>\text{\hspace{1em}<br><br>}<br><br>G_{\mathrm{ka}}}<<br><br>{\mathrm{\gamma <br><br>}}_2,$

 

for some preset γ

₂, such that γ

₂>

γ

, where;

k represents an index over all of the nodes having transmit frame positions of Fa and transmit color C0;

G_ja represents the transmission power loss between node Nc and node Na;

G_ka represents the transmission power loss between a given node having an index k and a frame position Fc, and node Na;

γ

represents the threshold SIR for a transmission, below which a transmission cannot take place; and

γ

₂ represents a preset SIR level greater than γ and

chosen to decrease the probability of SIR(Nc)<

γ

; and

f. periodically repeating steps a through e to update the ad-hoc network.

12. A method for bandwidth reservation for real-time traffic in a wireless ad-hoc network as set forth in claim 11, wherein the colors are channels developed from combinations selected from the group consisting of TDMA, CDMA, and FDMA schemes.

13. A wireless ad-hoc network developed and maintained by the method of claim 12.

14. A wireless ad-hoc network developed and maintained by the method of claim 11.

15. A wireless ad-hoc network including a plurality of nodes transmitting and receiving data via a plurality of colors, with the transmitting and receiving of the data being performed periodically with a data period p, wherein each one of the plurality of nodes has a connection state selected from the group consisting of connected, disconnected, and temporarily disconnected, wherein the plurality of nodes includes a communication origin node from which a data transmission occurs, and wherein each node has a frame position fp with respect to the origin node, a set of transmit colors in which the node is currently transmitting, a color in which the node is currently receiving, a set of usable colors, and a set of unusable colors, wherein the node which a particular node receives from is identified as the parent of the particular node, with the particular node identified as the child of the parent node, said wireless ad-hoc network developed and maintained by the method of claim 12.

16. A wireless ad-hoc network including a plurality of nodes transmitting and receiving data via a plurality of colors, with the transmitting and receiving of the data being performed periodically with a data period p, wherein each one of the plurality of nodes has a connection state selected from the group consisting of connected, disconnected, and temporarily disconnected, wherein the plurality of nodes includes a communication origin node from which a data transmission occurs, and wherein each node has a frame position fp with respect to the origin node, a set of transmit colors in which the node is currently transmitting, a color in which the node is currently receiving, a set of usable colors, and a set of unusable colors, wherein the node which a particular node receives from is identified as the parent of the particular node, with the particular node identified as the child of the parent node, said wireless ad-hoc network developed and maintained by the method of claim 11.

17. A method for bandwidth reservation for real-time traffic in a wireless ad-hoc network including the steps of:

a. providing a plurality of nodes transmitting and receiving data via a plurality of colors, with the transmitting and receiving of the data being performed periodically with a data period p, wherein each one of the plurality of nodes has a connection state selected from the group consisting of connected, disconnected, and temporarily disconnected, wherein the plurality of nodes includes a communication origin node from which a data transmission occurs, and wherein each node has a frame position fp with respect to the origin node, a set of transmit colors in which the node is currently transmitting, a color in which the node is currently receiving, a set of usable colors, and a set of unusable colors, wherein the node which a particular node receives from is identified as the parent of the particular node, with the particular node identified as the child of the parent node;

b. periodically transmitting a disconnected maintenance packet from each disconnected node, with each disconnected maintenance packet including the disconnected maintenance packet transmitting node ID, the node ID of a parent node from which the disconnected node seeks to receive, the frame position fp of the disconnected maintenance transmitting node, and the color in which the disconnected maintenance packet transmitting disconnected node seeks to receive;

c. periodically transmitting a connected maintenance packet from each connected node, with each connected maintenance packet including the node ID of the connected maintenance packet transmitting node, the node ID of the parent node from which connected node is currently receiving, the frame position fp of the node transmitting the connected maintenance packet, the color in which the connected maintenance packet transmitting node receives, a set of the usable colors in which the connected node may transmit, and a set of unusable colors in which the connected node is prohibited from transmitting;

d. receiving, at each particular node of the plurality of nodes, the maintenance packets from all nodes within a transmission range of the particular node;

e. using the maintenance packets received at each particular node to update the set of usable colors and the set of unusable colors for the particular node, where the set of usable colors for the particular node is defined as the complement of the set of unusable colors, and where the set of unusable colors of a first node N0 having transmit frame position F0 includes color c0 if there is at least one node Nj within transmit range of node N0, having a receive frame position of F0, such that node Nj is not a child of node N0, where node N0 receives in color c0;

f. reserving colors c0 and establishing data connections for connected and disconnected nodes Na, where a node Na can reserve color ca for receiving from a neighboring node Nc if node Na has receive frame Fc, and if node Nc can transmit in color c0 as determined in step d, and if the SIR of node Na satisfies the equation;

$\mathrm{SIR}<br><br>\text{\hspace{1em}<br><br>}<br><br>\left(N_a\right)=\frac{G_{\mathrm{ca}}}{\underset{k\ne <br><br>c}{\overset{\text{\hspace{1em}<br><br>}}{\sum <br><br>}}<br><br>\text{\hspace{1em}<br><br>}<br><br>G_{\mathrm{ka}}}><br><br>{\mathrm{\gamma <br><br>}}_2,$

 

for some preset γ

₂, such that γ

₂>

γ

, where;

k represents an index over all of the nodes having transmit frame positions of Fa and transmit color C0;

G_ja represents the transmission power loss between node Nc and node Na;

G_ka represents the transmission power loss between a given node having an index k and a frame position Fc, and node Na;

γ

represents the threshold SIR for a transmission, below which a transmission cannot take place; and

γ

₂ represents a preset SIR level greater than γ and

chosen to decrease the probability of SIR(Nc)<

γ

; and

g. periodically repeating steps a through f to update the ad-hoc network.

18. A method for bandwidth reservation for real-time traffic in a wireless ad-hoc network as set forth in claim 17, wherein the colors are channels developed from combinations selected from the group consisting of TDMA, CDMA, and FDMA schemes.

19. A wireless ad-hoc network developed and maintained by the method of claim 18.

20. A wireless ad-hoc network developed and maintained by the method of claim 17.