Multi-Objective QoS Based Routing Algorithm for Mobile Ad-hocNetworks
Thread Rating:
  • 0 Vote(s) - 0 Average
  • 1
  • 2
  • 3
  • 4
  • 5
computer science topics
Active In SP

Posts: 610
Joined: Jun 2010
01-07-2010, 03:47 PM

.doc   Multi-Objective QoS Based Routing Algorithm for Mobile Ad-hocNetworks.doc (Size: 78.5 KB / Downloads: 48)

Multi-Objective QoS Based Routing Algorithm for Mobile Ad-hocNetworks

Mobile Ad-Hoc NETwork (MANET) is a collection of wireless nodes that can dynamically be set up anywhere and anytime without using any pre-existing 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 Ad-hoc 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 Multi-Objective 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 Ad-hoc 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 two-fold: to find a feasible path for each transaction; and to optimize the usage of the network by balancing the load.
Routing in mobile ad-hoc 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 ad-hoc 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 ad-hoc 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 Multi-Objective 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 3-Cartesian co-ordinates are considered in this algorithm in determining expected and request zones by introducing the third co-ordinate z of geographic (earth centered) Cartesian co-ordinate 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 2-Hop 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 pareto-minimum vectors among r given vectors, each of dimension m, is a fundamental problem in multi-objective 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 single-objective 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 single-objective 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 trade-off 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 - to-75) %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 long-lived 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 end-to-end delay and by using location co-ordinates 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.
[1] Highly Dynamic Destination-Sequenced Distance-Vector Routing (DSDV) for Mobile Computers,
Perkins C.E. and Bhagwat P., Computer Communications Review, Oct 1994, pp.234-244.
Use Search at wisely To Get Information About Project Topic and Seminar ideas with report/source code along pdf and ppt presenaion

Important Note..!

If you are not satisfied with above reply ,..Please


So that we will collect data for you and will made reply to the request....OR try below "QUICK REPLY" box to add a reply to this page

Quick Reply
Type your reply to this message here.

Image Verification
Please enter the text contained within the image into the text box below it. This process is used to prevent automated spam bots.
Image Verification
(case insensitive)

Possibly Related Threads...
Thread Author Replies Views Last Post
  advantages and disadvantages of mobile phones in telugu jaseelati 0 232 07-02-2015, 02:21 PM
Last Post: jaseelati
  mobile phone based attendance tracking system ppt jaseelati 0 330 30-01-2015, 01:57 PM
Last Post: jaseelati
  mobile advantages and disadvantages in hindi wikipedia jaseelati 0 653 29-01-2015, 01:49 PM
Last Post: jaseelati
  mobile data internetworking standards jaseelati 0 333 29-01-2015, 01:15 PM
Last Post: jaseelati
  A Character Segmentation Algorithm for Printed Kannada Text Document uploader 1 1,508 10-01-2015, 12:52 PM
Last Post: zcfqmbrtb
  multi touch ppt jaseelati 0 179 09-01-2015, 04:36 PM
Last Post: jaseelati
  multi touch interaction ppt jaseelati 0 235 07-01-2015, 04:24 PM
Last Post: jaseelati
  difference between soc and aoc in mobile computing jaseelati 0 341 20-12-2014, 01:12 PM
Last Post: jaseelati
  online voting using bluetooth enabled mobile phone projec jaseelati 0 354 09-12-2014, 03:21 PM
Last Post: jaseelati
  online voting using bluetooth enabled mobile phone jaseelati 0 339 29-11-2014, 04:47 PM
Last Post: jaseelati