MultiObjective QoS Based Routing Algorithm for Mobile AdhocNetworks
computer science topics Active In SP Posts: 610 Joined: Jun 2010 
01072010, 03:47 PM
MultiObjective QoS Based Routing Algorithm for Mobile AdhocNetworks.doc (Size: 78.5 KB / Downloads: 48) MultiObjective QoS Based Routing Algorithm for Mobile AdhocNetworks Abstract: Mobile AdHoc NETwork (MANET) is a collection of wireless nodes that can dynamically be set up anywhere and anytime without using any preexisting network infrastructure. The dynamic topology of the nodes possess more routing challenges in MANET compared to infrastructure based network. Most current routing protocols in MANETs try to achieve a single routing objective using a single route selection metric. As the various routing objectives in Mobile Adhoc Networks are not completely independent, an improvement in one objective can only be achieved at the expense of others. Therefore, efficient routing in MANETs requires selecting routes that meet multiple objectives. Along with this requirement routing algorithm must be capable of providing different priorities to different QoS as needed by the application which vary form one application to other. Hybrid Routing Algorithm for MANET which uses the advantages of both reactive and proactive routing approaches in finding stable routes, reducing initial route delay and to minimize bandwidth usage. A generic MultiObjective Hybrid Algorithm is to find the best available routes considering multiple QoS parameters achieving multiple objectives by evaluating the different alternatives. This algorithm can also provide support to multiple number of QoS parameters which can be varied, is very much needed to support any kind of application, where each application have different priorities for the QoS parameters. Keywords: Mobile Adhoc Networks. 1 Introduction FUTURE Mobile Adhoc Networks are expected to support applications with diverse Quality of Service requirements. QoS routing is an important component of such networks. The objective of QoS routing is twofold: to find a feasible path for each transaction; and to optimize the usage of the network by balancing the load. Routing in mobile adhoc network depends on many factors like, including modeling of the topology, selection of routers, and initiation of request, and specific underlying characteristics that could serve as a heuristic in finding the path efficiently. The routing problem in mobile adhoc networks relates to how mobile nodes can communicate with one another, over the wireless media, without any support from infrastructured network components. Several routing algorithms have been proposed in the literature for mobile adhoc networks with the goal of achieving efficient routing. These algorithms can be classified into three main categories based on the way the algorithm finds path to the destination. They are: 1. Proactive Routing Algorithms 2. Reactive Routing Algorithms 3. Hybrid Routing Algorithms Proactive protocols perform routing operations between all source destination pairs periodically, irrespective of the need of such routes where as Reactive protocols are designed to minimize routing overhead. Instead of tracking the changes in the network topology to continuously maintain shortest path routes to all destinations, Reactive protocols determine routes only when necessary. The use of Hybrid Routing is an approach that is often used to obtain a better balance between the adaptability to varying network conditions and the routing overhead. These protocols use a combination of reactive and proactive principles, each applied under different conditions, places, or regions. A generic MultiObjective Hybrid Routing Algorithm uses the advantages of both reactive and proactive routing approaches to find the best available routes by considering multiple QoS parameters and achieving multiple objectives. 2 Proposed Algorithm It is a Multiâ€œObjective Hybrid Routing Algorithm for Mobile Ad Hoc Networks. This algorithm tries to achieve multiple objectives. Here each of these objectives depends upon one or multiple QOS parameters. Considered n QOS parameters which accounts for achieving multiple objectives. Depending upon the parameters we are considering and usage, different objectives can be achieved. These parameters can be varied depending upon the application. As every application have different requirements of the QOS and thus have different priorities of each parameter. So we have proposed a flexible generic scheme in which user can select different set of Ëœnâ„¢ QOS parameters accounting for achieving multiple objectives. The 3Cartesian coordinates are considered in this algorithm in determining expected and request zones by introducing the third coordinate z of geographic (earth centered) Cartesian coordinate system. Route Recovery with local route repair, based on distance metric of the path length is also added in this algorithm to support real time applications. This algorithm has five phases Neighbor Discovery, Route Discovery, Route Selection, Route Establishment and Route Recovery Phase. Route Discovery Phase consists of sub modules: Intra Zone Routing, Inter Zone Routing. A Neighbor Discovery Phase Here Neighbor Discovery Algorithm will look after the maintenance of Neighbor Tables and Zone Routing tables. Each and every node maintains Neighbor Tables and Zone Routing Tables. The Neighbor Table along with the neighbor node addresses also stores available QOS parameter values along the link between itself and its Neighbor. These parameters are considered for selecting best available routes by Intra Zone Routing Protocol (used to select the routes with in the zone). In this phase each and every node periodically transmits beacons to its neighbors. On reception of these packets from neighbors every node updates its Neighbor Table with appropriate values. Each node exchanges their Neighbor Tables from their corresponding neighbors and constructs Zone Routing Tables. Every node constructs Zone Routing Table from their Neighbor Tables using Link State Algorithm. A Zone is a set of nodes which lies with in a limited region in 2Hop distance from given node. B Route Discovery Phase This phase is used to find all the alternate routes available. It has sub modules Intra Zone Routing Protocol and Inter Zone Routing Protocol. Any node which requires route to any destination constructs Route Request Packet (RREQ) in which Desired QOS Metrics [Q1, Q2... Qn] and set of parameters [P1, P2... Pn] to be calculated during route Discovery Phase are introduced. Source node S initially searches for the destination node D whether it belongs to Zone or not. If it belongs to the zone it finds the route desired using Intra Zone routing Module. Intra Zone Routing Protocol is for selecting the path to any destination which is present with in the zone. Source node selects the path available from the zone routing table only when desired QOS metrics are satisfied. Inter Zone Routing Protocol is for selecting all the available routes to any destination node which lies outside the zone. S broadcasts the RREQ packets, on reception of RREQ every node will check whether it is a member of the Request zone, if it is a member then it checks whether the link between itself and its Predecessor Node is satisfying these QOS constraints or not, and if it can satisfy the QOS requirements then it broadcasts the request further by processing the parameters depending up on the metric, including its details else it discards the request, there by reducing unnecessary routing traffic. Destination ËœDâ„¢ may receive RREQ packets from alternate paths, these are the different alternatives available at D. Route Selection Algorithm is used to select the best available route and Route Reply Packet (RREP) is constructed at D and sent back along the path chosen. Each intermediate node processes the RREQ packets and stores the route request details in the route table along with the pointer to Local Route Repair Table (LRRT) in which QOS parameter values attained up to that node are stored to use it further for local route recovery if needed. Every node retains this LRRT table only if it has to repair the route locally, decided by distance metric in the Route Establishment phase. C Route Selection Phase In this phase the best available route among Ëœkâ„¢ alternatives have to be selected taking decision depending up on the Ëœmâ„¢ (multiple QOS parameters) attributes. Among the k alternatives all are not optimal solutions, pareto optimal solutions have to be found. Finding paretominimum vectors among r given vectors, each of dimension m, is a fundamental problem in multiobjective optimization problems. Multi Objective Optimization is used in Route Selection Phase, where Multi Objective Problem is transformed in to Single Objective Problem by weighting method. The goal of such singleobjective optimization problems is to find the best solution, which corresponds to the minimum or maximum value of an objective function. In this algorithm multiple objectives are reformulated as singleobjective problem by combining different objectives into one (that is, by forming a weighted combination of the different objectives). First, all the objectives need to be either minimized or maximized. This is done by multiplying one of them by 1 (i.e., max f2 is equivalent to min (f2) = minf2'). Next, these objectives must be lumped together to create a single objective function. Weighting (conversion) factors w1 w2... wn are used in order to obtain a single, combined objective function. Maximize{F} = (+/)w1f1(x)+(+/) w2f2 (x)...(+/)wnfn(x). To find the relative performance of each objective function each of the objective function value obtained is divided by corresponding desired QOS value. Now relative efficiency of each route is obtained by calculating the F value of all valid paths (which satisfy the QOS requirements) from source to destination. Finally, given this single objective function one can find a single optimal solution (optimal route). D Route Establishment Phase This phase is for reverse path set up i.e. the route is established from destination to source. After selecting the optimal route available by Route Selection phase, Route Reply packets will be sent along the path selected, back tracking from destination to source setting the status field value of corresponding entry in route table from Route Not Established(NE) to Established, and updating NextNode_ID as the P.Current_ID (the node from where RREP packet has received). Then send back the RREP packets towards source selecting next hop from route table which is stored during forward path set up. This phase itself decides whether the intermediate node is capable of handling Local route recovery for this path or not depending up on the distance metric which is explained in next section. If the node is capable of local recovery then retains LRRT table entries otherwise clears them thus saving space. E Route Recovery Phase Every routing algorithm to support real time applications must have efficient route recovery mechanisms. This algorithm has local route repair mechanism, to have this feature extra overhead is required (since each node has to store QOS requirements per route) but at the same time it is necessary to have this feature. To have a tradeoff between efficient route recovery mechanism and space overhead, path length is considered as a distance metric and divided the nodes in to 2 categories one which can handle local route recovery and other notifies Source or Destination to handle route recovery. Path length divided into (0  to  25) %, (25 â€œ to  75) %, (75  to  100) %. So middle 50% of the nodes which lie in the (25  to75) %portion of path length handle local route recovery and the remaining portions notify Source/Destination. In the route establishment phase every node calculates in which portion of the path length it lies, so as to handle route recovery. Every node which receives RERR messages checks whether it is capable of handling route recovery locally by checking whether LRRT table entries are available or not. If they are available construct RREQ packets locally with entries available from LRRT and broad cast it other wise send RERR packets towards source or destination. 3 Complexity Analysis of the Algorithm Let N be the total number of nodes in the network, n be the number of neighbor nodes of a particular node, z be the number of nodes in its zone and N1 be the number of nodes in the request zone. A Space Complexity For each node, a Neighbor Table and a Zone Routing Table are required. The size of each entry in the Neighbor Table is (9 Bytes + Ëœkâ„¢ Bytes), where Ëœkâ„¢ be the number of QOS parameters considered. The size of each entry in the Zone Routing Table is (9 Bytes + Ëœkâ„¢ Bytes). Total size required by each node will be ((9+k)*n + (9+k)*z). The total amount of space required by over all Networks will be N*(9*n + 9*z + k*(n+z)). Case 1: Average Case The Space Complexity = O (N* (9*n + 9*z + k*(n+z))). = O (N* (c1*n + c2*z + c3*(n+z))), where c1, c2, c3 are constants. = O (N* (c2+c3)*z), as z â€°Â¥ n = O (N* z). (â€°Â¤ O (N2)) This is for average space complexity Case 2: Best Case In the best case, the number of nodes in the zone equals the number of neighbor nodes. So the best case space complexity of the network becomes O (N*n). Case 3: Worst Case In the worst case, the number of neighbor nodes or the number of nodes in the zone equals to the total number of nodes in the network. In that case the overall complexity becomes O(N 2) (since z= N). B Time Complexity For the neighbor table maintenance, the proposed algorithm uses the Link state algorithm. It receives the neighbor tables from all the neighboring nodes and computes the zone routing table. As the numbers of neighboring nodes are n, the complexity for computing zone routing table is of order O(n2). Case 1: Average Case In the average case the route is found from the routing table using the binary search algorithm in O(log z) time. The average case time complexity of the algorithm for entire network is =N *(O (n2) + O (log z)). =O (N *log z), if 2 z > 2n =O (N *n2), otherwise n2 Case 2: Best Case In the best case the required route is directly found from the routing table in one step, i.e. in O(1) time. So, the best case time complexity of the algorithm for the entire network is N * (O(1) + O(n2 )) = O(N *n2 ). Case 3: Worst Case In the worst case, the route request has to go through the entire request zone. The complexity becomes 1 O(N *log(z)). Let m be the possible routes satisfying QOS at Destination node. Then for selecting k Pareto optimal solutions from m alternatives, time complexity is O(m2) Then for selecting the best route from k alternatives, the time complexity will be O(k2 ). In worst case k = m ten the time complexity will be O (m2). So the total time complexity for selecting the route will be O (m2) + O (m2) = O (m2). The worst case time complexity becomes N*(O(N1* log z) + O(m2)) 4 Conclusion MOHRA is an algorithm improved on top of New Hybrid Routing Algorithm (NHRA). NHRA is a single objective routing protocol, where as this algorithm addresses multiple objectives and it has the advantages of both reactive and proactive routing approaches. This algorithm is used to select optimal route available achieving multiple objectives like minimum delay, highly stable routes with desired bandwidth, which depends upon one or multiple QOS parameters like delay, associativity ticks (this metric is used to find link stability), and bandwidth. Depending upon the parameters considering and usage, different objectives can be achieved. This algorithm can provide support to multiple number of QoS parameter which can be varied achieving multiple objectives, which is a flexible scheme to support any kind of real time applications, where each application have different priorities and this is all possible with less computational effort. As we are using associativity count longlived routes are selected, ensuring a lower packet loss rate arising from the movement of intermediate nodes and fewer route failures. Thus accounting for the increase in packet delivery fraction and reducing endtoend delay and by using location coordinates search space can be reduced for route discovery. One more major contribution of this work is efficient Route Recovery mechanism with local route repair based on distance metric of the path length to support real time applications. Based on the simulation study and comparative analysis of the routing algorithms, it is observed that NHP with respect to end to end delay works well when compared with other algorithms, DSDV works well with respect to packet deliver fraction when compared other algorithms. References [1] Highly Dynamic DestinationSequenced DistanceVector Routing (DSDV) for Mobile Computers, Perkins C.E. and Bhagwat P., Computer Communications Review, Oct 1994, pp.234244. [2] google.com Use Search at http://topicideas.net/search.php wisely To Get Information About Project Topic and Seminar ideas with report/source code along pdf and ppt presenaion



