Joint Channel Assignment and Routing in Wireless Networks

• US 20080107069A1
• Filed: 11/07/2006
• Published: 05/08/2008
• Est. Priority Date: 11/07/2006
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Tan, Kun, Wu, Haitao, Yang, Fan, Li, Shipeng
• Granted Patent: US 7,826,366 B2
• Time in Patent Office: Days
• US Class Current: 370/329
• CPC Class Codes: H04W 40/14 based on stability
• CPC Class Codes: H04W 72/542 using measured or perceived quality

Abstract

In a described implementation, a channel cost metric (CCM) is determined in a wireless network environment. The CCM may be determined responsive to an expected transmission time (ETT) and a frequency of air time (FAT), which reflects a channel utilization. In an example implementation, a channel assignment and/or a routing for a network configuration may be switched responsive to the determined CCM.

Claims

1. A device that is capable of functioning as a wireless node, the device comprising:

one or more radios to communicate over at least one link on at least one channel; and

a channel cost metric (CCM) determiner to determine a CCM value, the CCM determiner comprising;

an expected transmission time (ETT) determiner to determine an ETT value; and

a fraction of air time (FAT) determiner to determine a FAT value that represents a total consumed air time proportion of a given interval;

wherein the CCM determiner is to determine the CCM value responsive to the ETT value and the FAT value such that the CCM value represents an expected transmission time on each channel that is weighted by channel utilization.

4. The device as recited in claim 1, wherein the FAT value is determined by the FAT determiner on a per-wireless-node basis.

5. The device as recited in claim 4, wherein the FAT value comprises an equivalent FAT value that is determined relative to a common reference channel.

6. The device as recited in claim 1, further comprising:

a joint channel assignment and routing (JCAR) implementer to switch at least one of a channel or a routing in a wireless network in which the wireless node is participating so as to lower a CCM level in the wireless network.

2. The device as recited in claim L, wherein the ETT value is determined by the ETT determiner on a per-wireless-node basis.

3. The device as recited in claim 2, wherein the ETT value is determined by the ETT determiner based on ETTs on a particular channel for multiple links that are within a predetermined interference range of the wireless node.

7. A method comprising:

identifying multiple possible joint channel assignment and routing (JCAR) patterns for a wireless network;

determining respective channel cost metric (CCM) values corresponding to respective JCAR patterns for at least a portion of the possible JCAR patters, each CCM value responsive to an expected transmission time (ETT) that is weighted by fraction of air time (FAT), with FAT representing a proportion of channel utilization;

selecting the JCAR pattern that corresponds to a smallest CCM value; and

if the smallest CCM value corresponding to the selected SCAR pattern is less than a current CCM value corresponding to a current SCAR pattern, conducting a switching operation to implement the selected SCAR pattern in the wireless network.

8. The method as recited in claim 7, further comprising:

detecting a channel having a utilization that is higher than a predetermined threshold level;

wherein the identifying, the determining, the selecting, and the conducting are performed responsive to the detecting.

9. The method as recited in claim 7, farther comprising:

checking if each possible JCAR pattern is feasible by checking that a total estimated air time among interfering links on a given channel is less than a pre-defined threshold.

10. The method as recited in claim 9, further comprising:

verifying network connectivity for each possible JCAR pattern that is checked as being feasible by verifying that each node-pair that is currently connected is maintained as being connected under the possible SCAR pattern.

11. The method as recited in claim 10, wherein the portion of possible JCAR patterns for the determining of CCM values comprises those possible JCAR patterns that are checked as being feasible and that are verified as maintaining network connectivity.

12. The method as recited in claim 7, wherein the conducting of the switching operation to implement the selected JCAR pattern in the wireless network is performed if the smallest CCM value corresponding to the selected JCAR pattern is less than the current CCM value corresponding to the current JCAR pattern by a predetermined threshold amount.

13. The method as recited in claim 7, further comprising:

receiving performance parameters about links in the wireless network that are within an interference range of a wireless node that is performing the method;

wherein the determining is performed using the received performance parameters and an ETT that is calculated on a per-wireless-node basis.

14. The method as recited in claim 7, wherein the conducting of the switching operation is aborted prior to completion if a wireless node detects a chain puzzle in which wireless nodes are connected by a single channel.

15. One or more processor-accessible media including processor-executable instructions, the processor-executable instructions comprising:

a channel assignment module to communicate with a medium access control (MAC) layer;

an interface switching module to communicate with a routing layer; and

a joint channel assignment and routing (JCAR) decision maker to make decisions on whether to switch a network configuration responsive to a channel cost metric (CCM), the CCM based on an expected transmission time (ETT) that is weighted by a frequency of air time (FAT);

wherein the FAT reflects a channel utilization and ETT is determined on a per-wireless-node basis.

16. The one or more processor-accessible media as recited in claim 15, wherein the JCAR decision maker is further to request a channel assignment switch with an adjacent wireless node and to enable neighbor wireless nodes to vote on the channel assignment switch.

17. The one or more processor-accessible media as recited in claim 15, wherein a network configuration switching may entail at least one of a channel assignment change or a radio interface change.

18. The one or more processor-accessible media as recited in claim 15, wherein the channel assignment module is to obtain a traffic parameter, a capacity parameter, and a loss ratio parameter for each link within a predetermined interference range of a wireless node by interacting with the MAC layer using probing.

19. The one or more processor-accessible media as recited in claim 15, wherein the JCAR decision maker is triggered to search for new network configuration patterns that may have a smaller CCM when the FAT on a channel is higher than a predetermined threshold.

20. The one or more processor-accessible media as recited in claim 19, wherein the processor-executable instructions further comprise:

a connectivity module to reconfigure channel assignments so as to enlarge network connectivity when the FAT on a channel is lower than a predetermined threshold.