Computing optimal channel allocations using decomposition methods and related devices
First Claim
Patent Images
1. A method for approximating an optimal allocation of channels to access points (APs) during a time frame, t, within a network comprising:
- (a) assigning a weight, Wn, to each AP;
(b) dividing an interference graph into a plurality of subgraphs;
(c) computing a maximized sum of weights associated with activated APs for each subgraph;
(d) combining each of the maximized sums to compute a total sum of weights for all of the subgraphs;
(e) forming new subgraphs;
(f) carrying out steps (c) and (d) using the new subgraphs;
(g) combining sums associated with the new subgraphs to compute a new total sum of weights; and
(h) selecting a highest total sum of weights from all of the total sum of weights, wherein the selected total sum represents a best approximation of optimal channel allocations.
12 Assignments
0 Petitions
Accused Products
Abstract
By decomposing (i.e., dividing) an interference graph into subgraphs, it becomes feasible to compute close approximations of an optimal channel allocation scheme within a reasonable amount of time. The channel allocation scheme may be used to allocate specific channels to access points (APs) in a wireless, local area network (WLAN).
20 Citations
32 Claims
-
1. A method for approximating an optimal allocation of channels to access points (APs) during a time frame, t, within a network comprising:
-
(a) assigning a weight, Wn, to each AP;
(b) dividing an interference graph into a plurality of subgraphs;
(c) computing a maximized sum of weights associated with activated APs for each subgraph;
(d) combining each of the maximized sums to compute a total sum of weights for all of the subgraphs;
(e) forming new subgraphs;
(f) carrying out steps (c) and (d) using the new subgraphs;
(g) combining sums associated with the new subgraphs to compute a new total sum of weights; and
(h) selecting a highest total sum of weights from all of the total sum of weights, wherein the selected total sum represents a best approximation of optimal channel allocations. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15)
-
-
16. A device for approximating an optimal allocation of channels to access points (APs) during a time frame, t, within a network operable to:
-
(a) assign a weight, Wn, to each AP;
(b) divide an interference graph into a plurality of subgraphs;
(c) compute a maximized sum of weights associated with activated APs for each subgraph;
(d) combine each of the maximized sums to compute a total sum of weights for all of the subgraphs;
(e) form new subgraphs;
(f) carry out steps (c) and (d) using the new subgraphs;
(g) combine sums associated with the new subgraphs to form a new total sum of weights; and
(h) select a highest total sum of weights from all of the total sum of weights, wherein the selected total sum represents a best approximation of optimal channel allocations. - View Dependent Claims (17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32)
-
Specification