﻿ A Motion and Counting Based-Routing Algorithm for Delay Tolerant Network

International Journal of Communications, Network and System Sciences
Vol.10 No.05(2017), Article ID:76527,10 pages
10.4236/ijcns.2017.105B002

A Motion and Counting Based-Routing Algorithm for Delay Tolerant Network

Xiao Du, Wuwen Lai, Jie Zhang, Hua Wang

School of Information and Electronics Beijing Institute of Technology, Beijing, China

Received: March 2, 2017; Accepted: May 23, 2017; Published: May 26, 2017

ABSTRACT

Considering the characteristics of Vehicular Ad-hoc Network (VANET), we here propose a Delay-Tolerant Networks (DTN) routing algorithm called Motion and Counting Based-Spray and Seek Routing algorithm (MNCBSS). This algorithm is based upon Spray and Wait Router and describes the method of optimization and specific procedures of the algorithm. Whereafter we perform the simulation over several classic DTN routing algorithms and MNCBSS algorithm, compare the routing algorithms by sketching the statistics and then give the analysis of the different performance of each scheme and eventually demonstrate effectiveness and reliability of the MNCBSS algorithm.

Keywords:

DTN, Routing, Optimization, Motion, Counting

1. Introduction

Delay-Tolerant Networks (DTN) works under challenged networks condition, and it is a new type of network structure system. Routing method is a key constituent part of this new network structure system [1] [2].

In DTN, we mainly use three indicators to evaluate a routing algorithm which are delivery-ratio, average-latency and overhead-ratio [3]. The importance of the indicators is hard to tell unless putting them into specific network circumstance.

Same routing algorithm in different network circumstance may perform disparately, so there is no routing algorithm which can apply to all kind of scenarios. In different network environments we will focus on different indicators. For instance, we assume the scenario is resource constrained sensor networks, so obviously overhead-ratio is more important than others. However, for most DTN networks, delivery-ratio is a priority to consider. Routing design idea is usually in the premise of ensuring a certain delivery rate to minimize the network average delay, reduce the network overhead ratio. For some specific network scenarios, it is possible to reduce the delivery rate of the way to improve the speed of information forwarding or reduce the overall network consumption [4] [5]. In this paper, a new DTN routing algorithm is proposed, which is based on spray and wait, which is a classic well-performance routing algorithm, which is called Motion and Counting Based-Spray and Seek Routing algorithm (MNCBSS). In the original route of the spray phase, the node movement state information and encounter counter information are used to determine whether the copies of the message should be sent out and then the waiting stage is converted into active search phase of the active degree of nodes, so as to get the DTN routing algorithm with better performance.

2. Research Background

Vehicular Ad-hoc Network (VANET) is a traditional mobile ad hoc network. The application of traffic on the road is a special kind of mobile ad hoc network. VANET’s network nodes are vehicles and roadside devices, which make it has some of the advantages of some other Mobile Ad-hoc Network (MANET) [6].

Compared with the general wireless communication terminal, the vehicle nodes have more power support, and the large space carrying capacity, and the vehicle also ensures the efficient wireless communication, the strong computing power and the more abundant buffer space.

With the popularization of GPS and GIS, the vehicle nodes in VANET can obtain a large number of external auxiliary information [7], including its position and speed information, traffic information and so on.

The vehicle nodes in VANET are more predictable than other mobile ad hoc networks. A link is established between the same directions of the vehicle. With the changing of network topology, the link becomes more unstable and the duration is shorter. Therefore, combining the driving direction, driving speed and traffic information of the vehicle we can predict the network topology and link state.

2.2. Spray and Wait Routing Algorithm

Spray and Wait [8] is a classical routing method, which is based on the method of limiting the number of messages in the network, while maintaining the high delivery ratio while reducing the overall routing overhead.

In the Spray and Wait route, the forwarding of a message copy is divided into two parts: Spray stage and the Wait stage. Each message M has a maximum copy of the quota L.

Spray stage: source node will distribute its’ copies to the first encounter node. There are two main forwarding modes, and one is source-spray. The source node will send a copy from its own quota to the target node, and then the maximum number of copies of the message set to the L-1. The other we call it dichotomy-spray. A node with message copies forwards the message to the target node and gives half of its copies of L to the target node, until the copy of the quota L is reduced to 1.

Wait stage: a relay node that carries a message copy is randomly moved in the network and waits for the destination node to meet, and then forwards the packet to it.

As the number of copies of the L is set up, the L copies is the maximum of the copy in the network, the number of the copy will not increase with the size of the network, so the network scalability is better.

3. MNCBSSS Routing Algorithm

3.1. Optimization Idea

MNCBSS routing algorithm is based on the characteristics of vehicle nodes in VANET, and the optimization of the Spray and Wait route is carried out in this paper. The main points of the optimization are mainly in the following two stages.

In Spray stage, we use the method called infection spread, which means source nodes holding their own copies of the messages will forward to any node encountered, and the forwarding number depends on which has already been setted. Therefore we can see in the process during a node encounter no comparative analysis and differential treatment are taking into account. The problem of this method is mainly manifested in low delivery ratio. In that case, this paper propose a method that message copies are forwarded differently based on the motion state of the node during the encounter period, in order to improve the delivery ratio of the routing algorithm.

In the Wait stage, spray and wait routing don’t do anything else, just passively wait until the destination node is encountered, then node which holds the message forwards the message out. In this case, whether forwarding is successful largely depends on the motion mode of the node and the destination node. Although this method reduce the routing overhead, it reduce the delivery ratio as well, so during the waiting period, we here turn the passive “wait” mode into active “search” mode. The concept “Active Parameter” is brought here to reflex the node’s active degree. When two node meet and set up connection, the node which carries message will compare the Active Parameter (AP) with target node to determine whether to send copies or not. Such process will improve the delivery ratio.

3.2. Algorithm Idea of the Spray Stage

In urban vehicle mobile environment, due to the road direction and distribution are generally fixed and smooth, so the movement of the vehicle is also more regular, and to a certain extent demonstrate the movement trend of the vehicle in the future. At the message diffusion stage, if two nodes’ movement directions are same or similar, the nodes they encounter in a period of time are same or similar, too. Then at this point the diffusion efficiency will be lower, if the directions of movement of the two nodes deviate, within a period of time encountered nodes will be very different. Such diffusion efficiency will be higher. At the same time, the generating and forwarding of the copy are also determined by the copy-counter, if the node in a row after C nodes found that the message M is not included, this shows that the degree of diffusion of M is at very low level, so we need to raise the message concentration to improve the delivery ratio. When a continuous D nodes encountered contain the copy of the message M, the M message concentration is too high, then the corresponding measures need to be taken to reduce the network overhead.

When the vehicle node A and node B met, then the node A holds a certain number of copies of message M which value is L, if L greater than 1, then the message M is at spray stage. In order to quickly dissipate the message copies into network, we should take movement trend and copy/delete-counter into account, and then decide how many copies of message should be forwarded or the message should be deleted. We will give the rules of the spraying of the message copies as follow.

If the direction of movement of the two nodes differ greatly and copy-counter value (refer to NC) reach copy threshold C, then we forward half copies of message M from node A to node B, if only one condition is satisfied of the two, forward one copy of message M from node A to node B, if delete-counter value (refer to ND) reach the drop threshold D then the copy number of node A minus one.

3.3. Algorithm Idea of Seek Stage

When the copy number of message M of node A is 1, then routing algorithm enter the search phase.

During the search phase, we introduce two variables to record and characterize the social activity of a vehicle node in the network: Node Encounter Counter (Hereinafter referred to as EC) and AP.

EC is a simple counter, the initial value is zero, when the node meet with other nodes, EC count plus 1. EC can partly reflect the node’s social activity, but may be not reliable at some time, for example, the initial position of the vehicle node is at map center, then the node will start with a higher EC value, but it is heading to lower node density of the local place, so its social activity decreased, only from the value of EC can not reflect the trend of node’ social activity, so another parameter is introduced here― Active Parameter―to more smoothly and accurately reflect the node’s activity.

The AP value is weighted sum of the current EC value of the node with the old AP value:

It can be seen that the AP has a certain update interval, each time to update interval, the AP will be updated, and then reset the EC counter. The value of the beta reflects the degree of relevance with old AP value, the greater the value of beta, the less relevance to the history of the node’s AP value.

When the two nodes A and B meet, a message M is determined to enter the search phase, node A first applies for access and get the AP value of the node B, then compares with the AP value of its own. If the node A has a larger AP value, the node A itself is more active, and the probability of meeting the target node is larger, so node A does not carry forward. If the AP value of the node A is smaller, then the successful delivery probability of node B is higher, so the node A will give a copy of the message to node B, then node A give up the forwarding right of message M.

After the waiting stage is converted into the seek stage, the delivery ratio of the single copy routing will be improved, and the network load will not be much affected.

The MNCBSS routing algorithm is shown in Figurer 1, and detailed implementation steps are as follows.

Step 1: two vehicle nodes met to establish a connection, the two sides exchanged AP value and motion state information, then calculate the angle between the direction of movement of the two nodes

Step 2: If there are messages whose destination node is target node, transmit them directly to the destination then confirms the transmission and clear the corresponding buffer.

Step 3: If target node is not the destination node, then the remain of the quota L is checked to determine which stage the node is at.

If the L > 1, it is at the spray stage. To determine the forwarding mode, it

Figure 1. The MNCBSS routing algorithm.

needs to calculate the angle α between direction of the motion of two node, copy-counter NC value and delete-counter ND value according to the movement state information of both sides. When the threshold D is reached, delete a copy of the message and end the processing of the message. If not to reach the threshold value D, then see if the threshold C is reached and angle α is bigger than 90 degree. If both conditions are met, then forward half copy number to the target node. If only one condition is satisfied, then forward only one of the copies, and reset the copy-counter and the delete-counter, then put an end to the message processing. If the two conditions are not satisfied, then do not forward and end message processing.

If L = 1, it is at the seek stage. Determine whether transmit or not by comparing the AP value of the two nodes, if the AP value of the target node is larger, the message is forwarded to the target node, otherwise do not forward.

4. Simulation Results and Analysis

4.1. Simulation Scenario Settings

In this paper, we use the Opportunistic Network Environment (ONE) simulation tool to analyze and evaluate the DTN protocol. It is a simulation of the routing protocol based on Java, which has the characteristics of object oriented, real network environment, discrete event driven, and it has the visual graphic interface, which can provide different kinds of simulation analysis and simulation results.

The simulation independent variable is Buffer Size, and the simulation map size is 4500 m * 3400 m, which contains 300 nodes, including the ordinary bus node and the tram nodes. The common vehicle node mobility model is Shortest Path Map Base Movement, along the road to the Point of Interests (POI) for the target, and the tram along the map on a fixed route and speed.

The simulation algorithm we choose consist of MNCBSS (this paper proposed), Spray and Wait, Epidemic. The routing parameters in the simulation are as follows.

The maximum copy quota of the Spray and Wait router is 6, and the spray pattern is Dichotomy.

The maximum copy quota of MNCBSS router is 6, and the correlation degree β is 0.75. The parameter β is gained by experiments.

Conventional parameter settings are shown in Table 1.

4.2. Simulation Results and Analysis

Due to the optimization of the two stages, the delivery rate of MNCBSS routing is slightly higher than that of the Spray and Wait routing and is significantly higher than the Epidemic routing in Figure 2. With the increase of the capacity of the node buffer, the delivery ratio of all kinds of algorithms are growing which is due to the smaller of the buffer size, the buffer of each node may be more quickly occupied. When a new message needs to be stored, the nodes will be

Figure 2. Comparison of delivery ratio among 3 algorithms.

Table 1. Settings for parameters of simulation environment.

sorted according to the TTL of the message, and then discard message with shortest TTL, which will result in a lot of message loss, so message delivery rate is very low. With the increase of the buffer space, the loss of the message is improved.

First let us see the Spray and Wait routing’s performance. Although the routing is a multi-copy routing, it limits the maximum number of copies of each message, and is influenced little by the buffer size after a certain point. Therefore, the curve tends to be stable at a certain range. In contrast, let’s see the epidemic routing’s performance. With the continuous generating of new copies of the message, the demand for the capacity of the node buffer increases, and their delivery ratio will be improved as well. MNCBSS routing is similar to the Spray and Wait routing, and the total number of copies of the message is limited. Besides, the spray phase is also optimized, so that the diffusion performance of MNCBSS routing is better. That is to say, each message may be stored in more nodes, the stationary point of the curve lay behind Spray and Wait router’s.

Network overhead ratio indicates the network overhead caused by each successful forwarding of a message to the destination node, which reflects the degree of the router consuming the network resource. As can be seen from Figure 3, the network overhead of the three router decrease differently when buffers increase. When the node buffer capacity is low, the number of successful forwarding message of all routing algorithms is very low, and that is because the node buffer size is too small, the amount of discarded data is large, so the network overhead is high. When the node buffer space is increased, the number of messages forced to drop is reduced, and the number of messages to be transmitted successfully is increased, which makes the network overhead decrease more quickly and reach a stable state.

The network overhead of Spray and Wait outperforms that of Epidemic’s. This is due to the strict restriction of the copy quota of each message, and the forwarding is not carried out in the waiting stage, which is only passively waiting for the destination node, so the network overhead ratio can be maintained at a very low level. Similarly, MNCBSS routing also limits the maximum number of messages, and the performance of the two is similar in big buffer. Besides, because the search stage of the passive waiting stage is converted to the active directional forwarding, the network overhead is slightly lower than that of Spray and Wait’ in small buffer.

The average latency of network can be used to characterize the effectiveness of the routing algorithm, which is shown by Figure 4. The average latency of any

Figure 3. Comparison of overhead ratio among 3 algorithms.

Figure 4. Comparison of end-to-end latency among 3 algorithms.

routing algorithm increases with the increasing of node buffer capacity. When calculating the latency, it selects the messages range that only contains the nodes that are successfully forwarded, and does not include the messages that are discarded or failed to deliver because of buffer overflowed and running out of TTL. When the buffer size is small, the messages which can’t be transmitted within a short period of time are discarded quickly, so it seems that the average latency is very low. So, it is pointless to compare the performance when the routing algorithms don’t reach their stable states. The optimization of MNCBSS routing in the spray phase makes the message has better diffusion performance, so it has lower Average Latency than Spray and Wait routing. When it comes to seek stage, the method of MNCBSS is more positive than Spray and Wait’s, so MNCBSS needs larger buffer size and it reflects on Figure 4.

5. Conclusion

In this paper, the proposed MNCBSS routing is a new DTN routing algorithm which considers the characteristics of vehicle ad-hoc networks to improve the routing algorithm. In the spray stage, the nodes use different spray mode to improve the diffusion degree of the message copies in the network. In the waiting stage, the MNCBSS is converted to the active “search” mode, so as to more effectively distribute the message copies. Through the simulation results, we can see that the MNCBSS routing in the maintenance of the lower network overhead, improve the information delivery rate, and reduce the latency.

Acknowledgements

This work is supported by “National High Technology Research and Development Program of China” (Grant No. 2015AA01A709) and “National Science Foundation of China (NSFC)” (Grant No: 61471037).

Cite this paper

Du, X., Lai, W.W., Zhang, J. and Wang, H. (2017) A Motion and Counting Based-Routing Algorithm for Delay Tolerant Network. Int. J. Communications, Network and System Sciences, 10, 14-23. https://doi.org/10.4236/ijcns.2017.105B002

References

1. 1. Fall, K. (2003) A Delay-Tolerant Network Architecture for Challenged Internets. Proc of ACM SIG- COMM’03, New York, 27-34. https://doi.org/10.1145/863955.863960

2. 2. Jain, S., Fall, K. and Patra, R. (2004) Routing in a Delay Tolerant Network. ACM SIGCOMM, 34, 145-158. https://doi.org/10.1145/1030194.1015484

3. 3. Wang, Z., Wang, X.H. and Sui, J.Q. (2012) Extending Research for ONE Simulator of Opportunistic Network. Application Research of Computers, 29, 272-277.

4. 4. Vahdat, A. and Becker, D. (2000) Epidemic Routing for Partially-Connected Ad Hoc Networks. Technical Report CS-2000-06, Duke Univer-sity.

5. 5. Lindgren, A., Doria, A. and Schelén, O. (2003) Probabilistic Routing in Intermittently Connected Networks. SIGMOBlLE Mobile Computing Communications Review, 7, 19-20. https://doi.org/10.1145/961268.961272

6. 6. Zhang, F. (2011) Research on MAC Protocol for Vehicular Ad Hoc Network. Beijing University of Posts and Telecommunications, Beijing.

7. 7. Hossmann, T. (2010) Know Thy Neighbor: Towards Optimal Mapping of Contacts to Social Graphs for DTN Routing. INFOCOM IEEE.

8. 8. Spyropoulos, T., Psounis, K. and Raghavendra, C.S. (2008) Efficient Routing in Intermittently Connected Mobile Net-works: The Multiple-Copy Case. IEEE/ ACM Trans. on Network, 16, 77-90. https://doi.org/10.1109/TNET.2007.897964