Reliable Data Delivery for Highly Dynamic MANETs

Reliable Data Delivery for Highly Dynamic MANETs

G. V. L. Kalyan1, T. Ramya2

1. M.Tech in Department of Electronics and Communication Engineering, SRM University, Chennai, 600203, INDIA

2. Assistant Professor in Department of Electronics and Communication Engineering, SRM University, Chennai, 600203, INDIA

AbstractDelivering data packets in reliable and timely manner in MANETs is addressed here. Traditional ad hoc routing protocols fail to serve this purpose. A novel routing algorithm called Position based Opportunistic Routing (POR) is proposed here. POR algorithm clubs the advantage of greedy forwarding with broadcast nature of opportunistic routing. When a node send data packets to its one hop neighbor, the nodes which are very nearer to the neighbor can overhear the transmission. Using this overhearing as a backup even when a node fails to transmits a data packet, the overheard candidates will take the task of forwarding data packets. When the node mobility increases, due to random motion of nodes there are more chances of occurring communication holes called voids. In order to deal with these communication holes, a void handling scheme called Virtual Destination based Void Handling (VDVH) is proposed and clubbed with the POR algorithm.

Keywords-greedy forwarding, opportunistic routing, reliable data delivery, void handing, black hole attack.

1. INTRODUCTION

   MANETs consist of wireless mobile nodes which can dynamically move and self-organize among themselves into a temporary network without any preexisting infrastructure. MANETs because of its multi-hop nature, infrastructure less transmission and self-organizing made them to attain a prominent role in the current scenario ([1], [2]). MANETs does not have a fixed topology. Traditional routing algorithms such as DSDV, AODV and DSR are susceptible to node mobility because predetermination of end to end routes is required. In case of MANETs because of constantly changing network topology it is difficult to maintain predetermined routes even before the data transmission ([2]).

   Geographic routing is the one which makes use of location information of the nodes to forward data packets. Here every node has only local view of topology where as other techniques need global view. Every node stores a table which consists of the location information of one-hop neighbors which is obtained by piggybacking periodically ([2]).

   Geographic routing uses the greedy forwarding technique for data forwarding. In greedy forwarding a node selects a next hope node if it is more nearer to the destination than any other nodes in its transmission range. But if the next hop node moves out, then the transmission fails ([3])

   Opportunistic routing (OR) uses the advantage of broadcast nature of wireless medium, which increases the transmission reliability and hence the network throughput. OR will overcome the drawback of unreliable wireless transmission by overhearing. Overhearing means ones transmission can be overheard by many neighboring nodes ([4]).

   In this paper POR algorithm is proposed which incorporates the greedy forwarding with OR. Here neighbors of next hop node which are very near will overhear the transmission. If next-hop node moves away, then the overheard candidates will take the task of forwarding data packets according to a locally formed priority order. In this way at least if one node is carrying the operation of data forwarding successfully the transmission will not fail which increases the robustness and also the throughput ([2]). The work flow of this paper is summarized as follows:

   • In section2 POR algorithm is proposed which can be implemented without any complex modification to MAC protocol.

   • The robustness of the protocol is increased with the concept of the overhearing which reduces the latency greatly.

   • In section3 a virtual destination based void handling scheme (VDVH) is triggered when a communication hole exists. The advantages attained by both greedy forwarding and opportunistic routing are still retained in the VDVH scheme.

   • In section4 we analyzed the performance of packet delivery ratio, end to end delay by changing the nodes mobility.

2. POSITION BASED OPPORTUNISTIC ROUTING

   The design of POR is a combination of geographic routing and opportunistic forwarding. Here there are some basic assumptions.

   • Every node is assumed to be aware of its own location and the position of its one-hop neighbors.

   • Neighbor hood location is obtained either by exchanging one hop beacons or piggybacking.

   • Destinations location is obtained by a location service.

   When a source node wants to transmit a packet, it obtains the location of destination and attaches it to the packet header.

   1. Routing in POR

      The basic routing of POR is explained in Fig 1a, 1b. In normal situations when there is no link break, the packet is forwarded by the next hop node itself (here node A, E). The overheard packet is suppressed by potential backup candidates (nodes B, C and nodes F, G) after seeing the next hops successful transmission.

      When node A fails to forward data packet (node A has moved away and cannot receive the packet) then the backup candidate which has highest priority (here node B) will take the turn of forwarding the packet and the lower priority nodes suppress its overheard packets Then node S will remove node A from its neighbor list and select a new next hop for the next subsequent packets.

      TABLE 1 Forwarding table in POR

      Src_node, Dest_node	Next_hop	Candidate_list
      N1,N11	N4	N5,N6
      N1,N13	N7	N8,N9
      	.	..

      Every node maintains a forwarding table that it has sent or forwarded. Before calculating a new forwarder list, it looks up the forwarding table, an example is shown in Table 1, to check if a valid item for that destination is still available. The forwarding table is constructed during data packet transmission and its maintenance is much easier compared to routing table. As the establishment of forwarding table depends on local information it is much easier to construct.

3. VOID HANDLING TECHNIQUE

   B The occurrence of communication hole is always a serious S A F problem and it is also an important technical challenge for any E geographic routing protocol. Due to unpredictable pattern of

   C node movement in MANETs and uncertain dynamics of time

   varying wireless network environments, it is impossible to

   G predict when and where a void will occur ([5]).

   Fig 1a Operation of POR in normal situation.

   1. Selection of Backup candidates

      The key problem in POR is the selection of backup candidates. Only the nodes which can overhear can serve as backup candidates. A node can overhear next-hop nodes transmission if its distance to the next hop node is less than half of its transmission range (i.e. R/2).

      So an appropriate void handling technique should be used to eliminate the loss of packets and reduce the wasting of network resources. This void handling technique should be triggered only if a data packet encounters a void and greedy forwarding fails at that void node ([5]).

      There are so many void handling techniques like flooding, perimeter routing, planar graph based void handling, bound- hole method etc., ([5]). reviously so many authors have suggested perimeter routing ([8]) as a better complementary void handling technique for geographic routing. But if we use it we are losing the advantage of backup candidates which we got through the opportunistic routing. So in order to retain the advantage of opportunistic routing even in void handling mode an efficient technique called Virtual Destination Based Void Handling (VDVH) is proposed here.

      B A. Virtual Destination Based Void Handling Technique

      S F

      In order to increase the robustness of POR protocol in the

      C E network where the nodes are randomly deployed and there are

      chances of occurring large holes in the network, so a void

      G handling technique based on virtual destination is proposed.

      Fig 1b Operation of POR when next-hop fails to receive the packet.

   2. Prioritizing of Backup candidates

      Nodes specified in the candidate list act as backup candidates. A candidate list will be attached to packet header and is updated hop by hop. The lower the index in candidate list, higher the priority is given.

      • Happening of mode change

        Most of the people get a doubt that at which node the packet forwarding should change from greedy mode to void handling mode. In all existing geographic routing protocols the mode change happen at the void node (the node experiencing the void). If the mode change happens as suggested by existing protocols i.e. at void node, we are losing the advantage got by

        greedy forwarding that is we are not taking optimal path to go around the hole (more number of hops are consumed ) and we are losing the availability of backup candidates. So in order to retain the advantages bought by greedy and opportunistic forwarding the mode change should change at trigger node (the node which forwards packets to a void node).

      • Virtual Destination

   A temporary target called virtual destination is introduced to forward the packets. Later those packets are forwarded to original destination successfully. Here one thing to observe is that routing carried to virtual destination and then to original destination, in the entire journey we are not losing the advantage of greedy forwarding (selecting optimal path) and even we do not lose the advantage bought by opportunistic routing (backup candidates). The only concern is on what basis a virtual destination node is selected.

   One study ([2]) suggests that distance between trigger node and destination node is considered as radius. Then make an offset from original destination which is fair enough to get rid of void. Any node available in that offset region is considered as virtual destination. But here we considered the node which is very near to the trigger node which can establish an alternate path to route around the void as virtual destination.

   Void Node Trigger Node

   Fig 2a Mode change at void node

   In fig 2a, 2b we compared the void handling mechanism triggered both at the void node and at the trigger node and shown that number of hops took to reach the destination node is less when mode change took place at trigger node.

4. PERFORMANCE ANALYSIS

   A flat grid topology of size 1200m * 600m is generated and 40 random nodes are deployed in NS2.35simulation tool. We had simulated POR algorithm and compared with traditional routing protocol called AODV ([5]) without communication hole. And we also created a topology with communication hole and compared the POR-VDVH scheme with GPSR ([6]) protocol. The performance metrics used are:

   • Packet delivery Ratio (PDR): It is a fraction of number of packets successfully received by a destination node to the number of packets sent by source node.

   • End-to-end delay: It is the amount of time taken by a packet to reach from source to destination.

   • Path length: Average number of hops conceived by a packet for a successful delivery to destination node.

   Simulations are performed in two scenarios as mentioned above. Common parameters used are shown in table 2.

   TABLE 2 SIMULATION PARAMETERS

   Parameter	Value
   MAC protocol	IEEE 802.11
   Propagation Model	Two ray ground
   Transmission Range	200metres
   Number of nodes	40
   Packet size	512 bytes
   Traffic type	Constant Bit Rate traffic
   Mobility model	Random Way Point model

   1. Scenario1: Topology without communication hole

      Here a flat grid topology of size 1200m * 600m with uniform distribution of 40 nodes is considered. Performance analysis for POR and AODV protocols are performed and corresponding graphs are plotted for PDR, end-to-end delay by varying the node speed from 1m/s to 50m/s.

      S

      D

      Warning message

      Virtual destination

      Fig 3 Uniformly distributed network topology without communication

      hole.

      p to

      When the node mobility is low i.e. from 1m/s to 25m/s the erformance of AODV for both PDR and end-to-end delay is lerable. When the node mobility increases further i.e. from 25m/s to 50m/s the performance of AODV is degraded where

      Fig 2b Mode change at trigger node

      as our proposed POR protocol outperforms AODV even in

      high mobility situation. The main reason is the availability of two backup candidates. Due to overhearing, along with next hop node the backup candidates also hear the packet transmission. If the next hop node fails to forward data packet a backup candidate with highest priority will take the task of forwarding the packet. In this way POR algorithm provides a satisfactory performance in PDR and end-to-end delay over AODV.

      Fig 4a Packet Delivery Ratio

      Fig 4b End-to-End delay

   2. Scenario2: Topology with Communication hole

   Here same topology as above with a communication hole at the centre is created. Performance analysis for POR-VDVH and GPSR protocols are performed and corresponding graphs are plotted for PDR, end-to-end delay and path length by varying the node speed from 1m/s to 50m/s.

   S

   Communication hole

   D

   Sssss

   Fig 5 Uniformly distributed network topology with a communication hole.

   Generally voids occur when there is unpredictability in nodes movement. If these voids occur there is performance degradation in a network like decrease of PDR, throughput and increase of latency. So using an efficient void handling technique improves the performance. Previously in GPSR protocol face routing is used as void handling mechanism.

   Fig 6a Number of hops vs mobility of node

   This face routing finds an alternate path around the void by traversing through the perimeter of the network. In these re route process it is losing the advantage of greedy routing by not selecting the optimal path. And also when the node speed increases beyond 30m/s its performance is not satisfactory. So a VDVH scheme is proposed which shows optimal performance by selecting an appropriate virtual destination and we are not losing the advantage of greedy forwarding i.e. we are choosing a path with less number of hops and more over we are having backup candidates even in the void handling process which drives in obtaining optimal performance

   REFERENCES

   Fig 6b Packet delivery ratio

   Fig 6c End-to-End delay

5. CONCLUSION

The problem of reliable data delivery in MANETs is addressed here. Due to constantly changing network topology traditional routing algorithms fails to serve the purpose. So an algorithm which takes optimal path by using the location information of direct neighbors and in case of frequent link breakages, backup candidates will continue the transmission of packets to reach the destination.

Another aspect examined here is the effect of communication hole which is inherited from geographic routing. A void handling mechanism which is based on virtual destination is proposed in order to handle the void effectively. VDVH scheme provides satisfactory performance by taking less number of hops compared to GPSR protocol because mode change happens at trigger node in VDVH where it happens at void node in GPSR protocol.

[1]: Imrich Chlamtac a, Marco Conti b, Jennifer J.-N. Liu c, Mobile ad hoc networking: imperatives and challenges Elsevier Ad Hoc Networks 1, pp 1364, 2003

[2]: Shengbo Yang, Chai Kiat Yeo, and Bu Sung Lee Toward Reliable Data Delivery for Highly Dynamic Mobile Ad Hoc Networks, IEEE Transactions on Mobile Computing, Vol. 11, No. 1, January 2012

[3]: Atekeh Maghsoudlou, Marc St-Hilaire, and Thomas Kunz, A Survey on Geographic Routing Protocols for Mobile Ad hoc Networks Carleton University, Systems and Computer Engineering, Technical Report SCE-11-03, October 2011

[4]: Haitao Liu and Baoxian Zhang, Opportunistic Routing for Wireless Ad Hoc and Sensor Networks: Present and Future Directions, IEEE Communications Magazine, December 2009

[5]: Shri Alarmelu.V, R. Poonkuzhali , Dr. M.Y. Sanavullah

An Efficient Void Handling Technique for Geographic Routing in MANET: A Survey, International Journal of Advanced Research in Computer Science and Software Engineering Volume 2, Issue 12, December 2012

[6]: K. Zeng, Z. Yang, and W. Lou, Location-Aided Opportunistic Forwarding in Multirate and Multihop Wireless Networks, IEEE Trans. Vehicular Technology, vol. 58, no. 6, pp. 3032-3040, July 2009.

[7]: S. Das, H. Pucha, and Y. Hu, Performance Comparison of Scalable Location Services for Geographic Ad Hoc Routing, Proc. IEEE INFOCOM, vol. 2, pp. 1228-1239, Mar. 2005.

[8]: B. Karp and H.T. Kung, GPSR: Greedy Perimeter Stateless Routing for Wireless Networks, Proc. ACM MobiCom, pp. 243-254, 2000.

[9]: S. Biswas and R. Morris, EXOR: Opportunistic Multi-Hop Routing for Wireless Networks, Proc. ACM SIGCOMM, pp. 133-144, 2005.

[10]: D. Chen, J. Deng, and P. Varshney, Selection of a Forwarding Area for Contention-Based Geographic Forwarding in Wireless Multi-Hop Networks, IEEE Trans. Vehicular Technology, vol. 56, no. 5, pp. 3111- 3122, Sept. 2007.

[11]:W. Navidi and T. Camp, Stationary Distributions for the Random Waypoint Mobility Model, IEEE Trans. Mobile Computing, vol. 3, no. 1, pp. 99-108, Jan./Feb. 2004.

[12]: The Network Simulator ns-2, http://www.isi.edu/nsnam/ns, 2011

[13]: J. Yoon, M. Liu, and B. Noble, Random Waypoint Considered Harmful, Proc. IEEE INFOCOM, pp. 1312-1321, 2003.