Characterizing the capacity region in multi-channel, multi-radio mesh networks

• US 20070147248A1
• Filed: 12/22/2005
• Published: 06/28/2007
• Est. Priority Date: 12/22/2005
• Status: Active Grant

• Current Assignee: RPX Corporation
• Original Assignee: Alcatel-Lucent USA, Inc. (Nokia Corporation)
• Inventors: Kodialam, Muralidharan, Nandagopal, Thyagarajan
• Granted Patent: US 7,920,991 B2
• Time in Patent Office: Days
• US Class Current: 370/235
• CPC Class Codes: H04L 41/145 involving simulating, designing, planning or modelling of a network

Abstract

A method of characterizing a capacity region in a multi-channel, multi-radio mesh network of nodes interconnected by links. The method includes: (a) modeling the network by determining one or more link-flow feasibility constraints; (b) obtaining a feasible upper-capacity bound by solving an optimization problem using the one or more link-flow feasibility constraints as necessary conditions; and (c) using an algorithm adapted to provide a feasible lower-capacity bound by (i) receiving the solution to the optimization problem as input, (ii) allocating channels to links to meet a demand vector that satisfies the one or more link-flow feasibility constraints, and (iii) scheduling flows along the allocated channels. The upper- and lower-capacity bounds define the capacity region.

Claims

1. A method of characterizing a capacity region in a multi-channel, multi-radio mesh network of nodes interconnected by links, the method comprising:

(a) modeling the network;

(b) obtaining a feasible upper-capacity bound by solving an optimization problem; and

(c) using an algorithm adapted to provide a feasible lower-capacity bound based on the solution to the optimization problem;

wherein the upper- and lower-capacity bounds define the capacity region.

2. The invention of claim 1, wherein, in step (a), the network is modeled by determining one or more link-flow feasibility constraints.

3. The invention of claim 2, wherein, in step (b), the optimization problem uses the one or more link-flow feasibility constraints as necessary conditions.

4. The invention of claim 3 wherein, in step (c), the algorithm is adapted to (i) receive the solution to the optimization problem as input, (ii) allocate channels to links to meet a demand vector that satisfies the one or more link-flow feasibility constraints, and (iii) schedule flows along the allocated channels.

5. The invention of claim 1, wherein the upper- and lower-capacity bounds define the capacity region.

6. The invention of claim 1, wherein at least one node in the network has two or more radios.

7. The invention of claim 1, wherein two or more nodes in the network conform to different standards.

8. The invention of claim 7, wherein one standard is one of IEEE 802.11 a/b/g, and another standard is 802.16.

9. The invention of claim 1, wherein one or more of the link-flow feasibility constraints are derived from one or more node and/or channel characteristics.

10. The invention of claim 9, wherein the node and/or channel characteristics comprise the maximum number of channels that can be active on a link during a time slot.

11. The invention of claim 9, wherein the node and/or channel characteristics comprise the maximum number of radios that a node can use during a time slot.

12. The invention of claim 1, wherein the one or more link-flow feasibility constraints are derived, at least in part, by modeling interference from one or more neighboring nodes.

13. The invention of claim 1, wherein the optimization problem is solved as a concurrent flow problem.

14. The invention of claim 13, wherein the optimization problem is solved as a primal-dual algorithm.

15. The invention of claim 14, wherein the primal-dual algorithm alternates between (i) sending flow along shortest-path pairs and (ii) adjusting the length of links along which flow has been sent, until an optimum solution is reached.

16. The invention of claim 15, wherein:

e represents a data link using channel i and having a capacity c_i(e);

S_j represents a schedulable set of link-channel pairs {S₁, . . . ,S};

P_q represents a set of paths P for a source-destination pair q from s(q) to d(q);

r(q) represents flow to be routed from s(q) to d(q);

x(P) represents an amount of flow sent on path P;

β

(S_j) is an associated constant for each set S_j;

λ

is a scaling factor of the network; and

a primal formulation for the primal-dual algorithm is;

maximize λ

, subject to;

$\begin{array}{c}\underset{\left(e,i\right)\in <br><br>S_j}{\sum <br><br>}<br><br>\frac{\underset{q}{\sum <br><br>}<br><br>\underset{P\in <br><br>{\mathrm{??}}_q<br><br>\text{;<br><br>}\ni <br><br>\left(e,i\right)}{\sum <br><br>}<br><br>x<br><br>\left(P\right)}{\mathrm{\beta <br><br>}<br><br>\left(S_j\right)<br><br>c_i<br><br>\left(e\right)}\le <br><br>1,\forall <br><br>j\in <br><br>\left\{1,2,\mathrm{\dots <br><br>}<br><br>\text{\hspace{1em}<br><br>},L\right\},\\ \underset{P\in <br><br>{\mathrm{??}}_q}{\sum <br><br>}<br><br>x<br><br>\left(P\right)=\mathrm{\lambda <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>r<br><br>\left(q\right),\forall <br><br>q,\\ X<br><br>\left(p\right)\ge <br><br>0,\forall <br><br>P\in <br><br>{\mathrm{??}}_q,\forall <br><br>q.\end{array}$

17. The invention of claim 1, wherein the algorithm is a static-channel assignment algorithm.

18. The invention of claim 17, wherein the link-channel allocation is performed prior to the scheduling of the flows.

19. The invention of claim 17, wherein the scheduling of the flows is performed by a greedy coloring algorithm.

20. The invention of claim 1, wherein the algorithm is a dynamic-channel assignment algorithm.

21. The invention of claim 20, wherein the link-channel allocation is performed substantially concurrently with the scheduling of the flows.

22. The invention of claim 19, wherein the greedy coloring algorithm assigns all flows in the fewest possible number of time slots.

23. The invention of claim 20, wherein the greedy coloring algorithm assigns all flows in the fewest possible number of time slots.

24. The invention of claim 20, wherein the greedy coloring algorithm comprises:

(a) aggregating all flows on different channels on a link into a single scaled flow; and

(b) at the beginning of each time slot;

(i) forming an ordered list by sorting the links in descending order of unassigned flows; and

(ii) for each link in the ordered list;

(1) assigning the link to a first channel and decrementing the unassigned flow on the link;

(2) selecting a channel with the highest capacity if the next link in the ordered list can be assigned to a channel in the time slot; and

(3) repeating step (ii) for the next link in the ordered list if the next link in the ordered list cannot be assigned to a channel in the time slot.

25. A multi-channel, multi-radio mesh network of nodes interconnected by links, wherein the network comprises an apparatus for characterizing a capacity region, the apparatus adapted to:

(a) model the network by determining one or more link-flow feasibility constraints;

(b) obtain a feasible upper-capacity bound by solving an optimization problem using the one or more link-flow feasibility constraints as necessary conditions; and

(c) use an algorithm adapted to a feasible lower-capacity bound by (i) receiving the solution to the optimization problem as input, (ii) allocating channels to links to meet a demand vector that satisfies the one or more link-flow feasibility constraints, and (iii) scheduling flows along the allocated channels;

wherein the upper- and lower-capacity bounds define the capacity region.

26. Apparatus for characterizing a capacity region in a multi-channel, multi-radio mesh network of nodes interconnected by links, the apparatus adapted to:

(a) model the network by determining one or more link-flow feasibility constraints;

(b) obtain a feasible upper-capacity bound by solving an optimization problem using the one or more link-flow feasibility constraints as necessary conditions; and

(c) use an algorithm adapted to a feasible lower-capacity bound by (i) receiving the solution to the optimization problem as input, (ii) allocating channels to links to meet a demand vector that satisfies the one or more link-flow feasibility constraints, and (iii) scheduling flows along the allocated channels;

wherein the upper- and lower-capacity bounds define the capacity region.