18-01-2013, 01:00 PM
Self-Reconfigurable Wireless Mesh Networks
1Self-Reconfigurable.pdf (Size: 966.18 KB / Downloads: 93)
Abstract
During their lifetime, multihop wireless mesh networks
(WMNs) experience frequent link failures caused by
channel interference, dynamic obstacles, and/or applications’
bandwidth demands. These failures cause severe performance
degradation in WMNs or require expensive manual network
management for their real-time recovery. This paper presents an
autonomous network reconfiguration system (ARS) that enables
a multiradio WMN to autonomously recover from local link
failures to preserve network performance. By using channel and
radio diversities in WMNs, ARS generates necessary changes in
local radio and channel assignments in order to recover from
failures. Next, based on the thus-generated configuration changes,
the system cooperatively reconfigures network settings among
local mesh routers. ARS has been implemented and evaluated
extensively on our IEEE 802.11-based WMN test-bed as well as
through ns2-based simulation. Our evaluation results show that
ARS outperforms existing failure-recovery schemes in improving
channel-efficiency by more than 90% and in the ability of meeting
the applications’ bandwidth demands by an average of 200%.
INTRODUCTION
WIRELESS mesh networks (WMNs) are being developed
actively and deployed widely for a variety of
applications, such as public safety, environment monitoring,
and citywide wireless Internet services [1]–[3]. They have also
been evolving in various forms (e.g., using multiradio/channel
systems [4]–[7]) to meet the increasing capacity demands
by the above-mentioned and other emerging applications.
However, due to heterogeneous and fluctuating wireless link
conditions [8]–[10], preserving the required performance of
such WMNs is still a challenging problem. For example, some
links of a WMN may experience significant channel interference
from other coexisting wireless networks. Some parts
of networks might not be able to meet increasing bandwidth
demands from new mobile users and applications.
MOTIVATION
We first describe the need for self-reconfigurable mr-WMNs.
Next, we introduce the network model and assumptions to be
used in this paper. Finally, we discuss the limitations of existing
approaches to achieving self-reconfigurability of mr-WMNs.
A. Why Is Self-Reconfigurability Necessary?
Maintaining the performance of WMNs in the face of dynamic
link failures remains a challenging problem [18]. However,
such failures can be withstood (hence maintaining the required
performance) by enabling mr-WMNs to autonomously
reconfigure channels and radio1 assignments, as in the following
examples.
• Recovering from link-quality degradation: The quality of
wireless links in WMNs can degrade (i.e., link-quality
failure) due to severe interference from other colocated
wireless networks [8], [19]. For example, Bluetooth,
cordless phones, and other coexisting wireless networks
operating on the same or adjacent channels cause significant
and varying degrees of losses or collisions in packet
transmissions, as shown in Fig. 1. By switching the tuned
channel of a link to other interference-free channels, local
links can recover from such a link failure.
Network Model and Assumptions
Multiradio WMN: A network is assumed to consist of mesh
nodes, IEEE 802.11-based wireless links, and one control
gateway. Each mesh node is equipped with radios, and
each radio’s channel and link assignments are initially made
(e.g., see Fig. 2) by using global channel/link assignment
algorithms [5], [12], [13]. Multiple orthogonal channels are
assumed available. For example, an IEEE 802.11a/b/g combo
PCMCIA card can tune 16 orthogonal channels. The interference
among multiple radios in one node is assumed to be
negligible via physical separation among antennas or by using
shields. The gateway is connected to the Internet via wire-line
links as well as to other mesh routers via wireless links.
Limitations of Existing Approaches
Given the above system models, we now discuss the pros
and cons of using existing approaches for self-reconfigurable
WMNs.
Localized Reconfiguration: Network reconfiguration needs
a planning algorithm that keeps necessary network changes
(to recover from link failures) as local as possible, as opposed
to changing the entire network settings. Existing channel assignment
and scheduling algorithms [12]–[14] provide holistic
guidelines such as throughput bounds and schedulability for
channel assignment during a network deployment stage. However,
the algorithms do not consider the degree of configuration
changes from previous network settings, and hence they often
require global network changes to meet all the constraints, akin
to edge coloring problems [27]. Even though these algorithms
are suitable for static or periodic network planning, they may
cause network service disruption, and thus are unsuitable for
dynamic network reconfiguration that has to deal with frequent
local link failures.
Planning for Localized Network Reconfiguration
The core function of ARS is to systematically generate localized
reconfiguration plans. A reconfiguration plan is defined as
a set of links’ configuration changes (e.g., channel switch, link
association) necessary for a network to recover from a link(s)
failure on a channel, and there are usually multiple reconfiguration
plans for each link failure. Existing channel-assignment and
scheduling algorithms [5], [12], [13] seek “optimal” solutions
by considering tight QoS constraints on all links, thus requiring
a large configuration space to be searched and hence making the
planning often an NP-complete problem [5]. In addition, change
in a link’s requirement may lead to completely different network
configurations. By contrast, ARS systematically generates reconfiguration
plans that localize network changes by dividing
the reconfiguration planning into three processes—feasibility,
QoS satisfiability, and optimality—and applying different levels
of constraints. As depicted in Fig. 3, ARS first applies connectivity
constraints to generate a set of feasible reconfiguration
plans that enumerate feasible channel, link, and route changes
around the faulty areas, given connectivity and link-failure constraints.
Then, within the set, ARS applies strict constraints (i.e.,
QoS and network utilization) to identify a reconfiguration plan
that satisfies the QoS demands and that improves network utilization
most.
Complexity of ARS
Thanks to its distributed and localized design, ARS incurs
reasonable bandwidth and computation overheads. First, the
network monitoring part in the reconfiguration protocols is
made highly efficient by exploiting existing data traffic and
consumes less than 12 kb/s probing bandwidth (i.e., one packet
per second) for each radio. In addition, the group formation
requires only message overhead (in forming a spanning
tree), where is the number of nodes in the group. Next,
the computational overhead in ARS mainly stems from the
planning algorithms. Specifically, generating its possible link
plans incurs complexity, where is the number
of available channels and the number of radios. Next, a
gateway node needs to generate and evaluate feasible plans,
which incurs search overhead in a constraint graph that consists
of nodes, where is the number of links that use
a faulty channel in the group.
Implementation Details
Fig. 7(a) shows the software architecture of ARS. First, ARS
in the network layer is implemented using netfilter [32], which
provides ARS with a hook to capture and send ARS-related
packets such as group-formation messages. In addition, this
module includes several important algorithms and protocols
of ARS: 1) network planner, which generates reconfiguration
plans only in a gateway node; 2) group organizer, which
forms a local group among mesh routers; 3) failure detector,
which periodically interacts with a network monitor in the
device driver and maintains an up-to-date link-state table;
and 4) routing table manager, through which ARS obtains or
updates states of a system routing table
Future Work
Joint OptimizationWith Flow Assignment and Routing: ARS
decouples network reconfiguration from flow assignment and
routing. Reconfiguration might be able to achieve better performance
if two problems are jointly considered. Even though there
have been a couple of proposals to solve this problem [5], [12],
they only provide theoretical bounds without considering practical
system issues. Even though its design goal is to recover
from network failures as a best-effort service, ARS is the first
step to solve this optimization problem, which we will address
in a forthcoming paper.
Use of ARS in IEEE 802.11 b/g WMNs: ARS is mainly evaluated
in IEEE 802.11a networks, where 13 orthogonal channels
are available. However, ARS can also be effective in a network
with a small number of orthogonal channels (e.g., three in IEEE
802.11b/g). Because ARS includes a link-association primitive,
it can learn available channel capacity by associating with idle
interfaces of neighboring nodes, and it further limits the range
of a reconfiguration group (e.g., nodes within 4 hops).
CONCLUSION
We first make concluding remarks and then discuss some future
work.
A. Concluding Remarks
This paper presented an autonomous network reconfiguration
system (ARS) that enables a multiradioWMN to autonomously
recover from wireless link failures. ARS generates an effective
reconfiguration plan that requires only local network configuration
changes by exploiting channel, radio, and path diversity.