Abstract

In this paper, we address the problem of routing in delay tolerant networks (DTN). In such networks there is no guarantee of finding a complete communication path connecting the source and destination at any time, especially when the destination is not in the same region as the source, which makes traditional routing protocols inefficient in that transmission of the messages between nodes. We propose to combine the routing protocol MaxProp and the model of “transfer by delegation” (custody transfer) to improve the routing in DTN networks and to exploit nodes as common carriers of messages between the network partitioned. To implement this approach and assess those improvements and changes we developed a DTN simulator. Simulation examples are illustrated in the article.

1. Introduction

Delay tolerant networks are wireless mobile ad hoc often where a communication path between a source node and destination node does not exist, either directly or through established routes by intermediate nodes. This situation occurs if the network is sparse and partitioned into several areas due to high mobility, low density nodes or when the network extends over long distances; In these cases, the traditional routing protocols have been developed for mobile ad hoc networks proved to be insufficient because they require the existence of a dense and connected in order to route the packets, To resolve this problem of routing in DTN networks, researchers have proposed the use of routing approaches based on the Principe Store-Carry-and-forward [1], such as:

The epidemic routing protocol [2]: Messages propagate through the network like an outbreak of disease. This approach ensures that the message reaches its destination as much as possible, but it also wastes a lot of resources by unnecessary transfers of messages.

The MaxProp routing protocol [3] uses several mechanisms to create a ranked list that determines which packets are transmitted first during a transfer opportunity. The primary factor that determines the ranked list is a delivery cost estimate assigned to each destination. The cost is based on the probability that the next transfer opportunity with a particular peer, estimated from observed history. These probabilities are added to form a path score; the minimum score of all possible paths via the current peer to a destination is chosen as the cost estimate.

The model of “transfer by delegation” (custody transfer) [1,4,5]: In this model by assigning responsibility for a message to a single node at any time. This model has the advantage of being economical in terms of resources, since a message is the responsibility of a node at any time during its delivery. However it now risk losing the message if the wearer goes down or destroyed.

Our approach is to combine the two approaches to routing, MaxProp [3] and the model of “transfer by delegation” (custody transfer) [1,4,5] to overcome the problems of routing in DTN networks.

To evaluate these improvements and changes we have developed a DTN simulator written in Java which is based on our approach.

2. Our Approach to Routing

Normally, one of the most fundamental requirements is to find a communication path between nodes in a sparse network and partitioned into several zones, in this case, communication between areas of the network depends only on the displacement of certain nodes between areas (Figure 1) As the delivery of messages depends on the mobility of nodes, it is very difficult to obtain global information and routing becomes an important issue.

With the aim to maximize the chances that a message reaches its destination and to minimize the resources consumed in the network such as bandwidth, capacity of storage devices and the energy of the different nodes in an environment characterized by disconnections that often occur because of the low density of nodes, node mobility and energy failure.

Our approach is to combine the routing protocol MaxProp [3] and the model of “transfer by delegation” (custody transfer) [1,4,5] to exploit the nodes as carriers of messages between the network partitioned .

The combination of these two approaches (MaxProp and The model of “transfer by delegation”) combines two kinds of routing technique based on the degree of the knowledge that the node has about its future contacts with other nodes in the network [6]:

• Technique of controlled routing.

• Technical routing predicted.

The key issues resolved by our approach:

• The choice of nodes that can act as carriers of messages (delegates) between the networks partitioned.

• Nodes incorporating elements of knowledge and contextual elements.

• Increases the chances that a message reaches its destination while minimizing the time from End to End.

• Economic from the point of view of the network resources consumed.

In this work we have developed a DTN simulator written in Java which is based on our approach to evaluate the different routing parameters.

3. Scenario of Our Approach

The probability are calculated locally in each area according to the approach of MaxProp [3] and the nodes move according to the two mobility models: Model Random Waypoint and model Restricted Random Waypoint [7-9] as shown in Figure 2.

N0 node wants to send a message to N1. This can not be done because there is no path between the two areas. The message is sent to N4 that has a better probability and a planned movement and stores it. As shown in Figure 3.

After a certain period of time, N4 moves to another area (as shown in Figure 4). The message reached its intended recipient using the routing protocol MaxProp.

 

4. Strategy for Transmission of Our Approach

 

4.1. When the Source and Destination are in Two Different Areas [1,3-5,10,11]

1) Nodes that can act as carriers are the nodes that have:

• A high probability.

• The planned movements between zones.

• A sufficient transmission energy.

2) In the case of a network where there are nodes that have random movements, the best carriers are the nodes that have:

• A high probability.

• A sufficient transmission energy.

3) In the case of a network where there are nodes that have random movements and nodes which have planned movements, the best carriers are the nodes that have:

• A planned and controlled movement between areas.

• A sufficient transmission energy.

4) When the nodes which have planned and controlled movements between zones are nodes that have better features in terms of energy and storage capacity as the case of buses, planes, trains...We may use them:

• On the one hand as the best carriers (delegates) of the message.

• Secondly as fixed relay “mobile” with a periodic occurrence in both areas, these relays can be exploited on the one hand to describe the movements and mobility of nodes [12] in each zone, based on the frequency of visits to these relays [10], secondly to increase the number of contacts between nodes.

 

4.2. The Principle of Communication in the Same Area [1,3-5,10,11]

• When a node encounters another node with the greatest probability, it sends the message to that node and still keep the message for transmission to other nodes in the future.

• When a node encounters another node that has a planned movement and a low probability, it sends this message to the node even if the probability is low, then it deletes the copy of the message, then it frees up the space at its storage unit.

• When a node encounters another node that has a planned movement and a high probability of, it sends the message to this node, then it deletes the copy of the message, then it releases the space at its storage unit.

 

4.3. Mechanisms of Acquittals

The acknowledgment mechanism between nodes is done according to the acknowledgment mechanism used by the model of “transfer by delegation” (custody transfer) [1,4,5].

4.4. Cases where the Nodes are not Allowed to Transmit Messages

• When a node encounters another node that has a high probability and has not enough energy.

• When a node encounters another node that has a planned movement and controlled and not enough energy.

• When a node encounters another node that has a planned and controlled movement and a high probability and has not enough energy.

5. Simulation and Test

The simulator is written in Java. JAVA is an object-oriented programming language, allows one hand to develop real applications and the other hand the object-oriented approach considers a program as consisting of a set of objects which adapts our approach. Figure 5

shows the general design of the application and Figure 6 shows the main interface of the application.

 

5.1. Assumptions and Data Analysis

1) Assumptions: We assume that Packet routing is done from the “store-carry-and-forward”; The nodes move according to the two models of random mobility: Restricted random waypoint and Radom Waypoint [7-9]; The speed of nodes varies between Vmin = 200 ms and Vmax = 50 ms; The space of traveled nodes varies between 50 and 500 units of surface; The number of nodes varies between 8 and 300 nodes; The number of packets from the source is 1000 packets; The energy level of each node is 1000 units of energy ; The probability is calculated locally according the routing protocol MaxProp [3]:

• MaxProp considers the probability, is the probability that j is the next node to establish con-

tact with the node i.

• For all nodes i, is initialized to .

• The cost of a path including nodes, will be the sum of probabilities that each connection along the path is not established.

• The cost that will be associated with each destination, is the smallest among those associated with different paths to d.

2) Data analysis: In this simulator we have analyzed the following data: The number of packets transmitted in the network; The number of packets not sent; The number of packets received by the destination; The energy consumed in the network; The amount of memory consumed in the network. This analysis is done according to the approach of the MaxProp and in our approach to compare the two approaches.

 

5.2. Tests and Results

Scénario1: Both areas are dense and connected. The internal connectivity of each zone is guaranteed. However,

 

there is no permanent connection between the two areas.

Scénario2: The node density is low in both areas. The internal connectivity of each zone is not guaranteed and there is no permanent connection between the two areas.

• Simulation results under the approach of MaxProp (see Figure 7 and Figure 9).

• Simulation results based on our approach (see Figure 8 and Figure 10).

6. Conclusions

DTN networks suffer from several shortcomings related to routing, especially when the network is partitioned into several zones and where the destination is not in the same region of the source, which makes traditional routing protocols ineffective to the extent of transmit messages between nodes.

We proposed an approach that involves combining the routing protocol MaxProp and the model of “transfer by delegation” custody transfer) to improve the routing in DTN networks.

According to the simulations realized, our approach has good performance in comparison to the MaxProp algorithm, but its effectiveness can be further improved.

7. References

[1]       F. Warthman, “Delay Tolerant Networks,” Delay Tolerant Networking Tutorial, 2003. http://www.ipnsig.org/ reports/DTN_Tutorial11.pdf

[2]       A. Vahdat and D. Becker, “Epidemic Routing for Partially Connected Ad Hoc Networks,” Technical Report CS-200006, Duke University, Durham, April 2000.

[3]       J. Burgess, B. Gallagher, D. Jensen and B. N. Levine, “MaxProp: Routing for Vehicle-Based Disruption-Tolerant Networks,” Proceedings of 25th IEEE International Conference on Computer Communications, Barcelona, 23-29 April 2006, pp. 1-11. doi:10.1109/INFOCOM.2006. 228

[4]       F. Guidec, “Deployment and Implementation Support Services Communicating in Pervasive Computing Environments,” Université de Bretagne Sud, Lorient, June 2008, pp. 35-65.

[5]       K. Fall, W. Hong and S. Madden, “Custody Transfer for Reliable Delivery in Delay Tolerant Networks,” Technical Report, Intel Research, Berkeley, 2003.

[6]       M. Ibrahim, “Routing and Performance Evaluation of Disruption Tolerant Networks,” University of Nice Sophia Antipolis, Nice, November 2008.

[7]       C. Bettstetter, H. Hartenstein and X. Pérez-Costa, “Stochastic Properties of the Random Way-Point Mobility Model,” ACM/Kluwer Wireless Networks, Special Issue on Modeling and Analysis of Mobile Networks, Vol. 10, No. 5, September 2004, pp. 555-567.  

[8]       C. Bettstetter, G. Resta and P. Santi, “The Node Distribution of the Random Waypoint Mobility Model for Wireless Ad Hoc Networks,” IEEE Transactions on Mobile Computing, Vol. 2, No. 3, July 2003, pp. 257-269. doi:10. 1109/TMC.2003.1233531

[9]       C. Bettstetter and C. Wagner, “The Spatial Node Distribution of the Random Waypoint Mobility Model,” Proceedings of German Workshop on Mobile Ad-Hoc Networks, GI Lecture Notes in Informatics, Ulm, 25-26 March 2002, pp. 1-18.

[10]    J. Leguay, T. Friedman and V. Conan, “Evaluating Mobility Pattern Space Routing for DTNs,” Proceedings of 25th IEEE International Conference on Computer Communications, Barcelona, 23-29 April 2006, pp. 1-10. doi: 10.1109/INFOCOM.2006.299

[11]    M. Musolesi, S. Hailes and C. Mascolo, “Context-Aware Adaptive Routing for Delay Tolerant Mobile Networks,” Proceedings of IEEE International Symposium on a World of Wireless, Mobile and Multimedia Networks, Taormina, 13-16 June 2005.

[12]    J. Leguay, “Heterogeneity and Routing in Delay Tolerant Networks,” Ph.D. Dissertation, Université Paris VI, Paris, July 2007.