Computing optimal channel allocations using decomposition methods and related devices
AssigneeAlcatel-Lucent USA Inc.
InventorsS. Golestani, Rajeev Rastogi, Mark Smith
Life of this patent
Estimating the term…
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).
Claims32
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.
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.
Dependencies are inferred from the claim text.