Method and apparatus for multicasting real time traffic in wireless ad-hoc networks

• US 6,721,290 B1
• Filed: 04/03/2000
• Issued: 04/13/2004
• Est. Priority Date: 04/03/2000
• Status: Expired due to Fees

• Current Assignee: HRL Laboratories LLC (The Boeing Co.)
• Original Assignee: HRL Laboratories LLC (The Boeing Co.)
• Inventors: Dao, Son, Kondylis, George D., Krishnamurthy, Srikanth V.
• Primary Examiner(s): VANDERPUYE, KENNETH N
• Application Number:
  US09/541,177
• Time in Patent Office: 1,471 Days
• Field of Search: 370/229, 370/390, 370/319, 370/320, 370/321, 370/342, 370/344, 370/347, 370/329, 370/338, 370/348
• US Class Current: 370/329
• CPC Class Codes: H04L 12/1854 with non-centralised forwarding system, e.g. chaincast
• CPC Class Codes: H04L 12/1886 with traffic restrictions for efficiency improvement, e.g. involving subnets or subdomains
• CPC Class Codes: H04L 12/189 in combination with wireless systems selective distribution or broadcast in wireless communication networks H04W4/06
• CPC Class Codes: H04W 28/26 Resource reservation
• CPC Class Codes: H04W 74/04 Scheduled access hybrid access H04W74/02
• 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 constant bit rate data in wireless ad-hoc networks. Constant 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 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, 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 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;

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 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;

c. periodically transmitting a temporarily disconnected maintenance packet from each temporarily disconnected node, with each temporarily disconnected maintenance packet including the node ID of the temporarily disconnected maintenance packet transmitting node, the node ID of the parent node from which temporarily disconnected node seeks to receive, the frame position fp of the node transmitting the temporarily disconnected maintenance packet, the color in which the temporarily disconnected maintenance packet transmitting node seeks to receive, a set of the usable colors in which the temporarily disconnected node is transmitting, and a set of unusable colors in which the temporarily disconnected 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 Na having frame position fpa includes color ca if there is at least one other node Nb within transmit range of the first node Na, having frame position fpb, where Nb is not a child of node Na, where Nb receives at color ca, and where (fpa+1) mod p=fpb mod p where p represents the data period p; and

f. establishing data connections for the disconnected nodes Nd and temporarily disconnected nodes Nd, where a node Nd can connect to a node Nc with color cd within a transmission range of the node Nd, and with a minimum frame position fpc=fpd−

1 only if node Nc can transmit at color cd, where color cd=color ca as determined in step e, and only if color cd is not a transmit color of any other node Nk with frame position fpk within the transmission range of the first node Nd, such that fpc mod p=fpk mod p where p represents the data period p;

g. periodically repeating steps a through f 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 1.

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

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

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

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. periodically transmitting a temporarily disconnected maintenance packet from each temporarily disconnected node, with each temporarily disconnected maintenance packet including the node ID of the temporarily disconnected maintenance packet transmitting node, the node ID of the parent node from which temporarily disconnected node seeks to receive, the frame position fp of the node transmitting the temporarily disconnected maintenance packet, the color in which the temporarily disconnected maintenance packet transmitting node seeks to receive, a set of the usable colors in which the temporarily disconnected node is transmitting, and a set of unusable colors in which the temporarily disconnected node is prohibited from transmitting;

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

f. 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 Na having frame position fpa includes color ca if there is at least one other node Nb within transmit range of the first node Na, having frame position fpb, where Nb is not a child of node Na, where Nb receives at color ca, and where (fpa+1) mod p=fpb mod p where p represents the data period p;

g. establishing data connections for the disconnected nodes Nd and temporarily disconnected nodes Nd, where a node Nd can connect to a node Nc with color cd within a transmission range of the node Nd, and with a minimum frame position fpc=fpd−

1 only if node Nc can transmit at color cd, where color cd=color ca as determined in step e, and only if color cd is not a transmit color of any other node Nk with frame position fpk within the transmission range of the first node Nd, such that fpc mod p=fpk mod p where p represents the data period p; and

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

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