Load balancing In Wireless Mesh Networks Using liquid–Simulated Algorithm

Load balancing In Wireless Mesh Networks Using liquid–Simulated Algorithm

• 1.
  1 Load balancing InWireless Mesh Networks Using liquid –Simulated Algorithm Eshetu Gusare Desisa Shaik Janbhasha College of Computing and Informatics College of Computing and Informatics Department of Computer science Department of Computer science harmeekoo2011@gmail.com afreen.jbasha@gmail.Com Assosa University, Assosa , Ethiopia. Assosa University, Assosa, Ethiopia. Abstract There are many routing approaches have been borrowed from mobile ad hoc network to achieve routing solutions in wireless mesh network. WMN was developed for reliable data communication and load balancing. AODV provides loop-free routes even while repairing broken links. On this paper, we propose a hierarchical routing framework which is adapted to a wireless mesh network (WMN) environment and ensures the most critical issue in the wireless network: load-balancing. We simplify clusters formation and maintenance procedure, propose limited topology broadcasting mechanism allowing WMC to choose the best path to a WMC in adjacent cluster, and connect to a number nearby WMR. Basing on that routing framework we propose a liquid-simulated algorithm to keep load-balances between WMRs. Keywords: Routing protocol; Load balancing; Wireless Mesh Network; algorithm 1. Introduction There are three types of wireless mesh network (WMN) architecture [1]: Infrastructure/backbone, Client WMNs, and Hybrid WMNs. A client WMN is simply a Mobile ad-hoc network (Manet). Infrastructure/backbone WMN is composed of conventional wireless nodes connected through wireless mesh routers. With many well-known downsides, these two architectures will soon be replaced by the hybrid WMN architecture. In this architecture, there are two distinct layers (Fig.1), they are: an ad hoc network which is composed of wireless mesh clients (WMC) and WMRs, with backbone connection between WMRs. WMN has distinct constraint between two types of nodes: WMRs and WMCs. WMCs have limited power resources and may be mobile. WMRs have minimum mobility and do not have strict constraint on power. For now, the term WMN in this paper will refer to Hybrid WMN. By nature of the hierarchical architecture, hierarchical routing is particularly worthy for this network. Hierarchical routing in wireless network is well researched by many papers and is concluded by [5]. To use this routing protocol, only a few points should be considered. Because of limited constraints, WMR should be a cluster-head (CH), and so clustering algorithm could be simplified to an algorithm that allows WMC to choose a WMR with minimal cost as its CH. Obviously, hierarchical routing implemented in this network must be much more reliable than one in Manet. However, more things have to be done in order to address some underlying problems.
• 2.
  2 Fig 1: WirelessMesh Network-Hybrid Architecture. Using a normal approach for hierarchical routing presented above, traffic generated at any WMC will always be routed to WMR (as CH) and then go to a destination even if they are adjacent clusters and routing packets through WMC to the destination may be better. For example in Fig.2, when we need to route packets from node 8 to 3, directed route from nodes 8 to 7 to 3 may be better than the route over CHs j and i. To solve this problem, we can have two approaches, proactive and reactive. In reactive approach, let source node ask cluster gateway or CH to know which way, through cluster gateway (CG) or through CH, should be better. In proactive approach, source node should know proactively all WMC that should be directly reached. To do this, the source node can simply broadcast its link-states to all nodes in its entire adjacent cluster. For example, node 9 will broadcast its link-states to all nodes in cluster j. But, this is a trivial solution. Because only part of adjacent cluster j needs to know the links state of 9, the rest won’t need it. They will use the backbone link over CH, for example, in the case of node 4. Also, in wireless network being limited bandwidth, load balancing is always a problem. Especially in WMN when a WMR have to serve a number of different connection from WMCs concurrently. This issue in Manet has been investigated by many papers. But mainly, the problem is not solved in WMN. Load- balancing in WMN becomes much more complicated in comparison with Manet in terms ofarchitecture layers of network and the large number of nodes in network. We have to deal with load-balancing in Client Tier (CT), Router Tier (RT) and controlling load that imposed by WMCs to each WMR. Because WMR is the most sensitive node in the network, in this paper, we will concentrate on problems of controlling load from WMC to WMR to balance traffic among WMRs. Fig 2:Example of two adjacent clusters We consider WMR and the set of WMCs around it as a cluster. Each WMC can belong to a number of WMR; these WMCs will create an overlapped area between clusters. By deciding which WMC belongs to which cluster, we can adjust the traffic of the overlapped cluster and thus keep load-balance between WMR. A solution to load-balancing uses an on-line algorithm presented in [6]. Online algorithm is a fast and low-cost algorithm but it only solves problems through local point of view and there is no guarantee on the global optimization result. In this research, basing on the idea of algorithm in [13], [14], we develop a liquid simulated algorithm to obtain a global optimal solution: WMC in overlapping areas is adjusted such that the whole network can reach directly to an optimal distribution of WMC. To support for the load- balancing algorithm, we choose a proactive
• 3.
  3 approach for therouting problems declared above. Since WMR is CH, a simple procedure for cluster formation and maintenance and a limited topology broadcasting method is proposed to reduce unnecessary broadcasting. 2. Related Work Hierarchical routing is known as a precious routing method in Manet because of ability to solve scalability problem. Many instance of this routing mechanism are presented in [2]. [3] investigated in control overhead in hierarchal routing. Beside, it also gives us an overall view and main characteristics of this mechanism. Developed from idea of using hierarchical mechanism, [3] and [4] proposeshierarchical routing protocols for WMN. In [3], network is organized into zone around WMR and use proactive method in both cluster and between CH. Traffics is routed over the backbone, even between two neighbors-clusters. In [4], authors studied network scenario with cluster size is 1- hop and they proposed two type of routing mechanism: using lower tier – cluster member tier and using backbone tier. They use reactive approach at both lower tier and higher tier. Location Service to manage mobility is not used. Usually, there are two approaches to Load-balancing in Manet, routing metric approach and flow control approach. In routing metric approach, for example [8], a new routing metric is proposed to avoid heavy load path. In flow control approach, load-balancing problem is formulated as a flow control problem with objective function is maximization throughput [7]. By jointing scheduling and routing, author provides a nice result on load balancing in backhaul network: load of nodes are the same if they have the same distance to the base station. Besides, in [6], author investigated load- balancing for channel assignment problems and modeled it as an online problem for temporary tasks with unrelated processors. Channels will be assigned to the most available base-station. Authors in [13] and [14] consider load at a nodes in the network as liquid level. Liquid can flow from high level node to low level nod. When liquid stop flowing, that mean there is no difference of liquid level between nodes, load- balance state is made. A simple algorithm is also proposed in [14] to solve this problem. 3. Implementation 1. Topology Broadcasting Topology control proposed in this paper strictly follows framework presented in [5]. Only the changed parts are present in this paper. Topology broadcasting in WMN includes two parts: topology broadcasting at CT and topology broadcasting at RT. At RT, with limited mobility of the WMRs, topology is rarely changed, packet control overhead for maintenance topology of WMRs is low. Proactive routing protocol [2] for ad hoc network should be used here. They are Wireless Routing Protocol [9] or Destination- Sequenced Distance Vector Routing [10]. At CT, things seem to be more complicated. At first, we look at the main idea behind this topology broadcasting procedure. Assume that we have two adjacent cluster presented in Fig.3. Broadcasting link state to adjacent cluster’s members permits cluster member chose the best way to the destination node not always have to use backbone links. Fig 3: Path between two WMC
• 4.
  4 From point ofview of node n, path pnm is efficient only When Thus, we can have two constraints on broadcasting:  Link state of a Ci will be broadcasted within its cluster ƒ  Equation (1) will limit topology broadcasting of Ci to its adjacent clusters. Implementation of proposal routing protocol uses Linkstates broadcasting technique and Dijkstra’s shortest path algorithm. Above constraints are done by adding more information in the broadcasting packet, routing tables and several simple checking steps. Each WMR will hold two tables, cluster member table called ClTb and a table for topology control at RT called RTTb. RTTb is updated by using a proactive protocol as mentioned earlier. ClTb is update when a WMC requests to joint the cluster. At CT, each WMC will also hold two tables, WMC table called WCTb and WMR table called WRTb. WRTb contains two valid shortest paths to WMRs. WCTb contains all valid path from that WMC other WMC within its cluster and adjacent cluster. Topology broadcasting in this routing protocol including two phase: Cluster formation, when all table are empty, and cluster maintenance. a. Cluster formation CH-Claim packet is broadcasted from each WMR to its neighbor WMCs. CH-Claim packet of Ri contains {idi, Di, Seq}. Di is distance from WMC to the WMR. Seq is identification of the claim packet. A WMC receives a CH-Claim packet it should do as follows  Update distance Di according to the cost of the link it receives the packet. Record packet in to its memory and forward the updated packet.  After timeout to, check the memory to getsmallest but larger than the primal one and also satisfies kshort condition. b. Limited Topology Broadcasting Link state now will be broadcasted by all member of a cluster. Overlapped WMC will hold topology of both of overlapped clusters. Topology is hold in WCTb. Overlapped WMC Cg on the border of cluster when receives a link state update from a cluster will send packet P to all its neighbors on the other cluster. In that, idr is cluster id, idi is WMC id. P is sent by building a border-casting tree [11]. At a WMC Cn in the cluster of Cm, Cn also update the packet P and do little bit different with normal behavior of border-casting: it follows border-cast only when (1) is satisfied. Otherwise, itdrops the packet. At any node satisfies (1), WCTb is updated. P’ is updated respecting to the current path length to the changed node mi mg += pppgi . Fig 4: Example of topology broadcasting and overlapped clusters. Figure 4 gives an example of topology covering by proposed mechanism with 2-short. Nodes in gray are covered by link state broadcasting of node 8. This example present all principal of the routing protocol.
• 5.
  5 c. Complexity Complexity ofthe topology broadcasting at CT is the same as hierarchical routing with two layers, at RT is the same as proactive routing in Manet. Table 1 shows complexity of the routing protocols. K is maximum number of node in a cluster. I is routing update interval. D is maximum radius of clusters. Any WMC can reach WMCs in adjacent cluster on a shortest path with proactive method. Overhead of link state updated is minimize by eliminate update to unnecessary nodes. 2. Load-balancing in WMN: The total load Φi at cluster Zi includes traffic from other WMR R Φi and traffic C Φi from WMC withinZi: Φ+Φ=Φ CR . If we assume that condition for output flow of all Ri in the network is the same, load-balancing problem will be: Minimize max{ Φ−Φ ji } with Z, Z ji∈∀ V (2) To adjust traffic Φ , we can adjust both of two components. In this paper, we let R Φi as it is and just concentrate on adjusting C Φi to solve problems (2). We approach C Φi from the traffic generated by each cluster, not from traffic of a separate WMC. Traffic of overlapped areas is controlled to get adapted to available capacity of WMRs. 4. Experimental Results We apply the algorithm to find the optimal solution of a network with three overlapped clusters given in Table 3. The Fig.8 shows that, traffic of clusters reach the most balance state. Fig 5: Traffic at clusters while applying algorithm
• 6.
  6 5. Conclusion In thispaper, we proposed a hierarchical routing framework basing on the well-known hierarchical routing frameworks. It includes a simple cluster formation procedure and limited topology broadcasting mechanism. That routing framework allows any WMC to choose the best path to another WMC in adjacent cluster and it also creates up overlapped clusters for load-balancing control. Basing on overlapped clusters, we proposed a liquid- simulated algorithm to control load-balancing of WMR by distributing traffic generated from overlapped appropriately to WMR. The fact we still have many further problems after this paper. The liquid-simulated algorithm proposed in this paper gives us a nice result. But coverage speed and complexity of algorithm, some of the most important property of network algorithm, are not studied yet. Model (2) may not capture entirely load-balancing problem in WMR. Some assumptions may not exist in the real network. They are assumptions on output condition of flows from WMR, traffic generation rate of WMC in overlapped areas. To make the model more available in practice, the future work must deal with a general case, without the assumptions. Distributed Computing archive Volume 63 , Issue 2 (February 2003) Special issue on Routing in mobile and wireless ad hoc networks Pages: 110 - 122 Year of Publication: 2003 ISSN:0743-7315 [4] Tsung-Chuan Huang, Chun-Kai Liao, Chyi-Ren Dow ”Zone-based hierarchical routing in two-tier backbone ad hoc networks", Networks, ICON 2004 Proceedings, 12th IEEE International Conference on 16- 19 Nov. 2004, On page(s) 650- 654 vol.2 ISSN: 1531-2216 [5] John Sucec, Ivan Marsic, “Hierarchical Routing Overhead in Mobile Ad Hoc Networks” IEEE Transactions on Mobile Computing, Vol.3 No. 1, January-March 2004 [6] P. Crescenzi, G. Gambosiand P. Penna, “On-line algorithms for the channel assignment problem in cellular networks,”Discrete Applied Mathematics, Vol. 137, no. 3, pp. 237–266, March 2004. [7] Viswanathan, H.; Mukherjee, S., “Throughput-range tradeoff of wireless mesh backhaul networks” IEEE Selected Areas in Communications Journal, Volume 24, Issue 3, March 2006 Page(s):593 – 602 6. References [1] Akyildiz, I.F., Wang, X. and Wang, W., ``Wireless Mesh Networks: A Survey,'' Computer Networks Journal (Elsevier), March 2005. [2] Changling Liu, JörgKaiser,“A Survey of Mobile Ad Hoc network Routing Protocols” Technique report, University of Magdeburg, http://www.minema.di.fc.ul.pt/papers.html [3] KaixinXu, Xiaoyan Hong, Mario Gerla "Landmark routing in ad hoc networks with mobile backbones" Journal of Parallel and Jae-Hwan Chang; Tassiulas, L.; “Maximum lifetime routing in wireless sensor networks” Networking, IEEE/ACM Transactions on Volume 12, Issue 4, Aug. 2004 Page(s):609 – 619 [8] Murthy, S. and J.J. Garcia-Luna-Aceves, “An Efficient Routing Protocol for Wireless Networks” ACM Mobile Networks and App. J., Special Issue on Routing in Mobile Communication Networks, Oct. 1996, pp. 183- 97.