Routing Algorithm for Delay-Tolerant Network Based on Price Game

Routing Algorithm for Delay-Tolerant Network Based on Price Game

Ligang Cong Huamin YangYanghui Wang 

School of Computer Science and Technology, Changchun University of Science and Technology, Changchun 130022, China

Corresponding Author Email:
10 September 2019
28 December 2019
29 February 2020
| Citation



Due to the limited resource of Delay-Tolerant Network (DTN) nodes, in order to prolong their life cycles, the nodes would exhibit a “selfish” behavior, which is quite common in DTN, and will seriously affect the overall performance of the network. Targeting at these issues, to suppress such behavior and improve the overall performance of DTN, this paper proposed a DTN routing algorithm based on the auction price game, which converted the routing process into a data forwarding service auction process, and took the “prices” and the history data of the nodes as the main basis for the selection of data nodes. The experimental results showed that, compared with Epidemic algorithm and FC algorithm, the proposed algorithm showed good performance in time delay and cost ratio, which had well suppressed the “selfish” behavior of the nodes, and the proposed algorithm is a DTN routing algorithm with balanced performance.


delay-tolerant network (DTN), price game, routing algorithm

1. Introduction

DTN is a new-type network structure used to cope with the “challenging environments” such as frequent link interruption, long time delay, and high bit error rate, etc., and it is a development direction of future networks [1]. The “selfish” behavior of nodes is an important problem in DTN, and the emergence of such problem will seriously affect the performance of the network. Therefore, how to utilize the resources of DTN more economically and avoid or reduce the “selfish” behavior is a challenge for the designer of the network [2, 3]. The so-called “selfish” behavior of nodes means that, in a DTN, the resources such as the node storage space, remaining energy, data processing capacity, and bandwidth between links are quite limited. To extend their life cycles, the nodes often display the phenomenon of unwilling to undertake data forwarding tasks, and such phenomenon is called the “selfish” behavior of DTN nodes [4-6].

Research found that the root cause for the “selfish” behavior of most DTN nodes is the conflict of interests between the nodes. If the interests between the nodes can be effectively balanced, then an effective cooperation mechanism could be constructed [7] so as to effectually solve the problem of “selfish” nodes during the routing process of DTN and improve the efficiency of the network [8, 9]. Cho et al. [10] proposed a military DTN routing framework, the PROVEST, which used a data-driven method to reduce the resource consumption of selfish nodes, meanwhile, it dynamically estimated the credibility of the nodes based on the changes in the environment and node conditions and adopted it to build the information transmission paths. Zhang et al. [11] designed a node cooperation mechanism called the PRI, which introduced the concept of reputation into the DTN node data forwarding process, and set a reputation value for each network node; a higher reputation value represented the more times a node provided data forwarding to other nodes, and a node with a higher reputation value also had a higher success rate in receiving data forwarding services from other nodes; on the contrary, a node with a lower reputation value had a higher probability of data forwarding requests being rejected. Wu et al. [12] proposed an incentive mechanism for routing nodes based on the game theory, in the process of data forwarding, the probability value was modified according to the performance of the node, the message was transmitted from node with a lower probability to the node with a higher probability, and virtual currency was adopted to reward the nodes with more forwarded data and increase the probability value. Wang et al. [13] designed a DTN incentive model called the ODEs, they introduced the concept of “reward” in data forwarding; nodes with more forwarded data had more “rewards” and nodes with less forwarded data had less “rewards”;  the accumulated "reward" value was associated with the priority of the node, which had suppressed the “selfish” behavior of nodes to a certain extent.

Most of the above studies were solely based on the current status of the network nodes or solely based on the historical reputation information of the nodes, although they had suppressed the “selfish” behavior of nodes to some extent, if the two could be considered comprehensively, it’ll not only suppress the “selfish” behavior of nodes, but also balance the network loads, extend the overall service life of the network, and improve the routing performance [14]. Therefore, this paper proposes a DTN routing algorithm based on the auction price game, which completes the routing selection process by comparing the quoted prices of neighbor nodes; the composition of the prices of neighbor nodes includes the current status and historical forwarding performance of the nodes, it suppresses the “selfish” behavior of nodes by strengthening the price factor, and improves the overall network performance while completing the routing.

This paper consists of five parts. The first part is an introduction to the research background and related issues, it outlines the basic ideas for solving the DTN routing problem and the “selfish” behavior of nodes; the second part describes the routing model proposed in this paper in detail; the third part converts the model into the routing algorithm; the fourth part compares the proposed model with other routing models through experiments to verify the effectiveness of the proposed model; the fifth part gives the conclusion.

2. DTN Auction Game Model

According to above analysis, the game theory can regulate and balance the benefits of event participants [15], and the introduction of this theory can suppress the “selfish” behavior of DTN nodes [16, 17] and improve the network performance. As the scale of DTN continues to expand, the node selfishness problem will be very prominent and will definitely become the bottleneck of DTN performance. Therefore, it is of great necessity to study how to effectively suppress the “selfish” behavior of DTN nodes, to this end, this paper proposes a DTN routing algorithm based on price game, in the hopes of solving the routing problem of DTN while suppressing the “selfish” behavior of nodes, as well as enhancing the overall performance of DTN.

2.1 DTN routing mode analysis

The number of DTN nodes is limited, and the locations of the nodes change frequently, lacking the fixed end-to-end connections, and the routing adopts the "storage-carry-forward" mode [18]. Therefore, the core problem of DTN routing lies in the process of finding a suitable data forwarding node which can make sure the data reach the target node while reducing the network consumption as much as possible.

When a node in DTN needs to send data, it usually has several alternative neighbor nodes. If the Epidemic routing algorithm is adopted at this time to spread the data to the entire network, the data will eventually reach the target node, but it’ll make the network full of the copies of the data, increase the consumption of the network, and greatly increase the probability of network congestion [19], therefore, multi-copy routing algorithms such as the Epidemic routing algorithm are not suitable for DTN. When designing routing algorithms for DTN, single-copy routing mode or finite-copy routing mode should be taken as priority, and choosing a proper data forwarding node is especially important.

Figure 1. DTN routing process

As shown in Figure 1, the DTN source node has data to send to the target node, during this period, it has to go through multiple node selections before finally hand over the data to the target node. In the process, since the nodes numbered 2 and 5 are more suitable due to their own conditions, they are chosen from multiple adjacent nodes to participate in data forwarding. The process described here seems to be quite simple, but the actual node selection process is much more complicated. Each forwarding node selection process in the routing process is very similar to the actual goods auction process. Therefore, the entire routing process can be abstracted into a multi-stage auction game model [20].

The source node is defined as the buyer, the "auction goods" purchased by it is the data forwarding service; the neighbor node is defined as the seller, and the "auction goods" provided by it is the data forwarding service as well. Each time a data forwarding service has been completed, the source node needs to pay a certain fee to the forwarding node [21]. At last, when the target node receives the data sent by the source node, it needs to pay the source node a certain fee to reward the source node to send the data to the target node. The entire routing process is divided into several nodes. Each stage is an auction game, and every auction game pursues the Nash equilibrium. Finally, the multi-stage auction games constitute a subgame perfect Nash equilibrium [22, 23].

2.2 Auction game model

The participants of the auction game are the source node and neighbor nodes of DTN, wherein the source node is the buyer of the data forwarding service, and it searches for reliable forwarding nodes through bidding; the neighbor nodes are the sellers of the data forwarding service, and they auction their own data forwarding services. During the process of the game, both the buyer and the seller need to make a quote of the service based on their own status and the status of other nodes they have mastered.

2.2.1 Definition of data forwarding service prices

(1) Quoted price of neighbor nodes

The neighbor nodes here refer to the seller nodes that provide data forwarding services during each game. If there is a node i that needs to forward data, then n nodes that are adjacent to it and have data forwarding conditions need to make a quote. The quoted price of any neighbor node j is defined as:

$p_{j}(i)=\lg \frac{h_{j} L_{i j}(t)}{s_{j}}$  (1)

where, hj represents the number of hops from node j to the target node, sj represents the remaining storage space of node j, and there is Lij(t)=32.44+201gdij(t)+201gfi, it represents the space transmission loss generated during the information transmission process from node i to node j at time t, and is called the free space transmission loss; dij(t) is the distance between nodes vi and vj at time t, fi is the link carrier frequency [24].

Formula (1) defined the quoted price of the data forwarding node. Under the same conditions, the more the number of hops, the greater the free space transmission loss, and the higher the price; the more remaining storage space, the lower the price. This design has fully considered the actual characteristics of DTN. The number of node hops, the free space transmission loss, and the remaining storage space are all closely related to the routing performance of DTN. Larger number of hops generally represents longer distance, and means that the data processing time delay is longer; under the same conditions, the fewer hops from the target node, the better. The greater the free space transmission loss, the worse the link quality. A larger remaining storage space is particularly important for DTN, larger remaining storage space means that the node could receive a large amount of data, its data forwarding ability is stronger, and the probability of network congestion is lower. Therefore, Formula (1) clearly reflects the data forwarding service ability of the current data node, the lower the quoted price, the stronger the service ability.

(2) Quoted price of source nodes

The so-called source nodes here refer to the buyers of the data forwarding service during each auction game, including the data source node that initiated the routing service for the first time, and the data forwarding nodes during the whole routing process. Assume the data source node number is i, then i's quoted price is:

$q_{i}=\frac{\sum_{j=1}^{n} p_{j}(i)}{n}$   (2)

where, n represents the total number of i’s neighbor nodes that can provide data forwarding services, and the quoted price of the data source node defined by Formula (2) is the mean of the quoted prices of all neighbor nodes, it is the average level of the data forwarding service prices of the neighbor nodes, and can reflect the general status of data forwarding services that could be provided by the current network. The purpose of this design is to make the routing data evenly distributed, so as to prevent individual nodes from taking too many tasks and failing prematurely, and the goal is to delay network congestion at the greatest extent.

2.2.2 Node earnings

During the routing process, the target node must pay corresponding reward to the source node to compensate for the energy it consumed for sending the data. At the same time, the source node must pay certain rewards to the forwarding nodes as well. In this way, neighbor nodes would start to compete with each other in order to obtain earnings from the data forwarding tasks. By comparing the prices, the source node selects a node from the many neighbor nodes to undertake the data forwarding service, and pays the reward. The earning is the core part of the auction game, it consists of two parts: the reward and the cost, this section will give an introduction to the earnings of the nodes.

(1) Definition of earning rules

In DTN, due to the different roles of nodes in the routing process, their earning rules vary as well, the specific rules are as follows:

1) In the entire DTN routing process, participant nodes can be divided into three types: data source node, forwarding node, and target node;

2) If a node belongs to none of the above types, its earning is 0;

3) If the node is a source node, its earning comes from the compensation provided by the target node;

4) If the node is a forwarding node, its earnings can be divided into two parts, the earning from data receiving game and the earning from data sending game, respectively;

5) If the node is a target node, it has no earning at all, it is only responsible for paying for the service behavior of other nodes, and its role is similar to the “central bank”;

6) The final earnings of the source node and forwarding node need to deduct the costs.

(2) Data forwarding service transaction price

The previous section introduced the quoted price of the source node and the neighbor nodes, and the Formula (3) below describes the transaction price of the data forwarding service. When a neighbor node's quoted price is lower than the data source node's posted price, then the neighbor node satisfies the basic conditions for forwarding data, and such nodes constitute a set of alternative data forwarding nodes.

$\sigma_{i j}=\left\{\begin{array}{c}p_{j}(i), p_{j}(i) \leq q_{i} \\ 0, p_{j}(i)>q_{i}\end{array}\right.$   (3)

In order to suppress the selfish behavior of the nodes and avoid the “routing black hole” in the network caused by only receiving data without sending data, here we introduce the node forwarding rate αj to represent the data forwarding history of node j. As shown in Formula (4), after dividing the quoted price by the forwarding rate, the results are sorted, and the node with the smallest result is selected as the data forwarding node.

$\sigma_{i j}=p_{j}(i), j=\arg \min \left(p_{j}(i) / \alpha_{j}\right)$   (4)

(3) Definition of the payoff function of source node

In the auction model, source node i is the buyer of data forwarding service, it generates data and completes a transmission, after the data forwarding is completed, the target node will pay a reward γ, the forwarding node uses this reward to pay the data forwarding service fee, and the remaining part is its own earning. The payoff function of source node i is:

$u_{j}(t)=\gamma-\sigma_{i j}-\frac{e_{i j}}{e_{j}(t)}+\frac{s_{i j}}{s_{j}}$  (5)

where, γ represents the reward paid by the target node, σij represents the reward paid by the source node to the forwarding node, eij is the consumed energy for data forwarding, ej(t) is the remaining energy of the source node, sijis the newly-added storage space after the source node sends the data, sj is the total remaining storage space of the source node. In order to ensure that the node earning is positive, the reward γ paid by the target node should satisfy:

$\gamma>\sigma_{i j}+\frac{e_{i j}}{e_{j}(t)}$   (6)

(4) Data forwarding node earnings

The forwarding node is not target node, but intermediate node. Assume that forwarding nodes do not consume energy when receiving data, and their energy consumption cost is 0; however, they still need to pay the cost of storage space, then the earnings of the forwarding nodes for receiving data can be expressed as:

$u_{i r}(t)=\sigma_{i j}-\frac{s_{i j}}{s_{i}}$   (7)

where, σij represents the reward paid by the source node to the forwarding node, sij is the reduced storage space after the forwarding node receives the data, and si is the total remaining storage space of the forwarding node. Because as a data forwarding node, besides receiving data, it also needs to send data, so its earning also includes the data sending part, and the sending process is basically the same as that of the source node. Therefore, the final total earning can be expressed as:

$u_{i}=u_{i \mathrm{r}}+u_{i s}$  (8)

where, uis is the data sending earning, which can be expressed as:

$u_{i s}(t)=\gamma-\sigma_{k i}-\frac{e_{k i}}{e_{k}(t)}+\frac{s_{k i}}{s_{k}}$   (9)

where, k represents the selected node in the twice sending process, and the meaning of other parts of the formula is the same with Formula (5).

3. Routing Algorithm Design

According to the description in the previous section, an auction game-based DTN routing model has been constructed. With the help of this model, an economical, efficient, and reliable path can be found between the source node and the target node. With this model as the basis, a price routing algorithm based on auction game is constructed in this section; the algorithm is named the “Auction Price Routing Algorithm”, abbreviated as APRA, which will be introduced in this section as well.

When a node in DTN needs to send data, it will first start the quotation mechanism, wait for the quoted prices and history data forwarding success rates of the neighbor nodes, and calculate the posted price of data forwarding. After it gets the quoted prices and success rates of the neighbor nodes, the routing model is adopted to process the prices and make routing selection.

Figure 2. Flow of the routing algorithm based on price game

The flow of the DTN routing algorithm based on the auction game mechanism is shown in Figure 2. The specific steps are as follows:

Step1: When node i needs to send data, it initiates a data transmission task and determines node j as the target node;

Step2: Judge whether the target node j is one of the neighbor nodes, if it is a neighbor node, directly deliver the data, skip other steps, and the algorithm terminates; if it is not a neighbor node, go to Step3;

Step3: Send price inquiry data packets to the neighbor nodes and wait for reply;

Step4: Receive the quoted prices and the history data forwarding success rates of neighbor nodes;

Step5: The data source node i calculates the posted price;

Step6: Determine the transaction price according to the posted price, quoted prices, and history data forwarding success rates;

Step7: Determine the data forwarding node and send the data;

Step8: The node which received the data repeats Step 2.

It should be noted that, in the Step 3 of the routing algorithm, the inquired node needs to exclude the “previous node”, which refers to the node that has sent the data to the current node in the previous routing step, and such design could effectively avoid the emergence of "routing loops".

4. Routing Algorithm Simulation Analysis

4.1 Simulation tool and scenario design

This study adopted ONE1.5 to conduct the simulation experiment of the routing algorithm. This software is a special software designed for DTN simulation. ONE [25] is an abbreviation of "Opportunistic Network Environment". The tool was developed by Ari Keränen, Jörg Ott and others of the Aalto University of Helsinki, Finland. The programming language is Java. At present, the tool is jointly maintained by researchers at the University of Aalto, Finland, and the Technical University of Munich, Germany. The software can be compiled and run on platforms such as Windows, Linux and MacOS.

The main simulation parameters of related simulation scenarios in this paper are shown in Table 1.

Table 1. Main simulation parameters




Communication rate



Node communication radius


The communication radius of the nodes

Node movement model


The movement model of the nodes

Node movement speed

3, 5

Movement speed per second

Node storage space


Storage space of the nodes

Data lifetime


The data packet lifetime is 120 minutes

Under such scenario, the routing model proposed in this paper was compared with the Epidemic routing algorithm and the FC (First Connection) routing algorithm.

4.2 Simulation results

4.2.1 Average time delay

In DTN, there are a large number of messages and their copies at the same time, so it’s quite meaningful to analyze the average time delay of the messages, so as to reflect the network status and performance more accurately. Figure 3 is a comparison of the average time delay of three routing models.

Figure 3. Average time delay of different routing models

As can be seen from the Figure 3 that the average time delay of the FC is the longest among the three routing models, it’s because the FC routing algorithm uses a single-copy mode to transmit the data, which reduces the data arrival probability, and increases the transmission time delay; The average time delay of the Epidemic routing model is the shortest, it’s because in an ideal network state, the epidemic routing method generates a large number of data copies, which reduces the average time delay of data transmission, but this method can easily cause network congestion; At the beginning of the simulation, the average time delay of the APRA was between the first two, its network time delay was slightly longer than that of the Epidemic routing model, but with the progress of the simulation time, the large number of copies of the Epidemic model gradually lowered the performance of the network and the average time delay increased; while the performance of APRA gradually tended to be stable, and outperformed the other two routing models in terms of time delay.

4.2.2 Network cost ratio

The network cost ratio refers to the proportion of the total amount of data that did not reach the target node successfully in the total amount of data that successfully reached the target node during various simulations. This ratio is generally used to reflect the overall transmission performance of the network. Figure 4 shows the network cost ratios of the three routing models during the simulation.

Figure 4. Network cost ratio of different routing models

It can be seen from the Figure 4 that the network cost ratio of APRA model was significantly lower than that of the Epidemic model, and it’s basically at the same level as the FC model. The goal of the proposed model is to improve network performance while saving network resources, the model won’t generate a large number of data copies or cause serious network congestion, so it has an ideal network cost ratio.

In summary, this section conducted a simulation experiment on APRA, the DTN routing algorithm proposed in this paper, and compared it with the Epidemic algorithm and the FC algorithm. APRA exhibited excellent performance, and it outperformed the other two algorithms in terms of comprehensive performance. It is a routing algorithm with balanced performance, and it achieved the original intention of the algorithm design: to find an economical, reliable and efficient transmission path.

5. Conclusion

This paper proposed a DTN routing algorithm based on the auction price game, the APRA, which converted the DTN forwarding node searching process to the auction price game process, it correlated the objects and behaviors in the routing process to the elements in the game, and found out a relatively economical data transmission path through the games between data sending nodes and data forwarding nodes; at the same time, it had effectively suppressed the “selfish” behavior of the nodes, and optimized the overall performance of the network; compared with Epidemic and FC algorithms, it could better save the network resources, and its routing performance is more balanced.


The Science and Technology Development Plan Project (20190302070GX) of Jilin Province of China; Science and Technology Project of Jilin province (20180414024GH); The 13th Five-Year Science and Technology Research Project of the Education Department of Jilin Province (JJKH20200793KJ).


[1] Fall, K. (2003). A delay-tolerant network architecture for challenged. Proceedings of the 2003 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications, pp. 27-34.

[2] Madoery, P.G., Fraire, J.A., Finochietto, J.M. (2018). Congestion management techniques for disruption-tolerant satellite networks. International Journal of Satellite Communications & Networking, 36(2): 165-178.

[3] Panagakis, A., Vaios, A., Stavrakakis, I. (2007). On the effects of cooperation in DTNs. Proceedings of the Second International Conference on Communication System software and Middleware, pp. 1-6. 2007.382571

[4] Dias, J.A., Rodrigues, J.J., Kumar, N., Saleem, K. (2015). Cooperation strategies for vehicular delay-tolerant networks. IEEE Communications Magazine, 53(12): 88-94.

[5] Manam, V.K.C., Mahendran, V., Murthy, C.S.R. (2014). Performance modeling of DTN routing with heterogeneous and selfish nodes. Wireless Networks, 20(1): 25-40. 013- 0583-z

[6] Matsuda, T., Takine, T. (2008). Epidemic routing for sparsely populated mobile ad hoc networks. IEEE Journal on Selected Areas in Communications, 26(5): 783-793.

[7] Akhtar, M.A.K., Sahoo, G. (2016). Enhancing cooperation in MANET using neighborhood compressive sensing model. Egyptian Informatics Journal.

[8] Mottaghinia, Z., Ghaffari, A. (2018). Fuzzy logic based distance and energy-aware routing protocol in delay-tolerant mobile sensor networks. Wireless Personal Communications, 100(3): 957-976. 018-5360-y

[9] Xu, M., Yang, Q., Kwak, K.S. (2016). Algebraic connectivity aided energy-efficient topology control in selfish ad hoc networks. Wireless Networks, 23(5): 1331-1341.

[10] Cho, J.H., Chen, I.R. (2018). PROVEST: Provenance-based trust model for delay tolerant networks. IEEE Transactions on Dependable & Secure Computing, 15(1): 151-165.

[11] Zhang, L., Zhang, X., An, C.J., Tang, C.J. (2014). A reputation-based incentive scheme for delay tolerant networks. Acta Electronica Sinica 42: 1738-1743. 0372-2112.2014.09.012

[12] Wu, F., Chen, T., Zhong, S., Qiao, C., Chen, G. (2013). A game-theoretic approach to stimulate cooperation for probabilistic routing in opportunistic networks. IEEE Transactions on Wireless Communications, 12(4): 1573-1583.

[13] Wang, R., Wu, Y.H., Huang, H.B., Deng, S. (2019). Cooperative transmission in delay tolerant network. Journal of Systems Engineering and Electronics, 30(1): 30-36.

[14] Chakrabarti, C., Banerjee, A., Chakrabarti, S., Chakraborty, A. (2015). A novel approach for non-cooperative node detection and avoidance using reputation-based scheme in mobile Ad hoc network. Lecture Notes in Electrical Engineering, 335: 279-289.

[15] Roughgarden, T. (2005). Selfish routing and the price of anarchy (Vol. 174). Cambridge: MIT Press.

[16] Benazir, S.A.M., Umarani, V. (2016). Detection of selfish & malicious behavior using DTN-chord monitoring in mobile networks. International Conference on Information Communication & Embedded Systems, pp. 1-5.

[17] Hao, W., Wei, W. (2018). A game theory based collaborative security detection method for internet of things systems. IEEE Transactions on Information Forensics & Security, 13(6): 1432-1445.

[18] Jain, S., Fall, K., Patra, R. (2004). Routing in a delay tolerant network. Proceedings of the 2004 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications, 34: 145-158.

[19] Chauhan, A., Lenzner, P., Melnichenko, A., Molitor, L. (2017). Selfish network creation with non-uniform edge cost. International Symposium on Algorithmic Game Theory, pp. 160-172.

[20] Rai, R., Rai, P. (2019). Survey on energy-efficient routing protocols in wireless sensor networks using game theory. In Advances in Communication, Cloud, and Big Data, Springer, Singapore, pp. 1-9.

[21] Roughgarden, T. (2020). Complexity theory, game theory, and economics: The Barbados lectures. Foundations and Trends® in Theoretical Computer Science, 14(3-4): 222-407. 

[22] Ayub, Q., Rashid, S. (2018). Resource refrain quota based routing protocol for delay tolerant network. Wireless Networks, 25(8): 4695-4704. 

[23] Reka, S.S., Ramesh, V. (2016). A demand response modeling for residential consumers in smart grid environment using game theory based energy scheduling algorithm. Ain Shams Engineering Journal, 7(2): 835-845.

[24] Liao, S.K., Cai, W.Q., Handsteiner, J., Liu, B., Yin, J., Zhang, L., Li, Y. (2018). Satellite-relayed intercontinental quantum network. Physical Review Letters, 120(3): 030501.

[25] Keränen, A., Ott, J., Kärkkäinen, T. (2009). The ONE simulator for DTN protocol evaluation. Proceedings of the 2nd International Conference on Simulation Tools and Techniques, pp. 1-10.