Channel selection for mesh networks having nodes with multiple radios

• US 7,539,151 B2
• Filed: 06/30/2005
• Issued: 05/26/2009
• Est. Priority Date: 06/30/2005
• Status: Expired due to Fees

• Current Assignee: Sky Royal Trading Limited (Guangdong Oujia Holding Co., Ltd.)
• Original Assignee: Intel Corporation
• Inventors: Hazra, Mousumi, Conner, W. Steven, Demirhan, Mustafa
• Primary Examiner(s): Pezzlo; John
• Application Number:
  US11/171,577
• Publication Number:
  US 20070002794A1
• Time in Patent Office: 1,426 Days
• Field of Search: 370/278, 370/252, 370/328, 370/329, 370/400, 370/401, 370/238, 370/419, 370/254, 709238-242
• US Class Current: 370/254
• CPC Class Codes: H04L 43/0888 Throughput
• CPC Class Codes: H04W 40/02 Communication route or path selection, e.g. power-based or shortest path routing
• CPC Class Codes: H04W 40/24 Connectivity information management, e.g. connectivity discovery or connectivity update
• CPC Class Codes: H04W 72/56 based on priority criteria
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks

Abstract

Channels are selected for nodes in a wireless mesh network in a mananer that enhances connectivity and throughput in the network. For a node in the network, channel configurations are first identified that satisfy a predetermined connectivity constraint with respect to neighbor nodes of the node. A channel configuration is then selected from the identified configurations based on an achievable throughput of the configuration.

Claims

1. A method for use in allocating channels in a wireless mesh network having multiple nodes, comprising:

identifying, for an uninitialized node in the wireless mesh network, neighbor nodes that have been initialized, said neighbor nodes being capable of supporting a direct wireless link with said uninitialized node, wherein an initialized node is a node that already has assigned channels;

generating a list of channel configurations for said uninitialized node that satisfy a predetermined connectivity constraint with respect to said identified neighbor nodes;

calculating throughput metrics for channel configurations on said list; and

selecting a channel configuration for said uninitialized node based on said throughput metrics.

2. The method of claim 1, further comprising:

changing a status of said uninitialized node to initialized after selecting a channel configuration.

3. The method of claim 2, further comprising:

repeating identifying, generating, calculating, selecting, and changing for another uninitialized node in the wireless mesh network.

4. The method of claim 2, further comprising:

acquiring a list of nodes in the wireless mesh network and changing a status of all nodes on said list of nodes to uninitialized before identifying neighbor nodes, wherein said uninitialized node is a first node on said list of nodes.

5. The method of claim 4, further comprising:

repeating identifying, generating, calculating, selecting, and changing for all nodes on said list of nodes, other than said first node, after changing said status of said first node.

6. The method of claim 4, wherein:

said list of nodes is organized based on proximity between the listed nodes.

7. The method of claim 1, wherein:

said predetermined connectivity constraint requires at least one common channel with each of said identified neighbor nodes.

8. The method of claim 1, wherein:

calculating throughput metrics for channel configurations on said list includes calculating a metric for a channel n using the following equation;

$\mathrm{TP}=\frac{100}{\left(\left(\#<br><br><br><br>\mathrm{of}<br><br><br><br>\mathrm{direct}<br><br><br><br>\mathrm{neighbors}<br><br><br><br>\mathrm{using}<br><br><br><br>\mathrm{channel}<br><br><br><br>n\right)+\left(\#<br><br><br><br>\mathrm{of}<br><br><br><br>\mathrm{two}<br><br><br><br>\mathrm{hop}<br><br><br><br><br><br>\mathrm{neighbors}<br><br><br><br><br><br>\mathrm{using}<br><br><br><br><br><br>\mathrm{channel}<br><br><br><br>n\right)\right)}.$

9. An article comprising a computer readable storage medium having instructions stored thereon that, when executed by a computing platform, operate to:

identify, for an uninitialized node in a wireless mesh network, neighbor nodes that have been initialized, said neighbor nodes being capable of supporting a direct wireless link with said uninitialized node, wherein an initialized node is a node that already has assigned channels;

generate a list of channel configurations for said uninitialized node that satisfy a predetermined connectivity constraint with respect to said identified neighbor nodes;

calculate throughput metrics for channel configurations on said list; and

select a channel configuration for said uninitialized node based on said throughput metrics.

10. The article of claim 9, wherein said instructions further operate to:

change a status of said uninitialized node to initialized after said channel configuration has been selected.

11. The article of claim 10, wherein said instructions further operate to:

acquire a list of nodes in the wireless mesh network and change a status of all nodes on said list of nodes to uninitialized before operation to identify neighbor nodes, wherein said uninitialized node is a first node on said list of nodes.

12. The article of claim 11, wherein said instructions further operate to:

repeat operation to identify neighbor nodes, operation to generate a list, operation to calculate throughput metrics, operation to select a channel configuration, and operation to change a status for another node after operation to change said status of said first node.

13. An apparatus for use in a wireless mesh network, comprising:

a controller to determine channel allocations for nodes within the wireless mesh network, said controller to;

acquire a list of nodes in the wireless mesh network;

set all nodes on said list of nodes to a status of uninitialized; and

for each successive node on said list of nodes;

identify neighbor nodes of said node that have been initialized, said neighbor nodes being capable of supporting a direct wireless link with said node;

generate a list of channel configurations for said node that satisfy a predetermined connectivity constraint with respect to said identified neighbor nodes;

calculate throughput metrics for channel configurations on said list;

select a channel configuration for said node based on said throughput metrics; and

change a status of said node to initialized after said channel configuration has been selected for said node.

14. The apparatus of claim 13, wherein:

said predetermined connectivity constraint requires at least one common channel with each of said identified neighbor nodes.

15. The apparatus of claim 13, wherein:

said controller calculates a throughput metric for a channel n within a channel configuration using the following equation;

$\mathrm{TP}=\frac{100}{\left(\left(\#<br><br><br><br>\mathrm{of}<br><br><br><br>\mathrm{direct}<br><br><br><br>\mathrm{neighbors}<br><br><br><br>\mathrm{using}<br><br><br><br>\mathrm{channel}<br><br><br><br>n\right)+\left(\#<br><br><br><br>\mathrm{of}<br><br><br><br>\mathrm{two}<br><br><br><br>\mathrm{hop}<br><br><br><br><br><br>\mathrm{neighbors}<br><br><br><br><br><br>\mathrm{using}<br><br><br><br><br><br>\mathrm{channel}<br><br><br><br>n\right)\right)}.$

16. A system for use in a wireless mesh network, comprising:

at least one dipole antenna to act as a transition to a wireless communication channel;

a controller, in communication with said at least one dipole antenna, to determine channel allocations for nodes within the wireless mesh network, said controller to;

acquire a list of nodes in the wireless mesh network;

set all nodes on said list of nodes to a status of uninitialized; and

for each successive node on said list of nodes;

identify neighbor nodes of said node that have been initialized, said neighbor nodes being capable of supporting a direct wireless link with said node;

generate a list of channel configurations for said node that satisfy a predetermined connectivity constraint with respect to said identified neighbor nodes;

calculate throughput metrics for channel configurations on said list;

select a channel configuration for said node based on said throughput metrics; and

change a status of said node to initialized after said channel configuration has been selected for said node.

17. The system of claim 16, wherein:

said predetermined connectivity constraint requires at least one common channel with each of said identified neighbor nodes.

18. The apparatus of claim 16, wherein:

said controller calculates a throughput metric for a channel n within a channel configuration using the following equation;

$\mathrm{TP}=\frac{100}{\left(\left(\#<br><br><br><br>\mathrm{of}<br><br><br><br>\mathrm{direct}<br><br><br><br>\mathrm{neighbors}<br><br><br><br>\mathrm{using}<br><br><br><br>\mathrm{channel}<br><br><br><br>n\right)+\left(\#<br><br><br><br>\mathrm{of}<br><br><br><br>\mathrm{two}<br><br><br><br>\mathrm{hop}<br><br><br><br><br><br>\mathrm{neighbors}<br><br><br><br><br><br>\mathrm{using}<br><br><br><br><br><br>\mathrm{channel}<br><br><br><br>n\right)\right)}.$