Assigning Slots in a Mesh Network

• US 20120039218A1
• Filed: 10/31/2011
• Published: 02/16/2012
• Est. Priority Date: 07/31/2008
• Status: Active Grant

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Palchaudhuri, Santashil, Raman, Gopalakrishnan
• Granted Patent: US 8,902,903 B2
• Time in Patent Office: Days
• US Class Current: 370/256
• CPC Class Codes: D21F 3/04 Arrangements thereof
• CPC Class Codes: D21G 9/0036 controlling the press or drying section
• CPC Class Codes: H04L 41/12 Discovery or management of network topologies
• CPC Class Codes: H04W 40/24 Connectivity information management, e.g. connectivity discovery or connectivity update
• CPC Class Codes: H04W 72/0446 Resources in time domain, e.g. slots or frames
• CPC Class Codes: H04W 74/04 Scheduled access hybrid access H04W74/02
• CPC Class Codes: H04W 8/005 Discovery of network devices, e.g. terminals
• CPC Class Codes: H04W 8/26 Network addressing or numbering for mobility support

Abstract

Assigning slots to nodes in a mesh network. Slot numbers are assigned to nodes in a wireless mesh network using a depth-first search combined with information on 2-hop neighborhoods for each node. Assigning slots using 2-hop neighborhood information allows slots to be safely reused. The slot assignment process may take process in parallel using different wireless channels for different subtrees rooted to a controller. Slot assignment may be repeated when the mesh topology changes. Reporting using the slot numbers allows for information from child nodes to be aggregated or filtered at parent nodes.

Claims

1-7. -7. (canceled)

8. A method comprising:

determining, by a network device, neighborhood information of mesh nodes in a tree;

performing, by the network device, a depth-first search of the tree based on the neighborhood information;

ordering, by the network device, the mesh nodes based on results of the depth-first search of the tree; and

assigning, by the network device, slot numbers to the mesh nodes based on the ordering.

9. The method of claim 8, wherein determining neighborhood information comprises creating a list of 2-hop neighbors for each mesh node in the tree.

10. The method of claim 9, wherein assigning slot numbers comprises assigning a slot number to a mesh node which is greater than slot numbers already allocated to any child nodes or any nodes in the mesh node'"'"'s 2-hop neighborhood.

11. The method of claim 10, wherein assigning slot numbers further comprises:

sending a token to an unvisited child node of the mesh node;

waiting for the token to return to the mesh node; and

remembering slot allocation of each child node of the mesh node.

12. The method of claim 11, further comprising:

appending an identifier and the slot number corresponding to the mesh node to the token; and

sending the token to a parent node of the mesh node.

13. The method of claim 8, further comprising:

requesting mesh nodes to report status in slot number sequence.

14. The method of claim 13, wherein a parent node aggregates status information reported by its child nodes.

15. The method of claim 13, wherein a parent node filters status information reported by its child nodes.

16. A network device comprising:

a processor;

a memory;

a determining mechanism coupled to the processor, the determining mechanism to determine neighborhood information of mesh nodes in a tree;

a searching mechanism coupled to the processor, the searching mechanism to perform a depth-first search of the tree based on the neighborhood information;

an ordering mechanism coupled to the processor, the ordering mechanism to order the mesh nodes based on results of the depth-first search of the tree; and

an assigning mechanism coupled to the processor, the assigning mechanism to assign slot numbers to the mesh nodes based on the ordering.

17. The network device of claim 16, wherein the determining mechanism further creates a list of 2-hop neighbors for each mesh node in the tree.

18. The network device of claim 17, wherein the assigning mechanism assigns a slot number to a mesh node which is greater than slot numbers already allocated to any child nodes or any nodes in the mesh node'"'"'s 2-hop neighborhood.

19. The network device of claim 18, wherein the assigning mechanism further to:

send a token to an unvisited child node of the mesh node;

wait for the token to return to the mesh node; and

remember slot allocation of each child node of the mesh node.

20. The network device of claim 19, wherein the assigning mechanism further to:

append an identifier and the slot number corresponding to the mesh node to the token; and

send the token to a parent node of the mesh node.

21. The network device of claim 16, further comprising:

a requesting mechanism coupled to a processor, the requesting mechanism to request mesh nodes to report status in slot number sequence.

22. The network device of claim 21, wherein a parent node aggregates status information reported by its child nodes.

23. The network device of claim 21, wherein a parent node filters status information reported by its child nodes.

24. A non-transitory computer-readable storage medium storing embedded instructions that are executed by one or more mechanisms implemented within a network device to perform a plurality of operations comprising:

determining neighborhood information of mesh nodes in a tree;

performing a depth-first search of the tree based on the neighborhood information;

ordering the mesh nodes based on results of the depth-first search of the tree; and

assigning slot numbers to the mesh nodes based on the ordering.

25. The non-transitory computer-readable storage medium of claim 24, wherein determining the neighborhood information comprises creating a list of 2-hop neighbors for each mesh node in the tree.

26. The non-transitory computer-readable storage medium of claim 24, wherein assigning slot numbers comprises assigning a slot number to a mesh node which is greater than slot numbers already allocated to any child nodes or any nodes in the mesh node'"'"'s 2-hop neighborhood.

27. The non-transitory computer-readable storage medium of claim 25, wherein assigning slot numbers further comprises:

sending a token to an unvisited child node of the mesh node;

waiting for the token to return to the mesh node; and

remembering slot allocation of each child node of the mesh node.

28. The non-transitory computer-readable storage medium of claim 24, further comprising:

appending an identifier and the slot number corresponding to the mesh node to the token; and

sending the token to a parent node of the mesh node.