Improving the Proactive Routing Protocol using Depth First Iterative Deepening Spanning Tree in Mobile Ad Hoc Network

Improving the Proactive Routing Protocol using Depth First Iterative Deepening Spanning Tree in Mobile Ad Hoc Network

• 1.
  International Journal ofElectrical and Computer Engineering (IJECE) Vol. 7, No. 1, February 2017, pp. 316~323 ISSN: 2088-8708, DOI: 10.11591/ijece.v7i1.pp316-323  316 Journal homepage: http://iaesjournal.com/online/index.php/IJECE Improving the Proactive Routing Protocol using Depth First Iterative Deepening Spanning Tree in Mobile Ad Hoc Network Justin Sophia I1 , N. Rama2 1 Department of Computer Science, Loyola College, Chennai 600034, India 2 Post Graduate and Research Department of Computer Science, Presidency College, Chennai 600005, India Article Info ABSTRACT Article history: Received Jun 21, 2016 Revised Aug 23, 2016 Accepted Sep 7, 2016 Owing to the wireless and mobility nature, nodes in a mobile ad hoc network are not within the transmission range. It needs to transfer data through the multi-intermediate nodes. Opportunistic data forwarding is an assuring solution to make use of the broadcast environment of wireless communication links. Due to absence of source routing capability with efficient proactive routing protocol, it is not widely used. To rectify the problem, we proposed memory and routing efficient proactive routing protocol using Depth-First Iterative-Deepening and hello messaging scheme. This protocol can conserve the topology information in every node in the network. In experimental analysis and discussion, we implemented the proposed work using NS2 simulator tool and proved that the proposed technique is performed well in terms of average delay, buffer and throughput. Keyword: Depth-first iterative-deepening Hello messaging scheme Proactive source routing Routing Copyright © 2017 Institute of Advanced Engineering and Science. All rights reserved. Corresponding Author: Justin Sophia I, Department of Computer Science, Loyola College, Chennai 600034, India. Email: justinsophia2014@gmail.com 1. INTRODUCTION Recent years several research activities are introduced for exchanging the node in Mobile Ad Hoc Network (MANET). Each node in a MANET works as both a host and router for transmission and receiving a data and also to maintain the information in the time of exchanging the nodes. MANET is one of the wireless communications and it didn’t need any other help from other devices, thus it can operate without exiting infrastructure and other mobile user. The idea behind the MANET is based on multihop wireless networking [1]. MANET individually support for data forwarding and topology discover. The most important operation in the network layer is data forwarding and routing the data in the network [2]. In MANET this network layer protocol forms connectivity to all nodes from hop to neighbors [3]. The concept behind the data forwarding and routing are based on packets. The packets from one link to another link is maintained by data forwarding therefore in this situation which packets are send from the source to destination is maintained by routing concept [4]. Data forwarding through packets prevent the drawbacks in wireless sensor network and helps to know about the present data packet in the network.There are three cases for routing protocol in MANET, they are reactive, proactive and hybrid [9]. The main work behind the reactive protocol is to give the prior location of the destination node. A routing protocol is used to route the packet between mobile nodes within the network. That route should consume minimum overhead and bandwidth. Routing in the ad-hoc wireless network contains challenging approach because of its infrastructure less network and its dynamic topology. Usual routing protocols for wired networks like link state or distance vector are no longer suitable for mobile ad-hoc wireless networks. The dynamic changes in MANET topology, communication between mobile nodes may
• 2.
   ISSN: 2088-8708 IJECEVol. 7, No. 1, February 2017 : 316 – 323 317 be slow due to the low bandwidth. Thus routing information of nodes has changed to adapt current node movement. In this paper the data forwarding is done using a lightweight Proactive Source Routing (PSR) protocol. The Iterative Deepening Depth-First Search (IDFS) combines depth-first search's space-efficiency and breadth-first search's completeness that uses much less memory. Here information is periodically exchanged among neighboring nodes for updated network topology information. By using adaptive Hello messaging scheme the neighbor discovery is effectively suppress the unnecessary Hello messages. This scheme dynamically adjusts Hello intervals, and the risk is reduced for the sender while transmitting a packet through a broken link that is not detected by Hello messaging; Instead of using a constant Hello interval, this proposed scheme uses a constant risk level. As the event interval increases, the Hello interval can also increase without increasing risk. If the event interval is extremely large, the Hello messaging interval is also correspondingly large; that is Hello messaging is practically suppressed. When a node receives or sends a packet, the Hello messaging interval is reset to a default value so that up-to-date information is kept in a neighbor table for active communication. Thus the proposed system with IDFS and adaptive Hello interval helps to reduce battery drain through practical suppression of an unnecessary Hello messaging. Based on the event interval of a node, the Hello interval can be enlarged without reduced detectability of a broken link, which decreases network overhead and hidden energy consumption. Hence it allows supporting of both sources routing andconventional IP forwarding. When doing this, the routing overhead of PSR is reduced. 2. RELATED WORK In [5] proposed a trust based framework in MANET for forwarding of data in networks. Author by counteracting to the dropping data and arbitrarily data have effectively designed a positive forwarding message. This framework also prevents the network against black hole attack. Some of the literature from [6-8] provide the solution for forwarding the data efficiently to a single destination node or group of node in a network. Zehua Wang [10] proposed PSR by maintains network topology using spanning tree. Here the concept of BFS and streamlined differential update technique is used. Wang also propose a new concept, known as CORMAN [11], which is a network layer solution to the opportunistic data transfer in mobile ad-hoc networks. This contains three modules that provide a solution for one of the existing challenges. Behrens and Garcia proposed in 1994 the Link Vector (LV) algorithm [12] reduces the overhead of (Link state) LS algorithms extremely by only including links in data forwarding in routing updates. The extreme case of LV, that one link is included per destination, coincides with the PFA. This technique is initially proposed for the Internet, but their ideas were later used to devise routing protocols in the MANET. A recent work done by Levchenko et al. [13] called approximate link state (XL) contains the LV and PFA in a nutshell. To define the correctness of the routing protocols stretch is used to evaluate the optimality soundness and completeness. XL also uses lazy update concept to further decrease the overhead. Therefore, in XL, node sends update message that contains the changed links which are on the only way that must be passed to a given destination, or the updated link that can improve the cost to a destination node. 3. PROPOSED METHODOLOGY 3.1. Over View of Proactive Source Routing In PSR (proactive source routing) based wireless networks, each node has its own routing table which contain current destination nodes, number of hops needed to reach the destination to broadcast the data packets and the links to be established with other nodes. In PSR, every node has depth-first iterative deepening spanning tree of whole network topology rooted at source node. To maintain the entire network structure information in each node, each iteration nodes in network needs to broadcast the spanning tree structure to the best of knowledge periodically. During recent iteration, information is collected from neighbor nodes. Based on this information, node can expand and refresh its knowledge about the network topology by constructing depth-first iterative-deepening tree. This knowledge will be distributed to its neighbors in the next round of operation. The network model is constructed as undirected graph G = (V, E) (1) where, V is the set of nodes or vertices and E is the set of wireless links or edges.
• 3.
  IJECE ISSN: 2088-8708 Improving the Proactive Routing Protocol using Depth First Iterative Deepening … (Justin Sophia I) 318 Two nodes A and B are connected by edge e = (u, v) belongs to E if they are close to each other and can directly communicate with given reliability. Given node v, N (v) denote its open neighborhood, i.e., {v ∈ V | (u, v) ∈ E}. N [v] denotes its closed neighborhood.During each of iteration an update operation is performed and broadcasted to all nodes in a network. At Starting, node v is single and root node in spanning tree which has knowledge of existence itself. Node V is exchanging spanning tree with the neighbors for construct a DFID within N [v].At the end of each operation interval, node v has collected recent information about routing messages from its neighbors and update its own DFID. It then broadcasts this tree to its neighbors at the end of the period. 3.2. Depth-First Iterative-Deepening A search program finds a goal state starting from the initial state by exploring states in the state space. A search algorithm which suffers neither the drawbacks of breadth-first nor depth-first search on trees is depth-first iterative-deepening (DFID). A brute-force search is a search algorithm that uses no information other than the initial state, the operators of the space, and a test for a solution .depth-first search Iterative deepening is a state space search strategy in which a depth-limited search is run repeatedly, increasing the depth limit with each iteration until it reaches d, the depth of the shallowest goal state. DFID is equivalent to breadth-first search, but uses much less memory on each iteration, it visits the nodes in the search tree in the same order as depth-first search, but the cumulative order in which nodes are first visited is effectively breadth-first. The algorithm works as follows: First, performs a depth-first search to depth one. Then, discarding the nodes generated in the first search, start over and do a depth-first search to level two. Next, start over again and do a depth-first search to depth three, etc., continuing this process until a goalstate is reached. Since DFID expands all nodes at a given depth before expanding any nodes at a greater depth, it is guaranteed to find a shortest-length solution. Also, since at any given time it is performing a depth-first search, and never searches deeper than depth d, the space it uses is O (d). Depth-first iterative-deepening is asymptotically optimal among brute-force tree searches in terms of time, space, and length of solution. The algorithm is described below. DFS depth (N, limit): DFS from the starting state N and with a depth cut off at the depth limit. Do DFS from the starting state N0 without exceeding a given depth limit. a. Length (x, y): the number of edges between a shortest path from the node x and the node y. b. Depth of a node x in a tree = length (root, x). 3.3. Depth-First Iterative-Deepening Algorithm Due to bad channel condition (i.e. link failure) many nodes are in the transmission range of node v, their periodic beacon updates were not received by v. In conventional hello message scheme, link failure information is not need to be updated until its neighbor is involved in communication. T indicates the time interval between when a link failure is recognized and when the link is actually needed. During T, multiple Hello packets are unnecessary. If a node has moved away from the current position where no active nodes are in its neighborhood but broadcast the hello message, energy is consumed unnecessarily. To avoid this problem, Hello packets should be suppressed. To overcome the drawbacks, proposed hello messaging scheme is used. The average Ta is given as Ta = (ALLOWED HELLO LOSS−0.5) ∗ HELLO INTERVAL (2) If the neighboring node moves out of the sender’s transmission range, there are two possible actions: a. Sender is asked to forward or b. Sender is not asked to forward. Consider case (1), because link failure will incur. To rectify the problem, the sender must know the availability of its link to the next hop node prior to forwarding a packet by setting the HELLO INTERVAL.In this paper, we focus on the expiration period respect to a given event interval. By doing this, unnecessary Hello messages are suppressed. In order to avoid the unnecessary Hello messages, calculate the probability of a node forwarding a packet in a given time period. All intervals are smaller than default HELLO INTERVAL (i.e., 1 sec), Analysis the event intervals, x, which are greater than default HELLO INTERVAL since the Hello interval is not changed if the interval is smaller than 1 sec. The cumulative distributed function (CDF) of x is as follows: F(x, β)=1 − e−x/β (3)
• 4.
   ISSN: 2088-8708 IJECEVol. 7, No. 1, February 2017 : 316 – 323 319 The exponential distribution implies that portion of intervals are less than a given interval x. This means that if we use an exponential distribution to estimate the probability that an interval is larger than a given interval, the estimation will give an upper bound. So the probability that an event occurs after a given interval is negligible. We use this analysis to adjust Hello interval conservatively. Take x as a link refresh period (Ta) and F(x, β) as the probability that an event occurs before the link is refreshed, i.e., F (x, β) = . Since a conventional Hello messaging scheme uses a constant value for, varies depending on β. This causes even inactive nodes to broadcast Hello packets periodically. We fix and make a variable so that the Hello interval is adaptive to the average event interval of a node, β. CDF of the exponential distribution using the as follows: 1 − e−x/β = x = −βln(1 − ) (4) x increases linearly as β increases. The neighboring node in the aforementioned two cases can use β for calculating the appropriate Hello interval to maximize Ta and minimize T. Once Td is determined, the Hello messaging interval of the neighboring node can be calculated with equation 1. With real traffic, the risk of sending a packet over a broken link will be less than in above equation because is the upper bound obtained by an exponential distribution. Node v responds by: a. First, updating N (v) with N (v) − {u}; b.Then, constructing the graph with the information of u removed, c. Finally, computing Tv. 4. EXPERIMENT AND RESULT In the experiment and result, we discussed and analyzed the routing nature of network using the proposed proactive routing protocol. The proposed methodology is implemented using NS-2 simulator which is common and well known network simulator tool mainly used in the simulation area of MANET, wireless sensor network, VANET etc. The proposed network simulation model consist of minimum 50 mobiles nodes in the dimension of 1000* 1000 initially.The analysis and evaluation is done by DFID and messaging scheme based tree construction in proactive routing protocol. The proposed work is compared with existing lightweight proactive protocol. The simulation parameters are used while developing proposed work which is detailed below in the Table 1. These parameters are used for construct the network. Table 1. Simulation Parameters Parameters Values Channel type Wireless Channel radio-Propagation model Two Ray Ground network interface type Wireless Phy MAC type 802_11 interface queue type Drop Tail /Pri Queue Radio Range 250M link layer type LL antenna model Omni Antenna max packet 50 (Minimum:512bytes, Maximum: 10,000bytes) number of mobile nodes 50 (Minimum:50, Maximum: 200) routing protocol AODV Simulation time 200 s(Minimum:200s, Maximum:10000s) X dimension of topography 1000 Y dimension of topography 1000 traffic CBR(Constant Bit Rate) Node Speed 5,10,15,20,25,30s Mobility Model Random Way point 4.1. Constant Bit Rate In this section, the comparative performance of average delay, overhead, packet delivery ratio an bandwidths are discussed with the constant bit rate of proposed work and existing work. In Figure 1, Average delay of proposed protocol is low compared to the existing protocol. It is represented by milliseconds with low average delay while varying the constant bit rate in proposed work.
• 5.
  IJECE ISSN: 2088-8708 Improving the Proactive Routing Protocol using Depth First Iterative Deepening … (Justin Sophia I) 320 In Figure 2, Overhead of proposed protocol is low compared to the existing protocol. It shows that the low Overhead (in milliseconds) while varying the constant bit rate in proposed work. In Figure 3, Packet delivery ratio (in %) of proposed protocol is high compared to the existing protocol. It shows that the high packet delivery ratio while varying the constant bit rate in proposed work. In Figure 4, Bandwidth (in milliseconds) of proposed protocol is high compared to the existing protocol. It shows that the high bandwidth while varying the constant bit rate in proposed work. Figure 1. Average delay Vs Constant bit rate Figure 2. Overhead Vs Constant bit rate Figure 3. Packet delivery ratio Vs Constant bit rate Figure 4. Bandwidth Vs Constant bit rate 4.2. Nodes In this section, comparison of performance of average delay, overhead, packet delivery ratio, Buffer utilization and bandwidth with varying nodes of proposed work and existing work are discussed. In the below Figure 5, Buffer utilization of proposed protocol is high compared to the existing protocol and shows that the high Buffer utilization while varying the nodes in proposed work. In Figure 6, Average delay (in milliseconds) of proposed protocol is low compared to the existing protocol and shows that the low average delay while varying the nodes. In Figure 7, Overhead of proposed protocol is low compared to the existing protocol and shows that the low overhead occurred during packet transfer while varying the nodes. In Figure 8, Packet delivery ratio (in %) of proposed protocol is high compared to the existing protocol. It shows that the high packet delivery ratio while varying the nodes. In figure 9, Bandwidth (Kbps) of proposed protocol is high compared to the existing protocol and shows that the high bandwidth while varying the constant bit rate.
• 6.
   ISSN: 2088-8708 IJECEVol. 7, No. 1, February 2017 : 316 – 323 321 Figure 5. Buffer utilization Vs varying nodes Figure 6. Average delay Vs varying nodes Figure 7. Overhead Vs varying nodes Figure 8. Packet delivery ratio Vs varying nodes Figure 9. Bandwidth Vs varying nodes 4.3. Speed In this section, performance of average delay, overhead, packet delivery ratio and bandwidth with varying speed of proposed work is compared with existing work. The Figure 10 shows the buffer utilization of proposed protocol with the existing protocol and shows the high Buffer utilization while varying the speed. In Figure 11, Average delay (in milliseconds) of proposed protocol is low compared with existing protocol. In Figure 12, Overhead of proposed protocol is low compared with the existing protocol.
• 7.
  IJECE ISSN: 2088-8708 Improving the Proactive Routing Protocol using Depth First Iterative Deepening … (Justin Sophia I) 322 In Figure 13, packet delivery ratio (in %) of proposed protocol is high compared with the existing protocol while varying the constant bit rate. In Figure 14, Bandwidth (in milliseconds) of proposed protocol is high compared with the existing protocol while varying the constant bit rate.From the result, it is understand that the proposed method provides result in terms of overhead, packet delivery ratio, bandwidth, average delay and buffer utilization with varying speed, nodes and constant bit rate. Figure 10. Buffer utilization Vs varying nodes Figure 11. Average delay Vs varying speed Figure 12: Overhead Vs varying speed Figure 13: Packet delivery ratio Vs varying speed Figure 14. Bandwidth Vs varying speed
• 8.
   ISSN: 2088-8708 IJECEVol. 7, No. 1, February 2017 : 316 – 323 323 5. CONCLUSION In this paper, memory and routing efficient proactive routing protocol is proposed to assist opportunistic data forwarding in MANETs. In PSR, every node in network conserves spanning tree of the network rooted itself. This information is periodically exchanged among neighboring nodes for updated network topology information. Thus, PSR allows a node to have full-path information to all other nodes in the network, although the communication cost is only linear to the number of the nodes. This allows it to support both source routing and conventional IP forwarding. When doing this, we try to reduce the routing and memory overhead of PSR as much as we can. The simulation results indicate that PSR has only a fraction of overhead than existing work. REFERENCES [1] Chlamtac I, Conti M, Liu JJ. “Mobile ad hoc networking: imperatives and challenges”, Adhoc networks. 2003 Jul 31; 1 (1): 13-64. [2] Papadimitratos P, Haas ZJ. “Secure message transmission in mobile ad hoc networks”, Ad Hoc Networks. 2003 Jul 31; 1(1): 193-209. [3] Mamatha GS, Sharma DS, “Network Layer Attacks and Defense Mechanisms in MANETS-A Survey”, International Journal of Computer Applications (0975–8887) Volume, 2010 Nov. [4] Periyasamy P and Nirmalsam S, “Reducing Retransmission Delay in Mobile-ADHOC–Network (MANET)”, International Journal of Scientific and Research Publications, Volume 4, Issue 4, April 2014, ISSN 2250-3153. [5] Li N, Das SK., “A trust-based framework for data forwarding in opportunistic networks”, Ad Hoc Networks. 2013 Jun 30; 11(4): 1497-509. [6] Boldrini C, Conti M, Passarella A. “Exploiting users’ social relations to forward data in opportunistic networks: The HiBOp solution”, Pervasive and Mobile Computing. 2008 Oct 31; 4(5): 633-57. [7] Burgess J, Gallagher B, Jensen D, Levine BN. “MaxProp: Routing for Vehicle-Based Disruption-Tolerant Networks”, InINFOCOM 2006 Apr 23 (Vol. 6, pp. 1-11). [8] Lindgren A, Doria A, Schelén O. “Probabilistic routing in intermittently connected networks”. ACM SIGMOBILE mobile computing and communications review. 2003 Jul 1; 7(3): 19-20. [9] Royer EM, Toh CK., “A review of current routing protocols for ad hoc mobile wireless networks”, IEEE personal communications. 1999 Apr; 6(2): 46-55. [10] Wang Z, Li C, Chen Y. “PSR: Proactive Source Routing in Mobile Ad Hoc Networks”, In Global Telecommunications Conference (GLOBECOM 2011), 2011 IEEE 2011 Dec 5 (pp. 1-6), IEEE. [11] Wang Z, Chen Y, Li C. “CORMAN: A novel cooperative opportunistic routing scheme in mobile Ad hoc networks”, IEEE Journal on Selected Areas in Communications. 2012 Feb; 30(2): 289-96. [12] Behrens J, Garcia-Luna-Aceves JJ. “Distributed, scalable routing based on link-state vectors”, In ACM SIGCOMM Computer Communication Review 1994 Oct 1 (Vol. 24, No. 4, pp. 136-147), ACM. [13] Levchenko K, Voelker GM, Paturi R, “Savage S. XL: An efficient network routing algorithm”, In ACM SIGCOMM Computer Communication Review 2008 Aug 17 (Vol. 38, No. 4, pp. 15-26), ACM. BIOGRAPHY OF AUTHOR Justin Sophia. I Lecturer, Department of Computer Science, Loyola College, Chennai 600034. Email: justinsophia2014@gmail.com