This is the accepted version of the article: Borrego Iglesias, Carlos; Hernández Orallo, Enrique; Magaia, Naercio. «General and mixed linear regressions to estimate inter-contact times and contact duration in Opportunistic Networks». Ad Hoc Networks, Vol. 93 (October 2019), art. 101927. DOI 10.1016/j.adhoc.2019.101927 This version is avaible at https://ddd.uab.cat/record/206283 under the terms of the license General and mixed linear regressions to estimate inter-contact times and contact duration in Opportunistic Networks Carlos Borregoa,∗, Enrique Hernández-Orallob , Naercio Magaiac a Department of Information and Communications Engineering Autonomous University of Barcelona, Barcelona, Spain b Departamento de Informática de Sistemas y Computadores. Universitat Politècnica de València, València, Spain c LASIGE, Faculdade de Ciências Universidade de Lisboa, Lisbon, Portugal Abstract In the context of Opportunistic Networking (OppNet), routing and delivery algorithms used for content dissemination employ different metrics to perform accurate decisions. It has been shown that of these metrics, the inter-contact time and the contact duration are very useful for characterising OppNet scenarios. In this article, we show that the exponential moving averages of the historical values of these metrics are correlated with future observed values, in addition to also being good estimators for them. Moreover, we go a step further to investigate how to locally, from the OppNet node perspective, improve the estimations for these metrics by defining two novel estimation functions. These estimation functions are based on two different linear models: a general regression model and a mixed regression model, where future values of the studied metrics are explained in terms of their corresponding exponential moving averages. Experimentation using real mobility traces from well-known OppNet scenarios show that our estimation functions greatly reduce the estimation error of the future values of both metrics when compared to representative state of the art proposals. Keywords: Opportunistic Networks, inter-contact time, contact duration, regression models, mixed models 1. Introduction node contact duration have shown, in a wide range of pub- lications, to be extremely useful as they are metrics that Opportunistic Networking (OppNet) [1] is an open re- effectively characterise the network’s node behaviour [2]. search field of computer networks that studies networks While the inter-contact time metric measures the time be- where mobile nodes communicate with each other even tween two successive contacts, the contact duration metric when there is no end-to-end connectivity between them. determines how long two nodes are in contact. As mobile devices get smarter, OppNet has emerged as a Examples of the benefits of these metrics in the lit- solid network solution that allows different applications to erature are numerous. For instance, many already pub- be deployed when under these network conditions. lished proposals have shown that the contact duration dis- One of the most challenging issues in OppNet is the tribution measured by each node is a very efficient met- routing and delivery decisions. Routing is the node de- ric for helping to increase the probability of simultaneous cision as to whether or not to forward a certain message forwarding by deliberately postponing message forward- upon contacting another node. The delivery decision de- ing [3]. In the very same way, the inter-contact time has termines whether a node should be considered to be the proven to be a very efficient metric for predicting the num- destination of the message. Unlike in connected networks, ber of future contacted nodes in a certain period of time. OppNet routing and delivery decisions are not trivial be- These kinds of predictions are very useful for complex mes- cause of OppNet’s dynamical properties when it comes to sage delivery decisions, such as in proposals like [4]. a node’s movement models. In order to estimate future values of the inter-contact In the OppNet literature, many different network met- time and contact duration metrics, the usual approach is to rics have been used to help with these routing and deliv- have these nodes fit these metrics to known distributions, ery decisions. Among these metrics, inter-contact time and such as exponential or power-law distributions, as in pro- posals like [5]. Another way of estimating these metrics is ∗ Corresponding to allow OppNet nodes to build and locally store previous author Email addresses: carlos.borrego@uab.cat (Carlos Borrego), metric average values from the past and use these averages ehernandez@disca.upv.es (Enrique Hernández-Orallo), as estimators for future metric values. For this purpose, ndmagaia@ciencias.ulisboa.pt (Naercio Magaia) Journal Publication June 25, 2019 statistical exponential moving averages (ewma) are very 2.1. Moving averages useful because with a single average value both old values An exponential moving average (ewma) is a very use- and recent values are considered. This is obtained by ap- ful statistic tool for averaging. It is a lightweight (in terms plying weighting factors which decrease exponentially and of storage requirements) moving average that, in an adap- never reach zero. tive way, takes into account both historical information In this article, we confirm that these exponential mov- from the past and new recently measured information. A ing averages of historical values of the two studied metrics general ewma is calculated every time a new measure is (inter-contact time and contact duration) are tightly cor- obtained in the following way: related with future observed values, while also being good estimators for them. In addition, we take a further step ewmanew = ewmaold + σ × (lastmeasured − ewmaold ) (1) forward and focus on investigating how to locally, from the OppNet node perspective, improve the estimations for where ewmanew is the new average value, ewmaold , the these metrics by defining two novel estimation functions old value, lastmeasured is the last value measured and that use their corresponding exponential moving averages. σ ∈ [0..1] a constant to give different weights to historical These estimation functions are created by defining two information and new information. different linear models: a general linear regression model This way of averaging information using ewma has been widely employed in OppNet because of these charac- and a linear mixed regression model, where the explained variables are the future values of the studied metrics and teristics. For example, in [6], the authors propose an Opp- the explanatory variables their corresponding exponential Net routing protocol that uses an ewma-based scheme in moving averages. In order to achieve this, we propose that order to keep nodal contact probabilities updated. Addi- the samples needed to define the proposed linear models be tionally, in [7, 8], the authors use ewma to estimate future collected by the very same OppNet nodes, and, in the case times between forwarding actions. of the mixed models, even share them upon encountering other nodes. 2.2. General linear regressions and mixed linear models Specifically, the contributions of this article can be Linear regression [9] is a basic statistical tool for pre- summarised as follows: dictive purposes. It is extremely useful for finding a re- lationship between two or more continuous variables. It • A first estimation function based on a general linear studies whether a set of variables are good for predicting a regression model to predict the inter-contact time certain outcome, also called the dependent variable. Given and the contact duration for OppNet. a random sample collection (Xi , Yi ), i = 1, . . . , n, the sim- plest form of a regression model with one dependent and • A second estimation function based on a mixed linear one independent variable is defined by the equation of the regression model to predict both metrics, based on general linear regression: node cooperation. Yi = α + β × Xi + i , i ∼ N (0, σ 2 ) (2) • We use real mobility traces to validate the correct- ness and performance of the two proposed estimation where Yi is the explained response (or dependent) variable, functions. Xi the explanatory (or independent) variable, α is called the intercept value (the value of the dependent value when The paper starts with Section 2, which contains some the explained equals 0) and β the slope value. The infor- background information on exponential averages and lin- mation that cannot be explained by this model are the ear models. Then, in Section 3, we examine the state of residuals i , which are assumed to be normally distributed the art of OppNet proposals that analyse the inter-contact with expectation 0 and variance σ 2 . time and contact duration metrics. Next, we provide a The model coefficients can be obtained as [10]: full description of our estimation models in Section 4. The ( Yi )×( Xi2 )−( Xi )×( Xi ×Yi ) P P P P paper continues with Section 5, where we present a com- α= (3) n×( Xi2 )−( Xi )2 P P parison of our proposal with others from the state of the art. Finally, Section 6 contains the conclusions we have Additionally, β is obtained in the following way: drawn from this work. P P P n×( XPi ×Yi )−( P Xi )×( Yi ) β= n( Xi2 )−( (Xi ))2 (4) 2. Background Linear mixed models [11] are an extension of simple In this section, we present some background informa- linear models that also take into account both the variation tion needed to understand our proposal. This will be a explained by the independent or explanatory variables of brief introduction on moving averages, general linear re- interest, also called fixed effects, as well as the variation gressions, and linear mixed models. not explained by the independent or response variables of interest, also called random effects. They are especially 2 useful when there is non-independence in the data, such 3.1. OppNet Routing and Delivery as when the data is hierarchically structured. Routing and delivery in OppNet are the decisions that The mixed linear model where information is struc- set the path of a message from a source to a destination. tured into different groups (i = 1, . . . , N ) and every group There are several surveys that cover the different chal- i contains ni observations can be defined as: lenges routing protocols must face in OppNet. Some ex- Yi = Xi × β + Zi × bi + i (5) amples of these surveys are [13, 14, 15, 16]. Among the different metrics used for routing and delivery decisions, where, again as in the linear regression model, Xi contains for this study we focus on two of them: inter-contact time the explanatory variable, but Yi contains the explained and contact duration. variable for the group i, and where N is the number of groups. There are two components in this model: the 3.2. Inter-contact time and contact duration aware rout- fixed term (Xi × β) and the random one (Zi × bi ). The ing/delivery algorithms component Zi × bi contains the effect on the model for The inter-contact time between nodes in an OppNet every group. This means that every group is allowed to has been proposed as a key metric for defining its perfor- have a different Y : X relationship. However, the β factor mance since it has been proven to have a broad impact on is applied to all of the groups. In order to represent Xi message delivery reliability [2]. For this reason, the inter- and Zi , two matrices of dimension ni × p and ni × q, are contact time has been widely used as a metric for per- defined respectively, where ni is the number of observa- forming routing or delivery decisions. For instance, there tions in Yi (the number of observations per group), p the is a wide range of social-aware OppNet routing propos- number of explanatory variables in Xi and q the number als that identify important nodes in a network by using of explanatory variables in Zi . different centrality metrics. A large part of these metrics A special case of mixed linear models that will be used are computed taking into account the inter-contact time of in this proposal is the random intercept model, where the the nodes: the shorter the inter-contact time is in a node, model intercept may change per group. The model is de- the more frequent that node will be encountered, thus in- fined as: creasing its popularity. For example, in [17], the authors Yij = α + β1 × Zi + β2 × Xij + ij (6) propose a social popularity-based routing protocol named where Yij is the explained variable, α is the independent SPBR that takes into account the inter-contact time and term, β2 is the fixed effect associated to the fixed Xij vari- multi-hop neighbour information. able, and β1 is the fixed effect associated to the random In the context of OppNet delivery protocols, in [4], Zi variable, which has as many levels as there are differ- the authors propose a general delivery scheme for many- ent sample groups. The random variable is included in cast group communications based on a mobile code. They the model assuming that the variations around the inter- present an application of this scheme for solving, by way cept for each member of Zi is normally distributed with a of an analytical delivery method, the problem of sending a certain variable. This mixed effect is modelled as: message to k and only k nodes of a heterogeneous and op- portunistic network scenario that best fit a given criterion. Yi = Xi × β + Zi × bi + i (7) For these purposes, the authors use for their delivery pro- In a matrix notation, the same model can be defined tocol the number of potential nodes belonging to a certain as: profile to which a message can be forwarded for a given pe-         riod of time. This number is calculated by understanding Yi1 1 Xi1 1 i1  Yi2  1 Xi2    1  i2  the inter-contact time of every node in the network. α Analysing the duration of node contacts in OppNet,  . = ..  × β +  ..  × βi +  ..  (8)          ..  1 .   .   .  also known as contact duration, has helped propose very Yini 1 Xini 1 ini efficient OppNet routing, delivery, data replication schemes From this model, we can extract its coefficients, which and caching protocols. For example, in the context of Opp- are the common slope (slope) and a list of intercept values Net cooperative caching, Zhuo et al. [18] propose a caching for the different groups (intercepti , i = 1, . . . , N ). These protocol that takes into account the impact of the con- values are the combination of the fixed effects and the tact duration limitation on cooperative caching by deriv- variance components of the random effects, as explained ing an adaptive caching bound at each OppNet node and in [12]. analysing its specific contact patterns with other nodes. In [19], the authors propose a contact duration-aware replica- tion protocol that operates in a fully distributed manner. 3. Related Work In this proposal, the authors give an analytical descrip- tion of the contact duration-aware data replication prob- In this section, we study the state of the art of Oppor- lem and propose a centralised solution for improving the tunistic Networking, paying special attention to two of the utilisation of the storage buffers as well as the contact metrics that will be estimated in this study: inter-contact opportunities. In [20], the authors propose an OppNet time and contact duration. 3 routing protocol that avoids forwarding failure by divid- that there is a characteristic time, approximately half a ing OppNet messages into smaller fragments. The authors day, beyond which the distribution of the inter-contact present a mathematical model that considers the contact time follows a power law distribution. After this time, the durations for deriving the optimal fragment size that min- distribution decays exponentially. imises message delivery delay. Nevertheless, this established approach of using the Proposals like [2, 17, 4, 18, 19] described in this sec- inter-contact times between pairs has been shown to achieve tion show that the inter-contact time and contact dura- non-representative characterisations [16]. Using the indi- tion metrics are useful tools for making network decisions, vidual nodes’ inter-contacts instead can lead to more pre- such as the delivery or the routing decision. In turn, these cise estimations. Furthermore, the aggregate inter-contact network decisions aim to improve the performance of the times distribution can only be representative of the indi- network in terms of metrics, such as the delivery latency vidual distributions when all nodes contacts patterns are or the delivery ratio. In the following section, we analyse supposed to be the same (the homogeneous network as- proposals that make estimations on these metrics. sumption) [15]. Therefore, considering that opportunistic networks are heterogeneous, the individual nodes’ inter- 3.3. Estimating inter-contact time and contact duration contact time will lead to better estimations as proposed in As detailed above, most routing algorithms require a this paper. good estimation of the inter-contact time and contact du- Summing up, in this section, we have presented the ration to provide reliable routing decisions. Thus, the state of the art of inter-contact time and contact duration OppNet research community has proposed different ways estimation on OppNet. To the best of our knowledge, there of estimating the inter-contact time of nodes in order to are very few proposals using linear models in OppNet. In make good routing or delivery decisions. [28], the authors show from an analytical perspective that In general, users tend to follow mobility patterns, that inter-contact times in OppNet can be approximated as ex- is, humans have strong habits they follow every day, al- ponentially distributed in certain mobility models. In or- lowing future behaviour to be predicted [21]. Therefore, der to prove this, they use linear regression analysis. Addi- the main idea is to predict future encounters among nodes tionally, in [29], by using real mobility traces, the authors using the past history of encounters [22]. Concretely, this of this study classify users as being vagabonds or socials paper studies the predictability of a node’s future contacts according to their social behaviour. They conclude, using by analysing their previous contacts. The authors propose linear regressions as statistical tools, that the effectiveness modelling the contact time series as a Poisson distribution of OppNet message dissemination predominantly depends (with the number of contacts being the Poisson events in on vagabonds because they outnumber socials. However, a fixed one-hour interval), showing that the number of as far as we know, there is no proposal in OppNet literature contacts per time unit in the future can be efficiently pre- that uses ewma as an explanatory variable for creating lin- dicted. This model has been evaluated and validated using ear general or mixed models for the purpose of estimating a trace recorded in the Politehnica University of Bucharest, future values of inter-contact times and contact duration. in addition to other known traces. Based on this con- In the following section, we explain our estimation pro- tact prediction model, along with other social criteria, the posal. authors propose in [23] a new opportunistic routing al- gorithm (SPRINT), which improves the delivery ratio of 4. Network Model messages as compared to traditional social-based routing approaches. In this section, we present our two proposed models A further improvement is JDER [24], a new probabilis- for estimating future values for the inter-contact time (ict, tic forwarding scheme also based on the history of previ- from this point on) and the contact duration (cd, from this ously encountered nodes, one that determines the network point on) metrics. First, in Section 4.1, we describe the cut-nodes, which will increase the probability of reaching functional architecture of the proposed estimation system the destination nodes. Another approach is to use a multi- and the required data. Then, in Section 4.2, we present our objective model and decision tree based mechanism for first estimation function based on a simple linear regres- optimising data dissemination under different target per- sion model. Finally, in Section 4.3, we complement this formances [25]. estimation function by proposing a second model based Additionally, other works like [26] estimate OppNet on linear mixed models. We provide in Algorithm 1 a the inter-contact time of nodes by analysing real mobil- list of the procedures needed to build the two models pro- ity traces. Studies like [5] have proven that the aggregate posed. Along with the network model description, we will inter-contact times distribution in OppNet can be fitted reference the related lines of the algorithm for the sake of to an exponential distribution for scenarios where nodes clearness. are vehicles. Instead, in [27], a similar exponential model for scenarios where nodes are human is proposed. Some 4.1. Functional architecture and dataset other works propose compound distributions to explain the The final objective of the proposed linear estimation inter-contact time. For example, in [26], the authors prove models is to provide a module (or object) that can estimate 4 LinearEstimation based on the current information. This information is up- dated when a new contact starts or ends. In OppNet, two Estimate_cd nodes contact each other if, by means of any neighbour Query DataSet discovery protocol, they find that they are within their communication range. Therefore, this neighbour discovery Estimate_ict protocol 1 module is required to detect new contacts (and Update their durations) and then to notify the LinearEstimation module. Therefore, when a connection is detected, the On_Start_Contact On_End_Contact On Start Contact method is called to calculate the cur- rent measured (ictm ) as (see line 3 from Algorithm 1): Start contact End contact event event ictm = time.now() − lasttimecontacted (9) where time.now() is the current time and lasttimecontacted Exchange Neighbour discovery data msg is the last time the node contacted any other node2 . In the Monitoring very same way, when a contact ends, the On End Contact method is called and the current cd value updated (line 14 Network Interface from Algorithm 1): cdm = time.now() − startcontact (10) Figure 1: Architecture of the estimation module. where startcontact is the time when the current contact with the node started. Note that the global variable startcontact Algorithm 1 Functions for LinearEstimation module. is updated when a new contact starts, and lasttimecontacted 1: procedure On Start Contact(node) is updated when a contact ends (lines 5 and 15 from Al- 2: if not first contact then gorithm 1). 3: ictm = time.now() - lasttimecontacted 4: end if Additionally, the node keeps an exponential moving 5: startcontact = time.now() average of the two studied metrics that get updated in the 6: ewmaict = ewmaict + σict × (ictm − ewmaict ) 7: dataset.add ict(ictm ,ewmaict ,wframe) On Start Contact and On End Contact in the following 8: if mixed then way (lines 6 and 16 from Algorithm 1): 9: dataset2 = exchangedata(dataset) 10: dataset.update(dataset2 ) 11: end if ewmaict = ewmaict + σict × (ictm − ewmaict ), 12: (11) end procedure ewmacd = ewmacd + σcd × (cdm − ewmacd ), 13: procedure On End Contact(node) 14: cdm = time.now() - startcontact 15: lasttimecontacted = time.now() where σict ∈ [0, 1] and σcd ∈ [0, 1] are the exponential mov- 16: ewmacd = ewmacd + σcd × (cdm − ewmacd ) ing average weight constants for giving different weights to 17: dataset.add cd(cdm ,ewmacd ,wframe) 18: end procedure historical measured values and new ones. 19: function Estimate ict return ict In order to estimate the ict and cd values, every node 20: if mixed then 21: (int,slope,ewmaict )=mxmodel ict(dataset,node) node locally builds a dataset DSnode , that contains a list 22: ict = int + slope × ewmaict of sample units: 23: else 24: (α,β,ewmaict )=lnmodel ict(dataset) 25: ict = α + β × ewmaict DSnode = {ds1 , ds2 , ..., ds|DSnode | } (12) 26: end if 27: end function In turn, every element dsd (d = 1, . . . , |DSnode |) that 28: function Estimate cd return cd 29: if mixed then belongs to dataset DSnode consists of five elements: 30: (int,slope,ewmacd )=mxmodel cd(dataset,node) 31: cd = int + slope × ewmacd dsd = [typed , measuredd , ewmad , timed , samplerd ] (13) 32: else 33: (α,β,ewmacd )=lnmodel cd(dataset) 34: cd = α + β × ewmacd where typed is the type of metric (ict or cd), measuredd is 35: end if a measured value for any of the two studied metrics (cal- 36: end function culated using equations 9 and 10), ewmad is the value for their corresponding exponential average (calculated using the ict and cd values from the collected information of equation 11), timed is the time when the metric was mea- previous contacts, which can be used, for example, by the sured and samplerd is the identification of the node that routing protocols. A possible functional structure of this module (LinearEstimation) is depicted in Figure 1. We 1 This module is provided by every OppNet implementation and also provide an algorithmic implementation of the main it is outside of the scope of this paper. 2 Note that for the first contact we cannot obtain an ict value as methods of this module in Algorithm 1. The main interface of the LinearEstimation module there is no previous contact. consists of two methods for obtaining the cd and ict values 5 sampled the measured value3 . The local dataset is up- 4.2.2. Estimation function dated with new ict entry when a new contact starts (line Consequently, a node node that at a given time has 7 from Algorithm 1) and with a new cd when the contacts measured and calculated m sample values can calculate ends (line 17 from Algorithm 1). the estimation for the future values of ict and cd as: In order to reduce the size of these datasets, we define ictm+1 = αict + βict × ewmaictm a temporal window frame of size wframe. That is, old ele- (18) cdm+1 = αcd + βcd × ewmacdm ments are not considered from the current dataset DSnode if the entries are older than wframe: where the α and β values can be obtained using equa- tions 3 and 4 detailed in section 2. The implementation of these estimations is shown in Algorithm 1, where the DSnode (wframe) = {ds1 , ds2 , ..., ds|DS 0 } ⊆ DSnode node | Estimate ict and Estimate cd functions calculate first the | ∀dsd = typed , measuredd , ewmad , timed , samplerd , α, β and ewma values using the dataset through functions dsd ∈ DSnode ⇒ time.now() − timed < wframe. lnmodel ict and lnmodel cd for later applying equation 18 (14) (lines 25 and 34). where time.now() is the current time and wframe indi- cates a period of time during which samples may be con- 4.3. Linear mixed model sidered. This also reduces the size of the messages ex- In the previous subsection, we have proposed a linear changed. As we will see in Section 4.3, in our mixed model, regression model for predicting future values for ict and when a contact occurs, both nodes exchange their datasets cd in terms of the already measured ones. Every node (using function exchangedata, line 9 from Algorithm 1). performed independent linear regression models. In this Therefore, when two nodes node1 and node2 meet, with section, we extend our proposal by allowing nodes to share datasets DSnode1 and DSnode2 , respectively, they update their measured values for both metrics in order to obtain their datasets: a more elaborate linear regression mixed model. DSnode1 = DSnode1 ∪ DSnode2 (15) DSnode2 = DSnode2 ∪ DSnode1 4.3.1. Model definition This procedure is performed in both contacted nodes using As explained in Section 2.2, mixed models are very use- dataset.update, as shown in the Algorithm 1, line 10. ful in contexts where data are clustered or hierarchically Finally, the impact of the wframe variable will be anal- organised. In our mixed model, the information gathered ysed in Section 5, to see its performance on our proposal. is clusterised, thus creating groups. These groups are the different nodes in the network. So, as random factors, 4.2. Linear regression model we use the qualitative variable node, which represents the In this section, we introduce the first estimation func- original node that measured the information, and, as fixed tion, based on a simple regression model. effects, we use the studied metrics and their corresponding exponential moving averages. The two expressions of ran- 4.2.1. Model definition dom intercept models below represent our proposed mixed After ending a contact with its nth contacted node, any models. given node in the network collects a dataset of n−1 sample First, we model the inter-contact time (ictd+1 ) as a units for the pair of values icti : ewmaicti , i = 1, . . . , n − 1 linear function of ewmaictd , where the intercept is allowed and n samples for cdi : ewmacdi , i = 1, . . . , n following to change per each node (nodei = 1, . . . , N ). In this model, equations 9 - 11. Given these previous values, we propose nodei is a factor with as many levels as nodes considered in a model for explaining the values of icti+1 in terms of the networks, where N is the maximum number of nodes in ewmaicti , and the values of cdi+1 in terms of ewmacdi the network. This means that nodes group their datasets using a bivariate linear regression model as: in N clusters of ni sample units for each group: icti+1 = αict + βict × ewmaicti + icti icti,j+1 = αict + βict 1 × nodei + βict 2 × ewmaictij + ictij (16) i = 1, . . . , N ; j = 1, . . . , ni cdi+1 = αcd + βcd × ewmacdi + cdi (19) where There are two components in this model that include icti ∼ N (0, σict 2 ), icti ∼ N (0, σcd 2 ) (17) explanatory variables: the fixed one, βict 2 × ewmaictij , Thus, icti+1 and cdi+1 are the response variables ex- and the random one, βict 1 × nodei , which represents the plained by ewmaicti and ewmacdi , respectively. The in- ict : ewmaict effect for every node. Each node is allowed to formation not explained by these models is defined by the have a different ict : ewmaict relationship. Our model con- residuals ict and cd , which are assumed to be normally siders the type of mixed model where the different nodes distributed with expectation 0 and variance σict 2 and σcd 2 , have the same slope, with different intercepts per node. respectively. We are using node as a random effect, assuming that the variations on the intercept for each node is normally dis- 3 Note that a sampler node may be a different node from the one tributed with a certain variance. This means that the dif- that keeps the sample unit. ferences per node regarding the intercept are small. Thus, 6 ictij represents the errors that are normally distributed from these mobility traces represent 41 students car- with covariance matrix Σ, Σ = σ 2 × I. rying iMote platforms5 . The number of contacts pro- Secondly, in the very same way, we proposed the fol- vided in these traces is 22,459. lowing mixed model to estimate the contact duration: • The second scenario, the Cambridge scenario, as pub- cdi,j+1 = αcd + βcd 1 × nodei + βcd 2 × ewmacdij + ictij lished in [30], is based on real Bluetooth traces from i = i, . . . , N ; j = 1, . . . , ni students from the System Research Group of the (20) University of Cambridge, UK, carrying small devices Once both mixed models are defined, as explained in for six days. Additionally, some stationary nodes Section 2.2, we can extract its coefficients, that is, the were placed at various points of interest. The num- common slopes (slopeict and slopecd , for the ict and cd ber of contacts provided in these traces is 10,873. mixed model, respectively) and a list of intercept values for the different nodes (interceptict i and interceptcd i , i = • The third scenario, the MIT scenario, as published 1, . . . , N , for the ict and cd mixed model, respectively). in [31], represents the activity information from 100 subjects at the Massachusetts Institute of Technol- 4.3.2. Estimation function ogy over the course of the 2004-2005 academic year. Consequently, a node (node) that for a given time has The number of contacts provided in these traces is obtained mict and mcd sample values in its dataset DSnode 102,593. may calculate the estimation for the future values of ict • The fourth scenario, the Asturias scenario, as pub- and cd as: lished in [32], contains connectivity traces extracted ictmict +1 = interceptict node + slopeict × ewmaictmict from GPS traces obtained from the regional Fire De- (21) cdmcd +1 = interceptcd node + slopecd × ewmacdmcd partment of Asturias, Spain. This data was gener- ated by GPS devices embedded in different vehicles where interceptict node and interceptcd node are the inter- such as cars, trucks and a helicopter and a few per- cept values for node node extracted from the ict and cd sonal radios. In total, 229 devices reported 3,098,642 mixed models, slopeict and slopecd their common slopes, contacts. and ewmaictmict and ewmacdmcd the last ewmaict and ewmacd values calculated. The implementation of these • The fifth scenario, the Taxis scenario, as published estimations is shown in Algorithm 1 (lines 22 and 31), in [33], contains mobility traces from 320 taxi cabs where the Estimate ict and Estimate cd functions calcu- in Rome over 30 days. The number of contacts pro- late first the intercept (int), slope and ewma values using vided in these traces is 224,588. the dataset through functions mxmodel ict and mxmodel cd, to be applied later in equation 18. A summary with the general characteristics of the sce- narios can be found in Table 1. Although the traces have different durations, in all cases we have only used the first 5. Evaluation 24 hours in order to compare results using equivalent time intervals. In this section, we present the experiments carried out The traces data are analysed to obtain information to evaluate the performance of our proposal. First, we about ict and cd metrics. Some of these mobility traces present our evaluation methodology used in this experi- contain information on the times when nodes start contact mentation. Then, we present the results. and end their encounters. Some others, such as the Taxis trace, contains GPS coordinates instead. For this type of 5.1. Evaluation methodology traces, we assume a range of 10m to obtain the informa- For the experiments conducted for this article, we chose tion on when the encounter starts and finishes (which can five different scenarios to analyse the performance of our resemble a typical Bluetooth range). Once the five traces proposal. The physical encounters for the five different were analysed, considering only the first 24 hours, we ob- scenarios were obtained from real mobility traces from the tained a dataframe with the following fields6 : Crawdad database4 , a community resource for collecting wireless data at Dartmouth College, United States. The • Type: represents the type of sample unit: ict or cd. five scenarios are the following: • Sampler: name of the node that has measured the • The first scenario, the Info5 scenario, is based on real sample. mobility traces, as published in [30]. These traces were retrieved during the 2005 edition of the Infocom 5 An iMote is a simple device made by Intel Research based on conference over the course of 2.97 days. Contacts a Zeevo TC2001P system-on-a-chip providing an ARM7 processor, Bluetooth connectivity and a 950mAh CR2 bakery. 6 Dataframe with all the traces and metric values can be requested 4 Mobility at: traces can be found at http://crawdad.org/. http://deic.uab.es/~cborrego/linear.html 7 Info5 Cambridge Taxis MIT Asturias 0.006 0.003 0.0020 0.006 0.006 Frequency Metric 0.004 0.0015 0.002 0.004 cd 0.004 0.0010 0.002 0.001 ict 0.002 0.002 0.0005 0.000 0.000 0.000 0.0000 0.000 0 500 1000 1500 2000 0 500 1000 1500 2000 0 500 1000 1500 2000 0 500 1000 1500 2000 0 500 1000 1500 2000 Time (s) Time (s) Time (s) Time (s) Time (s) Figure 2: Inter contact time and contact duration histograms for the five different scenarios. Info5 Cambridge Taxis MIT Asturias 10.0 10.0 10.0 9 9 7.5 7.5 7.5 log(ict) 6 6 5.0 5.0 5.0 3 3 2.5 2.5 2.5 0 0 0.0 0.0 0.0 2.5 5.0 7.5 10.0 0.0 2.5 5.0 7.5 10.0 0.0 2.5 5.0 7.5 10.0 4 6 8 4 6 8 10 log(ewma) log(ewma) log(ewma) log(ewma) log(ewma) (a) Linear model icti+1 = αict + βict × ewmaicti + ict . Info5 Cambridge Taxis MIT Asturias 10.0 10.0 9 9 9 7.5 7.5 log(cd) 6 6 5.0 5.0 6 3 3 2.5 2.5 3 0 0 0.0 0.0 2.5 5.0 7.5 3 5 7 0.0 2.5 5.0 7.5 10.0 6 7 8 9 2 4 6 8 log(ewma) log(ewma) log(ewma) log(ewma) log(ewma) (b) Linear model cdi+1 = αcd + βcd × ewmacdi + cdi . Figure 3: ict and cd general linear models after 24 hours for every node in the network. Colour circles represent metric values from the different nodes in the network. The circle colour is used to differentiate the different nodes. The grey lines depict their corresponding general linear models. • Custodier: name of the node that keeps the sample The evaluation results presented in the following sec- unit. tion have been performed by analysing this dataframe us- ing the statistical tools R, MATLAB, and Python7 . • Value: inter-contact time or contact duration sam- Finally, for the values of σict and σcd in equations 11, ple unit (seconds). we have used the constant value 0.7, as in classical pro- • Ewma: exponential weight moving average of inter- posals such as [34, 35, 36], and wframe was initially set to contact time or contact duration before the sample 24h. unit was obtained. 5.2. Performance evaluation • Time: time of the sample unit (seconds) The goal of this section is to evaluate the performance of our estimation proposals by comparing them with other • Scenario: name of the scenario well-known methods for estimating ict and cd. We present For example, an entry of our dataset containing the fol- the different methods that will be compared in this evalu- lowing values: ation as follows: • Linear model (LM in the figures) as explained in Type Sampler Custodier Value EWMA Time Scenario Section 4.2. cd x9 x25 30 35 450 Asturias • Linear mixed model (MX in the figures) as explained meaning that node x25 keeps a contact duration sample in Section 4.3. unit learned from x9 that was sampled at time 450 seconds with a value of 30 seconds and the previous calculated 7 Source code for the statistical tools can be requested at: EWMA was 35 seconds. http://deic.uab.es/~cborrego/linear.html 8 (a) Mixed model model ictij+1 = αict + βict 1 × nodei + βict 2 × ewmaictij + ictij . (b) Mixed model cdij+1 = αcd + βcd 1 × nodei + βcd 2 × ewmacdij + ictij . Figure 4: ict and cd linear mixed models after 24 hours for every node in the network. Colour circles represent metric values from the different nodes in the network. The circle colour is used to differentiate the different nodes. The grey lines depict their corresponding mixed models. The black lines depict the population models. • Pareto distribution (PD in the figures). The estima- Finally, in order to evaluate the performance of the tion of the inter-contact time and contact duration is different proposals, we have defined the following error performed using a Pareto distribution, which is pre- estimation: for a certain metric (ict or cd), we compute the viously calculated using the whole contact trace, as average of the estimation error of a node with ni samples in proposals like [37]. of the studied metric as: ni • Exponential distribution (XD in the figures). This P |estimatedn − measuredn | is similar to PD but using an exponential distribu- Errornodei = n=1 (22) tion, as in proposals like [5]. Note that both PD ni and XD are offline methods and therefore cannot Before analysing the different estimation proposals, it be implemented in the nodes. is interesting to depict the distribution of the measured inter-contact time and contact duration for the five sce- • Pareto (PW in the figures). The estimation of the narios (Figure 2). As can be seen, the histograms of the inter-contact time and contact duration is performed five different scenarios are very different. As can be seen using a Pareto distribution as well, but, this time is by the way these metrics are distributed, their estimation built by every node from previously collected sam- is a difficult challenge. ples. We depict the different models obtained from the traces • Exponential (EX in the figures). Similar to PW but to show the correlation between the exponential moving using an exponential distribution. averages of the historical values of the studied metrics and their corresponding future observed values. In Figure 3(a) • Median (MD in the figures). In this case, the esti- and Figure 3(b), we depict the linear regression model in- mation of the inter-contact time and contact dura- troduced in Section 4.2 for the ict metric and the cd met- tion is performed using the median from the previous ric for every node in the five different scenarios and for 24 samples, as in proposals like [38]. hours of activity. As can be seen, the nodes belonging to the Info5 scenario have similar slopes in the different mod- • Moving Average (MA in the figures). The estima- els, while in the other scenarios, the slopes and intercept tion of the inter-contact time and contact duration is vary significantly for the different nodes in the network. performed using the exponential moving average cal- Similarly, in Figure 4(a) and Figure 4(b), we depict the re- culated from previous samples, as in proposals like sults for the mixed regression models introduced in Section [7]. 9 Info5 Cambridge Taxis MIT Asturias 1250 2500 Estimation Error (s) 2500 600 1500 1000 Estimator 2000 2000 LM 1500 1000 750 400 1500 MX 1000 1000 500 PD 200 500 500 500 250 XD 0 0 0 0 0 LM MX PD XD LM MX PD XD LM MX PD XD LM MX PD XD LM MX PD XD (a) Performance study for inter-contact time estimation. Info5 Cambridge Taxis MIT Asturias 1250 2500 Estimation Error (s) 2500 600 1500 1000 Estimator 2000 2000 LM 1500 1000 750 400 1500 MX 1000 1000 500 PD 200 500 500 500 250 XD 0 0 0 0 0 LM MX PD XD LM MX PD XD LM MX PD XD LM MX PD XD LM MX PD XD (b) Performance study for contact duration. Figure 5: Performance study. Our linear model (LM) and mixed model (MX) versus using classical distributions such as Pareto (PD) and Exponential (XD) for estimating the two studied metrics ict and cd. 4.3. In this case, the thin lines represent the mixed models Scenario Nodes Contacts Best ict Best cd for the different nodes, while the dark line represents the Info5 41 10,152 MX MX Cambridge 51 1,216 LM MX population model, that is, the model that contains all the Taxis 304 6,506 LM LM nodes. MIT 97 5,042 MX MX Asturias 230 12,705 LM LM We then proceed to compare the performance in esti- mating for the different methods. We divide these com- Table 1: Main parameters of the scenarios. The number of contacts parisons into two. In the first one, we compare our esti- corresponds to the 24h traces extract used. Finally, the columns mation functions against the PD and XD models, where “Best ict” and “Best cd” represent which method from the ones the distribution is previously calculated. Note that these proposed in this study performs better. models are only considered to be a reference, since they consider the whole contact trace for estimating the values, in terms of estimation error than the general linear model and therefore, cannot be implemented in the nodes. In does. These results are shown in Table 1. With data avail- Figure 5(a) and Figure 5(b), we depict the error estima- able for only 5 scenarios, it is difficult to provide a general tion distribution, as defined in equation 22, for every node criterion to define which proposal fits best for a general in the five different scenarios. scenario. In the second type of comparison, we analyse the other proposals where the distributions of the behaviour of the 5.3. Autocorrelation analysis and EWMA dependence network are ignored by the nodes in the network and deci- sions are taken in terms of observed events, that is, expo- The main objective of this paper is to predict the fu- nential moving average (MA), the historical median (MD), ture values of the inter-contact times (ict) and contact the exponential distribution (XP) and the Pareto distri- durations (cd) of the nodes based on the history of their butions (PW). The results are shown in Figure 6(a) and previous contacts. Therefore, these contacts need to have Figure 6(b). As can be seen, our proposals –general linear some kind of regularity. Formally, the values in the time model (LM) and mixed model (MX)– outperform all of series of nodes contacts must exhibit some degree of auto- the other compared proposals in terms of the estimation correlation. error for estimating both ict and cd in all of the studied This autocorrelation is the basis of the EWMA esti- scenarios. mation. Concretely, EWMA estimation is based on giving When comparing our two proposals in terms of the es- more weight to recent values of a measured times series, timation error obtained for the ict metric, the scenario where the coefficient α represents the degree of weighting where the mixed model performs better than the general decrease. There is a strong dependence between EWMA linear model is the Info5 scenario. Instead, for the cd met- and autocorrelation: highly autocorrelated time series will ric, in three scenarios, our mixed model performs better produce better estimations. On the contrary, time series 10 Info5 Cambridge Taxis MIT Asturias 2500 1250 Estimator Estimation Error (s) 2500 600 1500 EX 2000 1000 2000 LM 1500 1000 750 400 1500 MA 1000 1000 500 MD 200 500 500 500 250 MX 0 0 0 0 0 PW EX LM MA MD MX PW EX LM MA MD MX PW EX LM MA MD MX PW EX LM MA MD MX PW EX LM MA MD MX PW (a) Performance study for inter-contact time. Info5 Cambridge Taxis MIT Asturias 500 1250 1500 1000 Estimator Estimation Error (s) 1500 EX 400 1000 750 LM 1000 1000 300 750 500 MA 200 500 500 500 MD 250 100 250 MX 0 0 0 0 0 PW EX LM MA MD MX PW EX LM MA MD MX PW EX LM MA MD MX PW EX LM MA MD MX PW EX LM MA MD MX PW (b) Performance study for contact duration. Figure 6: Performance study. Our linear model (LM) and mixed model (MX) versus built exponential distribution (EX), exponential moving average calculated from previous samples (MA), median from the previous samples (MD), built Pareto distribution (PW) for estimating the two studied metrics ict and cd. with no autocorrelation (for example, white noise) are not tain reasonable estimations of future ict and cd values, as predictable, and indeed, in these cases EWMA is useless. is evidenced by the results obtained in the previous sub- The coefficient of correlation between two values in a section. time series is called the autocorrelation function (ACF). It evaluates the autocorrelation between values that are 5.4. Overhead evaluation and optimisation k time periods apart (known as lag k). Note that in our As introduced in Section 4.3, our proposed mixed model case, the measurement intervals are not constant since new allows nodes to share their measured values for both met- values are obtained when a contact occurs. Concretely, we rics in order to obtain a more elaborate linear regression have obtained the ACF for the ict and cd time series from mixed model. To learn the amount of overhead implied by the traces used in this paper. Formally, we obtained a the exchange of messages when implementing our mixed time series for the contact of every node m of the traces: model, in Figure 8, we analyse the number of exchanged {ictm }, {cdm }. messages as a function of the scenario trace time. Four dif- In general, all used traces exhibit some degree of auto- ferent types of analysis are performed for the two studied correlation, as shown in the boxplots in Figure 7. These metrics: ict − total and cd − total, when all of the infor- plots were obtained in the following way: for a given lag mation observed by nodes is shared upon node encounter number and trace, we obtain the autocorrelation values and ict − lim and cd − lim, when only messages belonging for all the ict and cd time series of all nodes. The final to a window frame of two hours are used (see Section 4.3 result is two vectors with all the autocorrelations. We for the window frame definition). As expected, by limiting repeated this procedure for all traces and for lag values the window frame, we obtain a lower number of exchanged between 1 and 10. Then, the distribution of all the au- messages per contact. The number of exchanged messages tocorrelations is displayed using a boxplot, showing the observed seems reasonably small for OppNet. On the other minimum and maximum values and the interquartile range hand, when not limiting the number of exchanged mes- between a first quartile (Q1=25%) and the third quartile sages using the window frame, the number of exchanged Q3=75%). The results show that in all the traces, a high messages could affect the performance of the network, es- proportion of nodes have (at least) autocorrelations higher pecially in scenarios like the Taxis scenario, where there than 0.1. Furthermore, nodes exhibit higher autocorrela- is a large number of nodes. The value of two hours has tions for lower lag values by displaying wider interquartile been chosen by analysing the performance in terms of the ranges. error estimation when compared to the window frame. As Summing up, two main conclusions can be drawn from can be seen in Figure 9, the wframe value of two hours is a these results. First, there is a clear dependence between good compromise value with reasonable results in terms of values of recent contacts, and second, that using recent the error estimation for the two studied metrics, for both values for predicting new values, as EWMA does, can ob- general and mixed models in the five scenarios. 11 ICT Info5 ICT Cambridge ICT Taxis ICT MIT ICT Asturias 0.6 0.50 0.50 0.50 0.4 0.4 0.25 0.25 0.25 0.2 0.0 0.00 0.00 0.00 -0.25 -0.25 0.0 -0.25 -0.4 -0.50 -0.2 -0.50 -0.50 -0.75 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 Lag Lag Lag Lag Lag (a) Autocorrelation study for inter-contact time. CD Info5 CD Cambridge CD Taxis CD MIT CD Asturias 0.50 0.50 0.50 Autocorrelation 0.6 0.4 0.25 0.25 0.4 0.25 0.0 0.00 0.00 0.2 0.00 -0.25 -0.25 -0.25 -0.4 0.0 -0.50 -0.50 -0.50 -0.8 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 Lag Lag Lag Lag Lag (b) Autocorrelation study for contact duration. Figure 7: Autocorrelation study for the sampled values of the two studied metrics ict and cd. Number of messages (#) Info5 Cambridge Taxis MIT Asturias 50 100 Type 60 40 7.5 75 200 cd-lim 30 40 ict-lim 20 50 5.0 100 20 cd-total 10 25 0 0 2.5 ict-total 0 0 0 5 10 15 20 25 0 5 10 15 20 0 5 10 15 20 25 0 5 10 15 20 0 5 10 15 20 25 Trace time (hours) Trace time (hours) Trace time (hours) Trace time (hours) Trace time (hours) Figure 8: Number of messages exchanged as a function of time. Now, in Figure 10, we analyse the CPU overhead cost that exponential moving averages from historical metrics in terms of CPU seconds8 . We see that the generic linear observed for both metrics are correlated with their corre- models are not very sensitive to the size of the samples, sponding future values. while mixed models are. However, the amount of time Particularly, we have proposed two independent esti- needed for calculating the model is very small, considering mation functions based on two linear models: a general as well that this calculation can be computed at any time linear regression model and a linear mixed model. We and not necessary when performing the routing or delivery have shown, by using five different real mobility traces action. from well-known Opportunistic Networks scenarios, that Summing up, although the regression mixed model has our estimation functions greatly improve the estimation a slightly greater overhead than the linear model, mainly of future values for the studied metrics when compared due to its collaborative approach, in scenarios with a lower to other well-known proposals in terms of the error es- number of nodes it can obtain the better estimation. timation. Furthermore, these estimation models can be easily implemented and integrated into current OppNet 6. Conclusions routing protocols, thus enabling improved performance in their routing decisions with no significant overhead. In this paper, we have analysed the problem of esti- mating future values of the inter-contact time and the con- tact duration in Opportunistic Networks. We have shown Acknowledgements 8 Measured The authors thank Teresa Rosas and Llorenç Badiella using a Raspberry Pi Broadcom BCM2835 SoC full HD, 700MHz Low Power ARM1176JZ-F, 512MB SDRAM, 4GB SD for their generous help with the statistics explanation and with Raspbian. 12 ict (LM) cd (LM) ict (MX) cd (MX) Estimation Error (s) 800 Scenario 1000 700 Asturies 600 800 600 Cambridge 1000 600 500 Info5 400 400 400 500 MIT 300 Taxis 200 0 2 4 6 0 2 4 6 0 2 4 6 0 2 4 6 wframe (hours) wframe (hours) wframe (hours) wframe (hours) Figure 9: Error estimation as a function of the window frame for estimating the two studied metrics (ict and cd) using the general linear model (LM) and the mixed model (MX). CPU Time 0.15 CPU Time (s) Estimator 0.10 LM 0.05 MX 0.00 0 2000 4000 6000 8000 Number of samples Figure 10: CPU time model calculation as a function of the number of samples. R programming. This work was supported by LASIGE Re- [11] A. Zuur, E. Ieno, N. Walker, A. Saveliev, G. Smith, Mixed ef- search Unit, ref. UID/CEC/00408/2013, by the Catalan fects models and extensions in ecology with R. Gail M, Kricke- berg K, Samet JM, Tsiatis A, Wong W, editors, Spring. AGAUR 2017SGR-463 project and the Spanish Ministry [12] R. C. Littell, G. A. Milliken, W. W. Stroup, R. D. Wolfinger, of Science and Innovation TIN2017-87211-R project. O. Schabenberger, SAS for mixed models, SAS institute, 2007. [13] N. Chakchouk, A survey on opportunistic routing in wireless communication networks, IEEE Communications Surveys & References Tutorials 17 (4) (2015) 2214–2241. [14] V. F. Mota, F. D. Cunha, D. F. Macedo, J. M. Nogueira, A. A. [1] L. Pelusi, A. Passarella, M. Conti, Opportunistic networking: Loureiro, Protocols, mobility models and tools in opportunistic data forwarding in disconnected mobile ad hoc networks, Com- networks: A survey, Computer Communications 48 (2014) 5–19. munications Magazine, IEEE 44 (11) (2006) 134–141. [15] A. Passarella, M. Conti, Analysis of individual pair and ag- [2] S. Batabyal, P. Bhaumik, Improving network performance with gregate intercontact times in heterogeneous opportunistic net- affinity based mobility model in opportunistic network, in: works., IEEE Trans. Mob. Comput. 12 (12) (2013) 2483–2495. Wireless Telecommunications Symposium (WTS), 2012, IEEE, [16] E. Hernández-Orallo, J. C. Cano, C. T. Calafate, P. Manzoni, 2012, pp. 1–7. New approaches for characterizing inter-contact times in oppor- [3] K. Watabe, H. Ohsaki, Contact duration-aware epidemic broad- tunistic networks, Ad Hoc Networks 52 (2016) 160–172. casting in delay/disruption-tolerant networks, IEICE Transac- [17] Y. Song, J. Li, C. Li, F. Wang, Social popularity based rout- tions on Communications 98 (12) (2015) 2389–2399. ing in delay tolerant networks., International Journal on Smart [4] C. Borrego, G. Garcia, S. Robles, Softwarecast: a code-based Sensing & Intelligent Systems 9 (4). delivery manycast scheme in heterogeneous and opportunistic [18] X. Zhuo, Q. Li, G. Cao, Y. Dai, B. Szymanski, T. La Porta, ad hoc networks, Ad Hoc Networks. Social-based cooperative caching in DTNs: A contact duration [5] H. Zhu, L. Fu, G. Xue, Y. Zhu, M. Li, L. M. Ni, Recognizing aware approach, in: Mobile Adhoc and Sensor Systems, IEEE exponential inter-contact time in vanets, in: INFOCOM, 2010 8th International Conference on, 2011, pp. 92–101. Proceedings IEEE, IEEE, 2010, pp. 1–5. [19] X. Zhuo, Q. Li, W. Gao, G. Cao, Y. Dai, Contact duration [6] H. Dang, H. Wu, Clustering and cluster-based routing proto- aware data replication in delay tolerant networks, in: Network col for delay-tolerant mobile networks, IEEE Transactions on Protocols (ICNP), 2011 19th IEEE International Conference on, Wireless Communications 9 (6) (2010) 1874. IEEE, 2011, pp. 236–245. [7] C. Borrego, A. Sánchez-Carmona, Z. Li, S. Robles, Explore [20] S.-H. Kim, Y. Jeong, S.-J. Han, Use of contact duration for mes- and wait: A composite routing-delivery scheme for relative sage forwarding in intermittently connected mobile networks, profile-casting in opportunistic networks, Computer Networks Computer Networks 64 (2014) 38–54. 123 (2017) 51–63. [21] N. Magaia, C. Borrego, P. Pereira, M. Correia, Privo: A [8] C. Borrego, J. Borrell, S. Robles, Efficient broadcast in oppor- privacy-preserving opportunistic routing protocol for delay tol- tunistic networks using optimal stopping theory, Ad Hoc Net- erant networks, in: IFIP Networking, 2017, pp. 1–9. works 88 (2019) 5–17. [22] R.-I. Ciobanu, R.-C. Marin, C. Dobre, Interaction predictabil- [9] J. Neter, W. Wasserman, M. H. Kutner, Applied linear regres- ity of opportunistic networks in academic environments, Trans. sion models, Irwin Homewood, IL, 1989. Emerg. Telecommun. Technol. 25 (8) (2014) 852–864. [10] C. R. Rao, H. Toutenburg, Linear models, in: Linear models, [23] R. I. Ciobanu, C. Dobre, V. Cristea, SPRINT: social prediction- Springer, 1995, pp. 3–18. 13 based opportunistic routing, in: World of Wireless, Mobile and 2005-07-01) (Jul. 2005). Multimedia Networks, 14th Symposium and Workshops on a, [32] S. Cabrero, R. Garca, X. G. Garca, D. Melendi, CRAWDAD IEEE, 2013, pp. 1–7. dataset oviedo/asturies-er (v. 2016-08-08) (Aug. 2016). [24] R. Ciobanu, D. Reina, C. Dobre, S. Toral, P. Johnson, JDER: A [33] L. Bracciale, M. Bonola, P. Loreti, G. Bianchi, R. Amici, history-based forwarding scheme for delay tolerant networks us- A. Rabuffi, CRAWDAD dataset roma/taxi (v. 2014-07-17) (Jul. ing jaccard distance and encountered ration, J. Netw. Comput. 2014). Appl. 40 (C) (2014) 279–291. [34] M. Mirza, K. Springborn, S. Banerjee, P. Barford, M. Blodgett, [25] D. G. Reina, R. Ciobanu, S. Toral, C. Dobre, A multi-objective X. Zhu, On the accuracy of TCP throughput prediction for optimization of data dissemination in delay tolerant networks, opportunistic wireless networks, in: Sensor, Mesh and Ad Hoc Expert Systems with Applications 57 (2016) 178 – 191. Communications and Networks, 2009. SECON’09. 6th Annual [26] T. Karagiannis, J.-Y. Le Boudec, M. Vojnovic, Power law and IEEE Communications Society Conference on, IEEE, 2009, pp. exponential decay of intercontact times between mobile devices, 1–9. IEEE Transactions on Mobile Computing 9 (10) (2010) 1377– [35] Q. He, C. Dovrolis, M. Ammar, On the predictability of large 1390. transfer tcp throughput, in: ACM SIGCOMM Computer Com- [27] R. Groenevelt, P. Nain, G. Koole, The message delay in mobile munication Review, Vol. 35, ACM, 2005, pp. 145–156. ad hoc networks, Performance Evaluation 62 (1-4) (2005) 210– [36] M. Mirza, J. Sommers, P. Barford, X. Zhu, A machine learning 228. approach to tcp throughput prediction, in: ACM SIGMETRICS [28] M. Abdulla, R. Simon, The impact of intercontact time within Performance Evaluation Review, Vol. 35, ACM, 2007, pp. 97– opportunistic networks: protocol implications and mobility 108. models, TechRepublic White Paper. [37] A. Passarella, M. Conti, Characterising aggregate inter-contact [29] G. Zyba, G. M. Voelker, S. Ioannidis, C. Diot, Dissemination in times in heterogeneous opportunistic networks, in: Interna- opportunistic mobile ad-hoc networks: The power of the crowd, tional Conference on Research in Networking, Springer, 2011, in: INFOCOM, 2011 Proceedings IEEE, IEEE, 2011, pp. 1179– pp. 301–313. 1187. [38] A. Chaintreau, P. Hui, J. Crowcroft, C. Diot, R. Gass, J. Scott, [30] D.-G. Akestoridis, CRAWDAD dataset uoi/haggle (v. 2016- Impact of human mobility on opportunistic forwarding algo- 08-28): derived from cambridge/haggle (v. 2009-05-29) (Aug. rithms, IEEE Transactions on Mobile Computing 6 (6) (2007) 2016). 606–620. [31] N. Eagle, A. S. Pentland, CRAWDAD dataset mit/reality (v. 14