Multi-channel assignment method for multi-radio multi-hop wireless mesh networks

• US 8,824,380 B2
• Filed: 03/13/2009
• Issued: 09/02/2014
• Est. Priority Date: 09/19/2006
• Status: Active Grant

• Current Assignee: FireTide Incorporated (UNICOM Global, Inc.)
• Original Assignee: FireTide Incorporated (UNICOM Global, Inc.)
• Inventors: Jetcheva, Jorjeta Gueorguieva, Kailas, Sivakumar, Kanodia, Sachin, Natarajan, Mohan
• Primary Examiner(s): ANWAR, MOHAMMAD S
• Application Number:
  US12/404,166
• Publication Number:
  US 20090175238A1
• Time in Patent Office: 1,999 Days
• Field of Search: 370/328, 370/329, 370/338
• US Class Current: 370/329
• CPC Class Codes: H04W 28/082 among bearers or channels
• CPC Class Codes: H04W 72/0453 Resources in frequency domain, e.g. a carrier in FDMA
• CPC Class Codes: H04W 72/52 based on load
• CPC Class Codes: H04W 72/541 using the level of interference
• CPC Class Codes: H04W 72/542 using measured or perceived quality
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks

Abstract

Techniques are described for automatically determining quasi-static per-link channel assignments for each radio in multiple-hop mesh networks having nodes with two or more radios and where only a small number of channels is available for use in the network. The method optimally assigns the channels to the radios of all of the nodes in the network so as to achieve the lowest interference among links and the highest possible bandwidth.

Claims

1. A method of determining channel assignments for each radio in a multi-radio multiple-hop mesh network, the network being comprised of nodes and radio-to-radio links between the nodes, the method comprising:

determining the topology of the network at least in part via a depth-first search traversal;

reducing the network topology;

balancing the network topology by selectively choosing where each node should be attached to the network topology so as to distribute potential traffic load more evenly across the network at least in part via computing respective weights of each node as a number of nodes that are children of the respective node; and

selecting, in accordance with the reducing and the balancing, a channel for each radio.

2. The method of claim 1, further including:

measuring predetermined attributes of the network; and

wherein the reducing includes selecting the best path from each node to the root based at least in part on the network measurements.

3. The method of claim 1, further including:

measuring performance of each link;

calculating the expected load on each link; and

wherein the balancing is based at least in part on the measured performance of each link and the expected load on each link.

4. The method of claim 3, wherein the load calculation is based at least in part on the number of dependent nodes per node.

5. The method of claim 1, wherein the selecting tries to pick channels that minimize the interference in the network.

6. The method of claim 1, wherein the selecting tries to provide a non-degrading path to each node.

7. The method of claim 1, wherein the selecting is based at least in part on virtual links and physical links in the topology.

8. The method of claim 1, further including:

recording by each node the potentially reachable neighbors that may be on other channels.

9. The method of claim 8, further including:

when a node is disconnected from the network, reconnecting the node to the network by switching to the channel of one of the previously recorded neighbors.

10. The method of claim 9, wherein the switching is immediate.

11. The method of claim 8, further including:

when a node is disconnected from the network, reconnecting the node to the network by switching to the channel of the previously recorded neighbor that provides the best connectivity to the wired portal.

12. The method of claim 1, wherein the network uses omni-directional antennas.

13. The method of claim 1, wherein the network uses directional antennas.

14. The method of claim 1, wherein the selecting attempts to create a non-interfering assignment along a best path from each node towards a wired mesh portal.

15. The method of claim 1, wherein the selecting attempts to create a non-interfering assignment along a best path from each node towards a virtual portal, the virtual portal conceptually representing multiple wired mesh portals.

16. A non-transitory computer readable medium having a set of instructions stored therein which when executed by a processing device causes the processing device to perform procedures comprising:

determining the topology of a multi-radio multiple-hop mesh network at least in part via a depth-first search traversal, the network being comprised of nodes and radio-to-radio links between the nodes;

reducing the network topology;

balancing the network topology by selectively choosing where each node should be attached to the network topology so as to distribute potential traffic load more evenly across the network at least in part via computing respective weights of each node as a number of nodes that are children of the respective node; and

selecting, in accordance with the reducing and the balancing, a channel assignment for each radio.

17. The non-transitory computer readable medium of claim 16, wherein the determining, reducing, balancing, and selecting are carried out in a centralized manner by a multi-channel controller.

18. The non-transitory computer readable medium of claim 17, the procedures further comprising the multi-channel controller distributing the channel assignments.

19. The non-transitory computer readable medium of claim 17, the procedures further comprising the multi-channel controller distributing node-specific information to each node, the node-specific information comprising a list of neighbors and channels.

20. The non-transitory computer readable medium of claim 17, the procedures further comprising the multi-channel controller receiving notifications from the nodes regarding parent changes.

21. The non-transitory computer readable medium of claim 16, wherein the determining, reducing, balancing, and selecting are carried out in a distributed manner by at least some of the nodes.

22. The non-transitory computer readable medium of claim 16, wherein the selecting attempts to create a non-interfering assignment along a best path from each node towards a wired mesh portal.

23. The non-transitory computer readable medium of claim 16, wherein the selecting attempts to create a non-interfering assignment along a best path from each node towards a virtual portal, the virtual portal conceptually representing multiple wired mesh portals.