Research and Reviews - International Journals

Journal of Global Research in Computer Sciences

Menu

ISSN: 2229-371X

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.

A PROBABILISTIC REBROADCAST FOR REDUCING ROUTING OVERHEAD IN A REAL TIME MANET ENVIRONMENT

C.Rajan*1, C.Dharanya2 , Dr.N.Shanthi 3
  1. Assistant Professor, Dept of Information Technology, K.S.Rangasamy College of Technology, Tiruchngode, India.
  2. P.G Scholar, Dept of Information Technology, K.S.Rangasamy College of Technology, Tiruchngode, India.
  3. Dean, Dept of Computer Science and Engineering, Nandha Engineering College, Erode, India.
Related article at Pubmed, Scholar Google

Visit for more related articles at Journal of Global Research in Computer Sciences

Journal of Global Research in Computer Sciences

Abstract

Mobile Ad Hoc Network (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. MANETs are highly dynamic network because nodes may join and leave the network at any time. It has limited network capacity. Quality of Service routing in such networks is usually limited by the network breakage due to either energy depletion or node mobility of the mobile nodes. Mobility of nodes may cause 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 discussed a probabilistic rebroadcast for reducing routing overhead in a real-time MANET environment.

Keywords
Mobile ad hoc networks, dynamic networks, routing overhead, neighbor coverage and network connectivity

INTRODUCTION
A mobile ad-hoc network (MANET) is a self-configuring network of mobile routers (and associated hosts) connected by wireless links - the union of which form a random topology. The routers are free to move randomly and organize themselves at random; thus, the network's wireless topology may change rapidly and unpredictably. Such a network may operate in a standalone fashion, or may be connected to the larger Internet. Minimal configuration and quick deployment make ad hoc networks suitable for emergency situations like natural or human-induced disasters, military conflicts, emergency medical situations etc.
The traditional routing protocols for MANETs undertakes set-up and maintain routes between nodes. The existing routing protocols may be categorized into Proactive and Reactive routing protocols. e.g. Destination Sequenced Distance Vector (DSDV) , Optimized Link State Routing (OLSR), Reactive / On-demand, e.g. Ad hoc On-Demand Distance Vector routing protocol (AODV)[12], Dynamic Source Routing Protocol (DSR), Temporally Ordered Routing Algorithm (TORA) and Hybrid, e.g. Hybrid Ad hoc Routing Protocol (HARP) , Zone Routing Protocol (ZRP) attempt to provide only best effort delivery. Their target is limited to finding the minimum hops or the shortest paths[16].
In MANETs continuously changing network topology causes link breakage and termination of end-to-end route. The routing protocols need to resolve the link failure prediction. In conventional on-demand routing protocols use flooding to discover a route to a particular destination. They broadcast a Route REQuest (RREQ) packet to its immediate neighbours, and the broadcasting induces excessive redundant retransmissions of RREQ packet and causes the broadcast storm problem [2], which leads to a huge number of packet collisions, especially in dense networks. Therefore, it is essential to optimize this broadcasting mechanism.
Williams and Camp [3] The broadcasting protocols are classified into four classes. They are “probability based methods, simple flooding, neighbour knowledge methods and area based methods”. 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 methods and area based methods.
Kim et al. [4] indicates that the performance of neighbour knowledge methods is better than the area based ones, and the performance of area based methods is better than that of probability based ones.
These problems put in force to design a simple, scalable, robust and energy efficient routing protocol for multicast environment. A multicast Ad hoc on- demand Distance Vector routing protocol (MAODV) establishes and maintains a shared multicast routing tree to deliver data from a source to receivers of a multicast group.

LITERATURE REVIEW
In order to facilitate communication within the network, a routing protocol is used to discover routes between nodes. The primary goal of such an ad-hoc network routing protocol is correct and efficient route establishment between a pair of nodes so that messages may be delivered in a timely manner. Route construction should be done with a minimum of overhead and bandwidth consumption. An Ad-hoc routing protocol is a convention or standard that controls how nodes come to agree which way to route packets between computing devices in a MANET. In ad-hoc networks, nodes do not have a priori knowledge of topology of network around them, they have to discover it. The basic idea is that a new node announces its presence and listens to broadcast announcements from its neighbours. The node learns about new near nodes and ways to reach them, and announces that it can also reach those nodes. As time goes on, each node knows about all other nodes and one or more ways how to reach them. Recently, the issue of reducing the routing overhead associated with route discovery and maintenance in on demand routing protocols has attracted increasing attention[17].
Huang [9] proposed a methodology of dynamically adjust the Hello timer and Timeout timer according to the conditions of the network. For example, in a high mobility network it is desirable to use small values for the timers to quickly detect the changes in the network. On the other hand, in a low mobility network where the topology remains stable and with few changes, a large value for the timers is more effective to reduce the route overhead. In order to decide whether the mobility of the network is high or low, we use a simple way to approximate in real time of the link change rate. The reduction of the overhead is greatly achieved with the minimal cost of slightly increasing the drop rate in data traffic. While the packet loss increases around 1%, the overhead reduction reaches 40%.
Aminu [10] proposed a rebroadcast probability function which takes into account about the value of the packet counter together with some key simulation parameters(i.e., network topology size, transmission range and number of nodes) to determine the appropriate rebroadcast probability for a given node. The rebroadcast probability of a node is computed based on these parameters. Compared to the other schemes, simulation results have revealed that counter Function achieved superior saved rebroadcast and end-to-end delay without sacrificing reach ability in medium and dense networks.
Ould-Khaoua [11] proposed two new probabilistic route discovery methods. They are Adjusted Probabilistic route discovery (AP) and Enhance Adjusted Probabilistic route discovery (EAP).This addresses the broadcast storm problem in the existing on-demand routing protocols. The forwarding probability is determined by taking into account about the local density of the sending node. In order to reduce the routing overhead without degrading the network throughput in dense networks, the forwarding probability of nodes located in sparse areas is set high while it is set low at nodes located in dense areas. EAP-AODV reduces overhead by 71% while APAODV reduces the overhead by 55%.
image
MAODV [8] is a multicast extension for AODV protocol. MAODV based on shared trees on-demand to connect multicast group members. MAODV has capability of unicast, broadcast, and multicast. MAODV protocol can be route information obtained when searching for multicast; it can also increase unicast routing knowledge and vice-versa. When a node wishes to join a multicast group or it has data to send to the group but does not has a route to that group, it originates a route request (RREQ) message. Only the members of the multicast group respond to the join RREQ. If an intermediate node receives a join RREQ for a multicast group of which it is not a member or it receives a route RREQ and it does not have a route to that group, it rebroadcast the RREQ to its neighbours. But if the RREQ is not a join request any node of the multicast group may respond.
The multicasting technique is used to reducing the routing overhead and improve the routing performance.

NEIGHBOUR COVERAGE BASED PROBABILISTIC REBROADCAST (NCPR) PROTOCOL
This paper proposes neighbour coverage based probabilistic rebroadcast protocol [12] which combines both neighbour coverage and probabilistic methods. In order to effectively exploit the neighbor coverage knowledge, we need a novel rebroadcast delay to determine the rebroadcast order, and then we can obtain a more accurate additional coverage ratio. In order to keep the network connectivity and to reduce the redundant retransmissions, we need a metric named connectivity factor to determine how many neighbours should receive the RREQ packet [13]. After that, by combining the additional coverage ratio and the connectivity factor, we introduce rebroadcast probability, which can be used to reduce the number of rebroadcasts of the RREQ packet and to improve the routing performance.

A. Rebroadcast Delay:
We proposed a scheme to calculate the rebroadcast delay. The rebroadcast delay is to determine the forwarding order. The node which has more common neighbors with the previous node has the lower delay. If this node rebroadcasts a packet, then more common neighbors will know this fact [14]. Therefore, this rebroadcast delay enables the information about the nodes which have transmitted the packet to more neighbors, 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 neighbor nodes. To sufficiently exploit the neighbor coverage knowledge, it should be disseminated as quickly as possible. When node s sends an RREQ packet, all its neighbours ni, i = 1, 2 …receive and process the RREQ packet. We assume that node nk has the largest number of common neighbors with node s, node nk has the lowest delay. Once node nk rebroadcasts the RREQ packet, there are more nodes to receive the RREQ, because node nk has the largest number of common neighbors. Node nk rebroadcasts the RREQ packet depends on its rebroadcast probability calculated in the next subsection. The objective of this rebroadcast delay is not to rebroadcast the RREQ packet to more nodes, but to disseminate the neighbour coverage knowledge more quickly. After determining the rebroadcast delay, the node can set its own timer.
B. Rebroadcast Probability: We also proposed a novel scheme to calculate the rebroadcast probability. The scheme considers the information about the uncovered neighbours, connectivity metric and local node density to calculate the rebroadcast probability. The rebroadcast 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. The node which has a larger rebroadcast delay may listen to RREQ packets from the nodes which have lowered one [13]. We do not need to adjust the rebroadcast delay because the rebroadcast delay is used to determine the order of disseminating neighbour coverage knowledge. When the timer of the rebroadcast delay of node ni expires, the node obtains the final uncovered neighbour set. The nodes belonging to the final uncovered neighbour 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 neighbourhood, its uncovered neighbour set is not changed, which is the initial uncovered neighbor set. Now we study how to use the final uncovered neighbour set to set the rebroadcast probability. The metric Ra 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, 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 [3] derived that if each node connects to more than 5.1774 log n of its nearest neighbours, then the probability of the network being connected is approaching 1 as n increases, where n is the number of nodes in the network. Then we can use 5.1774 log n as the connectivity metric of the network. We assume 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).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. In this section, we calculate the rebroadcast delay and rebroadcast probability of the proposed protocol. We use the upstream coverage ratio of an RREQ packet received from the previous node to calculate the rebroadcast delay, and use the additional coverage ratio of the RREQ packet and the connectivity factor to calculate the rebroadcast probability in our protocol, which requires that each node needs its 1-hop neighbourhood information.

C. Algorithm Description:
The formal description of the Neighbour Coverage based Probabilistic Rebroadcast (NCPR) for reducing routing overhead in route discovery is shown in algorithm [1].
image
26: end if
NCPR protocol needs Hello packets to obtain the neighbour information, and also needs to carry the neighbour list in the RREQ packet. Therefore, in our implementation, some techniques are used to reduce the overhead of Hello packets and neighbour list in the RREQ packet, which are described as follows:
• In order to reduce the overhead of Hello packets, we do not use periodical Hello mechanism. Since a node sending any broadcasting packets can inform its neighbours of its existence, the broadcasting packets such as RREQ and route error (RERR) can play a role of Hello packets. We use the following mechanism [15] to reduce the overhead of Hello packets: Only when the time elapsed from the last broadcasting packet (RREQ, RERR, or some other broadcasting packets) is greater than the value of HelloInterval, the node needs to send a Hello packet. The value of HelloInterval is equal to that of the original AODV.
• In order to reduce the overhead of neighbour list in the RREQ packet, each node needs to monitor the variation of its neighbour table and maintain a cache of the neighbour list in the received RREQ packet. We modify the RREQ header of AODV, and add a fixed field num neighbours which represents the size of neighbour list in the RREQ packet and following the num neighbours is the dynamic neighbour list. In the interval of two close followed sending or forwarding of RREQ packets, the neighbour table of any node ni has the following 3 cases:
1) If the neighbour table of node ni adds at least one new neighbour nj , then node ni sets the num neighbours to a positive integer, which is the number of listed neighbours, and then fills its complete neighbour list after the num neighbours field in the RREQ packet. It is because that node nj may not have cached the neighbour information of node ni, and, thus, node nj needs the complete neighbour list of node ni;
2) If the neighbour table of node ni deletes some neighbours, then node ni sets the num neighbours to a negative integer, which is the opposite number of the number of deleted neighbours, and then only needs to fill the deleted neighbours after the num neighbours field in the RREQ packet;
3) If the neighbour table of node ni does not vary, node ni does not need to list its neighbours, and set the num neighbours to 0.
The nodes which receive the RREQ packet from node ni can take their actions according to the value of num neighbours in the received RREQ packet:
1) if the num neighbours is a positive integer, the node substitutes its neighbour cache of node ni according to the neighbour list in the received RREQ packet;
2) if the num neighbours is a negative integer, the node updates its neighbour cache of node ni and deletes the deleted neighbours in the received RREQ packet;
3) if the num neighbours is 0, the node does nothing. Because of the two cases 2 and 3, this technique can reduce the overhead of neighbour list listed in the RREQ packet.

CONCLUSION
In this paper a probabilistic rebroadcast protocol based on neighbour coverage to reduce the routing overhead in MANETs is discussed. This neighbour coverage knowledge includes additional coverage ratio and connectivity factor. We proposed a new scheme to dynamically calculate the rebroadcast delay, which is used to determine the forwarding order and more effectively exploit the neighbour coverage knowledge. 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. Finally multicasting is used to reduce the routing overhead and Quality of Service is maintained in MANETs.

References
  1. A Neighbour Coverage based Probabilistic Rebroadcast for Reducing Routing Overhead in Mobile Ad hoc Networks Xin Ming Zhang, Member, IEEE, En Bo Wang, Jing JingXia,and Dan Keun Sung, Senior Member, IEEE,2012.
  2. S. Y. Ni, Y. C. Tseng, Y. S. Chen, and J. P. Sheu. “The Broadcast Storm Problem in a Mobile Ad hoc Network,” Proc. of ACM/IEEE MobiCom’99, pp. 151-162, 1999.
  3. B. Williams and T. Camp, “Comparison of Broadcasting Techniques for Mobile Ad Hoc Networks,” Proc. ACM MobiHoc’02, pp. 194-205, 2002.
  4. J. Kim, Q, Zhang, and D. P. Agrawal, “Probabilistic Broadcasting Based on Coverage Area and Neighbour Confirmation in Mobile Ad hoc Networks,” Proc. of IEEE GLOBECOM’04, 2004.
  5. X.M. Zhang, E.B. Wang, J.J. Xia, and D. K. Sung, “An Estimated Distance based Routing Protocol for Mobile Ad hoc Networks,” IEEE Transactions on Vehicular Technology, vol.60,no.7, pp.3473-3484,Sept. 2011.
  6. 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. of SPECTS’08, pp. 165-172, 2008.
  7. J. Chen, Y. Z. Lee, H. Zhou, M. Gerla, and Y. Shu, “Robust Ad Hoc Routing for Lossy Wireless Environment,” Proc. of MILCOM’06, pp. 1-7, 2006.
  8. Elizabeth M. Royer and Charles E. Perkins: “Multicast Operation of the Ad- hoc On-Demand Distance Vector Routing Protocol", In Proc. of the 5th annual ACM/IEEE International Conference on Mobile Computing and Networking (MobiCom),. 207 - 218 August (1999).
  9. D. Johnson, Y. Hu, and D. Maltz, “The Dynamic Source Routing Protocol for Mobile Ad hoc Networks (DSR) for IPv4,” RFC 4728, 2007.
  10. Mohammed, M. Ould-Khaoua, L.M. Mackenzie, C. Perkins, and J. D. Abdulai, “Probabilistic Counter-Based Route Discovery for Mobile Ad Hoc Networks,” Proc. of WCMC’09, pp. 1335-1339, 2009.
  11. X. Wu, H. R. Sadjadpour, and J. J. Garcia-Luna-Aceves, “Routing Overhead as A Function of Node Mobility: Modelling Framework and Implications on Proactive Routing,” Proc. of IEEE MASS’07, pp. 1-9, 2007.
  12. R.Mohan, C.Rajan, Dr.N.Shanthi, “ A Stable Mobility Model Evaluation Strategy for MANET Routing Protocols,” IJARCSSE, December 2012.
  13. J. D. Abdulai, M. Ould-Khaoua, and L. M. Mackenzie, “Improving Probabilistic Route Discovery in Mobile Ad Hoc Networks,” Proc. Of IEEE Conference on Local Computer Networks, pp. 739-746, 2007.
  14. Network Simulator - ns-2 http://www.isi.edu/nsnam/ns/.
  15. X.M. Zhang, E.B. Wang, J.J. Xia, and D.K. Sung, “An Estimated Distance Based Routing Protocol for Mobile Ad Hoc Networks,” IEEE Trans. Vehicular Technology, vol. 60, no. 7, pp. 3473-3484, Sept. 2011.
  16. P. Chandra Sekhar , M.R. Pavan Kumar , K.S. Ranjith, E. Purushottam , Ch. Koteswararao " Impact Of Routing Overhead In A Real-Time MANET Environment" IJCTA, Vol 4 (2), 257-263, Apr 2013.
  17. Vinayak T. Patil , Asst. Prof. Padma,S. Dandannavar, "A Novel Rebroadcast Technique for Reducing Routing Overhead In Mobile Ad Hoc Networks" IOSR-JCE, Aug. 2013.