Characterizing the capacity region in multi-channel, multi-radio mesh networks
First Claim
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.
12 Assignments
0 Petitions
Accused Products
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.
9 Citations
22 Claims
-
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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20)
-
-
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.
-
Specification