© 2014 IJEDR | Volume 2, Issue 4 | ISSN: 2321-9939
Reliable Routing Protocol in Delay Tolerant
Networks
1
Vrunda Gamit, 2Prof. Purvi Ramanuj
1
PG Student, 2Head of the Department
Information and Technology Department, Shantilal Shah Engineering Collage, Bhavanagar, Gujarat.
________________________________________________________________________________________________________
Abstract - Delay Tolerant Networks (DTNs) are supports data transfer in challenging environments where a fully
connected end to end path may never exist between a source and destination. These networks deal with large transmission
delays, frequently disconnected paths, high link & path error and limited resources .examples of this kind of networks are
satellite communication, ad-hoc & sensor, vehicular networks. DTN routing protocols utilize the mobility of the nodes and
buffering of messages, this makes is possible for a node to carry a message and in that way bridge partition in the
network. It is also known as store-carry-forward. In this paper, we proposed reliable routing protocol in DTNs based on
network coding-Multi Generation Mixing policy, that increase the reliability, while increasing data transmission delay as
compared to the protocols with the best performance. Simulation of a network coding-based information delivery method
in wireless networks which improves the network performance and reliability. Network coding is a paradigm to efficiently
broadcast the data in wireless networks in which data flows coming from multiple sources are combined to reduce delay,
and enhance robustness against node failures. Simulation results show that the proposed routing protocol Multi
Generation Mixing Epidemic Routing Protocol (Epidemic_MGM) increase the Delivery Probability compare to the
Traditional epidemic routing protocol.
Keywords - Delay Tolerant Network, Routing Protocols, Network Coding, Network Simulator (NS2)
________________________________________________________________________________________________________
I. INTRODUCTION
DTNs is a class of networks where no assumption about the existence of a distinct the full path between source and
destination. In Mobile Ad-hoc Networks (MANET) routing protocols, network is fully connected and there always exists a path
between every node in the network, so traditional routing protocols for MANETS do not work well for DTNs. Network
environment where the nodes are characterized by opportunistic connectivity are referred to as Delay Tolerant Networks.
DTNs applications examples are: Inter-planet Satellite communication networks, Sparse mobile ad hoc networks, CountrySide area networks, Military battle field networks, Wireless Sensor networks, Exotic Media networks [1].In Delay Tolerant
Networks (DTNs) with frequent network partitioning, routing packets is a challenge, because the successful establishment of an
end-to-end path between source and destination nodes is not guaranteed.
Network coding-based routing is an adaptation of the traditional store and forward mechanism. In network coding relay nodes
combine and encode received packets before forwarding them. Network Coding technique can be used in wired as well as in
wireless networks to improve the performance of network. Network Coding can be used for performance improvement in terms of
achievable throughput, resource consumption, complexity, robustness and security and load balancing for uni-cast, multicast and
broadcast flow of traffic [4]. Network coding with multi-generation mixing has been introduced to minimize network coding
losses by allow the cooperative encoding and decoding among generations in a way that improves network coding [5].
II. DELAY TOLERANT NETWORKS
The most important routing objective in DTNs is to maximize the probability of message deliver. One of the major properties
of delay tolerant networks (DTNs) is that there does not always exist a complete path from a source to a destination. DTN routing
protocols appropriate the mobility of the nodes and buffering of messages. This also makes possible for a node to carry a message
and in that Way Bridge partitions in the network. It knows as store-carry-forward. When a message is created and stored in the
source node, if a contact becomes available to a next-hop node the message is sent over this contact. Messages are stored at the
new node until the destination node is found.
DTN routing protocols are categorized in single-copy schemes and multi-copy schemes. The difference between these
schemes is the number of copies of a message that may exist at the same time in the network. In Single-copy schemes, forwards a
single copy of each message through the network. This is a resource efficient method, but it does not work properly in long
delivery. While Multi-copy scheme forwards a copy of each message to the network is called replication. In Multi-copy scheme
several copies of the same message exists in the network, thus having a higher resource consumption compared to single-copy,
but it gives lower delivery delays because the probability of finding the destination node is low when only on copy exist. Direct
Delivery and First Contact routing protocols are single copy protocols. In this scheme a node holds a message until it encounters
the destination node. Epidemic routing, Spray & Wait routing and PRoPHET routing are multi-copy scheme protocols so they
require more buffer space. DTNs are vulnerable to many malicious actions and bring a number of new security challenges. The
use of specific routing mechanisms including flooding-based ones may even increase the risks associated with inserting false
information into the network. The research on DTN security is more challenging compared to mobile ad hoc networks due to its
security characteristics. These characteristics include long delivery delays, sporadic connectivity and opportunistic routing [1].
IJEDR1404039
International Journal of Engineering Development and Research (www.ijedr.org)
3627
© 2014 IJEDR | Volume 2, Issue 4 | ISSN: 2321-9939
2.1 DTN Characteristics
Intermittent Connection
Delivery latency and low data rate
Long queuing delay
Resource limitation.
2.2 DTN Architecture
The DTN architecture follows a method for interconnecting heterogeneous networks and this method use store-carry-forwards
paradigm to overcome communication disruptions. It also provides services like electronic mail, but with enhanced naming,
routing, and security capabilities. Nodes unable to support the full capabilities required by this architecture, may be supported by
application-layer proxies acting as DTN applications [4].
In store-carry-forwards paradigm, source node is forwarded a message to an intermediate node (fixed or mobile) thought to be
more close to the destination node. The intermediate node stores the message and carries it while a contact is not available. The
process is repeated, so the message will be relayed hop by hop until reaching its destination node [7]. Fig.1 describes the DTN
overlay network architecture as below.
Figure1: DTN Overlay Network Architecture
The bundle layer is called DTN nodes. It includes a hop-by-hop transfer of reliable delivery responsibility and optional end-toend acknowledgement. Bundle layer provides internetworking on heterogeneous networks operating on different transmission
media [8].
III. RELIABLE ROUTING PROTOCOL
3.1 Multi Generation Mixing Epidemic Routing Protocol (MGM Epidemic)
In this section, we introduce traditional epidemic routing protocol, network coding and multi generation mixing policy in
DTNs. The Network coding (NC) is confident intelligent mixing of the information carried by the different flows at intermediate
nodes of the network. Network-Coding extends the concept of encoding a message beyond source coding for compression and
channel coding for protection against errors and losses. NC is based on the idea that intermediate network nodes process packets
in addition to relaying them [2].
Epidemic Routing Protocol
In Epidemic Routing Protocol does not require previous knowledge about the network. [10].Each node retains two buffers.
First buffer is used for stored the messages. This is generated by the node itself. Second buffer is used for the message received
from the other node. Each message has a unique message ID related with it. Each node carrying a list of the message IDs of all
messages in its buffer and pending delivery is saved in form of summary vector. When two nodes are encounter, they comparing
their summary vectors. Two nodes exchange all messages which they do not have in common. After the message swapping
process, multiple copies of the message flow in the network. Every node have same messages in their buffers and all messages are
spread to the every node in to the network including the destination node [9].Epidemic routing is flooding-based in nature, as
nodes continuously copy and transmit messages to newly discovered contacts that do not already possess a copy of the message.
In the simplest case, epidemic routing is flooding; however, more sophisticated techniques can be used to limit the number of
message transfers. Epidemic routing has its roots in ensuring distributed databases remain synchronized, and many of these
techniques, such as rumor mongering, can be directly applied to routing. Epidemic routing protocol is multi-copy scheme
protocols so they require more buffer space [6].
Similar to the spread of infective diseases, each time a packet carrying node encounters a node that does not have a copy of
that packet, that carrier is said to infect this new node by passing on a packet copy. Newly infected nodes, one by one, behave
similarly. The destination receives the packet when it first meets the infected node. When the traffic load is very low, epidemic
routing is able to achieve minimum delivery delay at the expense of increased use of resources such as buffer space, bandwidth,
and transmission power [12].
Network Coding with Multi generation Mixing (MGM)
The basic principle of network coding consisting in limiting the number of message forwarding in resource restrictive
conditions. In replication based routing methods, successful transmission is achieved by delivering each of data packets separately
while in the network coding based scheme destination nodes can recover sent packets by receiving only a reasonable number of
coded packets. Network coding based schemes is more reliable approach for information delivery in DTN like networks. We next
IJEDR1404039
International Journal of Engineering Development and Research (www.ijedr.org)
3628
© 2014 IJEDR | Volume 2, Issue 4 | ISSN: 2321-9939
introduced basic network coding, in which intermediate nodes generate new mixes from received encoded fragments, increasing
the innovative encodings in the network [3].
Network Coding with Multi-generation mixing (MGM) is a Random Linear Network Coding (RLNC) approach which
improves the performance without increasing buffer size. In Network Coding with MGM goal is to enhance decodable rates in
situation where losses, prevent efficient propagation of sender packets. MGM allows the cooperative decoding among the
different generations of a mixing set which enhances decodablity [5].
1.
2.
Robustness to link failures -Besides robustness against random packet losses, network coding is useful for protection
from link failures. Live path protection, where a primary and a backup flow are transmitted for each connection, allows
very fast recovery from link failures, since rerouting is not required. By allowing sharing of network resources among
different flows, network coding can improve resource usage. For a single multicast session, there exists, for any set of
failure patterns from which recovery is possible with arbitrary rerouting, a static network coding solution that allows
recovery from any failure pattern in the set.
Complexity - In some cases, although optimal routing may be able to achieve similar performance to that of network
coding, the optimal routing solution is difficult to develop. For example, minimum-cost sub graph selection for multicast
routing involves Steiner trees, which is complex even in a centralized setting, while the consistent problem with network
coding is a linear optimization that admits low-complexity distributed solutions. In networks without intermediate
coding, destination nodes need to successfully receive a certain number of successive packets sent by the source node to
be able to attain information completely.
Figure 2 : Improving reliability with network coding
As shown in fig.2 [1], the use of network coding provides the receiver the ability to decode and exploit all sent information by
receiving a reasonable of free encoded packets. Hence, a lossy network could be more reliable by using network coding.
Benefits of network coding with multi generation mixing policy eventually led to adopt the idea for broadcast-based wireless
networks, where nodes are most often topic to resource limitations in terms of power, buffer and link capacity. In various wireless
networks such as sensor networks, mesh networks, vehicular networks and DTNs the links between end systems are
fundamentally intermittent due to dynamic network topology. To provide effective communication, intermediate mobile or
stationary nodes are responsible for acting as relays using the store-and -forward mechanism. If the buffer of a node is filled up
and new data arrives before the delivery of the stored messages to store new ones.
As shown in fig.3 [1], using network coding capability it is possible to mix and code newly arrived and old data in the buffer
and generate new encoding vectors as a function of all received data, without deleting any data in the buffer or dropping the new
ones.
Figure 3: Improving buffer performances with network coding
Implementation of network coding executes additional processing overhead due to encoding at the intermediate nodes of the
network and decoding at the destinations. More complex coding offers better performance at the cost of higher processing
overhead. As a result, in those environments where processing power is a unusual resource simple network coding algorithms like
XORing or linear methods could be used. Fig. 4 shows the each generation is encoded with previous generations mixing set
IJEDR1404039
International Journal of Engineering Development and Research (www.ijedr.org)
3629
© 2014 IJEDR | Volume 2, Issue 4 | ISSN: 2321-9939
Figure 4: Network Coding with MGM
In Multi Generation mixing set of size m generations can be coded together. A new set of generation packet is mixed with
previously conducted generations. Results show that MGM reduces overhead for a recovery of packets. In MGM, N packets are
grouped into generations where the size of each generation is k packets. Each generation is assigned an order number from 0 to
N/k. MGM generations are grouped into mixing sets where the size of mixing set is m generations. Every mixing set has an index
M. Generation i belongs to mixing set with index M=i/m. Each generation in mixing set has a position index. Position index (l) of
generation i in a mixing set of size m is i%m. In MGM packets of different generations are encoded together. When node sends a
packet have its place to generation i with position index l in mixing set, that node encode all packets that are related with the
generations of same mixing set and have the position indices less than or equal to l as shown in fig.4 [11]. Size of encoding vector
depends on the number of packets encoded composed at sender node. Number of packets that are encoded together depends on
the position index of the generation with which packet is related. Packet in generation with position index l have the size of
encoding vector is (l+1)k. So the sender will generate (l+1)k independent packets.
In Network Coding with MGM goal is to enhance decodable rates in situation where losses prevent efficient spread of sender
packets. MGM allows the supportive decoding among the different generations of a mixing set which enhances decodablity.
Compare to G-by-G Network coding with MGM additional encoded packets associated with generation protect more than one
generation. In the case of MGM if generation is unrecoverable due to the reception of insufficient encodings, it is still possible to
recover that generation mutually as a subgroup of mixing set generations. Packets received with generation of higher position
indices have information from generations of lower position indices and hence contribute in recovery of unrecovered generations
of lower position indices in the similar mixing set[12].
3.2 Proposed Algorithm
1) Sender Node
Step 1: Divide the message in to n generation of K packet in to each mixing set.
Step 2: Encode the generation using MGM Concept for each mixing set.
Step 3: Send Packets
2) Intermediate node
Step 1: Calculate the rank of received packets for each generation of particular mixing set.
Step 2: if the rank of received packets is sufficient than callforward else reencoding of received packets.
( rank >= generation_size*generation ID )
Step 3: Send the encoded packet with respective effective co-efficient vector.
3) Destination node
Step 1: Calculate the rank of received packets for each generation of particular mixing set.
Step 2: If rank is sufficient than decode it. Decode the packets using header information.
IV. SIMULATION AND RESULTS
We have simulated the Epidemic_MGM routing protocol in NS2( Network Simulator version 2). We run simulation for both
Epidemic MGM routing protocol and traditional Epidemic routing protocol.
4.1Performance Metrics
The following are the performance metrics used
Probability of Delivery: It is the fraction of generated messages that are correctly delivered to the final destination within a
given time period. It is defined as Number of packets delivered /Number of packets created
IJEDR1404039
International Journal of Engineering Development and Research (www.ijedr.org)
3630
© 2014 IJEDR | Volume 2, Issue 4 | ISSN: 2321-9939
Figure 5: A Comparison Chart of Packet Delivery Probability Vs Simulation Time
Fig.5 shows the comparison chart of packet delivery probability for Epidemic routing protocol and MGM Epidemic routing
protocol. From the chart it can be noticed that the probability of message delivery of MGM Epidemic routing protocol is higher
than traditional Epidemic routing protocol because Multi Generation Mixing strategy is use to minimize network coding losses by
allow the cooperative encoding and decoding among generations in a way that improves network coding. Network coding
provides the receiver the ability to decode and exploit all sent information by receiving a reasonable of free encoded packets.
Hence, a lossy network could be more reliable by using network coding.
A
verage Latency: It is the measure of average time between message is generated and when it is received by the destination.
Figure 6: A Comparison Chart of Average Latency Vs Simulation Time.
V. CONCLUSION
Delay Tolerant Networks has frequent network partitioning, routing packets is a challenge, because the successful
establishment of an end-to-end path between source and destination nodes is not guaranteed. DTNs are vulnerable to many
malicious actions and bring a number of new security challenges. Epidemic_MGM routing protocol allows the cooperative
decoding among the different generations of a mixing set which enhances decodablity , increase the packet delivery and reduce
average latency compared to traditional epidemic routing protocol.
REFERENCES
[1] Karimzadeh Mortera: Efficient Routing Protocol in Delay Tolerant Networks(DTNs), Department of communication
Engineering, May 2011.
[2] Network Coding Meets Multimedia-A Review,Enrico Magli,Mea Wang, pascal Frossard,Athina Markopoulou.
arxiv.org_pdf_1211.4206.pdf, 18 NoV 2012.
IJEDR1404039
International Journal of Engineering Development and Research (www.ijedr.org)
3631
© 2014 IJEDR | Volume 2, Issue 4 | ISSN: 2321-9939
[3] Network Coded Routing in Delay Tolerant Networks.An Experience Report Agoston Petz, Chien-Liang Fok, and Christine
Julien University of Texas-Austin{agoston,liangfok,c.julien}@utexas.edu Brenton Walker and Calvin Ardi Laboratory for
Telecommunications Sciences College Park, MD, USA {brenton, calvin}@ltsnet.net.ExtremeCom-2011Manaus,Brazil
http://pharos.ece.utexas.edu/wiki/images/2/2e/Petz-xtremeCom12.pdf,
[4] Comparative Study and Analysis of Multimedia Traffic Over Ad Hoc Network,Jayesh N. Modi, Department Of Computer
Science.International Journal of Research in Engineering & Technology(IJRET) Vol. 1,Issue 2,July 2013.--13732866504.%20Eng-Comparative-Jayesh%20Modi%20(2).pdf.
[5] Network Coding Based Multicast for VANET International Journal of Advanced Research In Engineering and
Technology(IJARET),Volume 5,Issue 4,April 2014,
[6] http://en.wikipedia.org/wiki/Routing_in_delay-tolerant_networking
[7] Improving Vehicular Delay-Tolerant Network Performance with Relay Nodes. Vasco N. G. J. Soares1,2,3, Farid
Farahmand4, and Joel J. P. C. Rodrigues1,2 1Instituto de Telecomunicações, NetGNA Group,Covilhã, Portugal 2Department
of Informatics, University of Beira Interior, Covilhã, Portugal 3Superior School of Technology, Polytechnic Institute of
Castelo Branco, Castelo Branco, Portugal 4Department of Engineering Science, SonomaStateUniversity,CA,USA
vasco.g.soares@ieee.org;arid.farahmand@sonoma.edu;joeljr@ieee.org.
[8] Cerf, V., Burleigh, S., Hooke, A., Torgerson, L., Durst, R.,Scott, K, Fall, K., Weiss,
H.RFC 4838, Delay-Tolerant
Networking Architecture. IRTF DTN Research Group (2007)
[9] A.Vahdatand, D. Becker“Epidemic Routing for Partially Connected Ad Hoc Networks ”, DukeTechnical Report, CS-200006,July 2000. available at issg.cs.duke.edu/epidemic/epidemic.pdf.
[10] Chintan B. Desai et al./ International Journal of Computer Science & Engineering Technology (IJCSET),ISSN : 2229-3345
Vol. 4 No. 03 Mar 2013.available at IJCSE13-04-03-058.pdf.
[11] H. R. Mohammed Halloush, “Network Coding With Multi Generation Mixing: A Generalized Framework for Practical
Network Coding,”Tech. Report,IEEE Transactions on Wireless Communications, Volume10,No. 2,February 2011.
[12] Performance Comparison of RAPID, Epidemic and Prophet Routing Protocols for Delay Tolerant Networks Harminder
Singh Bindra and A. L. Sangal, International Journal of Computer Theory and Engineering Vol. 4, No. 2, April 2012
http://ijcte.org/papers/473-G1323.pdf
[13] Network Coding with MGM based Anycast Packet Transmission in Vehicular Ad-Hoc Networks 1Ankit Patel, 2Zunnun
Narmawala 1,2Nirma University, Ahmedabad, India, IJCST Vol. 4, Issue 2, April - June 2013.
http://www.ijcst.com/vol42/3/ankit.pdf
IJEDR1404039
International Journal of Engineering Development and Research (www.ijedr.org)
3632