Movement Models Based Performance
Comparison of Routing Protocols in Delay
Tolerant Networks

Vinit Kumar; Anita Singhrova

Movement Models Based Performance Comparison of Routing Protocols in Delay Tolerant Networks

Vinit Kumar¹, Anita Singhrova²

M-Tech, Department of CSE, DCR University of Science & Technology, Murthal, Haryana, India
Professor, Department of CSE, DCR University of Science & Technology, Murthal, Haryana, India

Related article at Pubmed, Scholar Google

Visit for more related articles at International Journal of Innovative Research in Science, Engineering and Technology

Abstract

Delay-tolerant networks have the great potential to connecting devices and regions of the world that are being presently under-served by current networks. A challenge for Delay Tolerant Networks is to determine the routes through the network without having an end to end connection at any given instant of time. In DTN the routing of packets is done using store-carry-forward mechanism. In this paper, four popular routing protocols in DTN namely; Epidemic, Direct Delivery, Spray & Wait, Prophet have been considered for performance evaluation. The performance of these routing protocols has been evaluated using Shortest Path Movement models

Keywords

Delay-tolerant networks, Routing protocols, Message Delivery, Simulation

I. INTRODUCTION

DTN is an intermittently connected Network where the end-to-end paths may not exist and communication routes may only be available through time and mobility [1].Delay tolerant networking has received considerable attention from the research Community in recent years. Since in DTN, the path to destination is not connected, so the main issue for routing the packets is to find out the intermediate nodes through which the packet will be routed [2, 3]. When two nodes come in contact with each other, they may exchange the packets and such an opportunity is known as encounter. Routing and forwarding of data packets in DTN is a challenging task because of the uncertainty of mobility and intermittent behavior of the nodes [4]. There are several issues in Delay Tolerant Networks that needs to be addressed. The most crucial factor is encounter schedule, network capacity, storage capacity, energy etc [5]. DTNs may be characterized by combination of any of the following:

a) Intermittent Connection: As the node’s mobility and energy are limited, DTN frequently disconnects, thus resulting in continues change in DTN topology.

b) Limited resource: Node’s computing and processing ability, communication ability and storage space is weaker than the function of an ordinary computer due to the constraints of price, volume and power.

c) Dynamic topology: The DTN topology changes dynamically due to environmental changes, energy depletion or other failures, which results in dropping out of network. The requirements of entering DTN also change the topology.

d) Poor Security: In general, DTN is vulnerable to eavesdropping, message modification, routing spoofing, Denial of Service (DoS), and other security threats.

1.1 Need for Delay Tolerant Networks

a) Lack of Connectivity:If at any moment, there is no end-to-end path between source and destination, thenend-to-end communication cannot take place using the TCP/IP protocols suite. Here DTN comes into picture.

b) Irregular Delays: The long propagation delays between transmitting nodes compounded with queuing delay at each node can topple the TCP/IP protocols which rely largely on quick return of acknowledgement of a sent data. This can be overcome using DTNs.

c) Asymmetric Bidirectional Data Rates:Moderate asymmetries of bidirectional data rate can be tolerated to an extent in conventional protocols. But if asymmetries are large, protocols can be defeated easily.

1.2 Architecture

A Delay Tolerant Network can be considered as an overlay on the existing regional networks. This overlay is called as the bundle layer. This layer is intended to function above the existing protocol layers and provide the function of a gateway when two nodes come in contact with each other. The main advantage of this kind of protocol is flexibility. It can be easily linked with the already existing TCP/IP protocol networks or can be used to link two or more networks together. The position of the bundle layer can be seen in the following fig. 1.

Bundles are also called as messages. The transfer of data from one node to another can be made reliable by storing and forwarding entire bundles between nodes. The bundles comprise of three things, source node’s userdata, control information (e.g., source node ID, destination node ID, TTL etc.), and a bundle header.

II. BACKGROUND & RELATED WORK

In this Section, an overview off our routing protocols for DTN, namely Epidemic, Direct Delivery, Spray &wait and Prophet, along with their relative pros and cons have been described.

2.1 Epidemic

One of the earliest and probably the simplest protocols proposed for data delivery in DTNs is epidemic routing [6].This routing scheme results in inefficient use of the network resources such as power, bandwidth, and buffer at each node. Davisetal.[7]improved the basic epidemic scheme with the introduction of adaptive dropping policies. Harra setal.[8]further introduced Time-To-Live (TTL)as well as an expiry time associated with every message for controlled flooding in DTNs.

2.2 Prophet

The Prophet approach is based on the delivery predictability metric which is calculated at each node. This metric is calculated so that a node with a higher value for certain destination is estimated to be a better candidate for delivery a bundle to the destination. When two nodes meet each other, they exchange the value of the metrics for different known destinations.

Epidemic Routing performs well if network resources are unlimited. But in reality, the network resources like bandwidth, buffer space are limited. Therefore, in order to leverage mobility and use scarce resources efficiently, Lindgren et al. [9] proposed the Probabilistic Routing Protocol using History of Encounters and Transitivity (Prophet) . In this approach, sender forwards the message to the node having the highest probability of successful message delivery. This mechanism relies on the implicit assumption that all the nodes cooperate to message forwarding. This protocol has less message exchanges, less communication overhead, less delay, and higher delivery success rate as compared to the Epidemic Routing.

2.3 Spray and Wait

Spyropoulosetal.[10]proposed an effective routing approach named Spray and wait routing scheme to control the flooding in the network. In this routing scheme, there are two different phases:

a) Spray phase(only once):L message copies are initially spread to L distinct "relays".

b) Wait phase: If the destination is not reached in the spray phase, the L nodes carrying a message copy perform direct transmission

This protocol has less number of transmissions and less delivery delay as compared to the Epidemic Routing

2.4 Direct Delivery

This data delivery scheme is one of the simplest possible where a source delivers a packet to a destination when it comes in direct-contact. In other words, the source waits till it comes in radio range of the destination and then directly delivers the packet to the same. This scheme does not consume any additional resources and makes no additional copies of the data. However, the major limitation is that the delivery delay can be extremely large and in many cases the source and the destination may never come in direct-contact of each other[11].

III. ALGORITHMS

2.5 Random Direction:

This Algorithm focusses to "An Analysis of the Optimum Node Density for Ad hoc Mobile Networks" In This Algorithms nodes will start at a random place on the simulation area and pick a random direction and follow it to the edge of the simulation area. They will then pause and pick another direction to go in until they hit the edge again.

2.6 MapBased:

This Algorithm gives out Paths that use the roads of a SimMap from one node to another node of the Simulation Area..

2.7 Proposed Algorithms: Shortest Path Based

The Algorithm focusses mainly on energy efficiency by reducing the average number of messages forwarded from source to destination uses Dijkstra's algorithm to find shortestpaths between two random map nodes and Points Of Interest. It is assumed that the nodes are mobile in 4500cm by 3400cm area.

The proposed algorithm has the following Tradeoff:

a) Table size which is stored in every node occupies space.

b) Updation of table is dynamically due to change in location of the node.

IV. SIMULATION SETUP

The ONE simulator could be run on Linux, Windows, or any other platform supporting Java [12].

The ONE is a simulation environment that is capable of

a) Generating node movement using different movement models.

b) Routing messages between nodes with various DTN routing algorithms and sender and receiver types.

c) Visualizing both mobility and message passing in real time in its graphical user interface. In this work, ONE simulator [13] is used for the simulation. In this work, the nodes are assumed mobile in nature. The different simulation parameters taken in this work are given as per below table:

The setting and configurations used for varying the fields areas follows:

Varying the number of nodes: The nodes are increased as: 20->40->60->80->100, with an increment of 20 nodes in each group in each simulation. The time to live field is set to 300 seconds and all nodes moves according to their respective group speeds.

The following performance metrics are considered for comparative analysis of the routing protocols:

Throughput: It is defined as the ratio of number of messages delivered to destination and number of messages created by source node.

Message delivery probability: It is the probability of the messages that are correctly received by the destination within a given time period.

Overhead ratio: It is defined as:

Average buffer time: It is the average time for which messages stayed in the buffer at each node.

Average Latency: It is defined as the average message delay from creation to delivery

V. SIMULATION RESULTS

The movement model wise simulation results obtained with the present setup are represented in the following section.

5.1Throughput:

Throughput obtained for different mobility models for different routing scheme are depicted in Figures 3 to 6. It is clear that as the number of nodes increases, the throughput also increases. The throughput is highest in case of Shortest Path Based Movement Model and Minimum for Random Direction Movement Modal.

5.2 Packet Delivered:

Packet Delivered obtained for different mobility models for different routing scheme are depicted in Figures 7 to 10. It is clear that as the number of nodes increases, the Delivery of Packet also increases. The Delivered Packet is Maximum in case of Shortest Path Based Movement Model and Minimum for Random Direction Movement Modal.

5.3 Average Buffer Time:

Average Buffer Time for Delivery of Packet obtained for different mobility models for different routing scheme are depicted in Figures 11 to 14. It is clear that as the number of nodes increases, the Average buffer Time for Packet decrease for Epidemic and Prophet Scheme. The Average Buffer Time for Direct Delivery and Spray & Wait will increase with increase in number of nodes because Packet not delivered to next nodes until is availability is not sure.

5.4 Average Latency:

Average Latency obtained for different mobility models for different routing scheme are depicted in Figures 15 to 18. It is clear that as the number of nodes increases, the Average Latency also decreases. The Average Latency is Minimum in case of Shortest Path Based Movement Model and Maximum for Random Direction Movement Modal.

5.5 Overhead Ratio:

Overhead Ratio obtained for different mobility models for different routing scheme are depicted in Figures 19 to 21. It is clear that as the number of nodes increases, the Overhead Ratio also increases. The overhead Ratio for Direct Delivery Routing Scheme for Each mobility modal is zero. The Overhead Ratio is Maximum in case of Shortest Path Based Movement Model and Minimum for Random Direction Movement Modal.

VI. CONCLUSION

In the present work, the performance of four routing protocols in DTN namely Epidemic, Direct Delivery, Spray & Wait and Prophet has been evaluated. Different movement models was used for the simulations. From the simulation results, we found that: the Shortest Path Based Movement is better than the other movement modals because it has maximum Throughput, maximum Packet delivered, maximum Overhead Ratio, Minimum Average Latency and Minimum Average BufferTime. It useslowpower,low bandwidth and minimum bufferateachnode

References

K. Fall, “A Delay-tolerant network architecture for challenged internets,” in Proceedings of ACM SIGCOMM, 2003, pp. 27–34.
NelsonI.Dopico,Álvaro GutiérrezandSantiagoZazo. Performanceanalysisofadelay tolerantapplicationforherd localization. 2011Elsevier B.V.Allrights reserved.
SeunghunCha,ElmurodTalipov andHojung Cha. Data delivery schemeforintermittently connectedmobilesensor networks. 0140-3664/$,2012Elsevier.
L.Pelusi,A.Passarella,M.Conti.Opportunisticnetworking: Data forwarding in disconnected mobile ad hoc networks. IEEECommunicationsMagazine,vol.44,pp.134–141,Nov 2006.
C.-M.Huang,K.-C.Lan,C.-Z.Tsai. Asurvey of opportunistic networks. Proc.ofthe22ndIntl.Conferenceklon AdvancedInformationNetworking andApplications (WAINA), Biopolis,Mar.25-28,Okinawa,Japan,2008.
Vahdat, A. & Becker, D. (2000). Epidemic routing for partially-connected ad hoc networks, Technical report, Department of Computer Science, Duke University. Wang, Y., Jain,S., Martonosi, M. & Fall, K. (2005). Erasure-coding based routing for opportunistic networks, WDTN ’05: Proceedings of the 2005 ACM SIGCOMM workshop on Delay tolerant networking, ACM, New York, NY, USA, pp. 229–236.
Davis,J., Fagg,A. &Levine,B.(2001). Wearable computers aspackettransportmechanisms in highly-partitioned ad-hoc networks. Wearable Computers, 2001. Proceedings. FifthInternationalSymposiumon, pp.141 –148.
Harras,K.A., Almeroth,K.C.&Belding-royer,E.M. (2005). Delaytolerantmobile networks(dtmns):Controlled floodingschemesinsparse mobile networks. InIFIP Networking.
A. Lindgren,A.Doria,andO.Schelen. Probabilisticrouting inintermittently connectednetworks. ACMSIGMOBILE, MobileComputingandCommunicationsReview,vol.7,no.3, pp.19–20,2003.
T.Spyropoulos,K.Psounis,C.S.Raghavendra.Spray and wait:Anefficientroutingschemeforintermittently connected mobile networks. Proc.ofACMSIGCOMMWorkshopon Delay-TolerantNetworking(WDTN ’05),pp. 252–259, 2005.
Kapadia, S., Krishnamachari, B. & Ghandeharizadeh, S. (2009) Static replication strategies for content availability in vehicular ad-hoc networks, Mob. Netw. Appl. 14(5): 590– 610.
https:\\www.netlab.tkk.fi/tutkimus/dtn/theone
A.Keranen. OpportunisticNetwork Environment Simulator. SpecialAssignment Report,HelsinkiUniversity of Technology,Dept.OfCommunicationsandNetworking,May 2008.