Slot-based transmission synchronization mechanism in wireless mesh networks

• US 8,599,822 B2
• Filed: 08/26/2005
• Issued: 12/03/2013
• Est. Priority Date: 03/23/2005
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Castagnoli, Neal Dante
• Primary Examiner(s): AJIBADE AKONAI, OLUMIDE
• Application Number:
  US11/213,292
• Publication Number:
  US 20060215583A1
• Time in Patent Office: 3,021 Days
• Field of Search: 370/229, 370/230, 370/230.1, 370/231, 370/232, 370/233, 370/234, 370/235, 370/238, 370/238.1, 370/254, 370/329, 370/392, 370/395.31, 370/395.32, 370/395.4, 370/395.41, 370/395.42, 370/395.43, 370/406, 370/400, 370/442, 370/458, 370/459, 370/503, 370/508, 370/337, 370/351, 370/431, 370/252, 370/328, 370/330, 370/336, 370/338, 370/346, 370/347, 370/348, 370/443, 370/447, 370/448, 370/449, 370/350, 370/352, 370/355, 370/356, 455450-4522, 709/203, 709/230, 709238-242
• US Class Current: 370/350
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/04 Interdomain routing, e.g. hierarchical routing
• CPC Class Codes: H04L 45/48 Routing tree calculation
• CPC Class Codes: H04L 45/488 using root node determination
• CPC Class Codes: H04L 45/60 Router architectures
• CPC Class Codes: H04W 24/02 Arrangements for optimising operational condition
• CPC Class Codes: H04W 40/24 Connectivity information management, e.g. connectivity discovery or connectivity update
• CPC Class Codes: H04W 48/16 Discovering, processing access restriction or access information
• CPC Class Codes: H04W 74/002 Transmission of channel access control information
• 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

Methods, apparatuses and systems directed to synchronizing transmissions among parent and child routing nodes in a hierarchical wireless mesh network. In one implementation, the present invention employs a time slot scheduling algorithm to coordinate communications between wireless nodes of a hierarchical tree. In one implementation, the present invention provides a wireless mesh network where slot scheduling information propagates throughout the mesh, while individual nodes in the mesh compute their respective time slot schedules based on this information and the current state of the network. In one such implementation, a parent routing node computes its slot schedule and transmits certain parameters to its child nodes (as opposed to the schedule itself). The child node(s) then iterates the same scheduling function based on the parameters passed to it to determine the slots with which it should communicate to its parent node and its child nodes.

Claims

1. In a routing node for use in a hierarchical mesh network, wherein the routing node is operative to implement a data slot transmission schedule controlling transmission of data between a parent routing node and at least one child routing node, a method for scheduling data transfer, the method comprising

receiving, at the routing node, slot scheduling information from a parent routing node, wherein the slot scheduling information indicates one or more time slots during which the parent routing node has scheduled communications with the routing node;

and

computing, for the routing node, a data slot transmission schedule that indicates time slots for transmission of data between the parent routing node and at least one child routing node based on the slot scheduling information received from the parent routing node and the number of child routing nodes associated with the routing node, such that the number of child routing nodes associated with the routing node scheduled in any cycle of the data slot transmission schedule is relatively prime to the number of child nodes associated with the parent routing node scheduled in the same cycle of the data slot transmission schedule.

2. The method of claim 1 further comprising

deriving slot scheduling information from the computed data slot transmission schedule;

and

transmitting the derived slot scheduling information to the at least one child routing node.

3. The method of claim 1 wherein the slot scheduling information received from the parent routing node comprises a slot identifier and an effective number of child nodes associated with the parent routing node.

4. The method of claim 3 wherein the slot scheduling information further comprises the actual number of child nodes associated with the parent routing node.

5. The method of claim 2 wherein the slot scheduling information received from the parent routing node comprises a slot identifier and an effective number of child nodes associated with the parent routing node;

wherein the method further comprises

computing an effective number of child nodes based on the actual number of child nodes associated with the routing node, the slot identifier received from the parent routing node, and the effective number of child nodes associated with the parent routing node; and

wherein the data slot transmission schedule is based in part on the effective number of child nodes computed by the routing node.

6. The method of claim 1 wherein the slot scheduling information further comprises a time stamp;

and wherein the method further comprising

synchronizing implementation of the data slot transmission schedule based at least in part on the time stamp.

7. The method of claim 1 further comprising deriving slot numbers for the time slots of the slot scheduling information based on a circular address space, the circular address space being bound by a number that allows all slot cycles to repeat.

8. The method of claim 1, wherein the data slot transmission schedule ensures that none of the at least one child routing node is continually ignored by the routing node.

9. The method of claim 1, wherein the data slot transmission schedule ensures that there is no loop between the parent routing node and any one of the at least one child routing node.

10. A routing node for use in a hierarchical wireless mesh network, comprising

a network interface;

one or more processors;

a memory;

a routing node application, stored in the memory, comprising instructions operable to cause the one or more processors and the apparatus to

receive slot scheduling information from a parent routing node, wherein the slot scheduling information indicates one or more time slots during which the parent routing node has scheduled communications with the routing node; and

compute a data slot transmission schedule that indicates time slots for transmission of data between the parent routing node and at least one child routing node based on the slot scheduling information received from the parent routing node and the number of child routing nodes associated with the routing node, such that the number of child routing nodes associated with the routing node scheduled in any cycle of the data slot transmission schedule is relatively prime to the number of child nodes associated with the parent routing node scheduled in the same cycle of the data slot transmission schedule.

11. The routing node of claim 10 wherein the routing node application further comprises instructions operable to cause the one or more processors and the apparatus to

derive slot scheduling information from the computed data slot transmission schedule;

and

transmit the derived slot scheduling information to the at least one child routing node.

12. The routing node of claim 10 wherein the slot scheduling information received from the parent routing node comprises a slot identifier and an effective number of child nodes associated with the parent routing node.

13. The routing node of claim 12 wherein the slot scheduling information further comprises the actual number of child nodes associated with the parent routing node.

14. The routing node of claim 11 wherein the slot scheduling information received from the parent routing node comprises a slot identifier and an effective number of child nodes associated with the parent routing node;

and wherein the routing node application further comprises instructions operable to cause the one or more processors and the apparatus to

compute an effective number of child nodes based on the actual number of child nodes associated with the routing node, the slot identifier received from the parent routing node, and the effective number of child nodes associated with the parent routing node; and

wherein the data slot transmission schedule is based in part on the effective number of child nodes computed by the routing node.

15. The routing node of claim 10 wherein the slot scheduling information further comprises a time stamp;

and wherein the routing node application further comprises instructions operable to cause the one or more processors and the apparatus to

synchronize implementation of the data slot transmission schedule based at least in part on the time stamp.

16. The routing node of claim 10 wherein the routing node application further comprises instructions operable to cause the one or more processors and the apparatus to derive slot numbers for the time slots of the slot scheduling information based on a circular address space, the circular address space being bound by a number that allows all slot cycles to repeat.

17. A wireless routing node for use in a hierarchical wireless mesh network, comprising

means for wirelessly communicating with a parent routing node and at least one child routing node, and for receiving slot scheduling information from the parent routing node, wherein the slot scheduling information indicates one or more time slots during which the parent routing node has scheduled communications with the routing node;

and

means for computing a data slot transmission schedule that indicates time slots for transmission of data between the parent routing node and the at least one child routing node based on the slot scheduling information received from the parent routing node and the number of child routing nodes associated with the routing node, such that the number of child routing nodes associated with the routing node scheduled in any cycle of the data slot transmission schedule is relatively prime to the number of child nodes associated with the parent routing node scheduled in the same cycle of the data slot transmission schedule.

18. The wireless routing node of claim 17 further comprising

means for deriving slot scheduling information from the computed data slot transmission schedule;

and

means for transmitting the derived slot scheduling information to the at least one child routing node.

19. The wireless routing node of claim 17 wherein the slot scheduling information received from the parent routing node comprises a slot identifier and an effective number of child nodes associated with the parent routing node.

20. The wireless routing node of claim 19 wherein the slot scheduling information further comprises the actual number of child nodes associated with the parent routing node.

21. The wireless routing node of claim 18 wherein the slot scheduling information received from the parent routing node comprises a slot identifier and an effective number of child nodes associated with the parent routing node;

wherein the wireless routing node further comprises

means for computing an effective number of child nodes based on the actual number of child nodes associated with the routing node, the slot identifier received from the parent routing node, and the effective number of child nodes associated with the parent routing node; and

wherein the data slot transmission schedule is based in part on the effective number of child nodes computed by the routing node.

22. The wireless routing node of claim 17 wherein the slot scheduling information further comprises a time stamp;

and wherein the wireless routing node further comprises

means for synchronizing implementation of the data slot transmission schedule based at least in part on the time stamp.

23. The wireless routing node of claim 17 further comprising deriving slot numbers for the time slots of the slot scheduling information based on a circular address space, the circular address space being bound by a number that allows all slot cycles to repeat.