The DTN Routing Algorithm Based on Markov Meeting Time Span Prediction Model

Abstract

Putting forward an efficient routing algorithm in DTN (delay tolerant network) has become a focus of attention due to the existing phenomena that the connections between nodes in the network change dramatically over time and the communications suffer from frequent disruptions. In this paper, the meeting time span between nodes is predicted using the Markov model, and the relay node holding the shortest meeting time span with the destination node is determined as the most efficient node. In the two phases, spray phase and wait phase, the message is routed according to the utility value. Thus, the routing algorithm based on Markov meeting time span prediction model is provided. Simulation results suggest that this algorithm efficiently improves the delivery rate and reduces the average delay.

1. Introduction

DTN (delay tolerant network) [1] which is put forward by Fall at the international committee SIGCOMM in 2003 [2] is a kind of challenged network characterized by changing topology and lacking of stable links between terminates. End-to-end transmission latency may be arbitrarily long due to occasionally connected links [3, 4].

Examples of DTN are those operating in mobile or extreme scenarios such as interplanetary networks [5, 6], military networks [7], rural area networks [8], wildlife tracking sensor networks [9, 10], and pocket switched networks (PSNs) [11, 12]. Developing efficient routing protocols in this kind of network where topology changes dramatically has been a hot issue.

Generally, present routing protocols in DTN can be classified into two categories: copy-based routing [13] and efficiency-based routing [14]. Epidemic [15] is the basic copy-based routing protocol that exchanges messages in a simple way which seems like epidemic. Considering that the number of copies during its execution is out of control, this method will cost a lot of network resources: rubbish copies increase with the growth of time and finally lead to congestion.

To control the number of message copies, there comes a classical routing protocol based on quota: spray and wait [16, 17]. Several improvements have been made on it afterwards. Multiperiod spraying [18] extends the single spray phase into several spray phases, expecting efficient usage of network resources by infecting more nodes. Spray and focus [19] improves the wait phase. The message is routed through the node of the highest utility. Spray and forward [20] also improves the wait phase and calculates the meeting probability using the Markov location model. However, all the above methods only focus the improvements on one of the two phases, and spray and forward only considers the meeting possibility [21] at a specific place without considering the possible meeting on the way. To make up the above drawbacks, we propose a new DTN routing algorithm based on the Markov [22] meeting time span prediction model: predict and forward (PAF). The meeting time span is predicted using the Markov model, and the message is forwarded to the node of the highest utility. Experiments show that this method achieves higher delivery rate and lower average delay compared with epidemic or spray and wait routing protocols.

2. The DTN Routing Algorithm Based on Markov Meeting Time Span Prediction Model (PAF)

The main idea of PAF is as follows. Each node stores locally a multidimensional array which records the meeting time spans between the node and every other node. Then the general range of the next meeting time span is predicted from the previous time span using Markov model, and the highest utility value is endowed to the node holding the shortest meeting time span with the destination node. During both spray phase and wait phase, the message is forwarded to the node of the highest utility value.

2.1. The Meeting Time Span Prediction Model Based on Markov

In some DTNs where interested nodes exist, the meeting between nodes is not random. There are some regularities in the meeting time span. In our work, the previous meeting time spans are used to predict the general range of the next meeting time span by applying the Markov model and search for the efficient node which may be the earliest one to meet the destination node.

Set the meeting time span as a random variable X. The sequence $X_i$ forms a time-dispersed and state-dispersed Markov chain. For every two nodes in the network, record the meeting time span sequence $X_i$ , and map $X_i$ into one of the 5 states according to the following rules. When $\mathrm{0}<X_i\le \mathrm{100}$ , it is mapped to state 1. When $10\mathrm{0}<X_i\le \mathrm{200}$ , it is mapped to state 2. When $20\mathrm{0}<X_i\le \mathrm{500}$ , it is mapped to state 3. When $50\mathrm{0}<X_i\le \mathrm{1000}$ , it is mapped to state 4. When $10\mathrm{00}<X_i$ , it is mapped to state 5. So the meeting time spans of every two nodes can be described by a state sequence $a_i$ , which is consisted of states 1–5. According to the property of the Markov chain,

$$\begin{array}{l}P\left(X_n=a_n\mid X_{n-\mathrm{1}}=a_{n-\mathrm{1}},X_{n-\mathrm{2}}=a_{n-\mathrm{2}}\cdots X_{\mathrm{1}}=a_{\mathrm{1}}\right)\\ \hspace{1em}\hspace{1em}=P\left(X_n=a_n\mid X_{n-\mathrm{1}}=a_{n-\mathrm{1}}\right),\end{array}$$

(1)

where $X_i$ denotes the value of every meeting time span and $a_i$ denotes the state from 1 to 5. $X_i$ is collected by every node and stored as $a_i$ locally. When source node A meets a random node $B_i$ , the meeting time span sequences of these two nodes are updated, and then A gets the history meeting time span sequence between $B_i$ and the destination node stored at B. A state-transfer matrix P is created based on the previous sequence. Multiply the last state of the previous state sequence by P, and then the next meeting time span is predicted. The state-transfer matrix P is defined by

$$\begin{array}{cc}& P=\begin{array}{cc}& 1\hspace{1em}\hspace{0.5em}2\hspace{1em}\hspace{0.5em}3\hspace{1em}\hspace{0.5em}4\hspace{1em}\hspace{0.5em}5\\ \begin{array}{c}1\\ 2\\ 3\\ 4\\ 5\end{array}& \left(\begin{array}{ccccc}{P}_{11}& P_{12}& P_{13}& P_{14}& P_{15}\\ P_{21}& P_{22}& P_{23}& P_{24}& P_{25}\\ P_{31}& P_{32}& P_{33}& P_{34}& P_{35}\\ P_{41}& P_{42}& P_{43}& P_{44}& P_{45}\\ P_{51}& P_{52}& P_{53}& P_{54}& P_{55}\end{array}\right)\end{array},\end{array}$$

(2)

where $P_{ij}$ in transfer matrix denotes the transfer probability from state i to state j and

$$\begin{array}{cc}& {\sum }_{i=\mathrm{1}}^{\mathrm{5}}{P}_{ki}=\mathrm{1}\hspace{1em}\left(k=\mathrm{1,2},\mathrm{3,4},\mathrm{5}\right).\end{array}$$

(3)

For example, assuming that a sequence of the meeting time spans between node A and the destination node is 2, 1, 3, 2, 4, 5, 4, 1, 3, 2, 3, the state-transfer matrix is calculated as follows:

$$\begin{array}{cc}& P=\begin{array}{cc}& 1\hspace{1em}2\hspace{1em}\hspace{0.17em}\hspace{0.17em}3\hspace{1em}\hspace{0.5em}4\hspace{1em}\hspace{0.5em}5\\ \begin{array}{c}1\\ 2\\ 3\\ 4\\ 5\end{array}& \left(\begin{array}{ccccc}0& 0& 1& 0& 0\\ 1/3& 0& 1/3& 1/3& 0\\ 0& 1& 0& 0& 0\\ 1/2& 0& 0& 0& 1/2\\ 0& 0& 0& 1& 0\end{array}\right)\end{array}.\end{array}$$

(4)

Assuming that the current state is k, k denotes the state to which the meeting time span is mapped and corresponds to row k of matrix P. Search for the column with the highest probability in row k in the state-transfer matrix, and this column number is the next state we predict. Take matrix (4) for example. Supposing that the current state is 3, the highest probability in row 3 is 1, and it is located at column 2. So it is predicted that the next state is 2.

Based on the property of the Markov model, we can calculate the state $a_i$ to which the next meeting time span between node $B_i$ and the destination node should be mapped. The smaller $a_i$ is, the earlier the node will meet the destination node. However, there may be more than one node obtaining the smallest state. So it is necessary to determine which node the message will be forwarded to. To solve this problem, we adopt a two-step method, that is, taking the predicted state as an input and predicting again using the same state-transfer matrix. If there are still two or more nodes obtaining the smallest state, consider the last time the nodes meet the destination node, and choose the node with the earliest meeting time as the relay node. The sequence diagram describing this method is shown in Figure 1.

Figure 1

Sequence diagram of the prediction process using Markov model.

2.2. PAF Routing Algorithm

There exist some obvious disadvantages in the spray phase and wait phase of the classical spray and wait protocol. In spray phase, choosing a node randomly to spray may cause a problem: many messages will be sent to nodes with low efficiency. In the wait phase, waiting for the destination node negatively may miss the nodes which have higher meeting probabilities with the destination node.

PAF algorithm applies the Markov meeting time span prediction model in both the spray phase and wait phase. During the spray phase, this method tries to find the nodes, which may be the earliest one to meet the destination node within the communication range and performs binary spraying. Every node adopts the same spraying policy. When only one copy of the message is left, the node enters into the wait phase. During the wait phase, this method still tries to find the node which may be the earliest one to meet the destination node instead of waiting negatively, as shown in Figure 2. Thus, we provide the PAF routing method on the basis of the Markov meeting span prediction model.

Figure 2

The wait phase of our routing method.

3. Simulation Experiments

In this paper, we use the ONE (Opportunistic Network Environment simulator) to simulate the PAF routing method and evaluate the performance. The map of Helsinki city which is included in the ONE by default is used. There are three groups of nodes simulating the moving vehicles. Their moving speed is about 3 to 4 meters per second. The first group includes 40% of the total nodes and adopts the random-walking [23] model to simulate vehicles without a clear purpose. Interested nodes are added to the second group, so vehicles in this group tend to meet some other vehicles with a certain probability. This group simulates the vehicles keeping a specific habit. The ratio is about 30%. Nodes in the third group have fixed paths and are used to simulate buses on the road. The ratio is about 30% too.

In the scenario described above, we evaluate the performance of PAF routing algorithm in both delivery rate and average delay, then compare it with the classical epidemic and spray and wait routing protocols. Delivery rate and average delay are defined, respectively, as follows:

• (1)

  delivery rate

  $$\begin{array}{cc}& =\frac{{\sum }_i^{}\text{number of packets received by the node}\mathrm{\hspace{0.17em}\hspace{0.17em}}i}{{\sum }_i^{}\text{number of packets sent by the node}\mathrm{\hspace{0.17em}\hspace{0.17em}}i},\end{array}$$

  (5)

• (2)

  average delay

  $$\begin{array}{cc}& \hspace{1em}\hspace{1em}=\frac{{\sum }_i^{}{\sum }_j^{}\text{ETE delay of packet}\hspace{0.17em}j\hspace{0.17em}\text{received by the node}\mathrm{\hspace{0.17em}\hspace{0.17em}}i}{{\sum }_i^{}\text{number of packet received by the node}\mathrm{\hspace{0.17em}\hspace{0.17em}}i}.\end{array}$$

  (6)

Detailed configurations of the specific experimental parameters are given in Table 1.

Table 1

Values of specific experimental parameters.

Parameter	Value
Simulation time	5000 s
Simulation area	4000 m * 4000 m
Number of nodes	60, 80, 100, 120, 140
Moving speed	(3-4) m/s
Stay time	(0–120) s
Transmission speed	250 Kbps
Transmission range	50 m
Buffer size	40 MB
Interval of message generation	$[\mathit{5,15}]\hspace{0.17em}[\mathit{15,25}]\hspace{0.17em}[\mathit{25,35}]\hspace{0.17em}[\mathit{35,45}]$
TTL	300

3.1. Simulation Results and Analysis

Keeping the ratios of node groups unchanged, the total number of nodes is set to 60, 80, 100, 120, and 140, respectively. The message generation rate is 15 to 25 by default. Each node stores 4 message copies initially. The performance of epidemic, spray and wait, and PAF is simulated, and the results are plotted in Figure 3 (delivery rate) and Figure 4 (average delay).

Figure 3

Delivery rate for the three routing protocols under different number of nodes.

Figure 4

Average delay for the three routing protocols under different number of nodes.

As can be seen from Figure 3, the delivery rate of PAF is more than 20 percentage points higher than spray and wait, and more than 10 percentage points higher than epidemic. Because of the buffer limitation, epidemic does not achieve the desired performance. Furthermore, the gap in delivery rate increases and PAF obtains performance improvement as the number of nodes increases.

Figure 4 indicates that the average delay of PAF is less than epidemic and spray and wait under different number of nodes. Besides, the average delay of PAF is relatively stable, and there is no obvious fluctuation.

Set the total number of nodes to 100 and the initial number of message copies stored at each node to 4. Keeping the ratio of the three groups unchanged, we vary the message generation rate to 4 cases. The delivery rate (Figure 5) and average delay (Figure 6) of the three routing protocols are calculated.

Figure 5

Delivery rate for the three routing protocols under different message generation rates.

Figure 6

Average delay for the three routing protocols under different message generation rates.

By analyzing the data derived from Figures 5 and 6, it is easy to obtain the result that message generation rates do not influence the high performance of the PAF routing algorithm. Figure 5 shows that as the generation rate increases, the delivery rate of PAF increases obviously and much faster than the other two routing protocols. Figure 6 shows that the average delay of PAF stays in a low level without obvious fluctuation.

The number of nodes is set to 100 and the message generation rate is set to 15 to 25, just as we previously mentioned. The initial number of message copies is set to 2, 4, 6, and 8, respectively. Under different generation rates, delivery rate (Figure 7) and average delay (Figure 8) of the three routing protocols are obtained.

Figure 7

Delivery rate for the three routing protocols under different number of initial message copies.

Figure 8

Average delay for the three routing protocols under different number of initial copies.

It can be easily deduced from Figures 7 and 8 that PAF outperforms epidemic and spay and wait in both delivery rate and average delay when we vary the initial number of nodes.

4. Conclusion

In this paper, based on the classical routing protocol spray and wait, we have proposed the Markov meeting time span prediction model which can be used to predict the next meeting time span between a node and the destination node in both the spray phase and the wait phase. In spray phase, a node forwards half copies to the node that is predicted to be having the earliest meeting time with the destination node. In wait phase, instead of waiting negatively, the only message copy is forwarded to the node of the highest utility. The experiments suggest that this routing method could obviously increase the delivery rate and reduce the average delay. But because of the need for the local information of the nodes in contact, more connections are generated, thus more energy may be consumed. This is also reflected in our experiments, and exchanging energy for a high delivery rate and lower average delay is acceptable. Our future study mainly focuses on improving the performance of the routing method and reducing the energy consumption to a preferable threshold.