System and method for collision-free transmission scheduling in a network

• US 7,580,394 B2
• Filed: 11/27/2002
• Issued: 08/25/2009
• Est. Priority Date: 11/27/2002
• Status: Expired due to Fees

• Current Assignee: Nokia Corporation
• Original Assignee: Nokia Corporation
• Inventors: Garcia-Luna-Aceves, Jose J.
• Primary Examiner(s): Kincaid; Lester
• Assistant Examiner(s): HERRERA, DIEGO D
• Application Number:
  US10/306,613
• Publication Number:
  US 20040100929A1
• Time in Patent Office: 2,463 Days
• Field of Search: 370/338, 370/348, 370/349, 370/458, 370/459, 370/462, 370/463, 370/254, 370/400, 370/329
• US Class Current: 370/338
• CPC Class Codes: H04W 40/02 Communication route or path selection, e.g. power-based or shortest path routing
• CPC Class Codes: H04W 72/20 Control channels or signalling for resource management
• CPC Class Codes: H04W 72/535 based on resource usage policies

Abstract

A system and method is directed to enabling a collision-free transmission of a packet in a network by employing an access-point tree optimized MAC (ATOM) mechanism. The system enables a node in an ad hoc network to determine a collision-free transmission schedule based in part on information the node has about a distance to an access point along a routing tree rooted at the access point. The node may be assigned a time slot for collision-free transmission based in part on a bandwidth demand at the node, and traffic the node has to forward on behalf of a neighbor node.

Claims

1. A method, comprising:

sending a scheduling request over an access point tree to an access point, wherein the scheduling request comprises an aggregate of time slot requests associated with at least a node and a next hop node;

receiving a scheduling decision over the access point tree at the node for the node and the next hop node;

assigning a first orthogonal data channel to the access point, wherein a first time slot request in the scheduling decision enables communication over the first orthogonal data channel to a node that is one hop away from the access point; and

assigning a second orthogonal data channel to the node that is one hop away from the access point, wherein a second time slot request in the scheduling decision enables communication over the second orthogonal data channel between the node that is one hop away from the access point and another node that is two hops away from the access point,

wherein each time slot request in the scheduling decision is reserved for at least the next hop node and the node, and

wherein the scheduling decision enables the node to communicate a data packet collision-free over orthogonal data channels associated with the next hop node and the node.

2. The method of claim 1, wherein the orthogonal data channels further comprise multiple data channels that are based in part on a modulo three of a minimum hop distance of the node to the access point with data channel reuse.

3. The method of claim 1, wherein the scheduling decision further enables the node to communicate the data packet collision-free over orthogonal data channels between the node and a neighbor node.

4. The method of claim 1, further comprising:

assigning a third orthogonal data channel to the other node that is two hops away from the access point, wherein a third time slot request in the scheduling decision enables communication over the third orthogonal data channel between the other node that is two hops away from the access point and a third node that is three hops away from the access point.

5. The method of claim 1, further comprising:

determining the scheduling decision based in part on information associated with a number of hops to the access point along the access point tree that is rooted at the access point.

6. The method of claim 1, wherein the next hop node is identified based in part on at least one of a transmitter assigned local link identifier, and a medium access control address.

7. The method of claim 1, wherein the orthogonal data channels further comprise orthogonal data channels over the access point tree based in part on at least one of a frequency hop sequence, frequency band, data rate, direct-sequence code, and a frequency-hopped spreading code.

8. The method of claim 1, wherein sending the scheduling request further comprises employing a robust environmentally adaptive link medium access control protocol.

9. The method of claim 1, wherein sending the scheduling request and receiving the scheduling decision are based on a robust environmentally adaptive link medium access control, protocol and a two-hop neighborhood associated with the node.

10. The method of claim 1, wherein sending the scheduling request and receiving the scheduling decision further comprises communicating over a common channel in a broadcast mode.

11. The method of claim 1, further comprising:

assigning the node a time-slot for a collision-free communication of the data packet based in part on a bandwidth demand and communication of the node with at least one neighbor node.

12. The method of claim 1, wherein the network is an ad-hoc network.

13. The method of claim 1, further comprising:

determining the access point tree based on at least one of a static routing protocol, distance vector routing protocol, link state routing protocol, and a hybrid routing protocol.

14. An apparatus, comprising:

a transceiver configured to send a scheduling request over an access point tree to an access point and configured to receive a scheduling decision over the access point tree from the access point; and

a transcoder configured to

enable the scheduling request to comprise an aggregate of time slot requests associated with at least the apparatus and a next hop node, and

employ the scheduling decision to determine each time slot request that is reserved for at least the next hop node and the apparatus,

wherein the scheduling decision enables the apparatus to communicate the data packet collision-free over orthogonal data channels associated with the next hop node and the apparatus,

wherein the orthogonal data channels comprise a first orthogonal data channel to the access point, wherein a first time slot request in the scheduling decision enables communication over the first orthogonal data channel to a node that is one hop away from the access point, and

wherein the orthogonal data channels further comprise a second orthogonal data channel to the node that is one hop away from the access point, wherein a second time slot request in the scheduling decision enables communication over the second orthogonal data channel between the node that is one hop away from the access point and another node that is two hops away from the access point.

15. The apparatus of claim 14, wherein the orthogonal data channels further comprise multiple data channels that are based in part on a modulo three of a minimum hop distance of the apparatus to the access point with data channel reuse.

16. The apparatus of claim 14, wherein the scheduling decision further enables the apparatus to communicate the data packet collision-free over orthogonal data channels between the apparatus and a neighbor node.

17. The apparatus of claim 14, wherein the scheduling decision is based in part on information associated with a number of hops to the access point along the access point tree that is rooted at the access point.

18. The apparatus of claim 14, wherein the next hop node is identified based in part on at least one of a transmitter assigned local link identifier, and a medium access control address.

19. The apparatus of claim 14, wherein the orthogonal data channels further comprise orthogonal data channels over the access point tree based in part on at least one of a frequency hop sequence, frequency band, data rate, direct-sequence code, and a frequency-hopped spreading code.

20. The apparatus of claim 14, wherein sending the scheduling request further comprises employing a robust environmentally adaptive link medium access control protocol.

21. The apparatus of claim 14, wherein the transceiver is further configured to send the scheduling request and receive the scheduling decision based on a robust environmentally adaptive link medium access control protocol and a two-hop neighborhood associated with the apparatus.

22. The apparatus of claim 14, wherein the transceiver is further configured to send the scheduling request and receive the scheduling decision over a common channel in a broadcast mode.

23. The apparatus of claim 14, wherein each time slot request is based in part on a bandwidth demand and communication of the node with at least one neighbor node.

24. A system, comprising:

a node that is configured to send a scheduling request over an access point tree to an access point, wherein the scheduling request comprises an aggregate of time slot requests associated with at least the node and a next hop node; and

an access point that is configured to

determine a scheduling decision over the access point tree in response to the aggregated request,

transmit the scheduling decision over the access point tree to the node and the next hop node,

assign a first orthogonal data channel to the access point, wherein a first time slot request in the scheduling decision enables communication over the first orthogonal data channel to a node that is one hop away from the access point, and

assign a second orthogonal data channel to the node that is one hop away from the access point, wherein a second time slot request in the scheduling decision enables communication over the second orthogonal data channel between the node that is one hop away from the access point and another node that is two hops away from the access point.

wherein each time slot request in the scheduling decision is reserved for at least the next hop node and the node, and

wherein the scheduling decision enables the node to communicate the data packet collision-free over orthogonal data channels associated with the next hop node and the node.

25. The system of claim 24, wherein the orthogonal data channels further comprise multiple data channels that are based in part on a modulo three of a minimum hop distance of the node to the access point with data channel reuse.

26. The system of claim 24, wherein the scheduling decision further enables the node to communicate the data packet collision-free over orthogonal data channels between the node and a neighbor node.

27. The system of claim 24, wherein the access point determines the scheduling decision based in part on information associated with a number of hops to the access point along the access point tree that is rooted at the access point.

28. The system of claim 24, wherein the next hop node is identified based in part on at least one of a transmitter assigned local link identifier, and a medium access control address.

29. The system of claim 24, wherein the orthogonal data channels further comprise orthogonal data channels over the access point tree based in part on at least one of a frequency hop sequence, frequency band, data rate, direct-sequence code, and a frequency-hopped spreading code.

30. The system of claim 24, wherein sending the scheduling request further comprises employing a robust environmentally adaptive link medium access control protocol.

31. The system of claim 24, wherein sending the scheduling request is based on a robust environmentally adaptive link medium access control protocol and a two-hop neighborhood associated with the node.

32. A method, comprising:

assigning a node to an access point;

selecting an anchor node for the node, wherein the anchor node is selected as a next hop node along a hop path to the access point;

determining an access point tree based in part on the selected anchor node;

sending a scheduling request over the access point tree to the access point, wherein the scheduling request comprises an aggregate of time slot requests associated with at least the node and the anchor node;

determining a scheduling decision in response to the scheduling request; and

receiving the scheduling decision over the access point tree at the node for the node and the anchor node,

wherein each time slot request in the scheduling decision is reserved for at least the anchor node and the node,

wherein the scheduling decision enables the node to communicate the data packet collision-free over orthogonal data channels associated with the anchor node and the node,

wherein the orthogonal data channels comprise a first orthogonal data channel to the access point, wherein a first time slot request in the scheduling decision enables communication over the first orthogonal data channel to a node that is one hop away from the access point, and

wherein the orthogonal data channels further comprise a second orthogonal data channel to the node that is one hop away from the access point, wherein a second time slot request in the scheduling decision enables communication over the second orthogonal data channel between the node that is one hop away from the access point and another node that is two hops away from the access point.

33. A computer-readable program distribution medium encoding a computer program of instructions being configured to control a processor to perform:

communicating transmission-scheduling information between nodes in a network;

wherein the transmission-scheduling information includes routing information over a spanning tree rooted at an access point; and

sending a scheduling request over the access point tree to the access point, wherein the scheduling request comprises an aggregate of time slot requests associated with at least a node and a next hop node,

wherein each time slot request in a scheduling decision is reserved for at least the node and the next hop node,

wherein the scheduling decision enables the node to communicate a data packet collision-free over orthogonal data channels associated with the node and the next hop node,

wherein the orthogonal data channels comprise a first orthogonal data channel to the access point, wherein a first time slot request in the scheduling decision enables communication over the first orthogonal data channel to a node that is one hop away from the access point, and

wherein the orthogonal data channels further comprise a second orthogonal data channel to the node that is one hop away from the access point, wherein a second time slot request in the scheduling decision enables communication over the second orthogonal data channel between the node that is one hop away from the access point and another node that is two hops away from the access point.

34. An apparatus, comprising:

sending means for sending a scheduling request over an access point tree to an access point, wherein the scheduling request comprises an aggregate of time slot requests associated with at least a node and a next hop node; and

receiving means for receiving a scheduling decision over the access point tree at the node for the node and the next hop node,

wherein each time slot request in the scheduling decision is reserved for at least the next hop node and the node, and

wherein the scheduling decision enables the node to communicate the data packet collision-free over orthogonal data channels associated with the next hop node and the node,

wherein the orthogonal data channels comprise a first orthogonal data channel to the access point, wherein a first time slot request in the scheduling decision enables communication over the first orthogonal data channel to a node that is one hop away from the access point, and

wherein the orthogonal data channels further comprise a second orthogonal data channel to the node that is one hop away from the access point, wherein a second time slot request in the scheduling decision enables communication over the second orthogonal data channel between the node that is one hop away from the access point and another node that is two hoes away from the access point.

35. An apparatus, comprising:

transceiver means for sending a scheduling request over an access point tree to an access point and for receiving a scheduling decision over the access point tree from the access point; and

transcoder means for

enabling the scheduling request to comprise an aggregate of time slot requests associated with at least the apparatus and a next hop node, and

employing the scheduling decision to determine each time slot request that is reserved for at least the next hop node and the apparatus,

wherein the scheduling decision enables the apparatus to communicate the data packet collision-free over orthogonal data channels associated with the next hop node and the apparatus,

wherein the orthogonal data channels comprise a first orthogonal data channel to the access point, wherein a first time slot request in the scheduling decision enables communication over the first orthogonal data channel to a node that is one hop away from the access point, and

wherein the orthogonal data channels further comprise a second orthogonal data channel to the node that is one hop away from the access point, wherein a second time slot request in the scheduling decision enables communication over the second orthogonal data channel between the node that is one hop away from the access point and another node that is two hops away from the access point.