06-02-2013, 12:00 PM
Self-Reconfigurable Wireless Mesh Network
Self-Reconfigurable .docx (Size: 1.39 MB / Downloads: 39)
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 interferences from other coexisting wireless networks.
Even though many solutions for WMNs to recover from wireless link failures have been proposed, they still have several limitations as follows. First, resource-allocation algorithms[12]–[14] can provide (theoretical) guidelines for initial network resource planning. However, even though their approach provides a comprehensive and optimal network configuration plan, they often require “global” configuration changes, which are undesirable in case of frequent local link failures. Next, a greedy channel-assignment algorithm(e.g., [15]) can reduce the requirement of network changes by changing settings of only the faulty link(s). However, this greedy change might not able to realize full improvements,which can only be achieved by considering configurations of neighboring mesh router in additionto the faulty link(s). Third, fault-tolerant routing protocols, such as local rerouting [16] or multipath routing[17], can be adopted to use network-level path diversity for avoiding the faulty links. However, they rely on detour patho redundant transmissions, which may require more network resources than link-level network reconfiguration.
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 ofwireless links in WMNs can degrade (i.e., link-quality failure) due to severe interference from other collocated 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.
• Satisfying dynamic QoS demands:
Links in some areas may not be able to accommodate increasing QoS demands from end-users (QoS failures),2 depending on spatial or temporal locality [20]. For example, links around a conference room may have to relay too much data/video traffic during the session. Likewise, relay links outside the room may fail to support all attendees’ voice-over-IP calls during a session break. By reassociating their radios/channels with underutilized radios/channels available nearby, links can avoid communication failures.
• Coping with heterogeneous channel availability:
Links in some areas may not be able to access wireless channels during a certain time period (spectrum failures) due to spectrum etiquette or regulation [11], [21]. outperforms existing failure-recovery methods, such as static or1063-6692/$26.00 © 2010 IEEE394 IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 19, NO.APRIL 2011greedy channel assignments, and local rerouting. First, ARS’splanning algorithm effectively identifies reconfiguration plans that maximally satisfy the applications’ QoS demands, accommodating wice more flows than static assignment. Next, ARS avoids the ripple effect via QoS-aware reconfiguration planning, unlike the greedy approach. Third, ARS’s local reconfiguration improves network throughput and channel efficiency by more than 26% and 92%, respectively, over the local rerouting scheme.The rest of this paper is organized as follows. Section II describe the motivation behind this work. Section III provides the design rationale and algorithms of ARS. Section IV describes the implementation and experimentation results on ARS.Section V shows in-d epth simulation results of ARS.
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 hannel 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.
Next, the greedy channel-assignment algorithm, which considers only local areas in channel assignments (e.g., [15]), might do better in reducing the scope of network changes than the above-mentioned assignment algorithms. However, this approach still suffers from the ripple effect, in which one local change triggers the change of additional network settings at neighboring nodes (e.g., nodes using channel 3 in Fig. 2) due to association dependency among neighboring radios. This undesired effect might be avoided by transforming a mesh topology into a tree topology, but this transformation reduces network connectivity as well as path diversity among mesh nodes.
QoS-Awareness:
Reconfiguration has to satisfy QoS constraints on each link as much as possible. First, given eachlink’s bandwidth constraints, existing channel-assignment and scheduling algorithms [5], [12], [13] can provide approximately optimal network configurations. However, as pointed out earlier, these algorithms may require global network configuration changes from changing local QoS demands, thus causing network disruptions.We need instead a reconfiguration algorithm that incurs only local changes while maximizing the chance of meeting the QoS demands. For example, if link EH in Fig. 2 experiences a QoS failure on channel 1, then one simple reconfiguration plan would be to reassociate R1 of node H to R2 of node E in channel 5, which has enough bandwidth.
Cross-Layer Interaction:
Network reconfiguration has to jointly consider network settings across multiple layers. In the network layer, fault-tolerant routing protocols, such as [16] or multipath routing [17], allow for flow reconfiguration to meet the QoS constraints by exploiting path diversity. However, they consume more network resources than link reconfiguration because of their reliance on detour paths or redundant transmissions. existing networks that operate in the same channel.nal channels as closely as possible geographically.