Method for channel assignment and routing for multi-radio wireless mesh networks

• US 20070153702A1
• Filed: 01/04/2006
• Published: 07/05/2007
• Est. Priority Date: 01/04/2006
• Status: Active Grant

• Current Assignee: Alcatel-Lucent USA, Inc. (Nokia Corporation)
• Original Assignee: Alcatel-Lucent USA, Inc. (Nokia Corporation)
• Inventors: Bhatia, Randeep, Khan Alicherry, Mansoor, Li, Li
• Granted Patent: US 7,643,469 B2
• Time in Patent Office: Days
• US Class Current: 370/252
• CPC Class Codes: H04W 28/10 Flow control between communication endpoints
• CPC Class Codes: H04W 72/12 Wireless traffic scheduling
• CPC Class Codes: H04W 72/541 using the level of interference

Abstract

A methodology for making joint channel and routing assignments in multi-radio wireless mesh networks that takes into account interference constraints, the number of channels in a network and the number of radio available at each mesh router, and maximizes bandwidth allocation subject to fairness constraints. In particular, the methodology provides for routing, channel assignment and link scheduling in multi-radio mesh wireless networks utilizing a constant factor approximation technique that models the interference and fairness constraints and is able to account for the number of radios at each of the wireless nodes of a wireless mesh network.

Claims

1. A method for making joint channel and routing assignments in a wireless mesh network, said wireless mesh network having a plurality of nodes, a plurality of channels and a plurality of radios, said method comprising the steps of:

generating a flow graph of said wireless mesh network as function of said plurality of nodes, said plurality of channels and said plurality of radios;

identifying, as a function of a throughput of said wireless mesh network and a set of fairness constraints, a first routing of said plurality of channels and said plurality of radios from a flow from said flow graph;

a first adjusting of said flow to ensure a feasible channel assignment among said plurality of channels in said first routing, said first adjusting resulting in a second routing of said plurality of channels and said plurality of radios;

a second adjusting of said flow as a function of a maximum interference level across each channel of said plurality of channels in said second routing;

scaling said adjusted flow to eliminate all interference over said plurality of channels;

generating an interference free link schedule from said scaled, adjusted flow; and

applying said interference free link schedule across said wireless mesh network for exchanging communications between said plurality of nodes.

2. The method claim 1, wherein said identifying step further comprises the steps of:

applying a linear program to maximize said throughput subject to said fairness constraints, said linear program being formulated as a function of said flow graph.

3. The method of claim 1, wherein said first adjusting step further comprises the step of:

assigning particular ones of said channels to particular one of said radios, said assigning performed to minimize interference for said particular ones of said channels without a change in said second routing of said plurality of channels and said plurality of radios.

4. The method of claim 2, wherein said scaling step results in a feasible routing and channel assignment satisfying a sufficient condition for an interference free edge communication schedule.

5. The method of claim 1, wherein said generating said interference free schedule link schedule utilizes a plurality of edge flows corresponding to said flow.

6. The method of claim 2, wherein said linear program is applied subject to at least one flow constraint, at least one node radio constraint and at least one link congestion constraint.

7. The method of claim 1, wherein said wireless mesh network is an infrastructure wireless mesh network.

8. The method of claim 7, wherein at least one radio of said plurality of radios is IEEE 802.11 compliant.

9. The method of claim 8, wherein at least one node of said plurality of nodes is a gateway router.

10. The method of claim 9, wherein said infrastructure wireless mesh network provides network connectivity between a plurality of mobile clients and the Internet.

11. The method of claim 10, wherein said plurality of channels are orthogonal channels.

12. The method of claim 6, wherein said at least one flow constraint is given by:

$\underset{\left(u,v\right)\in <br><br>E^H}{\sum <br><br>}<br><br>f<br><br>\left(\left(u,v\right)\right)=\underset{\left(v,u\right)\in <br><br>E^H}{\sum <br><br>}<br><br>f<br><br>\left(\left(v,u\right)\right),\forall <br><br>v\in <br><br>V^H-\left\{s,t\right\}$

where H denotes a flow graph, V^H(E^H) denotes a set of nodes in H,. f(e) (c(e)) denotes the flow on an edge e of H, s denotes a source node, t denotes a sink node, u and v denote different nodes.

13. The method of claim 12, wherein said at least one radio constraint is given by:

$\underset{1\le <br><br>i\le <br><br>K}{\sum <br><br>}<br><br>\underset{e=\left(u,v\right)\in <br><br>E}{\sum <br><br>}<br><br>\frac{f<br><br>\left(e<br><br>\left(i\right)\right)}{c<br><br>\left(e\right)}+\underset{1\le <br><br>i\le <br><br>K}{\sum <br><br>}<br><br>\underset{e=\left(v,u\right)\in <br><br>E}{\sum <br><br>}<br><br>\frac{f<br><br>\left(e<br><br>\left(i\right)\right)}{c<br><br>\left(e\right)}\le <br><br>I<br><br>\left(v\right)$

where u and v denote different nodes, i denotes a channel, K denotes a total number of channels, e denotes an edge, and E denotes a set of edges.

14. The method of claim 13, wherein said at least one link congestion constraint is given by:

$\frac{f<br><br>\left(e<br><br>\left(i\right)\right)}{c<br><br>\left(e\right)}+\underset{e^{\mathrm{\prime <br><br>}}\in <br><br>H<br><br>\left(e\right)}{\sum <br><br>}<br><br>\frac{f<br><br>\left(e^{\mathrm{\prime <br><br>}}<br><br>\left(i\right)\right)}{c<br><br>\left(e^{\mathrm{\prime <br><br>}}\right)}\le <br><br>c<br><br>\left(q\right),\forall <br><br>e\in <br><br>E,1\le <br><br>i\le <br><br>K$

where c(q) denotes a constant value depending solely on the value of q.

15. The method of claim 4, wherein the scaling step employs a scaling factor L given by ζ

=max{1, max<sub>1<

i<

K</sub> Int(i)}where i denotes a channel, and K denotes a total number of channels.

16. The method of claim 6, wherein said linear program is given by:

$\min <br><br>\underset{1<<br><br>i<<br><br>K}{\sum <br><br>}<br><br>\underset{e=f<br><br>\left(v,u\right)\in <br><br>E}{\sum <br><br>}<br><br>\frac{f<br><br>\left(e<br><br>\left(i\right)\right)}{c<br><br>\left(e\right)}.$

where u and v denote different nodes, i denotes a channel, K denotes a total number of channels, e denotes an edge, and E denotes a set of edges.

17. The method of claim 1, wherein each radio of said plurality of radio operates on a particular one channel of said plurality of channels.

18. An article of manufacture comprising a machine-readable medium storing one or more programs for use in making joint channel and routing assignments in a wireless mesh network, said wireless mesh network having a plurality of nodes, a plurality of channels and a plurality of radios, said one or more programs when executed in a processor performing the steps of:

generating a flow graph of said wireless mesh network as function of said plurality of nodes, said plurality of channels and said plurality of radios;

identifying, as a function of a throughput of said wireless mesh network and a set of fairness constraints, a first routing of said plurality of channels and said plurality of radios from a flow from said flow graph;

a first adjusting of said flow to ensure a feasible channel assignment among said plurality of channels in said first routing, said first adjusting resulting in a second routing of said plurality of channels and said plurality of radios;

a second adjusting of said flow as a function of a maximum interference level across each channel of said plurality of channels in said second routing;

scaling said adjusted flow to eliminate all interference over said plurality of channels;

generating an interference free link schedule from said scaled, adjusted flow; and

applying said interference free link schedule across said wireless mesh network for exchanging communications between said plurality of nodes.

19. The article of manufacture claim 18, wherein said identifying step further comprises the steps of:

applying a linear program to maximize said throughput subject to said fairness constraints, said linear program being formulated as a function of said flow graph.

20. The article of manufacture claim 19, wherein said wireless mesh network is an infrastructure wireless mesh network which provides network connectivity between a plurality of mobile clients and the Internet.