Joint channel assignment and routing in wireless networks

• US 7,826,366 B2
• Filed: 11/07/2006
• Issued: 11/02/2010
• Est. Priority Date: 11/07/2006
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Yang, Fan, Tan, Kun, Wu, Haitao, Li, Shipeng
• Primary Examiner(s): Corsaro; Nick
• Assistant Examiner(s): Matharu; Manpreet S
• Application Number:
  US11/557,269
• Publication Number:
  US 20080107069A1
• Time in Patent Office: 1,456 Days
• Field of Search: 455/450, 455/451, 455/452.1, 455/452.2, 455/453, 370/228, 370/338, 370/235
• US Class Current: 370/235
• 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 functions as a wireless node in an ad hoc wireless network, the device comprising:

a plurality of heterogeneous radios to communicate wirelessly over at least one link on at least one channel of the ad hoc wireless network; and

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

an expected transmission time (ETT) determiner to determine an ETT value, the ETT value being a unit of time calculated as a function of collision probability on the link, traffic loading on the link, expected total traffic on the link, and average transmission time of one data frame across the link; 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 determines the CCM value utilizing both the determined ETT value and the determined FAT value such that the CCM value reflects expected transmission time on each channel as weighted by channel utilization; and

a joint channel assignment and routing (JCAR) implementer configured to evaluate one or more CCM values determined by the CCM determiner and to jointly switch a channel and a route between wireless nodes in the wireless network to lower the CCM value.

2. The device as recited in claim 1, 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.

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, wherein the the JCAR implementer switches the channel and the route between wireless nodes in the wireless network to lower the CCM value to a lowest CCM level determined for the wireless network.

7. A method performed by a device that functions as a wireless node, the method comprising:

identifying multiple possible joint channel assignment and routing (JCAR) patterns for a wireless ad hock network, wherein at least one JCAR pattern denotes a combined solution that jointly considers channel assignment and routing between wireless nodes in the wireless network;

determining respective channel cost metric (CCM) values corresponding to respective JCAR patterns for at least a portion of the possible JCAR patterns, each CCM value responsive to an expected transmission time (ETT) for transmitting one or more packets across at least one link that is weighted by fraction of air time (FAT), with FAT representing a proportion of channel utilization, the ETT for transmitting at least one of the one or more packets across the at least one link being calculated as a function of offered traffic load, an expected total traffic including retransmissions and an average transmission time of one data frame;

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

if the smallest CCM value corresponding to the selected JCAR pattern is less than a current CCM value corresponding to a current JCAR pattern, conducting a switching operation to implement the selected JCAR 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, further 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 JCAR 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 the device 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 embodied with processor-executable instructions, the processor-executable instructions comprising:

a link status measurement module configured to obtain and share a traffic rate parameter, a time varying link capacity parameter, and a link loss ratio parameter, for each link between nodes on a Multi-radio Multi-channel Multi-hop Wireless Network (M³WN), at least one of the nodes comprising a plurality of heterogeneous radios;

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 across a link L_(i,j)^l between nodes i and j as ETT_(i,j)^l=T_(i,j)^l,DATA/(1−

p_(i,j)^l), where T_(i,j)^l,DATA denotes an average transmission time of one data frame on the link, and p_(i,j)^l is a collision probability (due to interference) for link L_(i,j)^l on a per-wireless-node basis, wherein network configuration switching comprises a joint channel assignment and routing switch between wireless nodes such that a network partition is avoided.

16. The one or more processor-accessible media as recited in claim 15, wherein the JCAR decision maker is further to request the 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 the routing switch comprises a radio interface change.

18. The one or more processor-accessible media as recited in claim 15, wherein the channel assignment module obtains the traffic parameter, the capacity parameter, and the 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 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.