# Exploiting Communication Opportunities in Disrupted Network Environments

Lefteris Mamatas, Alexandra Papadopoulou, Vassilis Tsaoussidis

► To cite this version:

Lefteris Mamatas, Alexandra Papadopoulou, Vassilis Tsaoussidis. Exploiting Communication Opportunities in Disrupted Network Environments. 13th International Conference on Wired/Wireless Internet Communication (WWIC), May 2015, Malaga, Spain. pp.180-193, 10.1007/978-3-319-22572-2_13. hal-01728821

HAL Id: hal-01728821

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

Submitted on 12 Mar 2018

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
# Exploiting Communication Opportunities in Disrupted Network Environments

Lefteris Mamatas<fnref n="1" />, Alexandra Papadopoulou<fnref n="2" />, and Vassilis Tsaoussidis<fnref n="2" />

**Abstract.** The capability of a mobility model to detect certain patterns of user behavior (e.g., favorite walks or walking habits) enables solutions for a number of challenging networking problems, including efficient opportunistic communications and handoff / cellular planning. We argue that the limited viewpoint of a single mobile node and its scarce resources (e.g., energy, memory or processing) are major obstacles for accurate estimations. Targeting at hybrid network environments, we offload prediction capabilities to the fixed nodes that may be available in the area, offering a global view and the capability of resource-demanding calculations.

Here, we introduce a solution running on top of the infrastructure nodes that: (i) implements a mobility model which provides a number of mobility forecasts to the mobile users in the area, (ii) supports proactively the routing decisions of opportunistic mobile devices being taken at times there is not connectivity. We introduce the corresponding semi-Markov model and demonstrate its efficiency using scenarios deployed in a preselected city center, where a number of mobile nodes seek for Internet access.

**Keywords:** Delay-Tolerant Networks, Opportunistic Networks, Infrastructure-supported Mobile Communication, Mobility Prediction

## 1 Introduction

Internet is entering a new era, in which sophisticated devices can be deployed anywhere, run demanding applications and require connectivity occasionally or permanently. Various challenging networks have been introduced, initially as

<footnote n="1">¹ University of Macedonia,
Dept. of Applied Informatics,
156 Egnatia Str., 546 36 Thessaloniki, Greece
emamatas@uom.gr</footnote>

<footnote n="2">² Aristotle University of Thessaloniki,
Dept. of Mathematics,
541 24 Thessaloniki, Greece
apapado@math.auth.gr</footnote>

<footnote n="3">³ Democritus University of Thrace,
Dept. of Electrical and Computer Engineering,
12 Vas. Sofias Str., 67100 Xanthi, Greece
vtsaousi@ee.duth.gr</footnote>
stand-alone homogeneous networks that were gradually attached to the Inter-
net. Space Networks [22] are the most recent example; other examples include
the Mobile ad-hoc networks (MANETs), Delay - and disruption - tolerant net-
works (DTNs) [11], and Vehicular ad-hoc networks (VANETS) [13]. This inher-
ent heterogeneity is dominant in today's Internet; however, the properties of such
internetworks are typically studied in the context of the extended network mod-
ule alone (e.g., MANETs, DTNs, VANETS) and not in the appropriate context
of their influence to the global internetwork.

This hybrid setting requires supportive strategies to exploit even the slightest
communication opportunity; let alone the technology to allow for dynamic up-
dates and the capability to continuously seek an optimal solution. In this context,
what appears theoretically possible becomes conditionally feasible, only when
system granularity and routing accuracy can adequately match user-behavioral
and -mobility patterns. Beyond that, the complexity of the task increases if we
also consider device constraints, energy aspects and application diversity.

Here, we claim that infrastructure nodes around areas with poor or inter-
mittent connectivity could collectively build and, based on historical data, train
a stochastic model capable of predicting future contacts. Actually, each fixed
node can trace the coordinates of mobile devices passing by along with their
corresponding connectivity times. Such data can be communicated within the
infrastructure and constitute valuable input for the mobility model, which, in
turn, can produce node-level (i.e., detect mobility patterns of certain nodes),
or system-level estimations (e.g., number of nodes at a certain area after some
time). This allows each mobile node to query the system for information regard-
ing its future contact opportunities and expect by the neighboring fixed node to
reply with a potential suggestion. Such response information could become, for
example, a probability value or the coefficients of a known distribution. The lat-
ter can represent the inter-contact time PDF between a mobile/class of mobiles
and other mobiles or Internet hotspots.

So, the moving device can calculate the cost functions associated with po-
tential tactics - from holding data further, to forwarding to another node and
also to which particular direction - and make a decision with respect the delivery
time of the data or, perhaps, the certainty to reach the destination within some
required timeframe. It is obvious that storing the data in the source mobile un-
til a new hotspot appears is a conservative strategy that misses communication
opportunities. Furthermore, 3G networks are often expensive and unavailable.
In experiments documented in [3], in places 3G is not available there is WiFi
availability roughly half of the time. In our experience, forwarding decisions can
be taken with a level of accuracy that can be occasionally high (when the sce-
nario allows) although communication and processing overhead could be low.
Other approaches to location-prediction using historical information are based
on the limited contact history of a single node (e.g., [12]), group contact-time
information of a certain number of users (e.g., based on their social ties [10]) or
use offline network traces to evaluate the accuracy of Markov or semi-Markov
based approaches (e.g., [19], [9]).
In this paper, we employ a semi-Markov model for the prediction of contact opportunities. Semi-Markov models [15] were introduced as stochastic tools with capacity to accommodate a variety of applied probability models: they may provide more generality to describe the semantics of complex models - which, in turn, increases the complexity of analysis. However, the extra-added variables improve the modeling expressiveness of real-life problems. We also note that the increased complexity is assigned to the resource-capable fixed nodes, improving prediction accuracy without damaging the sensitive performance of mobile, battery-powered devices. It is documented (e.g., in [9], [25]) that Markov-based location predictors perform very well in practice, but require more complex and expensive mobility data for sophisticated forecasts such as the time and location of the next user movement or duration of stay in an area.

Our approach is characterized by two main advantages: (i) the fixed infrastructure allows for a global view of the system and improved predictions of connectivity opportunities, (ii) the mobile devices delegate resource-expensive operations to the infrastructure nodes in order to exploit their capabilities in terms of energy availability, processing power and memory allocation. Therefore, the performance of mobile devices is preserved without trading prediction accuracy and hence communication efficiency. Decoupling (but also improving) the forecasting capability from the routing strategy enables a number of new efficient protocols to be introduced. Furthermore, the forecasting connectivity opportunities can be a basis for an efficient energy-saving strategy also; the mobiles could be switching off their communication subsystems at times the probability to meet other nodes is low.

To demonstrate the potential of our solution, we consider an urban scenario where mobile users are interested into getting Internet access. Different hotspots are scattered in a city center (i.e., around 60 km² in Thessaloniki, Greece), covering with Internet connectivity some percentage of that area (i.e., less than 40%). The hotspots are deployed in real points of interest (central squares, museums and other places attracting people) and are collectively building a communication model. The mobile nodes can request information on neighboring nodes: how often or with what probability they do contact the available hotspots. Such information is passed from the closest hotspot to the mobile contacts. So, a moving user can easily make decisions on whether a neighboring node is more suitable to forward its own data towards the Internet. Indeed, as we show in our experimental results, we were able to identify useful mobility patterns for future efficient network protocol designs.

The paper is structured as follows. In Section 2 we review the state of the art that is relevant to the present work. In Section 3 we describe a particular scenario, along with the proposed semi-Markov stochastic model. In Section 4 we evaluate the above model in three experimental scenarios. Finally, in Section 5 we conclude the paper.
## 2 Related Work

Internet complexity has been increased rapidly since new communication paradigms, other than Infrastructure - based networking, have been incorporated into the internetworking model (e.g., ad-hoc, mesh or space networking). In this context, the network becomes also a storage device - not just a communication vehicle. This new property of the Internet alone challenges all known models and evaluation standards for internetworked systems. Furthermore, approaches such as Delay - and Disruption - Tolerant Networks (DTNs) [11] undergo major standardization efforts that target a unification perspective for the various pieces of the global network jigsaw puzzle. We note that protocols originally designed for a homogeneous network environment are not expected to work optimally in such a hybrid setting. An example work that brings closer different types of networks (i.e., wireless and mobile) is [8], attempting to define a continuum between the different networks.

A number of approaches support mobile communication using the surrounding infrastructure. In the area of VANETs, proposals either exploit infrastructure to support car-to-car communication (e.g., through roadside access points) or the opposite (e.g., [23]). Recent papers consider clouds as a dynamic infrastructure that improves mobile communication through offloading resources from the mobile users (e.g., [18]). The DTN throwboxes have been introduced as stationary, battery-powered nodes, embedded with storage and processing capabilities that are able to enhance the capacity of DTNs [4]. Mobile infostation networks use the infostation nodes to support mobile communications for this specific context (e.g., to keep information close to the mobile users [17]). Other proposals move a portion of the mobile data traffic to WiFi networks, exploiting the significantly lower cost of WiFi technology and existing backhaul infrastructure [24].

In the literature, approaches to mobile connectivity forecasting have been proposed in different contexts, such as resource reservation in cellular networks or handoff planning (e.g., [5, 28]). For example, BreadCrumbs [20] maintains a personalized mobility model on the user's device that tracks APs (i.e., using RF fingerprinting) and combines the predictions with an AP quality database to produce connectivity forecasts.

Compared to the related works, our solution decouples the mobility model from the routing protocol and offloads prediction operations to the surrounding infrastructure. This allows a larger number of samples to be considered (i.e., due to the more complete view) and more complicated calculations to be performed, improving the forecasting accuracy in a resource friendly way for the mobile devices. In our proposal, we model user mobility with a semi-Markov process with heterogeneous properties, allowing for flexible definition of different distributions for inter-contact times, under different conditions. Such conditions and other relevant patterns are being explored and associated with practical constraints (e.g., resource availability). Other relevant approaches using semi-Markov processes are [6], [29]. Both of them model routing behavior rather than mobility patterns.
# 3 Case Study and Modeling Considerations

## 3.1 Studied Environment

In this paper, we consider a heterogeneous network scenario consisting of both mobile and infrastructure nodes. In this context, we assume a communication system that integrates deployed infrastructure (e.g., a network of hotspots) with opportunistic networks, therefore allowing for additional communication opportunities even for uncovered city areas. The infrastructure nodes have been delegated the responsibility of tracking the position of mobile nodes as well as the potential estimation of their future positions.

At this stage, we study an urban scenario where mobiles require Internet connectivity at times they are not covered from deployed hotspots. For methodological reasons, we start from the particular environment and the study of next-place or WiFi connectivity forecasts in order to devise strategies for extended and efficient Internet access. As a next step, we plan to move on to more complicated scenarios, predicting device-to-device connectivity opportunities in heterogeneous deployments (i.e., mixing networked vehicles with pocket switched networks).

Our scenario includes a number of hotspots covering only a percentage of the area with connectivity (e.g., 30-40 %). There is a wide-range of mobile device types moving around the hotspots. Each mobile node may need to access the Internet or to interact with any other node. To address this demand, a dynamic path should be established between the communicating nodes, carrying the data to be transmitted. This is not trivial, since all nodes may be constantly moving and all participating node positions are not known in advance. The communication between the user and the closer hotspot can be handled from variations of well-known opportunistic network protocols, such as the Spray 'n Focus [26], the MaxProp [7] or any other similar.

In our case, the hotspots collectively train a model which is able to estimate the evolution of node topology structure, elaborated in the following subsection. In a more general setting, the source mobile node can query any hotspot for the destination node position or any other relevant information. If the latter node is directly connected to an infrastructure node, data will be carried through the infrastructure to the destination, straightaway. In case the destination mobile user is located in an uncovered area, data will be forwarded through the infrastructure to the hotspot that has the higher probability to be near the user. This hotspot is selected from the source mobile node using forecast information produced by the proposed semi-Markov model and the most recent location information of the destination mobile.

Since the source node may not be always connected to a hotspot, the infrastructure responses regarding the potential destination node positions will be more general, enhancing mobiles with limited but resource-efficient and accurate estimation capabilities. For example, the responses can be coefficients of known distributions, which are functions of time.
## 3.2 Semi-Markov Model and Basic Equations

In this subsection, we detail the proposed stochastic model and its basic equations reflecting different aspects of users' mobility behavior. The stationary nodes implement collectively the model and communicate the output of the equations to the interested mobile nodes. An efficient routing decision may require one or more calculations, based on its own criteria. We present usage examples along with the model description (denoted in italics), in the context of our proposed infrastructure. We note that all equations can be used as contact predictors for communication between the mobiles as well.

We model the users' mobility behavior using a Discrete-Time Semi-Markov System (DTSMS). A semi-Markov chain is a generalized Markov model and can be considered as a process whose successive state occupancies are governed by a Markov chain (i.e., embedded Markov chain), although state duration is described by a random double variable which associates with the present but also with the next transition state. A relevant model discussion focused on theoretical aspects can be found in [21].

At the beginning of our analysis, we assume a population of users moving around a city center (i.e., in this paper we considered the city of Thessaloniki) and pass through a number of scattered hotspots in real points of interest in the area (e.g., central squares, museums etc). The users can be stratified into a set of areas $S = 1, 2, ..., N$. We assume that a number of areas have network coverage (e.g., 1 to $K$) while other areas do not (e.g., $K$ to $N$). These areas are assumed to be exclusive and exhaustive, so that each user is located at exactly one area at any time. The system state at any given time is described by the vector $N(n) = [N_1(n), N_2(n), ..., N_N(n)]$, where $N_i(n)$ is the expected number of users located at an area $i$, after $n$ time slots. We consider a closed system with constant total population of users denoted with $T$. Also, we assume that the individual transitions between states occur according to a homogeneous semi-Markov chain (i.e., embedded semi-Markov chain). In this respect, let us denote by $P$ the stochastic matrix whose $(i,j)th$ element equals to the probability of a user in the system which entered an area $i$ to make its next transition to area $j$. Thus, whenever a user enters area $i$ selects area $j$ for its next transition, according to the probabilities $p_{i,j}$.

A mobile node may request a specific probability value in the form of $p_{i,j}$ from the infrastructure system. This expresses the probability of a node to reach an area $j$ after being at an area $i$, in the next transition. This value could be used from a mobile node in order to check if there is a chance for a user to pass by area $i$ and reach area $j$ straightaway. For example, the mobile could perform a quick check if two areas are adjacent.

In our model, the mobile user remains for sometime within area $i$, prior to entering area $j$. Holding times are described by the holding time mass function $h_{i,j}(n)$, which equals to the probability that a user entered area $i$ at its last transition holds for $n$ time slots in $i$ before its next transition, given that node moves to area $j$.
The holding time mass function $h_{i,j}(n)$ could be used by a mobile in order to check the possibility of a direct transition from area i to area j at a given time. Occasionally, the destination area may not matter, but instead, the transition is important: for example, a transition from a non-covered to a network-covered area. A node, therefore, at an isolated area may evaluate the cumulative probability to move to any area with connectivity, independently of which area it is.

By the same token, we discuss the following variation of the holding time mass function:

$$h_i(n) = \sum_{j=1,2,...,N(j \neq i)} p_{i,j}h_{i,j}(n) \quad (1)$$

The $h_i(n)$ function captures the probability of a mobile at state i to make a transition at time n (the particular destination area is irrelevant). Along the same lines, we introduce the probabilities:

$$h_i^{con}(n) = \sum_{j=1,2,...,K} p_{i,j}h_{i,j}(n) \quad (2)$$

$$h_i^{disc}(n) = \sum_{j=K,K+1,...,N} p_{i,j}h_{i,j}(n) \quad (3)$$

The functions $h_i^{con}(n)$ and $h_i^{disc}(n)$ capture the probabilities of a mobile to move from area i to any area with connectivity or not at time n, respectively. For example, a forwarding decision could be made based on the possibility of the forwarding node to carry data to an Internet access network.

We also detail equation $>w_i(n)$ which expresses the probability of a user who made a transition to area i to reach the next area in longer than n time slots:

$$>w_i(n) = \sum_{m=n+1}^{\infty} \sum_{k=1}^{N} p_{i,k}h_{i,k}(m) \quad (4)$$

The initial condition is $>w_i(0) = 1$.

Similarly, variations like $>w_i^{con}(n)$ and $>w_i^{disc}(n)$ could be introduced.

The $>w_i$ equations can support the forwarding decisions of the opportunistic routing protocol inline with data transmission deadlines, e.g., delay constraints for real-time or other time-critical applications.

A main aspect of the proposed model is related to the interval transition probabilities which correspond to the multistep transition probabilities of a Markov process. So, let us define as $q_{i,j}(n)$ the probability of a user from area i to be at an area j after n time slots, independently of the required intermediate state changes. This metric allows multi-path contact predictions, i.e., captures the probability of a node to be at an area after some time (or two mobiles to contact each other, in a general setting), independently of the required steps.

The basic recursive equation for calculating the interval transition probabilities is the following [14], [27]:

$$q_{i,j}(n) = \delta_{i,j} >w_i(n)$$
$$ + \sum_{k=1}^{N} \sum_{m=0}^{n} p_{i,k} h_{i,k}(m) q_{k,j}(n-m) \quad (5) $$

The initial condition is $q_{i,j}(0) = \delta_{i,j}$, where $\delta_{i,j}$ is defined:

$$ \delta_{i,j} = \begin{cases} 1 & \text{if } i = j \\ 0 & \text{elsewhere} \end{cases} \quad (6) $$

# 4 Evaluation

## 4.1 Evaluation Methodology

Here, we detail our evaluation methodology and the experimental scenarios we studied. We extracted a large area of the city center of Thessaloniki, Greece from the OpenStreetMap website [2]. The area's dimensions are 6.2km x 10.1km, including 397 streets and 1884 landmarks. We selected twelve representative points of interest, assuming they offer Internet connectivity as well. For simplicity, we consider as area 13 any other area without connectivity. Their locations were extracted from the same information source and selected based on their popularity (e.g., the Aristotles Square, the railway station, the St. Sophia Church, well-known museums etc). We use the one [16] simulations augmented with real parameters. A map screenshot that includes some of the selected points of interest is shown in figure 1. The mobile users walk around the city, following one of the identified streets each time and directing towards an area based on a mobility pattern detailed in the corresponding scenario. The users stay in each area from few minutes to hours and their walking speed ranges between 0.5 and 1.5 m/sec. Our next step is to use alternative mobility traces from the CRAWDAD database [1] in order to validate the general applicability of our proposal. A real deployment is in our plans as well.

We grouped our experiments into three distinct scenarios, demonstrating the efficiency of the proposed semi-Markov model, assuming corresponding user mobility behavior in the city center:

- A "Home-to-work" scenario, where a mobile node walks occasionally between home, work and the main city square. There is a 33% probability of the user to be in one of these three areas.

- A "Walking around the city" scenario, where the mobile node occasionally selects one of twelve different areas in the city center as the next visiting area, with equal probability.

- A "Going out" scenario, where the mobile node has a high probability (33%) to be in the main square (assuming it as a meeting point) and an equal probability for each of the other eleven areas.

For the above scenarios, we show how the proposed equations can be used as prediction mechanisms for a number of different mobility aspects and how different mobility patterns can be detected and exploited by a communication protocol.
<figure><img src="image_2.png" /><figcaption>Fig. 1. The experimental scenario</figcaption></figure>

## 4.2 Evaluation Results

**Scenario 1: "Home-to-Work"** In figures 2(a), 2(b) we show the equations $h_i$ and $h_{i,j}$, respectively. Both metrics reflect the probabilities of a mobile to move to the next area, at given time slots. In the case of figure 2(b), the destination area does not matter, as long as we have a state change. It takes some time (i.e., more than 50 secs) for the mobile to change state, a value that is a factor of the movement speed and the distance between the three areas. In figure 2(a), we show the probability of a mobile to move to one of the three areas (i.e., home, work or main square), when it is located at an area without connectivity (i.e., area 13). The three *h* probabilities (i.e., $h_{13,1}$, $h_{13,3}$ and $h_{13,9}$) have often similar values, something not surprising given the experimental setup parameters. This behavior leads to reduced communication overhead of the forecasting request interactions between mobiles and infrastructure: an average value suffices.

The *w* metric (figure 2(c)) reflects the probability of a user who made a transition to an area, to reach to the next area after at least *n* time slots. In this case, there is a very low probability for a state change, if the mobile stays at a particular area for more than 600 secs. The $w_{13}(n)$ value is indeed interesting, since it represents the probability of a mobile node being at an area without connectivity, to move to an area with connectivity in less than *n* minutes. In this example, there is an insignificant chance of a connectivity time that exceeds 200 secs. Of course, this result is guided by the experimental setup parameters.

Equation *q*, shown in figure 2(d), reflects the probability of a node being at an area without connectivity to move to an area with connectivity at some given time, but without considering the number of areas crossed. We see that after some time, i.e., 200-300 secs, the probabilities to move to one of the three areas with connectivity, tend to converge to fixed values. Curve $q_{13,13}(n)$ shows the probability of a mobile being at an area without Internet connectivity to visit an area covered by a hotspot, stay for a while and then leave the hotspot again.
<figure><img src="image_3.png" /><figcaption>(a) Probability of a user to remain for time $n$ within area $i$, prior to entering area $j - h_{i,j}(n)$</figcaption></figure>

<figure><img src="image_4.png" /><figcaption>(c) Probability of a user who made a transition to area $i$ to reach the next area in longer than $n$ time slots - $w_i(n)$</figcaption></figure>

<figure><img src="image_5.png" /><figcaption>(e) Probability of a user to remain for time $n$ within area $i$, prior to entering area $j - h_{i,j}(n)$</figcaption></figure>

<figure><img src="image_6.png" /><figcaption>(g) Probability of a user who made a transition to area $i$ to reach the next area and reach area $j$ with multiple steps, after in longer than $n$ time slots - $w_i(n)$ and $n$ time slots - $q_{i,j}(n)$</figcaption></figure>

<figure><img src="image_7.png" /><figcaption>(b) Probability of a user to remain for time $n$ within area $i$, prior to entering any other area - $h_i(n)$</figcaption></figure>

<figure><img src="image_8.png" /><figcaption>(d) Probability of a user to leave area $i$ and reach area $j$ with multiple steps, after $n$ time slots - $q_{i,j}(n)$</figcaption></figure>

<figure><img src="image_9.png" /><figcaption>(f) Probability of a user to remain for time $n$ within area $i$, prior to entering any other area - $h_i(n)$</figcaption></figure>

<figure><img src="image_10.png" /><figcaption>**Fig. 2.** "Home-to-work" and "Walking around the city" scenarios results</figcaption></figure>
**Scenario 2: "Walking Around the City"** Compared with scenario 1, the *h* values have an equivalent behavior (see figures 2(e), 2(f)) because the transition probabilities of state changes in the two scenarios are similar. The main difference lies in the number of states (i.e., 12 areas for scenario two and 3 areas for scenario one). In figures 2(e), 2(f), we depict three states only, for clarity and comparison purposes (i.e., between the three scenarios). We note that the *h* values reflect changes between state 13 (i.e., area without connectivity) and any other available state. This happens because we assume that available hotspots do not have overlaps and have uncovered areas between them. State changes are associated with the parameters of our system, i.e., waiting time at each state. In our case, it is a random value picked from a uniform distribution in the range of [0, 120] seconds.

Of course, the topological properties of the system (i.e., locations and dis-
tances between the hotspots) do matter and impact the state change probabilities
between the different areas within the same scenario. This is reflected on the *w*
values (i.e., figure 2(g)) and the *q* values (i.e., figure 2(h)). After some time, the
different *q* values converge to fixed values.

**Scenario 3: "Going out"** Through the *h* metrics (i.e., figures 3(a), 3(b)), we see a notable difference compared with the previous two scenarios. The *h* values for area 1 (the main square of the city, the Aristotle Square) are significantly lower. In this scenario, state 1 has been chosen with a probability 0.33. So, there is a high probability for a node to remain at the main square (i.e., same destination state to the source state). This is a pattern that could potentially be detected (i.e., hotspots that have a high probability to host mobile users). The same is reflected in a number of other metrics. For example, the *w*₁(*n*), *q*₁₃,₁(*n*) values are significantly higher than other *q*, *w* values, respectively (see figures 3(c), 3(d)).

To summarize, the proposed model allows detection of certain patterns re-
garding the spatial behavior of the users. Some examples are:

- How probable is a state change between two particular states in a single step (i.e., *h*ᵢ,ₖ values) or in many steps (i.e., *q*ᵢ,ₖ values).

- What is the probability of a state transition from some given state to any other target state (i.e., *h*ᵢ and *w*ᵢ values).

- Whether some states have a significantly higher probability to be reached (i.e., *q*ᵢ,ₖ, or *w*ᵢ or *h* values).

5 Conclusions

In this paper, we detailed a communication paradigm where infrastructure and
opportunistic networks can efficiently inter-operate. We argue that:

- Opportunistic networks can bridge distant infrastructure networks (i.e., in areas without connectivity) using sophisticated routing protocols capable of detecting and exploiting user mobility patterns.
- Infrastructure nodes can support opportunistic communication with mechanisms that: (i) detect system - wide mobility patterns, and (ii) perform resource - expensive forecasting calculations for the benefit of the mobile devices.

We introduced a semi-Markov model and detailed a number of equations able to predict different aspects of user mobility behavior. This work focuses on the infrastructure being able to support a variety of network protocols exploiting communication opportunities using a number of accurate user- and system-level forecasts. Our approach allows for more complete and complex mobility models that would be difficult to integrate in a homogeneous network setting. A sophisticated protocol design exploiting the potential of the proposed infrastructure is in our short-term plans.

<figure><img src="image_11.png" /><figcaption>(a) Probability of a user to remain for time $n$ within area $i$, prior to entering area $j - h_{i,j}(n)$</figcaption></figure>

<figure><img src="image_12.png" /><figcaption>(b) Probability of a user to remain for time $n$ within area $i$, prior to entering any other area - $h_i(n)$</figcaption></figure>

<figure><img src="image_13.png" /><figcaption>(c) Probability of a user who made a transition to area $i$ to reach the next area in and reach area $j$ with multiple steps, after longer than $n$ time slots - $w_i(n)$
(n time slots - $q_{i,j}(n)$)</figcaption></figure>

<figure><img src="image_14.png" /><figcaption>**Fig. 3.** "Going out" scenario results</figcaption></figure>
Acknowledgement

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

The research leading to these results has received funding from the Eu-
ropean Unions (EU) Horizon 2020 research and innovation programme under
grant agreement No 645124 (Action full title: Universal, mobile-centric and op-
portunistic communications architecture, Action Acronym: UMOBILE). This
paper reflects only the authors views and the Community is not liable for any
use that may be made of the information contained therein.

References

1. CRAWDAD, A Community Resource for Archiving Wireless Data At Dartmouth, http://crawdad.cs.dartmouth.edu

2. OpenStreetMap - The Free Wiki World Map, http://www.openstreetmap.org

3. Balasubramanian, A., Mahajan, R., Venkataramani, A.: Augmenting mobile 3g using wifi. In: Proceedings of the 8th international conference on Mobile systems, applications, and services. pp. 209–222. MobiSys ’10, New York, NY, USA (2010)

4. Banerjee, N., Corner, M., Levine, B.: An energy-efficient architecture for dtn throw-boxes. In: 26th IEEE International Conference on Computer Communications (INFOCOM 2007). pp. 776–784. IEEE (2007)

5. Bhattacharya, A., Das, S.K.: Lezi-update: an information-theoretic approach to track mobile users in pcs networks. In: Proceedings of the 5th annual ACM/IEEE international conference on Mobile Computing and Networking. pp. 1–12. MobiCom ’99, ACM, New York, NY, USA (1999)

6. Boldrini, C., Conti, M., Passarella, A.: Modelling social-aware forwarding in opportunistic networks. In: IFIP Performance Evaluation of Computer and Communication Systems (PERFORM 2010). pp. 1–12 (2010)

7. Burgess, J., Gallagher, B., Jensen, D., Levine, B.: Maxprop: Routing for vehicle-based disruption-tolerant networks. In: IEEE INFOCOM. vol. 6, pp. 1–11. Barcelona, Spain (2006)

8. Chen, Y., Borrel, V., Ammar, M., Zegura, E.: A framework for characterizing the wireless and mobile network continuum. ACM SIGCOMM Computer Communication Review 41(1), 5–13 (2011)

9. Chon, Y., Shin, H., Talipov, E., Cha, H.: Evaluating mobility models for temporal prediction with high-granularity mobility data. In: International Conference on Pervasive Computing and Communications (PerCom 2012). pp. 206–212. IEEE (2012)

10. De Domenico, M., Lima, A., Musolesi, M.: Interdependence and predictability of human mobility and social interactions. In: Proceedings of the Pervasive 2012, Newcastle, UK (2012)

11. Fall, K.: A delay-tolerant network architecture for challenged internets. In: Proceedings of the 2003 conference on Applications, Technologies, Architectures, and Protocols for Computer Communications. pp. 27–34. ACM (2003)

12. Gambs, S., Killijian, M., del Prado Cortez, M.: Next place prediction using mobility markov chains. In: Proceedings of the First Workshop on Measurement, Privacy, and Mobility. p. 3. ACM (2012)

13. Hartenstein, H., Laberteaux, K.: A tutorial survey on vehicular ad hoc networks. IEEE Communications Magazine 46(6), 164–171 (2008)
14. Howard, R.: Dynamic Probabilistic Systems: Vol.: 2.: Semi-Markov and Decision Processes. John Wiley and Sons (1971)

15. Iosifescu Manu, A.: Non homogeneous semi-markov processes. Studii si Cercetuari Matematice 24, 529-533 (1972)

16. Keränen, A., Ott, J., Kärkkäinen, T.: The ONE Simulator for DTN Protocol Evaluation. In: SIMUTools '09: Proceedings of the 2nd International Conference on Simulation Tools and Techniques. ICST, New York, NY, USA (2009)

17. Kubach, U., Rothermel, K.: Exploiting location information for infostation-based hoarding. In: Proceedings of the 7th annual international conference on Mobile computing and networking. pp. 15-27. MobiCom '01, ACM, New York, NY, USA (2001)

18. Kumar, K., Lu, Y.: Cloud computing for mobile users: can offloading computation save energy? Computer 43(4), 51-56 (2010)

19. Lee, J.K., Hou, J.: Modeling steady-state and transient behaviors of user mobility: formulation, analysis, and application. In: Proceedings of the 7th ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc). pp. 85-96. ACM (2006)

20. Nicholson, A.J., Noble, B.D.: Breadcrumbs: forecasting mobile connectivity. In: Proceedings of the 14th ACM international conference on Mobile Computing and Networking. pp. 46-57. MobiCom '08, ACM, New York, NY, USA (2008)

21. Papadopoulou, A., Mamatas, L., Tsaoussidis, V.: Semi markov modeling for user mobility in urban areas. In: Proceedings of the 2nd Stochastic Modeling Techniques and Data Analysis International Conference (SMTDA 2012) (June 5-8, 2012)

22. Papastergiou, G., Psaras, I., Tsaoussidis, V.: Deep-space transport protocol: a novel transport scheme for space dtns. Computer Communications 32(16), 1757-1767 (2009)

23. Petit, B., Ammar, M., Fujimoto, R.: Protocols for roadside-to-roadside data relaying over vehicular networks. In: Wireless Communications and Networking Conference (WCNC 2006). vol. 1, pp. 294-299. IEEE (2006)

24. Iris, V.A., Kalyvas, D.: Enhancing mobile data offloading with mobility prediction and prefetching. In: Proceedings of the seventh ACM international workshop on Mobility in the evolving internet architecture. pp. 17-22. MobiArch '12, ACM, New York, NY, USA (2012)

25. Song, L., Deshpande, U., Kozat, U.C., Kotz, D., Jain, R.: Predictability of lanw mobility and its effects on bandwidth provisioning. In: Proceedings of the 25th IEEE International Conference on Computer Communications (INFOCOM). pp. 1-13. IEEE (2006)

26. Spyropoulos, T., Psounis, K., Raghavendra, C.: Efficient routing in intermittently connected mobile networks: the multiple-copy case. IEEE/ACM Transactions on Networking 16(1), 77-90 (2008)

27. Vassiliou, P., Papadopoulou, A.: Non homogeneous semi markov systems and maintainability of the state sizes. Journal of Applied Probability 29, 519-534 (1992)

28. Yu, F., Leung, V.: Mobility-based predictive call admission control and bandwidth reservation in wireless cellular networks. Computer Networks 38(5), 577-589 (April 2002)

29. Yuan, Q., Cardei, I., Wu, J.: Predict and relay: an efficient routing in disruption-tolerant networks. In: Proceedings of the tenth ACM international symposium on Mobile Ad hoc Networking and Computing. pp. 95-104. ACM (2009)