Characterizing the capacity region in multi-channel, multi-radio mesh networks
View Patent ↗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.
1. A server-implemented method of characterizing a capacity region in a multi-channel, multi-radio mesh network of nodes interconnected by links, the method comprising:
(a) the server modeling the network;
(b) the server obtaining a feasible upper-capacity bound by solving an optimization problem; and
(c) the server using an algorithm that provides a feasible lower-capacity bound based on the solution to the optimization problem, wherein the algorithm comprises (i) receiving the solution to the optimization problem as input, (ii) allocating channels to links to meet a demand vector that satisfies a plurality of link-flow feasibility constraints, and (iii) scheduling flows along the allocated channels;
wherein:
the upper- and lower-capacity bounds define the capacity region;
each of a plurality of nodes in the network has a number of channels and a number of radios; and
in at least one of the plurality of nodes, the number of channels is different from the number of radios.
2. The method of claim 1 , wherein, in step (a), the network is modeled by determining the link-flow feasibility constraints.
3. The method of claim 2 , wherein, in step (b), the optimization problem uses the link-flow feasibility constraints as necessary conditions.
4. The method of claim 1 , wherein at least one node in the network has two or more radios.
5. The method of claim 1 , wherein two or more nodes in the network conform to different standards.
6. The method of claim 5 , wherein one standard is one of IEEE 802.11 a/b/g, and another standard is 802.16.
7. The method of claim 1 , wherein one or more of the link-flow feasibility constraints are derived from one or more node and/or channel characteristics.
8. The method of claim 7 , wherein the node and/or channel characteristics comprise the maximum number of channels that can be active on a link during a time slot.
9. The method of claim 7 , wherein the node and/or channel characteristics comprise the maximum number of radios that a node can use during a time slot.
10. The method of claim 1 , wherein the link-flow feasibility constraints are derived, at least in part, by modeling interference from one or more neighboring nodes.
11. The method of claim 1 , wherein the optimization problem is solved as a concurrent flow problem.
12. The method of claim 11 , wherein the optimization problem is solved as a primal-dual algorithm.
13. The method of claim 12 , 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.
14. The method of claim 13 , wherein:
e represents a data link using channel i and having a capacity c i (e);
S j represents a schedulable link-channel pair, with representing the number of schedulable link-channel pairs in the set {S 1 , . . . , S }, >1;
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;
each schedulable link-channel pair S j has an associated constant β(S j ), where β(S j )≠0;
λ is a scaling factor of the network; and
a primal formulation for the primal-dual algorithm is:
maximize λ, subject to:
∑
(
e
,
i
)
∈
S
j
∑
q
∑
P
∈
𝒫
q
:
P
∋
(
e
,
i
)
x
(
P
)
β
(
S
j
)
c
i
(
e
)
≤
1
,
∀
j
∈
{
1
,
2
,
…
,
ℒ
}
,
∑
P
∈
𝒫
q
x
(
P
)
=
λ
r
(
q
)
,
∀
q
,
x
(
P
)
≥
0
,
∀
P
∈
𝒫
q
,
∀
q
.
15. The method of claim 1 , wherein the algorithm is a static-channel assignment algorithm.
16. The method of claim 15 , wherein the link-channel allocation is performed prior to the scheduling of the flows.
17. The method of claim 15 , wherein the scheduling of the flows is performed by a greedy coloring algorithm.
18. The method of claim 17 , wherein the greedy coloring algorithm assigns all flows in the fewest possible number of time slots.
19. The method of claim 1 , wherein the algorithm is a dynamic-channel assignment algorithm.
20. The method of claim 19 , wherein the link-channel allocation is performed substantially concurrently with the scheduling of the flows.
21. A server for characterizing a capacity region in a multi-channel, multi-radio mesh network of nodes interconnected by links, the server comprising a processor performing the steps of:
(a) modeling the network by determining a plurality of link-flow feasibility constraints;
(b) obtaining a feasible upper-capacity bound by solving an optimization problem using the link-flow feasibility constraints as necessary conditions; and
(c) using an algorithm that provides 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 link-flow feasibility constraints, and (iii) scheduling flows along the allocated channels;
wherein:
the upper- and lower-capacity bounds define the capacity region;
each of a plurality of nodes in the network has a number of channels and a number of radios; and
in at least one of the plurality of nodes, the number of channels is different from the number of radios.
22. A server-implemented method of characterizing a capacity region in a multi-channel, multi-radio mesh network of nodes interconnected by links, the method comprising:
(a) the server modeling the network;
(b) the server obtaining a feasible upper-capacity bound by solving an optimization problem; and
(c) the server using an algorithm that provides a feasible lower-capacity bound based on the solution to the optimization problem, the algorithm comprising scheduling flows using a greedy coloring algorithm;
wherein:
the upper- and lower-capacity bounds define the capacity region;
each of a plurality of nodes in the network has a number of channels and a number of radios;
in at least one of the plurality of nodes, the number of channels is different from the number of radios; and
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 e in the ordered list:
(1) assigning link e to a first channel for link e and decrementing the unassigned flow on link e;
(2) selecting and assigning, for link e, a second channel with the highest capacity if the next link following link e in the ordered list can be assigned to the second channel in the time slot; and
(3) repeating step (ii) for the next link following link e in the ordered list if the next link following link e in the ordered list cannot be assigned to a channel in the time slot.