Optimal Routing Under The High Dynamic And Uncertain Traffic In WMN

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.

1. INTRODUCTION.

   Wireless mesh networks have attracted increasing attention and deployment as a high-performance and low cost solution to last-mile 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 optimization-based 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.

2. 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 multi-commodity flow problem formulation and solves it via linear programming. The work of [21] presents bandwidth allocation schemes to achieve maximum throughput and lexicographical max-min 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 campus-wide 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 end-host multi-homing. 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.

3. 1. Network Model

      Figure 1. Illustration of Wireless Mesh Network

      We consider a multi-hop 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 multi-hop 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.

   2. 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 inter-mesh-router 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.

   3. Interference Model and Schedulability

      In a wireless network, packet transmissions are subject to location-dependent 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.

4. 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 LP-solver. 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 Algorithm-I 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.

5. 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 non-zero 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

6. 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 (Algorithm-I), while the last one employs the algorithm under uncertainty demand (Algorithm-II).

• 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 Algorithm-I to adapt to the new demand. This solution yields the optimal routing result at the cost of frequent routing computation and update.

• Average-Demand-based 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.

• Uncertainty-aware 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. Uncertainty-aware solution demonstrate the same trend, but continuously outperforms the average-demand 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 average-demand 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 uncertainty-aware 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

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.

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

2. N. Thompson, G. He, and H. Luo. Flow scheduling for end-host multihoming. In Proceedings of IEEE INFOCOM, 2006.

3. 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.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

18. M. Kodialam and T. Nandagopal. Characterizing the capacity region in multi-radio multi-channel wireless mesh networks. In Proc. of IEEE WiMesh, 2005.

19. D. Kotz and K. Essien. Analysis of a campus-wide wireless network. In ACM MobiCom, pages 107118, 2002.

20. 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.

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

22. 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.

23. A. Raniwala and T. Chiueh. Architecture and algorithms for an ieee 802.11-based multi-channel wireless mesh network. In Proc. of IEEE INFOCOM, 2005.