A DTN Oriented Adaptive Routing Algorithm Based on Node Load

Hongyan Cui ,Diyue Chen ,Roy E.Welsch

1 State Key Laboratory of Networking and Switching Technology,Beijing University of Posts and Telecommunications,Beijing 100876,China

2 Beijing Laboratory of Advanced Information Networks,Beijing University of Posts and Telecommunications,Beijing 100876,China

3 Massachusetts Institute of Technology,Cambridge,MA 02139,USA

Abstract: In recent years,Delay Tolerant Networks(DTN)have received more and more attention.At the same time,several existing DTN routing algorithms generally have disadvantages such as poor scalability and inability to perceive changes in the network environment.This paper proposes an AdaptiveSpray routing algorithm.The algorithm can dynamically control the initial maximum message copy number according to the cache occupancy rate of the node itself,and the cache occupancy rate is added as an impact factor to the calculation of the probability of each node meeting the destination node.In the forwarding phase,the node will first compare the meeting probability of itself and the meeting node to the destination node,and then choose different forwarding strategies.The simulation shows that the AdaptiveSpray algorithm proposed in this paper has obvious advantages compared with the existing routing algorithms in terms of message delivery rate and average delay.

Keywords: DTN;routing algorithm;adaptive;cache management

I.INTRODUCTION

Internet services based on the TCP/IP protocol have now penetrated into all aspects of human social life,greatly improving people’s living standards.The main features of the service model provided by the TCP/IP protocol are: a relatively fixed communication infrastructure,a stable end-to-end transmission path between the data source and the destination,and the relatively short data transmission delay between nodes.

However,with the continuous expansion of various new research fields,more diverse and more complex network environments have emerged.As early as the end of the 20th century,researchers began to work on the interstellar Internet [1].However,the characteristic of celestial movement is that there is no end-toend stable connection,and because nodes are usually deployed on different planets,the transmission delay between nodes is very high and the connection between nodes is frequently interrupted [2].The existing end-to-end TCP/IP network architecture is not applicable to interstellar Internet networks.At the same time,with the continuous development of wireless communication technology and the emergence of various new technologies,the applications of various mobile terminal devices are becoming wider and wider.Researchers found that many wireless communication networks on land also have the same communication problems as interstellar networks,such as social networks[3],vehicle-mounted networks[4],wireless sensor networks[5]and so on.In these networks,in most cases there is no end-to-end transmission path.Even if there is an end-to-end transmission path,it is relatively easily interrupted,the data transmission rate is small,and the transmission delay is long.In these application scenarios,many severe challenges are encountered when using traditional TCP/IP protocol for network communication.In order to deal with the data transmission problems of these networks,Kevin Fall in 2003 first proposed the Delay Tolerant Network (DTN) model [6].The DTN model adds a new protocol layer on the basis of the traditional TCP/IP protocol,which is the Bundle layer [7].The Bundle layer is located between the application layer and the transport layer of the traditional Internet model.Its function is similar to the gateway of the traditional application layer,but it does not perform packet switching,but message forwarding.When a message arrives at a node,the node will first store the message and carry the message to move in the network.When the node carrying the message needs to pass the message to other nodes,the message is moved from the storage location on that node to the storage location on another node.In this way,the message is transmitted until the delivery of the message is completed or the life cycle of the message is exhausted and is discarded.The storage-carry-forwarding mode of the DTN network overcomes intermittent connections,long delay time,changeable network topologies and high error rates and other related problems,and improves the quality of network communication.

In DTN networks,nodes are able to move and there is usually no end-to-end network connectivity between nodes,resulting in no fixed topology for the entire network.The traditional routing algorithms are based on stable network topology,so these algorithms cannot be applied to DTN networks.Therefore,the routing algorithm is one of the most important research fields for DTN networks[8,9].This article first introduces several typical routing algorithms for DTN networks in detail,and analyzes the advantages and disadvantages of these routing algorithms.On this basis,this paper considers the influence of node cache occupancy rate on message delivery,and proposes an AdaptiveSpray-ByPro algorithm based on the node cache occupancy rate.

The remaining structure of this article is as follows:Section II mainly introduces some existing routing algorithms in DTN networks;Section III proposes an AdaptiveSprayByPro algorithm based on node cache occupancy;Section IV simulates the AdaptiveSpray-ByPro algorithm and compares it with several classic DTN routing algorithms;Section V summarizes the work of this article.

II.RELATED WORKS

In recent years,experts and scholars have put forward many effective routing strategies for different DTN application scenarios.Considering the number of copies of messages in the network,routing strategies can be divided into forwarding-based and replication-based[10].

For forwarding-based routing strategies,at any given time,only one node carries a message for transmission in the network.When encountering a suitable relay node for the next hop,the current node delivers the message to the meeting intermediate node until the message is delivered to the destination node or the life cycle of the node is exhausted.When the destination node receives the message,there is no need to notify the node in the network to delete the copy of the message.Therefore,this strategy consumes relatively little network resources.But the disadvantage is that there is only one message in the network,and the DTN itself is a restricted network,so the message delivery rate is low.

Direct Delivery [11] is the simplest routing algorithm based on forwarding.The main idea is that the source node generates a message,the source node will always carry the message in the network,and will not forward the message additionally.Until it meets the destination node,the source node will not deliver the message to the destination node.In the entire delivery process,there is only one copy of the message,and the number of times a message is delivered in the network is one.

First Contact [12] is also a relatively simple routing strategy based on forwarding.The difference with Direct Delivery is that in the message delivery process,the source node forwards the message to the intermediate node that it meets.Its main idea is that the source node generates a message and stores and carries the message to move in the network,when the source node encounters an intermediate node during the movement,it will forward the message to the intermediate node.The intermediate node carries the message and continues to deliver the message with the same strategy until the message is successfully delivered to the destination node or discarded due to exhaustion of its life cycle.When a node carrying a message meets multiple intermediate nodes at the same time,the message will be randomly forwarded to one of the nodes for delivery.

Different from the routing strategy based on forwarding,the routing strategy based on replication mainly increases the probability of the message meeting the destination node by increasing the number of copies of the message in the network.The increase in the number of message copies leads to a large consumption of network resources and is prone to congestion problems [13,14].However,in an environment with relatively sufficient network bandwidth and node cache space,a routing strategy based on replication will greatly improve the success rate of message delivery.

The Epidemic routing algorithm[15]was originally proposed by Vahdat and Becker in 2000.The principle is that the node carrying the message moves in the network,and when it encounters a neighbor node and the neighbor node does not carry the message,the node carrying the message copies the message and transmits it to the neighbor node.In the same way,all nodes carrying the message copy and forward the message to all intermediate nodes until the message reaches the destination.Epidemic routing will greatly increase the delivery rate of messages,and the transmission delay is relatively small.However,as the number of replicas in a restricted network such as DTN increases,a large number of replicas occupy network resources,which can easily to cause network congestion.

In order to overcome the problems caused by the Epidemic routing,a Spray and Wait algorithm[16]can be considered.It mainly reduces network overhead by limiting the number of copies of messages in the network.The source node generates the message and sets the number of copies of the message in the network.Initially,the message is copied and transmitted like Epidemic routing.After the message reaches the set maximum number of copies,the message will no longer be copied,but carried by the node.The Spray and Wait routing is mainly divided into two phases:spray and wait.In the spray phase,the node generates a message and copies L message copies,which are carried by the source node and passed to the L intermediate nodes encountered first.If there is no destination node of the message among the L nodes at this time,it will enter the wait phase.In the wait phase,the L nodes and the source node carrying the message will move around the network with the message until a certain node encounters the destination node of the message,and then forward the message.The Binary Spray and Wait algorithm improves on the original Spray and Wait algorithm.In the spray phase,it adopts a halving forwarding method,which effectively improves the message delivery rate.

The maximum message copy number L is a key parameter that determines the performance of the Spray and Wait algorithm.The paper[17]controls L by controlling the regeneration and deletion of messages.If the message has been copied and forwarded before the message expires,it indicates that the number of message copies has not reached the upper limit of the current network,and the message can be regenerated by resetting the remaining life time of the message and the number of available copies,thereby increasing the value of L;If the node carrying the message and the node carrying the same message have never met before,it means that too many nodes have carried the message.At this time,delete the message to limit the value of L and restore the storage space.This method changes the value of the maximum message copy number L from a fixed value to a variable value that can be adapted to the application environment,which expands the application range of the algorithm.

Prophet[18]is a routing algorithm based on probability.The author believes that the movement of nodes is not blind and random,but has certain rules to follow.It mainly uses the historical transmission probability of the node to the destination node to calculate the current transmission probability of the node to the destination node.When two nodes meet,determine whether the node carrying the message should pass the message to the meeting node by comparing the probability of the encounter between the two nodes and the destination node.Each node maintains a forwarding probability table.When a node carrying a message encounters another node,the node does not blindly forward the message to the encountering node,but uses the probability forwarding table to calculate its probability of reaching the destination node,by comparing the probability value to decide whether to pass the message to the meeting node.

III.ALGORITHM DESIGN

Obviously,for routing in the DTN network,if a message is copied and forwarded to more nodes,the greater the probability of successful delivery,the most extreme is the Epidemic algorithm,but the shortcomings are also obvious,occupying too much network resources;Similarly,if a message is copied and forwarded to other nodes as little as possible,the delivery rate will decrease.The most extreme is Direct Delivery algorithm.Spray and Wait algorithm is between these two algorithms,that is,some restrictions on the number of copies.However,in the Spray and Wait algorithm,the maximum message copy number of the source node is a fixed input value,and this value does not consider the load of the network and the cache occupancy rate of each node.Research shows that in DTN networks of different scales and different transmission strengths,the optimal maximum message copy number varies greatly,and the use of different maximum message copy numbers will have a great impact on the performance of the algorithm.In addition,in the Spray and Wait algorithm,the delivery of messages is not pre-judged,and forwarding and delivery occurs every time a new node is encountered.This increases the blindness of message transmission,increases unnecessary waste of network resources,and reduces the rate of message delivery.

To address the problems in the Spray and Wait algorithm,this section proposes an improved algorithm,the AdaptiveSpray algorithm,and its forwarding process is shown in Figure 1.The algorithm is divided into three stages: the Adaptive message replication phase,the SpraybyPro phase,and the ForwardbyPro phase.

Figure 1.AdaptiveSpray algorithm flowchart.

Figure 2.Message delivery rate of each algorithm.

3.1 Adaptive Message Replication Phase

The adaptive message replication phase is the preparation phase before data forwarding.First,obtain the total size of the message data in the node cache by calculation.The message sources in the node cache are mainly divided into two types: one is the message newly generated by the node,and the other is the message received by the node as a relay node.

The calculation formula for the message received by the node as a relay node is as Eq.(1):

Received{mi.size}represents the data size of a message received before the current time.Xrepresents the total number of messages successfully received by this node before the current time.

The message generated by the node as the source node is calculated as Eq.(2):

Created{mi.size}represents the data size of a message created before the current time.Yrepresents the total number of messages successfully created by this node before the current time.

Therefore,the sum of the message sizes in the node cache can be expressed as Eq.(3):

The cache of each node in the network has an initial size:Buffersize.The calculation formula of node cache occupancy rateβnowis as Eq.(4):

Before the source node initiates the transmission task,it will copyLcopies of the message.Unlike the traditional Spray and Wait routing algorithm,whereLinitis an initial set value,in the AdaptiveSprayByPro algorithm,the source node can dynamically adjust the initial number of replicated copies of messages in real time according to its cache occupancy.The calculation formula ofLis as Eq.(5):

Linitis an initial set value,βnowis the current buffer occupancy rate of the source node,βbestis the optimal buffer occupancy rate of all nodes that are initially set,andais an adjustment factor.

This is equivalent to providing a negative feedback for network operation,helping to maintain the overall network load level at an appropriate level.

3.2 SpraybyPro Phase

After the source node completes the copy of the message,it enters the SpraybyPro phase.In this phase,all nodes first calculate the probability value P of themselves encountering other nodes.Taking into account the impact of some node performance on message transmission,especially in DTN,the energy and cache occupancy of nodes in the network will affect its delivery of messages to the destination node.In this paper,the cache occupancy rate is added to the calculation of the P value in the form of an impact factor.The calculation of P can be divided into three parts:

Firstly,the delivery probability value will be updated with each encounter and the calculation formula used is as Eq.(6):

P(a,b)oldis the probability before meeting,Pinitis an initialization parameter,andαis an adjustment factor.

Secondly,if A and B have not met for a long time,the calculation formula at this time is as Eq.(7):

γis a constant in the range(0,1),kis the number of time units since the last update.

Thirdly,if A and B often meet,and B and C often meet again,then there is a transitive connection between A and C,and the calculation formula is asEq.(8):

Algorithm 1.Algorithm for SpraybyPro phase.

βis a constant in the range [0,1].At this phase,the message forwarding process between nodes is shown in algorithm 1:

3.3 ForwardbyPro Phase

In the SpraybyPro phase,if the number of copies of the message carried by the node itself is reduced to 1,then it enters the ForwardbyPro phase.At this phase,the message forwarding process between nodes is shown in algorithm 2:

IV.SIMULATION RESULTS

In this section,ONE software [19,20] is used to test each algorithm.The simulation is based on the map of Helsinki.Several nodes are randomly placed in the area.These nodes are divided into four groups to simulate different types of mobile nodes in reality,the specific parameters of each group of nodes are shown in Table 1.At the same time,each group of nodes will berandomly assigned their points of interest in the map.After completing a movement process,the probability of nodes selecting their corresponding points of interest as new destination locations is higher than that of other locations in the map.The probability of selecting different points of interest as the new destination location is also random and different.This is to simulate the different working attributes of different network nodes in the real DTN network scene,and the movement is not completely random.

Table 1.Node attribute table.

Table 2.Parameters of high intensity transmission scenario.

Algorithm 2.Algorithm for ForwardbyPro phase.

In order to better evaluate the performance of routing algorithms in DTN networks,this paper mainly uses three indicators: message delivery rate,network overhead rate,and average delay for evaluation.

The message delivery rate is defined as the ratio of the number of successfully delivered messages to the total number of messages delivered in the DTN net-work.The calculation formula is as follows Eq.(9):

The network overhead rate is defined as the ratio of the number of messages that are not successfully delivered to the destination node to the number of messages that are successfully delivered to the destination node.The calculation formula is as follows Eq.(10):

The average delay is defined as the average time spent in the entire network for all successfully delivered messages from the source node to the destination node.The calculation formula is as follows Eq.(11):

tidrepresents the time when messageiwas received,tisrepresents the time when messageiwas generated,andnrepresents the total number of messages successfully delivered.The algorithms for comparison in this section are as follows:DirectDelivery,Epidemic,Spray and Wait (L=8),Prophet (Pinit=0.75,γ=0.98,β=0.25) and AdaptiveSpray(Linit=8,βbest=0.5).

4.1 High Intensity Transmission Scenario

In this scenario,the data generation interval is very short and the data generated is large.The specific parameters are shown in Table 2:

By modifying the number of nodes,the impact of mobile node density on the performance of different DTN routing algorithms is examined.

As shown in Figure 2,as the density of nodes increases,the message delivery rate of the DirectDelivery algorithm is basically unchanged and maintained at a low level,the curves of the other four algorithms have similar trends.The AdaptiveSpray algorithm has the best performance,when the node density is high,its message delivery rate is more than 10% higher than the Spray and Wait algorithm.It is because the AdaptiveSpray algorithm limits the number of copies of message copies,reduces the cache occupancy rate of each node in the high transmission intensity environment,reduces the queuing delay within the node,and thereby increases the message delivery rate.At the same time,unlike the Spray and Wait algorithm that maintains a fixed number of message copies L,the AdaptiveSpray algorithm can dynamically adjust the value of L through the cache occupancy rate of each node.When the node density increases,the cache occupancy rate of each node decreases,and the most suitable L value also changes at this time.Therefore,after increasing the node density,the AdaptiveSpray algorithm has obvious advantages.

It can be seen from Figure 3 that the network overhead rate of DirectDelivery,Spray and Wait and AdaptiveSpray is independent of node density and kept at a low level.While with the increase of node density,the increasing trend of the network overhead rate of Epidemic and Prophet algorithms is obvious.

Figure 3.Network overhead rate of each algorithm.

Figure 4.Average delay of each algorithm.

It can be seen from Figure 4 that the AdaptiveSpray algorithm performs best.This is because it can dynamically adjust the L value through the cache occupancy rate of each node,always maintaining the cache occupancy rate of each node at an appropriate level,and reducing the queuing delay within the node.In addition,unlike the blind forwarding in the Spray and Wait algorithm,the AdaptiveSpray algorithm compares the probability of the current node and the encountering node reaching the destination node,and then performs selective forwarding,which improves the forwarding efficiency and reduces the total delay.

4.2 Low Intensity Transmission Scenario

In this scenario,the data generation interval is long and each datum generated is relatively small.The specific parameters are shown in Table 3:

Table 3.Parameters of low intensity transmission scenario.

By modifying the number of nodes,examine the impact of mobile node density on the performance of different DTN routing algorithms:

It can be seen from Figure 5 that in a network environment with low transmission intensity and low network load,as the node density increases,the messagedelivery rate of each algorithm does not change much,and the message delivery rate of the DirectDelivery algorithm remains at a low level.The AdaptiveSpray algorithm expands advantages over the Spray and Wait algorithm in terms of message delivery rate.This is because the initial message copy number L value in the Spray and Wait algorithm is still consistent with the high transmission intensity scenario.However,in a network environment with low transmission intensity,the gap between the initial L value and the theoretically optimal L value may be increased.This also shows that the Spray and Wait algorithm has certain limitations,the adaptability is poor and the L value needs to be updated artificially.The AdaptiveSpray algorithm can update the value of L according to the node’s cache occupancy rate,adapt to the changes in the network environment,and make up for this defect.

Figure 5.Message delivery rate of each algorithm.

It can be seen from Figure 6 that the overhead rate of the three algorithms of DirectDelivery,Spray and Wait and AdaptiveSpray is still basically independent of node density,and kept at a low level.Compared with high transmission intensity scenarios,the overall network overhead rate decreased.While with the increase of node density,the increasing trend of the network overhead rate of Epidemic and Prophet algorithms is still obvious.

Figure 6.Message delivery rate of each algorithm.

Figure 7.Message delivery rate of each algorithm.

It can be seen from Figure 7 that with the increase of node density,the average delay of the other four algorithms except the DirectDelivery algorithm is reduced,and the AdaptiveSpray algorithm performs best.It shows that in the low intensity transmission scenario,the AdaptiveSpray algorithm based on probability selective forwarding can still effectively reduce the total delay.

V.CONCLUSION

This paper proposes an AdaptiveSpray routing algorithm based on node cache occupancy.In the initial stage,the source node calculates the maximum number of message copies based on its current cache occupancy rate,thereby forming negative feedback on the overall network load.In the message spray stage,nodes decide to adopt different forwarding strategies according to the probability of themselves and the encountering node reaching the destination node,thereby reducing the blindness of message delivery.

In the two different DTN test scenarios of high transmission intensity and low transmission intensity,this paper compares the three indicators of message delivery rate,network overhead rate and average delay.The results show that the AdaptiveSpray algorithm proposed in this paper has obvious advantages in message delivery rate and average delay,and the network overhead rate is maintained at a stable low level.

ACKNOWLEDGEMENT

This work was supported by National Key R&D Program of China (2020YFB1807805,2020YFB1807800),CERNET Innovation Project(NGII20190806).