A Modified Rebroadcast Algorithm for Reducing Routing Overhead in Mobile Ad-Hoc Networks

A Modified Rebroadcast Algorithm for Reducing Routing Overhead in Mobile Ad-Hoc Networks

Tissa Zacharia B.Tech, Prof. B. Suganthi M.E.

Associate Professor

Department of ECE Department of ECE

RVS College of Eng. and Technology RVS College of Eng. and Technology

Abstract:

A Mobile Ad Hoc networks (MANET) are essential in situations where on communication infrastructure exists and communicating entities are mobile. Such networks are characterized by dynamic topologies, existence of bandwidth constrained variable capacity links, energy constrained operations. Due to all this features routing overhead is a major issue in Ad-Hoc networks. The main objective of this paper is to reduce the routing overhead by using a modified rebroadcast algorithm. This is achieved by using local route repair algorithm and neighbor coverage based probabilistic rebroadcasting based on rebroadcast probability and connectivity factor. Simulation results shows that the proposed algorithm significantly reduces routing overhead, end-to-end delay, packet dropping rate and increases packet delivery rate.

Keywords: Mobile Ad-Hoc Networks, neighbor coverage, probabilistic rebroadcast, connectivity factor, routing overhead.

1. Introduction

   Mobile Ad-hoc Network (MANET) is a collection of communication devices or nodes that wish to communicate with infrastructure less support and without predetermined organization of available links. In MANETs, the peer-to-peer mode of operation can greatly extend the distance of the wireless networks .

   Ad-hoc routing protocols have been developed to provide the route discovery and maintenance mechanisms for each mobile node in the network to communicate with all other nodes of the network. There two types of routing protocols: Proactive and Reactive. In proactive routing each node should indicate all other nodes in the network if there is any change in the network topology. The maintenance of the up-to-date information will increase the cost of routing overhead. Distance vector (DV) protocol, Destination Sequenced Distance Vector (DSDV) protocol, Wireless Routing protocol Fisheye State Routing (FSR) protocol are the examples of Proactive protocols. In Reactive routing protocol, each node in a network discovers or maintains a route based on-demand. It floods a

   control message by global broadcast during discovering a route and when route is discovered then bandwidth is used for data transmission. This protocol needs less routing information but the disadvantages are that it produces huge control packets due to route discovery during topology changes which occurs frequently in MANETs and it incurs higher latency and the cost of routing overhead. The examples of this type of protocol are Dynamic Source Routing (DSR) [1], Ad-hoc On Demand Routing (AODV) and Associativity Based Routing (ABR) protocols.

   In AODV when a source node desires to establish a communication with other node, it initiates a path-discovery process to locate the other node [2]. The source node broadcasts a RREQ packet with its IP address, Broadcast ID (BrID), and the sequence number of the source and destination. The broadcast systems face many problems like repetition of messages, mixing up against other codes which leads to considerable number of packet collisions especially in dense networks.. This makes it difficult for us to separate out the messages. This problem is also known as broadcast storm problem [3].

   Williams and Camp [4] categorized broadcasting protocols into four classes: simple flooding, probability based methods, area based methods and neighbor knowledge methods. For the above four classes of broadcasting protocols, they showed that an increase in the number of nodes in a static network will degrade the performance of the probability based and area based methods. Kim et al.

   [5] indicated that the performance of neighbor knowledge methods is better that of area based ones, and the performance of area based methods is better than that of probability based ones.

   A new route repair Algorithm is suggested, which predicts the link failure, and perform local route repair with low end-to-end delay and packet dropping and reduces the routing over head and thus increases packet delivery rate.

2. Related Works

Broadcasting is the most basic system of many applications in the mobile ad hoc network system. It helps in connecting with the routers, routing protocols, messages, accepting or declining them. Blind flooding is extensively used in ad hoc routing protocols for on-demand route discovery, where a mobile node blindly rebroadcasts received route request (RREQ) packets until a route to a particular destination is established. This can potentially lead to high channel contention, causing redundant retransmissions and thus excessive packet collisions in the network. Such a phenomenon induces what is known as broadcast storm problem [3], which has been shown to greatly increase the network communication overhead and end-to-end delay. The impact of such a problem can be reduced if measures are taken during the propagation of RREQ packets. H. AlAamri et.al [6] has proposed an algorithm called On-demand Tree based Routing Protocol (OTRP) OTRP to reduce the number of redundant rebroadcasts when previous information about destination is not available to improve scalability of Ad hoc networks. To achieve this in OTRP, route discovery overheads are minimized by selectively flooding the network through a limited set of nodes, referred to as branching-nodes through a new algorithm called Tree based Optimized Flooding (TOF) which strategically selects forwarding nodes during the route discovery phase.

Ni et al. [7] studied the flooding protocol analytically and experimentally and showed that a rebroadcast can provide only 61% additional coverage at most and only 41% additional coverage in average over that already covered by the previous transmission. So, rebroadcasts are very costly and should be used with carefulness. He also classified broadcasting schemes into five classes to reduce redundancy, contention, and collision: probabilistic, counter-based, distance-based, and location-based and cluster-based. In probabilistic scheme, a mobile host rebroadcasts packets according to a certain probability.

Kim et al. [5] proposed a probabilistic broadcasting scheme based on coverage area and neighbor confirmation. This scheme uses the coverage area to set the rebroadcast probability, and uses the neighbor confirmation to guarantee reach ability. Peng et al. [8] proposed a neighbor knowledge scheme named Scalable Broadcast Algorithm (SBA). This scheme determines the rebroadcast of a packet according to the fact whether this rebroadcast would reach additional nodes. Abdulai et al. [9] proposed a Dynamic Probabilistic

Route Discovery (DPR) scheme based on neighbor coverage. In this approach, each node determines the forwarding probability according to the number of its neighbors and the set of neighbors which are covered by the previous broadcast. This scheme only considers the coverage ratio by the previous node, and it does not consider the neighbors receiving the duplicate RREQ packet.

Stann et al. [10] proposed a Robust Broadcast Propagation (RBP) protocol to provide reliability for flooding in wireless networks. This presented a new outlook for broadcasting: not to make a single broadcast more efficient but to make a single broadcast more reliable.

1. Local Route Repair

   In Local Route Repair (LRR) [11] AODV based on Link Prediction each node maintains two tables NPL (NeighborPower List) and PDT (Power Difference Table), Link failure Threshold (LFTHRSH) and one LFF (Link Failure Flag). NPL contains the last received signal strength for packets originating from each neighbor. This table is updated whenever a packet is received and happens at least once every Hello interval. PDT contains the rate at which power is changing between each pair of neighbors. PDT describes whether the link signal strength which is changing between each pair of neighbors is increasing or decreasing. This table is also update whenever a packet is received. When the link strength is under LFTHRSH, the quality is so poor, and then it is assumed the link is already broken.

   A node checks the two tables periodically. When it finds the link strength is decreasing and is under LFTHRSH for a defined time, Let the LFF of the link equal to one which means the link is broken and a local route repair algorithm is executed. If route is established, the route reply RREP is sent to the source node which in turn sends the data to the destination. Otherwise a route error message is sent and let the LFF of the link is equal to zero.

   Figure.1. Local Route Repair

   As shown in Figure.1, there is a route ABFCEHJ. The relative mobility of node c and node E results in the link breaks between them. Node c instead of sending RERR back to source node carries out local repair. For the local repair, if node D receives RREQ and has a route to node j, it will return RREP and establishes a route entry in its routing table with j as its destination node and E as its next one hop node. Similarly G also receives RREQ and has a route to node j, it will also return RREP and establishes a route entry in its routing table with j as its destination i as next one hop node. In this way Local Route Repair process is completed. The REPLY is sent back to the source node, which contains number of hop information. The source node sends the data using the shortest route.

   This is an algorithm to repair the Local broadcast route. This route repair algorithm predicts the link failure, and perform local route repair. AODV takes too much time to restore the route after a link break, along the active route is broken. This time is too long for some application, such as the real time services of voice and video. The route restoring time can be reduced if the recommended HELLO interval is reduced. In this paper a neighbor coverage based probabilistic rebroadcast algorithm is added with LRR algorithm to reduce the route rebuilding time so that real time voice and data can be

   packet, the RREQ packet can reach more additional neighbor nodes. To the UnCovered Neighbors (UCN) set U(ni) of node ni is defined as follows:

   U (ni) = N (ni) [N (ni) N(s)] {s}, (1)

   where N(s) and N(ni) are the neighbors sets of node s and ni, respectively. s is the node which sends an RREQ packet to node ni. According to Eq. (1), we obtain the initial UCN set. Due to broadcast characteristics of an RREQ packet, node ni can receive the duplicate RREQ packets from its neighbors. Node ni could further adjust the U(ni) with the neighbor knowledge.

   In order to suitably utilize the neighbor knowledge and avoid channel collisions, each node should set a rebroadcast delay. The selection of a proper delay is the key to success for the NCPR protocol because the scheme used to determine the delay time affects the propagation of neighbor coverage knowledge. When a neighbor receives an RREQ packet, it could calculate the rebroadcast delay according to the neighbor list in the RREQ packet and its own neighbor list. The rebroadcast delay Td(ni) of node ni is defined as follows:

   Ns Nn

   transmitted in MANET.

2. A Neighbor Coverage Based

   Tp (ni) 1-

   i

   Nni

   Probabilistic Rebroadcast Protocol (NCPR)

   The NCPR routing protocol reduces the number of redundant rebroadcast by calculating the rebroadcast delay and rebroadcast probability [12]. The rebroadcast probability determines the probability of rebroadcasting. The rebroadcast delay will decide the order of rebroadcast. The upstream coverage ratio of an RREQ packet which is received from the previous node is used to calculate the rebroadcast delay. It is also used to find the additional coverage ratio of the RREQ packet and the connectivity factor to calculate the rebroadcast probability rebroadcast probability contains two factors additional coverage ratio and connectivity factor. In NCPR protocol, each node needs its1-hop neighborhood information, Uncovered Neighbors Set and Rebroadcast Delay. When node ni receives an RREQ packet from its previous node s; it can use the neighbor list in the RREQ packet to calculate

   approximately how many its neighbors have not been

   Td (ni) = MaxDelay × Tp (ni), (2)

   where Tp(ni) is the delay ratio of node ni, and MaxDelay is a small constant delay. | · | is the number of elements in a set. When a node sends a RREQ packet all its neighbors receive and process the RREQ packet. The neighbor node with largest number of common nodes with the source node has the lowest delay. Then there are more nodes which can utilize the neighbor knowledge to UCN sets. The rebroadcast delay will determine the order of retransmission and spread the neighbor knowledge more quickly. The node rebroadcast the RREQ packet depending on the rebroadcast probability of the node.

   If node ni is the neighbor node of a source node s, the additional coverage ratio Ra(ni) is the ratio of number of nodes that are additionally covered by a single broadcast to the total number of neighbors. The additional coverage ratio of node ni is defined as follows:

   covered by the RREQ packet from s. If node ni has more neighbors uncovered by the RREQ packet from s, which means that if node ni rebroadcasts the RREQ

   Ra(ni) =

   U(n i ) Nn i

   (3)

   Xue et.al. [13] has determined 5.1774 log n as the connectivity metric. Connectivity factor is the number of neighbors connected to the total number of neighbors of a node. Connectivity factor provides density adaptation to the rebroadcast probability. Connectivity factor is inversely proportional to the local node density. In dense network the total number of neighbors is greater than the number of connected neighbors. Then connectivity factor decreases the rebroadcast probability and thus increases the efficiency of NCPR in the dense area.If local node density is low Fc increases the rebroadcast probability and increases the reliability of the NCPR in the sparse area. The ratio of the number of nodes that need to receive the RREQ packet to the total number of neighbors of node ni is Fc(ni).

   The minimum connectivity factor Fc(ni) of a

   Table.1 Simulation Parameters

   node ni is

   Fc(ni) =

   Nc N(n i )

   Simulation Parameters	Value
   Simulator	NS-2(v 2.34)
   Topology Size	1000 m × 1000 m
   No. of nodes	25,50,75,125200
   Transmission Range	250 m
   Nodes Speed	1 m/s to 5 m/s
   Interface Queue length	50
   Traffic Type	CBR
   Packet Size	512bytes

   (4)

   The rebroadcast probability Pre(ni) is computed by combining additional coverage ratio and connectivity factor. Pre(ni) of a node ni is defined as follows.

   Pre(ni) = Fc(ni) × Ra(ni) (5)

   The computed rebroadcast probability Pre(ni) may be greater than 1,but it does not affect the behavior of the protocol .

   The node ni rebroadcast the RREQ packet received from source node s based on the rebroadcast probability Pre(ni).

   The modified rebroadcast algorithm combines the local route repair algorithm and NCPR algorithm which reduce the routing overhead by limiting the number of redundant rebroadcast.

4. Performance Evaluation

   The modified rebroadcast algorithm is simulated using network simulator 2 (NS-2.34).The different network scenarios are considered for simulation. The performance metric such as routing overhead, packet delivery ratio, end-to-end delay and packet dropping rate have been evaluated against increasing number of nodes in a given area. The simulation parameters are listed in table.1.

   1. Routing Overhead

      Routing Overhead is defined as the data bits added to user transmitted data for carrying routing information, error correcting and operational instructions. The control overhead is defined as the ratio of the total packet size of control packets (include RREQ, RREP, RERR, and Hello) to the total packet size of data packets delivered to the destinations.

      Figure.2. Routing Load Vs No. of nodes

      The Figure.2. shows the routing load for increasing number of nodes in a given area and the routing load increases as the number of nodes increases. The modified algorithm reduces the routing overload by limiting the number of rebroadcast. The routing loads obtained for the NCPR algorithm are 0.33344 and 7.26015 for 25 and 200 nodes respectively. Similarly, for the modified algorithm the values for 25 and 200 nodes are 0.28414 and

      6.19447.The routing overhead of the modified algorithm has reduced.

   2. MAC Collision Rate

      The average number of packets (including RREQ, route reply (RREP), RERR, and CBR data packets) dropped resulting from the collisions at the MAC layer per second.

      Figure.3.Collision rate Vs No. of nodes

      The Figure.3. shows the collision rate for increasing number of nodes in a given area. The collision rate increases as the number of nodes increases. As the routing overhead of the modified algorithm decreased, the collision rate also decreases. The collision rates obtained for the NCPR algorithm are 25614.0 and 83301.3 for 25 and 200 nodes respectively. Similarly, for the modified algorithm the values for 25 and 200 nodes are 15099 and 72173.25.The Collision Rate of the modified algorithm has reduced.

   3. End-to-End Delay

      End to end delay which includes all possible delays caused by buffering during route discovery time, queuing at the interface queue, retransmissions and processing time from the sources to the destinations. It is defined as the average time taken by a data packet to arrive in the destination. Only the data packets that successfully delivered to the destinations that counted.

      Figure.3. End-to-End Delay Vs No. of nodes

      The Figure.3. shows the end-to-end delay for increasing number of nodes in a given area and it increases as the number of nodes increases. In the modified algorithm, as the routing overhead and collision rate has decreased the end-to-end delay decreases. The end-to-end delay obtained for the NCPR algorithm are 29820.9and 36843 for 25 and 200 nodes respectively. Similarly, for the modified algorithm the values for 25 and 200 nodes are 26571.2and 34456.4.The end-to-end delay of the modified algorithm has decreased.

   4. Packet Delivery Ratio

      PDR is defined as the average of the ratio of the number of data packets received by each receiver over the data packets send by the source.

      Figure.4. Packet Delivery Ratio Vs No. of nodes

      The Figure.4 .shows the Packet Delivery Ratio for increasing number of nodes in a given area and it decreases as the number of nodes increases. In the modified algorithm, as the end-to-end delay has decreased, the packet delivery ratio increases. The delivery ratios obtained for the NCPR algorithm are 0.22328 and 0.06667 for 25 and 200 nodes respectively. Similarly, for the modified algorithm the values for 25 and 200 nodes are 0.26518 and 0.19739.The delivery ratio of the modified algorithm has increased.

5. CONCLUSION

   This paper has proposed a modified rebroadcast algorithm in mobile ad hoc networks (MANETS) to reduce the routing overhead. The addition of the local rout repair algorithm to the NCPR protocol increases the packet delivery ratio of the proposed algorithm by reducing the latency of packets. The routing overhead of the modified algorithm is reduced by limiting the number of RERR packets .This is accomplished by setting a threshold value which helps to predict the link failure along the active route and perform the

   local route repair. As a continuation of this work, in future cryptographic algorithm can be used to obtain secure transmission of data packets.

6. REFERENCES

1. D.Johnson, Y.Hu, D.Maltz, The Dynamic Source Routing Protocol for Mobile AdHoc Networks(MANETS)for IPv4, IETF RFC 4728, vol. 15, pp. 153-181,2007.

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

3. S.Y. Ni, Y.C. Tseng, Y.S. Chen, and J.P. Sheu, The Broadcast Storm Problem in a Mobile Ad Hoc Network, Proc. ACM/IEEE MobiCom, pp. 151-162, 1999.

4. B. Williams and T. Camp, Comparison of broadcasting techniques for mobile ad hoc networks, Proceedings of the Third ACM International Symposium on Mobile Ad Hoc Networking & Computing (MobiHoc),2002, pp. 194205

5. 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.

6. 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.

7. Y. C. Tseng, S. Y. Ni, Y. S. Chen, and J. P. Sheu, The broadcast storm problem in a mobile ad hoc network, Wireless Networks, vol. 8, no. 2/3,pp. 153167, Mar.-May 2002.

8. W. Peng and X. Lu, On the Reduction of Broadcast Redundancy in Mobile Ad Hoc Networks, Proc. ACM MobiHoc, pp. 129-130, 2000.

9. J.D. Abdulai, M. Ould-Khaoua, L.M.Mackenzie, and A. Mohammed, Neighbor Coverage: A Dynamic Probabilistic Route Discovery for Mobile Ad Hoc Networks, Proc. Intl Symp. Performance Evaluation of Computer and Telecomm. Systems (SPECTS08), pp. 165- 172, 2008.

10. F. Stann, J. Heidemann, R. Shroff, and M.Z. Murtaza, RBP:Robust Broadcast Propagation in Wireless Networks, Proc. Intl Conf. Embedded Networked Sensor Systems (SenSys 06), pp. 85-98, 2006.

11. Ravindra .E1, VinayaDatt V Kohir2 and V. D Mytri3, A Local Route Repair Algorithm Based on Link Failure Prediction in Mobile Ad Hoc Network, World Journal of Science and Technology, 1(8): 64-67, ISSN: 2231 2587, 2011.

12. Xin Ming Zhang, En Bo Wang, Jing Jing Xia,and Dan Keun Sung A Neighbor Coverage based Probabilistic Rebroadcast for Reducing Routing Overhead in Mobile Ad hoc Networks, IEEE,2012.