Elsevier

Ad Hoc Networks

Volume 52, 1 December 2016, Pages 160-172
Ad Hoc Networks

New approaches for characterizing inter-contact times in opportunistic networks

https://doi.org/10.1016/j.adhoc.2016.04.003Get rights and content

Abstract

Characterizing the contacts between nodes is of utmost importance when evaluating mobile opportunistic networks. The most common characterization of inter-contact times is based on the study of the aggregate distribution of contacts between individual pairs of nodes, assuming an homogenous network, where contact patterns between nodes are similar. The problem with this aggregate distribution is that it is not always representative of the individual pair distributions, especially in the short term and when the number of nodes in the network is high. Thus, deriving results from this characterization can lead to inaccurate performance evaluation results.

In this paper, we propose new approaches to characterize the inter-contact times distribution having a higher representativeness and, thus, increasing the accuracy of the derived performance results. Furthermore, these new characterizations require only a moderate number of contacts in order to be representative, thereby allowing to perform a temporal modelization of traffic traces. This a key issue for increasing accuracy, since real-traces can have a high variability in terms of contact patterns along time. The experiments show that the new characterizations, compared with the established one, are more precise, even using short time contact traces.

Introduction

In Opportunistic networks, contacts are sporadic and can appear intermittently so routes are built dynamically. Any contact between nodes can opportunistically be used for message relaying, provided it is likely to bring the message closer to the final destination, thus depending on cooperation to work properly. Applications of such networks include Mobile Ad-Hoc Networks (MANETs), Vehicular Ad-Hoc Networks (VANETs) and Mobile Social Networks.

Evaluating the performance of these opportunistic networks is a challenging issue. A common approach is to simulate these networks using a network simulation tool under realistic mobility traces. Nevertheless, simulation can be very time consuming and restricted to the limited scenarios of the available mobility traces. In order to avoid these drawbacks analytical models can provide a fast and broader performance evaluation. Analytical models require anyway a precise and concise description of the mobility patterns. For example, there are many analytical performance models that assume that the inter-contact times distribution between pairs of nodes are exponentially distributed with a given rate λ. For example, using a contact rate λ we can obtain the transmission delay and cost of routing protocols, such as epidemic routing protocols [1], [2], and the impact of node selfishness on mobile networks [3], [4]. The precision of the previous models clearly depends on how accurate is the estimation of the contact rate λ, which at the same time directly depends on the representativeness of the characterized distribution [5]

Therefore, characterizing inter-contact times (or inter-meeting times) between nodes is essential for analyzing the performance of contact based protocols such as cooperative or opportunistic networks. The established approach is to characterize the inter-contact times distribution between pairs of nodes using an aggregate distribution [6], [7], [8], [9], [10]. This distribution is obtained by aggregating the individual pair distribution of all node pair combinations in the network. The individual pair distribution is defined as the distribution of the time elapsed between two consecutive contacts between the same pair of nodes [11]. Another way to characterize inter-contact times is to consider the time elapsed between contacts for any pair of nodes in a group (known as inter-any-contact times). This characterization was briefly studied in [6] using human mobility traces. The conclusions were that inter-any-contact times are longer that individual pairs inter-contact times (as expected), but with a similar distribution shape. This paper also shows a time dependence in the contact distribution, with different pattern distributions for the diurnal and night periods.

Previous works have studied the distribution of the inter-contact times by collecting data from real mobile network environments [1], [7], [8], [9], [12], [13], [14]. Some of these works have shown that the aggregate inter-contact times distribution is exponential with rate λ for both human and vehicle mobility scenarios [1], [9], [13]. The work in [12] analyzed some popular mobility traces and found that over 85% of the individual pair distributions fit an exponential distribution. Nevertheless, there is some controversy about whether this exponential distribution relates to real mobility patterns. Some empirical results have shown that the aggregate inter-contact times distribution follows a power-law distribution and has a long tail [7], meaning that some pairs of nodes barely experience any contact. In [15] it is shown that in a bounded domain, the inter-contact distribution is exponential, but in an unbounded domain the distribution is power-law. The dichotomy of this distribution is described in [8], which shows a truncated power law with exponential decay appearing in its tail after some cutoff point. A recent paper [11], presented the dependence between the individual pair distributions and the aggregate distribution. It is stated that, starting from exponential individual pair distributions, the aggregate distribution is distributed according to a Pareto law. It also verifies the dichotomy property of the aggregate distribution analytically.

Summing up, most of the literature is based on the aggregate distribution, assuming that it is representative of the individual pair distribution [11]. This is the case of the so called homogeneous opportunistic networks assumption, where all pair contact patterns are supposed to be the same. Thus, the contact rate of the aggregate distribution is similar to the individual pair distributions contact rates. Nevertheless, as shown in [11], these contact rates are only similar when the length of the contact trace is large. Furthermore, most traces exhibit a non-homogenous behavior, where pair contact patterns are different. For example, analyzing a contact trace of a University campus we can observe that the contact pattern between students can be different to the contact pattern between staff members. Thus, obtaining a representative characterization (for example λ) of these heterogeneous networks to be used in analytical models is a challenging issue.

A practical approach would be to obtain an equivalent contact rate, aggregating the individual contact rates, as in the homogeneous case (the homogeneous assumption). However, this can lead to an inaccurate characterization, as shown in [16]. The authors of this paper compared three methods for fitting the exponential distribution from traces, always using an aggregation based distribution. These methods were evaluated using a Continuous-Time Markov Chain model of the epidemic diffusion. The results showed that none of the characterization methods used was accurate enough. Therefore, an alternative approach to accurately estimate this individual pair distribution (and the contact rate) is needed, especially for heterogeneous networks.

In this paper, we propose new approaches to improve the characterization of the inter-contact times distribution presenting higher representativeness and, thus, increasing the precision of the results obtained. Using different characterizations, three inter-contact time distributions are considered: the Aggregate Pairs distribution, that is the established characterization; the Aggregate Nodes distribution, that is obtained as the aggregate of inter-contact distributions between one node and the rest of nodes; and the Any Contact distribution, that is the inter-contact distribution between any nodes. First, we study their statistical representativeness showing that, for the same trace length, the Aggregate Pairs distribution has a very low representativeness, especially when the number of nodes is high, in contrast with the others having a good representativeness. Second, we study the relation among these distributions. We prove that, if all individual pair distributions are exponentially distributed, the Any Contact distribution is a new exponential distribution as well. This is not true for the aggregate distributions, that depends on the distribution of each individual λ [11]. The previous conclusions are very important because it allows obtaining the λ value used in the analytical models in a more precise way.

Finally, we evaluate the precision of the three distributions using both synthetic and real contact traces. The precision is evaluated using a well known analytical model, namely the epidemic message diffusion, that is based on a given exponential inter-contact times distribution with rate λ obtained from the three previous characterization methods. Experimental results confirm that the established Aggregate Pairs distribution is under-representative and, consequently, the precision of the results obtained using the epidemic routing model is too low, especially when the number of nodes of the evaluated network is high. Instead, the results using the Aggregate Nodes and the Any-Contact distributions are much more precise, requiring significantly smaller contact traces. Furthermore, these distributions allow the evaluation of the time dependence, obtaining more accurate results, in contrast with the low representativeness (and poor precision) of the Aggregate Pairs distribution.

The rest of the paper is organized as follows. In Section 2 we introduce three methods for characterizing inter-contact times distributions, evaluating their representativeness. Section 3 studies the relation between these distributions, and the associated contact rate. The experimental evaluation of the precision of the different characterizations is described in Section 4 using both synthetic and real contact traces. Finally, Section 5 presents some concluding remarks.

Section snippets

Characterizing inter-contact times distributions

In this section we describe three possible methods for characterizing the inter-contact times distribution from a contacts trace. Beside the established Aggregate Pair characterization we introduce two new approaches: the Aggregate Nodes and the Any Contact characterizations. We study their representativeness by introducing two metrics; the average number of measures and the inter-contact rate. We then evaluate the proposed metrics through some real traces.

Relation between distributions

In this section we study the relation between the different distribution characterizations (AP, AN, AC). Our main goal is to establish relations between the individual distributions and the aggregate distributions. The established approach is to obtain the individual pair contact rate (λp) from the aggregate pairs inter-contact rate (λAP). This relation is of special interest, as many analytical models based on Markov Chains use λp as the contact rate. In this section we introduce new

Experimental evaluation

In the previous sections we have studied the representativeness of the different distributions and the relation between them. We showed that the average node (AN) distribution, and especially the any contact (AC) distribution, have better statistical representativeness than the widely established Aggregate Pairs (AP) distribution. Now, we are going to evaluate the precision of these characterizations.

There are many analytical performance models that assume that the inter-contact times

Conclusions

In this paper we introduced new approaches to characterize the inter-contact times distribution in order to increase the representativeness, and thus the precision of the analytical performance models based on these exponential distributions. The usefulness of exponential characterizations and models is based on its simplicity. Using only two parameters (contact rate and number of nodes) we can model a high variety of protocols, such as epidemic diffusion, two-hop, selfish node detection, among

References (24)

  • R. Groenevelt et al.

    The message delay in mobile ad hoc networks

    Perform. Eval.

    (2005)
  • ZhangX. et al.

    Performance modeling of epidemic routing

    Comput. Netw.

    (2007)
  • M. Karaliopoulos

    Assessing the vulnerability of DTN data relaying schemes to node selfishness

    IEEE Commun. Lett.

    (2009)
  • E. Hernández-Orallo et al.

    CoCoWa: a collaborative contact-based watchdog for detecting selfish nodes

    IEEE Trans. Mob. Comput.

    (2015)
  • E. Hernández-Orallo et al.

    A representative and accurate characterization of inter-contact times in mobile opportunistic networks

    Proceedings of the 16th ACM International Conference on Modeling, Analysis and Simulation of Wireless and Mobile Systems, MSWiM ’13

    (2013)
  • HuiP. et al.

    Pocket switched networks and human mobility in conference environments

    Proceedings of the 2005 ACM SIGCOMM Workshop on Delay-tolerant Networking, WDTN ’05

    (2005)
  • A. Chaintreau et al.

    Impact of human mobility on opportunistic forwarding algorithms

    IEEE Trans. Mob. Comput.

    (2007)
  • T. Karagiannis et al.

    Power law and exponential decay of inter contact times between mobile devices

    Proceedings of the 13th Annual ACM International Conference on Mobile Computing and Networking, MobiCom ’07

    (2007)
  • ZhuH. et al.

    Recognizing exponential inter-contact time in VANETs

    Proceedings of the 29th Conference on Information Communications, INFOCOM’10

    (2010)
  • A. Passarella et al.

    Modelling inter-contact times in social pervasive networks

    Proceedings of the 14th ACM International Conference on Modeling, Analysis and Simulation of Wireless and Mobile Systems, MSWiM ’11

    (2011)
  • A. Passarella et al.

    Characterising aggregate inter-contact times in heterogeneous opportunistic networks

    Proceedings of the 10th International IFIP TC 6 Conference on Networking – Volume Part II, NetworkinG’11

    (2011)
  • GaoW. et al.

    Multicasting in delay tolerant networks: a social network perspective

    Proceedings of the tenth ACM International Symposium on Mobile Ad hoc Networking and Computing, MobiHoc ’09

    (2009)
  • Cited by (18)

    • General and mixed linear regressions to estimate inter-contact times and contact duration in opportunistic networks

      2019, Ad Hoc Networks
      Citation Excerpt :

      There are several surveys that cover the different challenges routing protocols must face in OppNet. Some examples of these surveys are [13–16]. Among the different metrics used for routing and delivery decisions, for this study we focus on two of them: inter-contact time and contact duration.

    • Analytical evaluation of the performance of contact-Based messaging applications

      2016, Computer Networks
      Citation Excerpt :

      Thus, from now on, we will use the term “contact rate” to refer to the “effective contact rate”. This rate is not based on any underlying mobility model but it was obtained using real mobility traces (see [19]). In this section we propose an analytical performance model to evaluate the dissemination of messages considering the data transmission time in a place where people can enter and leave.

    • Stochastic Multi-Distribution Modeling of Inter-Contact Times

      2022, International Conference on Information Networking
    View all citing articles on Scopus

    This work was partially supported by Ministerio de Economia y Competitividad, Spain (Grant TEC2014-52690-R) and Generalitat Valenciana, Spain (Grant AICO/2015/108).

    View full text