Neighbour Coverage Based Probabilistic Scheme for Reducing Routing Overhead in Manets

DOI : 10.17577/IJERTV3IS040811

Download Full-Text PDF Cite this Publication

Text Only Version

Neighbour Coverage Based Probabilistic Scheme for Reducing Routing Overhead in Manets

Nikhila T Suresh M.Tech scholar IT Department

Rajagiri School of Engg. &Tech Kochi,India

Mujeebudheen Khan A I Asst. Professor

IT Department

Rajagiri School of Engg. &Tech Kochi,India

Abstract MANET is an evolving research area in networking for communicating mobile users. MANET has some features like dynamic topology, no fixed infrastructure etc. and highlighted feature among them is it's mobility. Because of this high mobility, frequent path failures and route repairing are done in order to maintain the communication unaffected. But the overhead for the above specified operations are very high. Our scheme especially proposes to reduce the routing overhead during the route breakages. These utilize the neighbour knowledge information in the network and then define the probability factor for the route management. Probability value for each neighbour node is calculated using 2 key factors like additional coverage ratio and connectivity factor. The additional coverage ratio means the ratio of number of neighbours covered by one broadcast to the total number of neighbours of the source node. We done the simulations using NS-2 and done the analysis. This shows performance improvements in terms of throughput, normalized overhead, packet drop etc. In future we can add this mechanism in to the existing on demand protocol AODV to get rid of the overhead, latency and time required for setting up new path in case of route failures.

Keywords-MANET; neighbour knowledge; routing overhead; probability.


    The Mobile Ad-hoc Network (MANET) has some difference compared to the wireless environment. Some important features like

    • Dynamic network topology

    • Device heterogeneity

    • Power constraints

    • Limited Security

    • Autonomacity

    • Network scalability

    • Multi-hop routing

      The communication in MANET done through the multi- hop routing includes the route discovery and route management. The conventional routing protocols use conventional broadcasting technique to find the route. The data should reach the destination in an optimized way by reducing the overhead.

      There Here in this paper [3], a working group named with manet has been formulated by the Internet Engineering Task

      Force (IETF). Braodcasting is the fundamental process in many fields like MANET, multicast services, mathematical problems like graph-related problems, LAN emulations etc. For avoiding the network issues, broadcasting by flooding is used. In manet, due to the high mobility broadcasting is the one solution that can be utilized. The main issues related with this are: redundancy, contention

      and collision. The main characteristics of broadcasting are: they are spontaneous and its Unreliability in nature. The solutions to this problem are classified in to 5 as in paper [4]for reducing the overhead. They are: Probability based scheme, distance based scheme, location based scheme, cluster based scheme and counter based scheme. Broadcasting is the basic operation in mobile ad-hoc networks for route discovery and maintenance .It is the process in which the source node sends the broadcast request packets to each of its neighbours. In manet, routing protocols, either it may be unicast or multicast flooding is used. This has a lot of problems associated with it like congestion, redundancy etc. Thus it becomes very costly and consumes a big amount of network resources available in the network. A group exploited different problems associated with the flooding and thus they categorized protocols [5] in to a no of categories like simple flooding, probability based methods, area based methods, neighbor knowledge methods etc. The analysis [6] of the above specified protocols showed that the neighbor knowledge methods are better.


    The routing protocols in MANET are for routing the packets securely in to the destination and this is broadly divided into two i.e. table driven and on demand protocols. The table driven protocol deals with the routing tables associated with each of the nodes in the network where as the on demand protocol find the route to the destination node as and when the need arises.

    The conventional on-demand routing protocols use the flooding to discover a new route. The overhead involved in route discovery is very high. Broadcasting is very costly and it consumes a lot of resources present in the network. The AODV uses flooding to discover new routes for route management process.

    1. AODV

      First, In paper [2], the AODV protocol is detailed with complete operation, message formats, routing etc. The Ad hoc On-Demand Distance Vector (AODV) routing protocol is used by the mobile nodes in an ad hoc network. This is an on demand routing protocol and thus it finds the route to the destination only when it is asked to do. The messages like Route REQuests (RREQ), Route REPlies (RREP) and Route ERRors (RERR) are used. The working of AODV and its packet structure is explained in detail. Whenever a source needs to send packets to its destination it immediately send out RREQ packets to each of its neighbors in the range. Then those neighbor nodes will again send the RREQ packets to their neighbors if they didnt have any routes to the specified destination. This process continues until this PREQ reaches a node that has a valid route to the destination node. At each intermediate node, when a RREQ is received a route to the source is created. When the node with a valid route to the destination is reached, the RREP packet is returned back through the path stored in the RREQ packet. If any path breakage is occurred during the packet routing then PERR is prorogated. The main disadvantages are:

      • AODV takes much longer time to reconstruct the route when the failure of pre-established route occurs

      • It is because when failure of a link occurs, either of its end node prepares a Route ERR message and sends it to the source node. The source needs to reconstruct the route by broadcasting the Route REQ message again.

      • Increases network traffic

      • It leads to higher latency due to the fact that the route has to be discovered.

      • Sometimes broadcasting storm occurs


    A NCPR contains the following mechanisms

    1. Neighbour discovery

    2. Delay calculation

    3. Probability calculation

    4. Performance Evaluation

    The source finds its neighbours and in order to effectively exploit the neighbour coverage knowledge, we propose a novel delay to determine the rebroadcast order, and then we can obtain the more accurate additional coverage ratio by sensing neighbour coverage knowledge. We define a connectivity factor to provide the node density adaptation.

    By combining the additional coverage ratio and connectivity factor, we set a reasonable probability for the neighbour nodes. The project is based on bottom-up approach method

    1. Selection of neighbours

      A MANET (mobile ad hoc network) is a collection of mobile nodes that cooperate to forward packets for each other to allow them to communicate beyond direct wireless transmission range. The source node has updated knowledge of the network structure within its proximity but its knowledge about further areas of the network can be obsolete due to node mobility. This error becomes worse as the data packet i

      forwarded towards the destination node. For finding the neighbours, first calculate the distance of every node to every other node. Then a value is fixed as the range of the node. The nodes, that comes under the range of a node is considered as the neighbours of that node. When topology changes, then the neighbours of the node also change. The nodes that are the neighbours of a particular node at a time may not the neighbours of that node at a later time.

      Here we use euclidian distance formula for calculating distance which is derived from pythagoras formula. The transmission range set to be as 200 m.

    2. Delay calculation

      We proposed a scheme to calculate the delay as in [1]. The delay is to determine the forwarding order. The node which has more common neighbours with the previous node has the lower delay. If this node rebroadcasts a packet, then more common neighbours will know this fact.

      Therefore, this delay enables the information about the nodes which have transmitted the packet to more neighbours, which is the key success for the proposed scheme. When a node ni receives an RREQ packet from its previous node s, node s can use the neighbour list in the RREQ packet to estimate how many its neighbours have not been covered by the RREQ packet . If node ni has more neighbours uncovered by the RREQ packet from s, which means that if node ni rebroadcasts the RREQ packet, the RREQ packet can reach more additional neighbour nodes. Here in the equation for delay calculation, N(ni) refers to the neighbour set for the node ni N(ns) refers to the neighbour set for the node s and | indicates the no of elements in a neighbour set for the node.

    3. Probability calculation

      We proposed a novel scheme to calculate the probability [1]. The scheme considers the information about the uncovered neighbours, connectivity metric and local node density to calculate the probability. The probability is composed of two parts: a) additional coverage ratio, which is the ratio of the number of nodes that should be covered by a single broadcast to the total number of neighbours

      and b) connectivity factor, which reflects the relationship of network connectivity and the number of neighbours of a given node. Here the terms like U(ni) indicates the uncovered neighbour set for node ni, N(ni) refers to the neighbour set for the node ni and Nc is the network connectivity metric equivalent to 5.1774 log n as in [1].

      The additional coverage ratio indicates the ratio of the number of nodes that are additionally covered by this rebroadcast to the total number of neighbours of node ni. The nodes that are additionally covered need to receive and process the RREQ packet. As Ra becomes bigger [1], more nodes will be covered by this rebroadcast, and more nodes need to receive and process the RREQ packet, and, thus, the rebroadcast probability should be set to be higher.

      Merits of the proposed system are:-

      • Low normalized overhead

      • No need to maintain the route information

      • More reliable data transfer

      • Packet drop is less

      • Packet delivery ratio is high

    4. Performance Evaluation

      We selected AODV as the baseline because AODV is one of the widely used routing protocols in MANETs. To simulate the system, NS2 is used. Here we used tcl script, awk files, trace files, xgraphs etc. Different factors are considered and xgraphs are plotted based on the comparison. The performance of the proposed system is compared against the AODV routing protocol based on the following parameters like

      1. No of packets dropped

      2. Throughput

      3. Normalized overhead

    1. No of packets dropped

      For evaluation of the performance of the proposed system, no of packets dropped for both AODV and NCPR is calculated. No of packet drop is the amount of data collided or missed on the way to reach at the destination. This may happened due to the network congestion or error in packets or low signal power. Here the proposed one shows the better performance as shown in following figure 4.1.

    2. Throughput

      For evaluation of the performance of the proposed system, throughput for both AODV and NCPR is calculated. Throughput is the amount of data delivered per unit time. The xgraphs of the throughputs for both AODV and NCPR states that the throughput of NCPR is higher when compared with that of AODV as shown in figure 4.3.

    3. Normalized overhead

    Normalized overhead is the overhead that is incurred while routing a packet.NOH =Number of routing packets/ Number of packets received Figure 4.2 shows the xgraph based on the comparison of NOH of both NCPR and AODV. The figure shows that the normalized overhead of NCPR is low compared to AODV


Here we discuss some implementation details including the simulator and its parameters .We used Network Simulator version 2.35 and also made use of tcl scripts, awk files, trace files , xgraphs etc. The Network Simulator is an event based simulator through which we can see simulation scenario through an animator called Network AniMator (NAM) and by executing the tcl script we could obtained the corresponding trace files. This trace file records each and every events occurred during the simulation time including packet drop, ack received etc. For processing the data inside trace file we had to write awk file and using this awk file we plotted the xgraphs for different parameters. These parameter values are computed using the awk file and this can also write data to any .dat file. Here these .dat files are used for plotting the xgraphs shown below.

  1. Simulation model

    Table 4.1 Simulation model

    1. No of packets dropped

      Figure 4.1 Packet Drop AODV Vs NCPR

      By comparing the performance of AODV vs NCPR in terms of no of packets dropped, it shows less no of drops in case of NCPR

    2. Overhead

      Figure 4.2 Overhead for AODV Vs NCPR

    3. Throughput

Figure 4.3 Throughput for AODV Vs. NCPR


In MANET the energy (a) of a node is very crucial and limited factor. So we need to keep track it using a special entity called energy administrator. These energy administrators check the power statistics of each node and report it eventually. There is trustee agent which is responsible for giving trust values (b) to other nodes depending upon its history of performance , RSSI values etc. Packet integrity check values (c) are given for maintaining the integrity of packet. Initially it is a positive integer value if any modification on packet is detected then it will be decremented. Then the administrator selection algorithm is used for the selection of the administrator node with high final trust value calculated by summing up the above specified values (a),(b) and (c).Then certification authority is also selected depending up on the administrator node. This certification authority will categorize the nodes as legitimate

nodes and illegitimate nodes. For more energy efficiency, GNDA algorithm can be used.


The routing is difficult in MANET because mobility may cause radio links to break frequently. Mobile nodes keep changing their position in an unpredictable manner.A routing algorithm must keep track of the destinations position and modify routes whenever the old routes become stale. In a high mobility MANET, although every mode can move freely, they usually follow some mobility patterns. Fast changes of topology increases the complexity of routing. In this project, problem of routing overhead in mobile ad-hoc networks is considered. This project proposes a probabilistic scheme for reducing the overhead occurred in route discovery. The key terms used here are delay and probability. These make use of neighbour knowledge information for each node in the network. Thus we can

improve the routing peformance in mobile scenario. The proposed scheme mitigates the network collision and contention, so as to increase the packet delivery ratio and decrease the average end-to-end delay.


  1. Xin Ming Zhang,En Bo Wang A Neighbor Coverage-Based Probabilistic Rebroadcast for Reducing Routing Overhead in Mobile Ad Hoc Networks, IEEE TRANSACTIONS ON MOBILE COMPUTING, VOL. 12, NO. 3, MARCH 2013.

  2. C. Perkins, E. Belding-Royer, and S. Das, Ad Hoc On-Demand Distance Vector (AODV),IETF RFC 3561,, 2003.

  3. H. AlAamri, M. Abolhasan, and T. Wysocki, On Optimising Route Discovery in Absence of Previous Route Information in MANETs, , Proc. IEEE Vehicular Technology Conf. (VTC), pp. 1-5,2009.

  4. A. Mohammed, M. Ould-Khaoua, L.M. Mackenzie, C. Perkins,and J.D. Abdulai, Probabilistic Counter-Based Route Discovery for Mobile Ad Hoc Networks, Proc.Intl Conf. Wireless Comm. and Mobile Computing: Connecting the World Wirelessly (IWCMC 09),pp. 1335- 1339, 2009

  5. B. Williams and T. Camp, Comparison of Broadcasting Techniques for Mobile AdHoc Networks, Proc. ACM MobiHoc, pp. 194-205, 2002.

  6. J. Kim, Q. Zhang, and D.P. Agrawal, Probabilistic Broadcasting Based on Coverage Area and Neighbor Confirmation in Mobile Ad Hoc Networks,, Proc. IEEE GlobeCom, 2004.

  7. J.D. Abdulai, M. Ould-Khaoua, and L.M. Mackenzie, Improving Probabilistic Route Discovery in Mobile Ad Hoc Networks,, Proc. IEEE Conf. Local Computer Networks, pp. 739-746, 2007.

Leave a Reply