9512.net
甜梦文库
当前位置:首页 >> >>

Interference-aware topology control and qos routing in multi-channel wireless mesh networks


Interference-Aware Topology Control and QoS Routing in Multi-Channel Wireless Mesh Networks
?

Jian Tang, Guoliang Xue and Weiyi Zhang Department of Computer Science and Engineering Arizona State University Tempe, AZ 85287-8809, USA. {jian.tang, xue, weiyi.zhang}@asu.edu. ABSTRACT
The throughput of wireless networks can be signi?cantly improved by multi-channel communications compared with single-channel communications since the use of multiple channels can reduce interference in?uence. In this paper, we study interference-aware topology control and QoS routing in IEEE 802.11-based multi-channel wireless mesh networks with dynamic tra?c. Channel assignment and routing are two basic issues in such networks. Di?erent channel assignments can lead to di?erent network topologies. We present a novel de?nition of co-channel interference. Based on this concept, we formally de?ne and present an e?ective heuristic for the minimum INterference Survivable Topology Control (INSTC) problem which seeks a channel assignment for the given network such that the induced network topology is interference-minimum among all K-connected topologies. We then formulate the Bandwidth-Aware Routing (BAR) problem for a given network topology, which seeks routes for QoS connection requests with bandwidth requirements. We present a polynomial time optimal algorithm to solve the BAR problem under the assumption that tra?c demands are splittable. For the non-splittable case, we present a maximum bottleneck capacity path routing heuristic. Simulation results show that compared with the simple common channel assignment and shortest path routing approach, our scheme improves the system performance by 57% on average in terms of connection blocking ratio.

General Terms
Algorithm, Design, Performance

Keywords
Wireless Mesh Network, QoS Routing, Topology Control, Channel Assignment.

1.

INTRODUCTION

Categories and Subject Descriptors
C.2.1 [Computer-Communication Networks]: Network Architecture and Design - Wireless Communication
? Research supported in part by ARO grant W911NF-041-0385 and NSF grant CCF-0431167. The information reported here does not re?ect the position or the policy of the federal government.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for pro?t or commercial advantage and that copies bear this notice and the full citation on the ?rst page. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior speci?c permission and/or a fee. MobiHoc’05, May 25–27, 2005, Urbana-Champaign, Illinois, USA. Copyright 2005 ACM 1-59593-004-3/05/0005 ...$5.00.

A wireless mesh network ([1, 21, 22]) is a multihop wireless network consisting of a large number of wireless nodes, some of which are called gateway nodes and connected with a wired network. It has attracted much research attention due to its potential applications, including last-mile broadband Internet access, neighborhood gaming, Video-onDemand (VoD), distributed ?le backup, video surveillance and so on ([3]). Due to the limited channel capacity, the in?uence of interference, the large number of users and the emergence of real-time multimedia applications, improving network throughput and supporting QoS have become two critical requirements in such networks. Using multiple channels instead of a single channel in multihop wireless networks has been shown to be able to improve the network throughput dramatically ([21, 22]). The IEEE 802.11b standard and IEEE 802.11a standard ([12, 13]) o?er 3 and 12 non-overlapping channels respectively. We consider a multi-channel wireless mesh network, in which every node is equipped with multiple Network Interface Cards (NICs) and each of them can be tuned to one of the available channels. A pair of NICs can communicate with each other if they are on the same channel and are within the transmission range of each other. The throughput improvement in such networks is brought mainly by allowing multiple simultaneous transmissions within a neighborhood. In a single channel wireless network, two transmissions in a neighborhood are not allowed to happen at the same time because of contention for the shared wireless channel. However, in a multi-channel network, no collision will be caused by such simultaneous transmissions as long as they work on di?erent channels. QoS routing in multihop wireless networks is very challenging due to interference among di?erent transmissions. Even in a multi-channel wireless network, interference still exists since two transmissions may interfere with each other if they are using the same channel. A QoS connection request usually comes with a bandwidth requirement and QoS routing seeks a source to destination route with requested

68

bandwidth. If no such route can be found, the connection request should be blocked. In order to solve the QoS routing problem in multihop wireless networks, we need to consider two types of contentions: inter-?ow contention and intra?ow contention ([26]). Suppose P is a candidate route for the current connection request. Inter-?ow contentions are the contentions caused by the interference between a wireless link on P and a wireless link which is not on P and used by existing connection requests. Intra-?ow contentions are the contentions caused by the interference between a wireless link on P and another wireless link on P . Intra-?ow contentions are very hard to determine during the phase of route discovery since the route is still unknown at that time. To our best knowledge, this is the ?rst paper addressing QoS provisioning in an IEEE 802.11-based multi-channel wireless mesh network. We study a wireless mesh network with dynamic tra?c, i.e., connection demands have random sources, destinations and arrival times, without assuming all tra?c demands are given a priori by a tra?c pro?le as in [21, 22]. We believe that this dynamic tra?c model is more useful in reality because considering the aforementioned applications in the future, we should expect not only some tra?c from wireless nodes to Internet via gateway nodes but also substantial random and unpredictable tra?c among wireless nodes within the mesh network. It is hard to precisely predict the tra?c demands in advance. How to assign channel for each NIC and how to route tra?c are two basic issues in such networks. For channel assignment, we adopt a static assignment scheme ([21, 22]), i.e., assigning channels for each NICs before connection requests arrive and keep the computed assignment for a long period of time. Changes or adjustments will only be made if a set of new nodes are added or some nodes fail. The dynamic scheme, i.e., assigning channels for NICs in route discovery and allowing channel switching during packet transmissions, is not very suitable for wireless mesh networks. Because dynamic assignment may cause the deafness problem (transmitter and intended receiver happen to be on di?erent channels) and need ?ne grained synchronization ([15, 24]). In [15], the authors propose a hybrid channel assignment method to solve the above problems, which assigns one NIC of each node statically to a common control channel, and allows other interfaces dynamically switch among other data channels. However, this method will hold back the throughput improvement, especially for the case in which the number of NICs in each node is very small. Moreover, the channel switching delay of current commercial IEEE 802.11 hardware is in the range of a few milliseconds to a few hundred microseconds ([15]), which is intolerable for most real-time multimedia applications. Once a channel assignment is given, the network topology can be determined. Intuitively speaking, we want the channels assigned to the NICs in a common neighborhood to be as di?erent as possible such that interference can be reduced. In addition, we need to preserve the network connectivity and support survivability. In this paper, we ?rst present a novel de?nition of cochannel interference which can capture the impact of interference precisely. Based on this de?nition and by fully considering both interference and connectivity, we de?ne the minimum INterference Survivable Topology Control (INSTC) problem which seeks a channel assignment for the given network such that the induced network topology is interference-minimum among all K-connected topologies. K-

connectivity is required for survivability and load-balancing purposes. We assume the transmission power of each NIC is ?xed. So the topology control problem studied here is quite di?erent from all previous topology control problems ([7, 19]) in which the network topology is controlled by carefully adjusting the transmission power at each node. We present an e?ective heuristic for the INSTC problem which guarantees that the topology is K-connected to enhance survivability. In the second part of the paper, we fully exploit the in?uence of intra-?ow and inter-?ow contentions for the multihop QoS routing which has not been well addressed before, especially under the scenario of multi-channel multiNIC multihop wireless networks. We present an optimal LP-based polynomial time QoS routing algorithm for the given network topology to solve the formulated BandwidthAware Routing (BAR) problem by assuming that the tra?c demands are splittable. We also present an e?ective maximum bottleneck capacity path heuristic without assuming the splittability. Like the other higher layer solutions proposed in [15, 21, 22], our scheme can be used without making any change on IEEE 802.11 DCF. The rest of this paper is organized as follows. We discuss related work in Section 2. We describe the system model and formally de?ne the problems in Section 3. We present our interference-aware topology control scheme and QoS routing algorithms in Section 4 and Section 5, respectively. Simulation results are presented in Section 6. We conclude the paper in Section 7.

2.

RELATED WORK

Recently, people begin to study multi-channel multihop wireless networks, such as multi-channel wireless mesh networks and multi-channel Mobile Ad hoc NETwork (MANET), since network throughput can be substantially improved by making full use of the non-overlapping channels. In [22], the authors propose and evaluate one of the ?rst IEEE 802.11based multi-channel multi-hop wireless mesh network architectures. They develop a set of centralized algorithms for channel assignment, bandwidth allocation, and routing. They also present distributed algorithms utilizing only local tra?c load information to dynamically assign channels and to route packets in a later paper [21]. Draves et al. in [8] present a new metric named Expected Transmission Time/Weighted Cumulative ETT (ETT/WCETT), for multiradio, multihop wireless networks which can be used for ?nding a high-throughput path between a source and a destination. They also present a Multi-Radio Link-Quality Source Routing (MR-LQSR) protocol by incorporating this metric. In [15], the authors propose algorithms for channel assignment and routing in multi-channel multi-NIC MANETs. Vaidya et al. ([24]) also present a routing protocol for the scenario in which each node only has one NIC. Besides routing protocols, several link layer and MAC layer solutions have also been proposed for multi-channel multihop wireless networks in [2, 5, 23]. We note that previously proposed channel assignment schemes ([21, 22]) are not suitable for the dynamic tra?c model here since no tra?c demand pro?le is available as the guideline for channel assignment. Moreover, they do not guarantee K-connectivity. In addition, none of previously known routing schemes can support QoS routing with bandwidth requirements in a 802.11-based multi-channel wireless network. QoS routing in single channel MANETs has been well

69

studied in the literature. Perkins et al. have extended the basic Ad hoc On-Demand distance Vector (AODV) routing protocol to support QoS [20]. Formats of packets, such as route request (RREQ) packet or route reply (RREP) packet, are modi?ed to specify the service requirements which must be satis?ed by the forwarding nodes. Xue and Ganz in [25] introduce a resource reservation-based routing and signaling algorithm named Ad hoc QoS on-demand routing (AQOR), which provides end-to-end QoS support in terms of both bandwidth and end-to-end delay, in IEEE 802.11-based MANETs. Several QoS routing protocols ([16, 17, 18, 27]) have been proposed under the assumption of a TDMA or TDMAover-CDMA MAC layer. The authors of [10] consider bandwidth as the QoS parameter in TDMA-based wireless ad hoc networks with limited energy resources. A constraint model for the QoS-aware Minimum Energy Multicast (QoS-MEM) problem in terms of Integer Linear Programming (ILP) is presented. Recent research has shown that interference can make a signi?cant impact on the performance of a wireless network. As a pioneering work, Gupta and Kumar in [11] show that in a wireless network with n identical nodes, the √ per-node throughput is Θ(1/ n log n) by assuming random node √ placement and communication pattern. It becomes Θ(1/ n) under the assumption of optimal node placement and communication pattern. In [14], the authors model the in?uence of interference using a con?ict graph and derive upper and lower bounds on the optimal throughput. Burkhart et al. give a concise and intuitive de?nition of interference in [7]. Based on this de?nition, they show that most currently proposed topology control algorithms do not e?ectively constrain interference. They propose algorithms to compute interference-optimal connected subgraphs and spanners. In [19], the authors extend results from [7] and present algorithms for constructing a network topology in wireless ad hoc networks such that the maximum (or average) link (or node) interference of the topology is either minimized or approximately minimized. In [26], the authors present a framework for multihop packet scheduling to achieve maximum throughput by considering the in?uence of intra-?ow and inter-?ow contentions.

wireless node in the network with its location known. By abusing the notation a little bit without confusion, we also use v to denote its corresponding wireless node, or even the location of its corresponding wireless node. There is an undirected edge (u, v) ∈ E connecting vertex u and vertex v if d(u, v) ≤ r, where d(u, v) is the Euclidean distance between u and v. The edge (u, v) in G corresponds to a wireless link between nodes u and v in the wireless network. The use of undirected links re?ects the fact that the IEEE 802.11 DCF requires the sender to be able to receive a link layer acknowledgment message from the receiver for every transmitted data packet. Throughout this paper, we will use vertices and nodes interchangeably, as well as edges and links. A channel assignment A assigns each node v ∈ V a set A(v) of Q di?erent channels: A(v) ? {1, 2, . . . , C}. The channels in A(v) correspond to the Q di?erent channels that the Q NICs at node v are tuned to. A channel assignment A de?nes a topology GA (V, EA ) in the following natural way: There is an edge e = (u, v; k) on channel λ(e) = k between nodes u and v in GA if and only if d(u, v) ≤ r and λ(e) ∈ A(u) A(v). Note that GA may be a multi-graph, i.e., a graph including multiple edges between the same pair of nodes, because a pair of nodes may share two or more channels. An example of channel assignment and its corresponding topology is given in Figure 1, where C = 3 and Q = 2. The label associated with each node indicates the channels assigned to that node. The label associated with each edge indicates the channel shared by the nodes incident with that edge. Note that the pair of nodes A and B share two channels. Therefore there are two edges connecting vertices A and B in the corresponding topology, one on channel 1 and the other on channel 2.

{2,3} C

3

2

3. PROBLEM DEFINITION
In this section, we will ?rst describe our system model and notations. Then, we will formally de?ne the optimization problems we are going to study. We use a similar network model as described in [21, 22]. The IEEE 802.11 Distributed Coordination Function (DCF) ([12]) is assumed to be used to handle multiple access in the MAC layer. There are totally C non-overlapping frequency channels in the system and each node is equipped with Q NICs where Q ≤ C. In order to e?ciently and fully make use of the network resources, we assume that each NIC is tuned to a channel and that any two NICs at the same node are tuned to di?erent channels. All nodes in the network use the same ?xed transmission power, i.e, there is a ?xed transmission range (r > 0) and a ?xed interference range R > r (which is typically 2 to 3 times of r [21]) associated with every node. We also assume that all wireless nodes are stationary. We use an undirected graph G(V, E) to model the wireless mesh network where V is the set of n vertices and E is the set of m edges. Each vertex v ∈ V corresponds to a

{1,2} A 1 2 B {1,2}

E
1

1

D {1,2}

{1,3}

1

GA

Figure 1: Network topology given by a channel assignment Half-duplex operation is enforced for each NIC to prevent self-interference, i.e., one NIC can only transmit or receive at one time. However, while one NIC at a node v is transmitting/receiving data on one channel, another NIC at node v can simultaneously transmit/receive data on a di?erent channel. Due to the broadcast transmission nature of the radio and the ?xed transmission power, we can imagine that

70

associated with each node u, there is a disk Du centered at u with radius R (the interference disk). Without confusion, we will also use Du to denote the set of nodes covered by this disk. It follows from the de?nition that for any pair of wireless nodes u and v, v ∈ Du implies u ∈ Dv , and vice versa. Assume that u, v, x, y are wireless nodes such that d(u, v) ≤ r and d(x, y) ≤ r. If node x or node y are covered by one of the interference disks at u and v (correspondingly, node u or node v must be covered by one of the interference disks at x and v) and that there is a channel k ∈ A(u) A(v) A(x) A(y), then the link e = (u, v; k) on channel λ(e) = k interferes with the link e = (x, y; k) on channel λ(e ) = k, since simultaneous transmissions along (u, v; k) and (x, y; k) (using channel k) will lead to collision. This de?nition of link interference also includes the cases where the two links share a common node and the case where e and e are identical (the notion that a link interferes with itself is a technical agreement that simpli?es the notations later). In Figure 2, link (A, B; 2) interferes with link (C, D; 2). Let e be a link in GA . We will use IEe to denote the set of links in GA that interferes with link e.
C 2 D

In order to ensure the existence of a K-connected topology GA , the original network G must be K-connected. Now we switch our attention to the routing problem. In this paper, we study symmetric communication. The bandwidth requirement in a connection request indicates the total bandwidth required for the communication in both directions. As discussed in Section 1, the intra-?ow contention complicates the bandwidth computation. Instead of seeking a single routing path, we compute a splittable ?ow allocation. Speci?cally, f (e, ρ) is used to denote the bandwidth to be allocated on link e for connection ρ. The splittable ?ow approach enables us to compute a route with required bandwidth in polynomial time in a multihop wireless network. We need to compute the available bandwidth on each wireless link in the given topology when establishing a connection. Let CAP (e) be the (physical) capacity of link e, which is usually a ?xed value, e.g. CAP (e) = 11(M bps), ?e ∈ EA if IEEE 802.11b is used. Definition 3 (Available Bandwidth). The Link Load of e ∈ GA , denoted by L(e), is the sum of the bandwidth allocations of all the existing connections that use link e: L(e) = ρ is an existing connection f (e, ρ). The Available Bandwidth of link e ∈ GA , denoted by A(e), is CAP (e) ? e ∈IEe L(e ). In our de?nition of link interference, we have adopted the notion that IEe contains e itself. This notion is used in the above de?nition. We note that the above method for computing available bandwidth is a worst-case computation. Suppose that links e1 and e2 both interfere with link e, but do not interfere with each other. Then traf?c on e1 and e2 may be transmitted simultaneously using IEEE 802.11 DCF. In this case, the available bandwidth on link e is actually larger than the value computed based on De?nition 3. Therefore A(e) is a lower bound for the actual available bandwidth. This bound is tight because it is achievable in the worst case. The de?ned computation method is necessary to provide required bandwidth for each QoS connection demand. Here, we need not only to allocate enough bandwidth for the incoming connection request, but also to make sure that the bandwidth allocated for existing connections is not a?ected. Some previous QoS routing papers such as [25] employ similar computation methods. Definition 4 (BAR Problem). Let there be some existing connections on the topology GA induced by a given channel assignment A. Let ρ be a new connection request with source node s, destination node t, and bandwidth requirement B. The Bandwidth-Aware Routing (BAR) problem seeks a ?ow allocation F such that the total s–t ?ow is equal to B and that e ∈IEe f (e , ρ) ≤ A(e), ?e ∈ GA . If such a ?ow allocation can be found, the connection request ρ will be admitted and the available bandwidth will be updated on related links accordingly. Otherwise, the connection request will be blocked.

R

A

2

B

Figure 2: Link (A, B; 2) interferes with link (C, D; 2). As discussed earlier in this section, a channel assignment de?nes a corresponding topology. It is desirable to have a channel assignment whose corresponding topology has relatively low interference. We formalize interference-aware topology control and related concepts in the following. Definition 1 (Co-Channel Interference). Let a channel assignment A and its corresponding network topology GA be given. Let e be any link in GA . The Link CoChannel Interference of link e, denoted by I(e), is |IEe |. The Topology Co-Channel Interference of GA , denoted by I(GA ), is maxe∈GA I(e). Definition 2 (INSTC Problem). Given the network G and an integer K, the minimum INterference Survivable Topology Control (INSTC) problem seeks a channel assignment A such that the corresponding network topology GA is K-connected and has the minimum topology cochannel interference among all K-connected topologies induced by channel assignments.

4.

INTERFERENCE–AWARE TOPOLOGY CONTROL

In this section, we will present an e?ective heuristic for the INSTC problem de?ned in the previous section. We say link (u, v) ∈ G and link (x, y) ∈ G potentially interfere with each other if x ∈ Du Dv or y ∈ Du Dv .

71

Note again that this condition implies u ∈ Dx Dy or v ∈ Dx Dy . So the concept of link potential interference is symmetric. We need this concept because our topology control algorithm tries to ?nd a channel assignment (before a channel assignment is known, the actual interference of links are unknown). Therefore the previous de?nition for co-channel interference cannot be employed here. Similarly, we use P Ee to denote the set of links in G that potentially interfere with link e ∈ G. We need the following de?nition. Definition 5 (Link Potential Interference). Let e be any link in G. The Link Potential Interference (LPI) of e, denoted by IP (e), is |P Ee |. Our topology control algorithm is formally presented as Algorithm 1. In the algorithm, we try to compute the channel assignment for the nodes by going through the edges in a K-connected subgraph of the network in a non-increasing order of link potential interference values. Algorithm 1 Interference-aware topology control Step 1 Use binary search on all LPIs to ?nd the smallest min possible LPI, IP and a subgraph of G, G (V, E ) such that G is K-connected and includes all links min whose LPI is at most IP . Step 2 Initialize A(u) to ? for all u ∈ V . Select the link in G one by one in a descending order of LPIs. Update the channel assignment for nodes u and v corresponding to link e = (u, v) ∈ G based on the following rules: 1. If A(u) A(v) = ?, then do nothing.

2. If A(u) A(v) = ? but |A(u)| < Q and |A(v)| < Q, then A(u) := A(u) {k}, A(v) := A(v) {k}, where k is the least used channel in P Ee . 3. If A(u) A(v) = ?, but |A(u)| < Q and |A(v)| = Q, then A(u) := A(u) {k}, where k is the least used channel in P Ee among channels in A(v). 4. If A(u) A(v) = ?, |A(u)| = |A(v)| = Q, let k be the least used channel in P Ee among channels in A(u) A(v). Without loss of generality, assume that k ∈ A(u). Let k = k be an channel in A(v) that is most used in P Ee . Replace k in A(v) by k. For all the edges (v, w) already considered for which the change of A(v) makes A(v) A(w) = ? (this implies k ∈ A(w)), replace k in A(w) by k. This replacement may be performed recursively. Step 3 Assign nodes having unassigned NICs with the least used channels among assigned channels from their neighboring nodes.

Proof. The induced topology GA based on the node channel assignment A computed by Algorithm 1 must be Kconnected, because we will obtain a K-connected topology G (V, E ) after running Step 1. In Step 2, the edges in G are checked one by one and the channel assignment for the end nodes of the selected edge are updated. In this way, every edge in G will have at least a corresponding edge in GA . By running Step 3, new edges may be added into GA and no existing edge will be removed from GA . Therefore, K-connectivity can be guaranteed by Algorithm 1. Step 1 takes O(Kn3 log m) time since K-connectivity testing on G can be done in O(Kn3 ) if the algorithm in [9] is used. It is obvious that case 4 is the most time-consuming case in Step 2. In this case, computing A(u) A(v) will take O(Q) time. Finding the least used link in P Ee takes O(m) time since there will be at most m links in P Ee . The channel replacement process will stop after O(n) steps, as there are O(n) nodes involved. Q can be considered as a constant because the total number of available channels, C, is normally a small constant (3 or 12). Q is usually less than C, otherwise, the channel assignment will become trivial. So Step 2 takes O(m2 ) time. Step 3 can be done in O(n2 ) because we need to check the channel assignment for all nodes in Step 3. Each node may have O(n) neighbors in G. Channel assignment can be decided after checking the channel assignment of all those neighbors. Therefore, the total worst-case time complexity of Algorithm 1 is O(Kn3 log m + m2 ). This completes the proof. ? Essentially, a K-connected topology with minimum maximum link potential interference will be found by Step 1 with the hope that the ?nally computed channel assignment will lead to a topology with low co-channel interference. In addition, a link will be kept in G as long as it has relatively low potential interference, i.e., the G will be relatively dense enough, which hopefully will bene?t the performance of routing because a large number of candidate routes are available. We always assign the least used channels to links in Step 2-Step 3, In this way, the channels assigned to nodes will be as di?erent as possible in a potential interference neighborhood. In [15], the authors classify the static channel assignment schemes for multi-channel wireless networks into two groups, the common channel approach ([4]) and the varying channel approach ([21, 22]). Like discussed before, the channel assignment schemes proposed in [21, 22] cannot be applied here since we do not assume that the tra?c demands are given or can be precisely predicted, and moreover Kconnectivity cannot be guaranteed. In the common channel approach, NICs of all nodes are assigned to a common set of channels. Obviously, the topology given by such method is a feasible solution for our INSTC problem. So we will compare our scheme with the common channel assignment approach in the simulations.

5.

INTERFERENCE-AWARE QOS ROUTING

Theorem 1. Algorithm 1 correctly computes a node channel assignment whose corresponding network topology is Kconnected in O(Kn3 log m + m2 ) time.

In this section, we will present a polynomial time optimal algorithm for solving the bandwidth-aware routing problem. Our optimal algorithm is based on solving a Linear Programming (LP). As a result, the computed route is ?ow based, which is not guaranteed to be a single path. Computing a

72

single path with required bandwidth subject to both inter?ow contention and intra-?ow contention does not seem to be possible in polynomial time since intra-?ow contention can be determined only if the path is given but there may exist exponential number of single paths between a source and a destination node. Therefore, we will present a maximum bottleneck capacity path heuristic for this purpose.

We ?x s to any of the vertices si ∈ VA and ?x t to any of the vertices tj ∈ VA . We de?ne the ?ow allocation variables, fe : e ∈ EA , which indicates the bandwidth to be allocated on link e. We present our LP formulation as follows. minimize
e∈EAO

(|IEe | ? fe )

(1)

5.1 Optimal Algorithm
We ?rst present an LP formulation for the routing problem and then formally present the complete algorithm. We assume that we have already obtained a good channel assignment A and its corresponding topology GA (V, EA ). Our QoS routing will be operated on the topology GA (V, EA ). Given a new connection request ρ with source node s, destination node t, and bandwidth requirement B. We want to ?nd a route with required bandwidth on the given topology. We need to construct an auxiliary digraph GA (VA , EA ) from the topology GA (V, EA ) for our LP formulation. We will describe the construction of GA (VA , EA ) in a way that is easy to understand. For each node v ∈ V , VA contains Q nodes v λ1 (v) , v λ2 (v) , . . . , v λQ (v) , where λ1 (v) < λ2 (v) < · · · < λQ (v) are the Q channels constituting the set A(v). For each v ∈ V and 1 ≤ i < Q, EA contains a directed edge from v λi (v) to v λi+1 (v) and a directed edge from v λi+1 (v) to v λi (v) , both with capacity set to ∞. Such edges are called intra-node edges. We will use use EAI to denote the set of intra-node edges. For each undirected edge (u, v; k) ∈ EA , EA contains two directed edges (uk , v k ) and (v k , uk ). Such edges are called inter-node edges. The capacity of such edges are set to A(u, v; k) (available bandwidth). We will use EAO to denote the set of inter-node edges. Clearly, EA = EAI EAO . To reduce the network complexity, we also eliminate some of the intra-node edges in the following way. Let v i be any node in VA . If there does not exist a node wi ∈ VA and j = i such that (v i , wi ) ∈ EA and (v j , wj ) ∈ EA , then we can shrink the intra-node edges incident with v i . After this shrinking step, we will have a graph where intra-node edges only exist at nodes which are incident with multi-edges in the topology. By abusing the notation a little bit, we will use GA (VA , EA ) to denote this reduced graph. Figure 3 shows the directed graph GA constructed from the network topology in Figure 1. Note that we only have intranode edges at nodes A1 , A2 , B 1 , B 2 . All other intra-node edges are shrunk. We therefore drop the superscript at the nodes E i , C i and Di .
{2,3} C

Subject to : Flow conservation constraint: fe ?
out e∈Ev in e∈Ev

fe = 0

?v ∈ VA \ {s , t }

(2)

Bandwidth requirement constraint: fe ?
e∈E out
s

fe = B
e∈E in
s

(3)

Interference constraint: fe ≤ A(e)
e ∈IEe

?e ∈ EAO

(4)

fe ≥ 0

?e ∈ EA

(5)

In the above formulation, IEe denotes the set of internode edges interfering with link e ∈ EAO . The intra-node out edge will be ignored when interference is considered. Ev in and Ev are the outgoing and incoming edge sets of node v in GA respectively. A(e) denotes the available bandwidth on link e, whose value is the same as the available bandwidth of its corresponding link in GA (refer to De?nition 3). Constraint (2) is a general ?ow conservation constraint which makes sure an s –t ?ow allocation is computed. Constraint (3) guarantees that the total bandwidth requirement B from the connection request is satis?ed. With the intra?ow and inter-?ow contentions fully considered, Constraint (4) ensures that the available bandwidth on each link is large enough for the ?ow (bandwidth) allocation. The objective function (1) is set to minimize the interference in?uence from the current connection, which hopefully will increase the chance for the upcoming connection requests to be admitted. The optimal algorithm for solving BAR problem is presented as Algorithm 2 in the following. Theorem 2. Algorithm 2 correctly solves the BAR problem in polynomial time. Proof. As we discussed earlier, the correctness of the algorithm lies in the fact that Equations 2-5 ensure that the constraints in De?nition 4 are all satis?ed. The auxiliary graph GA includes at most nQ nodes and at most 2mQ + 2nQ edges. Since Q is a small constant, we will ignore Q in our analysis. It is obvious that Step 1 can be done in polynomial time. The LP formulation has O(n + m) constraints and O(n + m) variables. Therefore, Step 2 takes polynomial time. Clearly, updating the link loads and available bandwidth information can be done in polynomial time as well. ?

3

2 2

3

{2} A2 2 2 B2 {2}

{1} A
1

1 1

E {1,3}
1

1 1

D {1,2}

1

1 1 B1 {1}

GA

Intra-node Edge Inter-node Edge

Figure 3: Construction of GA

73

Algorithm 2 Optimal BAR Algorithm Step 1 Construct GA (VA , EA ) from the given topology GA (V, EA ). Step 2 Solve LP formulation speci?ed by Constraints (15) on GA . Step 3 if a feasible solution can be found Output the corresponding ?ow allocation in GA . Update the load and available bandwidth of each a?ected link in GA . else block the connection request. endif

which has the maximum bottleneck capacity value among all s-t single paths and its hop-count is bounded by a given threshold H. For ease of presentation, we ?rst present an algorithm to ?nd a bottleneck capacity bounded minimum hop-count path on a given network topology, which is a minimum hop-count s-t single path among all s-t single paths with bottleneck capacity bounded by a given threshold T . Algorithm 3 Bottleneck capacity bounded minimum hopcount path algorithm Step 1 Construct an auxiliary digraph GB (VB , EB ) where VB contains all the wireless nodes and EB contains all the links in GA whose bottleneck capacity are at least T . Step 2 Apply Breadth First Search (BFS) algorithm to compute an s–t path P in GB with minimum hopcount.

5.2 Maximum Bottleneck Capacity Path Heuristic
In order to route packets based on the ?ow allocation computed by Algorithm 2, tra?c needs to be splitted at some intermediate nodes. Sometimes tra?c splitting is not preferred because of di?culties in packet fragmentation and reassembly. So we also propose a heuristic for the BAR problem, which computes a single path for packet routing. Note here no splitting means for a speci?c connection, tra?c can only be received by a single NIC and/or be transmitted by a single NIC (these two NICs can be di?erent) at any involved node. The basic idea of our heuristic is to carefully select a candidate s-t single path on the given network topology GA for an incoming connection request, which most likely will satisfy all bandwidth constraints. Obviously, a single path also corresponds to a ?ow allocation, where the allocated bandwidth in each link on the path is equal to B. Then we check its feasibility according to De?nition 4. If no constraint is violated, the connection request is accepted and the found candidate path is used for routing. Otherwise, block the connection request. Before describing the algorithm, we need to introduce a new metric for the candidate path computation. Definition 6 (Bottleneck Capacity). The Link Bottleneck Capacity of link e, denoted by BC(e) is BC(e) = mine ∈IEe A(e )/B . The Path Bottleneck Capacity of a single path P , denoted by BC(P ), is BC(P ) = mine∈P BC(e). When a path P is established for a connection, two or more links on this path may interfere with some common link e. The available bandwidth on link e must be large enough to tolerate such interference. Otherwise, path P cannot be used for routing because bandwidth requirements cannot be satis?ed in the system. Intuitively, we prefer to select those links with relatively higher bottleneck capacity values because by doing so, we can reduce the probability for the bandwidth constraint to be violated. The total required bandwidth on each link cannot exceed its available bandwidth. On the other hand, we prefer a path with relatively low hop-count because the more hops a candidate path has, the longer delay packets will su?er, and more importantly, the higher bandwidth invalidation probability it will cause. Therefore, we try to ?nd a hop-count bounded maximum bottleneck capacity path as the candidate path,

Our maximum bottleneck capacity path heuristic is listed as Algorithm 4. Algorithm 4 Maximum bottleneck capacity path heuristic Step 1 Use binary search on all link bottleneck capacity values to ?nd the maximum link bottleneck capacity T so that the corresponding path P on GA computed by Algorithm 3 with bottleneck capacity threshold T has a total hop-count no more than the given threshold H. Step 2 Check the feasibility of path P according to De?nition 4. Step 3 if Path P is feasible Output path P . Update the load and available bandwidth of each a?ected link in GA . else Block the connection request. endif

Algorithm 3 takes O(m) time since GA contains at most mQ edges. Therefore, Step 1 of Algorithm 4 can be done in O(m log m) time. Similarly, Step 2 takes O(mn) time since a path in GA has at most n hops. Step 3 needs O(m2 ) time. Thus, the total time complexity for Algorithm 4 is O(m2 ). The hop-count threshold H is usually set to a Bound Ratio β multiplied by the number of hops of the corresponding minimum hop-count path. Since the minimum hop-count path is not unique for a speci?c source-destination pair, we can obtain a minimum hop-count path with larger bottleneck capacity value than other corresponding minimum hopcount paths by using our heuristic and setting β = 1, which will make the found path more likely to be a feasible solution. Setting β larger than 1 will allow the algorithm to select a path with a larger bottleneck capacity. However, having more hops may counteract such gain. We will discuss this in more detail in Section 6.

74

6. PERFORMANCE EVALUATION
In this section, we evaluate the performance of our algorithms via simulations. We consider static wireless mesh networks with n nodes randomly located in a 900×900m2 region. In all simulation scenarios, we require 2-connectivity (K = 2) be preserved by the topology control algorithm. Each node has a ?xed transmission range of 250m and interference range of 500m ([21]). In all scenarios, each connection request is generated with a randomly chosen sourcedestination pair and a random bandwidth requirement B which is no more than a given maximal bandwidth requirement (Bmax ). In total, 1000 connection requests are injected in each simulation run. The lifetime (LT ) of each connection speci?es how many time units it will last. This is also a random number uniformly distributed between 1 and a maximal value (LTmax ) which is set to 200 in all simulations. The connection Blocking Ratio, i.e., the ratio between the number of blocked connections and the total number of connection requests, is the metric used for our performance evaluation. The following ?ve system parameters can in?uence the performance: network size (n), the number of available non-overlapping channels (C), the number of NICs (Q) in one node, the channel capacity (CAP ) and the tra?c load. According to IEEE 802.11 speci?cations, we set the channel number (C) to be 3 (802.11b) in some scenarios and 12 (802.11a) in others, and the corresponding channel capacity (CAP ) are 11(M bps) and 54(M bps) respectively. We adjust the tra?c load by ?xing the mean connection request arrival interval to be 15 time units and vary the maximal bandwidth requirement (Bmax ). The number of NICs (Q) at each node is set to 2 in some scenarios and 3 in others. We ?rst show the performance of combined topology control and routing scheme with regards to connection blocking ratio. The corresponding results are presented in Figures 48. We compare our solutions, i.e., our interference-aware topology control heuristic (Algorithm 1) along with optimal BAR algorithm (Algorithm 2) or the Maximum Bottleneck Capacity Path heuristic (Algorithm 4), with a simple approach including the Common channel assignment approach ([4]) and minimum hop-count (Shortest) Path routing. These schemes are labelled as BAR, MBCP and CSP, respectively in the ?gures and will also be called the BAR, the MBCP and the CSP scheme for brevity. Notice that we set the bound ratio β to 1.0 and 1.5 for the maximum bottleneck capacity path heuristic respectively in each scenario. We make the following observations from our simulation results. Our BAR scheme performs best in all cases. Compared with the CSP scheme, it reduces the blocking ratios from 32.5% to 13.9% on average, which is a 57% improvement. This improvement becomes more substantial when the network resources (Q, C, CAP ) become relatively large (Figures 6–8). This is because our scheme is fully aware of the in?uence of the interference and makes use of available resources more wisely. For example, the more channels we have, the more likely the nodes in the neighbor are assigned to di?erent channels so that the in?uence of interference can be reduced. This will eventually increase the chance for a connection request to be admitted. However, more channels will not lead to any improvement if common channel assignment approach is applied. Our MBCP scheme always outperforms the CSP scheme. Setting the bound ratio to di?erent values does not change

60 BAR MBCP(1.0) MBCP(1.5) CSP 50

40 Blocking Ratio (%)

30

20

10

0

1

2

3 Maximal Bandwidth Requirement

4

5

Figure 4: n = 25, C = 3, Q = 2, CAP = 11
60 BAR MBCP(1.0) MBCP(1.5) CSP 50

40 Blocking Ratio (%)

30

20

10

0

1

2

3 Maximal Bandwidth Requirement

4

5

Figure 5: n = 40, C = 3, Q = 2, CAP = 11 the blocking ratios too much. This is due to the fact that by setting the bound ratio to a relatively high value, links with high bottleneck capacity may be selected for routing which will reduce the probability for the path to be blocked. On the other hand, the selected path may have more hops, which on the contrary, will increase the bandwidth violation probability and eventually cause the connection to be blocked. These two factors will counteract with each other. Furthermore, the blocking ratio increases with the increase of the maximal bandwidth requirement since more bandwidth needs to be allocated for each connection. This reduces the chance for an upcoming connection request to be accepted. Substantial blocking ratio reduction is achieved by having one more NICs in each node (Figure 7–8). NICs on a node can be simultaneously used for transmission as long as they are assigned to di?erent channels. Therefore, more bandwidth is brought to system when one more NIC is provided for each node. In the second part, we try to verify the e?ectiveness of our topology control algorithm on di?erent networks, i.e,

75

60 BAR MBCP(1.0) MBCP(1.5) CSP 50

60 BAR MBCP(1.0) MBCP(1.5) CSP 50

40 Blocking Ratio (%) Blocking Ratio (%) 15 20 Maximal Bandwidth Requirement 25 30

40

30

30

20

20

10

10

0 10

0 10

15

20 Maximal Bandwidth Requirement

25

30

Figure 6: n = 25, C = 12, Q = 2, CAP = 54
60 BAR MBCP(1.0) MBCP(1.5) CSP 50 50 60

Figure 8: n = 40, C = 12, Q = 3, CAP = 54
IATC Common

40 Blocking Ratio (%) Blocking Ratio (%)

40

30

30

20

20

10

10

0 10

0 15 20 Maximal Bandwidth Requirement 25 30

1

2

3

4

5 Trail

6

7

8

9

10

Figure 7: n = 40, C = 12, Q = 2, CAP = 54 di?erent node deployments. Our optimal BAR algorithm are always used for QoS routing. In each scenario, we randomly generate 10 networks, each with 25 nodes. In each trial, we employ our Interference-Aware Topology Control (IATC) algorithm and the common channel assignment approach (Common) respectively to assign channels to nodes and observe the obtained connection blocking ratios. The results are shown in Figures 9–10. As expected, our interference-aware topology control algorithm always achieves lower blocking ratios than the common channel assignment approach no matter how the nodes are deployed in the plane. Quite consistent with the previous results, the performance improvement becomes more remarkable when more network resources are available.

Figure 9: n = 25, C = 3, Q = 2, CAP = 11, Bmax = 2 have presented a novel de?nition of co-channel interference to precisely capture the in?uence of the interference. According to this de?nition, we formally de?ned the minimum INterference Survivable Topology Control (INSTC) problem and presented an e?ective heuristic for INSTC. We also formulated and presented a polynomial time optimal algorithm to solve the Bandwidth-Aware Routing (BAR) problem on a given network topology induced by topology control. Simulation results show that our scheme outperforms the existing scheme substantially. Studying distributed algorithms for the proposed problems will be of our interest in the future.

8.

REFERENCES

7. CONCLUSIONS
In this paper, we have studied interference-aware topology control and QoS routing in IEEE 802.11-based multichannel wireless mesh networks with dynamic tra?c. We

[1] I. F. Akyildiz, X. Wang, W. Wang, Wireless mesh networks: a survey, Elsevier Journal of Computer Networks(2005), In press. [2] A. Adya, P. Bahl, J. Padhye, A. Wolman, and L. Zhou, A multi-radio uni?cation protocol for IEEE

76

60 IATC Common

50

[15]

40 Blocking Ratio (%)

[16]

30

[17]
20

10

[18]

0

1

2

3

4

5 Trail

6

7

8

9

10

[19]

Figure 10: n = 25, C = 12, Q = 2, CAP = 54, Bmax = 15 [20] 802.11 Wireless Networks, Proceedings of IEEE BroadNets’2004. P. Bahl, Opportunities and challenges of community mesh networking, Keynote Presentation @ MICS Workshop in ETH Zurich, 2004. V. Bahl, A. Adya, J. Padhye, A. Wolman. Reconsidering the wireless LAN platform with multiple radios, Workshop on Future Directions in Network Architecture, 2003. P. Bahl, R. Chandra, and J. Dunagan, SSCH: Slotted seeded channel hopping for capacity improvement in ieee 802.11 ad-hoc wireless networks, Proceedings of ACM MobiCom’2004, pp. 216–230. J. A. Bondy and U. S. R. Murthy, Graph Theory with Applications, North Holland, 1976. M. Burkhart, P. von Rickenbach, R. Wattenhofer, A. Zollinger, Does topology control reduce interference, Proceedings of ACM MobiHoc’2004, pp. 9–19. R. Draves, J. Padhye, and B. Zill, Routing in multi-radio, multi-hop wireless mesh networks, Proceedings of ACM MobiCom’2004, pp. 114–128. S. Even, An algorithm for determining whether the connectivity of a graph is at least k, SIAM Journal of Computing Vol. 4(1975), pp. 393-396. S. Guo, O. Yang, QoS-aware minimum energy multicast tree construction in wireless ad hoc networks, Elsevier Journal of Ad Hoc Networks, Vol. 2(2004), pp. 217–229. P. Gupta, P. R. Kumar, The capacity of wireless networks, IEEE Transactions on Information Theory, Vol. 46(2000), pp. 388–404. IEEE 802.11 Working Group, Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Speci?cations, 1997. IEEE 802.11a Working Group, Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Speci?cations - Amendment 1: High-speed Physical Layer in the 5 GHz band, 1999. K. Jain, J. Padhye, V. Padmanabhan and L. Qiu, Impact on interference on multihop wireless network

[3]

[21]

[4]

[22]

[5]

[23]

[6] [7]

[24]

[8]

[25]

[9]

[26]

[10]

[27]

[11]

performance, Proceedings of ACM MobiCom’2003, pp. 66–80. P. Kyasanur, N. H. Vaidya, Routing and interface assignment in multi-channel multi-interface wireless networks, Proceedings of WCNC’2005. W. H. Liao, Y. C. Tseng, K. P. Shih, A TDMA-based bandwidth reservation protocol for QoS routing in a wireless mobile ad hoc network, Proceedings of IEEE ICC’2002, pp. 3186–3190. C. R. Lin, J. S. Liu, QoS routing in ad hoc wireless networks, IEEE Journal on Selected Areas in Communications Vol. 17(1999), pp. 1426–1438. H. Liu, X. Jia, D. Li, C. H. Lee, Bandwidth guaranteed call admission in TDMA/CDMA ad hoc wireless networks, Elsevier Journal of Ad Hoc Networks(2005), In press. K. Moaveninejad, X. Y. Li, Low-interference topology control for wireless ad hoc networks, Journal of Ad Hoc and Sensor Wireless Networks(2005), Accepted for publication. C. E. Perkins, E. M. Royer, S. R. Das, Quality of service for ad hoc on-demand distance vector routing (work in progress), IETF Internet Draft, 2000. A. Raniwala, T. Chiueh, Architecture and algorithms for an IEEE 802.11-based multi-channel wireless mesh network, Proceedings of IEEE INFOCOM’2005. A. Raniwala, K. Gopalan, T. Chiueh, Centralized channel assignment and routing algorithms for multi-channel wireless mesh networks, ACM Mobile Computing and Communications Review (MC2R), Vol. 8(2004), pp. 50–65. J. So, N. H. Vaidya, Multi-channel MAC for ad hoc networks: Handling multi-channel hidden terminals using a single transceiver, Proceedings of ACM MobiHoc’2004, pp. 222–233. J. So, N. H. Vaidya, A routing protocol for utilizing multiple channels in multi-hop wireless networks with a single transceiver, UIUC Technical Report, 2004. Available at: http://www.crhc.uiuc.edu/wireless /groupPubs.html Q. Xue, A. Ganz, Ad hoc QoS on-demand routing (AQOR) in mobile ad hoc networks, Journal of Parallel Distributed Computing Vol. 63(2003), pp. 154–165. H. Zhai, J. Wang, Y. Fang, Distributed packet scheduling for multihop ?ows in ad hoc networks,Proceedings of IEEE WCNC’2004, pp. 1081–1086. C. Zhu, S. Corson, QoS routing for mobile ad hoc networks, Proceedings of IEEE INFOCOM’2002, pp. 958–967.

[12]

[13]

[14]

77


赞助商链接

更多相关文章:
更多相关标签:

All rights reserved Powered by 甜梦文库 9512.net

copyright ©right 2010-2021。
甜梦文库内容来自网络,如有侵犯请联系客服。zhit325@126.com|网站地图