# Probabilistic Routing Based on Two-Hop Information in Delay/Disruption Tolerant Networks

Authors: Xu Wang; Rongxi He; Bin Lin; Ying Wang
Journal: Journal of Electrical and Computer Engineering
 (2015)

---

## Abstract

We investigate an opportunistic routing protocol in delay/disruption tolerant networks (DTNs) where the end-to-end path between source and destination nodes may not exist for most of the time. Probabilistic routing protocol using history of encounters and transitivity (PRoPHET) is an efficient history-based routing protocol specifically proposed for DTNs, which only utilizes the delivery predictability of one-hop neighbors to make a decision for message forwarding. In order to further improve the message delivery rate and to reduce the average overhead of PRoPHET, in this paper we propose an improved probabilistic routing algorithm (IPRA), where the history information of contacts for the immediate encounter and two-hop neighbors has been jointly used to make an informed decision for message forwarding. Based on the Opportunistic Networking Environment (ONE) simulator, the performance of IPRA has been evaluated via extensive simulations. The results show that IPRA can significantly improve the average delivery rate while achieving a better or comparable performance with respect to average overhead, average delay, and total energy consumption compared with the existing algorithms.


---

## Body

## 1. Introduction

Delay/disruption tolerant networks (DTNs) [1, 2] are one of the most interesting evolutions of mobile ad hoc networks (MANETs), in which an end-to-end path from the source to the destination may not exist at all times [3]. Routing is one of the key factors to affect the performance of a DTN. Due to the intermittent connectivity, traditional ad hoc routing protocols such as AODV and DSR are not appropriate for a DTN [3–5]. Therefore, it is imperative to develop new routing protocols specifically for DTNs.Depending on the nature of the network environment, there are different types of DTNs [5, 6], such as interplanetary networks [7], ZebraNet [8], DataMule [9], and village networks [10]. In the last few years, many research efforts have been focused on designing efficient routing protocols for DTNs. The work in [3–5] provided comprehensive surveys of routing protocols for DTNs. The authors of [6] introduced the research advancements in the topics of networking architecture and application designs, routing, multicasting, delay and buffer management, congestion and flow control, cooperative schemes, and mathematical modeling for DTNs.To cope with the intermittent connectivity, the mechanism of store-carry-forwarding [11] was introduced in the routing of DTNs; that is, when a node cannot immediately forward a message to a next-hop node, it buffers the message until it has a chance to send the message. The inherent behavior of DTNs is random and unknown in advance [11]. For such a stochastic network, flooding-based routing schemes were suggested to deliver messages. The simplest decision is to flood messages to all neighbors within a node’s communication range. Epidemic routing (ER) proposed in [11] is such a flooding-based protocol, in which whenever two nodes encounter, they replicate and exchange all different messages. A rigorous, unified framework was developed in [12] to investigate epidemic routing and its variations and to illustrate the differences among various forwarding and recovery schemes. ER has a high delivery rate and low latency under a scenario with infinite buffer size and network bandwidth, while its communication overhead is very high. However, the buffer size and network bandwidth are limited and even scarce resources in a DTN in most cases. In order to reduce the communication overhead and to lower the demand on buffer size and network bandwidth, Spray and Waiting routing protocol was proposed in [13, 14] for a DTN, which can reduce not only the total number of copies per message, but also the average delivery delay.Random waypoint mobility model [15] is a popular model that has been widely used to evaluate the routing performance in MANETs and DTNs. However, nodes are not likely to move around randomly in reality but rather move in a predictable fashion based on repeated behavioral patterns, especially if nodes represent human users [16]. The authors of [16, 17] investigated the routing policy for a DTN by considering the regularity of a node’s movement to improve the routing performance and proposed a history-based routing approach called PRoPHET, which utilized the history information of contacts between meeting nodes to make forwarding decision.In order to improve the performance of PRoPHET [16, 17] in terms of the amount of delivered messages to the destination, reducing the amount of aborted transmissions and lowering the buffer time, an improved PRoPHET routing protocol was introduced in [18] by implementing a predictability improved factor for the calculation of routing metric. Simulation results showed that the scheme can increase the number of messages delivered to the destination with less aborted transmissions.Based on the pioneering work of [16, 17], an updated version of PRoPHET called PRoPHETv2 was proposed in [19] to alleviate some potential issues of PRoPHET such as the parking lot problem; that is, there are instances when PRoPHET will produce inappropriate evolution of its delivery predictability if a group of nodes come together such as a number of users with DTN devices congregating in the supermarket parking lot and repeatedly exchange their sets of delivery predictability and to improve its performance by presenting some minor modifications to the calculations of routing metric done in [16, 17] while maintaining the original ideas. Simulation results showed that PRoPHETv2 had a better performance than the original PRoPHET, especially in cases of heterogeneous network mobility scenarios.The authors of [20] observed that the delivery predictabilities in PRoPHET [16, 17] for two nodes would increase rapidly or reduce suddenly when they encounter each other frequently or have no chance to meet in a while and called it as the problem of routing jitter. In order to tackle the problem, that is, to smooth the changing curve of delivery predictability value, an advanced PRoPHET protocol (denoted by PRoPHET-A in this paper) was proposed to solve it. The key idea is to introduce average delivery predictability of n encountered times to replace the original delivery predictability, which is helpful to smooth the change of the fluctuating probability value. The calculation of delivery predictability in [16, 17] was also amended accordingly. The simulation results showed that PRoPHET-A had a better performance than PRoPHET with respect to both average delay and message delivery rate.However, the aforementioned routing protocols only consider how to use the contact information of immediate encounters to calculate the delivery predictability and to choose a node with higher value for message forwarding. Actually, a node with smaller delivery predictability at a given time may encounter a node with very high delivery predictability to the destination in the future. If this node is selected as the forwarder, it is possible that the message has a higher delivery probability to the destination eventually. With this in mind, it is much better to choose an appropriate forwarder based on the two-hop information of delivery predictability for the increase of message delivery rate to the destinations.The main objective of this paper is to further improve the PRoPHET [16, 17] for a better average delivery rate and the reduction of its average overhead by utilizing the contact information of two-hop neighbors. We first propose a weighted forwarding metric for a node to choose a suitable forwarder, with a joint consideration of the history contact information of its immediate encounters and two-hop neighbors. And then, based on the weighted forwarding metric, an improved probabilistic routing algorithm (IPRA) is proposed. Our work differs from previous work [16–20] in that we consider not only the contact information of the immediate encounters, but also that of two-hop neighbors to make an informed decision for message forwarding. We compare IPRA with PRoPHET [16, 17] and its improved algorithms [19, 20] by extensive simulations based on the Opportunistic Networking Environment (ONE) simulator [21, 22], specifically designed for the evaluation of DTN routing and application protocol. Simulation results show that IPRA has the best performance of average delivery rate while achieving a better or comparable performance with respect to average overhead, average delay, and total energy consumption compared with the existing schemes in different conditions.The remainder of this paper is organized as follows. Section2 presents the network model and describes the intuition of IPRA by comparing its operation with PRoPHET. Section 3 describes the proposed algorithm. Simulation results are presented in Section 4. Conclusions are given in Section 5.


## 2. Network Model and Problem Statement

### 2.1. Network Model

Define a network topologyG(N,L) for a given DTN, where N is the set of mobile nodes and L is the set of links. Each node has a limited buffer size and moves in a predictable fashion based on repeated behavioral patterns. A node Ni in a DTN is called a neighbor (or contact) of node Nj only if it is currently in the communication range of Nj. For two neighbors, a link exists to represent the current connectivity between them. Due to mobility, failures, or other factors, a link in a DTN may go up or down over different time. When the link is up, the two nodes have an opportunity to exchange messages. In a DTN, routes are selected at each hop where messages are forwarded. Each node with a message exploits information of history contacts to choose a forwarder among its immediate encounters. If a forwarder is available, the message will be duplicated and forwarded to it for the transmission to the eventual destination. When no neighbor is suitable for message forwarding, the current node with the message buffers it and waits for future contact opportunities. If a message fails to be sent to its eventual destination during its lifetime, it will be discarded and removed from the buffer.


### 2.2. Problem Statement

In PRoPHET [16, 17], a delivery predictability metric pab  (pab∈[0,1]) was introduced to indicate the chance for node A to meet node B. The value of pab reflects how likely for node A to deliver a message to node B. When two nodes encounter, they exchange the information about the delivery predictabilities for known destinations and update the value based on
(1)pab=pab′+(1-pab′)×pi,
where pi∈(0,1] is an initialization value and pab′ is the previous value of pab before current update. Obviously, the more times two nodes encounter, the higher value of delivery predictability is. Two nodes that do not meet each other in a while are less likely to be good forwarders for the messages [16, 17]. The value of delivery predictability is reduced according to
(2)pab=pab′×γk,
where γ∈[0,1) is an aging constant and k is time units that have lapsed from the last time the metric was updated [17].In addition, when nodeA meets node B, node A also updates the delivery probability for each node known by node B in accordance with a transitive property specified as [16, 17]
(3)pac=pac′+(1-pac′)×pab×pbc×β,
where β∈[0,1] is a scaling constant to reflect the impact of the transitivity on the delivery predictability. In PRoPHET [16, 17], when two nodes A and B meet, they only compare the delivery predictability for the message from node A to the destination D and from node B to node D to determine whether to forward the message or not. A message is duplicated and sent to the other node only if the delivery predictability is higher at the other node.Due to the history contact information of one-hop neighbors being exploited in the aforementioned protocol, only the node with larger delivery predictability at the given time can be selected as the forwarder. However, the node with larger current delivery predictability may encounter nodes with very small delivery predictability to the destination or even meet no node in the future. If this node is picked as the forwarder, it is not guaranteed that the message has a higher delivery probability to the destination eventually. On the contrary, if a node with a relatively small value of immediate delivery predictability but with potential neighbors that have very high probability to meet the destination is selected as the forwarder, it is very likely that the message is eventually delivered to the destination with a higher probability. Therefore, it is much better to choose the forwarder with a joint consideration of the history contact information of immediate encounters and two-hop neighbors.Figure1 compares different routing algorithms by using one-hop information or two-hop information in a DTN, where node A carrying a message for the destination D meets node B. The values of immediate delivery predictability from A to D and from B to D are pad=0.4 and pbd=0.2, respectively. According to PRoPHET [16, 17], the message will still be carried by node A due to its higher probability to meet node D than that of node B as denoted in Figure 1(a). However, in the near future, node B will meet node E which has a very high delivery predictability to node D; that is, ped=0.8, while node A will meet no node. The delivery predictability from node B to node D via node E, that is, pbed=0.48, is higher than pad, which can be calculated by using (4) specified in the following section. Accordingly, if node A forwards the message to node B, it is very possible that the message has a higher delivery probability to node D eventually. As shown in Figure 1(b), owing to pbed>pad, node A shall replicate the message and forward it to node B.Comparison of different routing algorithms for message forwarding in a DTN wherepad>pbd and pbed>pad. (a) PRoPHET in [16, 17], where node A continues to carry the message. (b) Probabilistic routing based on two-hop neighbors’ information, where node B is selected as the forwarder to carry the message.
(a)
(b)


## 2.1. Network Model

Define a network topologyG(N,L) for a given DTN, where N is the set of mobile nodes and L is the set of links. Each node has a limited buffer size and moves in a predictable fashion based on repeated behavioral patterns. A node Ni in a DTN is called a neighbor (or contact) of node Nj only if it is currently in the communication range of Nj. For two neighbors, a link exists to represent the current connectivity between them. Due to mobility, failures, or other factors, a link in a DTN may go up or down over different time. When the link is up, the two nodes have an opportunity to exchange messages. In a DTN, routes are selected at each hop where messages are forwarded. Each node with a message exploits information of history contacts to choose a forwarder among its immediate encounters. If a forwarder is available, the message will be duplicated and forwarded to it for the transmission to the eventual destination. When no neighbor is suitable for message forwarding, the current node with the message buffers it and waits for future contact opportunities. If a message fails to be sent to its eventual destination during its lifetime, it will be discarded and removed from the buffer.


## 2.2. Problem Statement

In PRoPHET [16, 17], a delivery predictability metric pab  (pab∈[0,1]) was introduced to indicate the chance for node A to meet node B. The value of pab reflects how likely for node A to deliver a message to node B. When two nodes encounter, they exchange the information about the delivery predictabilities for known destinations and update the value based on
(1)pab=pab′+(1-pab′)×pi,
where pi∈(0,1] is an initialization value and pab′ is the previous value of pab before current update. Obviously, the more times two nodes encounter, the higher value of delivery predictability is. Two nodes that do not meet each other in a while are less likely to be good forwarders for the messages [16, 17]. The value of delivery predictability is reduced according to
(2)pab=pab′×γk,
where γ∈[0,1) is an aging constant and k is time units that have lapsed from the last time the metric was updated [17].In addition, when nodeA meets node B, node A also updates the delivery probability for each node known by node B in accordance with a transitive property specified as [16, 17]
(3)pac=pac′+(1-pac′)×pab×pbc×β,
where β∈[0,1] is a scaling constant to reflect the impact of the transitivity on the delivery predictability. In PRoPHET [16, 17], when two nodes A and B meet, they only compare the delivery predictability for the message from node A to the destination D and from node B to node D to determine whether to forward the message or not. A message is duplicated and sent to the other node only if the delivery predictability is higher at the other node.Due to the history contact information of one-hop neighbors being exploited in the aforementioned protocol, only the node with larger delivery predictability at the given time can be selected as the forwarder. However, the node with larger current delivery predictability may encounter nodes with very small delivery predictability to the destination or even meet no node in the future. If this node is picked as the forwarder, it is not guaranteed that the message has a higher delivery probability to the destination eventually. On the contrary, if a node with a relatively small value of immediate delivery predictability but with potential neighbors that have very high probability to meet the destination is selected as the forwarder, it is very likely that the message is eventually delivered to the destination with a higher probability. Therefore, it is much better to choose the forwarder with a joint consideration of the history contact information of immediate encounters and two-hop neighbors.Figure1 compares different routing algorithms by using one-hop information or two-hop information in a DTN, where node A carrying a message for the destination D meets node B. The values of immediate delivery predictability from A to D and from B to D are pad=0.4 and pbd=0.2, respectively. According to PRoPHET [16, 17], the message will still be carried by node A due to its higher probability to meet node D than that of node B as denoted in Figure 1(a). However, in the near future, node B will meet node E which has a very high delivery predictability to node D; that is, ped=0.8, while node A will meet no node. The delivery predictability from node B to node D via node E, that is, pbed=0.48, is higher than pad, which can be calculated by using (4) specified in the following section. Accordingly, if node A forwards the message to node B, it is very possible that the message has a higher delivery probability to node D eventually. As shown in Figure 1(b), owing to pbed>pad, node A shall replicate the message and forward it to node B.Comparison of different routing algorithms for message forwarding in a DTN wherepad>pbd and pbed>pad. (a) PRoPHET in [16, 17], where node A continues to carry the message. (b) Probabilistic routing based on two-hop neighbors’ information, where node B is selected as the forwarder to carry the message.
(a)
(b)


## 3. Description of the Proposed Algorithm

The critical issue addressed in this paper is how to select a forwarder with the objectives to improve the message delivery ratio and to reduce communication overhead for a DTN. The original PRoPHET [16, 17] makes a decision whether or not to forward the message based on the history contact information of a node’s immediate encounters, that is, one-hop information. Although quite a few algorithms have been proposed to improve the performance of PRoPHET, most of them mainly focus on the optimization of the formula for the calculation of delivery predictability only with a consideration of one-hop information. Based on the issues discussed in the previous section, we will describe some improvements to the forwarder selection mechanism of PRoPHET by utilizing two-hop neighbors’ information and finally propose an improved probabilistic routing algorithm (IPRA). Before describing the proposed algorithm, following notations are introduced:Sa, the set of nodes for which node A has information records of history contacts. That is, node A may meet these nodes with different probability;padw, the weighted forwarding metric for node A to be selected as a forwarder to send the message to node D. A big value of padw means that node A is more suitable to act as the forwarder;pad, the delivery predictability from node A to node D, which can be calculated according to (1), (2), and (3);pbed, the delivery predictability from node B to node D via node E, which can be calculated as
(4)pbed=pbe×ped.In PRoPHET [16, 17], due to only one-hop information of immediate encounters being utilized, node A currently carrying the message may miss a chance to select node B with lower pad while having a potential neighbor with very high probability to meet the destination D as the forwarder as depicted in Figure 1(a). Actually, if node B is chosen as the forwarder, it is very helpful to successfully deliver the message to the destination. In our proposed IPRA, two-hop information has been taken into account to calculate the nodes’ weighted forwarding metric and to determine the forwarder selection, which is depicted in Figure 2. In Figure 2, node A with a message for the destination node D meets node B and pad=0.35 and pbd=0.3. We assume that the sets of encounters for node A and node B are Sa={A1,A2,A3,…,Am} and Sb={B1,B2,B3,…,Bn}, respectively. When node A meets node B, that is, B is within the communication range of A, the two nodes first exchange history information of contacts and compute their individual weighted forwarding metric padw and pbdw as
(5)padw=pad+∑Ak∈SA,k=1,2,…,mpaakd,pbdw=pbd+∑Bk∈SB,k=1,2,…,npbbkd.Figure 2
Two encountering nodes and their sets of nodes being encountered potentially in a DTN wherepad>pbd and pbdw>padw.And then, nodeA compares its weighted forwarding metric with node B to decide whether or not to duplicate the message and deliver it to node B according to the comparison result of padw and pbdw. If padw≥pbdw, node A will continue to carry the message; otherwise, it shall replicate the message and forward it to node B.Node setsSa or Sb may have many members, in which the node with smaller delivery predictability has a little contribution to the value of padw or pbdw. In order to reduce the burden of computations, a threshold α(0<α<1) is introduced to exclude node Ak with paakd≤α from Sa and node Bk with pbbkd≤α from Sb in (5). For example, with an assumption that α=0.3 in Figure 2, nodes A2 and Bn will be excluded from Sa and Sb for the calculation of padw and pbdw, since paa2d=0.15 and pbbnd=0.24. According to (5), we can obtain the values of padw and pbdw; that is, padw=1.02 and pbdw=1.06, respectively. Therefore, node B shall be selected as the forwarder to carry the message as denoted in Figure 2.Algorithm1 shows the pseudocodes of message transmission in IPRA when node A meets node B. Its complexity is mainly determined by the procedure of comparison operations and adjustments of the weighted forwarding metric and the delivery predictability. It is approximately O(N2), where N is the number of destinations.Algorithm 1:The message transmission when node A with a message for the destination D encounters node B.
for  nodes A and B  do
Drop the message with an expired lifetime;
Exchange history information of contacts;
Update delivery predictability according to (1)–(3);
Calculatepadw and pbdw according to (5);
end
if  padw≥pbdw  then
NodeA continue to carry the message;
end
else
NodeA replicates the message and forwards it to node B;
NodeB check its buffer space;
if its buffer being full with the received message then
Drop a message in its buffer according to FIFO queue;
end
NodeB carry the message;
end


## 4. Simulation Results and Analysis

In this section, we conduct extensive simulations based on the ONE simulator [21, 22], which is specifically designed for evaluating DTN routing and application protocol. Our goal is to compare the performance of IPRA with original PRoPHET [16, 17] and its two improved algorithms, that is, PRoPHETv2 [19] and PRoPHET-A [20].


### 4.1. Simulation Scenario

The simulation scenario is taken from a real map of Helsinki downtown area covering a 4500 m × 3400 m region with different numbers of nodes [20–22], which is developed by the University of Helsinki to investigate the Opportunistic Networks in real life. The map information includes streets, shops, parks, bus stops, and trams of Helsinki. All nodes are divided into 6 groups. A node group has a common set of simulation parameters like moving speed and pause time distribution, data transmission rate, message buffer size, and communication range [20]. In the scenario, Group 1 and Group 3 are pedestrian groups; Group 2 is automobile group; Group 4, Group 5, and Group 6 are trolleybus groups. The pedestrians and cars randomly choose destinations in their reach on the map and follow the shortest path to the destination. The trolleybuses follow predetermined routes to match trolleybus routes [21, 22]. With the exception of Group 4, other groups use Bluetooth devices. IEEE 802.11b WLAN devices have been used by Group 4. The detailed parameters for each group are given in Table 1. The source and destination for each message are randomly chosen from all nodes. The message size varies from 500 kB to 1 MB, and the message lifetime is set to 18000 seconds. The duration of simulation is 43200 seconds. The work of [17] indicated that pi=0.75, γ=0.98, and β=0.25 were reasonable choices for the simulation parameters of PRoPHET. In order to compare our algorithm with PRoPHET under the same simulation setting, the same value for pi, γ, and β is also set in our simulations. In the beginning of the simulations, a warm-up period of 1000 seconds is used to initialize the delivery predictability. All the results presented here are averages from 5 simulation runs using different random seeds.Table 1
Parameters for nodes in different groups.
Groups
Parameters
Moving speed (m/s)
Pause time (s)
Communication range (m)
Data rate(KBps)
Buffer size (MB)
1 and 3
0.5–1.5
0–120
10
250
5
2
2.7–13.9
0–120
10
250
5
4
7–10
10–30
300
10000
50
5 and 6
7–10
10–30
10
250
50


### 4.2. Performance Evaluation

We have compared the performance with respect to average delivery rate (ADR), average overhead (AO), and average delay (AD). ADR is the probability of the messages being received correctly by the destination within a given period of time. AO refers to the average number of copies for a message to be successfully delivered to its destination, which is defined as(6)AO=nc-ndnd,
where nc is the total number of message copies during the simulation and nd is the total number of successfully received messages. AD is the average value of the difference between the time for the message being created and the time for the message to be delivered to the destination [21, 22].We first investigate the effect ofα to the performance of IPRA by changing its value from 0.1 to 0.9. The total number of nodes is 126, that is, each of the first three groups and the others including 40 nodes and 2 nodes, respectively. Other parameters are the same as Table 1. The simulation results are shown in Figure 3. The simulation results for the other three algorithms have also been given in Figure 3. Since all of them are not involved in the parameter of α, there is no change under different values of α.The performance of IPRA with different values ofα: (a) average delivery rate (ADR); (b) average overhead (AO); (c) average delay (AD).
(a)
(b)
(c)It can be seen from Figure3 that the value of α has a great impact on the performance of IPRA. With an increase of α, the performance of IPRA is gradually close to that of PRoPHET. In detail, the AO of IPRA is increased monotonically, and the ADR and AD of IPRA are decreased gradually. The main reason is that with a bigger value of α, more nodes are excluded from Sa and Sb. Accordingly, a smaller number of candidates are available for the forwarder selection of node A and node B, which reduces the chance to pick out a more suitable node for message forwarding. Potentially, it may reduce the delivery ratio. In the extreme case with α=1.0, no node is included in Sa and Sb. Therefore, no two-hop information can be used by IPRA to select forwarders. In this case, IPRA is almost the same as PRoPHET. Another observation from Figure 3 is that with α being less than 0.7, IPRA has the biggest ADR among the four algorithms while it has a lower AO than PRoPHETv2 and a slight increase of AO and AD compared with PRoPHET-A. In general, smaller value of α is better for the ADR improvement of IPRA. However, smaller α means that more nodes are included in Sa and Sb. Then more computations are required for nodes to choose forwarders. In order to keep an affordable computation burden and to achieve a considerable performance gain, α=0.3–0.4 is a reasonable choice. It is a slight improvement for the performance of IPRA to continue reducing the value of α; on the contrary, more additional computations are introduced. In the following simulations, we set α=0.3.We evaluate the performance of the four algorithms under different number of nodes by changing the number of nodes in Group 1, Group 2, and Group 3 from 10 to 60 and keeping the number of nodes in Group 4, Group 5, and Group 6 to be 2. Other parameters are the same as Table1. The simulation results are shown in Figures 4–6.Figure 4
Average delivery rate (ADR) versus number of nodes.Figure 5
Average overhead (AO) versus number of nodes.Figure 6
Average delay (AD) versus number of nodes.Figure4 shows the performance of the four algorithms in terms of average delivery rate for different number of nodes. We can observe that the proposed IPRA algorithm outperforms other counterparts, followed by PRoPHET-A, PRoPHETv2, and PRoPHET in sequence. The reason is that compared with the other three algorithms, IPRA not only considers the delivery predictability of immediate encounters but also combines the two-hop neighbors’ information to pick a more suitable forwarder. It is very helpful to select the nodes with high chance to meet the destination for message forwarding. Potentially, it can improve the delivery ratio.Figure5 compares the performance of the four algorithms in terms of average overhead for different number of nodes. It is clear to see that the average overhead grows with the increase of the number of nodes. As more nodes are introduced, the probability for two nodes to meet each other is also increased, which is beneficial to pick a more suitable forwarder, resulting in more copies in the network and the increase of AO. Another observation from Figure 5 is that, with a small number of nodes, the AO value of IPRA is very close to that of PRoPHET-A; with a large number of nodes, the AO value of IPRA is higher than that of PRoPHET-A but is still much lower than that of PRoPHETv2 and PRoPHET. The main reason is that, with a large number of nodes, higher probability to select a more suitable forwarder is achieved by our proposed algorithm, which is useful to increase the delivery ratio while duplicating the messages more times.Figure6 compares the performance of the four algorithms in terms of average delay. They almost achieve the same performance, only with a slight difference for average delay. In detail, IPRA has a little larger AD than others. The main reason is that the other three algorithms only choose the nodes with higher direct delivery predictability to forward messages. With two-hop information, IPRA increases the probability for two nodes to exchange messages; and more messages are delivered to the destination. These extra delivered messages are messages that were discarded in the three one-hop information based algorithms but are now able to be delivered to their destinations during its lifetime due to more suitable forwarders being selected by IPRA. Consequently, a longer delay may be incurred for these messages.In order to investigate the effect of the limited buffer size of nodes to the proposed IPRA algorithm, we ran a series of simulations by changing the buffer size of nodes in Group 1, Group 2, and Group 3 from 3 MB to 10 MB and keeping the buffer size of nodes in Group 4, Group 5, and Group 6 to be 50 MB. The total number of nodes is 126, that is, each of the first three groups and the others including 40 nodes and 2 nodes, respectively. Other parameters are the same as Table1. The simulation results are shown in Figures 7–9.Figure 7
Average delivery rate (ADR) versus buffer size.Figure 8
Average overhead (AO) versus buffer size.Figure 9
Average delay (AD) versus buffer size.Figure7 compares the performance of the four algorithms in terms of ADR for different buffer sizes. It can be seen that buffer size has a profound impact on ADR performance. In all algorithms, ADR is found to increase monotonically with an increase of buffer size. The reason for this is that a larger buffer size means that more messages can be buffered and the risk of message overflow decreases. Correspondingly, a higher chance to eventually deliver messages to the destinations can be achieved. Another observation from Figure 7 is that the IPRA protocol yields the best ADR and PRoPHET the worst, with PRoPHETv2 and PRoPHET-A falling in between. And there is only a slight difference between PRoPHETv2 and PRoPHET-A. In addition, with an increase of buffer size, there is a significant improvement for IPRA compared with other algorithms. This is probably due to the fact that, with a larger buffer size, more messages can be carried by nodes. With the efficient forwarder selection strategy, IPRA has a higher probability to pick an appropriate forwarder that has a high chance to eventually encounter the destination and to deliver messages to the destination during their lifetime.Figure8 shows the performance of the four algorithms in terms of AO against different buffer sizes. It is easy to see that considerable overhead reduction can be achieved by IPRA compared with PRoPHET and PRoPHETv2, no matter what is the buffer size. It seems that increasing the buffer size has a subtle effect to AO for message delivery.Figure9 shows the performance of the four algorithms in terms of AD when we have different buffer sizes. Also there is no obvious difference between IPRA and the other three algorithms for different buffer sizes. IPRA has a slightly larger average delay than other algorithms because more messages being dropped by other algorithms have been eventually delivered to the destination by IPRA before the end of lifetime and may lead to a longer delay.In order to investigate the effect of the message lifetime to the performance of IPRA, we also ran a series of simulations by changing the message lifetime from 180 minutes to 480 minutes and keeping the total number of nodes 126. Other parameters are the same as Table1. The simulation results are shown in Figures 10–12.Figure 10
Average delivery rate (ADR) versus message lifetime.Figure 11
Average overhead (AO) versus message lifetime.Figure 12
Average delay (AD) versus message lifetime.Figure10 compares the performance of the four algorithms in terms of ADR under different message lifetime. It can be seen that message lifetime has a slight impact on ADR performance. With a bigger value of message lifetime, each node can keep the messages for a longer time and has a higher chance to encounter more suitable forwarders, which seemed to be helpful for the increase of delivery ratio. However, each node with limited buffer size can only carry a limited number of messages. When its buffer is full, the message will be dropped even if its lifetime is not expired. Therefore, a big value of message lifetime does not always mean a high delivery ratio. Another observation from Figure 10 is that IPRA yields the best ADR and PRoPHET the worst, with PRoPHETv2 and PRoPHET-A falling in between. And there is only a slight difference between PRoPHETv2 and PRoPHET-A.Figure11 shows the performance of the four algorithms in terms of AO against different message lifetime. It is clear to see that considerable overhead reduction can be achieved by IPRA compared with PRoPHET and PRoPHETv2, no matter what is the message lifetime. It seems that increasing the message lifetime has a subtle effect to AO for message delivery.Figure12 shows the performance of the four algorithms in terms of AD with different message lifetime. Also there is no obvious difference between IPRA and the other three algorithms for different message lifetime.In order to further evaluate the performance of IPRA, more simulations are run under three different scenarios (small, medium, and large scenarios) taken from the real map of Helsinki downtown area covering 4500 m × 3400 m, 5400 m × 4300 m, and 8300 m × 7300 m regions, respectively. For the small scenario, the number of nodes in each group is 5, 10, 5, 2, 2, and 2. The buffer size for Group 1 and Group 3 is 10 MB; and the communication range for Group 4 is 250 m. For the medium scenario, the number of nodes in each group is 100, 100, 100, 4, 2, and 4. The buffer size for Group 1 and Group 3 is 10 MB. For the large scenario, each of the first three groups and the others include 100 nodes and 5 nodes. The buffer size for Group 1 and Group 3 is 15 MB. For the three scenarios, the buffer size for Group 2, Group 4, Group 5, and Group 6 is 50 MB; and other parameters are the same as Table1. The simulation results are shown in Figures 13–15.Figure 13
Average delivery rate (ADR) under different scenarios.Figure 14
Average overhead (AO) under different scenarios.Figure 15
Average delay (AD) under different scenarios.From Figures13–15, we can observe that, for the small case, there is no oblivious difference between the four algorithms. However, there is a large gap between IPRA and the other three algorithms in terms of ADR in the medium and large scenarios, since more and more nodes are included in the scenarios. In the medium and large scenarios, the AO value of IPRA is slightly higher than that of PRoPHET-A but is still lower than that of PRoPHET and PRoPHETv2. IPRA has the lowest value of AD compared with the other three algorithms in the medium and large scenarios.Finally, in order to investigate the extra overhead introduced by IPRA with two-hop information, we investigate the total energy consumption (TEC) for message transmissions during the simulation time for the four algorithms under different scenarios covering a 4500 m × 3400 m region of Helsinki downtown area with different number of nodes (keeping buffer size 5 MB and message lifetime 5 h), different buffer size (126 nodes and 5 h lifetime), or different message lifetime (126 nodes and 5 MB buffer size), respectively. Other parameters are the same as Table1. More energy consumptions mean more message transmissions and more overhead. We assume that the average energy consumption for one message transmission is one unit. The simulation results are shown in Figures 16–18.Figure 16
Total energy consumption (TEC) versus number of nodes.Figure 17
Total energy consumption (TEC) versus buffer size.Figure 18
Total energy consumption (TEC) versus message lifetime.From Figures16–18, we can observe that PRoPHET-A performs best and PRoPHET the worst, followed by PRoPHETv2 and IPRA in sequence. IPRA almost achieves the same TEC performance with PRoPHETv2, only with a little larger TEC than it. The main reason is that, with the efficient forwarder selection strategy, IPRA has a higher probability to pick an appropriate forwarder, resulting in more message copies in the network. Potentially, it may improve the delivery ratio while transmitting more messages and consuming more energy.


## 4.1. Simulation Scenario

The simulation scenario is taken from a real map of Helsinki downtown area covering a 4500 m × 3400 m region with different numbers of nodes [20–22], which is developed by the University of Helsinki to investigate the Opportunistic Networks in real life. The map information includes streets, shops, parks, bus stops, and trams of Helsinki. All nodes are divided into 6 groups. A node group has a common set of simulation parameters like moving speed and pause time distribution, data transmission rate, message buffer size, and communication range [20]. In the scenario, Group 1 and Group 3 are pedestrian groups; Group 2 is automobile group; Group 4, Group 5, and Group 6 are trolleybus groups. The pedestrians and cars randomly choose destinations in their reach on the map and follow the shortest path to the destination. The trolleybuses follow predetermined routes to match trolleybus routes [21, 22]. With the exception of Group 4, other groups use Bluetooth devices. IEEE 802.11b WLAN devices have been used by Group 4. The detailed parameters for each group are given in Table 1. The source and destination for each message are randomly chosen from all nodes. The message size varies from 500 kB to 1 MB, and the message lifetime is set to 18000 seconds. The duration of simulation is 43200 seconds. The work of [17] indicated that pi=0.75, γ=0.98, and β=0.25 were reasonable choices for the simulation parameters of PRoPHET. In order to compare our algorithm with PRoPHET under the same simulation setting, the same value for pi, γ, and β is also set in our simulations. In the beginning of the simulations, a warm-up period of 1000 seconds is used to initialize the delivery predictability. All the results presented here are averages from 5 simulation runs using different random seeds.Table 1
Parameters for nodes in different groups.
Groups
Parameters
Moving speed (m/s)
Pause time (s)
Communication range (m)
Data rate(KBps)
Buffer size (MB)
1 and 3
0.5–1.5
0–120
10
250
5
2
2.7–13.9
0–120
10
250
5
4
7–10
10–30
300
10000
50
5 and 6
7–10
10–30
10
250
50


## 4.2. Performance Evaluation

We have compared the performance with respect to average delivery rate (ADR), average overhead (AO), and average delay (AD). ADR is the probability of the messages being received correctly by the destination within a given period of time. AO refers to the average number of copies for a message to be successfully delivered to its destination, which is defined as(6)AO=nc-ndnd,
where nc is the total number of message copies during the simulation and nd is the total number of successfully received messages. AD is the average value of the difference between the time for the message being created and the time for the message to be delivered to the destination [21, 22].We first investigate the effect ofα to the performance of IPRA by changing its value from 0.1 to 0.9. The total number of nodes is 126, that is, each of the first three groups and the others including 40 nodes and 2 nodes, respectively. Other parameters are the same as Table 1. The simulation results are shown in Figure 3. The simulation results for the other three algorithms have also been given in Figure 3. Since all of them are not involved in the parameter of α, there is no change under different values of α.The performance of IPRA with different values ofα: (a) average delivery rate (ADR); (b) average overhead (AO); (c) average delay (AD).
(a)
(b)
(c)It can be seen from Figure3 that the value of α has a great impact on the performance of IPRA. With an increase of α, the performance of IPRA is gradually close to that of PRoPHET. In detail, the AO of IPRA is increased monotonically, and the ADR and AD of IPRA are decreased gradually. The main reason is that with a bigger value of α, more nodes are excluded from Sa and Sb. Accordingly, a smaller number of candidates are available for the forwarder selection of node A and node B, which reduces the chance to pick out a more suitable node for message forwarding. Potentially, it may reduce the delivery ratio. In the extreme case with α=1.0, no node is included in Sa and Sb. Therefore, no two-hop information can be used by IPRA to select forwarders. In this case, IPRA is almost the same as PRoPHET. Another observation from Figure 3 is that with α being less than 0.7, IPRA has the biggest ADR among the four algorithms while it has a lower AO than PRoPHETv2 and a slight increase of AO and AD compared with PRoPHET-A. In general, smaller value of α is better for the ADR improvement of IPRA. However, smaller α means that more nodes are included in Sa and Sb. Then more computations are required for nodes to choose forwarders. In order to keep an affordable computation burden and to achieve a considerable performance gain, α=0.3–0.4 is a reasonable choice. It is a slight improvement for the performance of IPRA to continue reducing the value of α; on the contrary, more additional computations are introduced. In the following simulations, we set α=0.3.We evaluate the performance of the four algorithms under different number of nodes by changing the number of nodes in Group 1, Group 2, and Group 3 from 10 to 60 and keeping the number of nodes in Group 4, Group 5, and Group 6 to be 2. Other parameters are the same as Table1. The simulation results are shown in Figures 4–6.Figure 4
Average delivery rate (ADR) versus number of nodes.Figure 5
Average overhead (AO) versus number of nodes.Figure 6
Average delay (AD) versus number of nodes.Figure4 shows the performance of the four algorithms in terms of average delivery rate for different number of nodes. We can observe that the proposed IPRA algorithm outperforms other counterparts, followed by PRoPHET-A, PRoPHETv2, and PRoPHET in sequence. The reason is that compared with the other three algorithms, IPRA not only considers the delivery predictability of immediate encounters but also combines the two-hop neighbors’ information to pick a more suitable forwarder. It is very helpful to select the nodes with high chance to meet the destination for message forwarding. Potentially, it can improve the delivery ratio.Figure5 compares the performance of the four algorithms in terms of average overhead for different number of nodes. It is clear to see that the average overhead grows with the increase of the number of nodes. As more nodes are introduced, the probability for two nodes to meet each other is also increased, which is beneficial to pick a more suitable forwarder, resulting in more copies in the network and the increase of AO. Another observation from Figure 5 is that, with a small number of nodes, the AO value of IPRA is very close to that of PRoPHET-A; with a large number of nodes, the AO value of IPRA is higher than that of PRoPHET-A but is still much lower than that of PRoPHETv2 and PRoPHET. The main reason is that, with a large number of nodes, higher probability to select a more suitable forwarder is achieved by our proposed algorithm, which is useful to increase the delivery ratio while duplicating the messages more times.Figure6 compares the performance of the four algorithms in terms of average delay. They almost achieve the same performance, only with a slight difference for average delay. In detail, IPRA has a little larger AD than others. The main reason is that the other three algorithms only choose the nodes with higher direct delivery predictability to forward messages. With two-hop information, IPRA increases the probability for two nodes to exchange messages; and more messages are delivered to the destination. These extra delivered messages are messages that were discarded in the three one-hop information based algorithms but are now able to be delivered to their destinations during its lifetime due to more suitable forwarders being selected by IPRA. Consequently, a longer delay may be incurred for these messages.In order to investigate the effect of the limited buffer size of nodes to the proposed IPRA algorithm, we ran a series of simulations by changing the buffer size of nodes in Group 1, Group 2, and Group 3 from 3 MB to 10 MB and keeping the buffer size of nodes in Group 4, Group 5, and Group 6 to be 50 MB. The total number of nodes is 126, that is, each of the first three groups and the others including 40 nodes and 2 nodes, respectively. Other parameters are the same as Table1. The simulation results are shown in Figures 7–9.Figure 7
Average delivery rate (ADR) versus buffer size.Figure 8
Average overhead (AO) versus buffer size.Figure 9
Average delay (AD) versus buffer size.Figure7 compares the performance of the four algorithms in terms of ADR for different buffer sizes. It can be seen that buffer size has a profound impact on ADR performance. In all algorithms, ADR is found to increase monotonically with an increase of buffer size. The reason for this is that a larger buffer size means that more messages can be buffered and the risk of message overflow decreases. Correspondingly, a higher chance to eventually deliver messages to the destinations can be achieved. Another observation from Figure 7 is that the IPRA protocol yields the best ADR and PRoPHET the worst, with PRoPHETv2 and PRoPHET-A falling in between. And there is only a slight difference between PRoPHETv2 and PRoPHET-A. In addition, with an increase of buffer size, there is a significant improvement for IPRA compared with other algorithms. This is probably due to the fact that, with a larger buffer size, more messages can be carried by nodes. With the efficient forwarder selection strategy, IPRA has a higher probability to pick an appropriate forwarder that has a high chance to eventually encounter the destination and to deliver messages to the destination during their lifetime.Figure8 shows the performance of the four algorithms in terms of AO against different buffer sizes. It is easy to see that considerable overhead reduction can be achieved by IPRA compared with PRoPHET and PRoPHETv2, no matter what is the buffer size. It seems that increasing the buffer size has a subtle effect to AO for message delivery.Figure9 shows the performance of the four algorithms in terms of AD when we have different buffer sizes. Also there is no obvious difference between IPRA and the other three algorithms for different buffer sizes. IPRA has a slightly larger average delay than other algorithms because more messages being dropped by other algorithms have been eventually delivered to the destination by IPRA before the end of lifetime and may lead to a longer delay.In order to investigate the effect of the message lifetime to the performance of IPRA, we also ran a series of simulations by changing the message lifetime from 180 minutes to 480 minutes and keeping the total number of nodes 126. Other parameters are the same as Table1. The simulation results are shown in Figures 10–12.Figure 10
Average delivery rate (ADR) versus message lifetime.Figure 11
Average overhead (AO) versus message lifetime.Figure 12
Average delay (AD) versus message lifetime.Figure10 compares the performance of the four algorithms in terms of ADR under different message lifetime. It can be seen that message lifetime has a slight impact on ADR performance. With a bigger value of message lifetime, each node can keep the messages for a longer time and has a higher chance to encounter more suitable forwarders, which seemed to be helpful for the increase of delivery ratio. However, each node with limited buffer size can only carry a limited number of messages. When its buffer is full, the message will be dropped even if its lifetime is not expired. Therefore, a big value of message lifetime does not always mean a high delivery ratio. Another observation from Figure 10 is that IPRA yields the best ADR and PRoPHET the worst, with PRoPHETv2 and PRoPHET-A falling in between. And there is only a slight difference between PRoPHETv2 and PRoPHET-A.Figure11 shows the performance of the four algorithms in terms of AO against different message lifetime. It is clear to see that considerable overhead reduction can be achieved by IPRA compared with PRoPHET and PRoPHETv2, no matter what is the message lifetime. It seems that increasing the message lifetime has a subtle effect to AO for message delivery.Figure12 shows the performance of the four algorithms in terms of AD with different message lifetime. Also there is no obvious difference between IPRA and the other three algorithms for different message lifetime.In order to further evaluate the performance of IPRA, more simulations are run under three different scenarios (small, medium, and large scenarios) taken from the real map of Helsinki downtown area covering 4500 m × 3400 m, 5400 m × 4300 m, and 8300 m × 7300 m regions, respectively. For the small scenario, the number of nodes in each group is 5, 10, 5, 2, 2, and 2. The buffer size for Group 1 and Group 3 is 10 MB; and the communication range for Group 4 is 250 m. For the medium scenario, the number of nodes in each group is 100, 100, 100, 4, 2, and 4. The buffer size for Group 1 and Group 3 is 10 MB. For the large scenario, each of the first three groups and the others include 100 nodes and 5 nodes. The buffer size for Group 1 and Group 3 is 15 MB. For the three scenarios, the buffer size for Group 2, Group 4, Group 5, and Group 6 is 50 MB; and other parameters are the same as Table1. The simulation results are shown in Figures 13–15.Figure 13
Average delivery rate (ADR) under different scenarios.Figure 14
Average overhead (AO) under different scenarios.Figure 15
Average delay (AD) under different scenarios.From Figures13–15, we can observe that, for the small case, there is no oblivious difference between the four algorithms. However, there is a large gap between IPRA and the other three algorithms in terms of ADR in the medium and large scenarios, since more and more nodes are included in the scenarios. In the medium and large scenarios, the AO value of IPRA is slightly higher than that of PRoPHET-A but is still lower than that of PRoPHET and PRoPHETv2. IPRA has the lowest value of AD compared with the other three algorithms in the medium and large scenarios.Finally, in order to investigate the extra overhead introduced by IPRA with two-hop information, we investigate the total energy consumption (TEC) for message transmissions during the simulation time for the four algorithms under different scenarios covering a 4500 m × 3400 m region of Helsinki downtown area with different number of nodes (keeping buffer size 5 MB and message lifetime 5 h), different buffer size (126 nodes and 5 h lifetime), or different message lifetime (126 nodes and 5 MB buffer size), respectively. Other parameters are the same as Table1. More energy consumptions mean more message transmissions and more overhead. We assume that the average energy consumption for one message transmission is one unit. The simulation results are shown in Figures 16–18.Figure 16
Total energy consumption (TEC) versus number of nodes.Figure 17
Total energy consumption (TEC) versus buffer size.Figure 18
Total energy consumption (TEC) versus message lifetime.From Figures16–18, we can observe that PRoPHET-A performs best and PRoPHET the worst, followed by PRoPHETv2 and IPRA in sequence. IPRA almost achieves the same TEC performance with PRoPHETv2, only with a little larger TEC than it. The main reason is that, with the efficient forwarder selection strategy, IPRA has a higher probability to pick an appropriate forwarder, resulting in more message copies in the network. Potentially, it may improve the delivery ratio while transmitting more messages and consuming more energy.


## 5. Conclusions

In order to further improve the message delivery rate of the PRoPHET protocol, a new weighted metric has been introduced for message forwarder selection which jointly considers the contact information of immediate encounters and the two-hop neighbors. Based on the forwarder selection strategy, an improved probabilistic routing algorithm (IPRA) has also been proposed in this paper, which has a higher chance to deliver messages to the destinations. Under the real map scenario of Helsinki downtown area with different nodes and different buffer sizes, extensive simulations have been performed to compare the performance of our proposed algorithm with PRoPHET [16, 17], PRoPHETv2 [19], and PRoPHET-A [20]. Simulation results show that IPRA can explore the advantages of two-hop contact information to select a more suitable forwarder. It has the best performance of average delivery rate while achieving a better or comparable performance with respect to average overhead, average delay, and total energy consumption compared with the existing schemes.



---

*Source: 918065-2015-01-26.xml*