©2010 International Journal of Computer Applications (0975 - 8887) Volume 1 – No. 17

Routing Approaches in Delay Tolerant Networks: A Survey
R. J. D'Souza
National Institute of Technology Karnataka, Surathkal, India

Johny Jose
National Institute of Technology Karnataka, Surathkal, India

ABSTRACT
Delay Tolerant Networks (DTNs) have evolved from Mobile Ad Hoc Networks (MANET). It is a network, where contemporaneous connectivity among all nodes doesn’t exist. This leads to the problem of how to route a packet from one node to another, in such a network. This problem becomes more complex, when the node mobility also is considered. The researchers have attempted to address this issue for over a decade. They have found that communication is possible in such a challenged network. The design of routing protocol for such networks is an important issue. This work surveys the literature and classifies the various routing approaches. discontinuity in the network. There are also methods that have employed additional mobile nodes, to provide better message delivery. Researchers are even exploring how the social interaction of humans can be utilized for routing in a DTN. This survey has made an extensive study of the various routing strategies taken by the researchers in the past few years. We have classified them based on the type of knowledge used for routing.

2. FLOODING BASED APPROACHES
Knowledge about the network helps in deciding the best next hop. It can happen that the network has absolutely no knowledge about the network. In such a scenario, all nodes are made relay nodes. Such schemes are called epidemic routing schemes. The basic concept of epidemic routing is to flood the packets, like the virus spreading in an epidemic. That is, a node copies its message to all the nodes that come in contact with it, provided the recipient node does not have a copy of it already. Vahdat and Becker [62] is perhaps the earliest proponent of such a scheme. Probably they were inspired by the algorithm proposed by Demers et al [14]. To identify if the node has already seen a message, each node maintains a summary vector. This is an index of the messages that it has already seen. When two nodes meet, this summary vector is exchanged. This enables the nodes to identify the new messages and request for them. In order to control the resource utilization, the authors propose the use of a hop counter and limit the hop of each message. Undoubtedly, flooding the network with messages will consume network resources like bandwidth, buffer, node energy etc. As demonstrated by Tseng et al [61], this can seriously degrade the performance, if the resources are scarce. Hence there is a need to control the flooding.

Categories and Subject Descriptors
C.2.2 [Computer Communication Networks]: Network Protocols – Routing Protocols.

General Terms
Algorithms, Design, Performance

Keywords
Delay Tolerant Network, Opportunistic Network, Routing

1. INTRODUCTION
The past decade has seen significant research in the field of communication in a DTN. Conventional routing protocols do not work in a DTN because they assume end-to-end connectivity. DTNs are characterized by the absence of it. Hence the timer and acknowledgement mechanisms of the TCP/IP protocol will fail here. This problem is further aggravated by the mobility of the nodes. The node mobility introduces the problem of lack of knowledge about the current position of the node, if its mobility pattern is unknown. Several approaches have been adopted to achieve reliable communication in such challenged networks. The researchers have focused on various issues like reducing the delivery delay or increasing the delivery ratio. Optimizing resource usage, providing scalability etc are also issues explored by various algorithms. Each of them has its own merits and demerits and is suitable in certain domains. Coming to the domain of routing protocol itself, several approaches have been adopted. Flooding the message in the network seems to be the most trivial approach. Attempts to offset the limitations of flooding based approaches have introduced a host of other schemes. Some of them use knowledge of the history of contacts made by the nodes, to route the messages. Some other algorithms forward messages to another node which has a better probability to make the message reach nearer to the destination. Mobility was seen as a hurdle to routing, but some researchers have used mobility to bridge the

2.1

Measures to Control Flooding

Several methods have been proposed to control the flooding. Most of the routing strategies were designed with the aim to avoid flooding. Even when flooding is adopted, care has been taken to conserve the resources. Some approaches also take care to free the buffer, after the message has been delivered.

2.1.1

Bounding the Number of Copies

In a flooding based approach, resources can be conserved by limiting the number of copies in the network. Spyropoulos et al [54] proposed several single copy schemes. The simplest of them was the case where the source directly delivers the message to the destination. The authors also proposed other single copy schemes such as randomized routing algorithm, utility based routing and as seek and focus routing algorithm.

8

©2010 International Journal of Computer Applications (0975 - 8887) Volume 1 – No. 17 In the randomized routing protocol, the message is handed over to another node, which has a better delivery probability. This is based on the principle that handing over the message to another node is better than holding it. The utility-based routing protocol takes into account the relative positions of the different nodes. But this scheme has a slow start, as the location information has to be built up. The seek and focus algorithm is a combination of randomized routing protocol and utility-based routing protocol. It initially performs a randomized routing and later switches to utility-based routing. Grossglauser et al [21] suggested another single-copy scheme. The source copies the message to the first node it meets. If this is not the destination, then this node will do a direct delivery. The authors assume that all the nodes move around randomly and meet every other node. Also each node is assumed to have infinite buffer. Thus it is a single copy, twohop scheme. The single-copy schemes cannot be categorized as epidemic scheme. However, it can be seen as an extreme case of controlling the number of copies in the network, into one. Groenevelt et al [20] proposed a controlled flooding scheme, which is an improvement of the single-copy scheme. The source makes n copies in the first phase. Each of these copies will try for a direct delivery. Thus this algorithm can be viewed as a multicopy, two-hop scheme. The Spray and Wait algorithm proposed by Spyropoulos et al [55] is another modification of the same scheme, to bound the number of copies in the network. Here, the authors show that this scheme is optimal when inter-node contact probabilities are independent and identically distributed (iid). However, tuning the parameters becomes a challenge here. Though these schemes [20, 55] improve the delivery ratio, the buffer utilization is more. In order to improve buffer utilization, Hanbali et al [26] suggested to limit the life time of each message copy. Harras et al [27] suggested three parameters to control the message flooding: viz. willingness probability, time-to-live, and kill time. Balasubramanian et al [1] proposed the RAPID algorithm. This algorithm can optimise a specific metric, for example, the average delay. They considered routing as a resource allocation problem. Before replicating packets, the algorithm checks if the replication justifies the resource utilization. It also maintains the number of replicas available in the network as well as their location. PRioritized EPidemic routing (PREP) described by Ramanathan et al [48] is another algorithm that keeps track of the priority of a packet and disseminates it in an epidemic manner. Priority of a packet depends on its cost, expiry time etc. erasure coded and then routed using estimation based routing. The same authors further improved this approach in [41] by utilising the knowledge of the mobility pattern of the network to route the erasure coded blocks. Chen et al [11] also applied erasure coding, but combined it with some replication techniques.

3

HISTORY BASED APPROACHES

A history based routing approach utilizes the history of encounters between nodes, to make a more informed routing decision. This idea was probably inspired by Davis et al [13], who studied the buffer management schemes. Their study revealed that dropping the ‘least encountered’ message is the best policy for buffer management. Intuitively, a node that has encountered the destination many times, is likely to encounter the destination again. This is the principle behind history based routing protocols. The Zebranet project [36] is one of the earliest attempts to use history of encounters for routing decisions. This was a project to monitor zebra movement in their habitat. Zebras were fitted with tracking collars. They are the mobile nodes. Periodically the researcher (base station) moves into the zebra area and collects data. Each mobile node has a hierarchy level. This hierarchy level is a function of the frequency of its contact with the base station. The hierarchy level can increase or decrease with time, depending on its frequency of contact with the base station. A node hands over its data only to another node that is higher in the hierarchy. In this way, the history of the node’s encounter with the base station becomes the metric for data forwarding. Lindgren et al [43] proposed a PRObabilistic Protocol using History of Encounters and Transitivity (PROPHET), a probabilistic routing protocol. This used the history of encounters, to compute the delivery predictability of the nodes. Each node maintains the delivery predictability of every other node for all known destinations. When nodes meet each other, this information is exchanged. In addition, it also incorporates transitivity information to decide the next hop. The authors claim that PROPHET has a higher delivery ratio than epidemic, with much lower communication overhead. The Fresher Encounter SearcH (FRESH) algorithm of DuboisFerriere [15] replaced the network-wide search for the destination by several smaller searches. When a node wants to send a message to a destination, it does not search for the destination. In stead, it searches for a node that has seen the destination more than itself. This procedure is repeated, till the destination is reached. Here again, the history of encounter is used for routing. Tan et al [59] adapted link state routing for DTN scenario. The link forwarding probability is calculated from the history of encounters. Based on this, the shortest expected path is found. This protocol is named Shortest Expected Path Routing (SEPR). The Meet and Visit routing (MV routing) proposed by Burns et al [7] is an improvement over the algorithms that use only the frequency of node contacts. It uses the frequency of the past contacts of nodes and also the visit to certain regions. Jain et al [31], in their work proposed several routing algorithms, based on knowledge oracles. They proposed the Minimum Expected Delay (MED) protocol, which is based on the future contact schedule. Jones et al [34, 35] improved this work by proposing Minimum Estimated Expected Delay (MEED), where the expected delay is computed using the

2.1.2

Embedding Additional Information

Another technique to conserve resources in a flooding approach was by embedding additional information into the message so that the number of copies can be limited. There are two such popular methods: network coding and erasure coding. In network coding, decoding algorithm is embedded into the coded message blocks. Erasure coding embeds redundancy into the message blocks. Widmer et al [64] proposed a network coding approach, which encoded the packets before flooding. Thus it is a flooding approach and hence it has all the limitations of flooding approach. Lin et al [42] utilised opportunistic routing to network coded packets. Wang et al [63] and Jain et al [32] introduced erasure coding. This approach bounded the number of copies in the network. Liao et al [40] proposed a method where the message is

9

©2010 International Journal of Computer Applications (0975 - 8887) Volume 1 – No. 17 observed contact history. Using a sliding window, each node records the connection and disconnection time of every contact. In this way, the most recent information is available for routing purpose, while MED has only offline information. The MaxProp of Burgess et al [6] is a protocol designed for vehicle-based DTNs. Such a DTN is characterised by large storage capacity and energy source, but short contact duration. Hence it discusses prioritisation of packets to be forwarded and dropped. These priorities are decided by the path likelihood, which depends on history of encounters. Thus it becomes a history-based controlled flooding. The NECTAR protocol of Etienne et al [47] used contact history to create a neighbourhood index. This index was used for routing. Yuan et al [67] is another proposal in this category. The Predict and Relay (PER) protocol proposed by them assumes that node movement is semi-deterministic. If sufficient history information is available, the node movement could be predicted. They also claim that it is possible to predict when the contact will occur and how long it will last, by using a time-homogeneous semi-Markov process model. The above protocols used history of previous contacts for controlling the flooding. Some other protocols use the context information to aid in routing. Context-aware Adaptive Routing (CAR) proposed by Musolesi et al [46] is one such protocol. MobySpace proposed by Leguay et al [38] utilised the mobility pattern of nodes as context information. A MobySpace consists of Mobypoints. Each Mobypoint summarizes some characteristics of a node’s mobility pattern. Nodes with similar mobility patterns are close in MobySpace. They are the optimum carriers of messages. Leguay et al [39] evaluated the same concept on multi-copy routing schemes to see how it can be used to control flooding. Opportunistic Routing with Window Aware Replication (ORWAR) proposed by Sandulescu et al [49] also exploited the knowledge of the context. The contexts are speed, direction of movement and radio range. This context information is used to decide the contact window size. It also prioritises the messages by using a differentiation mechanism and allocates more resources to messages with high utility. Messages with highest utility are replicated first and removed from the buffer last. This protocol is similar to Spyropoulos et al [55] where the source made a fixed number of replicas. In [55], these replicas were handed over to the first encountered nodes. But in [49] distribution was based on the evaluation of node’s available window. Grossglauser et al [22] proposed another algorithm that was based on context information. Here the context information was the time lag between the last encounter with the destination. further explored by Goodman et al [19]. Infostations could be seen as high bandwidth connectivity areas. The access options could be ‘drive-through, walk-through and sitthrough’. A drive-through Infostation deals with few simultaneous users, while a sit-through Infostation is similar to a LAN environment. The Shared Wireless Infostation Model (SWIM) architecture proposed by Small et al [52] is another work that deploys Infostations at various locations. Mobile nodes forward data to the Infostations. Each Infostation is considered as a destination and they are connected. So in effect, SWIM architecture is very similar to the epidemic scheme of Vahdat et al [62], except that in the SWIM architecture, each Infostation is a destination. The throwbox concept of Zhao et al [71] is another attempt to utilize stationary nodes for data delivery. Their work was directed towards algorithms for placement of throwboxes. The work of Farahmand et al [17] is an extension of this. They proposed an architecture with three types of nodes: terminal, relay and mobile nodes. Users who want to send/receive messages, access terminals using any available network protocol. Terminal nodes are stationary. These messages are carried to other places by mobile nodes. Mobile nodes are placed in vehicles and they can’t communicate among themselves. Relay nodes are used to enable transfer of messages from one mobile node to another. They have proposed two heuristic algorithms: one that minimises the number of hop counts between source and destination (MRH) and another that minimises the average message delivery time (MRD).

4.2

Using Mobile Devices

Chatzigiannakis et al [9] proposed SNAKE protocol, which used additional mobile nodes. Here a sequence of nodes, called supporters, moved in a coordinated way and cover the entire area. These supporters became a moving backbone to the DTN. The simulation showed that a small number of supporters can effect efficient communication. Chatzigiannakis et al [10] presented another protocol named RUNNERS, which was an improvement over [9]. Here, each additional node performs a random walk, covering the entire region. The RUNNER protocol has proved to be more efficient than SNAKE by way of message delay and memory requirements. Zebranet project [36] was another early attempt that employed a special mobile node to collect data from the mobile nodes. Shah et al [50] suggested a three-tier architecture called DataMULE (Mobile Ubiquitous LAN Extension). The MULEs are in the middle tier and move around the sensor area randomly, collecting data. They have large storage capacity and renewable energy source. They pass on the collected data to the base station. This project was aimed at collecting data from stationary sensor nodes in an energy efficient manner. The above three approaches [9, 10, 50] depended on the random movement of the special nodes. There are other schemes that introduced non-randomness into the mobility of the special nodes. This allowed the special nodes to be controlled so that the desired QoS can be achieved. Such special nodes are commonly referred to as ferry, in the literature. Several variations of the ferry-based approaches can be seen in the literature. It may be single ferry (SF) approach or multi-ferry (MF) approach. For both SF and MF approaches, the movement may be predetermined or dynamic. The

4 SPECIAL APPROACHES

DEVICES

BASED

Here we study the protocols that use additional devices to effect communication. These additional devices may be stationary or mobile.

4.1

Using Stationary Devices

In this approach, one or more stationary nodes are used to facilitate data transfer. Frenkiel et al [18] was the first to propose the concept of Infostation, a low cost stationary node, to aid in message transfer in disconnected networks. It was

10

©2010 International Journal of Computer Applications (0975 - 8887) Volume 1 – No. 17 predetermined ferry path may be different or same for each tour. The dynamic ferry movement may be ferry initiated (FIMF) or node initiated (NIMF). The MF approach may allocate zones for each ferry or all the ferries may be allowed to move around the entire region. It may consider all ferries as equal or may organize them hierarchically. Zhao et al [68] introduced MF approach and studied its application in networks with stationary nodes. Algorithms for controlling the ferry route are also discussed here. Kansal et al [37] proposed another single ferry approach that introduced controllable mobile components into the network. Somasundara et al [53] studied the scheduling in a single ferry scheme. Scheduling was important in their work, because their task was to collect data from sensor nodes with varying data growth rate. Tariq et al [60] studied the route design problem and proposed OPWP (OPtimized Way-Points). This algorithm learns the mobility model of the nodes and chooses a set of way-points. The ferry moves through these points and meets the nodes. The single ferry approach is simple, but doesn’t perform well at high traffic load and large network scenarios. Hence we think of a multi-ferry approach. Multiple ferries can definitely improve the message delivery ratio. It can also provide robustness against ferry failures. The design issues of multiple ferries revolve around introducing cooperation among the ferries for more efficient data delivery. Zhao et al [69] described a multi-ferry case, with no energy or storage constraint. The MF movement is proactive. They studied FIMF and NIMF cases. Simulation showed improved data delivery and energy consumption than epidemic schemes. Jea et al [33] introduced another multiferry scenario, where all ferries are equal. The authors are interested in the load balancing of the ferries, considering the fact the nodes need not be uniformly placed. Zhao et al [70] was concerned with the design of ferry routes, where the ferries interact among themselves. Simulation showed that throughput, delay and resource requirement at nodes and ferries are improved with the number of ferries. Harras et al [28] studied the intra-region message transfer schemes. The proposed scheme used a dedicated set of messengers. They have proposed several classes of messenger scheduling algorithms. Gu et al [23] gave an algorithm to schedule the message ferries so that no buffer overflow occurs. They schedule the ferries to collect data from sensors that have different data generation rate. This is similar to the work of Somasundara et al [53], but adapted to a multi-ferry scenario. Gu et al [24] designed a multi-ferry scheme which studies the use of ferries when some messages have an urgent nature. The proposal was a Differentiated Message Delivery (DMD), that distinguishes and services urgent and regular messages separately. They investigated the minimum required speed for the mobile node so that there is no data loss and the urgent messages are able to be delivered within the time limit. They also found out the loss rate of regular and urgent messages for a given mobile node speed. Shin et al [51] controlled the movement of message ferries to follow a Levy Walk pattern. Levy walk has an optimality property. And they showed through simulation that this approach is very effective in situations where the knowledge about the network such as contact history, trajectory or locations of destination, is limited. Another hot research topic is exploiting the social context of the users for data forwarding. Su et al [58] describes an experiment in a campus environment to test the feasibility of using mobility and opportunistic pair-wise contact, to form an ad hoc network. They did not use any predetermined mobility model. They concluded that the user mobility can be used to form a network. The Haggle project [25] introduced in 2006 connects humans with mobile devices, in a DTN fashion. Humans carry mobile devices with them. These devices have processing and storage capacity which can be utilized for data transmission in a DTN environment. Spyropoulos et al [56] cites various authors and establish that the assumptions made in traditional mobility models do not hold in real-life situations. They propose a heterogeneous community based mobility model, that captures real-life mobility features. They claim that their model is highly tunable and analytically tractable. Miklas et al [44] builds on this concept and establishes that separating people into two groups of friends and strangers, results in a more efficient routing protocol. It also provides more effective security management and higher query hit rate in mobile applications. The authors also showed that human encounter has diurnal and weekly cycles. Simulations proved that social information provides substantial performance improvement. In a similar work done by Yoneki et al [65], four categories of nodes are proposed: familiar, familiar stranger, stranger and friend. This is an improvement over [44]. Srinivasan et al [57] studied and characterized mobility patterns in a campus of 22341 students. The daily class schedule was used to infer their contact pattern. They demonstrated that contact patterns can be exploited to design efficient aggregation algorithms. Using the contact data, they also designed aggregation algorithms, in which with a small number of nodes, a large fraction of the data was aggregated. Chaintreau et al [8] also studied how human mobility can be utilized in opportunistic forwarding. They modelled the distribution of contact times and inter contact times between nodes, using the observed real traces and found that it follows power-law distributions with heavy tail. They also found that models like Random Waypoint and Random Walk do not model heavy tails and so are not the best choices to study realistic opportunistic networks. Musolesi et al [45] builds on this and proposes community based mobility models (CMM). They showed that CMM has the heavy tail characteristics for contact and inter-contact times. They also showed that MANET protocols work better when CMM model is used. Ekman et al [16] presented another mobility model that closely follows the everyday life of an average person. Boldrini et al [2] continued on the work of Chaintreau et al [8] and Musolesi et al [45] to understand how the mobility pattern of users affect the performance of routing protocols. They based their study on group mobility models. They studied how different human mobility patterns impact on the routing performance in opportunistic network. In this work, they concluded that context (social information) based routing schemes reduce congestion and provide acceptable QoS with much lower overhead. Boldrini et al [3] used the history of the social relationships among users as the context. Each node maintains its own identity table (IT) and that of its neighbours. The proposed algorithm is named HiBOp and is able to automatically learn the connectivity opportunities determined by the users’ movement patterns and exploit them efficiently.

4.3

Using Social Context 11

©2010 International Journal of Computer Applications (0975 - 8887) Volume 1 – No. 17 The work of Daly et al [12] introduced a new metric called betweenness, to forward data. Betweenness is one of the ways to measure the centrality of a node. Centrality of node is an expression of its relative importance in the network. In a social network, it indicates how important the person is. It is also a measure of the extent to which a person (node) has control over the information flowing between two other nodes. Routing decisions can be based on betweenness. In this case, all decisions are made solely on local calculations. Hui et al [29] proposed the bubble algorithm, which is also based on the two aspects of a society, viz. community and centrality. The bubble algorithm identifies the popular nodes in the source community and the destination community. They play an important role in message transfer. Boldrini et al [4] also proposed a data dissemination system, which is based on the social relationship between users. The work of Yoneki et al [66] on this theme introduced the idea of correlated interaction. They identify social communities and hubs within communities. An overlay network is then built between these hubs. Their work also included three community detection algorithms. Boldrini et al [5] is another work which exploited the social relationship to transmit messages. Here they propose the ContentPlace framework. When a node makes contact with another, it advertises the data objects it is interested in and also exchanges summaries of the data objects it carries. Utility value is attached to each data object. This enables the nodes to decide where to place a data object, so that its availability can be optimised. Continuing in this line, the authors of Ioannidis et al [30] studied how the social network can assist in distribution of dynamic content. fall into more than one category. We attempted to classify the various schemes based on the type of knowledge used by the routing protocol. We have also tried to follow the evolution of the various protocols, from one approach to another. A pure epidemic routing protocol does not require any knowledge about the network. However, in order to conserve resources, the flooding had to be controlled. For this, knowledge of factors like history of encounter, mobility pattern etc are be used. Though in its early stages, a considerable amount of work has been carried out in this direction. They give valuable insight into enabling communication in a DTN.

7
[1]

REFERENCES
A. Balasubramanian, B. N. Levine, and A. Venkataramani, “Dtn routing as a resource allocation problem,” ACM SIGCOMM, 2007. C. Boldrini, M. Conti, M. and A. Passarella, “Impact of social mobility on routing protocols for opportunistic networks,” Proceedings of the First IEEE WoWMoM Workshop on Autonomic and Opportunistic Networking (AOC), 2007. C. Boldrini, M. Conti, I. Iacopini, and A. Passarella. “HiBOp: a History Based Routing Protocol for Opportunistic Networks,” Proceedings of IEEE WoWMoM, 2007. C. Boldrini, M. Conti, and A. Passarella, “Modelling data dissemination in opportunistic networks,” Proceedings of ACM Workshop on Challenged Networks (CHANTS), 2008. C. Boldrini, M. Conti and A. Passarella, “ContentPlace: Social-aware Data Dissemination in Opportunistic Networks,” MSWiM’08, October 27–31, 2008. J. Burgess, B. Gallagher, D. Jensen, and B. Levine, “Maxprop: Routing for vehicle-based disruptiontolerant networks,” Proceedings of INFOCOM, 2006. B. Burns, O. Brock and B. N. Levine, “MV routing and capacity building in disruption tolerant networks,” Proceedings of IEEE INFOCOM, 2005. A. Chaintreau, P. Hui, J. Crowcroft, C. Diot, R. Gass, and J. Scott, “Impact of Human Mobility on Opportunistic Forwarding Algorithms,” IEEE Transactions on Mobile Computing (INFOCOM 2006), 2007, pp. 606–620. I. Chatzigiannakis, S. Nikoletseas and P. Spirakis, “Analysis and Experimental Evaluation of An Innovative and Efficient Routing Protocol for Ad- Hoc Mobile Networks,” Lecture Notes in Computer Science, vol. 1982, 2001, pp. 99–111.

[2]

[3]

[4]

5

OPEN RESEARCH ISSUES

[5]

Research on routing in DTN is still in its infancy. Much progress has been achieved by the research community in bridging the gap of disconnection and enabling communication in DTNs. However, there are several areas in DTN routing that requires research attention. In DTN routing, there are several parameters of interest. Some of them are: delivery ratio, delivery latency, resource usage (particularly bandwidth and buffer), information gathering and usage, hop count, number of copies of message in the network, loop freedom, maintenance of routing vector/table, scalability, multi-path support etc. Optimization of these parameters is to be investigated. Some of these parameters may be in conflict with some others and hence a trade off may be required. It is to be noted that very little work has been done in the field of security of data transmission in DTN. A DTN faces all the security threats that a conventional network faces and more. Hence the security in DTN is an important issue. Utilizing the social structure of humans is a very promising research area. Practically everyone carries some handheld devices. Knowledge of the social structure can enable these devices to be the bridge between the disconnectedness.

[6]

[7]

[8]

[9]

[10] I. Chatzigiannakis, S. Nikoletseas, N. Paspallis, P. Spirakis and C. Zaroliagis, “An Experimental Study of Basic Communication Protocols in Ad-Hoc Mobile Networks,” Proceedings of the 5th Workshop on Algorithmic Engineering, 2001. [11] L.-J. Chen, C.-H. Yu, T. Sun, Y.-C. Chen and H.-H. Chu, “A hybrid routing approach for opportunistic networks,” ACM SIGCOMM Workshop on Challenged Networks, 2006. [12] E. Daly and M. Haahr, “Social network analysis for routing in disconnected delay-tolerant MANETs,” Proceedings of MobiHoc, 2007.

6

CONCLUSION

We have made an in depth study of the various routing protocols, proposed for DTN and classified them. It is not possible to classify each of the schemes into exactly one of the many classes. Most approaches are hybrid in nature and may

12

©2010 International Journal of Computer Applications (0975 - 8887) Volume 1 – No. 17 [13] J. Davis, A. Fagg, and B. Levine, “Wearable computers as packet transport mechanisms in highly partitioned ad hoc networks,” Proceedings of 5 IEEE International Symposium on Wearable Computers, Zurich, Switzerland, 2001. [14] A. A. Demers, D. Greene, C. Hauser, W. Irish, J. Larson, S. Shenker, H. Sturgis, D. Swinehart, and D. Terry, “Epidemic algorithms for replicated database maintenance,” Proceedings of the Sixth Symposium on Principles of Distributed Computing, 1987, pp. 1– 12. [15] H. Dubois-Ferriere, M. Grossglauser and M. Vetterli, “Age matters: Efficient route discovery in mobile ad hoc networks using encounter ages,” Proceedings of ACM OBIHOC, 2003. [16] F. Ekman, A. Keränen, J. Karvo and J. Ott, “Working Day Movement Model,” MobilityModels’08, May 26, 2008. [17] F. Farahmand, I. Cerutti, A. N. Patel, Q. Zhang and J. P. Jue, “Relay node placement in vehicular delaytolerant networks,” IEEE Global Telecommunications Conference - GLOBECOM 2008, vol. 27, no. 1, November 2008, pp. 2514-2518. [18] R. H. Frenkiel and T. Innielinski, “Infostations: The joy of ‘manytime, many-where’ communications,” Journal on Mobile Computing, May, 1996. [19] D. Goodman, J. Borras, N. Mandayam and R. Yates, “INFOSTATIONS: A new system model for data and messaging services,” IEEE VTC’97, volume 2, May 1997, pp. 969–973. [20] R. Groenevelt, P. Nain, and G. Koole, “The message delay in mobile ad hoc networks Performance Evaluation,” 62(1-4):210–228, Oct. 2005. [21] M. Grossglauser, and D. N. Tse, “Mobility Increases the Capacity of Ad Hoc Wireless Networks,” IEEE/ACM Transactions on Networking, Vol. 10, No. 4, August 2002, pp. 477-486. [22] M. Grossglauser and M. Vetterli, ‘Locating nodes with EASE: last encounter routing in ad hoc networks through mobility diffusion,” Proceedings of the 22nd IEEE Annual Joint Conference of the IEEE Computer and Communications Societies (IEEE INFOCOM), 2003. [23] Y. Gu, D. Bozdag, E. Ekici, F. Ozguner and C.-G. Lee, “Partitioning based mobile element scheduling in wireless sensor networks,” Proceedings of the 2nd Annual IEEE Conference on Sensor and Ad Hoc Communications and Networks, 2005. [24] Y. Gu, D. Bozda˘g and E. Ekici, “Mobile Element Based Differentiated Message Delivery in Wireless Sensor Networks,” Proceedings of the 2006 International Symposium on a World of Wireless, Mobile and Multimedia Networks (WoWMoM'06) 2006. [25] http://www.haggleproject.org/index.php/Main_Page [26] A. Al Hanbali, P. Nain, and E. Altman, “Performance of ad hoc networks with two-hop relay routing and limited packet lifetime,” Proc. of IEEE/ACM ValueTools, Pisa, Italy, Oct. 2006. [27] K. A. Harras, K. C. Almeroth, and E. M. BeldingRoyer, “Delay tolerant mobile networks (dtmns): Controlled flooding in sparse mobile networks,” IFIP Networking, 2005. [28] K. Harras and K. Almeroth, “Inter-regional messenger scheduling in delay tolerant mobile networks,” Proceedings of WoWMoM'06, June 2006. [29] P. Hui, J. Crowcroft, and E. Yoneki, “Bubble rap: social-based forwarding in delay tolerant networks,” Proceedings of MobiHoc, 2008, pp. 241–250. [30] S. Ioannidis, A. Chaintreau, and L. Massoulie, “Optimal and scalable distribution of content updates over a mobile social network,” Proceedings of INFOCOM, 2009. [31] S. Jain, K. Fall, and R. Patra, “Routing in a delay tolerant network,” Proceedings of ACM SIGCOMM, 2004. [32] S. Jain, M. Demmer, R. Patra and K. Fall, “Using Redundancy to Cope with Failures in a Delay Tolerant Network,” SIGCOMM’05, August 22–26, 2005. [33] D. Jea, A. Somasundara and M. Srivastava, “Multiple controlled mobile elements (data mules) for data collection in sensor networks,” DCOSS, 2005. [34] E. P. C. Jones, L. Li, and P. A. S.Ward, “Practical routing in delay-tolerant networks,” Proceedings of ACM SIGCOMM Workshop on Delay Tolerant Networking (WDTN), 2005. [35] E. P. C. Jones, L. Li, J. K. Schmidtke and P. A. S.Ward, “Practical Routing in Delay-Tolerant Networks,” IEEE Transactions on Mobile Computing, Vol. 6, No. 8, Aug. 2007. [36] P. Juang, H. Oki, Y.Wang, M. Martonosi, L. S. Peh, and D. Rubenstein, “Energy-efficient computing for wildlife tracking: Design tradeoffs and early experiences with Zebranet,” Proceedings of ACM ASPLOS, 2002. [37] A. Kansal, A. A. Somasundara, D. D. Jea, M. B. Srivastava and D. Estrin, “Intelligent fluid infrastructure for embedded networks,” ACM MobiSys 2004, 2004. [38] J. Leguay, T. Friedman and V. Conan, “Evaluating MobySpace Based Routing Strategies in Delay Tolerant Networks,” Universit´e Pierre et Marie Curie, Laboratoire LiP6–CNRS, Thales Communications. [39] J. Leguay, T. Friedman and V. Conan, “Evaluating Mobility Pattern Space Routing for DTNs,” Proceedings of the 25th IEEE International Conference on Computer Communications (INFOCOM), April 2006. [40] Y. Liao, K. Tan, Z. Zhang, and L. Gao, “Combining Erasure-coding and Relay Node Evaluation in Delay Tolerant Network Routing,” Microsoft Technical Report, MR-TR, 2006. [41] Y. Liao, K. Tan, Z. Zhang, and L. Gao, “Estimation based erasure coding routing in delay tolerant networks,” International Wireless Communications and Mobile Computing Conference, 2006. [42] Y. Lin, B. Liang, and B. Li, “Performance Modeling of Network Coding in Epidemic Routing,” MobiOpp’07, June 11, 2007. [43] A. Lindgren, A. Doria, and O. Schelen, “Probabilistic routing in intermittently connected networks,” ACM SIGMOBILE CCR, 7(3), 2003, pp. 19–20.

13

©2010 International Journal of Computer Applications (0975 - 8887) Volume 1 – No. 17 [44] A. G. Miklas, K. K. Gollu, K. K.W. Chan, Stefan Saroiu, K. P. Gummadi and E. Lara, “Exploiting Social Interactions in Mobile Systems,” UbiComp 2007, pp. 409–428. [45] M. Musolesi and C. Mascolo, “A Community Mobility Model for Ad Hoc Network Research,” Proceedings of ACM/SIGMOBILE REALMAN, 2006. [46] M. Musolesi and C. Mascolo, “CAR: Context-aware Adaptive Routing for Delay Tolerant Mobile Networks,” IEEE Transactions on Mobile Computing, Feb 2009. [47] E. C. R. de Oliveira and C´ elio V. N. de Albuquerque, “NECTAR: A DTN Routing Protocol Based on Neighbourhood Contact History,” SAC’09 March 2009. [48] R. Ramanathan, R. Hansen, P. Basu, R. Rosales-Hain and R. Krishnan, “Prioritized Epidemic Routing for Opportunistic Networks,” MobiOpp’07, June 11, 2007. [49] G. Sandulescu and S. Nadjm-Tehrani, “Opportunistic DTN Routing with Window-aware Adaptive Replication,” AINTEC’08, November 18–20, 2008. [50] R. C. Shah, S. Roy, S. Jain, and W. Brunette, “Data Mules: Modeling and Analysis of a Three-tier Architecture for Sparse Sensor Networks”, Elsevier Ad Hoc Networks Journal, 2003. [51] M. Shin, S. Hong and I. Rhee, “DTN Routing Strategies using Optimal Search Patterns,” CHANTS’08, September 15, 2008. [52] T. Small and Z.J. Haas, “The Shared Wireless Infostation Model – A New Ad Hoc Networking Paradigm (or Where there is a Whale, there is a Way),” MobiHoc ’03, June 2003 [53] A. A. Somasundara, A. Ramamoorthy and M. B. Srivastava, “Mobile element scheduling for efficient data collection in wireless sensor networks with dynamic deadlines,” Proceedings of the 25th IEEE International Real Time Systems Symposium 2004, 2004. [54] T. Spyropoulos, K. Psounis, and C. S. Raghavendra, “Single-copy Routing in Intermittently Connected Mobile Networks,” First Annual IEEE Communications Society Conference on Sensor and Ad Hoc Communications and Networks, 2004, pp. 235-244. [55] T. Spyropoulos, K. Psounis, and C. Raghavendra, “Spray and wait: an efficient routing scheme for intermittently connected mobile networks,” Proceedings of 2005 ACM SIGCOMM workshop on Delay-tolerant networking, 2005, pp 252–259. [56] T. Spyropoulos, K. Psounis and C. Raghavendra, “Performance analysis of mobility-assisted routing,” Proceedings of MobiHoc, 2006, pp. 49–60. [57] V. Srinivasan, M. Motani and W. T. Ooi, “Analysis and Implications of Student Contact Patterns Derived from Campus Schedules,” MobiCom’06, September 23–26, 2006. [58] J. Su, A. Chin, A. Popivanova, A. Goely and E. Lara, “User Mobility for Opportunistic Ad-Hoc Networking,” 6th IEEE Workshop on Mobile Computing Systems and Applications (WMCSA), Dec. 2004. [59] K. Tan, Q. Zhang and W. Zhu, “Shortest Path Routing in Partially Connected Ad Hoc Networks,” IEEE Globecom, 2003. [60] M. M. B. Tariq, M. Ammar and E. Zegura, “Message ferry route design for sparse ad hoc networks with mobile nodes,” ACM MobiHoc ‘06, May 22-25, 2006. [61] Y.-C. Tseng, S.-Y. Ni, Y.-S. Chen, and J.-P. Sheu, “The Broadcast Storm problem in a mobile ad hoc network,” Wireless Networks, vol. 8, no. 2/3, 2002. [62] A. Vahdat and D. Becker, “Epidemic routing for partially connected ad hoc networks,” Technical Report CS-200006, Duke University, 2000. [63] Y. Wang, S. Jain, M. Martonosi, and K. Fall, “Erasure coding based routing for opportunistic networks,” Proceedings of ACM SIGCOMM Workshop on Delay Tolerant Networking (WDTN), 2005. [64] J. Widmer and J.-Y. L. Boudec, “Network coding for efficient communication in extreme networks,” Proceedings of ACMSIGCOMM Workshop on Delay Tolerant Networking (WDTN), 2005. [65] E. Yoneki, P. Hui and J. Crowcroft, “Visualizing Community Detection in Opportunistic Networks,” CHANTS’07, September 14, 2007. [66] E. Yoneki, P. Hui, S. Chan, and J. Crowcroft, “A socio-aware overlay for publish/subscribe communication in delay tolerant networks,” Proceedings of MSWiM, 2007, pp. 225–234. [67] Q. Yuan, I. Cardei, and J. Wu, “Predict and Relay: An Efficient Routing in Disruption-Tolerant Networks,” MobiHoc ’09, May 2009. [68] W. Zhao and M. Ammar, “Proactive routing in highlypartitioned wireless ad hoc networks,” 9th IEEE International Workshop on Future Trends of Distributed Computing Systems, May, 2003. [69] W. Zhao, M. Ammar and E. Zegura, “A message ferrying approach for data delivery in sparse mobile ad hoc networks,” Proceedings of MobiHoc, 2004, pp 187-198. [70] W. Zhao, M. Ammar and E. Zegura, “Controlling the Mobility of Multiple Data Transport Ferries in a Delay-Tolerant Network,” INFOCOM, 2005. [71] W. Zhao, Y. Chen, M. Ammar, M. D. Corner, B. N. Levine, and E. Zegura, “Capacity enhancement using throwboxes in dtns,” IEEE MASS, October 2006.

14