02-05-2014, 11:44 AM
A Traffic-Aware Channel and Rate Re-Assignment Algorithm for Wireless Mesh Networks
A Traffic-Aware Channel .pdf (Size: 656.6 KB / Downloads: 21)
Abstract
Channel assignment is among the most challenging issues for multi-radio wireless mesh networks, given the variety of
objectives that can be pursued and the computational complexity of the resulting problems. The channel assignment problem has been
also shown to be inter-dependent with the routing problem, i.e., the problem to determine the amount of traffic flow to be routed on
every link. Such a relationship raises the need to re-compute the channel assignment every time the traffic pattern changes. However,
channel assignment algorithms designed to assign channels from scratch will likely return a completely different configuration of radios,
which would disrupt the network operation for the time required to switch to using the links established on the new channels. As shown
by the experiments we conducted, such a time may not be negligible, due to the resistance of routing protocols designed for wireless
ad hoc and mesh networks to rapidly flagging a link as established/lost. Such a consideration, along with the observation that channel
assignment algorithms may be sub-optimal, led us to the design of a channel re-assignment algorithm that takes the current channel
assignment into account and attempts to cope with the new traffic pattern in the best manner possible while modifying the channel on
a limited number of radios. In this paper, we illustrate such a channel re-assignment algorithm and evaluate its performance by means
of both simulations and experiments with real hardware.
INTRODUCTION
SINCE their introduction, wireless mesh networks
(WMNs) have attracted a lot of interest from both the
international research community and industries. Such
an interest from industries is due to the possibility to
cover metropolitan areas without a wired infrastructure,
which makes WMNs a cost effective solution to imple-
ment, for instance, Wireless ISPs. Researchers, instead,
have been attracted by the challenging issues related to
the configuration and management of WMNs. One of
such issues is the assignment of channels to radios in
case mesh routers are equipped with multiple radios.
The multi-radio configuration is becoming increasingly
common, as routers may exploit the availability of multi-
ple radios to simultaneously transmit and/or receive on
different channels. Consequently, it is possible to reduce
the interference and increase the throughput by carefully
planning the assignment of channels to radios.
R ELATED
WORK
The channel assignment problem in multi-radio WMNs
has been investigated in the literature recently. Many
proposals aim to minimize some network-wide measure
of interference and do not study the channel assignment
problem in conjunction with the routing problem. For
instance, in [3] the goal is to find a channel assignment
which minimizes the size of the largest collision domain
subject to the constraint that the induced graph must still
be K-connected. A centralized algorithm is presented
in [4] which also takes the traffic generated by mesh
clients into account. In [5], an interference-free channel
assignment is sought by using superimposed codes.
MesTiC [6] is a rank-based channel assignment, where
the rank of a node is a function of its aggregate traffic,
its number of hops from the gateway and its number of
radio interfaces. In [7], both centralized and distributed
algorithms are presented, which aim to minimize the
number of pairs of links that are interfering. A dis-
tributed channel assignment algorithm and a distributed
routing protocol are proposed in [8]. Dhananjay et al. [9]
present a distributed protocol for channel assignment
and routing in dual-radio mesh networks.
PERFORMANCE E VALUATION
In this section we present the results of the simulation
study and the experiments we carried out to evaluate
the performance of MVCRA-R algorithm. The goal of the
simulation study is to show that updating the network
configuration by running MVCRA-R allows to increase
the network throughput with respect to both leaving
the channel assignment unchanged and updating the
network configuration by running a channel assignment
algorithm that ignores the current configuration. We
remark that we do not simulate the transient stage
when radios switch channels (results may be affected by
inaccuracies in the simulator). Instead, simulations start
from the new network configuration determined by the
channel (re-)assignment algorithms. Thus, simulations
aim at evaluating the throughput in the long term.
The experiments we conducted with real hardware,
instead, aim to gain some insight into the effects of
switching channels. We show that a large number of
simultaneous channel switches severely impacts the net-
work performance, thus justifying our objective of lim-
iting the number of channel switches.
CONCLUSIONS
In this paper we presented the Minimum Variation
Channel and Rate Re-Assignment (MVCRA-R) algo-
rithm, which takes the current channel assignment and
the new set of flow rates into account and attempts
to minimize the maximum total utilization over all
the collision domains while constraining the number
of radios that can be assigned a new channel. With
respect to MVCRA, MVCRA-R leverages the possibil-
ity to adjust the link transmission rates and presents
some enhancements such as an improved definition of
the link priorities. We performed extensive simulation
studies that confirmed that MVCRA-R roughly meets
the constraint on the maximum allowed number of
radio changes and outperforms both MVCRA and a
channel assignment algorithm such as FCRA in terms
of maximum total utilization and network throughput.