초록 ▼

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 hierar

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.

대표청구항 ▼

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 comp

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; andcomputing, 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; andtransmitting 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; andcompute 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; andtransmit 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; andmeans 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; andmeans 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.