Project topics and materials
Get Complete Project Material File(s) Now! »
Opportunistic Networks: Characteristics and Chal-lenges
This all started high in the sky with satellite networks and the idea of an Interplanetary Internet [1]. To work with such type of networks is clearly different from working with our common wired or Wi-Fi networks. Compared to most systems, interplanetary networks do bear unusual features. For instance, topological distance between spatial nodes is often of thousands of kilometers inducing long delays between the emission and reception of a signal. These long delays are considered faulty in usual networks. However in this case, it is a natural part of their functioning.
Fall formalized the characteristics of a “delay-tolerant network architecture” for chal-lenged networks [2]. By bringing a back-to-earth vision to challenged networks, Fall sparked a lot of interests in our fellow scientists. By lifting a few technical constraints, our community could extend wireless networks use to such challenged networks. This new paradigm could be applicable to urban areas with urban nomads always carrying connected devices (laptops, smartphones, etc.) When two or more of these devices are close enough, they have potential connectivity and transmitting powers thanks to their embedded technologies. Transmitting information hop-by-hop between these moving devices becomes theoretically possible. Such challenged networks are called “disruption-tolerant networks” (DTN) or “opportunistic networks”.1 In this thesis, we focus on urban human-driven networks (networks between user-carried devices in a city setting, see Fig. 1.1).
Opportunistic networks rely on device’s “short” range connectivity (currently Blue-tooth, NFC or Wi-Fi Direct) to transmit data. Therefore, nodes can transmit data only when they are close enough i.e., in contact. Fig. 1.2 presents an example of a 4-node DTN. At time t1, A and B as well as C and D are connected. Next at t2, they form a chain and finally at t3, B moves away leaving A, C, and D fully connected. Any disruption-tolerant protocol should cope with such a connected/disconnected scenario.
In order to reach the destination, nodes use a hop-by-hop “store, carry, and forward” scheme. Their main functioning differences compared to classic networks are as follows:
• High latency. Between the source and the destination, there may be several store and forward processes occurring after different nodes collocation. This can take quite some time between actually sending a message and receiving it. This high latency would not work with traditional networking paradigms. As an example, the TCP protocol would have to be completely retuned to fit this high latency.
• Disconnection periods. One of the challenges of DTN is to tolerate complete disconnection periods in their process. Any previous networking paradigm con-sidered a disconnection in their session to be an error and had to resume the process at best or to restart it completely at worst. In DTN, nodes do not need to have an explicit connection or session from the sender to the receiver. This not-necessarily-connected property of DTN offers much more freedom in network utilization than any other existing paradigm.
• Mobility. Previous network paradigms or other research fields deem mobility as an opponent to good functioning. Here, a very interesting feature of human-driven opportunistic networks is the mobility of the nodes. Everyday people commute to work and travel long distances carrying connected devices.2 Whenever they are close to someone, they can transmit data and during travel times, commuters encounter many persons that can act as potential data carriers. They may even encounter some people regularly without realizing it. This regular encounter phe-nomenon is called “the familiar stranger” and can be use for opportunistic for-warding [3]. Mobility allows us benefiting from these opportunistic encounters while previous networks did not. However, mobility is not the same for everyone nor is it a random process, therefore, its implications are not that obvious.
• Limited longevity. Limited resources. Low data rates. These properties stem from the devices in use in DTN. Portable devices like smartphones, laptop, 2On average, commuting takes 25 minutes un the US but around 1.7 million Americans are “mega-commuters” and have commuting duration of 90 minutes or more and of length at least 80 kilometers.
Figure 1.3: A snapshot of a 7-node network at instant t. A is in contact with B and C while nodes D, E, F, and G are beyond contact. From A’s point of view, most opportunistic approaches only use the knowledge that B and C are nearby (direct connectivity knowledge). If A wanted to transmit something to E, who would it send it to? B or C. With this current vision, A cannot easily determine who to send the message to.
or game stations work on batteries and have a limited daily lifespan. The more applications we use, the less batteries last. So, finding the accurate power mode for opportunistic networking is an important issue. Limited resources also come from the devices capacities, but as technology progresses, we find smartphones almost as powerful as desktops and the main constraint resides in the embedded wireless technology. However, if we consider opportunistic networks between vehicles for example, restrictions over battery life, memory resources, or data rates are weaker.
• Security. For mobile networks, security always remains an issue. As long as a device stores data to forward it and respects the content’s privacy, a node has no idea of what it stores. Therefore the security issue here is as hard to deal with as it is with any other mobile network.
Motivating Example
Let us observe an example of opportunistic networks. In most opportunistic approaches, decisions are made depending on what happens around a given node, more precisely which nodes are in “contact” with it. This notion of contact is fundamental in DTN as we will see throughout this manuscript.
Fig. 1.3 presents a snapshot of an opportunistic network with 7 nodes. At instant t, when we observe the situation through node A’s point of view, A has two nodes in contact with it (namely B and C). All the remaining nodes from D to F are beyond contact. All opportunistic decisions concerning A are made according to A’s current states and both B and C information. Still, we observe that A has an end-to-end path to nodes D and E so their behavior could and should influence A’s forwarding decisions. For instance, A could easily transfer data to both D and E, or probe their encounters history to decide whether they are “good” carriers.
Figure 1.4: The same 7-node network snapshot but with a neighborhood-wise vision for node A. Here, A would take into account all nodes to whom it has a contemporaneous path instead of only considering nodes in contact. If A wanted to send a message to E, it would use C as a next hop because C belongs to the shortest path between C and E at that moment.
Now consider that A wants to send a message to E. A would only know that B and C are currently in contact and, at most, that D is reachable. A would more likely only know that it is in contact with B and C. So who should A use as next hop carrier? Using only contact knowledge, it is hard to tell as B and C seem to have the same properties to E – not in contact. But if A considered not only contact but the knowledge of all its nearby nodes and neighbors, A would certainly send to C to minimize the path length between A and E – 3 hops instead of 4 (see Fig. 1.4). This example shows that the current approach of considering only nodes in contacts in DTN may hamper a node’s vision of the situation and prevents it from taking optimal decisions network-wise.
Problem Statement
In this dissertation, we question the current opportunistic network vision in use. We address two main issues.
Question 1: Is the current DTN vision enough? As we have shown in the previ-ous example, considering only contacts in DTN overlooks many closeby opportunities. So, does ignoring neighbors beyond contacts harm DTN usage? The historical contact notion in DTN remains important as it settles direct communication possibilities. Nev-ertheless, this notion does not limit the capabilities of communication to nodes at a one-hop distance. If there are neighbors in contact, there may be others nodes closeby at a 2- or 3+-hop distance. In real life, when one is seated on a bus, she may be close to 3 or 4 other commuters but that does not mean she cannot see other people a little further away or that she cannot speak to them. All these bus passengers are potential information carriers and their importance should not be neglected. When they arrive at their bus stop, they move to different places and this non random human-driven mobil-ity expands the range of possible hop-by-hop communications. The more we can spread a message, the more people we can reach, and the higher the probability of reaching a given destination in shorter delays.
Question 2: Why not considering a proximity notion in DTN? Noticing the flaws of the mere contact vision in DTN. We wonder how node proximity has been treated until now in opportunistic networks. A few intents at using proximity and resulting end-to-end paths of length strictly greater than 1 hop exists but none of them actually defined a notion of close vicinity in DTN [4, 5, 6, 7]. To the best of our knowledge, this is the first time a study formalizes the notion of vicinity in DTN. With a formalized vision of vicinities, we can start characterizing its behavior and the possibilities of communications beyond simple contacts and answer questions like: how marginal are such transmission possibilities? What is the behavior of these vicinities at a network level? Are there specific links between a node and members of its vicinity? What are the properties of vicinities in DTN? Replying to these interrogations can help opportunistic networks understanding on many stages. Plus, understanding vicinity movements may improve opportunistic knowledge bootstrapping in DTN protocols.
Contributions of this Thesis
In this dissertation, we answer the previously raised questions through the following contributions.
Contribution 1: Uncovering the Properties of Intercontacts in DTN. We first wonder if the DTN vision limited to nodes in contact is enough to benefit from DTN’s original properties. We begin by showing how sub-optimal such a vision is and then formalize the concept of vicinity in opportunistic networks. To the best of our knowledge, our work is the first to ever expose a precise definition for vicinity in DTN namely κ-vicinity. κ-vicinity is a node-centered definition for vicinities in DTN. A node’s κ-vicinity is the set of neighbors located within κ-hops from it. Note that we use connectivity graphs to derive our notion of vicinity. We also defined κ-contact and κ-intercontact notions to fit the pairwise relationships between two nodes and analyze their temporal distributions. We also analyze the internal topological properties of κ-vicinities to understand neighbors disposition. Finally, we observe the improvements of vicinity annexation in a simple forwarding protocol (Chapter 3).
Our main contributions with this regard are as follows:
• We identify the binary assertion issue in opportunistic networks where most op-portunistic networks approaches consider only nodes in contact and neglect other nearby nodes.
• We defined close vicinity in DTN with the “κ-vicinity” and the related connectivity notions of “κ-contact” and “κ-intercontact”.
• We show how κ-contact intervals distributions depend on node-centered density with behavior changing whenever the density is “sparse” or “dense”.
• We assess the tradeoff between additional vicinity knowledge and monitoring costs and conclude that a κ between 3 and 4 is enough for the type of datasets we consider.
• By using the 2-vicinity instead of the usual contact vision in opportunistic net-works, we can improve by 80% a given opportunistic performance metric.
Contribution 2: Digging into the Vicinity Dynamics of Mobile Opportunistic Networks. We analyze the internal κ-vicinity dynamics of opportunistic networks. We chose to model the node-centered vicinity behavior with a chain process using exact pairwise distances values as states. We call this model asynchronous vicinity motion. We observe the transitional probabilities between any given states to understand vicinity movements. We identify two different chain types and three main movement patterns namely birth, death and sequential moves in κ-vicinities. We observe their repartition in different datasets and how they can be leveraged in opportunistic networks. We analyze vicinity behaviors using timelines which is the sequence of shortest distances between pairs of nodes in the network. To ease the analysis of vicinities in various scenarios, we implemented a Python module to automatically perform all the aforementioned vicinity dynamics analyses. After extracting vicinity movements characteristics with asynchronous vicinity motion, we manage to recreate synthetic timelines exhibiting chosen datasets properties using the TiGeR generator (Chapter 4).
In this part, we make the following contributions:
• We conceive asynchronous vicinity motion, a model for internal dynamics in κ-vicinities.
• We identify three main vicinity motion patterns “birth, death, and sequential” movements and some of their properties: death rates remain stable independently of states, birth patterns are alike independently of the observed datasets and by considering death and sequential movements, for some states they represent more than 80% of all outgoing movements.
• We propose a pairwise vicinity behavior generator and its open access implemen-tation included in the Vicinity package we provide.3
Contribution 3: Predicting Vicinity Dynamics. In our latest contribution, we in-vestigate how predictability applies in the κ-vicinity and how accurately vicinity motion captures the network operation. We create a heuristic based on transitional probabilities of vicinity motion to predict a pair of preferential pairwise distances between nodes for the future steps. In asynchronous vicinity motion, steps have various durations. Since our heuristic predicts pairwise distances for future steps, having constant duration steps may bring a more powerful forecasting. Therefore, we present the synchronous vicinity motion, a time-aware variant of vicinity motion. Synchronous vicinity motion samples its surroundings every τ seconds. A step is now of constant duration τ seconds here. We analyze the performances of asynchronous and synchronous vicinity motion (AVM and SVM) heuristics and show their prediction power in terms of pairwise distances not only for the next considered interval but also intervals further away in time (Chapter 5).
Our main findings are:
• The definition of a time-aware vicinity motion called synchronous vicinity motion.
• The possibility of inferring future κ-vicinity distances using Markov chains tran-sient state analysis with our heuristic that can predict pairwise distances up to a 99% accuracy with the SVM model and 40% with AVM.
• A comparison of full duration and partial knowledge forecasting performance showing how vicinity motion is able to sensibly capture network behavior even with shorter sensing durations.
As a final note, it is important to underline that the observations we make depend of the datasets we use. We believe that similar observations can be made in other settings where mobility is influenced by human behavior. To enable such verification, we provide an implementation of our main analyses in the Python Vicinity package available at the following address: http://vicinity.lip6.fr.
Table of contents :
1 Introduction
1.1 Opportunistic Networks: Characteristics and Challenges
1.2 Motivating Example
1.3 Problem Statement
1.4 Contributions of this Thesis
2 Related Work and Datasets
2.1 Related Work
2.1.1 Contact and intercontact vision
2.1.2 DTN characterization and end-to-end connectivity usage
2.1.3 Routing techniques
2.1.4 Mobility models
2.1.5 Prediction in DTNs
2.2 Datasets
2.2.1 Connectivity assumptions
2.2.2 Real-world datasets
2.2.3 Synthetic datasets
3 Uncovering Vicinity Properties of Intercontacts inDTNs
3.1 The Binary Assertion Issue
3.2 The Notion of Vicinity
3.2.1 Vicinity definition for opportunistic networks
3.2.2 Missed transmission possibilities with binary assertion
3.2.3 Pairwise behavior variability
3.3 Temporal !-vicinity Characterization
3.3.1 !-intercontact distributions
3.3.2 !-contact distributions
3.4 Inner Topological Characterization
3.4.1 The seat of !-vicinities: connected components
3.4.2 !-vicinity ego density Di!
3.4.3 A rule of thumb for card(Vi!
3.5 The Strength of Vicinity Annexation
3.5.1 Threshold optimization
3.5.2 Loss and delays
3.5.3 Overheads
3.6 Recommandations
3.7 Conclusion
4 Digging into the Vicinity Dynamics ofMobile Opportunistic Networks
4.1 Why Vicinity Dynamics?
4.2 Vicinity Package Introduction
4.3 The Asynchronous Vicinity Motion Framework
4.3.1 Timeline generation
4.3.2 Vicinity analysis
4.4 Asynchronous Vicinity Motion: Analyses and Patterns
4.4.1 Short and extended chains
4.4.2 Max-min distance division
4.4.3 Vicinity chains distributions
4.4.4 Vicinity patterns
4.4.5 Asynchronous vicinity motion take-aways
4.5 TiGeR: Synthetic Timeline Generator
4.5.1 Motivation
4.5.2 Generation processes
4.5.3 Evaluation
4.6 Observations
4.7 Conclusion
5 PredictingVicinityDynamics
5.1 Problem Statement
5.2 Vicinity Motion-based Markovian Heuristic
5.2.1 Synchronous vicinity motion (SVM)
5.2.2 Heuristic
5.2.3 Implementation
5.3 Methodology
5.4 Complete Knowledge Heuristic Evaluation
5.4.1 AVM-full
5.4.2 SVM-full
5.5 Partial Knowledge Heuristic Evaluation
5.5.1 AVM-half
5.5.2 SVM-half
5.6 Conclusion
6 Conclusion & Perspectives
6.1 Summary of Contributions in this Thesis
6.2 General Remarks
6.3 Perspectives on Research Directions
A List of Publications
List of Figures
List of Tables
Bibliography
