Computing optimal channel allocations using decomposition methods and related devices

• US 7,522,566 B2
• Filed: 09/30/2004
• Issued: 04/21/2009
• Est. Priority Date: 09/30/2004
• Status: Active Grant

• Current Assignee: RPX Corporation
• Original Assignee: Alcatel-Lucent USA, Inc. (Nokia Corporation)
• Inventors: Smith, Mark Anthony, Golestani, S. Jamaloddin, Rastogi, Rajeev
• Primary Examiner(s): Orgad, Edan
• Assistant Examiner(s): Ho, Chuong T
• Application Number:
  US10/953,355
• Publication Number:
  US 20060067258A1
• Time in Patent Office: 1,664 Days
• Field of Search: 370/338, 370329-337, 370/347, 370/310, 370/328, 455/450, 455446-449, 455/422, 455/403, 455/442
• US Class Current: 370/338
• CPC Class Codes: H04W 16/10 Dynamic resource partitioning
• CPC Class Codes: H04W 16/14 Spectrum sharing arrangements between different networks
• CPC Class Codes: H04W 16/20 for indoor coverage or short range network deployment
• CPC Class Codes: H04W 16/32 Hierarchical cell structures
• CPC Class Codes: H04W 28/16 Central resource management; Negotiation of resources or communication parameters, e.g. negotiating bandwidth or QoS [Quality of Service]
• CPC Class Codes: H04W 28/26 Resource reservation
• CPC Class Codes: H04W 84/12 WLAN [Wireless Local Area Networks]

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).

Claims

1. A method for allocating one or more channels to access points (APs) during a time frame, t, within a network comprising:

(a) assigning a weight, W_n, where n=1,2, . . . n ,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 first, 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;

(h) selecting a highest total sum of weights from the first computed total sum of weights and all of the subsequently computed, new total sum of weights, wherein the selected total sum represents a best approximation of optimal channel allocations; and

(i) allocating one or more channels to an AP based on the selected total sum performing the steps (a)-(i) by a controller.

2. The method as in claim 1 wherein the network comprises a wireless, local area network (WLAN).

3. The method as in claim 1 further comprising dividing the interference graph using a plurality of parallel horizontal and vertical interference strips.

4. The method as in claim 3 further comprising eliminating APs from the interference graph associated with areas that are associated with the plurality of parallel horizontal and parallel vertical interference strips.

5. The method as in claim 3 wherein a width of each strip equals a maximum interference distance.

6. The method as in claim 5 wherein the maximum interference distance comprises a distance beyond which an AP does not interfere with another AP.

7. The method as in claim 3 further comprising positioning the parallel strips such that a beginning of one parallel strip is separated by a selected decomposition interval, I, from the beginning of another parallel strip.

8. The method as in claim 7 wherein a width of a subgraph equals I-1.

9. The method as in claim 1 wherein the step of forming new subgraphs comprises shifting parallel horizontal or parallel vertical interference strips a distance equal to a width of a strip to form the new subgraphs.

10. The method as in claim 7 wherein the decomposition interval is selected to be O(1/∈

), where ∈

represents a deviation from an optimal value and O(1/∈

) represents a value proportional to 1/∈

.

11. The method as in claim 10 wherein the best approximation comprises a (1+∈

) approximation of the optimal channel allocation when an interference pattern of APs, associated with the selected total sum, conforms to a quasi-unit disk graph.

12. The method as in claim 1 further comprising identifying an active set of APs within each of the subgraphs.

13. The method as in claim 12 wherein each active set comprises one or more APs that can be allocated a channel from a group of available channels.

14. The method as in claim 12 further comprising allocating a channel from among the group of available channels to each AP within a subgraph, provided the same channel cannot be assigned to a pair of APs that make up an edge of an interference graph representing the subgraph.

15. The method as in claim 4 further comprising:

selecting an interference graph associated with the selected highest total sum of weights;

adding previously eliminated APs back to the selected interference graph;

attempting to allocate a channel to each added AP provided the same channel cannot be assigned to a pair of APs that make up an edge; and

adding a weight attributed to each AP that is allocated a channel to the selected total sum of weights to form a modified, total sum,

wherein the modified total sum represents a closer approximation of the optimal channel allocations than the best approximation.

16. A device for allocating one or more channels to access points (APs) during a time frame, t, within a network operable to:

(a) assign a weight, W_n, where n =1,2, . . . n, 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 first, 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;

(h) select a highest total sum of weights from the first computed total sum of weight and all of the subsequently computed, new total sum of weights, wherein the selected total sum represents a best approximation of optimal channel allocations; and

(i) allocating one or more channels to an AP based on the selected total sum.

17. The device as in claim 16 wherein the network comprises a wireless, local area network (WLAN).

18. The device as in claim 16 further operable to divide the interference graph using a plurality of parallel horizontal and vertical strips.

19. The device as in claim 18 further operable to eliminate APs from the interference graph associated with areas that are associated with the plurality of parallel horizontal and vertical strips.

20. The device as in claim 18 wherein a width of each strip equals a maximum interference distance.

21. The device as in claim 20 wherein the maximum interference distance comprises a distance beyond which an AP does not interfere with another AP.

22. The device as in claim 18 further operable to position the parallel strips such that a beginning of one parallel strip is separated by a selected decomposition interval, I, from the beginning of another parallel strip.

23. The device as in claim 22 wherein a width of a subgraph equals I-1.

24. The device as in claim 16 further operable to shift parallel horizontal or parallel vertical interference strips a distance equal to a width of a strip to form the new subgraphs.

25. The device as in claim 22 wherein the decomposition interval is selected to be O(1/∈

), where ∈

represents a deviation from an optimal value and O(1/∈

) represents a value proportional to 1/∈

.

26. The device as in claim 25 wherein the best approximation comprises a (1+∈

) approximation of the optimal channel allocation when an interference pattern of APs associated with the selected total sum conforms to a quasi-unit disk graph.

27. The device as in claim 16 further operable to identify an active set of APs within each of the subgraphs.

28. The device as in claim 27 wherein each active set comprises one or more APs that can be allocated a channel from a group of available channels.

29. The device as in claim 27 further operable to allocate a channel from among the group of available channels to each AP within a subgraph, provided the same channel cannot be assigned to a pair of APs that make up an edge of an interference graph representing the subgraph.

30. The device as in claim 19 further operable to:

select an interference graph associated with the selected highest total sum of weights;

add previously eliminated APs back into the selected interference graph;

attempt to allocate a channel to each added AP provided the same channel cannot be assigned to a pair of APs that make up an edge; and

add a weight attributed to each AP that is allocated a channel to the selected total sum of weights to form a modified, total sum,

wherein the modified total sum represents a closer approximation of the optimal channel allocations than the best approximation.

31. The device as in claim 16 wherein the device comprises a controller.

32. The device as in claim 16 wherein the device comprises a base station controller.