ISSN ONLINE(2320-9801) PRINT (2320-9798)

All submissions of the EM system will be redirected to Online Manuscript Submission System. Authors are requested to submit articles directly to Online Manuscript Submission System of respective journal.

Reducing Routing Overhead In Manet Using Ncpr Protocol

Ms.Manjula.R1, Mr.Santhosh.R2
  1. PG Scholar, Karpagam University, Coimbatore
  2. Assistant Professor/CSE, Karpagam University, Coimbatore
Related article at Pubmed, Scholar Google

Visit for more related articles at International Journal of Innovative Research in Computer and Communication Engineering

Abstract

Mobile Ad hoc network is a collection of wireless mobile nodes. MANET is able to form a temporary network without any centralized administration. Due to high mobility of nodes in Mobile Ad hoc Network. There exist frequent link breakages and path failures. In a route discovery mobile nodes blindly retransmits the route request packets to the neighbor nodes unless it finds the route to its destination, and thus it causes the broadcast storm problem. in order to effectively exploit the neighbor coverage knowledge, we propose a rebroadcast delay to determine rebroadcast order, we also define a connectivity factor to keep network connectivity factor we set a rebroadcast probability. Hence it combines the advantages of neighbor coverage knowledge and probabilistic mechanism, it significantly decrease the number of retransmissions to reduce the routing overhead and also to improve the routing performance.

I. INTRODUCTION

Mobile ad hoc networks (MANETs) consist of a collection of mobile nodes which can move freely. These nodes can be dynamically self-organized into arbitrary topology networks without a fixed infrastructure. One of the fundamental challenges of MANETs is the design of dynamic routing protocols with good performance and less overhead. Many routing protocols, such as Ad hoc On-demand Distance Vector Routing (AODV) and Dynamic Source Routing (DSR), have been proposed for MANETs. The above two protocols are on demand routing protocols, and they could improve the scalability of MANETs by limiting the routing overhead When a new route is requested . However, due to node mobility in MANETs, frequent link breakages may lead to frequent path failures and route discoveries, which could increase the overhead of routing protocols and reduce the packet delivery ratio and increasing the end-to-end delay. Thus, reducing the routing overhead in route discovery is an essential problem.
The conventional on-demand routing protocols use flooding to discover a route. They broadcast a Route REQuest (RREQ) packet to the networks, and the broadcasting induces excessive redundant retransmissions of RREQ packet and causes the broadcast storm problem, which leads to a considerable number of packet collisions, especially in dense networks. Therefore, it is indispensable to optimize this broadcasting mechanism. Some methods have been proposed to optimize the broadcast problem in MANETs in the past few years. Williams and Camp 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. indicated that the performance of neighbor knowledge methods is better than that of area-based ones, and the performance of area-based methods is better than that of probability-based ones. We now obtain the initial motivation of our protocol: Since limiting the number of rebroadcasts can effectively optimize the broadcasting, and the neighbor knowledge methods perform better than the areabased ones and the probability-based ones.
Quality of Service (QoS) routing in such networks is usually limited by the network breakage due to either node mobility or energy depletion of the mobile nodes. Another issue that effects the QoS routing is routing overhead. Due to high mobility of nodes in mobile ad hoc networks (MANETs), there exist frequent link breakages which lead to frequent path failures and route discoveries. The overhead of a route discovery cannot be neglected. In this paper we described the impact of routing overhead in a real-time- time MANET environment with suitable scenarios. And also we suggested some methods to reduce the routing overhead over the network such that to improve the Quality of Service (QoS) routing in MANETS.

II. RELATED WORK

Broadcasting is an effective mechanism for route discovery, but the routing overhead associated with the broadcasting can be quite large, especially in high dynamic networks. Ni et al. studied the broadcasting protocol analytically and experimentally, and showed that the rebroadcast is very costly and consumes too much network resource. The broadcasting incurs large routing overhead and causes many problems such as redundant retransmissions, contentions, and collisions. Thus, optimizing the broadcasting in route discovery is an effective solution to improve the routing performance. Haas et al. proposed a gossip based approach, where each node forwards a packet with a probability. They showed that gossipbased approach can save up to 35 percent overhead compared to the flooding. However, when the network density is high or the traffic load is heavy, the improvement of the gossip-based approach is limited. Kim et al. 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 reachability. Peng and Lu 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.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. Thus, there is a room of further optimization and extension for the DPR protocol. Several robust protocols have been proposed in recent years besides the above optimization issues for broadcasting. Chen et al. proposed an AODV protocol with Directional Forward Routing (AODV-DFR) which takes the directional forwarding used in geographic routing into AODV protocol. While a route breaks, this protocol can automatically find the next-hop node for packet forwarding. Keshavarz-Haddad et al. proposed two deterministic timer-based broadcast schemes: Dynamic Reflector Broadcast (DRB) and Dynamic Connector-Connector Broadcast (DCCB). They pointed out that their schemes can achieve full reachability over an idealistic lossless MAC layer, and for the situation of node failure and mobility single broadcast more efficient but to make a single broadcast more reliable, which means by reducing the frequency of upper layer invoking flooding to improve the overall performance of flooding. In our protocol, we also set a deterministic rebroadcast delay, but the goal is to make the dissemination of neighbor knowledge much quicker.

III. PROBLEM DEFINITION

Broadcasting is an effective mechanism for route discovery, but the routing overhead associated with the broadcasting can be quite large, especially in high dynamic networks. The broadcasting incurs large routing overhead and causes many problems such as redundant retransmissions, contentions, and collisions. Thus, optimizing the broadcasting in route discovery is an effective solution to improve the routing performance. Existing approaches only considers the coverage ratio by the previous node, and it does not consider the neighbors receiving the duplicate RREQ packet, which will degrades routing performance as well increased routing overhead will alleviate network traffic.

IV. SYSTEM MODEL

4.1 TOPOLOGY FORMATION
Constructing Project design in NS2 should takes place. Each node should send hello packets to its neighbor node which are in its communication range to update their topology.
4.2 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 estimate how many its neighbors have not been 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 packet, the RREQ packet can reach more additional neighbor nodes. 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 sufficiently exploit the neighbor knowledge and avoid channel collisions, each node should set a rebroadcast delay. The choice of a proper delay is the key to success for the proposed protocol because the scheme used to determine the delay time affects the dissemination 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. Then, there are more nodes which can exploit the neighbor knowledge to adjust their UCN sets. Of course, whether node nk rebroadcasts the RREQ packet depends on its rebroadcast probability calculated in the next section. The objective of this rebroadcast delay is not to rebroadcast the RREQ packet to more nodes, but to disseminate the neighbor coverage knowledge more quickly. After determining the rebroadcast delay, the node can set its own timer.
image
4.3 NEIGHBOR KNOWLEDGE AND REBROADCAST PROBABILITY
The node which has a larger rebroadcast delay may listen to RREQ packets from the nodes which have lower one. For example, if node ni receives a duplicate RREQ packet from its neighbor nj, it knows that how many its neighbors have been covered by the RREQ packet from nj. Thus, node ni could further adjust its UCN set according to the neighbor list in the RREQ packet from nj. We do not need to adjust the rebroadcast delay because the rebroadcast delay is used to determine the order of disseminating neighbor coverage knowledge to the nodes which receive the same RREQ packet from the upstream node. Thus, it is determined by the neighbors of upstream nodes and its own.
When the timer of the rebroadcast delay of node ni expires, the node obtains the final UCN set. The nodes belonging to the final UCN set are the nodes that need to receive and process the RREQ packet. Note that, if a node does not sense any duplicate RREQ packets from its neighborhood, its UCN set is not changed, which is the initial UCN set. Now, we study how to use the final UCN set to set the rebroadcast probability.
This metric indicates the ratio of the number of nodes that are additionally covered by this rebroadcast to the total number of neighbors of node ni. The nodes that are additionally covered need to receive and process the RREQ packet. As Ra becomes bigger, 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. Xue and Kumar derived that if each node connects to more than 5:1774 log n of its nearest neighbors, then the probability of the network being connected is approaching 1 as n increases, where n is the number of nodes in the network.
The above rebroadcast probability is defined with the following reason. Although the parameter Ra reflects how many nexthop nodes should receive and process the RREQ packet, it does not consider the relationship of the local node density and the overall network connectivity.
The parameter Fc is inversely proportional to the local node density. That means if the local node density is low,the parameter Fc increases the rebroadcast probability, and then increases the reliability of the NCPR in the sparse area.
If the local node density is high, the parameter Fc could further decrease the rebroadcast probability, and then further increases the efficiency of NCPR in the dense area.
Thus, the parameter Fc adds density adaptation to the rebroadcast probability.
Algorithm Description
The formal description of the Neighbor Coverage-based Probabilistic Rebroadcast for reducing routing overhead in route discovery is shown in Algorithm 1.
Algorithm 1. NCPR
Definitions:
RREQv: RREQ packet received from node v.
Rv:id: the unique identifier (id) of RREQv.
NðuÞ: Neighbor set of node u.
Uðu; xÞ: Uncovered neighbors set of node u for RREQ whose id is x.
Timerðu; xÞ: Timer of node u for RREQ packet whose id is x.
{Note that, in the actual implementation of NCPR protocol,every different RREQ needs a UCN set and a Timer.}
1: if ni receives a new RREQs from s then
2: {Compute initial uncovered neighbors set Uðni;Rs:idÞ for RREQs:}
3: Uðni;Rs:idÞ ¼ NðniÞ _ ½NðniÞ \ NðsÞ_ _ fsg
4: {Compute the rebroadcast delay TdðniÞ:}
5: TpðniÞ ¼ 1 _ jNðsÞ\NðniÞj
jNðsÞj
6: TdðniÞ ¼ MaxDelay _ TpðniÞ
7: Set a Timer(ni;Rs:id) according to TdðniÞ
8: end if
9:
10: while ni receives a duplicate RREQj from nj before Timer(ni;Rs:id) expires do
11: {Adjust Uðni;Rs:idÞ:}
12: Uðni;Rs:idÞ ¼ Uðni;Rs:idÞ _ ½Uðni;Rs:idÞ \ NðnjÞ_
13: discard(RREQj)
14: end while
15:
16: if Timer(ni;Rs:id) expires then
17: {Compute the rebroadcast probability PreðniÞ:}
18: RaðniÞ ¼ jUðni;Rs:idÞj jNðniÞj
19: FcðniÞ ¼ Nc jNðniÞj
20: PreðniÞ ¼ FcðniÞ _ RaðniÞ
21: if Random(0,1) _ PreðniÞ then
22: broadcast(RREQs)
23: else
24: discard(RREQs)
25: end if
26: end if

V. CONCLUSION AND FUTURE RESEARCH

We proposed a probabilistic rebroadcast protocol based on neighbor coverage to reduce the routing overhead in MANETs. This neighbor coverage knowledge includes additional coverage ratio and connectivity factor. Rebroadcast delay is used to determine the forwarding order and more effectively exploit the neighbor coverage knowledge. Our proposed protocol generates less rebroadcast traffic than the flooding and some other optimized scheme in literatures. Because of less redundant rebroadcast, the proposed protocol mitigates the network collision and contention, so as to increase the packet delivery ratio and decrease the average end-to-end delay. The proposed protocol has good performance when the network is in high density or the traffic is in heavy load.
We propose our proposed approach with efficient routing. As well as security is also a challenging factor in adhoc networks. Resisting flooding attacks in ad hoc networks incur two flooding attacks: Route Request (RREQ) and Data flooding attack. In RREQ flooding attack the attacker selects many IP addresses which are not in the network or select random IP addresses depending on knowledge about scope of the IP address in the network. In future we propose a new trust approach based on the extent of friendship between the nodes is proposed which makes the nodes to co-operate and prevent flooding attacks in an ad hoc environment.

References

  1. Xin Ming Zhang, Member, IEEE, En Bo Wang, Jing Jing Xia, and Dan Keun Sung, Senior Member, IEEE, 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) Routing, IETF RFC 3561, 2003.
  3. D. Johnson, Y. Hu, and D. Maltz, The Dynamic Source Routing Protocol for Mobile Ad Hoc Networks (DSR) for IPv4, IETF RFC 4728, vol. 15, pp. 153-181, 2007.
  4. 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.
  5. X. Wu, H.R. Sadjadpour, and J.J. Garcia-Luna-Aceves, “Routing Overhead as a Function of Node Mobility: Modeling Framework and Implications on Proactive Routing,” Proc. IEEE Int’l Conf. Mobile Ad Hoc and Sensor Systems (MASS ’07), pp. 1- 9, 2007.
  6. 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.
  7. 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. Int’l Conf. Wireless Comm. And Mobile Computing: Connecting the World Wirelessly (IWCMC ’09),pp. 1335-1339, 2009.
  8. B. Williams and T. Camp, “Comparison of Broadcasting Techniques for Mobile Ad Hoc Networks,” Proc. ACM MobiHoc, pp. 194-205, 2002.
  9. 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.
  10. 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.
  11. Z. Haas, J.Y. Halpern, and L. Li, “Gossip-Based Ad Hoc Routing,” Proc. IEEE INFOCOM, vol. 21, pp. 1707-1716, 2002.
  12. W. Peng and X. Lu, “On the Reduction of Broadcast Redundancy in Mobile Ad Hoc Networks,” Proc. ACM MobiHoc, pp. 129-130, 2000.
  13. J.D. Abdulai, M. Ould-Khaoua, L.M. Mackenzie, and A. Mohammed, “Neighbour Coverage: A Dynamic Probabilistic Route Discovery for Mobile Ad Hoc Networks,” Proc. Int’l Symp. Performance Evaluation of Computer and Telecomm. Systems (SPECTS ’08), pp. 165-172, 2008.
  14. J. Chen, Y.Z. Lee, H. Zhou, M. Gerla, and Y. Shu, “Robust Ad Hoc Routing for Lossy Wireless Environment,” Proc. IEEE Conf. Military Comm. (MILCOM ’06), pp. 1-7, 2006.
  15. A. Keshavarz-Haddady, V. Ribeirox, and R. Riedi, “DRB and DCCB: Efficient and Robust Dynamic Broadcast for Ad Hoc and Sensor Networks,” Proc. IEEE Comm. Soc. Conf. Sensor, Mesh, and Ad Hoc Comm. and Networks (SECON ’07), pp. 253-262, 2007.