System and method for collision-free transmission scheduling using neighborhood information and advertised transmission times

• US 6,791,997 B2
• Filed: 08/26/2002
• Issued: 09/14/2004
• Est. Priority Date: 08/25/2001
• Status: Expired due to Term

• Current Assignee: Nokia Corporation
• Original Assignee: Nokia Corporation
• Inventors: Beyer, David, Garcia-Luna-Aceves, Jose J.
• Primary Examiner(s): Jung, Min
• Application Number:
  US10/228,173
• Publication Number:
  US 20030067892A1
• Time in Patent Office: 750 Days
• Field of Search: 370/336, 370/442, 370/447, 370/448, 370/461, 370/252, 370/254, 370/255
• US Class Current: 370/447
• CPC Class Codes: H04L 45/20 Hop count for routing purposes, e.g. TTL
• CPC Class Codes: H04W 40/24 Connectivity information management, e.g. connectivity discovery or connectivity update
• CPC Class Codes: H04W 72/20 Control channels or signalling for resource management
• CPC Class Codes: H04W 72/535 based on resource usage policies
• CPC Class Codes: H04W 8/245 from a network towards a terminal
• CPC Class Codes: H04W 80/02 Data link layer protocols
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks

Abstract

The present invention provides a medium access control (MAC) protocol for the collision-free transmission of packets into a channel, such that nodes are assigned time slots for collision-free transmission based on the knowledge that they acquire regarding the constituency of their local neighborhoods and the advertisements of the time slots when nodes in local neighborhoods will attempt to transmit again.

The scheduling procedure may utilize an age of the network together with the unique identifiers of nodes. The candidate transmission times for each node are determined using a list of the subsequent transmission times advertised by other nodes. The node discards the advertised transmission times from the list of potential transmission times, and computes its candidate transmission times using a function that provides a varying (pseudorandom) distribution of outputs for a varying sample of inputs. This function ay be a hash function, an encryption function, or a table lookup function. The computation of the candidate transmission times uses the identifiers of those nodes for which no advertised transmission time has been obtained.

Claims

1. A system for distributed packed scheduling, comprising:

physical neighborhood list, wherein the physical neighborhood list is a data structure that is associated with a first node in an ad hoc network and includes a transmit time parameter, wherein the transmit time parameter is related to a time period in which the first node is not eligible to be selected as a transmitting node by a priority function; and

a control packet that is transmitted in response to the transmit time parameter.

2. The system of claim 1, further comprising a compressor arranged to compress the physical neighborhood list.

3. The system of claim 1, wherein the control packet is a network configuration packet.

4. The system of claim 1, wherein the transmit time parameter is a transmit holdoff time.

5. The system of claim 1, wherein the transmit time parameter is a next transmit time.

6. The system of claim 1, wherein the transmit time parameter includes a transmit holdoff time and a next transmit time.

7. The system of claim 1, wherein the physical neighborhood list includes a reported flag associated with the transmit time parameter.

8. The system of claim 1, wherein the ad hoc network further comprises a plurality of other nodes, the first node and the plurality of other nodes are each arranged to perform the priority function, and wherein the priority function is configured to select a transmitting node among the first node and the plurality of other nodes.

9. A method for distributed packed scheduling, comprising:

determining physical network information associated with a first node in an ad hoc network, wherein the physical information includes a node identifier and a transmit time parameter, and wherein the transmit time parameter is related to a time period in which the first node is not eligible to be selected as a transmitting node by priority function;

creating a control packet in accordance with the physical neighborhood information; and

transmitting the control packet in accordance with the transmit time parameter.

10. The method of claim 9, wherein the control packet is a network configuration packet.

11. The method of claim 9, wherein the control packet comprises:

distance parameter;

node identifier;

next transmit time, wherein the next transmit time is related to a time before which the first node will not transmit the control packet; and

transmit holdoff time, wherein the transmit holdoff time is related to a time period in which the control packet is eligible to be transmitted.

12. The method of claim 11, wherein the control packet further comprises a MAC address.

13. The method of claim 9, wherein the control packet is configurable.

14. The method of claim 9, wherein the control packet is adaptive.

15. The method of claim 9, wherein the physical neighborhood information further includes a reported flag responsive to the transmit time parameter.

16. The method of claim 9, wherein the transmit time parameter is a transmit holdoff time.

17. The method of claim 9, wherein the transmit time parameter is a next transmit time.

18. The method of claim 9, wherein the transmit time parameter includes a transmit holdoff time and a next transmit time.

19. The method of claim 9, wherein the ad hoc network further comprises a plurality of other nodes, the first node and the plurality of other nodes are each arranged to perform the priority function, and wherein the priority function is configured to select a transmitting node among the first node and the plurality of other nodes.

20. A method for compressing a plurality of neighbor entries in a neighborhood list contained in a network configuration packet, comprising:

excluding a neighbor entry when

the neighbor entry was reported in a round robin list, wherein the round-robin list comprises neighbor entries that are selected in a round-robin manner from a subset of the plurality of neighbor entries;

operating in a two-hop-scheduling mode and the neighbor entry is a three-hop neighbor entry; and

a reported flag associated with the neighbor entry is set; and

including the neighbor entry in a compressed neighborhood list if it has not been excluded, wherein the reporting flag is set to true upon transmission of the network configuration packet.

21. The method of claim 20, further comprising the step of ordering the compressed neighborhood list in accordance with the transmit time parameters associated with the neighbor.

22. The method of claim 20, wherein a value of the reported flag corresponds to whether a next transmit time has been reported, and wherein the next transmit time is related to a time period in which the network configuration packet is guaranteed not to be transmitted.

23. A method for transmitting a network configuration packet associated with a node in an ad hoc network, comprising:

determining a next transmit time associated with the node;

determining a next holdoff time associated with the node;

selecting a time for transmitting the network configuration packet based upon the next transmit time and the next holdoff time;

evaluating a skip transmit flag, wherein the skip transmit flag is associated with error correction, and if the skip transmit flag is false;

creating a network configuration packet, wherein the network configuration packet comprises a plurality of neighborhood entries;

for each of the plurality of neighborhood entries, setting a reported flag associated with the neighbor entry in accordance with whether the neighbor entry has been reported; and

transmitting the network configuration packet.

24. A method for transmission scheduling in an ad hoc network comprising:

ordering neighbor entries in a physical neighbor list in accordance with next transmit times associated with neighbor entries;

calculating an earliest subsequent transmit time for each neighbor entry;

setting a temporary transmit time associated with a neighbor node equal to a value representing the sum of an advertised transmit holdoff time associated with the neighbor node and a current transmit time associated with the neighbor node;

holding a neighborhood election; and

scheduling a next transmit time based on the neighborhood election.

25. The method of claim 24 wherein calculating the earliest subsequent transmit time further comprises adding the next transmit time associated with the neighbor entry to a transmit holdoff time associated with the neighbor entry.

26. The method of claim 24 wherein holding a neighborhood election comprises holding the neighborhood election among eligible competing nodes such that only eligible competing nodes compete in the election, and wherein the eligible competing nodes consist of neighbor nodes in the physical neighborhood list having an earlier subsequent transmit time equal to or less than the temporary transmit time.

27. The method of claim 26 wherein holding the neighborhood election further comprises:

determining the eligible competing nodes; and

setting the temporary time equal to a next network configuration frame when the eligible completing node does not win the election.

28. The method of claim 27, further comprising:

determining when a first condition is satisfied, wherein the first condition is satisfied when the temporary transmit time associated with the node equals the next transmit time of a node in the physical neighborhood list; and

setting the temporary transmit time equal to a next network configuration frame when the first condition is satisfied.

29. The method of claim 26, further comprising:

transmitting a network configuration packet at the scheduled transmit time, wherein the network configuration packet comprises a list of neighbor entries, each of the neighbor entries is associated with a node, and wherein each of the neighbor entries includes the next transmit time of the associated node and the transmit holdoff time of the associated node.