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

• US 20030067892A1
• Filed: 08/26/2002
• Published: 04/10/2003
• Est. Priority Date: 08/25/2001
• Status: Active Grant

• Current Assignee: Nokia Corporation
• Original Assignee: Nokia Corporation
• Inventors: Beyer, David, Garcia-Luna-Aceves, Jose J.
• Granted Patent: US 6,791,997 B2
• Time in Patent Office: Days
• US Class Current: 370/328
• 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 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 may be a hash function, an encryption function, or a table-lookup function. The computation of candidate transmission times uses the identifiers of those nodes for which no advertised transmission time has been obtained.

Claims

1. A system for distributed packet scheduling, comprising:

a physical neighborhood list, wherein the physical neighborhood list is a data structure that is associated with a node in an ad hoc network and includes a transmit time parameter; 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. A method for distributed packet scheduling, comprising:

determining physical neighborhood information associated with a node in an ad hoc network, wherein the physical neighborhood information includes a node identifier and a transmit time parameter;

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

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

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

10. The method of claim 8, wherein the control packet comprises:

a distance parameter;

a node identifier;

a next transmit time; and

a transmit holdoff time.

11. The method of claim 8, wherein the control packet is configurable.

12. The method of claim 8, wherein the control packet is adaptive.

13. The method of claim 10, wherein the control packet further comprises a MAC address.

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

15. The method of claim 8, wherein the transmit time parameter is a transmit holdoff time.

16. The method of claim 8, wherein the transmit time parameter is a next transmit time.

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

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

when operating in a two-hop-scheduling mode, if 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.

19. The method of claim 18, wherein the reported flag is set to true upon transmission of the network configuration packet.

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

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

evaluating a skip transmit flag, and if the skip transmit flag is set;

creating a network configuration packet;

setting a reported flag associated with a neighbor entry in accordance with whether the neighbor entry has been reported; and

transmitting the network configuration flag.

22. 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 addition of an advertised transmit holdoff time associated with the neighbor node to a current transmit time associated with the neighbor node;

holding a neighborhood election; and

scheduling a next transmit time based on the neighborhood election.

23. The method of claim 22 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.

24. The method of claim 22, wherein the eligible competing nodes includes neighbor nodes in the physical neighbor list having an earlier subsequent transmit time equal to or less than the temporary transmit time.

25. The method of claim 24, wherein holding the neighborhood election further comprises:

determining eligible competing nodes; and

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

26. The method of claim 25, further comprising determining when the temporary transmit time associated with the node equals the next transmit time of a node in the physical neighbor list, and when;

setting the temporary transmit time equal to a next network configuration frame.