27-06-2012, 05:10 PM
A Dynamic Channel Allocation Mechanism for IEEE 802.11 Networks
[attachment=25826]
Abstract
The great popularity of IEEE 802.11 along with
channel scarcity may lead to a degraded overall performance if
an intelligent channel allocation process is not used. A channel
allocation unaware of other network’s presence in the area may
increase medium access contention and co-channel interference,
harming networks’ aggregate capacity. This work proposes a
new automatic channel allocation mechanism for infra-structured
IEEE 802.11 networks that works in an independent and
distributed manner in access points and uses clients station’s
measurements exchanged with the new IEEE 802.11k standard.
I. INTRODUCTION
The growing number of networks based on wireless IEEE
802.11 standard has created some operational problems. The
channel selection is one of the problems that appear in 802.11
networks operating in the infrastructure mode. At this mode,
all packets are exchanged between stations and the Access
Point (AP). The channel selection at the AP determines the
center frequency utilized on these transmissions. This choice
may adversely affect networks’ performance by increasing the
medium access contention and the co-channel interference.
The IEEE 802.11b [1] and 802.11g [2] standards operate in
2.4 GHz unlicensed frequency band, known also as Industry,
Scientific and Medical band (ISM band). IEEE 802.11 divides
ISM band into 11 channels, but only 3 of them (channels 1,
6 and 11) do not have spectrum overlap. IEEE 802.11a [3]
operates in 5.4 GHz unlicensed frequency band and offers 12
non-overlapping channels, 8 for indoor use and 4 for outdoor.
The 802.11 channel scarcity (a problem more evident in
802.11b and 802.11g standards) limits the number of networks
that can coexist in the same area without interference.
Spectrum sharing is the main source of interference, harming
communication throughput and latency. However, other interference
contributions, as adjacent channel interference, are also
important. Hence, we can propose three basic objectives to
decrease interference: spectral share minimization - avoiding
medium access contention and maximizing frequency reuse;
adjacent channel interference minimization - avoiding performance
degradation generated by spectrum overlap; co-channel
interference minimization - avoiding unacceptable signal-tonoise
ratio (SNR) generated by remote stations transmissions.
In practice, the channel selection problem may appear in
two different scenarios: with or without unique administration.
In scenarios with unique administration, the central entity has
Marcel William Rocha da Silva and Jos´e Ferreira de Rezende are
in the Grupo de Teleinform´atica e Automac¸ ˜ao, COPPE, Programa
de Engenharia El´etrica, Universidade Federal do Rio de Janeiro, Rio
de Janeiro-RJ, Brasil, 21.945-970, Phone: +55 21 2260 5010. Emails:
{marcel,rezende}[at]gta.ufrj.br. This work is supported by
CAPES/CNPq/FINEP/FAPERJ.
access to many important useful settings that make easier to
find solutions and develop mechanisms to channel allocation
problem. In scenarios of decentralized administration, different
entities control the APs and there is very little knowledge
about other APs in the area. These cases impose great challenges
at the search of channel allocation solutions because of
the information scarcity and the lack of coordination between
the administrators controlling the APs.
This work proposes a new channel allocation mechanism
for infrastructured 802.11 networks operating in decentralized
scenarios. The proposed mechanism operates at the AP selecting
the operating channel automatically and does not require
communication between the APs. To achieve this goal, it uses
some features proposed in the new IEEE 802.11k [4] draft
standard that standardizes radio information measurements
exchange amongst stations.
The next Section presents some channel selection related
works and Section III explains some important 802.11 interference
properties. Then, in Section IV, we present a brief
overview of the new 802.11k draft standard. Sections V and
VI present the proposed dynamic channel selection mechanism
and its performance evaluation, respectively. Finally, Section
VII draws the conclusions.
II. RELATED WORKS
Many other works have discussed the IEEE 802.11 channel
allocation problem [5–9]. However, most of them analyze
and propose solutions only to centralized scenarios. Solutions
utilizing graph-coloring techniques are the most adopted [5, 6,
8, 9]. Usually, this approach considers each AP as a vertex of
the network representing graph, and each potential interference
region between the BSSs (Basic Service Sets) (Figure 1) as
an edge.
Fig. 1. Example of BSSs disposed in a region and its representing graph.
Finding graph coloring solutions to 802.11 channel allocation
problem is, in general, a NP-hard problem [6, 8,
9]. Therefore, algorithms to find optimal solutions present
higher computational effort with larger networks. To face this
SBrT © 403
VI INTERNATIONAL TELECOMMUNICATIONS SYMPOSIUM (ITS2006), SEPTEMBER 3-6, 2006, FORTALEZA-CE, BRAZIL
limitation, the authors usually propose heuristics with low
computational costs that find suboptimal solutions. The main
difference between algorithms proposed for channel allocation
is the objective function, which indicates what the coloring
algorithms goal is.
The work [5] proposes a heuristic algorithm for graph
coloring that takes into account the traffic demand of each
BSS for the channel allocation. In [6], the authors proposed
a greedy coloring algorithm to find a channel allocation that
maximizes the number of neighbors with different channels.
Work [7] claims that AP placement and channel selection are
coupled problems and proposes a new technique to perform
this task.
To the best of our knowledge, [8] is the only previous
work to propose solution to channel allocation in decentralized
scenarios. They developed a new approach to the coloring
technique by setting weights to the edges of the interference
graph indicating the relevance of utilizing different channels
in the vertex connected by that edge. The edges weights are
a metric of the number of stations placed in the conflict
region that originated that edge. The BSSs’ client stations are
responsible for detecting the presence of other BSSs’ client
stations in interference region. They realize a passive scan
of the operating channels to sense packets destined to other
APs. The reason why client stations are responsible for this
task, and not the AP, is that they have a better view of the
interference scenario than the AP. Their proposed channel
selection mechanism operates in centralized or distributed
fashion.
The work in [8] was extended in [9], when the authors
discuss that the channel selection task can be coupled with load
balance. However, with this new increment the mechanism
focus deviate from the decentralized scenario where the client
stations cannot decide which AP it uses. Another channel
selection mechanism, cited in [8] and [9], is the LCCS (Least
Congested Channel Search). It is a mechanism implemented
at some CISCO APs that searches for another channel (with
less occupation) when others BSSs traffic exceeds a threshold.
The mechanism proposed in this paper resembles LCCS.
The most important differences are that it measures others
BSSs traffic at the client stations (which have a better picture
of interference than the AP) and it searches better channels
conditions proactively.
III. INTERFERENCE IN IEEE 802.11
Some points related to interference in 802.11 networks
needs discussion for completely understanding of the proposed
algorithm. Interference represents a problem in any wireless
communication system. However, in 802.11 networks it appears
in a slight different way, especially due to the medium
access mechanism adopted by 802.11.
With CSMA/CA, prior to transmitting a frame, a station
senses the medium idle for a small amount of time. If it
senses other stations’ transmission, it waits the end of their
transmission to start its own, avoiding a possible collision.
This feature makes CSMA/CA very robust to interference in
exchange to delay and throughput performance.
IEEE 802.11 transmissions generates three reception regions
where receiving stations behave differently [10]. The reception
zone, nearest to the transmitter, is where receiving stations
can notice and decode packets. The carrier sense zone is the
intermediate one, where receiving stations can only notice
packets transmissions due to energy levels but they cannot
be decoded. Moreover, at the interference zone, receiving
stations cannot notice packet transmissions but their energy
contribution is added to the noise floor as interference.
Fig. 2. CSMA/CA activity avoiding interference.
In Figure 2, when station (1) transmits, stations (2) and (3)
must wait the end of this transmission before starting another
one, sharing channel access with the station (1). Station (4),
which is outside the reception and carrier sense zones, does
not share medium access with station (1), but it suffers cochannel
interference generated by its transmissions.
The above example shows that packet decoding (at reception
zone) or carrier sense (at carrier sense zone) avoid concurrent
transmissions of stations inside each other’s reception
or carrier sense zone. The packet decoding makes it obtain
information about packet transmission duration (through a
field of 802.11 MAC header). Therefore, stations set the
NAV (Network Allocation Vector) that is an indicator counter
of transmissions ending. The carrier sense itself detects that
the medium is idle due to energy thresholds and avoids cochannel
interference generation. This way, CSMA/CA avoids
interference of near networks that are using the same channel.
However, it increases medium access contention through
medium access sharing.
As seen above, CSMA/CA particularities suggests that
channel selection mechanism must differently account for near
and far stations presence that increases medium access sharing
or noise levels, respectively. In our proposal, we utilize channel
load level and noise level to solve this problem.
IV. IEEE 802.11K STANDARD
The new 802.11k draft standard [4] specifies some types
of radio information and the respective messages to request
and report them. The main 802.11k objectives are to enable
specific radio features measurements by network stations,
standardize request/report messages to the exchange of these
measurements and make the gathered information available to
higher network layers. This standard development will offer
SBrT © 404
VI INTERNATIONAL TELECOMMUNICATIONS SYMPOSIUM (ITS2006), SEPTEMBER 3-6, 2006, FORTALEZA-CE, BRAZIL
useful management tools to network stations to provide useful
information to new protocols and mechanisms.
A. Radio Measurements
So far, the 802.11k draft standard specifies eight types of
radio measurements information. For the sake of brevity, we
present only the radio measurements used in this proposal.
• Channel Load Information: gather channel load information
in a specific number of channels in the measurement
duration. The sensing station obtains it by
dividing the amount of time the medium was idle by the
measurement duration. The sensing station may use NAV
or carrier sense to detect if the medium was idle.
• Noise Histogram: gives noise level histogram of noise
values collected in a specific number of channels in the
measurement duration. The sensing station makes noise
measurements only when the medium is idle.
A station can conduct measurements at its operating channel
or at non-serving channels1 and most of them may be
performed passively only by packet exchange observation,
without affecting network operation. However, non-serving
channels measurement may lead to performance degradation
since the sensing station needs to switch channels during
measurement and stay incapable of exchanging packets during
this period. The 802.11k standard recommends requesting only
short and spaced non-serving channel measurements.
A request option that can reduce overhead generated by nonserving
channels measuring is the concurrent measurement.
The sensing node may conduct most information measurement
concurrently, decreasing the information acquisition time and
the performance harm it generates. Another feature that can
reduce the impact of measuring non-serving channels is the
packet buffering technique, which is already used in 802.11
power saving mechanism, where the AP stores packets destined
to stations in power save mode. The stations could use
this technique when measuring non-serving channels.
B. Message Exchange
IEEE 802.11k standard defines two basic message types:
request and report messages. Stations may exchange these
messages in station-station or station-AP fashion. Besides, they
can send these messages in unicast, broadcast or multicast.
The message exchange occurs either by one station requesting
other station measurement information or by one station
reporting by itself its measured information.
Each request/report message is a MAC management frame
that has information about measurements settings, which advise
the sensing station about how to execute measurements
(channels, duration, start time, concurrency aspects, etc.). Each
information measurement contains one element per information
type that has the measurement information (in requests)
or the measurement results (in reports).
1Channels different of the operating channel used by the network.
V. DYNAMIC CHANNEL SELECTION
As discussed in Section III, a bad channel allocation may
increase medium access contention and co-channel interference.
Therefore, the channel selection algorithm proposed
needs to consider this information at the selection process.
To achieve this goal, we use the 802.11k standard to feed
APs channel selection algorithm with channel load and noise
levels. However, before presenting the algorithm, we present
some concerns about how to obtain these inputs.
A. Algorithm Inputs Acquisition
With the proposed mechanism, client stations are responsible
for conducting measurements. It is not desirable that the
AP itself do measurements because client stations have a much
better picture of potential interference problems than the AP
[8, 9]. Besides, making the AP switch channels periodically
would turn down all BSS communications simultaneously.
The selection algorithm implemented in the AP uses request
and report messages of the 802.11k standard in order to trigger
and collect measurements. The AP periodically sends request
messages to the client stations elected to perform the channels
sensing task. These stations should perform measurements
concurrently in all possible non-overlapping channels. Sensing
nodes’ election is an important step of the algorithm. We
propose realizing measurements in all client stations since this
generates a wide view of the interference problem.
The AP sends measurement requests to each station at a
random time within the algorithm execution window. Hence,
the algorithm will have reports from all client stations that it
manages at its execution and will use the mean values of the
reports received for load and noise levels.
One problem that should arise is the overhead generated
by each client measuring all channels in each algorithm
execution window. However, the overhead generated by this
measurement only becomes significant if the measurements
duration and periodicity are high. If these parameters are kept
low, the overhead generated will be negligible.
Once it has measurement results from all channels, the
channel selection algorithm starts its operation. The algorithm
reads two arrays, one with channel load values and
other with channel noise values. Each position carries the
averages of channel load or noise level of the channel it
represents. Obtaining each channel load value is a simple
average calculation of the values returned by the client station
reports. Obtaining noise average values, however, is not a
simple average calculation since these values are returned in
a histogram format (Figure 3). To obtain the average we used
equation 1.
Fig. 3. Histogram example: the letters represent the number of events at
each value range, and the numbers represent the average value of each range.
Average =
1 × a + 2 × b + 3 × c + 4 × d + 5 × e
a + b + c + d + e
(1)
SBrT © 405
VI INTERNATIONAL TELECOMMUNICATIONS SYMPOSIUM (ITS2006), SEPTEMBER 3-6, 2006, FORTALEZA-CE, BRAZIL
Note also that the channel load measurement should take
into account only the traffic generated by others BSS stations.
Otherwise, the AP can perform a channel switch when its own
traffic raises channel occupation.
B. Channel Selection Algorithm
As the priority of the algorithm is to minimize channel load,
it only considers noise levels of lightly loaded channels for
selecting an operating channel. The algorithm has three steps:
1) if the load of the current channel does not exceed a
certain threshold α, the current operating channel is
maintained and the algorithm is finished. Otherwise,
proceeds to step 2.
2) selects the N channels with the lowest load and proceeds
to step 3.
3) chooses among the N channels selected above the one
that presents the lowest noise level.
The α threshold, cited in the first step, works like an
aggressiveness adjust parameter, and indicates how much
channel load is tolerated at the operating channel. Only if
channel load exceeds the α parameter, the channel selection
mechanism perform the search for a better condition executing
steps two and three of the selection algorithm. This prevents
many undesirable channel switches due to other BSS control
traffic.
VI. SIMULATIONS
For the evaluation of the automatic channel selection mechanism
proposed, this work presents simulations with ns-22. The
main objective of these simulations is to evaluate the algorithm
parameters and the gains obtained with the channel selection
mechanism.
The simulations with ns-2 required the implementation of
new features not present at its original code. Firstly, we
implemented the channel occupation and noise measuring
mechanisms as specified in the 802.11k standard. Besides,
we also implemented all the co-channel noise calculation
in ns-2. Other key feature implemented is the ability of
switching channels during a simulation run. Moreover, in order
to simulate infrastructured networks, we used the NOAH3 (No
Ad-Hoc Routing Agent) module to avoid ad hoc routing traffic.
We fixed some parameters through the performed simulations.
Each BSS comprehends one AP along with three
client stations that generate one TCP flow each towards the
AP (uplink traffic). The physical transmission rate is set to
11 Mbps for data frames and 2 Mbps for control frames.
A. Channel Selection Interval
An important parameter of the proposed mechanism is the
channel selection interval. This parameter is a uniform random
variable of a given mean value. For each simulation scenario,
the mean value of the interval is varied from 20 seconds to
140 seconds, but keeping the same ratio between the mean
2The Network Simulator (ns-2) - http://www.isi.edu/nsnam/ns/
3NOAH - http://icapeople.epfl.ch/widmer/uwb/ns-2/noah/
value, its upper and lower limits and the simulation duration.
The uniform random variable limits are four times shorter than
the mean, and the simulation duration is five times higher.
The simulations that evaluate the selection interval comprehend
nine BSSs randomly disposed in a 2000-meter side
square area, the α parameter is set to 10%, the number of
non-overlapping channels to three and the channel measuring
time to 150ms. Fifty simulation runs for each selection interval
were used. All results presented below are the averaged values
of these runs with a 95% confidence interval.
32
33
34
35
36
37
38
39
40
20 40 60 80 100 120 140
Aggregate Throughput (Mbps)
Mean Selection Interval (seconds)
area=2000mx2000m, channels=3, BSSs=9, alpha=10%, sensing time=150ms
(a) Aggregate Throughput.
4
5
6
7
8
9
10
11
12
20 40 60 80 100 120 140
Average Channel Switches
Mean Selection Interval (seconds)
area=2000mx2000m, channels=3, BSSs=9, alpha=10%, sensing time=150ms
(b) Average Channel switches.
Fig. 4. Channel selection periodicity variation.
As it can be seen in Figure 4(a), the aggregate throughput
presents some slight performance degradation for shorter and
longer channel selection intervals. For shorter values, the harm
generated by the communication pause time, which has a fixed
value, increases. For longer channel selection intervals, the
information measured by sensing nodes are outdated and do
not reflect the real network interference picture, making the
channel selection algorithm to perform wrong channel choices.
Figure 4(b) presents the number of channel switches during
the simulation time. This value increases for short selection
intervals. This happens because, as with the aggregate throughput,
pauses in communication are more significant, affecting
the sensing task, which may return wrong values.
SBrT © 406
VI INTERNATIONAL TELECOMMUNICATIONS SYMPOSIUM (ITS2006), SEPTEMBER 3-6, 2006, FORTALEZA-CE, BRAZIL
From the results, we conclude that for the channel selection
interval a value about 60 seconds is the best choice for the
scenarios analyzed. Therefore, we will use this value as a base
to evaluate other algorithm parameters.
[attachment=25826]
Abstract
The great popularity of IEEE 802.11 along with
channel scarcity may lead to a degraded overall performance if
an intelligent channel allocation process is not used. A channel
allocation unaware of other network’s presence in the area may
increase medium access contention and co-channel interference,
harming networks’ aggregate capacity. This work proposes a
new automatic channel allocation mechanism for infra-structured
IEEE 802.11 networks that works in an independent and
distributed manner in access points and uses clients station’s
measurements exchanged with the new IEEE 802.11k standard.
I. INTRODUCTION
The growing number of networks based on wireless IEEE
802.11 standard has created some operational problems. The
channel selection is one of the problems that appear in 802.11
networks operating in the infrastructure mode. At this mode,
all packets are exchanged between stations and the Access
Point (AP). The channel selection at the AP determines the
center frequency utilized on these transmissions. This choice
may adversely affect networks’ performance by increasing the
medium access contention and the co-channel interference.
The IEEE 802.11b [1] and 802.11g [2] standards operate in
2.4 GHz unlicensed frequency band, known also as Industry,
Scientific and Medical band (ISM band). IEEE 802.11 divides
ISM band into 11 channels, but only 3 of them (channels 1,
6 and 11) do not have spectrum overlap. IEEE 802.11a [3]
operates in 5.4 GHz unlicensed frequency band and offers 12
non-overlapping channels, 8 for indoor use and 4 for outdoor.
The 802.11 channel scarcity (a problem more evident in
802.11b and 802.11g standards) limits the number of networks
that can coexist in the same area without interference.
Spectrum sharing is the main source of interference, harming
communication throughput and latency. However, other interference
contributions, as adjacent channel interference, are also
important. Hence, we can propose three basic objectives to
decrease interference: spectral share minimization - avoiding
medium access contention and maximizing frequency reuse;
adjacent channel interference minimization - avoiding performance
degradation generated by spectrum overlap; co-channel
interference minimization - avoiding unacceptable signal-tonoise
ratio (SNR) generated by remote stations transmissions.
In practice, the channel selection problem may appear in
two different scenarios: with or without unique administration.
In scenarios with unique administration, the central entity has
Marcel William Rocha da Silva and Jos´e Ferreira de Rezende are
in the Grupo de Teleinform´atica e Automac¸ ˜ao, COPPE, Programa
de Engenharia El´etrica, Universidade Federal do Rio de Janeiro, Rio
de Janeiro-RJ, Brasil, 21.945-970, Phone: +55 21 2260 5010. Emails:
{marcel,rezende}[at]gta.ufrj.br. This work is supported by
CAPES/CNPq/FINEP/FAPERJ.
access to many important useful settings that make easier to
find solutions and develop mechanisms to channel allocation
problem. In scenarios of decentralized administration, different
entities control the APs and there is very little knowledge
about other APs in the area. These cases impose great challenges
at the search of channel allocation solutions because of
the information scarcity and the lack of coordination between
the administrators controlling the APs.
This work proposes a new channel allocation mechanism
for infrastructured 802.11 networks operating in decentralized
scenarios. The proposed mechanism operates at the AP selecting
the operating channel automatically and does not require
communication between the APs. To achieve this goal, it uses
some features proposed in the new IEEE 802.11k [4] draft
standard that standardizes radio information measurements
exchange amongst stations.
The next Section presents some channel selection related
works and Section III explains some important 802.11 interference
properties. Then, in Section IV, we present a brief
overview of the new 802.11k draft standard. Sections V and
VI present the proposed dynamic channel selection mechanism
and its performance evaluation, respectively. Finally, Section
VII draws the conclusions.
II. RELATED WORKS
Many other works have discussed the IEEE 802.11 channel
allocation problem [5–9]. However, most of them analyze
and propose solutions only to centralized scenarios. Solutions
utilizing graph-coloring techniques are the most adopted [5, 6,
8, 9]. Usually, this approach considers each AP as a vertex of
the network representing graph, and each potential interference
region between the BSSs (Basic Service Sets) (Figure 1) as
an edge.
Fig. 1. Example of BSSs disposed in a region and its representing graph.
Finding graph coloring solutions to 802.11 channel allocation
problem is, in general, a NP-hard problem [6, 8,
9]. Therefore, algorithms to find optimal solutions present
higher computational effort with larger networks. To face this
SBrT © 403
VI INTERNATIONAL TELECOMMUNICATIONS SYMPOSIUM (ITS2006), SEPTEMBER 3-6, 2006, FORTALEZA-CE, BRAZIL
limitation, the authors usually propose heuristics with low
computational costs that find suboptimal solutions. The main
difference between algorithms proposed for channel allocation
is the objective function, which indicates what the coloring
algorithms goal is.
The work [5] proposes a heuristic algorithm for graph
coloring that takes into account the traffic demand of each
BSS for the channel allocation. In [6], the authors proposed
a greedy coloring algorithm to find a channel allocation that
maximizes the number of neighbors with different channels.
Work [7] claims that AP placement and channel selection are
coupled problems and proposes a new technique to perform
this task.
To the best of our knowledge, [8] is the only previous
work to propose solution to channel allocation in decentralized
scenarios. They developed a new approach to the coloring
technique by setting weights to the edges of the interference
graph indicating the relevance of utilizing different channels
in the vertex connected by that edge. The edges weights are
a metric of the number of stations placed in the conflict
region that originated that edge. The BSSs’ client stations are
responsible for detecting the presence of other BSSs’ client
stations in interference region. They realize a passive scan
of the operating channels to sense packets destined to other
APs. The reason why client stations are responsible for this
task, and not the AP, is that they have a better view of the
interference scenario than the AP. Their proposed channel
selection mechanism operates in centralized or distributed
fashion.
The work in [8] was extended in [9], when the authors
discuss that the channel selection task can be coupled with load
balance. However, with this new increment the mechanism
focus deviate from the decentralized scenario where the client
stations cannot decide which AP it uses. Another channel
selection mechanism, cited in [8] and [9], is the LCCS (Least
Congested Channel Search). It is a mechanism implemented
at some CISCO APs that searches for another channel (with
less occupation) when others BSSs traffic exceeds a threshold.
The mechanism proposed in this paper resembles LCCS.
The most important differences are that it measures others
BSSs traffic at the client stations (which have a better picture
of interference than the AP) and it searches better channels
conditions proactively.
III. INTERFERENCE IN IEEE 802.11
Some points related to interference in 802.11 networks
needs discussion for completely understanding of the proposed
algorithm. Interference represents a problem in any wireless
communication system. However, in 802.11 networks it appears
in a slight different way, especially due to the medium
access mechanism adopted by 802.11.
With CSMA/CA, prior to transmitting a frame, a station
senses the medium idle for a small amount of time. If it
senses other stations’ transmission, it waits the end of their
transmission to start its own, avoiding a possible collision.
This feature makes CSMA/CA very robust to interference in
exchange to delay and throughput performance.
IEEE 802.11 transmissions generates three reception regions
where receiving stations behave differently [10]. The reception
zone, nearest to the transmitter, is where receiving stations
can notice and decode packets. The carrier sense zone is the
intermediate one, where receiving stations can only notice
packets transmissions due to energy levels but they cannot
be decoded. Moreover, at the interference zone, receiving
stations cannot notice packet transmissions but their energy
contribution is added to the noise floor as interference.
Fig. 2. CSMA/CA activity avoiding interference.
In Figure 2, when station (1) transmits, stations (2) and (3)
must wait the end of this transmission before starting another
one, sharing channel access with the station (1). Station (4),
which is outside the reception and carrier sense zones, does
not share medium access with station (1), but it suffers cochannel
interference generated by its transmissions.
The above example shows that packet decoding (at reception
zone) or carrier sense (at carrier sense zone) avoid concurrent
transmissions of stations inside each other’s reception
or carrier sense zone. The packet decoding makes it obtain
information about packet transmission duration (through a
field of 802.11 MAC header). Therefore, stations set the
NAV (Network Allocation Vector) that is an indicator counter
of transmissions ending. The carrier sense itself detects that
the medium is idle due to energy thresholds and avoids cochannel
interference generation. This way, CSMA/CA avoids
interference of near networks that are using the same channel.
However, it increases medium access contention through
medium access sharing.
As seen above, CSMA/CA particularities suggests that
channel selection mechanism must differently account for near
and far stations presence that increases medium access sharing
or noise levels, respectively. In our proposal, we utilize channel
load level and noise level to solve this problem.
IV. IEEE 802.11K STANDARD
The new 802.11k draft standard [4] specifies some types
of radio information and the respective messages to request
and report them. The main 802.11k objectives are to enable
specific radio features measurements by network stations,
standardize request/report messages to the exchange of these
measurements and make the gathered information available to
higher network layers. This standard development will offer
SBrT © 404
VI INTERNATIONAL TELECOMMUNICATIONS SYMPOSIUM (ITS2006), SEPTEMBER 3-6, 2006, FORTALEZA-CE, BRAZIL
useful management tools to network stations to provide useful
information to new protocols and mechanisms.
A. Radio Measurements
So far, the 802.11k draft standard specifies eight types of
radio measurements information. For the sake of brevity, we
present only the radio measurements used in this proposal.
• Channel Load Information: gather channel load information
in a specific number of channels in the measurement
duration. The sensing station obtains it by
dividing the amount of time the medium was idle by the
measurement duration. The sensing station may use NAV
or carrier sense to detect if the medium was idle.
• Noise Histogram: gives noise level histogram of noise
values collected in a specific number of channels in the
measurement duration. The sensing station makes noise
measurements only when the medium is idle.
A station can conduct measurements at its operating channel
or at non-serving channels1 and most of them may be
performed passively only by packet exchange observation,
without affecting network operation. However, non-serving
channels measurement may lead to performance degradation
since the sensing station needs to switch channels during
measurement and stay incapable of exchanging packets during
this period. The 802.11k standard recommends requesting only
short and spaced non-serving channel measurements.
A request option that can reduce overhead generated by nonserving
channels measuring is the concurrent measurement.
The sensing node may conduct most information measurement
concurrently, decreasing the information acquisition time and
the performance harm it generates. Another feature that can
reduce the impact of measuring non-serving channels is the
packet buffering technique, which is already used in 802.11
power saving mechanism, where the AP stores packets destined
to stations in power save mode. The stations could use
this technique when measuring non-serving channels.
B. Message Exchange
IEEE 802.11k standard defines two basic message types:
request and report messages. Stations may exchange these
messages in station-station or station-AP fashion. Besides, they
can send these messages in unicast, broadcast or multicast.
The message exchange occurs either by one station requesting
other station measurement information or by one station
reporting by itself its measured information.
Each request/report message is a MAC management frame
that has information about measurements settings, which advise
the sensing station about how to execute measurements
(channels, duration, start time, concurrency aspects, etc.). Each
information measurement contains one element per information
type that has the measurement information (in requests)
or the measurement results (in reports).
1Channels different of the operating channel used by the network.
V. DYNAMIC CHANNEL SELECTION
As discussed in Section III, a bad channel allocation may
increase medium access contention and co-channel interference.
Therefore, the channel selection algorithm proposed
needs to consider this information at the selection process.
To achieve this goal, we use the 802.11k standard to feed
APs channel selection algorithm with channel load and noise
levels. However, before presenting the algorithm, we present
some concerns about how to obtain these inputs.
A. Algorithm Inputs Acquisition
With the proposed mechanism, client stations are responsible
for conducting measurements. It is not desirable that the
AP itself do measurements because client stations have a much
better picture of potential interference problems than the AP
[8, 9]. Besides, making the AP switch channels periodically
would turn down all BSS communications simultaneously.
The selection algorithm implemented in the AP uses request
and report messages of the 802.11k standard in order to trigger
and collect measurements. The AP periodically sends request
messages to the client stations elected to perform the channels
sensing task. These stations should perform measurements
concurrently in all possible non-overlapping channels. Sensing
nodes’ election is an important step of the algorithm. We
propose realizing measurements in all client stations since this
generates a wide view of the interference problem.
The AP sends measurement requests to each station at a
random time within the algorithm execution window. Hence,
the algorithm will have reports from all client stations that it
manages at its execution and will use the mean values of the
reports received for load and noise levels.
One problem that should arise is the overhead generated
by each client measuring all channels in each algorithm
execution window. However, the overhead generated by this
measurement only becomes significant if the measurements
duration and periodicity are high. If these parameters are kept
low, the overhead generated will be negligible.
Once it has measurement results from all channels, the
channel selection algorithm starts its operation. The algorithm
reads two arrays, one with channel load values and
other with channel noise values. Each position carries the
averages of channel load or noise level of the channel it
represents. Obtaining each channel load value is a simple
average calculation of the values returned by the client station
reports. Obtaining noise average values, however, is not a
simple average calculation since these values are returned in
a histogram format (Figure 3). To obtain the average we used
equation 1.
Fig. 3. Histogram example: the letters represent the number of events at
each value range, and the numbers represent the average value of each range.
Average =
1 × a + 2 × b + 3 × c + 4 × d + 5 × e
a + b + c + d + e
(1)
SBrT © 405
VI INTERNATIONAL TELECOMMUNICATIONS SYMPOSIUM (ITS2006), SEPTEMBER 3-6, 2006, FORTALEZA-CE, BRAZIL
Note also that the channel load measurement should take
into account only the traffic generated by others BSS stations.
Otherwise, the AP can perform a channel switch when its own
traffic raises channel occupation.
B. Channel Selection Algorithm
As the priority of the algorithm is to minimize channel load,
it only considers noise levels of lightly loaded channels for
selecting an operating channel. The algorithm has three steps:
1) if the load of the current channel does not exceed a
certain threshold α, the current operating channel is
maintained and the algorithm is finished. Otherwise,
proceeds to step 2.
2) selects the N channels with the lowest load and proceeds
to step 3.
3) chooses among the N channels selected above the one
that presents the lowest noise level.
The α threshold, cited in the first step, works like an
aggressiveness adjust parameter, and indicates how much
channel load is tolerated at the operating channel. Only if
channel load exceeds the α parameter, the channel selection
mechanism perform the search for a better condition executing
steps two and three of the selection algorithm. This prevents
many undesirable channel switches due to other BSS control
traffic.
VI. SIMULATIONS
For the evaluation of the automatic channel selection mechanism
proposed, this work presents simulations with ns-22. The
main objective of these simulations is to evaluate the algorithm
parameters and the gains obtained with the channel selection
mechanism.
The simulations with ns-2 required the implementation of
new features not present at its original code. Firstly, we
implemented the channel occupation and noise measuring
mechanisms as specified in the 802.11k standard. Besides,
we also implemented all the co-channel noise calculation
in ns-2. Other key feature implemented is the ability of
switching channels during a simulation run. Moreover, in order
to simulate infrastructured networks, we used the NOAH3 (No
Ad-Hoc Routing Agent) module to avoid ad hoc routing traffic.
We fixed some parameters through the performed simulations.
Each BSS comprehends one AP along with three
client stations that generate one TCP flow each towards the
AP (uplink traffic). The physical transmission rate is set to
11 Mbps for data frames and 2 Mbps for control frames.
A. Channel Selection Interval
An important parameter of the proposed mechanism is the
channel selection interval. This parameter is a uniform random
variable of a given mean value. For each simulation scenario,
the mean value of the interval is varied from 20 seconds to
140 seconds, but keeping the same ratio between the mean
2The Network Simulator (ns-2) - http://www.isi.edu/nsnam/ns/
3NOAH - http://icapeople.epfl.ch/widmer/uwb/ns-2/noah/
value, its upper and lower limits and the simulation duration.
The uniform random variable limits are four times shorter than
the mean, and the simulation duration is five times higher.
The simulations that evaluate the selection interval comprehend
nine BSSs randomly disposed in a 2000-meter side
square area, the α parameter is set to 10%, the number of
non-overlapping channels to three and the channel measuring
time to 150ms. Fifty simulation runs for each selection interval
were used. All results presented below are the averaged values
of these runs with a 95% confidence interval.
32
33
34
35
36
37
38
39
40
20 40 60 80 100 120 140
Aggregate Throughput (Mbps)
Mean Selection Interval (seconds)
area=2000mx2000m, channels=3, BSSs=9, alpha=10%, sensing time=150ms
(a) Aggregate Throughput.
4
5
6
7
8
9
10
11
12
20 40 60 80 100 120 140
Average Channel Switches
Mean Selection Interval (seconds)
area=2000mx2000m, channels=3, BSSs=9, alpha=10%, sensing time=150ms
(b) Average Channel switches.
Fig. 4. Channel selection periodicity variation.
As it can be seen in Figure 4(a), the aggregate throughput
presents some slight performance degradation for shorter and
longer channel selection intervals. For shorter values, the harm
generated by the communication pause time, which has a fixed
value, increases. For longer channel selection intervals, the
information measured by sensing nodes are outdated and do
not reflect the real network interference picture, making the
channel selection algorithm to perform wrong channel choices.
Figure 4(b) presents the number of channel switches during
the simulation time. This value increases for short selection
intervals. This happens because, as with the aggregate throughput,
pauses in communication are more significant, affecting
the sensing task, which may return wrong values.
SBrT © 406
VI INTERNATIONAL TELECOMMUNICATIONS SYMPOSIUM (ITS2006), SEPTEMBER 3-6, 2006, FORTALEZA-CE, BRAZIL
From the results, we conclude that for the channel selection
interval a value about 60 seconds is the best choice for the
scenarios analyzed. Therefore, we will use this value as a base
to evaluate other algorithm parameters.