# An Empirical View on Opportunistic Forwarding Relay Selection Using Contact Records

Jia Jianbin, Chen Yingwen, Xu Ming

► To cite this version:

Jia Jianbin, Chen Yingwen, Xu Ming. An Empirical View on Opportunistic Forwarding Relay Selection Using Contact Records. 9th International Conference on Network and Parallel Computing (NPC), Sep 2012, Gwangju, South Korea. pp.256-263, 10.1007/978-3-642-35606-3_30. http-01551313

HAL Id: hal-01551313

https://inria.hal.science/hal-01551313

Submitted on 30 Jun 2017

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# An Empirical View on Opportunistic Forwarding Relay Selection Using Contact Records

Jia Jianbin, Chen Yingwen, Xu Ming

School of Computer, National University of Defense Technology, Changsha, 410073, China
jiajianbin.nudt@gmail.com, csywchen@gmail.com,
xuming@nudt.edu.cn

**Abstract.** Opportunistic routing schemes usually infer future contact time to select next hop relays. But the effect of relay selected in this way is uncertain. In order to get further understanding of the intrinsic uncertainty characteristic of relay efficiency, this paper makes an empirical investigation on opportunistic forwarding relay selection schemes using contact records. Based on the underlying opportunistic vehicular network extracted from large-scale realistic vehicle traces, we evaluated the efficiency of relay selection and got some intrinsic sight of opportunistic forwarding. The questions we investigated are: What is the probability that a selected relay can make the end-to-end delay reduced? How much the latency can be saved by a properly selected relay? Such an empirical study is meaningful for the protocol design and applications deployment in future opportunistic networks.

**Keywords:** opportunistic networks; relay selection; residual expected delay; delay reduced ratio

## 1 Introduction

In Delay Tolerant Networks (DTN) or Opportunistic Networks (ON), carry-and-forward technique is the major method used for delivering messages. Direct Forwarding (DF) is the most basic scheme, in which messages are carried until the source node contacts with the destination directly. Relays may be involved to assist data exchange in order to obtain better delivery performance. In this case, a primary issue is how to select effective relays. A lot of schemes proposed in previous literatures make relay decision based on the predication of future contact opportunities from history information of connectivity between mobile nodes [1][2].

However, the inaccuracy of predication in practical leads to the selected relay(s) has only an incidental rather than intentional effect on delivery metrics such as end-to-end delay [3]. For example in Fig. 1, if we assume node $R_2$ is selected as relay, whether the delivery delay of relay assisted forwarding ($S \rightarrow R_2 \rightarrow D$) is really lower than that of direct forwarding ($S \rightarrow D$) is questionable. In addition, whether the selected relay node $R_2$ has more time saved than other candidate nodes in $R_1, R_3, \dots$, and $R_n$ is still unclear.
<figure><img src="image_2.png" /><figcaption>Fig. 1. Example of Relay Assisted Data Delivery</figcaption></figure>

For such “incidental” relay efficiency, this paper provides an empirical study in the background of vehicular DTN. In particular, we mainly focus on the following questions: How to select a proper node as relay? What is the probability that a relay can make the end-to-end delivery delay reduced? How much latency time can be saved by a properly selected relay?

The main contributions of this paper are: (1) We introduce an more effective op-
portunistic relay selection scheme based on Residual Expected Delay (RED), which
utilizes local pairwise contact records and the elapsed time since last encounter to
estimate residual encounter time. (2) Based on the underlying vehicular DTN, we
investigate relay efficiency in terms of the ratio of delay time can be reduced and the
number of possible relays can be selected. Empirical results reflect that the relay effi-
ciency is related to the distribution of direct forwarding delay.

The structure of the paper is organized as follows: The next section presents related work, the third section introduces the RED based relay selection scheme and the estimation framework of RED value. Section IV gives the detailed evaluation results and analysis of relay efficiency in underlying vehicular DTN. The conclusion of this paper is made in Section V.

2 Related Works

The core issue of opportunistic messages forwarding is relay selection. Using the knowledge of history contact records between mobile nodes to assist forwarding decision is an important method. S. Jain et al. [4] proposed the Minimum Expected Delay (MED) algorithm in which the value of expected delay is defined as the average waiting time calculated from connectivity schedules of mobile nodes. Evan P. C. Jones et al. [5] improved MED and propose Minimum Estimated Expected Delay (MEED), where the expected delay is calculated using the observed contact history of a sliding history window. While H. Chen et al. in [6] proposed a forwarding scheme that each node decides whether to forward the message to its current encounter by comparing their minimum expected meeting delays (MEMDs) to the destination. The MEMD is calculated based on the past inter-contact times between each pair of nodes and the elapsed time since their last contact.

Our work also uses history contact records to predict residual encounter time with
considering the elapsed time from last meeting time. The difference lies in that we
focus on the direct forwarding residual delay time and employ a per-contact relay
decision scheme. Particularly, we make an empirical investigation on the relay selection methods. Such a work provides some insight into the opportunistic forwarding scheme in practical.

# 3 RED based Forwarding Scheme

In this section, we describe the Residual Expected Delay (RED) based relay selection scheme. RED is the estimation value of residual meeting time for a pair of nodes.

## 3.1 Residual Expected Delay Estimation

Assume each node records the last $n + 1$ meeting times with others. For a pair of nodes, the records are represented by time series $t_1, t_2, \dots, t_{n+1}$, where $t_1$ is the most recent record and $t_{n+1}$ is the oldest record. If current time is $t$, then ET is calculated as $T_E = t - t_1$. Thus, the last $n$ inter contact time (ICT) series can be calculated as $t_1 - t_2, t_2 - t_3, \dots, t_n - t_{n+1}$. To be described conveniently, we denote the ICT series with $I_1, I_2, \dots, I_n$, in which the ICTs are sorted by length. Thereby, the residual encounter time for a node pair can be estimated as follow.

Given a set of ICT records of node pair $S-D$ are $I_1, I_2, \dots, I_n$, where $I_1 \le I_2 \le \dots \le I_n$. If the elapsed time from last meeting between $S$ and $D$ to the relay decision moment is $T_E$, and $I_k \le T_E < I_{k+1}$, then the expectation of residual encounter time $T_R$ for $S-D$ can be calculated by

$$E[T_R] = \frac{1}{n-k} \sum_{k+1}^{n} I_i - T_E \quad (1)$$

Note, when the elapsed time $T_E$ is lower than the minimum value in $\{I_1, I_2, \dots, I_n\}$, i.e. $T_E < I_1$, the residual delay estimated according to Eq. 1 degrades to the mean inter contact time (MICT). While if $T_E$ is equal to or greater than the maximum value in $\{I_1, I_2, \dots, I_n\}$, i.e. $T_E \ge I_n$, Eq. 1 is invalid to estimate the residual delay. In this situation, we also use the mean inter contact time as the estimation value as well. Therefore, Eq. 1 is improved to be as the following

$$E[T_R] = \begin{cases} \frac{1}{n-k} \sum_{k+1}^{n} I_i - T_E, & I_k \le T_E < I_{k+1} \\ \frac{1}{n} \sum_{1}^{n} I_i, & T_E < I_1 \text{ or } T_E \ge I_n \end{cases} \quad (2)$$

## 3.2 Residual Delay based Relay Selection Decision

Suppose from the time node $S$ injects a message (Msg), which is target to the destination node $D$, to the time $S$ contact with $D$ directly, $S$ will meet a set of nodes, represented by $\Omega = \{R_1, R_2, \dots, R_m\}$ in chronological order. In order to reduce the delay time of direct forwarding, $S$ may choose a node from $\Omega$ to assist the transmission of Msg. Therefore, $\Omega$ can be regarded as potential candidate set of relay. Naturally, the central issue is how to find out an appropriate node from $\Omega$ to be utilized as relay.
Residual delay is an effective metric for relay selection decision, which refers to the time from a relay decision moment to the time that the message arriving at destination successfully. Formally, the RED based relay selection strategy is described as following. Assume $T_{RXY}$ represents the residual delay of a message delivered from node X to Y directly. $R_1, R_2, \dots, R_n$ are the intermediate nodes that source node S met before the target D. The relay selection judgment is determined by comparing the residual expected delay values (calculated according to Eq. 2) of node pairs S-D and $R_i-D$.

**RED Based Strategy:** For $R_i \in \{R_1, R_2, \dots, R_m\}$, if

$$E[T_{RSD}] \geq E[T_{RR_iD}] \quad (3)$$

then $R_i$ is regarded to be fitting for carrying and forwarding Msg to D.

# 4 Empirical Evaluation

In this section, we present the empirical investigation results of RED based relay selection strategy. The evaluation is carried out with Cabspotting [7] taxi traces. These taxis operate in San Francisco city Bay area with a core driving coverage of about 11 × 13 km². A Cabspotting trace dataset containing the trace records of 536 vehicles within 25 days can be found in CRAWDAD [8]. We randomly generate a test set composed by 8000 pairs of source-destination (S-D) combination. To avoid the delivery time of S-D sessions being beyond the record time span in the trace dataset, the messages sending requests are randomly injected by node S within the first three days of the records.

To investigate the RED based relay selection method, we design a two-hop opportunistic forwarding algorithm with single copy scheme, in which, only one relay node is needed, and there exists only one replication of message in the network, i.e., if the previous carrier forward the message to the next node, it will discard its own replica. The algorithm uses the per-contact relay decision paradigm, in which the message sender (or carrier) makes a judgment at each time when it meet with a potential relay node, until the message is hand over. Although the two-hop single relay forwarding algorithm is somewhat naive, it is able to generally reflect the relay efficiency of opportunistic forwarding scheme in practical. In addition, we compare RED based forwarding scheme with MICT based scheme [4][5] in which the mean inter contact time value is used as a rough estimation of residual delay time.

## 4.1 Performance Metrics

We call the constraint conditions used for relay selection as Qualified Condition, such as Eq. 1. Nodes satisfying qualified condition are called Qualified Node. Generally, a qualified node is expected to have the ability of reducing delivery delay of messages, but whether it can achieve such a benefit is not sure. For distinguishing, we refer to the qualified node satisfying delay reduce expectation as Good Relay. Percentage of
delay reduced and the ratio of good nodes in qualified nodes reflect the efficiency of the relay qualifying strategy.

Assume the direct forwarding delay is denoted by $T_{DF}$, and the relay assisted delivery delay is denoted by $T_{SRD}$. Then, the two metrics to investigate the performance of opportunistic relaying scheme are defined as follows.

* Delay Reduced Ratio (DRR): DRR is measured with the delivery time saved by relay forwarding compared to the delay of direct forwarding. Formally,

$$DRR = \frac{T_{DF} - T_{SRD}}{T_{DF}}$$

* Good Relay Ratio (GRR): GRR is defined as the ratio of good relay number to the qualified node number. Formally,

$$GRR = \frac{N_{good relay}}{N_{qualified node}}$$

## 4.2 Delay Reduced Ratio

First, let us look at the average delay reduced ratio of potential relays in different candidate sets. Three relay candidate sets are considered: (1) all potential relays without qualified condition filtering (all the nodes met by S before it meets D); (2) MICT based qualified nodes according to Eq. 3; and (3) RED based qualified nodes according to Eq. 3. As displayed in Table I, The average DRRs for the three relay candidate sets are about 3.93%, 10.25% and 23.85% respectively. Meanwhile, when only considering good relays in those candidates, the average DRRs are about 27.79%, 32.00% and 44.88% respectively. Such result suggests that taking into account the elapsed time is effective when choosing relays in opportunistic forwarding. And it implies when properly selected a relay with RED based strategy, more than 40% of delay time could be reduced in a general view.

<table><caption>**Table 1.** Overall Average Delay Reduced Ratio</caption><thead><tr><th></th><th>Potential Relays</th><th>MICT Qualified</th><th>RED Qualified</th></tr></thead><tbody><tr><th>All Relays</th><td>3.93%</td><td>10.25%</td><td>23.85%</td></tr><tr><th>Good Relays</th><td>27.79%</td><td>32.00%</td><td>44.88%</td></tr></tbody></table>

<table><caption>**Table 2.** Average Delay Reduced Ratio for First Meet Relay</caption><thead><tr><th></th><th>Basic FMR</th><th>MICT based FMR</th><th>RED based FMR</th></tr></thead><tbody><tr><th>First Relay</th><td>6.77%</td><td>11.50%</td><td>15.20%</td></tr><tr><th>First Good Relay</th><td>35.60%</td><td>37.22%</td><td>53.75%</td></tr></tbody></table>

Then, we investigate the distribution of average delay reduced ratio correlated with direct forwarding delay. Fig. 2 shows the average delay reduced ratio in different direct forwarding delay levels. DRR is represented by the vertical axis, while DF delay is represented by the horizontal axis. To reflect DRR under different DF delay
levels, we divide the horizontal axis into the unit of a day's time, and then count the average DRR in each DF delay level. For example, the average DRR corresponding to 10 days in horizontal axis means the average DRR of those S-D pairs whose direct forwarding delay is larger than 10 days and lower than 11 days.

<figure><img src="image_3.png" /><figcaption>Fig. 2. Delay Reduced Ratio in Average</figcaption></figure>

<figure><img src="image_4.png" /><figcaption>Fig. 3. Delay Reduced Ratio for First Meet Relay</figcaption></figure>

Fig. 2(a) exhibits the average DRR distribution for three kinds of candidate relay sets, and Fig. 2(b) exhibits the corresponding average DRR distribution only considering good candidate relays. Both of the figures show that the average DRR of MICT qualified nodes is a little better than the average of un-qualifying relays. In the same time, the average DRR of RED scheme is much better than others. Particularly, when DF delay is higher than 5 days, RED scheme is more advantageous.

For a determined single relay, if we consider the basic first meet relay (FMR), the average DRRs are exhibited in Table II and Fig.3. The basic FMR uses the first met node as the single relay without judgment. MICT-FMT or RED-FMT respectively uses the first met node satisfying MICT or RED based qualified conditions as the single relay. It is apparently that the FMR result is mainly in accordance with the trend of general average situation introduced above. This proves a relay selected with RED is more effective in reducing opportunistic forwarding delay.

**Discussion:** From Fig. 2(a) and Fig. 3(a), we can also learn that, when the DF delay is lower than one day's time (corresponding to zero in horizontal axis), the average DRRs of all three schemes are lower than zero. This suggests that under this con-
dition, direct forwarding is likely to be more effective than taking a relay. On the other hand, the corresponding DRRs of good relay showed in Fig. 2(b) and Fig. 3(b) perform quite well. This difference is resulted from that good relays are relatively less in the potential relay candidates, which is the paradigm examined in the next part.

<figure><img src="image_5.png" /><figcaption>Fig. 4. Average Good Relay Ratio</figcaption></figure>

<figure><img src="image_6.png" /><figcaption>Fig. 5. The CDF of Delivery Delay</figcaption></figure>

## 4.3 Good Relay Ratio

Fig. 4 shows the average good relay ratio corresponding to different DF delay levels. We can find that when DF delay is higher than one day, the good relay ratio of RED scheme is much better than that of MICT scheme and all potential one's. This indicates that a RED qualified relay has higher probability to make the delivery delay reduced. In other words, it proves the RED based relay selection decision is more accurate than MICT. Another noteworthy feature is that when DF delay time is less than one day, the good relay ratio is also very low. This confirms the observation that direct forwarding is likely more effective than using relay in low DF delay level, where the good relay ratio is only about 40%.

**Discussion:** Considering DRR and GRR jointly, we can see that when DF delay is high, relaying schemes have better DRR and GRR at the same time. Therefore, relay forwarding is more effective than direct forwarding. Particularly, in the scenario of underlying vehicular DTN, when DF delay is larger than one day's time, it is prefer to use relay scheme. On the other hand, when DF delay is lower than one day, direct forwarding has better delivery performance. This can be confirmed in Fig.5, in which the cumulative distribution of direct forwarding delay, average delivery delay of MICT qualified relay forwarding and average delivery delay of RED qualified relay forwarding are plotted. In fact, the CDF shows when DF delay is lower than 20 hours, direct forwarding is more promising in delivery ratio.

This insight of efficiency transition between direct forwarding and relay forwarding would like to maintain in other opportunistic network scenarios with specific critical DF delay value. From another point of view, this insight suggests it is more proper to use a hybrid multi-copy scheme which uses relay forwarding and also retains direct forwarding. It also reflects that the relay selection scheme only using contact records is inefficient when DF delay is low. More effective method or improvement should be proposed to remedy this drawback.
# 5 Conclusions and Future Work

In this paper, we introduced a residual expected delay based relay selection scheme, and made an empirical investigation on the opportunistic relay efficiency. We demonstrated the relay efficiency in terms of delay reduced ratio and good relay ratio. Evaluation result shows that the RED based relay selection scheme taking into consideration the elapsed time exhibits better performance than the mean inter-contact time based scheme. However, the correlation between relay efficiency and direct forwarding delay implies that when the direct forwarding delay is lower than some value, opportunistic single relay assisted delivery is likely to not obtain benefit in reducing end-to-end delay. Therefore, the helpfulness and harmfulness of opportunistic relay forwarding should be reconsidered.

In the next step, we will look at the performance of multi-relay opportunistic forwarding schemes in different realistic scenarios. Another problem drawing our attention is to deal with the ineffective relay selection in low direct forwarding latency.

**Acknowledgments.** This research is partially supported by the National Science Foundation of China under Grant No. 61070211 and No. 61003304; and Hunan Provincial Natural Science Foundation of China under grants No. 09JJ4034.

# References

1. Lindgren, A., Doria, A., Schelen, O.: Probabilistic Routing in Intermittently Connected Networks. In: Dini, p., Lorenz, P., Souza, J.N.(eds). Lecture Notes in Computer Science, Vol. 3126, pp. 239-254. Springer, Heidelberg (2004)

2. Nelson, S.C., Bakht, M., Kravets, R.: Encounter-Based Routing in DTNs. In Proceedings of INFOCOM 2009, pp. 846-854. IEEE Press, New York (2009)

3. Balasubramanian, A., Levine, B.N., Venkataramani, A.: DTN routing as a resource allocation problem. In: Proceedings of SIGCOMM 2007, pp. 373-384. ACM Press, New York (2007)

4. Jain, S., Fall, K., Patra, R.: Routing in a delay-tolerant network. In: Proceedings of SIGCOMM 2004, pp. 145-158. ACM Press, New York (2004)

5. Jones, E.P.C., Li, L., Ward, P.A.S.: Practical routing in delay-tolerant networks. In: Proceedings of the 2005 ACM SIGCOMM workshop on Delay-tolerant networking, pp. 1-7. ACM Press, New York (2005)

6. Chen, H., Lou, W.: On Using Contact Expectation for Routing in Delay Tolerant Networks. In: Proceedings of 2011 International Conference on Parallel Processing (ICPP), pp. 683-692. IEEE Press, New York (2011)

7. Piorkowski, M., Djukic, N.S., Grossglauser, M.: A Parsimonious Model of Mobile Partitioned Networks with Clustering. In: Proceedings of 1st International Conference on Communication Systems and NETworkS (COMSNETS), pp. 258-267. IEEE Press, New York (2009)

8. CRAWDAW, http://www.crawdad.cs.dartmouth.edu/