An Efficient Load Balancing Techniques for Wireless Mesh Networks

An Efficient Load Balancing Techniques for Wireless Mesh Networks

1. Anbu Ananth Dr. K. Selvakumar

   Assistant Professor & Department of CSE Associate Professor & Department of CSE Annamalai University, India Annamalai University, India

   Abstract Recent years, wireless network is become a very hot topic for researchers. To overcome the problems present in unipath routing, using multiple paths is one way to improve the performance of routing protocols which address the problems of scalability, security, lifetime of network and instability of wireless transmission. The availability of multiple routes enables a more reliable transmission in the frequently changing wireless network environment e.g., in the case of a sudden relaying node breakdown. And also, the multi-path routing provides load balancing, which may be especially valuable in MANETs due to limited resources of these networks. MP-OLSR is one of the multipath routing protocols. In this paper, we do a modification to the existing MPOLSR routing protocol by changing the Dijkstra's algorithm. The route computation is based on the modified Dijkstra's algorithm, which computes routes quickly than its predecessor. The idea of the algorithm is to use the cost function to get the disjoint paths quickly.

   Keywords Load balancing, Wireless Mesh Network, Multipath OLSR.

   1. INTRODUCTION

      The recent advance of wireless communication technologies has prompted a flourish of a new kind of multi-hop wireless network architecture, called wireless mesh networks (WMNs). WMNs typically comprise a number of static wireless routers that are attached to reliable sources of energy. The wireless routers are interconnected with each other via wireless links and provide communication services to mobile or static users in their vicinities. Some of the routers are directly connected to a fixed infrastructure (i.e., a wired network like the Internet) and serve as gateways for other wireless routers.

      Wireless Mesh Network is a promising technology which is mainly emerged to provide low cost broadband internet access to a large community of users. It is designed to trounce the shortcomings of wireless ad-hoc networks. Figure 1 Mesh network architecture contains mesh clients, routers and gateways. Mesh routers have least mobility and form the backbone of wireless mesh network. Each node in the network operates not only as a host but also as a router, forwarding packets on behalf of other nodes that may not be within direct wireless transmission range of their destinations. Clients can be of users laptops and PDAs which are either mobile or stationary. Mesh routers are quasi static in nature. The clients can connect to the external network through the gateway nodes.

      Fig 1:Architectural Diagram of WMN

      One of the main concerns for WMNs is the reduction of the overall network capacity due to interferences between adjacent nodes [2]. To mitigate wireless interferences, several techniques can be used including multiple radios [2], directional antennas and MIMO (multiple input multiple output). However, such physical layer solutions alone are not enough. To maximize the network utilization while preserving fairness requirements, efficient routing scheme is critical [1]. To address this need, we propose a simple and effective load- balanced routing scheme, via which the network utilization is maximized while providing fairness and bandwidth guarantees.

   2. LITERATURE REVIEW

      Most of the proposed multipath protocols are based on the single-path version of an existing routing protocol: AODV and AOMDV [11], DSR and SMR [12].

      Most of these protocols are based on a reactive routing protocol (AODV [4] or DSR [3]). In fact, reactive multipath routing protocols improve network performances (load balancing, delay and energy efficiency), but they also have some disadvantages:

      Route request storm: Multipath reactive routing protocols can generate a large number of route request messages. When the intermediate nodes have to process duplicate request messages, redundant overhead packets can be introduced in the networks [13].

      Inefficient route discovery: To find node-disjoint or link disjoint paths, some multipath routing protocols prevent an intermediate node from sending a reply from its route cache [14]. Thus, a source node has to wait until a destination replies. Hence, the route discovery process of a multipath routing protocol takes longer compared to that of DSR or AODV protocols.

      Compared to reactive routing, the proactive routing protocols need to send periodic control messages. Hence, several researchers consider proactive routing protocols as not suitable for ad hoc networks [5]. For a network with low mobility and network load, the reactive routing protocols generate fewer control messages. However, given a network with high mobility and large traffic, the cost of route discovery and route maintenance will rise significantly.

      On the other hand, the proactive protocols try to keep a routing table for all possible destinations and therefore provides a transmission delay shorter than reactive routing protocols [15]. Furthermore, because the proactive protocols try to maintain the information of the whole network by periodical control messages, they can discover multiple routes more efficiently without much extra cost.

      Mobile Mesh protocol [18], [19] describes schemes for link discovery, routing and border discovery in wireless mesh networks, but does not consider load balancing. In [20] authors describe choosing a high throughput path between a source and a destination for community wireless networks. Raniwala et al.

      1. discuss load balancing in wireless mesh networks with nodes having multi-channel radios, but these radios would require multiple cards and antennas for each node and would be expensive to deploy. Hespanha et al. [22] formulate secure load balanced routing in networks as a zero-sum game between the designer of the routing algorithm and an adversary that attempts to intersect packets. They show that for some versions of the game, the optimal routing policies also maximize the throughput between the source and the destination node.

         There is extensive literature on optimization problems on dynamic and static load balancing across meshes [23]. Optimal load balancing across meshes is known to be a hard problem. Akyildiz et al. [6] exhaustively survey the research issues associated with wireless mesh networks and discuss the requirement to explore multipath routing for load balancing in these networks. However, maximum throughput scheduling and load balancing in wireless mesh networks is an unexplored problem.

         Some studies exploit the advantage of multiple path routing. In [7], Jain et al. consider the problem of optimal multi-path routing, where the interferences are modeled by a conflict graph. A similar problem is addressed by Kodialam and

         Nandagopal in [8]. This study deals with the joint problem of routing and scheduling of multi-path flows, assuming that each wireless station is equipped with a single radio but the stations use orthogonal channels in order to avoid interferences.

         In [9], the authors extend their result for the case of multiple radios. These studies have shown that multi-path routing maximizes overall traffic flow while providing fair service and bandwidth guarantees. However, these methods face difficulties in the traffic management, since the traffic between each sourcedestination pair may be divided into multiple small flows and they generate high communication and computation overhead on th network nodes [10,24]. In [24], Ganjali and Keshavarzian claim that in practice the load distribution obtained by multi-path routing is essentially similar to the single path routing, unless a very large number of paths are used (which is practically infeasible).

   3. MULTIPATH INTRODUCTION

      The multi-path routing approach experimentally evaluated in this paper is based on solutions presented in [1, 7]. The idea of novel route calculation technique is based on a multiple use of the shortest path algorithm for a specially modified topology graph. Instead of running the algorithm for the case of the computing node as the origin of any route, all the neighbors of the computing node, except the one being currently examined as a possible next hop, are removed from the topology graph along with their adjacent edges. Then the Dijkstras shortest path algorithm is run for the chosen neighbouring node as a route origin [7]. The procedure is repeated for each neighbor of the computing node. As a result, the computing node obtains several routing tables (one table per neighbor), which can be easily merged into its final routing table with multiple entries for every possible destination. The implemented version of modified protocol provides the routing entries containing information on the destination node address, the next-hop node address, and the number of hops on the shortest route through a given next hop to a given destination [1].

      The modified route calculation algorithm can be described as a diagram as shown in Figure 2. The example of the algorithm execution is illustrated in Figure 3.

      Fig. 2. Algorithm for calculation of multiple routes

      The OLSR protocol extension has been designed to cooperate with backpressure like scheduling. As a result of modified protocol operation, the transmitting node is able to provide the backpressure based scheduler with the possible choices of the next hop for every destination node. The solution is a variation of the unconstrained backpressure approach (the flooding). It is aimed at the restriction of all possible next-hop choices to a collection of reasonable choices for a given destination all the neighbors of the computing node, for which the destination node is unreachable without further contribution from one of the remaining neighbors of the computing node, are excluded from the set of proposed next hops.

      Given the fact that a routing decision is made on each hop on the path, the proposed solution is not fully loop-resistant. Moreover, the topology information can be delayed or may not be synchronized. However, in such cases the backpressure rule can help avoid routing decisions resulting in loops or backward traffic, since the backlog levels never increase on a path from the source to the destination for a given flow [7].

      Flexibility is one of the additional advantages of the proposed solution.

      Fig. 3. An example of the multiple routes calculation (for node 2)

      Firstly, the routing table can be easily recalculated and some enhancements for our method can be introduced. Such enhancements can be based, e.g., on eliminating entries whose shortest routes are too long, which is particularly valuable when the delay factor is essential.

      Secondly, the number of hops can be replaced by some other metric (e.g., ETX based), which enables the application of various policies for routes exclusion. As stated in [7], the important advantage of the proposed multi-path extension of OLSR is the fact that all the possible next hops for each destination are calculated jointly at a stroke (similarly as in the case of the single-path Dijkstras algorithm used in the standard version of OLSR [6]).

      Modified Dijkstras Algorithm

      We simply apply Dijkstras algorithm and maintain an array count[]. At any step of the algorithm, if v S, then count[v] denotes the number of shortest paths from s to v. When we are relaxing an edge (u,v) with u S; v S, there are three cases to be considered.

      If d[v] > d[u]+w(u, v), then any shortest path from s to u, coupled with the edge (u, v), can be a potential shortest path from s to v. Thus, we set count[v] = count[u].

      On the other hand, if d[v] = d[u] + w(u, v), then we keep track of every existing potential shortest path to v, plus we add the number of shortest paths to u coupled with the edge (u, v). Thus, we set count[v] = count[v]+count[u].

      Finally, if d[v] < d[u], we need not update any information. The correctness of our algorithm follows from exactly the same

      0.25

      0.2

      0.15

      0.1

      0.05

      Routing Load

      argument that is used to prove correctness of Dijkstras. The running time is O(E log V ).

   4. RESULTS & DISCUSSION

      Packet Delivery Ratio %

      Packet Loss

      For evaluating the performance of the Modified MPOLSR, simulations are performed using Network Simulator(NS2). The simulation scenarios are modelled with network parameters which represents the real time implementation. During all the simulations the network parameters are kept constant but only the size of the network i.e the number of nodes are alone changed to better evaluate the performance of the proposed algorithm. The through, packet loss, packet delivery ratio and routing load are taken as performance metrics. During each simulation the trace file is generated and using perl scripts the values are calculated. The throughput is calculated by finding the ratio between the amount of data travelled during the simulation period and the duration of the simulation and is expressed in kilo bytes per second(kbps). The packet loss which reflects the real performance of the routing algorithm is calculated by finding the difference between the number packets originating from the source node and the number of data packets reaching the destination. The packet delivery ratio is the ratio between the number of packets sent to the number of packets received. The routing load is the ratio between the number of routing packets sent to the total number of the sent packets. The routing load depicts the impact of the additional load put over the network by the routing packets. The following parameters were used to build the simulation environment the MAC layer is modelled using IEEE 802.11 standard and the physical layer is implemented with the wireless physical channel. The Droptail queue method with Priority management is utilized to manage the waiting and incoming data packets at the intermediate nodes. The size of the data packets transmitted during the simulation is chosen to be 512 bytes. If larger the size of the data packets then the amount of energy spent to transmit the data packets will be higher so a moderate size of the data packet is chosen. The size of the simulation area is chosen to be 500X500 which is enough to hold the maximum number of nodes during the simulation.

      9

      8

      7

      6

      5

      4

      3

      2

      1

      0

      100

      98

      96

      94

      92

      90

      88

      20 30 40 50 60

      No. of Nodes

      0

      Fig.5 Node Vs Routing Load

      20 30 40 50 60

      No. of Nodes

      Fig.6 Node Vs Packet Loss

      20 30 40 50 60

      No. of Nodes

      AODV

      OLSR MMPOLSR

      AODV OLSR MMPOLSR

      AODV OLSR MMPOLSR

      0

      AODV

      OLSR MMPOLSR

      500

      400

      300

      200

      100

      Throughput in kbps

      Fig.7 Node Vs Packet Delivery Ratio

      20 30 40 50 60

      No. of Nodes

      Fig.4 Node Vs Throughput

      During all the simulations the constant bit rate type of traffic is used and random way point movement is used for the node movement. The simulations were performed with 20, 30, 40 and 50 numbers of nodes using both OLSR and Modified MPOLSR and the results are tabulated below. The results

      indicate that the Modified MPOLSR outperforms the OSLR by all the metrics. In Fig.6 shows that the packet loss is greatly reduced in the Modified MPOLSR when comparedto OLSR in all the simulation scenarios. In Fig.7 the PDR of Modified MPOLSR is higher when compared to OSLR. Fig.4 shows that the throughput is increased which represents that the Modified Dijkstra algorithm is performing better with varying network size. The multipath nature of the proposed routing algorithm guarantees the delivery of the data packets originating from the source node therefore the Packet loss is reduced even when the network size is increasing. The running time of the Modified MPOLSR is lesser when compared to its counterparts. The running time of the Modified MPOLSR is O(E log V )normally the MPOLSR consumes O(E2 log V).

   5. CONCLUSIONS

The usage of multiple path routing protocol instead of single path is increased nowadays. Many protocols were developed as a single path routing protocol at the very beginning. It means that from the source to the destination only one path is on duty. But to increase the reliability of the data transmission, other kind of protocols was proposed: multipath routing protocol. In this proposed work it is been tried to use more than one path to send data. So the main objective of these protocols is how to find the reliable paths and ensure load balancing. The multiple paths is disjoint (all the links are combination of the above 2 kinds). These paths can be used as backup route or at the same time for parallel data transmission. To decrease delay and to maximize network life time are also goals included in the proposed multipath protocols.

The proposed modified multipath OLSR is also compared with AODV routing protocol which exhibits lesser performance when compared to the proposed Protocol.

REFERENCES

1. R. Bruno, M. Conti, E. Gregori, Mesh networks: commodity multihop ad hoc networks, IEEE Commun. Mag. 47 (3) (2005) 123131.

2. R. Draves, J. Padhye, B. Zill, Routing in multi-radio, multihop wireless mesh networks, in: Proceedings of ACM Mobicom04, Philadelphia, PA, USA, September 2004, pp. 114128.

3. D.B. Johnson, Y. Hu, D.A. Maltz, IETF Request for Comments: 4728, The Dynamic Source Routing Protocol (DSR) for Mobile Ad Hoc Networks for IPv4, February 2007.

4. C. Perkins, E. Royer, Ad-hoc on-demand distance vector routing, in: Second IEEE Workshop on Mobile Computing Systems and Applications, 1999, pp. 90100.

5. M. Tarique, K.E. Tepe, S. Adibi, S. Erfani, Survey of multipath routing protocols for mobile ad hoc networks, Journal of Network and Computer Applications 32 (2009) 11251143.

6. I. Akyildiz, X. Wang, W. Wang, “Wireless Mesh Networks: A Survey'', Computer Networks Journal 47, (Elsevier), March 2005. pp. 445-487.

7. K. Jain, J. Padhye, V. Padmanabhan, L. Qiu, Impact of interference on multi-hop wireless network performance, in: Proceedings of ACM Mobicom03, San Diego, CA, USA, September 2003, pp. 66 80.

8. M. Kodialam, T. Nandagopal, Characterizing the achievable rates in multihop wireless networks, in: Proceedings of ACM Mobicom03, San Diego, CA, USA, September 2003, pp. 4254.

9. M. Kodialam, T. Nandagopal, Achievable rates in multi-hop wireless mesh networks with orthogonal channels, IEEE/ACM Transactions of Networking, September 2005, in preparation.

10. P. Pham, S. Perreau, Performance analysis of reactive shortest single-path and multi-path routing mechanism with load balance, in: Proceedings of IEEE INFOCOM03, Sun Francisco, CA, USA, 2003.

11. M.K. Marina, S.R. Das, On-demand multi path distance vector routing in d hoc networks, in: Proceedings of the Ninth International Conference on Network Protocols, IEEE Computer Society, Washington, DC, USA, 2001, pp. 1423.

12. S. Lee, M. Gerla, Split multipath routing with maximally disjoint paths in ad hoc networks, Helsinki, Finland, 2001, pp. 32013205.

13. Z. Yao, J.J. Jiang, P. Fan, Z. Cao, V. Li, A neighbor table based multipath routing in ad hoc networks, in: 57th IEEE Semi Annual Vehicular Technology Conference, vol. 3, 2003, pp. 17391743.

14. Z. Ye, S.V. Krishnamurthy, S.K. Tripathi, A framework for reliable routing in mobile ad hoc networks, in: IEEE INFOCOM, San Francisco, CA, USA, 2003, pp. 270280.

15. E. Cizeron, S. Hamma, A multiple description coding strategy for multi-path in mobile ad hoc networks, in: International Conference on the Latest Advances in Networks (ICLAN), Paris, France, 2007.

1. http://www.oreillynet.com/pub/a/wireless/2004/01/2 2/wirelessmesh.html

2. www.mitre.org/work/tech_transfer/mobilemesh/

3. R. Draves, J. Padhye, B. Zill, Routing in Multi- Radio, Multi-Hop Wireless Mesh Networks,MobiCom04, Sept. 2004, Philadelphia, PA

4. A. Raniwala, T. Chiueh, Architecture and Algorithms for an IEEE 802.11-Based Multi-Channel Wireless Mesh Network, IEEE Infocom Mar 2005, Miami, FL.

5. J. Hespanha, S. Bohacek, Preliminary Results in Routing Games, American Control Conference,Arlington, VA, June 2001, vol. 3, pp. 1904-1909

6. G. Horton, "A multi-level diffusion method for dynamic load balancing", Parallel Computing. 19 (1993), pp. 209-229

7. Y. Ganjali, A. Keshavarzian, Load balancing in ad hoc networks: single-path routing vs. multi-path routing, in: Proceedings of IEEE INFOCOM03, Hong Kong, 2004.