Slot-Based Transmission Synchronization Mechanism in Wireless Mesh Networks

• US 20140036724A1
• Filed: 10/04/2013
• Published: 02/06/2014
• Est. Priority Date: 03/23/2005
• Status: Active Grant

• Current Assignee: Neal Dante Castagnoli
• Original Assignee: Neal Dante Castagnoli
• Inventors: Castagnoli, Neal Dante
• Granted Patent: US 9,338,727 B2
• Time in Patent Office: Days
• US Class Current: 370/254
• 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-21. -21. (canceled)

22. 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.

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

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

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

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

27. The method of claim 26, wherein the effective number of child nodes computed by the routing node is relatively prime as to the effective number of child nodes of the parent routing node.

28. The method of claim 22, wherein the slot scheduling information further comprises a time stamp;

and wherein the method further comprises;

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

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

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

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

32. 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.

33. The routing node of claim 32, 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.

34. The routing node of claim 32, 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.

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

36. The routing node of claim 33, 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.

37. The routing node of claim 36, wherein the effective number of child nodes computed by the routing node is relatively prime as to the effective number of child nodes of the parent routing node.

38. The routing node of claim 32, 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.

39. The routing node of claim 32 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.

40. 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.

41. The wireless routing node of claim 40, 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.

42. The wireless routing node of claim 40, 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.

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

44. The wireless routing node of claim 41, 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.

45. The wireless routing node of claim 44, wherein the effective number of child nodes computed by the routing node is relatively prime as to the effective number of child nodes of the parent routing node.

46. The wireless routing node of claim 40, 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.

47. The wireless routing node of claim 40, 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.