Pinning and cascading avoidance in dynamic channel assignment for wireless LANS

• US 8,289,901 B2
• Filed: 03/17/2009
• Issued: 10/16/2012
• Est. Priority Date: 03/17/2009
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Tosic, Predrag, Shetty, Sandeep Jay, Chan, Douglas
• Primary Examiner(s): Sheikh, Ayaz
• Assistant Examiner(s): Haliyur, Venkatesh
• Application Number:
  US12/405,429
• Publication Number:
  US 20100238871A1
• Time in Patent Office: 1,309 Days
• Field of Search: 370328-463, 455/456.1, 709/231
• US Class Current: 370/328
• CPC Class Codes: H04W 16/10 Dynamic resource partitioning
• CPC Class Codes: H04W 24/00 Supervisory, monitoring or testing arrangements
• 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 72/00 Local resource management
• CPC Class Codes: H04W 84/12 WLAN [Wireless Local Area Networks]

Abstract

Techniques are provided to determine channel assignments for wireless access point (AP) devices in a wireless local area network (WLAN). From each of a plurality of AP devices operating at least one of a plurality of channels in the WLAN, wireless activity data is received that represents activity in each channel associated with signals of devices operating in the WLAN and associated with signals and energy from devices that are not operating in the WLAN as detected by the AP devices by receiving radio frequency energy in each of the plurality of channels. During a channel plan evaluation session, the wireless activity data is evaluated for multiple ones of the plurality of access point devices to determine whether the channel on which an access point device operates should be changed such that a decision to change the channel for at least one access point is limited to a localized region of the wireless network and does not necessarily affect a channel change decision for access points outside of the localized region of the wireless network. The channel on which the at least one access point device operates is changed or assigned based on the evaluation. In one form, the wireless activity data is a single metric that is derived from multiple pieces of data, each representing a different component of wireless activity determined by an AP device to be occurring in a channel.

Claims

1. A method comprising:

at a controller device configured to communicate with a plurality of wireless network access point devices operating on at least one of a plurality of channels in a wireless network, receiving from the access point devices wireless activity data representing activity in each of the channels;

generating at least one metric derived from the wireless activity data corresponding to one or more physical metrics measured by the access point devices representing activity in each of the channels associated with signals of devices operating in the wireless network and associated with signals and energy from devices that are not operating in the wireless network, wherein the at least one metric is a mathematical conversion of the one or more physical metrics;

during a channel plan evaluation session, evaluating the at least one metric for multiple ones of the access point devices to determine whether a channel on which at least one access point device operates should be changed such that a decision to change the channel on which the at least one access point device operates is limited to a localized region of the wireless network and does not affect a channel change decision for access points outside of the localized region of the wireless network; and

changing the channel on which the at least one access point device operates based on said evaluating.

2. The method of claim 1, wherein evaluating comprises:

(i.) generating a list of candidate access point devices whose metric is to be evaluated during the channel plan evaluation session;

(ii.) selecting a selected access point device in the list of candidate access point devices;

(iii.) evaluating a selected metric of the at least one metric corresponding to the selected access point device to determine whether a different channel from a current channel that the selected access point device is operating on would provide better performance based on other metrics of the at least one metric for each channel;

(iv.) identifying neighbor access point devices in the localized region of the wireless network for the selected access point device based on a receive signal strength with respect to signals transmitted by the selected access point device;

(v.) analyzing an impact of a channel change for the selected access point device to the neighbor access point devices in the localized region of the wireless network;

(vi.) removing from the list the selected access point device and one or more neighbor access point devices in the localized region of the wireless network based on said (v.) analyzing; and

repeating (ii.) selecting, (iv.) identifying, (v.) analyzing and (vi.) removing with respect to a next selected access point in the list until the list is empty.

3. The method of claim 2, wherein (iv.) identifying comprises identifying one-hop neighbor access point devices for which the receive signal strength exceeds a threshold and identifying two-hop neighbor access point devices for which the received signal strength from signals from any one of the one-hop neighbor access point devices exceeds a threshold.

4. The method of claim 3, wherein (v.) analyzing comprises evaluating a one-hop metric of the at least one metric for each of the one-hop neighbor access point devices on each of the channels based on a choice for a new channel for the selected access point device;

generating a new metric for the selected access point device for the new channel;

comparing the new metric for the new channel with a current metric for a current channel for the selected access point device;

determining whether a difference between the new metric for the new channel and the current metric for the current channel of the selected access point device satisfies a first criterion.

5. The method of claim 4, when it is determined that the new metric for the new channel and the current metric for the current channel of the selected access point device satisfies the first criterion, further comprising computing a cumulative metric from the new metric for the selected access point device and neighbor metric metrics for the one-hop and two-hop neighbor access point devices.

6. The method of claim 5, and further comprising:

comparing the cumulative metric with a second criterion; and

assigning a new channel plan evaluation session to the selected access point and to the one-hop and two-hop neighbor access point devices depending on whether the difference satisfies the first criterion, depending on whether the cumulative metric satisfies the second criterion and depending on whether channel searching is performed during a first channel searching stage or a second channel searching stage.

7. The method of claim 6, wherein during the first channel searching stage, said assigning the new channel plan evaluation session is based on satisfying the first criterion or the cumulative metric and satisfying the second criterion and during the second channel searching stage, said assigning the new channel plan evaluation session is based on satisfying the first criterion and the cumulative metric and satisfying the second criterion.

8. The method of claim 7, wherein during the first channel searching stage, removing comprises removing only the one-hop neighbor access point devices from the list, and during the second channel searching stage, removing comprises removing the one-hop and two-hop neighbor access point devices from the list.

9. The method of claim 2, wherein (ii.) selecting comprises selecting the selected access point device in the list that has a worst metric among remaining access point devices in the list.

10. The method of claim 2, wherein (ii.) selecting comprises selecting the selected access point device randomly from the list according to at least one of:

a uniform distribution and a distribution that assigns a greater probability to those access point devices in the list whose metric indicates a worst performance.

11. The method of claim 2, wherein (ii.) selecting the selected access point device comprises alternating at successive selection iterations between randomly selecting remaining access point devices in the list and selecting one access point device in the list that currently has a worst metric among the remaining access point devices in the list.

12. A system comprising:

a plurality of wireless network access point devices each configured to operate on at least one of a plurality of channels in a wireless network, wherein each access point is configured to receive radio frequency energy in each of the plurality of channels to measure physical metrics of the channels from the radio frequency energy;

a controller apparatus configured to;

receive wireless activity data from each of the wireless access point devices;

generate at least one metric derived from the physical metrics representing activity in each of the channels associated with signals of devices operating in the wireless network and associated with signals and energy from devices that are not operating in the wireless network, wherein the at least one metric is a mathematical conversion of the one or more physical metrics;

communicate with the access point devices and to supply control signals that control which channel each of the wireless network access point devices uses for operating in the wireless network;

evaluate during a channel plan evaluation session the at least one metric for multiple ones of the access point devices to determine whether a channel on which at least one access point device operates should be changed such that a decision to change the channel on which the at least one access point device operates is limited to a localized region of the wireless network and does not affect a channel change decision for access points outside of the localized region of the wireless network; and

change the channel on which the at least one access point device operates based on evaluation of the metric for multiple ones of the plurality of access point devices.

13. The system of claim 12, wherein the controller apparatus is configured to evaluate by:

(i.) generating a list of candidate access point devices whose metric is to be evaluated during the channel plan evaluation session;

(ii.) selecting a selected access point device in the list of candidate access point devices;

(iii.) evaluating a selected metric of the at least one metric corresponding to the selected access point device to determine whether a different channel from a current channel that the selected access point device is operating on would provide better performance based on other metrics of the at least one metric for each channel;

(iv.) identifying neighbor access point devices in the localized region of the wireless network for the selected access point device based on a receive signal strength with respect to signals transmitted by the selected access point device;

(v.) analyzing an impact of a channel change for the selected access point device to the neighbor access point devices in the localized region of the wireless network;

(vi.) removing from the list the selected access point device and one or more neighbor access point devices in the localized region of the wireless network based on said (v.) analyzing; and

repeating (ii.) selecting, (iv.) identifying, (v.) analyzing and (vi.) removing with respect to a next selected access point in the list until the list is empty.

14. The system of claim 13, wherein the controller apparatus is configured to perform said (iv.) identifying by identifying one-hop neighbor access point devices for which the receive signal strength exceeds a threshold and identifying two-hop neighbor access point devices for which the received signal strength from signals from any one of a one-hop neighbor access point device exceeds a threshold.

15. The system of claim 13, wherein the controller apparatus is configured to perform said (ii.) selecting by selecting the selected access point device in the list that has a worst metric among remaining access point devices in the list.

16. The system of claim 13, wherein the controller apparatus is configured to perform said (ii.) selecting the selected access point device randomly from the list according to at least one of:

a uniform distribution and a distribution that assigns a greater probability to those access point devices in the list whose metric indicates a worst performance.

17. The system of claim 13, wherein the controller apparatus is configured to perform said (ii.) selecting the selected access point device by alternating at successive selection iterations between randomly selecting remaining access point devices in the list and selecting one access point device in the list that currently has a worst metric among the remaining access point devices in the list.

18. One or more tangible non-transitory computer readable storage media storing instructions for execution by a processor and when executed operable to:

receive from each of a plurality of wireless access point devices operating on at least one of a plurality of channels in a wireless network, wireless activity data representing activity in each of the channels;

generate at least one metric derived from the wireless activity data corresponding to one or more physical metrics measured by the access point devices representing activity in each of the channels associated with signals of devices operating in the wireless network and associated with signals and energy from devices that are not operating in the wireless network, wherein the at least one metric is a mathematical conversion of the one or more physical metrics;

during a channel plan evaluation session, evaluate the wireless activity data for multiple ones of the access point devices to determine whether a channel on which at least one access point device operates should be changed such that a decision to change the channel on which the at least one access point device operates is limited to a localized region of the wireless network and does not affect a channel change decision for access points outside of the localized region of the wireless network; and

change the channel on which the at least one access point device operates based on the evaluation.

19. The non-transitory computer readable storage media of claim 18, wherein the instructions that are operable to evaluate comprises instructions that are operable to:

(i.) generate a list of candidate access point devices whose wireless activity data is to be evaluated during the channel plan evaluation session;

(ii.) select a selected access point device in the list of candidate access point devices;

(iii.) evaluate a selected metric of the at least one metric, wherein the selected metric is a mathematical conversation of a physical metric corresponding to the selected access point device to determine whether a different channel from a current channel that the selected access point device is operating on would provide better performance based on other metrics of the at least one metric for each channel;

(iv.) identify neighbor access point devices in the localized region of the wireless network for the selected access point device based on a receive signal strength with respect to signals transmitted by the selected access point device;

(v.) analyze an impact of a channel change for the selected access point device to the neighbor access point devices in the localized region of the wireless network;

(vi.) remove from the list the selected access point device and one or more neighbor access point devices in the localized region of the wireless network based on said (v.) analyze operation; and

(vii.) repeat said (ii.) select, (iv.) identify, (v.) analyze and (vi.) remove operations with respect to a next selected access point in the list until the list is empty.

20. The non-transitory computer readable storage media of claim 19, wherein the instructions that are operable to (ii.) select comprise instructions that are operable to select the selected access point device randomly from the list according to at least one of:

a uniform distribution and a distribution that assigns a greater probability to those access point devices in the list whose metric indicates a worst performance.

21. The non-transitory computer readable storage media of claim 19, wherein the instructions that are operable to (ii.) select the selected access point device comprise instructions that are operable to alternate at successive selection iterations between randomly selecting remaining access point devices in the list and selecting one access point device in the list that currently has a worst metric among the remaining access point devices in the list.