 Open Access
 Total Downloads : 354
 Authors : Rohina Khanam, Raafiya Gulmeher
 Paper ID : IJERTV2IS70318
 Volume & Issue : Volume 02, Issue 07 (July 2013)
 Published (First Online): 17072013
 ISSN (Online) : 22780181
 Publisher Name : IJERT
 License: This work is licensed under a Creative Commons Attribution 4.0 International License
Optimal Routing Under The High Dynamic And Uncertain Traffic In WMN
Optimal Routing Under The High Dynamic And Uncertain Traffic In WMN
Rohina Khanam Raafiya Gulmeher
P.G. Student Assistant Professor
Department Of Computer Science and Engineering Department Of Computer Science and Engineering
Khaja Banda Nawaz College of Engineering Khaja Banda Nawaz College Of Engineering
Gulbarga, Karnataka, India Gulbarga, Karnataka, India
Abstract: Network routing plays a critical role in determining the performance of a wireless mesh network. To study the best mesh network routing strategy which can maximize the network throughput while satisfying the fairness constraints, existing research proposes to formulate the mesh network routing problem as an optimization problem. These works usually make ideal assumptions such as known static traffic input. Whether they could be applied for practical use under the highly dynamic and uncertain traffic in wireless mesh network is still an open issue. The main objective of this paper is to understand the effects of traffic uncertainty in wireless mesh networks and consider these effects in throughput maximization routing. It identifies the appropriate optimization framework that could integrate the statistical user traffic demand model into a tractable throughput maximization problem. The trace driven simulation study demonstrates that our algorithm can effectively incorporate the traffic demand uncertainty in routing optimization, and outperform the throughput maximization routing which only considers static traffic demand.
Keywords: WSN , Uncertain Demand Mesh Network Routing , Traffic Demand.

INTRODUCTION.
Wireless mesh networks have attracted increasing attention and deployment as a highperformance and low cost solution to lastmile broadband Internet access. In wireless mesh networks, local access points and stationary wireless mesh routers communicate with each other and form a backbone network which forwards the traffic from mobile clients to the Internet. Traffic routing in the mesh backbone network plays a critical role in determining the performance of a wireless mesh network. These existing routing solutions usually fall into two ends of the spectrum. On one end of the spectrum are the heuristic algorithms. Although many of such approaches are adaptive to the dynamic environments of wireless networks, they lack the theoretical foundation to analyze how well the network performs globally ,e.g., whether the network resource is fully utilized, whether the flows share the network in a fair fashion. On the other end of the spectrum, there are theoretical studies that formulate these network planning decisions into optimization problems . Yet these results usually make ideal assumptions towards the network such as known static traffic input, which makes them unsuitable
for practical use in the highly dynamic wireless networking environments.
This paper investigates the traffic routing problem for throughput optimization with fairness constraint under uncertain demand. In particular, it studies how traffic from(to) local access points could be routed in a mesh network so that the minimum proportion of the demands from all local access points could be maximized. If the traffic demand from each local access point is known a priori, the throughput optimization problem with fairness constraint could be formulated as a linear programming problem maximum concurrent flow problem . To incorporate demand uncertainty into this optimization framework, this paper first characterizes the uncertain traffic demand using a random variable.
To incorporate demand uncertainty into this optimization framework, this paper first characterizes the uncertain traffic demand using a random variable. Under this model, the proportions of traffic demands are also random variables for a given routing strategy. Thus this paper extends the maximum concurrent flow problem to a stochastic optimization problem where the expected value of the performance ratio between the achieved traffic demand proportion and its optimum is maximized. This paper further presents two fast 1 approximation algorithms for throughput optimization under fixed and uncertain demand respectively. These traffic demands are used to drive the simulation. Our simulation results demonstrate that our statistical problem formulation could effectively incorporate the traffic demand uncertainty in routing optimization, and our algorithm outperforms the conventional solution which only considers the static traffic demand.
The original contributions of this paper are two fold. First, to the best of our knowledge, this is the first work that integrates statistical user traffic demand model into a tractable throughput optimization problem for wireless mesh networks. Second, this paper evaluates the practicability of optimizationbased routing solutions using the trace data collected in the real wireless network environments.
The remainder of this paper is organized as follows.
Sec. 2 presents about the related work , Sec.3 presents the network and traffic demand model., Sec. 4 formulates the mesh network routing problem under fixed traffic demand
based on maximum concurrent flow and presents a fast approximation algorithm., Sec. 5 extends the routing problem to handle uncertain traffic demand. We show simulation results in Sec. 6 and finally conclude the paper in Sec. 7.

RELATED WORK.
We evaluate and highlight our original contributions in light of previous related work. The problem of wireless mesh network routing has been extensively studied in the existing literature. For example, routing algorithms are proposed to improve the throughput for wirelessmesh networks via integrating MAC layer information [7], such as expected packet transmission time [8]. Joint solutions for channel allocation and routing are explored in [20] using a centralized algorithm and in [19] in a distributed fashion. These heuristic solutions lack the theoretical foundation to analyze how well the network performs globally (e.g., whether the network resource is fully utilized, whether the flows share the network in a fair fashion) under their routing schemes. There are also theoretical studies that formulate these network planning decisions into optimization problems. For example, the works of [5], [14] study the optimal solution of joint channel assignment and routing for maximum throughput under a multicommodity flow problem formulation and solves it via linear programming. The work of [21] presents bandwidth allocation schemes to achieve maximum throughput and lexicographical maxmin fairness respectively. [9] presents a rate limiting scheme to enforce the fairness among different local access points. These results provide valuable analytical insights to the mesh network design under ideal assumptions such as known static traffic input. It is not clear whether they will be unsuitable for practical use under highly dynamic traffic situation. Different from these existing works, our work explicitly incorporates traffic uncertainty into the routing optimization, thus better fits the routing need in the dynamic wireless mesh networks. Distributed algorithms have presented for joint scheduling and routing in [17], and for joint channel assignment, scheduling and routing in [17]. These distributed algorithms only use local information for traffic routing, thus have the potential to accommodate dynamic traffic. However, their crucial properties, such as convergence speed and messaging overhead, are yet to be evaluated under realistic traffc conditions. Trace analysis has been used to study the behavior of wireless networks in many recent works. To name a few, the works of [15, 12] analyze a campuswide wireless network traffic and its changes in two years. [18] statistically characterizes both static flows and roaming flows in a large campus wireless network. In [22], the flow level traffic pattern is used to design a scheduling algorithm for endhost multihoming. Different from these existing works, which focus on either user behavior, network flow or link performances, we provide a framework that integrates traffic uncertainty model with its performance optimization. Our work is also related to dynamic traffic engineering [23] in Internet and oblivious routing [6], which also consider the impact of demand uncertainty in make routing decisions. The major difference between our
work and these existing works lies in the different network models of wireless mesh network and Internet and the different problem formulations. In particular, traffic engineering tries to minimize the congestion (utilization) of the wired links of a network. In multihop wireless network, wireless link utilization can not be used to characterize the network performance due to the location dependent contention in the vicinity area. The objective of our research is to maximize the ratio between flow throughput and its demand, subject to the schedulability and fairness constraints.


Network Model
Figure 1. Illustration of Wireless Mesh Network
We consider a multihop wireless mesh network as illustrated in Fig. 1. In this network, local access points aggregate the traffic from mobile clients that are associated with them. They communicate with each other, also with stationary wireless routers, forming a multihop wireless backbone network which forwards the user traffic to a gateway access point connecting to the Internet. In the following discussion, local access point, gateway access point, and mesh routers are collectively called mesh nodes. We model the backbone of a wireless mesh network as a directed graph G = (V,E), where each node u V represents a mesh node. Among these nodes, g
V is the gateway access point that connects to the Internet. A directed edge e = (u, v) E denotes that u can transmit to v directly. We assume that all mesh nodes have a uniform transmission range denoted by r(u, v) RT. . We
denote r(u, v) as the distance between u and v. An edge e = (u, v) E if and only if r(u, v) RT. We also use r(e) to represent the length of edge e. Let b(e) bit/sec be the data rate of edge e, which is maximum data that can be carried in a second along e.

Traffic Demand Model
Fig.2. architecture of traffic demand model
This paper investigates the throughput optimization routing scheme for wireless mesh backbone network. Thus we consider the aggregated traffic among the mesh nodes. In particular, we regard the gateway access points as the source of all incoming traffic and the destination of all outgoing traffic of a mesh network. Similarly, the local access points, which aggregate the client traffic, serve as the sources of all outgoing traffic and the destinations of incoming traffic. For simplicity, we call the aggregated traffic that shares the same source and destination as a flow and denote it as f F, where F is the set of all aggregated flows. It is worth noting that although we consider only one gateway access point in this paper, our problem formulation and algorithm presented here could be easily extended to handle multiple gateway routers and intermeshrouter traffic. Finally, we denote the rate of an aggregated flow f F as xf , and use x = (xf , f F) to represent the aggregated flow rate vector.

Interference Model and Schedulability
In a wireless network, packet transmissions are subject to locationdependent contention, which means that simultaneous transmissions in the proximate region may interfere with each other and result in packet collision. Usually the interference range of a node is larger than its transmission range. Thus we denote the interference range of a node as RI = (1+)RT, where 0 is a constant. In this paper, we consider the protocol model for packet transmission [11]. In the protocol model, packet transmission from node u to v is successful if and only if
(1) the distance between these two nodes r(u, v) satisfies r(u, v) < RT ; (2) any other node w V within the interference range of the receiving node v, i.e., r(w, v) RI
, is not transmitting. Two edges e, e_ interfere with each other, if they can not transmit simultaneously based on the protocol model. We use I(e) denote the set of edges which interfere with edge e. To study the throughput optimization routing problem, we first need to understand the constraint of the flow rates. Let y = (ye, e E) denote the wireless link rate vector, where ye is the aggregated flow rate along wireless link e. Link rate vector y is said to be schedulable, if there exists a stable schedule that ensures every packet transmission with a bounded delay. Essentially, the constraint of the flow rates is defined by the schedulable
region of the link rate vector y. The link rate schedulability problem has been studied in several existing works, which lead to different models [ 16, 24]. In this paper, we adopt the model in [13], which presents a sufficient condition under which a link scheduling algorithm is given to achieve stability with bounded and fast approximation of an ideal schedule. Based on this model, we define S(e) as a subset of I(e), where each e' I(e) that has a length r(e') greater than or equal to r(e) is in S(e). In the following discussion, we refer S(e) as the adjusted interference set of e.


Fixed Demand Mesh Network Routing
Fig 3: Fixed mesh network routing
We investigate the throughput optimization routing problem for wireless mesh backbone network. The objective of this problem is to maximize the throughput of aggregated flows among local access points and the gateway, while satisfying the fairness constraints. This problem is usually formulated as a maximum concurrent flow problem. In this section, we first study the formulation of throughput optimization routing in wireless mesh backbone network under fixed traffic demand. We then present a fully polynomial time approximation algorithm (FPTAS) for this problem, which finds an approximate solution. The problem formulation and algorithm presented in this section serve as the basis of the uncertain demand routing problem. Recall that f F is the aggregated traffic flow between local access points and the gateway. We use df to denote the demand of flow f and d = (df , f F) to denote the demand vector consisting of all flow demands. Consider the fairness constraint that, for each flow f, its throughput being routed is in proportion to its demand df . Our goal is to maximize (so called scaling factor) where at least df amount of throughput can be routed for flow f. We assume an infinitesimally divisible flow model where the aggregated traffic flow could be routed over multiple paths and use Pf to denote the set of unicast paths that could route flow f. Let xf (P) be the rate of flow f over path P Pf.
The problem could be solved by a LPsolver. To reduce the complexity for practical use, we present a fully polynomial time approximation algorithm (FPTAS) for problem P, which finds an approximate solution. The key to a fast approximation algorithm lies on the dual of this problem, which is formulated as follows. First we define AeP = Se P as the number of wireless links a path P passes in the adjusted interference set Se. We assign a price e to each set Se for e E. The objective is to minimize aggregated price for all adjusted interference sets.
Fig.4 Routing AlgorithmI Under Fixed Demand
The algorithm design follows the idea of [10]. To start with, we initialize the price on each adjusted inerference set Se as (Line 1). We also zero the traffic on all paths P Pf (Line 2). Then for each flow f, we route df units of data. We do so by finding the lowest priced path in the path set Pf (Line 7), then filling traffic to this path by its bottleneck capacity (Lines 8 to 10). Then we update the prices for physical edges appeared in this path based on the function defined in Line 11. We keep filling traffic to flow f in the above fashion until all df units are routed. This procedure is repeated until the aggregate price of interference sets Se for all e E weighted by the capacity c exceeds 1 (Line 3). We make following notes to our algorithm. First, it completes in finite time, which is guaranteed by the asymptotic link price update function defined in Line 11. here is the step size, which controls the growing speed of the link price. Second, as one might see, the algorithm in fact routes more traffic than the network is able to afford. Therefore, a scaling procedure is needed to scale down the routed traffic so it fits the capacity of each physical link in the network.

Uncertain Demand Mesh Network Routing
Fig.5.uncertain demand mesh network
Now we proceed to investigate the throughput optimization routing problem for wireless mesh backbone network when the aggregated traffic demand is uncertain. We model such uncertain traffic demand of an aggregated flow f F using a random variable Df . We assume that Df follows the following discrete probability distribution
Pr(Df = di f) = qi f where Df = {d1f , d2f, …, dmf} is the set of of values for Df with nonzero probabilities. Let d = (df,
df Df, f F) be a sample traffic demand vector of all flows, D be the corresponding random variable, and D be the sample space. We assume that the demand from different access points are independent from each other. Thus the distribution of D is given by the joint distribution of these random variables as follows.
Pr(D = d) = Pr(Df = dif, f F) = f F qif.
Let us consider a traffic routing solution (xf (P), P Pf, f
F) that satisfies the capacity constraint It is obvious that the is a function of d:
where xf = () . Further let us consider the optimal routing solution under demand vector d. Such a solution could be easily derived based on Algorithm I . We denote the optimal value of as (d). We further define the performance ratio of routing solution (xf (P), P Pf, f F) as follows:
Obviously, the performance ratio is also a random variable under uncertain demand. We denote it as . is a function of random variable D. Now we extend the wireless mesh network routing problem to handle such uncertain demand. Our goal is to maximize the expected value of , which is given as follows.
Fig .6. Routing Algorithm II Under Uncertain Demand
Now we present an approximation algorithm for PU . This algorithm (Algorithm II) has the same initialization as the algorithm for problem P (Algorithm I). Then we march into the iteration, in which we find dmin, the demand whose price min is the minimum among others (Lines 4 to 12). If min 1, then the algorithm stops (Lines 13 and 14), since Inequality (8) and (9) would be satisfied for all demand. Otherwise, we will increase the price of dmin by routing more traffic through its node pairs. This procedure (Lines 16 to 22) is the same as what has been described in the lines 4 to 11 of the previous algorithm. Following the same proving sequence for Algorithm I, we are able to prove the similar properties with Algorithm II

Simulation Study
We evaluate the performance of our algorithms via simulation study. In the simulated wireless mesh network, 30 mesh nodes are randomly deployed over a 800Ã—800m2 region, among which 10 nodes are local access points that forward traffic for clients. Node 10 which resides in the center of the deploy region is selected as the gateway router. Each mesh nodes has a transmission range of 250m. The simulated network topology is shown in figure below
Fig.7. simulation in OMNET++
6.2 Performance Comparison
We compare the performance of three traffic routing solutions described as follows. In particular, the first two employ the throughput maximization algorithm under fixed demand (AlgorithmI), while the last one employs the algorithm under uncertainty demand (AlgorithmII).

Online Solution: This solution keeps track of the dynamically changing demand and maximizes the throughput based on the current demand of each access point, meanwhile maintaining the fairness among them. Since the access point demand keeps changing, it has to continuously rerun AlgorithmI to adapt to the new demand. This solution yields the optimal routing result at the cost of frequent routing computation and update.

AverageDemandbased Solution: This solution estimates the dynamic traffic demand using the mean
value from its probability distribution for each access point. It computes a fixed route based on this average demand vector using Algorithm I. Using only the average demand, this solution does not consider the uncertainty of the traffic demand.

Uncertaintyaware Solution: This solution accommodates the uncertainty in traffic demand by maximizing the throughput for all demand vectors normalized by their occurring probabilities. In particular, it employs Algorithm II with the traffic distribution derived from the traces.
Fig.8. Comparison of Three Algorithms
The above three routing solutions under a series of experiments. For each experiment, the traffic demand of each access point is generated based on their probability distribution. We repeat the experiment for 100 times with 100 randomly generated traffic demand vectors. For each experiment, we derive its scaling factor , which is the minimum ratio of throughput and demand among all access points. Fig.8 plots the sorted values of in these 100 experiments. Evidently, the online solution keeps delivering the optimal scaling factor, at the cost of rerouting for each experiment. Comparatively, average demand solution provides a single set of routes for all demand vectors, but still achieves a scaling factor no worse than 50% of the optimum, except at the last 5 experiments. Uncertaintyaware solution demonstrate the same trend, but continuously outperforms the averagedemand solution by 20%. Although there are exceptions in the first 20 experiments when the optimal value of is low, the difference is minor. we compare the aggregated throughput of all local access points enabled by these three solutions. Obviously, throughout all experiments, the aggregated throughput remains the same for averagedemand and uncertainty aware solutions since they stick to only one set of routes. The online solution, however, results in unstable aggregate throughput over different experiments. While its maximum value is higher than the other two solutions, the minimum throughput is also well below both of them.
Fig. 9. Comparison of Aggregated Throughput
Our simulation results demonstrate that our statistical problem formulation could effectively incorporate the traffic demand uncertainty in routing optimization, and its algorithm outperforms the algorithm which only considers the static traffic demand.
7 Conclusion
The throughput optimization routing problem for wireless mesh networks. Different from existing works which assume fixed traffic demand known a priori, this work considers the traffic demand uncertainty. It models such uncertain demand with random variables, extends the classical maximum concurrent flow problem with statistical demand input, and derives approximation algorithms for uncertaintyaware traffic routing. Simulation study is conducted based on the traffic demands from the real wireless network traces. The results show that our problem formulation and algorithm could effectively incorporate the traffic demand uncertainty.
8.References

J. Tang, G. Xue, and W. Zhang. Maximum throughput and fair bandwidth allocation in multichannel wireless mesh networks. In Proc. of IEEE INFOCOM, 2006.

N. Thompson, G. He, and H. Luo. Flow scheduling for endhost multihoming. In Proceedings of IEEE INFOCOM, 2006.

H. Wang, H. Xie, L. Qiu, Y. R. Yang, Y. Zhang, and
A. Greenberg. Cope: traffic engineering in dynamic networks. In Proc. of ACM SIGCOMM, 2006.

Y. Xue, B. Li, and K. Nahrstedt. Optimal resource allocation in wireless ad hoc networks: A pricebased approach. IEEE Transactions on Mobile Computing, 5(4):347364, April 2006.

A community resource for archiving wireless data at dartmouth. http://crawdad.cs.dartmouth.edu/.

Ilog cplex mathematical programming optimizers. http://www.ilog.com/products/cplex.

Mit roofnet. http://www.pdos.lcs.mit.edu/roofnet/.

Seattle wireless. http://www.seattlewireless.net.

M. Alicherry, R. Bhatia, and L. Li. Joint channel assignment and routing for throughput optimization in multiradio wireless mesh networks. In Proc. of ACM MobiCom, 2005.

Y. Azar, E. Cohen, A. Fiat, H. Kaplan, and H. Racke. Optimal oblivious routing in polynomial time. J. Comput. Syst. Sci., 69(3), 2004.

S. Biswas and R. Morris. Exor: opportunistic multi hop routing for wireless networks. In Proc. of ACM SIGCOMM, pages 133144, 2005.

R. Draves, J. Padhye, and B. Zill. Routing in multi radio, multihop wireless mesh networks. In Proc. of ACM Mobicom, pages 114128, 2004.

V. Gambiroza, B. Sadeghi, and E. W. Knightly. End toend performance and fairness in multihop wireless backhaul networks. In Proc. of ACM MobiCom, 2004.

N. Garg and J. Konemann. Faster and simpler algorithms for multicommodity flow and other fractional packing problems. In Proc. of IEEE FOCS, 1998.

P. Gupta and P. Kumar. The capacity of wireless networks. IEEE Trans. on Information Theory, pages 388 404, 2000.

T. Henderson, D. Kotz, and I. Abyzov. The changing usage of a mature campuswide wireless network. In Proc. of ACM MobiCom, pages 187201, 2004.

K. Jain, J. Padhye, V. Padmanabhan, and L. Qiu. Impact on interference on multihop wireless network performance. In Proc. of Mobicom, September 2003.

M. Kodialam and T. Nandagopal. Characterizing the capacity region in multiradio multichannel wireless mesh networks. In Proc. of IEEE WiMesh, 2005.

D. Kotz and K. Essien. Analysis of a campuswide wireless network. In ACM MobiCom, pages 107118, 2002.

V. S. A. Kumar, M. V. Marathe, S. Parthasarathy, and
A. Srinivasan. Algorithmic aspects of capacity in wireless networks. In Proc. of ACM SIGMETRICS, pages 133144, 2005.

X. Lin and S. Rasool. A distributed joint channel assignment, scheduling and routing algorithm for multichannel ad hoc wireless networks. In INFOCOM, 2007.

X. G. Meng, S. H. Y. Wong, Y. Yuan, and S. Lu. Characterizing flows in large wireless data networks. In Proc. of ACM MobiCom, 2004.

A. Raniwala and T. Chiueh. Architecture and algorithms for an ieee 802.11based multichannel wireless mesh network. In Proc. of IEEE INFOCOM, 2005.
A. Raniwala, K. Gopalan, and T. Chiueh. Centralized channel assignment and routing algorithms for multi channel wireless mesh networks. Mobile Computing and Communications Review, 8(2):5065, 2004.