Adaptive communication protocol for wireless networks

• US 7,184,413 B2
• Filed: 02/10/1999
• Issued: 02/27/2007
• Est. Priority Date: 02/10/1999
• Status: Expired due to Term

• Current Assignee: Nokia Technologies Oy (Nokia Corporation)
• Original Assignee: Nokia, Inc. (Nokia Corporation)
• Inventors: Beyer, David A., Fullmer, Chane L., Garcia-Luna-Aceves, J. Joaquin
• Primary Examiner(s): Harper; Kevin C.
• Application Number:
  US09/248,738
• Publication Number:
  US 20060104301A1
• Time in Patent Office: 2,939 Days
• Field of Search: 370254-255, 370/257, 370/310, 370336-337, 370/345, 370347-348, 370/431, 370/437, 370442-445, 370/447, 370/450, 370458-459, 370464-465, 370/468, 370/478, 370/498, 370/503, 370/913, 370/338, 370/350, 370/462, 455/450, 709/248, 368/47
• US Class Current: 370/254
• CPC Class Codes: H04J 3/0667 Bidirectional timestamps, e.g. NTP or PTP for compensation of clock drift and for compensation of propagation delays arrangements for monitoring round trip delays in packet switching networks H04L43/0864
• CPC Class Codes: H04W 72/20 Control channels or signalling for resource management
• CPC Class Codes: H04W 72/566 of the information or information source or recipient
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks

Abstract

A communication protocol that provides link-level and media access control (MAC) level functions for wireless (e.g., ad-hoc) networks and is robust to mobility or other dynamics, and for scaling to dense networks. In a mobile or otherwise dynamic network, any control-packet collisions will be only temporary and fair. In a dense network, the network performance degrades gracefully, ensuring that only a certain percentage of the common channel is consumed with control packets. The integrated protocol allows packets (e.g., data scheduling control packets) to be scheduled in a collision-free and predictable manner (known to all neighbors), multicast packets can be reliably scheduled, as well as streams of delay- or delay-jitter-sensitive traffic. Further, using an optional network code, the scheduling of control packets can appear to observers to be randomized.

Claims

1. A method, comprising activating a node of a computer network such that the node first attempts to establish contact with other nodes that may exist within the computer network by cycling through a set of common channels for communication within the computer network, the node at each channel attempting to establish contact by transmitting a request packet including a code identifying the network thereon and, after transmitting a request packet on one of the common channels, the node listens for a response packet before proceeding to a next one of the common channels, wherein upon receiving a response packet including the code identifying the network first transmitted by the request packet from one of the other nodes, the node enters a synchronization mode and joins the computer network and, if unsuccessful in establishing contact with other nodes, then the node establishes itself as a single node network,

wherein the response packet includes a parameter specifying time with the computer network.

2. A method, comprising activating a node of a computer network such that the node first attempts to establish contact with other nodes that may exist within the computer network by cycling through a set of common channels for communication within the computer network, the node at each channel attempting to establish contact by transmitting a request packet including a code identifying the network thereon and, after transmitting a request packet on one of the common channels, the node listens for a response packet before proceeding to a next one of the common channels, wherein upon receiving a response packet including the code identifying the network first transmitted by the request packet from one of the other nodes, the node enters a synchronization mode and joins the computer network and, if unsuccessful in establishing contact with other nodes, then the node establishes itself as a single node network;

wherein while the node is established as a single node network, the node listens for attempts by further nodes to join a network;

upon detecting one or more attempts by the further nodes to join a network, the node transmits a response thereto; and

the response includes an indication of time within the single node network.

3. The method of claim 2 wherein the response further includes a network code.

4. A method comprising:

receiving, at first node of a computer network, a packet from a second node of the computer network;

using information contained in the packet from the second node in determining whether or not to adjust a time at the first node according to whether a priority of the second node is lesser or greater than a priority of the first node;

adjusting the time at the first node only if the priority of the second node is greater than the priority of the first node; and

not adjusting the time at the first node if the priority of the second node is less than or equal to the priority of the first node, wherein the information contained in the packet from the second node includes an indication of time within the computer network according to the second node, wherein if both the first and second nodes are not locked, then the priority of the second node is greater than the priority of the first node if the indication of time of the second node is greater than the time at the first node.

5. The method of claim 4 wherein the first node first transmits a Transition Request packet before adjusting the time at the first node.

6. The method of claim 5 wherein nodes synchronized with the first node receive the Transition Request packet from the first node and adjust corresponding local times according to a time specified in the Transition Request packet.

7. The method of claim 4, wherein the indication of time is adjusted for delays within the computer network.

8. A method, comprising computing a transmission time for a packet from a first node of a computer network according to the identification of the node and an indication of the network age up to the start of a current frame within which the packet is to be transmitted and, wherein the computing is performed using a function that provides a varying distribution of results for varying inputs of the identification of the first node and the age of the network, the results ranging from a minimum to a maximum representing a number of transmission slots per frame within which a control packet may be transmitted.

9. The method of claim 8 wherein the packet comprises a network control packet.

10. The method of claim 9 wherein the control packet advertises a schedule for a data transmission.

11. The method of claim 10 wherein the schedule includes an identification of one or more nodes to receive the data transmission.

12. The method of claim 11 wherein the schedule further includes a data transmission time.

13. The method of claim 12 wherein the schedule further includes a data transmission channel.

14. The method of claim 8 wherein the function comprises an encryption function.

15. The method of claim 8 wherein the function comprises a hash function.

16. The method of claim 15 wherein the hash function comprises the MD5 hash function.

29. The method of claim 8 wherein the first node transmits at the transmission time if it further has priority exceeding a priority threshold.

17. A method, comprising computing a transmission time for a packet from a first node of a computer network according to the identification of the node and an indication of the network age up to the start of a current frame within which the packet is to be transmitted, wherein the computing is performed using a table of entries of pseudorandom values.

18. The method of claim 17 wherein the pseudorandom values represent transmission slots within the frame within which a control packet may be transmitted.

19. The method of claim 17 further comprising computing, at the first node, transmission times for other nodes of the computer network.

20. The method of claim 19 wherein computing transmission times for the other nodes is performed using unique identifiers for each of the other nodes and the network age.

21. The method of claim 20 wherein computing transmission times for the other nodes is accomplished using a function that is also used for computing the transmission time for the first node.

22. The method of claim 21 wherein the other nodes are all within a two-hop neighborhood of the first node in the computer network.

23. The method of claim 22 wherein the first node resolves contentions for transmission times between itself and any of the other nodes according to a priority determination.

24. A method, comprising computing a transmission time for a packet from a first node of a computer network according to the identification of the node and an indication of the network age up to the start of a current frame within which the packet is to be transmitted, further comprising computing, at the first node, transmission times for other nodes that are within a two-hop neighborhood of the first node in the computer network using unique identifiers for each of the other nodes and the network age, wherein computing transmission times for the other nodes is accomplished using a function that is also used for computing the transmission time for the first node, wherein the first node resolves contentions for transmission times between itself and any of the other nodes according to a priority determination which uses a function that provides a unique output for various identification and network age inputs.

25. The method of claim 24 wherein the function comprises an encryption algorithm.

26. The method of claim 24 wherein the function comprises a table look-up.

27. The method of claim 24 wherein the priority determination is further made using a priority bias associated with each of the nodes.

28. The method of claim 27 wherein the first node transmits at the transmission time if it is determined to have priority over the other nodes.

30. The method of claim 24 wherein the first node transmits at the transmission time if it is determined to have priority over the other nodes.

31. The method of claim 30 wherein the first node transmits at the transmission time if it further has priority exceeding a priority threshold.

32. A method, comprising computing a transmission time for a packet from a first node of a computer network according to the identification of the node and an indication of the network age up to the start of a current frame within which the packet is to be transmitted, wherein the packet comprises a network control packet which advertises a schedule for a data transmission, and the schedule includes a persistence indicator.

33. A method, comprising computing a transmission time for a packet from a first node of a computer network according to the identification of the node and an indication of the network age up to the start of a current frame within which the packet is to be transmitted, wherein the packet comprises a network control packet which advertises a schedule for a data transmission and the schedule includes an identification of one or more nodes to receive the data transmission, wherein the nodes to receive the data transmission are identified by local identifiers being smaller than network identifiers associated with the nodes.

34. The method of claim 33 wherein the first node transmits a mapping of the local identifiers to the network identifiers within the network.

35. A method, comprising computing a transmission time for a packet from a first node of a computer network according to the identification of the node and an indication of the network age up to the start of a current frame with which the packet is to be transmitted, further comprising computing, at the first node, transmission times for other nodes that are within a two-hop neighborhood of the first node in the computer network using unique identifiers for each of the other nodes and the network age, wherein computing transmission times for the other nodes is accomplished using a function that is also used for computing the transmission time for the first node, wherein the first node resolves contention for transmission times between itself and any of the other nodes according to a priority determination and the priority determination is made using a table of pseudorandom values.

36. The method of claim 35 wherein the table of pseudorandom values is indexed by a value derived from a media access control layer address of the first node to retrieve an entry corresponding to a first priority determination.

37. The method of claim 36 wherein the first priority determination is checked by logically combining the media access control layer address of the first node with the entry corresponding to the first priority determination to resolve conflicts.

38. A method, comprising using a topology-independent scheduling procedure utilizing an age of the network and unique identifiers for each node of the network to determine the candidate packet transmission times within a computer network for each of the nodes therein and a topology-dependent scheduling procedure to avoid collisions in contended time periods, wherein the topology-independent scheduling procedure computes the candidate transmission times for each of the nodes using a function that provides various distribution of outputs for various sampling of inputs.

39. The method of claim 38 wherein the function comprises at least one of a hash function, an encryption function or a table look-up operation.

40. The method of claim 38 wherein conflicts for the candidate transmission times for each of the nodes are resolved according to a priority associated with each of the nodes.

41. The method of claim 40 wherein the priority for each of the nodes is determined according to a function that provides a unique output for each set of inputs.

42. The method of claim 41 wherein the function that provides a unique output for each set of inputs comprises at least one of an encryption function, a hash function or a table look-up operation.

43. The method of claim 41 wherein the inputs to the function that provides a unique output for each set of inputs comprise one or more of a unique identifier associated with each node, a scheduling frame number for the network, and a priority bias for each node.

44. A network comprising:

a node,

wherein the node first attempts to establish contact with other nodes that may exist within the network by cycling through a set of common channels for communication within the network, the node at each channel attempting to establish contact by transmitting a request packet including a code identifying the network thereon and, after transmitting a request packet on one of the common channels, the node listens for a response packet before proceeding to a next one of the common channels, wherein upon receiving a response packet including the code identifying the network first transmitted by the request packet from one of the other nodes, the node enters a synchronization mode and joins the computer network and, if unsuccessful in establishing contact with the other nodes, then the node establishes itself as a single node network, and

wherein the response packet includes a parameter specifying time with the computer network.

45. The network of claim 44, wherein upon detecting one or more attempts by the other nodes to join a network, the node transmits a response thereto.

46. The network of claim 44, wherein the response includes an indication of time within the single node network.

47. The network of claim 46, wherein the response further includes a network code.

48. The network of claim 44, wherein while the node is established as a single node network, the node listens for attempts by further nodes to join a network.

49. A network comprising:

a node,

wherein a transmission time for a packet from the node is computed according to the identification of the node and an indication of the network age up to the start of a current frame within which the packet is to be transmitted and, wherein the computing is performed using a function that provides a varying distribution of results for varying inputs of the identification of the node and the age of the network, the results ranging from a minimum to a maximum representing a number of transmission slots per frame within which a control packet may be transmitted.

50. The network of claim 49, wherein the packet comprises a network control packet.

51. The network of claim 49, wherein the function comprises an encryption function.

52. The network of claim 49, wherein the function comprises a hash function.

53. The network of claim 52, wherein the hash function comprises the MD5 hash function.

54. A network comprising:

a first node,

wherein a transmission time for a packet from the first node is computed according to the identification of the node and an indication of the network age up to the start of a current frame within which the packet is to be transmitted, wherein the computing is performed using a table of entries of pseudorandom values.

55. The network of claim 54, wherein the pseudorandom values represent transmission slots within the frame within which a control packet may be transmitted.

56. The network of claim 54, wherein the first node computes transmission times for other nodes of the computer network.

57. The network of claim 56, wherein the first node computes transmission times for the other nodes using unique identifiers for each of the other nodes and the network age.

58. The network of claim 57, wherein the other nodes are all within a two-hop neighborhood of the first node in the computer network.

59. The network of claim 58, wherein the first node resolves contentions for transmission times between itself and any of the other nodes according to a priority determination.

60. A network comprising:

a first node; and

other nodes,

wherein a transmission time for a packet from the first node is computed according to the identification of the node and an indication of the network age up to the start of a current frame within which the packet is to be transmitted,

wherein transmission times are computed, at the first node, for the other nodes that are within a two-hop neighborhood of the first node using unique identifiers for each of the other nodes and the network age,

wherein computing transmission times for the other nodes is accomplished using a function that is also used for computing the transmission time for the first node, and

wherein the first node resolves contentions for transmission times between itself and any of the other nodes according to a priority determination which uses a function that provides a unique output for various identification and network age inputs.

61. The network of claim 60, wherein the function comprises an encryption algorithm.

62. The network of claim 60, wherein the function comprises a table look- up.

63. The network of claim 60, wherein the priority determination is further made using a priority bias associated with each of the nodes.

64. The network of claim 63, wherein the first node transmits at the transmission time if it is determined to have priority over the other nodes.

65. The network of claim 64, wherein the first node transmits at the transmission time if it further has priority exceeding a priority threshold.

66. The network of claim 60, wherein the first node transmits at the transmission time if it is determined to have priority over the other nodes.

67. The network of claim 66, wherein the first node transmits at the transmission time if it further has priority exceeding a priority threshold.

68. A network comprising:

receiving means for receiving, at first node of the network, a packet from a second node of the network;

determining means for determining, using information contained in the packet from the second node, whether to adjust a time at the first node according to whether a priority of the second node is lesser or greater than a priority of the first node; and

adjusting means for adjusting the time at the first node only if the priority of the second node is greater than the priority of the first node,

wherein the information contained in the packet from the second node includes an indication of time within the computer network according to the second node, and

wherein, if both the first and second nodes are not locked, then the priority of the second node is greater than the priority of the first node if the indication of time of the second node is greater than the time at the first node.