Optimization of Routing Algorithm in Wireless Mesh Networks

Bhupendra Kumar Gupta and [Link] Dept. of Computer Applications ITER, SOA University {bhpendragupta, biswamohanacharya}@[Link] Abstract
Wireless mesh networks (WMNs) have attracted increasing attention and deployment as a high-performance and low cost solution to last-mile broadband Internet access. Wireless mesh networks have emerged as a potential technology for nextgeneration wireless networking. WMNs have been widely accepted in the traditional application sectors of ad hoc networks because of their advantages over other wireless networks. With increasing demand for real-time services in the next generation wireless networks, quality-of-service (QoS) based routing offers significant challenges in WMNs. WMNs consist of mesh routers and mesh clients where fixed mesh routers form the multi-hop backbone of the network and it is assumed that each individual mesh client will follow the prescribed protocols. However, these mobile devices, owned by individual users, will likely do what is the most beneficial to their owners, i.e. act 'selfishly'. Traffic routing plays a critical role in determining the performance of wireless mesh networks. Routing in any network has a great impact on the overall network performance, thus a routing protocol or an algorithm for WMNs should be carefully designed taking into account the specific characteristics of that network. In addition, in wireless networks, serious unfairness can occur between users if the issue is not addressed in the network protocols or algorithms. In this paper, we formulate the problem of routing as a network optimization problem, and present a general LP (linear programming) formulation for modeling the problem. We propose the optimized algorithm for known traffic demand and then explain the performance ratio for this. The routing algorithms derived from these formulations usually claim analytical properties such as optimal resource utilization and throughput fairness. 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.

Manoj Kumar Mishra Dept. of Information Technology ITER, SOA University manojmishra@[Link]

transportation systems, and community networks etc. It consists of two types of wireless nodes namely Mesh Routers and Mesh Clients. Each node does not operate as a host only but also acts as a router, which forwards the packets on behalf of other nodes that may not be within the direct transmission range of their destination. WMNs dynamically self organize and self configure, with the nodes in the networks automatically, establishing and maintaining mesh connectivity among themselves. 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. The backbone of the wireless mesh network consists of mesh routers, which connect each other in an ad hoc manner via wireless links. The presence of backbone mesh routers and utilization of multiple channels and interfaces allow the wireless mesh network to have better capacity than that of the infrastructure-free ad hoc network formed by mesh clients directly. A special type of the mesh routers, referred to as gateway nodes, is capable of Internet connection, and other mesh routers and associated terminal clients have to access the Internet through the gateway nodes as given in the Fig-1.

1.1. Need for load balanced algorithms

Data communication in WMNs is possible along multiple hops, nodes that are in communication range of each other can communicate directly, while the nodes that are spatially disjoint uses other intermediate nodes to relay the packets. Application of such a network is in personal area networking, emergency operations such as search and rescue in disaster caused areas, policing and fire fighting, military applications such as on the battle field, civilian environment such as taxi cab networks, meeting rooms, sports stadium etc. Almost all routing protocols in one way or other, try to converge into shortest path routing. One of the advantages of using shortest path routing is that it is good for overall energy efficiency because energy needed to transmit a packet is directly proportional to path length or number of hops. But the shortest

1. Introduction
WMNs have become popular due to its universal networking capabilities. It supports a wide range of applications, such as public safety, emergency response communications, intelligent

978-1-4244-5612-3/09/$26.00 c 2009 IEEE

1150

Fig.1 Structure of WMNs path routing is restricted to use the same set of hops to route the data packets, thus causing some of the heavily loaded nodes and thus causing some of the nodes to die earlier resulting into holes in the network or even worst into partitioning of the network. Thus the need for load balanced routing emerges. A common routing performance metric with respect to a known traffic demand is resource utilization. For example, link utilization is commonly used for traffic engineering in the Internet [1], where the objective is to minimize the utilization at the most congested link. The existing research on optimal mesh network routing [2] usually aim to maximize the flow throughput, while satisfying the fairness constraints. In this formulation, traffic demand is reflected as the flow weight in the fairness constraints. We formulate the problem of routing as a network optimization problem, and present a general LP (linear programming) formulation for modeling the problem and then we propose the optimized algorithm for known traffic demand and explain the performance ratio for this. The performance ratio can be extended to develop the optimized algorithm under unknown (uncertain) traffic. The routing algorithms derived from these formulations usually claim analytical properties such as optimal resource utilization and throughput fairness.

2. Literature Review
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, a lot of research has been performed. The problem of wireless mesh network routing has been extensively studied in the existing literatures. Routing algorithms are proposed to

improve the throughput for wireless mesh networks via integrating MAC layer information [3], such as expected packet transmission time [4]. Joint solutions for channel allocation and routing are explored in [5] in a centralized fashion and in [6] 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. In [7] [8] the authors study the optimal solution of joint channel assignment and routing for maximum throughput under a multicommodity flow problem formulation and solve it via linear programming. The authors in [9] present bandwidth allocation schemes to achieve maximum throughput and lexicographical max-min fairness respectively. A rate limiting scheme to enforce the fairness among different local access points is discussed in [10]. 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 suitable for practical use under highly dynamic traffic situation. Distributed algorithms have been presented for joint scheduling and routing, and for joint channel assignment, scheduling and routing in [11]. These distributed algorithms only use local information for traffic routing and 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 traffic conditions. The 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. Our approach is also related to dynamic traffic engineering [12] in Internet and oblivious routing [13], which also considers the impact of demand uncertainty in making routing decisions. The major difference between our approach and these existing studies lay in the different network models of wireless mesh network, Internet and the problem formulations. In particular, traffic engineering tries to minimize the congestion (utilization) of the wired links of a network. In multi-hop wireless networks, 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. The model for the wireless mesh network is represented hierarchically as shown in Fig-2.

3. Network Model
1151

2009 World Congress on Nature & Biologically Inspired Computing (NaBIC 2009)

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 as , and use to represent the aggregated flow rate vector.

3.2 Interference Model & Schedulability

In a wireless network, packet transmissions are subject to location responsive interference. Here the assumptions are that all the mesh nodes have the uniform transmission range denoted by . Generally the interference range is larger than its transmission range. Here the interference range of a mesh node is denote as , where is a constant. In this paper, we consider the protocol model presented in [14]. Let be the distance between and such that . In the protocol model, packet transmission from node to is successful iff 1. The distance between these two nodes satisfies . 2. Any other node within the interference range of the receiving node , i.e., ,is not transmitting. If node can transmit to directly, they form an edge . We denote the capacity of this edge as which is the maximum data rate through edge . Let be the set of all edges. We say two edges interfere with each other, if they can not transmit simultaneously based on the protocol model. Further we define the interference set which contains the edges that interfere with edge . To study the throughput optimization routing problem, we first need to understand the constraint of the flow rates. Let denote the wireless link rate vector, where is the aggregated flow rate along wireless link . Link rate vector 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 . The link rate schedulability problem has been studied by several existing researchers, which lead to different models [15,16,17]. In this paper, we adopt the model in [16], In particular, [16] 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 the subset of , where each that has length is in set .In the following discussion we refer as the adjusted interference set of . Based on the results presented in [16] we have the following claims.

Fig. 2 Network model In wireless mesh network, local access points aggregate the traffic from mobile clients that are associated with them. They communicate with each other and also with stationary wireless routers network forming a multi-hop wireless backbone which forwards the user traffic to a gateway access point connecting to the Internet. In our discussion, local access point, gateway access point, and mesh routers are collectively called mesh nodes. Here the backbone of a wireless mesh network has been modeled as a directed grap , where each node represents a mesh node. Among these nodes, is the gateway access point that connects to the Internet. A directed edge denotes that can transmit to directly. We assume that all mesh nodes have a uniform transmission range denoted by . We denote as the distance between and . An edge . We also use to represent the length of edge . Let bit/sec be the data rate of edge , which is the maximum data that can be carried in a second along the edge .

3.1. 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 , where is the set of all aggregated flows. It is worth noting that although we consider only one gateway access point in this

1152

2009 World Congress on Nature & Biologically Inspired Computing (NaBIC 2009)

Claim 1. (Sufficient Condition of Schedulability) The link rate vector is schedulable if the following condition is satisfied: Eq.(1) where bit/sec is the data rate of edge . For ease of exposition, we assume that for all in the following discussion.

4. Problem Formulation
We know that is the aggregated traffic flow between local access points and the gateway. We use to denote the demand of flow and to denote the demand vector consisting of all flow demands. Consider the fairness constraint that, for each flow , its throughput being routed is in proportion to its demand . Our goal is to maximize (scaling factor) where at least amount of throughput can be routed for flow . We assume an infinitesimally divisible flow model where the aggregated traffic flow could be routed over multiple paths and we have used to denote the set of unicast paths that could route flow . Let be the rate of flow over path . Obviously the aggregated flow rate along edge is given by which is the sum of flow rates that are routed through paths passing edge . Based on the sufficient condition of schedulability in Eq.(1) of claim 1, we have Eq.(2) The throughput optimization routing with fairness constraint is then formulated as the following linear programming (LP) problem: Maximize Eq.(3) Subjected to the constraints Eq.(4) Eq.(5) , Eq.(6) Here the optimization objective is to maximize , such that at least units of data can be routed for each aggregated flow with demand . Inequality (4) enforces fairness by requiring that the comparative ratio of traffic routed for different flows satisfies the comparative ratio of their demands. Thus, the absolute value is scaling up or scaling down all demands, while stays unchanged. Inequality (5) enforces capacity constraint by requiring the traffic aggregation of all flows passing wireless link satisfy the sufficient condition of schedulability. This problem

formulation follows the classical maximum concurrent flow problem, which has also been used in Internet traffic engineering and load balancing routing. Note that the above problem formulation follows the classical maximum concurrent flow problem. Although being extensively used to study mesh network routing schemes under known and fixed traffic demand, such throughput optimization problem formulation is hard to extend to handle the case of uncertain demand. In light of this need, we proceed to study the congestion minimization routing. This differs from the throughput optimization problem where the traffic demand may not be completely routed subject to the constraints of the network capacity. Rather, the congestion minimization problem will route all the traffic demands, which may violate the network capacity constraint, and thus the goal is to minimize the network congestion. For defining above minimization problem we need to define as the number of wireless links a path passes in the adjusted interference set . Therefore the objective here is to minimize the aggregated congestion for all adjusted interference sets i.e. to minimize where be the congestion to each set for Subjected to the constraints that the total congestion over i.e. for any path for flow must be at least the congestion of flow and the second constraint is that the weighted flow congestion over its demand must be at least one. Therefore the minimization problem here can be modeled as follows Eq.(7) Minimize Subjected to the constraints Eq.(8) Eq.(9) where is the weighted flow congestion over demand . Based on the above dual problem we can write the following algorithm

4.1 Algorithm based on the above simplex problem

1. 2. 3. Initialize the congestion for each edge as . Initialize the traffic on all to zero. For each flow 3.1 Rout units of data by finding lowest congested path in the path set , then fill the traffic to this path to its bottleneck capacity. 3.2 Then update the congestion for the edges appeared in this path.

2009 World Congress on Nature & Biologically Inspired Computing (NaBIC 2009)

1153

3.3

Fill the traffic to flow until all units are routed.

5. Simulation Study
We evaluate the performance of our algorithm through simulation study. In the simulated wireless mesh network, mesh nodes are randomly deployed over a region, among which nodes are local access points that forward traffic for clients. Node which resides in the center of the deploy region is selected as the gateway router. Each mesh nodes has a transmission range of . The simulated network topology is shown in Fig-3.

wireless LAN at aggregating and forwarding client traffic. Thus, we select access points and assign their traffic traces to the local access points in our simulation. Fig-4 plots the time series of the traffic volume during one hour period at the same time of a day (12pm-1pm) from access points sample and derive its probability density function. Fig-5 plots the probability density function for the corresponding access points of Fig-4. or consecutive work days. We remove the weekend days from the traces due to their extreme low traffic volume. From the figure, we observe that the traffic at each access point is highly dynamic and unpredictable due to the insufficient level of aggregation. This observation motivates the need of mesh routing schemes that are aware of the traffic uncertainty. Based on the one-hour traffic volume data from the traces, we further derive the traffic demand distribution for each access point. We divide the obtained raw traffic volume into finite collection of traffic demand ranges. This algorithm 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 the given algorithm to adapt to the new demand. This solution yields the optimal routing result at the cost of frequent routing computation and update.

6. Conclusions and Future Work

Fig.3 Mesh Network Topology In this paper we have studied the throughput optimization routing problem for wireless mesh networks, which is different from existing algorithm with the assumption of certain traffic demand known a-priori. In order to maximize the outgoing flow we have designed the maximized simplex problem where we have maximized the scaling factor keeping in mind the constraints. To achieve this objective the corresponding minimized problem for congestion has been designed and extensive simulation results confirm our claim. Here we have considered the certain traffic demand, which may not be the real scenario always as the demand for traffic changes dynamically. Hence in future we aim to extend our claim for uncertain traffic demand to focus on the real scenario.

Fig.4: Traffic Time Series

Fig. 5: Traffic Demand Distribution To simulate the traffic demand at each local access point, we analyze the traces collected in the campus wireless LAN. By analyzing the log trace at each access point, we are able to derive its incoming and outgoing traffic volume in a -minute period. We argue that the local access points of a wireless mesh network serve a similar role as the access points of

References
[1] X. Lin and S. Rasool, A distributed joint channel assignment scheduling and routing algorithm for multichannel ad hoc wireless networks in INFOCOM, 2007.

1154

2009 World Congress on Nature & Biologically Inspired Computing (NaBIC 2009)

[2] Y. Azar, E. Cohen, A. Fiat, H. Kaplan, and H. Racke. Optimal oblivious routing in polynomial time. J. Comput. [Link]., 69(3), 2004. [3] S. Biswas and R. Morris. Exor: opportunistic multi-hop routing for wireless networks, in Proc. of ACM SIGCOMM, pages 133144, 2005. [4] R . Draves, J. Padhye and B. Zill, Routing in multi-radio multi-hop wireless mesh networks, in Proc. of ACM Mobicom, pages 114128, 2004. [4] 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. [6] 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. [7] 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. [8] M. Kodialam and T. Nandagopal, Characterizing the capacity region in multi-radio multi-channel wireless mesh networks, in Proc. of IEEE WiMesh, 2005. [9] J. Tang, G. Xue, and W. Zhang, Maximum throughput and fair bandwidth allocation in multichannel wireless mesh networks, in Proc. of IEEE INFOCOM, 2006. [10] 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. [11] X. Lin and S. Rasool, A distributed joint channel assignment, scheduling and routing algorithm for multichannel ad hoc wireless networks, in INFOCOM, 2007. [12] 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. [13] Y. Azar, E. Cohen, A. Fiat, H. Kaplan, and H. Racke, Optimal oblivious routing in polynomial time, J. Comput. Syst. Sci., 69(3), 2004. [14] D. Aguayo, J. Bicket, S. Biswas, G. Judd, R. Morris, Link-level measurements from an 802.11b mesh network, in ACM Annual Conference of the

Special Interest Group on Data Communication (SIGCOMM), August 2004, pp. 121131. [15] K. Jain, J. Padhye, V. Padmanabhan, and L. Qiu, Impact on interference on multi-hop wireless network performance. in Proc. of Mobicom , September 2003. [16] V. S. A. Kumar, M. V. Marathe, S. Parthasarathy, and A. Srinivasan. Algorithmic aspects of capacity in wireless networks, in Proc. of ACM SIGMETRICS, pp 133144, 2005. [17] 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. [18] I. Chlamtac, M. Conti, J. Liu, Mobile ad hoc networking: imperatives and challenges, Ad Hoc Networks 1 (1) (2003) 1364. [19] I.F. Akyildiz, W. Su, Y. Sankarasubramaniam, E. Cayirci, Wireless sensor networks: a survey, Computer Networks 38 (4) (2002) 393422. [20] I.F. Akyildiz, I.H. Kasimoglu, Wireless sensor and actor networks: research challenges, Ad Hoc Networks 2 (2004) 351367. [21] L. Krishnamurthy, S. Conner, M. Yarvis, J. Chhabra, C. Ellison, C. Brabenac, E. Tsui, Meeting the demands of the digital home with high-speed multi-hop wireless networks, Intel Technology Journal 6 (4) (2002) 5768. [22] S. Tierney, Mesh Networks, whitepaper of [Link]. [23] J. Jun, M.L. Sichitiu, The nominal capacity of wireless mesh networks, IEEE Wireless Communications 10 (5) (2003) 814. [24] R. Poor, Wireless mesh networks, Sensors, February 2003. [25] R. Poor, Wireless mesh links everyday devices, Electronic Engineering Times, 5 July 2004.

2009 World Congress on Nature & Biologically Inspired Computing (NaBIC 2009)

1155