Keywords: 6, 1 Typical static neighborhood topologies vs dynamic neighborhood

List of Figures 4.3 Performance comparison of all algorithms . . . . . . . . . . . . . . . . . . . 4.4 Delivery delay of GRAD-DOWN with a network of 20, 50 or 100 nodes . . 4.5 Contacts map (from the top, p = 0, 0.1, 0.2, 0.5, 1 respectively) . . . . . . . 4.6 Shortcuts introduced by disorder reduces message passing path length . . . 4.7 Message passing chains (from the top, p = 0, 0.1, 0.2, 0.5, 1 respectively) . . 4.8 Average message passing chain length . . . . . . . . . . . . . . . . . . . . . 4.9 Building block of the Markov chain modeling the message passing process . 4.10 Average delivery delay of FIRST-CONTACT in function of rewiring rate for 100-nodes networks (theoretical result) . . . . . . . . . . . . . . . . . . 4.11 Average delivery delay of GRAD-DOWN algorithm in function of rewiring rate for 100-nodes networks (theoretical result) . . . . . . . . . . . . . . . . 5.1 Evolution over time of the average shortest path length of real DTNs . . . 5.2 Symmetry of the shortest paths in Infocom05 trace . . . . . . . . . . . . . 5.3 The involvement of a node on the shortest path of another node is inversely proportional to the average inter-contact time between these two nodes . . 5.4 Example of the interest dissemination phase . . . . . . . . . . . . . . . . . 5.5 Correlation between the utility values of a node and the shortest dynamic path length from that node to the content subscriber . . . . . . . . . . . .

First and foremost, I would like to express my sincerest gratitude to my supervisors, Prof. Patrick Sénac and Prof. Michel Diaz, without whom this thesis would have not been possible. My special thanks go to them for their guidance and support, insight and knowledge that kept me highly motivated and allowed me to perform my best during this work. They both have been an inspiration to me. I would like to thank Prof. Eric Fleury and Dr. Marcelo Dias de Amorim for offering their precious time to review this thesis. I wish to thank Prof. Ana Cavalli, Prof. Andrzej Duda and Prof. Serge Fdida, for accepting to be members of my dissertation committee.

During these years, I have been in a great research group of nice people from whom I learned a lot. I would like to thank professors Jérôme Lacan, Emmanuel Lochin and Tanguy Pérennou for their stimulating and constructive comments that were very helpful to me to improve my research. I thank Emmanuel for his help to install my working machine and account on Tetrys, the server on which many simulation results in this thesis were produced. I thank my friendly and cheerful fellow PhD students: Victor, Thomas, Tuan, Hugo, Pierre Ugo, Remi, Alex, Chi, Khanh, Hamdi, Rami,... Finally, I thank my family for supporting me throughout all my studies in France, for giving me advice and love at the most difficult moments of my life.

Dynamic networks

Nowadays, we are living in the world of mobile technologies. The two past decades witnessed the sky-rocketing development of mobile telephony. From 12 millions in 1990, the number of worldwide mobile phone subscribers hits 6 billions by the end of 2011, an impressive figure in a world of 7 billions people. With the advent of tablets, PDAs, laptops, the utility of these handheld devices are now not limited to telephoning only, instead users also use them to access to the Internet anywhere at anytime. This ubiquitous world of mobile and wireless systems has important impacts not only on everyday life of people by gradually changing their habits of communication but also at the economic, industrial and cultural levels with lots of new forms of applications, services and usages.

In such mobile space, the last recent years were the golden years of mobile applications which conducted to a dramatic growth of mobile data traffic over the Internet, specifically mobile video. In 2011, mobile data traffic was 8 times the size of the entire global Internet in 2000. And it is expected that this amount of data will still increase at high pace in the near future. This stresses the importance for research and development on higher Although the concept is promising and seductive, it raises several challenges to both theoretical and experimental network science. The dynamic nature of the network makes classical approaches applied for infrastructure-based networks impracticable. Classical protocols basically based on the assumption of an end-to-end path cannot be applied due to the lack of guarantee for such path in this dynamic context. Consequently, there is the need for a deep understanding of the nature of these networks and for proposing adapted communication solutions. One of the most basic and interesting open questions is how to deliver efficiently messages between dynamic nodes. This thesis aims to answer this question by first proceeding to an in-depth analysis on the nature of dynamic networks and then providing an efficient practicable routing solution based on the intrinsic properties of these networks.

Modeling Dynamic Networks

Dynamic networks, as defined in the previous paragraph, are formed by human opportunistic contacts and hence are strongly tied to human dynamics expressed through the movements. As the first step to understand the nature of these networks, we provide a model to capture various characteristics of human mobility usually observed in real traces. It was shown that human movement has preferential attachment and attraction to geographic zones properties. This means that people moves often between a few sites

Behavioral and Structural Properties of Dynamic Networks

and have a high probability to return to these sites. It was also shown that the flight distance of human movement follows a power law.

Traditionally, mobile networking researches are based on simple mobility models, e.g.

Random Waypoint, Random Direction models, in which parameters are chosen from an uniform distribution. These models are simple and mathematically tractable but not realistic. They fail to express the basic characteristics of human mobility and hence introduce biases to research results in dynamic networks. Therefore a more realistic and still tractable model is necessary for mobile networking community. Some elaborated mobility models are proposed but they are either too complex for analysis or miss important features such as reflect network protocol performance as observed in real situation.

In this thesis, we provide a mobility model that captures a large spectrum of human mobility features, reflect with high fidelity salient characteristics of human movement, and still is simple to implement and mathematically tractable [START_REF] Nguyen | STEPS-an Approach for Human Mobility Modeling[END_REF]. This first contribution serves as a foundational brick for the next part of the thesis.

Behavioral and Structural Properties of Dynamic Networks

Based on the previously introduced model, we study the spatio-temporal structure of dynamic networks. The research about dynamic networks under the umbrella of network science is still new and then there is still a few insight about how these networks evolve at the spatio-temporal structural level. The understanding of these characteristics of dynamic networks, like for the static networks' counterparts, are necessary for designing and implementing efficient network protocols, especially for solving the routing problem that we address in this thesis.

In the context of static networks, it was observed the emergence of small-world structure in which the clustering coefficient is high and the shortest path length is short. This special structure allows information to spread as fast as in a random network. Many real static networks exhibit these properties. In this thesis, by extending the notion of clustering and shortest path to spatio-temporal domain, we show that dynamic networks have similar behaviors. Moreover, we show that highly mobile nodes are one of the factors contributing to the emergence of the small-world phenomenon in dynamic networks [2].

On the other hand, we investigate contact patterns in dynamic networks. It was shown that human contacts exhibit some degree of regularity and periodicity. We propose a model to capture this contact regularity and order degree in dynamic networks and show that, if correctly exploited, the disorder can improve significantly information routing in such networks [3,[START_REF]1 Time structure of a DTN[END_REF]. We propose two routing algorithms that exploit the temporal structure of human contact network to route information with a good tradeoff between resources and performance. These findings are the theoretical foundations of our routing solution.

Routing in Dynamic Networks

Basically, routing is the process of selecting a path to send messages from a sender to a receiver. This is the core process of any communication systems. For instance, the postal service performs this process to find the fastest way to send parcels while minimizing the operational cost; in the old time, telephone network operators switched jacks to make connections between two telephones. Network operators employ routing protocols to route data packets between autonomous systems, etc. In the Internet, routing algorithms are implemented in each router to assure this process. When a packet arrives at a router, the algorithm is in charge of selecting the next destination to forward the package.

Nowadays, the Internet functions based on the Internet Protocol (IP). IP is the principal protocol assuring the packet routing between hosts in the Internet. Traditionally, routers use IP address which is a binary suites assigned for each network interface to forward datagrams over the network. IP address is the analog of postal address. Each host has an IP table which consists of addresses of known hosts. When a sender host has a packet to send to a destination host, it writes its IP address and the destination's address in the IP packet header before sending the packet to another host. The routers when receiving the packet check the IP address of the destination, consult their IP table and then use the routing algorithm to find the next host to forward the package. This process occurs at different level of the Internet (i.e., local, intra domain, inter domain)

depending on the position of the source and the destination. The routing algorithm may be different at each level.

In an infrastructured environment, routing algorithms are based on the assumption that an end-to-end path between the sources and the destination exists. On the contrary in a dynamic network, nodes and links are unstable, making that end-to-end paths are not guaranteed. For instance, a node can be disconnected from the network because it is out of radio range of other nodes or because of battery shortage. Basically, routing in 1.4. Routing in Dynamic Networks such environment must rely on the store-move-and-forward communication mechanism in which relay nodes keep messages in their buffer until the next opportunistic contact with another node.

Besides, with the huge amount of content, content sharing becomes one of the most important usage of the Internet. Unfortunately, the Internet was invented with the hostcentric idea in mind (i.e. to make communication between two host) and hence tie the content identity with IP address of the host storing the content. This tight coupling is not suitable for the new usage of the Internet of today. For instance, it poses problem by forcing users to rely on an address resolution system to retrieve a content which might be stored in many servers over the Internet. The new content-centric communication paradigm aims to solve these problems by considering the content as the first class citizen in the Internet world. Specifically, in such paradigm, IP address is replaced by content name. Routing in a content-centric manner means that using the content name to request and retrieve the content. This is usually based on the publish-subscribe mechanism in which users subscribe for a content and the content providers publishes and send the requested content to the users.

Applying the content-centric paradigm in the context of dynamic networks is the most suitable manner to enable content sharing over dynamic environment. Using IP and the implementation of an address resolution is inefficient due to the continuously changing topology of dynamic networks. The main problem is how to choose the relay nodes that minimize some cost functions, e.g., delay or delivery ratio, in such dynamic environment. This is a hard problem because nodes have generally only a local view of the network.

Basically, researches propose heuristics which can be divided in two categories: oblivious and non-oblivious routing approaches. In the first approach, routers forward packets to any encountered node without considering the network context. The second approach consists of using local informations learned through opportunistic contacts, e.g., contact history or social information, to select good relays.

In this thesis, leveraging on the theoretical findings previously studied, we propose an efficient routing protocol for content-centric dynamic networks [START_REF] Nguyen | STIgmergy Routing (STIR) for Content-Centric Delay-Tolerant Networks[END_REF][START_REF] Nguyen | Swarm-based Intelligent Routing (SIR) -a New Approach for Efficient Routing in Content Centric Delay Tolerant Networks[END_REF]7]. In this protocol, nodes maintain an utility function that sums up their proximity to the destination and update the utility value at each opportunistic contact. The utility values form a gradient field in the network allowing contents to "flow" along the steepest slopes to reach the destinations. We show that this protocol outperforms classical approaches.

Organization of this thesis

The main contributions of this thesis are structured as follows. In Chapter 2, we propose STEPS -a simple parametric model which covers a large spectrum of human mobility patterns. The model implements two seminal features of human mobility, i.e., preferential attachment and attractors. We show that this model can capture various characteristics of human mobility usually observed in real traces, e.g., inter-contact/contact time distribution.

In Chapter 3, we study dynamic networks in both space and time domain to extract their salient structural characteristics. Specifically, we show that highly dynamic nodes can play the role of bridge between disconnected components and help to reduce significantly the characteristic path length of the network, hence contributing to the emergence of the small-world structure in dynamic networks. In STEPS, starting from a regular dynamic network in which nodes tend to stay in their preferential zones, we rewire it by progressively increasing the percentage of nomadic nodes in the network. We show that, as soon as the ratio of nomadic nodes passes 10%, the network exhibits a small-world properties with a high dynamic clustering coefficient and a low shortest dynamic path length.

In chapter 4, we study temporal contact patterns in dynamic networks, on particular their disorder degree. We show that real dynamic networks exhibits some degree of disorder and irregularity which, if correctly exploited, improves significantly routing performances. First, we introduce a model for the disorder degree of dynamic networks. This model allows us to rewire contacts in a totally regular temporal network with a probability p, so injecting some disorder degree into the network. We then investigate intensively real dynamic network and found that their disorder degree ranges from medium to high (p real ranges from 50% to 70%). We introduce a simple but efficient greedy algorithm which leverages on the temporal structure of dynamic networks to deliver messages with a good performance/resource tradeoff. Simulation and analytical analysis show that this algorithm outperforms other approaches. Moreover, the algorithm achieves its optimal performance in networks with a disorder degree of 20%.

Based on the idea developed in Chapter 4, in Chapter 5, we propose a new efficient routing protocol for content-centric dynamic network. In this protocol, nodes maintain an utility function which summarizes their spatio-temporal proximity to the destination node.

The utility values update is performed during each opportunistic contact. Consequently, a gradient field is formed in the network allowing the messages to flow along the steepest 1.5. Organization of this thesis slope to reach the destination. This routing algorithm can be easily adapted to both address-centric or content-centric dynamic networks. Simulation results show that the protocol outperforms classical routing protocols for DTNs.

Chapter 6 brings out a potential application of content-centric dynamic networks in the context of mobile cloud computing. In this chapter, by applying swarm optimization techniques, we show that mobility can increase dramatically the processing capacity of dynamic networks. On the other hand, we show that the network structure has also an important impact on the processing capacity of the network [8].

Finally, chapter 7 will conclude the thesis and give directions for future works. Mobility is the seminal process which underlines dynamic networks composed of human portable devices. In this chapter, we are interested in the modeling of such dynamic networks. We introduce Spatio-TEmporal Parametric Stepping (STEPS) -a simple parametric mobility model which can cover a large spectrum of human mobility patterns. STEPS abstracts spatio-temporal preferences in human mobility by using a power law to rule the nodes movement coupled with two fundamental mobility principles. Nodes in STEPS have preferential attachment to favorite locations where they spend most of their time. Via simulations, we show that STEPS is able, not only to express peer to peer properties such as inter-contact/contact time and to reflect accurately realistic routing performance, but also to express the structural properties of the underlying interaction graph such as the small-world phenomenon. Moreover, STEPS is easy to implement, flexible to configure and also theoretically tractable.

Introduction

Human mobility is known to have a significant impact on performance of opportunistic networks. Unfortunately, there is no model that is able to capture all the characteristics of human mobility due to its high complexity. We introduce Spatio-TEmporal Parametric

Stepping (STEPS) -a powerful formal model for human mobility or mobility inside social/interaction networks. The introduction of this new model is justified by the lack of modeling and expressive power, in the currently used models, for the spatio-temporal correlation usually observed in human mobility.

We show that preferential location attachment and location attractors are invariants properties, at the origin of the spatio-temporal correlation of mobility. Indeed, as observed in several real mobility traces, while few people have a highly nomadic mobility behavior the majority has a more sedentary one.

We assess the expressive and modeling power of STEPS by showing that this model successes in expressing easily several fundamental human mobility properties observed in real traces of dynamic network:

-The distribution of human traveled distance follows a truncated power law.

-The distribution of pause time between travels follows a truncated power law.

-The distribution of inter-contact/contact time follow a truncated power law.

-The underlying dynamic graph can emerge a small-world structure.

The rest of this chapter is structured as follows. After an overview of the state of the art in Section 2.2, we present the major idea and formally introduce STEPS in Section 2.3.

Section 2.4 shows the capacity of STEPS to capture salient features observed in real dynamic networks, going from inter-contact/contact time to epidemic routing performances and small-world phenomenon. Finally we conclude the chapter in Section 2.5.

Related works

Human mobility has attracted a lot of attention of not only computer scientists but also epidemiologists, physicists, etc because its deep understanding may lead to many other important issues in different fields. The lack of large scale real mobility traces made that research is initially based on simple abstract models, e.g., Random Waypoint, Random Walk (see [9] for a survey). These models whose parameters are usually drawn from an uniform distribution, although are good for simulation, can not reflect the reality and even are considered counterproductive in some cases [START_REF] Yoon | Random waypoint considered harmful[END_REF]. In these models, there is no notion of spatio-temporal preferences.

Recently, available real data allowed researchers to understand deeper the nature of human mobility. The power law distribution of the traveled distance was initially reported in [START_REF] Brockmann | The scaling laws of human travel[END_REF] in which the authors study the spatial distribution of human movement based on bank note traces. The power law distribution of the inter-contact time was initially studied by Chaintreau et al. in [START_REF] Chaintreau | Impact of human mobility on opportunistic forwarding algorithms[END_REF]. In [START_REF] Karagiannis | Power law and exponential decay of inter contact times between mobile devices[END_REF], Karagiannis et al. confirm this and also suggest that the inter-contact time follows a power law up to a characteristic time (about 12 hours) and then cut-off by an exponential decay.

In [START_REF] González | Understanding individual human mobility patterns[END_REF], the authors show that people have a significant probability to return to a few highly frequented locations. Another study [START_REF] Song | Modelling the scaling properties of human mobility[END_REF] shows that humans show significant propensity to return to the locations they visited frequently before, like home or workplace.

These two intrinsic human mobility characteristics, i.e., location preference and attractor, are implemented in our model. Some more sophisticated mobility models have been proposed. In [START_REF] Ekman | Working day movement model[END_REF], the authors have proposed an universal model being able to capture many characteristics of human daily mobility by combining different sub-models. With a lot of parameters to configure, the complexity of this type of model makes them hard to use.

In [START_REF] Lee | Slaw: A mobility model for human walks[END_REF], the authors propose SLAW -a Random Direction like model -except that the traveled distance and the pause time distributions are ruled by a power law. An algorithm for trajectory planning was added to mimic the human behavior for always choosing the optimal path. Although being able to capture statistical characteristics like inter-contact, contact time distribution, the notion of spatio-temporal preferential attachment is not covered by this model.

Another modeling stream aims to integrate social behaviors. In [START_REF] Musolesi | A community based mobility model for ad hoc network research[END_REF], a community based model was proposed in which the movement depends on the relationship between nodes. The network area is divided in zones and the social attractivity of a zone is based on the number of friends in the same zone. The comparisons of this model with real traces show a difference for the contact time distribution. Recent research shows that some mobility model (including [START_REF] Hsu | Modeling spatial and temporal dependencies of user mobility in wireless mobile networks[END_REF]), despite of their capacity of capturing spatio-temporal characteristics, deviate significantly in routing performances when compared to the ones obtained with real traces [START_REF] Thakur | On the efficacy of mobility modeling for dtn evaluation: Analysis of encounter statistics and spatio-temporal preferences[END_REF]. This aspect that has not always been considered in existing models is indeed really important because it

shows the capacity of a model to reproduce a fundamental feature of a dynamic network.

Characterizing & Modeling Human Mobility

STEPS is inspired by observable characteristics of the human mobility behavior, specifically the spatio-temporal correlation. Indeed, people share their daily time between some specific locations at some specific time, e.g., home/office, night/day. These spatio-temporal patterns repeat at different scales and has been recently observed on real traces [START_REF] Hsu | Modeling spatial and temporal dependencies of user mobility in wireless mobile networks[END_REF].

On a short time basis, i.e., a day, a week, we can assume that one have a finite space of locations. According to these observations, we define two mobility principles:

• Preferential attachment: the probability for a node to move in a location is inversely proportional to the distance from his preferential location.

• Attractor: when a node is outside of his preferential location, he has a higher probability to move closer to this location than moving farther.

From this point of view, the human mobility can be modeled as a finite state space Markov chain in which the transition probability distribution expresses a movement pattern. In STEPS, a location is modeled as a zone which corresponds to a Markov chain state.

Inside a zone, nodes can move freely according to a random mobility model such as Random Waypoint. The displacement between zones is drawn from a power law distribution whose the exponent value expresses the more or less nomadic behavior. By simply tuning the power law exponent, STEPS can cover a large spectrum of mobility patterns from purely random ones to highly localized ones. Besides, complex heterogeneous mobility behavior can be described by combining nodes with different mobility patterns as defined by their preferential zones and the related attraction power. Group mobility is also supported on our implementation. Hereafter, we give the details of this model.

STEPS

Assume that the network area is a square torus1 divided in N square zones. The distance between zones is defined according to a metric. We use Chebyshev distance in this case. Figure 2.1(b) illustrates an example of a 5 × 5 torus with the distances from the zone A. One can imagine a zone as a geographic location (e.g., home, school, supermarket) or a logical location (i.e., a topic of interest such as football, music, philosophy, etc).

Therefore, we can use the model to study both human geographic mobility and human social behaviors. In this thesis, we deal only with the first case.

In such structured space, each mobile node is associated with a preferential zone z pref .

For the sake of simplicity, we assume that each node is attached to one zone. However, this model can be extended by associating a node with several preferential zones. The node movement between zones is driven by a power law satisfying the two mobility principles described above. The probability mass function of this power law is given by

P [D = d] = β (1 + d) α , (2.1)
where D is a discrete random variable representing the distance from z pref , α is the power law exponent that represents the attraction power of z pref and β is a normalizing constant.

From Equation 2.1 we can see that, the farther a zone is from the preferential zone, the less probability the node to move in. This is the principle of preferential attachment.

On the other hand, when a node is outside its preferred zone, it has a higher probability to move closer to this one than moving farther. This is the principle of attraction. In consequence, with a power law, the model is able to capture two basic characteristics of human mobility.

This small set of modeling parameters allows the model to cover the full spectrum of mobility behaviors. Indeed, according to the value of the α exponent a node can have a more or less nomadic behavior. For instance, -when α < 0, nodes have a higher probability to choose a long distance than a short one and so the preferential zone plays a repulsion role instead of a attraction one;

-when α > 0, nodes are more localized, hence tend to stay in their preferential zones;

-when α = 0, nodes move randomly towards any zone with a uniform probability.

We summarize the details of STEPS in Algorithm 1. A MATLAB implementation of STEPS can be downloaded at [START_REF] Nguyen | STEPS mobility model[END_REF].

The Underlying Markov Chain

In this section, we give the details and the properties of the Markovian model underlying STEPS. Wherever node's preferential zones are, the torus structure gives different nodes the same spatial structure, i.e., they have the same number of zones with a given distance from their preferential zones. More specifically, for a distance d, we have 8d zones with equal distances from z pref . Consequently, the probability for a node to choose one among these zones is

P z i , d z i z pref = d = 1 8d P [D = d] = β 8d(1 + d) α . (2.2)
Because the probability for a node to select a destination zone z i depends only on the distance between z i and z pref , wherever the node is residing, it has the same probability

Input: Initial zone ← z pref 1 repeat 2
Choose a random distance d from the probability distribution (2.1);

p contact = P A (z 0 )P B (z 0 ) + . . . + P A (z n-1 )P B (z n-1 ) = N -1 i=0 P (z i ) 2 = dmax d=0 1 8d β (d + 1) α 2 , (2.5)
where

d max = √ N 2
is the maximum distance between zones in the torus.

Let ICT be the discrete random variable which represents the time elapsed before A and B are in contact again. One can consider that ICT is the number of trials until the first success of an event with probability of success p contact . Hence ICT follows a geometric distribution with the parameter p contact . Therefore, the probability mass function of ICT is given by

P [ICT = t] = (1 -p contact ) t-1 p contact . (2.6)
It is well known that the continuous analog of a geometric distribution is an exponential distribution. Therefore, the inter-contact time distribution for i.i.d. nodes can be approximated by an exponential distribution. This is true when the attractor power α is equals to 0, i.e., when nodes move uniformly, because there is no spatio-temporal correlation between nodes. But when α = 0, there is a higher correlation in their movement and in consequence the exponential distribution is not a good approximation. Indeed, in [START_REF] Cai | Toward stochastic anatomy of inter-meeting time distribution under general mobility models[END_REF], the authors report this feature for the Correlated Random Walk model where the correlation of nodes induces the emergence of a power law in the inter-contact time distribution. In the following, we provide simulation results related to this feature for STEPS.

Figure 2.2 gives the log-log and linear-log plots of the complementary cumulative distribution function or CCDF of the inter-contact time that results from a simulation of the Markov chain described above when α = 0 and α > 0. In the first case, the intercontact time distribution fits an exponential distribution (i.e., is represented by a linear function in the linear-log plot) while in the second case it fits a power law distribution (i.e., is represented by a linear function in the log-log plot) with an exponential decay tail.

These results confirm the relationship between the spatio-temporal correlation of nodes and the emergence of a power law in inter-contact time distribution.

Fundamental Properties of Opportunistic Networks in STEPS

It is worth mentioning that a mobility model should express the fundamental properties observed in real opportunistic networks. In this section, we show that STEPS can, indeed, capture the salient characteristics of human mobility.

Inter-Contact Time Distribution

The inter-contact time is defined as the delay between two encounters of a pair of nodes. Real traces analysis suggest that the distribution of inter-contact time can be approximated by a power law up to a characteristic time (i.e., about 12 hours) followed Chapter 2. Understanding and Modeling Dynamic Networks by an exponential decay [START_REF] Karagiannis | Power law and exponential decay of inter contact times between mobile devices[END_REF]. In the following we will use the set of traces presented by Chaintreau et al. in [START_REF] Chaintreau | Impact of human mobility on opportunistic forwarding algorithms[END_REF] as base of comparison with STEPS mobility simulations. In order to demonstrate the capacity of STEPS to reproduce this feature, we configured STEPS to exhibit the results observed in the Infocom 2006 conference trace which is the largest trace in the dataset. Table 2.1 summarizes the characteristics of this trace. given by the STEPS simulations fits with the one given by the real trace.

Contact Time Distribution

Because of the potential diversity of nodes behaviors, it is more complicated to reproduce the contact duration given by real traces. Indeed, the average time spent for each contact depends on the person. For instance, some people spend a lot of time to talk while the others just check hands. We measured the average contact duration and the average node degree, i.e., the global number of neighbor nodes, of the Infocom06 nodes and ranked them according to their average contact duration. The result is reported in

Routing Performance

An often neglected feature when introducing a mobility model is its ability to reproduce the performances given by routing protocols on top of real traces. In order to assess the capacity of STEPS to offer this important property, we ran Epidemic routing on STEPS and Infocom06 trace and compared the respective routing delays. For each trace, the average delay to spread a message is measured as a function of the number of nodes who

Understanding Opportunistic Network Structure with STEPS

A good mobility model should allow not only to express faithfully peer-to-peer interaction properties such as inter-contact time and contact time, but also to reproduce the fundamental structure of the underlying interaction graph as modeled by a temporal graph, i.e. graphs with time varying edges. The structural properties of static interaction graphs have been studied leading to the observation of numerous instances of real interaction graph with a high clustering and a low shortest path length [START_REF] Watts | Collective dynamics of small-world networks[END_REF]. Such a structure of graph is called small-world. With respect to routing, the small world structure induces fast message spreading in the underlying network.

Our research on the small-world phenomenon in dynamic networks is fully detailed in Chapter 3. In this chapter, we provide only the preliminary ideas which lead to those final results. Specifically, this is our first attempt to extend the notions of clustering coefficient and shortest path length introduced in [START_REF] Watts | Collective dynamics of small-world networks[END_REF] for dynamic networks.

Let G(t) = (V(t), E(t)) be a temporal graph with the time varying set of vertexes V(t)

and the time varying set of edges E(t). We define the temporal clustering coefficient and temporal shortest path length as follows.

-Temporal clustering coefficient : Let N (w, i) be the set of neighbors of node i for a time window w. The temporal clustering coefficient is defined as the ratio of the actual number of connections between the neighbors of i to the possible number of connections between them during the time window w. Intuitively, it represents the cliquishness of a time varying friendship circle. Formally, that is

C i = 2 j |N (w, j) ∩ N (w, i)| |N (w, i)| (|N (w, i)| -1) , (2.7)
where j is a neighbor of i and |X| denotes the cardinal of X.

-Temporal shortest path length : Let R ij (t) ∈ {0, 1} denotes a direct or indirect connection, i.e., via multiple connections at different times, between node i and node j at time t. The shortest path length between i and j is defined as the earliest time from an initial time t 0 when there is a connection between them. That is

L ij = inf{t|R ij (t) = 1}. (2.8)
To visualize the phenomenon in STEPS, we create scenarios where there are two categories of nodes with different attraction power. In the first category, nodes have a high mobile behavior (i.e., α is small) while in the second one, they are more localized (i.e., α is large). The idea is to "rewire" a highly clustered and weakly dynamic network (i.e., with the population in the second category) by introducing highly mobile nodes into that graph. By tuning the ratio of number of nodes between these two categories, we measure the metrics defined in (2.7) and (2.8). Figure 2. 5(b) shows that between a regular and random structure, the network exhibits structures where the temporal clustering coefficient is high while the temporal shortest path length is low. This first result suggests the existence of the small-world phenomenon in dynamic graphs which will be studied in Chapter 3. Moreover, this result shows the expressive capacity of STEPS to reproduce behaviors of real dynamic networks.

Conclusion

In The small-world phenomenon first introduced in the context of static graphs consists of graphs with high clustering coefficient and low shortest path length. This is an intrinsic property of many real complex static networks. Recent research has shown that this structure is also observable in dynamic networks but how it emerges remains an open problem.

In this chapter, we first formalize the metrics to qualify the small-world structure and then investigate in-depth various real traces to highlight the phenomenon. With help of STEPS, we point out that highly mobile nodes are at the origin of the emergence of the small-world structure in dynamic networks. Finally, we study information diffusion in such small-world networks. Analytical and simulation results with epidemic model show that the small-world structure increases significantly the information spreading speed in dynamic networks.

Introduction

In his famous experiment, Milgram showed that the human acquaintance network has a diameter in the order of six, leading to the small-world qualification. Watts and Strogatz later introduced a model of small-world phenomenon for static graphs [START_REF] Watts | Collective dynamics of small-world networks[END_REF]. They proposed a random rewiring procedure for interpolating between a regular ring lattice and a random graph. Between these two extrema, the graph exhibits an exponential decay of the average shortest path length contrasting with a slow decay of the average clustering coefficient.

Interestingly, numerous real static networks exhibit such property. From a communication perspective, Watts and Strogatz also pointed out that a small-world network behaves as random network in terms of information diffusion capacity.

However, the great majority of studies on small-world networks properties and behaviors focused on static graphs and ignored the dynamics of real mobile networks. For example, in a static graph, an epidemic cannot break out if the initial infected node is in a disconnected component of the network; conversely in a mobile network, nodes movements can ensure the temporal connectivity of the underlying dynamic graph. Moreover, an epidemic can take off or die out depending not only on the network structure and the initial carrier, but also on the time when the disease begins to spread. These aspects cannot be captured by a static small-world model.

In order to formalize the dynamic small-world phenomenon, we extend to dynamics networks the notions of dynamic clustering coefficient and shortest dynamic path. By studying the evolution of these metrics from our rewiring process, we show the emergence of a class of dynamic small-world networks with high dynamic clustering coefficients and low shortest dynamic path length. We then demonstrate the capacity of STEPS to capture these structural characteristics of mobile opportunistic networks by showing that, when increasing progressively the dynamicity of a network from an initial stable state, then this rewiring process entails the emergence of a small-world structure.

The rest of the chapter is structured as follows. Section 3.2 introduces previous works that inspired our contribution. In Section 3.3, after having formally defined the notions of dynamic clustering coefficient and shortest dynamic path length, we analyze various real traces and show the intrinsic properties of dynamic networks that induce the small-world phenomenon. We show how the small-world structure emerge in dynamic networks in Section 3.4. In Section 3.5, from simulations and analytical analysis, we study information diffusion performances in dynamic small-world networks. Finally, Section 3.6 concludes the chapter.

Related works

In [START_REF] Watts | Collective dynamics of small-world networks[END_REF], Watts and Strogatz introduce a model of small-world phenomenon in static graphs. From a regular ring lattice, they rewire randomly edges in this graph with a probability varying from 0 (i.e. leading to a regular network) to 1 (i.e. leading a random graph). During this process they observed an abrupt decrease of the average shortest path length, leading to short path of the same order of magnitude as observed in random graphs, while the clustering coefficient is still of the same order of magnitude than the one of a regular graph. This features suggested the emergence of the small-world phenomenon.

The authors also demonstrate that this graph structure, observed in many real static networks, allows information to diffuse as fast as in a random graph.

Kleinberg [START_REF] Kleinberg | Navigation in a small world[END_REF] extended the model to 2-d lattices and introduced a new rewiring process. This time, the edges are not uniformly rewired but follow a power law 1 d α where d is the distance on the lattice from the starting node of the edge and α is the parameter of the model. Newman [START_REF] Newman | The Structure and Function of Complex Networks[END_REF] proposed another definition of the clustering coefficient which has a simple interpretation and is easier to process. The authors argue that the definition in [START_REF] Watts | Collective dynamics of small-world networks[END_REF] favors vertices with low degree and introduces a bias towards networks with a significant number of such vertices.

Although research pays much attention to the small-world phenomenon in static networks, either through modeling or analytical analysis, the small-world phenomenon in dynamic networks like opportunistic networks is still not well understood. This is partly due to the lack of models and metrics for dynamic graphs. Recently, J.Tang et al. [START_REF] Tang | Temporal distance metrics for social network analysis[END_REF] defined several metrics for time varying graphs, including temporal path length, temporal clustering coefficient and temporal efficiency. They showed that these metrics are useful to capture temporal characteristics of dynamic networks that cannot be captured by traditional static graph metrics. The definition of dynamic path, introduced in this paper, is close to their definition (we had the dual metric of the number of hops). We also introduce a new definition of dynamic clustering coefficient which captures more accurately the dynamics of opportunistic networks.

In [START_REF] Tang | Small-world behavior in time-varying graphs[END_REF], the authors highlight the existence of the small-world behavior in real dynamic network traces. Using the definition of temporal correlation introduced in [START_REF] Clauset | Persistence and periodicity in a dynamic proximity network[END_REF], they show that real dynamic networks have a high temporal correlation and low temporal shortest path, suggesting a dynamic small-world structure. In this modeling work, we extend consistently to dynamic networks the initial small-world metrics defined in [START_REF] Watts | Collective dynamics of small-world networks[END_REF] (i.e., shortest path length and clustering coefficient).

Small-world Phenomenon in Dynamic Networks

In this section, we formalize the notion of small-world phenomenon in dynamic networks by introducing two metrics used for qualifying such phenomenon: shortest dynamic path length and dynamic clustering coefficient. Then by analyzing extensively real opportunistic network traces, we show fundamental characteristics which are at the origin of the dynamic small-world phenomenon.

Dynamic Small-world Metrics

Shortest Dynamic Path Length

Basically, the shortest path problem in static graphs consists in finding a path such that the sum of the weights of its constituent links is minimized. From a graph theory point of view a dynamic networks can be described by a temporal graph, i.e., a temporal sequence of graphs that describe the discrete evolution of the network according to nodes and links creation and destruction events. A path in a dynamic network can be seen as an ordered set of temporal links that allow a message to be transferred using the storemove-forward paradigm between two nodes. Formally, let l t ij be a link between node i and node j at instant t. A dynamic path from node u to node v from time t 0 to time t is described by a time ordered set p uv (t 0 , t) = l t 0 ui , l t 1 ij , . . . , l t wv where t k+1 > t k . We consider two metrics of dynamic paths:

-Delay : the sum of the inter-contact times between consecutive links which constitutes the path.

-Number of hops : the number of temporal links which constitutes the path.

This leads to the following definition of shortest dynamic path length.

Definition 1

The shortest dynamic path is the path giving the minimum amount of delay 4 . If there are several paths giving the same delay, then we select the one giving the minimum number of hops. Formally, the shortest dynamic path length between i and j from time t 0 is

L t 0 ij = inf {t -t 0 |∃p ij (t 0 , t)} . (3.1)
The shortest dynamic path length of a network of N nodes from time t 0 is the average of 4. we can also have another definition for minimizing the number of hops. In this work, we focus only on delay constrained path.

the shortest dynamic path lengths of all pairs of nodes in the network

L t 0 = ij L t 0 ij N (N -1) . (3.2)
To find the shortest dynamic path length of all pairs of nodes, we propose an algorithm leveraging on the following interesting property of adjacency matrix in static graphs.

The adjacency matrix A is defined as the matrix in which the element (A) i,j ∈ {0, 1}

at row i and column j denotes the existence of a link between node i and node j. If we process the power n of such matrix, then its element (A n ) i,j gives the number of paths of length n between i and j. Indeed, for example, when n = 2, (A

2 ) i,j = k (A) i,k × (A) k,j
sums all the possibilities to go from i to j through an intermediate node k. We extend this property to dynamic networks. Let A t , t = 0, 1, . . . , n be the adjacency matrix of a dynamic network at time t. The matrix C t obtained as follows

C t = A t ∨ A 2 t ∨ . . . ∨ A n t , (3.3)
where A i t denotes the binary version of the matrix A i t (i.e. the element (A t ) i,j equals to 1 if (A t ) i,j > 0 and 0 otherwise) has its elements (C t ) i,j which indicate if there is a direct or indirect link (up to n hops) between i and j at time t. Indeed, (C t ) i,j is the logical sum of all possibilities to have a direct or indirect link (up to n hops) between i and j at time t. In consequence, the product

D t = C 0 C 1 . . . C t (3.4)
results in a matrix in which the element (D t ) i,j specifies, when not null, that there is dynamic path of delay t between i and j. Therefore the shortest dynamic path length from node i to node j is given by the smallest value of t such as (D t ) i,j equals to 1.

It is straight-forward to demonstrate that if a node k belongs to a shortest path between node i and node j then the i to k sub-path gives the shortest path between i and k. Therefore the shortest path between two nodes i and j can be easily backwardly reconstructed. Note that at time t two nodes can be connected to each other via a multiple hops path. To find the complete spatio-temporal path with all the intermediate nodes,

we simply apply a breath first search each time we find a spatial multiple hops link. In practice, as it's unlikely to have a large number of nodes connected to each other at a given moment, we can optimize the algorithm by limiting the number of iterations n in Equation 3.3 to an upper bound of the network diameter. Finally, this algorithm is more efficient (time complexity O(n 3 )) than the depth first search approach as proposed in [START_REF] Tang | Temporal distance metrics for social network analysis[END_REF] (time complexity O(n 4 )).

We provide a MATLAB implementation of this algorithm in [START_REF] Nguyen | All-pairs Shortest Dynamic Path Length Algorithm[END_REF].

Dynamic Clustering Coefficient

As defined in [START_REF] Watts | Collective dynamics of small-world networks[END_REF], the clustering coefficient measures the cliquishness of a typical friend circle. The clustering coefficient of a node is calculated as the fraction of actual existing links between its neighbors and the number of possible links between them. The clustering coefficient of a network is calculated by averaging the clustering coefficients of all the nodes in the network. In [START_REF] Newman | The Structure and Function of Complex Networks[END_REF], Newman defines the clustering coefficient in term of transitivity. The connection between nodes u, v, w is said to be transitive if u connected to v and v connected to w implies that u is connected to w. The clustering coefficient of a network is then calculated as the fraction of the number of closed path of length two over the number of path of length two, where a path of length two is said to be closed if it is a transitive path. This definition is simple to interpret and easy to calculate. Considering that, the initial definition gives more weight to nodes with low degree and introduces a bias towards graph composed of several of these nodes, in this work, we favor Newman's definition and extend it to dynamic networks.

In [START_REF] Tang | Temporal distance metrics for social network analysis[END_REF] In order to avoid this temporal bias, we propose a new definition of dynamic clustering coefficient which captures the dynamics of the degree of transitivity and is independent of the measuring time interval. [START_REF] Brockmann | The scaling laws of human travel[END_REF])

when the transitive path from i to j is formed, that is C t 0 i = 1 t-t 0 .
The dynamic clustering coefficient of a network of N nodes is then calculated by averaging over the dynamic clustering coefficient of all the nodes from time t 0

C = 1 N i C i . (3.5)
We also provide a MATLAB code for computing the dynamic clustering coefficient at [START_REF]Dynamic Clustering Coefficient Algorithm[END_REF].

Opportunistic Network Traces Analysis

In this section, we analyze extensively real opportunistic network traces to understand how small-world behavior emerges in dynamic networks. We first apply the above definitions to highlight the existence of dynamic small-world phenomenon on these traces. For that, we use the data sets from the Haggle project [START_REF] Chaintreau | Impact of human mobility on opportunistic forwarding algorithms[END_REF][START_REF] Leguay | Opportunistic content distribution in an urban setting[END_REF] which consists of the recording of opportunistic bluetooth contacts between users in conference or office environments.

The settings of these data sets are summarized in Table 3.1.

For each trace, we measure the shortest dynamic path length and the dynamic clustering coefficient every 2000 seconds to see the evolution of these metrics over time. The obtained values are then normalized and plotted in Figure 3.2. We can observe a periodic hours. This can be easily explained by the fact that human daily activity is periodic with nigh/day phases. Indeed, people are more nomadic during day while they are mostly sedentary at night. Besides, it is interesting to note that the dynamic clustering coefficient and the shortest dynamic path length evolve in opposite phase. Despite of a slight diversity in different traces due to differences in nodes number and density, traces durations, etc, during the dynamic phase (i.e., day, for instance, the period around 24 hours in Infocom2005 trace), these networks always exhibit high dynamic clustering coefficients and low shortest dynamic path lengths, suggesting the existence of a dynamic small-world phenomenon.

To explain the emergence of this phenomenon, let us focus on and analyze the structure of these networks during the dynamic phases. In the Watts and Strogatz model, the smallworld phenomenon emerges when shortcut edges are randomly added to a regular graph.

These shortcuts allow the average shortest path length to be reduced significantly while conserving network nodes's cliquishness. We argue that in dynamic networks, mobile nodes are implicitly at the origin of these shortcuts. Indeed, it is known that people spend their daily life among different social communities at specific locations at different times (e.g., colleagues at office in the morning, family at home in the evening). A community can be disconnected from the others in space and/or in time. Besides, some people are more "mobile" than other, they have contacts in many communities and move often between these communities or areas. These "nomadic" nodes contribute to reduce significantly the shortest dynamic path length from nodes in a disconnected component to the rest of network and hence contribute to the emergence of the dynamic small-world phenomenon.

To identify the spatio-temporal shortcuts in dynamic networks, we introduce a metric that measures the influence a node has on the characteristic dynamic path length of the network. The nodes with highest influence are the ones whose removal from the network increases the most the average shortest dynamic path length of the network. To identify these nodes one may adapt to dynamic networks the notion of betweeness centrality already introduced for static networks. In the context of dynamic networks, we call it dynamic betweeness centrality. Consider a node i, first of all, we measure the average of the shortest dynamic path length between all pairs of nodes s, t except paths from and to i. Then, we remove i from the network and perform the same measure. The dynamic betweeness centrality of i is defined as the ratio between these two measures. Formally, that is

x i = st L st st L st , (3.6)
where L st and L st are respectively the shortest dynamic path lengths from s to t after and before removing i.

We measure the dynamic betweeness of all nodes at different times on the traces. We then apply our allpairs-shortest-dynamic-path algorithm to find all the shortest dynamic paths from node 31 to others before and after removing node 34. Figure 3.5 shows that node 34 is crucial for node 31 to efficiently communicate with other nodes at that instant. Therefore node 34 plays the role of a spatio-temporal shortcut between node 31 and the other nodes. This result can be observed for any node with a high dynamic betweeness. Indeed, if the so disconnected network part is a giant component, then the impact of the removal of a dynamic shortcut can dramatically increase the characteristic dynamic path length of the network.

Modeling Dynamic Small-world Structure with STEPS

The previous section showed that the dynamic small world phenomenon is intrinsic to a great diversity of opportunistic network traces. Therefore, the definition of a model that abstracts this phenomenon in order to study the impact of its emergence on dynamic networks communications performances is a significant issue. In this section, we

show the modeling and expressive capacity of the STEPS model introduced in Chapter 2 for capturing the dynamic small-world structure in opportunistic networks. As evoked previously, the dynamic small-world phenomenon results from human mobility behaviors:

-People move between communities -Some people are nomad while the others are more sedentary. These nomadic nodes move from zone to zone, contributing to reduce the network diameter.

Consider an opportunistic network modeled by STEPS in which each node belongs to a preferential attachment zone. We introduce two types of nodes: sedentary nodes which move only inside their preferential zone and nomadic nodes which can move between zones. Nodes moving in two different zones cannot be connected and therefore nodes in different zones can communicate only through the movement of nomadic nodes. Initially, nomadic nodes are uniformly distributed over all zones. We introduce another parameter of STEPS p which is the fraction of nomadic nodes.

Obviously, when p equals to 0, there is no possible communication between nodes in different zones and hence the network is totally partitioned in disconnected zones. On the contrary, when p equals to 1, all the nodes are nomadic and hence there are dynamic paths between clusters and in consequence the network is highly connected. In consequence, the rewiring process consists in varying p from 0 to 1. We are interested in the properties of networks which are formed between these two extrema.

We confidence intervals. We observe that the shortest dynamic path length drops rapidly as soon as we introduce a small percentage of nomadic nodes (i.e. less than 10 %) into the network while the clustering coefficient remains very high. This result is consistent with the original static small-world model described in [START_REF] Watts | Collective dynamics of small-world networks[END_REF] and show how the small-world phenomenon can emerge in opportunistic networks. Following the understanding and modeling of the small world phenomenon in dynamic networks, this section studies the effect of the phenomenon on information diffusion performances. We present here the analytical and simulation results obtained with the At each time t, mobile nodes jump to another site while sedentary nodes stay where they are. Initially, the network has 1 infected node and all other nodes are susceptible.

We formulate the dynamics of the network's infection through a differential equation as follows.

Consider a node i. Let x i (t) be the random variable that denotes the probability of node i being infected at time t. Let's express the probability that i becomes infected between time t and t + dt. As a static node i can only be infected by a mobile node m, this infection occurs with probability δ mi (i.e. probability that node m jumps to site i). As a consequence, the probability that the infection (or information) is transmitted during the interval dt is βdt where β is the transmission rate, which is a standard parameter of the SI epidemic model. Summing over all the mobile nodes and then multiplying by the probability 1x i that i is not infected at time t, we obtain the differential equation

dx i dt = β(1 -x i ) m δ mi x m . (3.7)
On the other hand, for a mobile node to be infected, the node must be in contact with a mobile or static node that is already infected. If a mobile node i jumps to a site j where resides an static node, the infection occurs with probability x j + m =i δ mj x m because i can receive the information from either j or another mobile node. We obtain

dx i dt = β(1 -x i )(x j + m =i δ mj x m ) . (3.8)
On the contrary, if the destination site j is associated to a mobile node then the probability of infection is m =i δ mj x m and hence

dx i dt = β(1 -x i ) m =i δ mj x m . (3.9)
Combining all these cases, we obtain the following matrix differential equation describing the dynamics of the system

dx dt =β(1 -x) • (1 -m) • [D(m • x)] + + m • {D [(1 -m) • x + D(m • x)]} , (3.10)
where x = [x 1 . . . x N ] is the random vector containing nodes infection probabilities and m is the binary vector in which m i = 1 for a mobile node and m i = 0 for a static node.

The matrix

D =     δ 11 . . . δ 1N . . . . . . . . . δ N 1 . . . δ NN     = λ     1 . . . 1 (1+d 1N ) α . . . . . . . . . 1 (1+d N 1 ) α . . . 1    
is the stochastic matrix describing the stationary state of the system.

To have an approximated solution of Equation 3.10, we integrate it by numerical method. We also ran simulations with a network of 100 nodes, with α equals to 0, β equals to 1 and different values for the fraction of mobile nodes. The average over 100 simulations is then compared with the analytical results. Finally, we run simulation with the complete version of the small-world model. The obtained result is the average over 10 simulations of a 100-nodes network with the same configurations described above. Figure 3.9 shows a similar result compared to the simplified case. The effect of displacement time between zones only spreads the curves so that the epidemic take much longer time to take off.

Conclusion

In this chapter, we have explained the formation, evolution, behavior and performances of dynamic small-world networks. We first formalized the metrics that qualify the smallworld structure in dynamic networks. From an in-depth analysis of real mobility traces, we then highlighted the small-world phenomenon in real dynamic networks. In STEPS, from a highly clusterized network composed of nodes with localized moves, we perform a rewiring process which consists in varying the percentage of nomadic nodes in the network.

These highly mobile nodes play the role of bridges between disconnected clusters and hence reduce significantly the shortest dynamic paths between nodes. Finally, from a joint use of analytical analysis and simulations, we studied information diffusion in dynamic smallworld networks. We showed that the emergence of a small-world structure in dynamic networks is accompanied by a sudden improvement of information diffusion performances in the network. For our best knowledge, this is the first attempt to explain the emergence of the small-world phenomenon in dynamic networks. However, we are convinced that there is still room for improvement. Although one contributing factor of the small-world structure was found, further unique properties of dynamic networks might be contributing as well and hence should be also investigated. Dynamic networks, such as mobile opportunistic networks, exhibit some degree of regularity on their temporal contact patterns [START_REF] Clauset | Persistence and periodicity in a dynamic proximity network[END_REF]. The impact of this regularity on network performances has not been well studied and analyzed. In this chapter, we study this temporal dimension of dynamic networks and its impacts on routing performances. We propose a simple parametric network model which covers a large spectrum of contact patterns from strictly periodic to fully random ones. Based on this model, we study the impact of contact patterns regularity on routing performances and we show how to exploit this temporal structure to navigate with a good resource/performance tradeoff in dynamic networks.

Simulation and analytical analysis show that efficient routing with respect to their degree of regularity emerge within a subset of dynamic networks. Moreover, we show that there is a specific degree of regularity where routing performance achieves its optimum.

Introduction

The advent of new generations of wireless communication devices, coupled with the ever-increasing growth of multimedia contents, make multimedia services becoming one of the most resources-consuming use of the Internet. In this thesis, we envision a network at the edge of the Internet in which human portable devices, endowed with peer-to-peer communication and sensing capacities, communicate each other without infrastructure to offer potentially free infrastructureless new multimedia services. Because of their mobility nature, these dynamic networks might suffer from nodes and links churns, and hence can be classified within the scope of Delay/Disruption Tolerant Networks (DTNs). These

Human-Centric DTNs, if successfully deployed, will play the role of a complement to infrastructure-based networks by freeing users from infrastructure dependence and reducing the load on the network core. These networks will pave the way for an pervasive computing environment to which users can access anywhere, anytime. One can imagine many future applications of this type of network, e.g., content sharing and retrieval, gaming, recovery networks, offloading, etc.

The modeling and study of the properties of these dynamic networks under the umbrella of the science of dynamic and stochastic graphs is a recent scientific field when compared to the field of static networks and their underlying graph models [32]. Therefore there remains numerous open questions. One of the most interesting fundamental problem is the issue of efficient routing in such networks. Indeed, unlike routing in static networks with the support of the well developed static graph theory, there is still no widely developed theoretical background to understand deeply the routing issues in dynamic networks. In the context of DTNs, several routing algorithms and heuristics have been proposed [33], trying to answer some specific questions about routing while usually ignoring and not leveraging on the profound structural properties of dynamic networks.

In this chapter, we aim to contribute to understanding the impact of the dynamic structure of Human-Centric DTNs on information routing. In DTNs, communication relies on intermittent contact between nodes and their mobility. Routing in such a network means finding a temporal path between a source node and a destination node. The definition of such path has been previously introduced in Chapter 3. Finding an efficient temporal path is made difficult by the lack of a-priori knowledge of the evolution of the dynamic network topology. In other words, nodes can base their forwarding decisions on their local knowledge based on a limited temporal and spatial scope only. In the context of acquaintance networks [START_REF] Jeffrey Travers | An Experimental Study of the Small World Problem[END_REF], it was shown that people implicitly solve the information routing problem by leveraging on spatial or structural properties of the network, such as nodes relative or absolute positions [START_REF] Kleinberg | Navigation in a small world[END_REF], nodes centrality [START_REF] Watts | Identity and search in social networks[END_REF], to enforce the forwarding decision.

The rest of the chapter is structured as follows. Section 4.2 introduces related works that inspired our contribution. In Section 4.3, we present the underlying temporal structure of dynamic networks, formalize the notions of disorder degree in contact patterns and then introduce a simple parametric network model to capture this characteristic of dynamic networks. In Section 4.4, we investigate real dynamic network traces to estimate the disorder degree of these networks. In Section 4.5, we introduce two greedy algorithms which leverages on the temporal structure to navigate in dynamic networks. Simulation results of their performances and optimality are also presented. Analytical results are discussed in Section 4.6. Finally, Section 4.7 will conclude the chapter.

Related Works

With the potential of future pervasive mobile networks, recent researches have drawn attention to the theories of dynamic networks (see [START_REF] Holme | Temporal networks[END_REF] a for a good review of recent researches on temporal networks). The persistence and regularity of communication patterns is one interesting aspect of dynamic networks. In In the context of human acquaintance networks, the famous experiment of Milgram [START_REF] Jeffrey Travers | An Experimental Study of the Small World Problem[END_REF] consists in sending a package from a group of persons living in Boston to a randomly chosen person in Massachusetts only through their acquaintances. The obtained result was striking in the fact that the chains of persons leading to the destination are very short, having on average only 6 peoples. This can be considered a typical example of routing in a social network. The routing problem we are addressing here is different. We consider Human-Centric DTNs in which nodes (i.e., mobile devices) can communicate only through peer-to-peer contacts (i.e., when they are in the radio range of each other) and there is no long range contact unlike the postal service in the Milgram case. Besides, nodes in the network may not know each other in advance.

Kleinberg [START_REF] Kleinberg | Navigation in a small world[END_REF] is interested in the algorithmic component of the experiment of Milgram, i.e. how individuals can find such short routes in such large social network. The author proposes a simple model that embeds the geographic world in a 2D lattice (the result can be generalized to other number of dimensions). Nodes have local contacts with neighboring nodes and choose a long-range contact with a far node with a probability inversely proportional to the distance to the later. The probability distribution follows a power law d -α where d is the distance and α is the unique parameter of the model. By applying a greedy algorithm in which nodes select the contact closest to the destination as message relay, the author demonstrates that the routing delay reaches its optimum (i.e., in logarithmic time) when α equals to 2 and is polynomial otherwise. This is due to the isotropic structure of the network at the optimum which establishes gradient allowing nodes to have a cue to find short paths. In [START_REF] Kleinberg | Complex Networks and Decentralized Search Algorithms[END_REF], Kleinberg discusses various decentralized search algorithms.

Watts et al. [START_REF] Watts | Identity and search in social networks[END_REF] proposed another model for searching in social networks. The network is embedded in a hierarchical social structure in form of b-ary tree. One can imagine starting from the top level which represents the whole world, and the lower levels of the tree will correspond to countries, cities, etc down to the smallest social organization in which one people knows only one other. In such structure, the distance between nodes is measured by the height of the nearest common ancestor. The authors proposed a method to generate networks from this structure by connecting randomly nodes at distance x with probability p(x) = c exp -αx where α is the parameter of the model and c is a normalizing constant. Again, they found that there is only one value of α allowing a greedy search algorithm to perform in logarithmic time otherwise the delay is polynomial.

The above approaches work under the assumption that nodes know some information on the whole network or on the destination which are not necessarily true in the case of DTNs. In the context of DTNs, routing has drawn much attention (see [33] for a survey).

Generally, we can classify the routing protocols in three categories: oblivious routing, mobility-based routing and social-based routing. In the first approach, nodes don't use any information on the network and either randomly forward the message or just flood it into the network. In the second approach, nodes leverage on the information on mobility like their position to make the forwarding decision. The third approach consists in using the social information, e.g., node degree, detected communities, contact history, to forward the message to the best candidate nodes. These informations are not always available or difficult to obtain.

In this work, we postulate that mobile nodes may leverage on the intrinsic temporal structure that exists in every DTNs to efficiently route information. Intuitively, when looking for someone through a third person, people usually ask questions such as "when was the last time you met him/her?, Do you know someone who recently meets him/her ?" etc. Therefore, time is also a cue to consider for routing in DTNs. We address this issue in the next section.

Temporal Structure of Dynamic Networks

This section aims to introduce the temporal structure that exists inherently in DTNs and a model that captures the disorder degree of such networks. Dynamic networks such as DTNs, in contrast to static networks, evolve in temporal and spatial dimensions. In Chapter 2 and Chapter 3, we have modeled and analyzed dynamic networks in both dimensions. However, if we focus only on the temporal aspect of the network by making abstraction of node's movement, the network can be seen as a temporal graph G(E(t), V (t)) where E(t) and V (t) are respectively the set of edges and vertexes of the network at time t.

One of the most simple and natural structure that could emerge from a dynamic network could be given by a relation of temporal and spatial order. This consideration leads to study if it makes sense to consider the notion of spatio-temporal proximity between nodes in a dynamic network. Intuitively, we can consider that the more often a node is close to another node the smaller is its spatiotemporal distance from this node. Therefore this notion of spatiotemporal distance is define from a statistical point of view according the time and space behavior of nodes. Moreover, this notion of distance can be recursively defined by considering the transitive closure of contacts between nodes. This consideration raises the following questions that will find answers in this chapter and the following ones:

-Is there any simple way to process in every node, just from its opportunistic contacts, its spatiotemporal distance to the other nodes?

-Can we use this notion and the resulting order relation entailed on the space of nodes to improve routing decisions in dynamic networks?

Following opportunistic contacts between nodes from a source to a destination along a dynamic path (as defined in Chapter 3) every node can potentially process how far the source is from it. In other words every node of a dynamic path can be aware of the distance between the source and itself. However we have seen that a temporal path is not symmetric. In other words, if a nodes knows the spatiotemporal distance between the source and itself, the symmetric temporal distance is not necessarily the same. Fortunately, as shown in Chapter 5, several traces analysis that we have driven lead to the conclusion that the spatio temporal distance in dynamic graph as defined later in this chapter is symmetric. This mean that during some time window the dynamic path length between node i and node j is equal to the dynamic path length between j and i. Therefore as soon as a nodes of a dynamic network can process their respective distance they can use this information during opportunistic contact for assessing if a node in contact is "closer" or "farther" from a destination node.

More formally, this notion of temporal distance is base on the two following metrics -Delay d j i (t): the delay of node i with respect to node j at time t is the elapsed time from the last moment when there was a dynamic path from j to i. For example, if i was connected to node k who had previously been connected to j at time t 0 then

d j i (t) is t -t 0 .
Formally,

d j i (t) = {inf(t -t 0 )|t 0 ≤ t and
∃ a dynamic path from j to i starting at time t 0 } .

-Hops h j i (t): the number of nodes on the path. In the previous example, the dynamic path is j → k → i so the number of hops is 2.

If mobile nodes in a DTN keep track of these metrics with respect to other nodes, the metric values will maintain an order relation between all the nodes in the network which represents a "temporal and spatial proximity" between nodes. In consequence, this order relation forms a gradient field from a node towards the others. It's worthy to note that this temporal structure is inherent to any dynamic network in which there are intermittent contacts between nodes. Figure 4.1 illustrates this temporal structure with respect to one network node.

To build such structure, we need to maintain two scalars d k i (t) and h k i (t) for each destination k at each node i. This is analog to maintaining routing tables in IP networks.

Initially, the metrics are null because nodes do not know about each others. Through opportunistic contacts, nodes learn about the existing of other nodes and update their scalars. The algorithm to build and maintain the temporal structure is summarized in Algorithm 2. Indeed, when two nodes are in contact, the node which is farther from path and hence updates its delay value (i.e., equals to the other node's delay value) and its number of hops (i.e., equals to number of the other node plus 1). Note that the delay metric can be implemented by two methods. The straightforward implementation of the definition consists in using a timer to keep track of the delay with respect to a destination. We consider here a simpler method that consists in memorizing only the last moment when there was a dynamic path from the destination. That is, d k i (t) = {sup(t 0 )|t 0 ≤ t and ∃ a path from k to i starting at time t 0 }. These two simple metrics reflect how a DTN is structured. Indeed, a DTN may be very regular, i.e., with a periodic contact pattern in which a node is always connected to the same node after the same time interval. In such network, the metric values are constant or periodic. On the contrary, the network regularity may be random such that a node can be connected to any node at any time. In this case, the metric values evolve randomly. We introduce in this chapter a simple parametric model able to capture the regularity/disorder degree of DTNs. This model covers the full scope between a totally regular network and a totally random network by gradually increasing the disorder of network's contact patterns.

Let us consider a network of N nodes n 0 , . . . , n N -1 that evolves over time with a periodic contact pattern as follows. At time 0, n 0 is connected to n 1 ; at time 1, n 1 is connected to n 2 ; at time 2, n 2 is connected to n 3 and so on. This contact pattern repeats We introduce disorder into this network by rewiring its links as follows. For each contact, with a probability p we replace it by a contact between another pair of nodes.

With probability 1p we let the contact unchanged. We operate this rewiring process by advancing in time until time T max (i.e. we rewire the first contact then the second contact and so on until the last contact at T max ). We illustrate the process in Figure 4.2.

This rewiring process results in:

-When p = 0, the network is totally regular and expresses a periodic contact pattern.

Disorder Degree of Real Dynamic Networks

-When p = 1, the network is totally random i.e. any contact can happen at any time.

-By varying p between 0 and 1, we gradually inject disorder into the network. Therefore the parameter p quantifies the disorder degree of the dynamic network.

Disorder Degree of Real Dynamic Networks

In this section, we investigate various real traces of Human-Centric DTNs to estimate their disorder degree using the previously described model. To estimate the rewiring probability p of real networks, we first need to identify the periodic contact patterns in the traces. We apply the following algorithm to detect the contact patterns and estimate the value of p. For each pair of nodes (i, j), their contact times are collected and a time series c ij (t) in which c ij (t) = 1 if i encounters j at time t and 0 otherwise is generated.

The auto-correlation coefficients of these series

Corr ij (k) = Tmax-k i=1 c ij (i)c ij (i + k) (4.1)
give us the number of contacts that are separated by k time units. We then reorder the auto-correlation coefficients in descending order and select the second mode M ij for each pair of nodes (the first mode corresponds to k = 0). The lag k that gives this mode is the most frequent contact period. For each pair of nodes, we count the number of k-periodic contacts then sum up globally. Consequently, an estimate of p is given by

p real = contacts -ij M ij contacts . (4.2)
We ran the algorithm on various traces ( [START_REF] Scott | {CRAWDAD} data set cambridge/haggle (v. 2009-05-29[END_REF][START_REF] Meroni | {CRAWDAD} data set unimi/pmtr[END_REF][START_REF] Leguay | {CRAWDAD} data set upmc/content (v. 2006-11-17[END_REF][START_REF] Eagle | Reality mining: sensing complex social systems[END_REF]). These network traces contain recorded bluetooth connection activities in different environments. Table 4.1 shows the characteristics and the estimated p real values of all traces.

The results show that the analyzed Human-Centric DTNs exhibit a low disorder degree ranging from 10% to 40%. We can see that the large traces seem to have a larger disorder degree than the small ones. Especially, spontaneous networks, such as networks at conferences, exhibit a higher randomness than business structured networks. The results also suggest that, the more a DTN is structured around a business activity, the more regular the network is. Routing aims to find an efficient path from a node to another which minimizes some costs. That is, if a node i wants to send a message m to a node j, how do i can find a path to j which minimize some cost function. In this thesis, we propose a simple and efficient solution using the temporal structure introduced in the previous section. As previously discussed, the temporal structure creates a order relation between nodes. Such order relation can be the cue allowing a node to find the efficient path. Indeed, when two nodes are in contact, they know which one is closer to the destination. Therefore the decision of forwarding the message to the destination can be based on this order relation.

A straightforward solution of routing in DTN is to send the message to every encountered node while keeping a message copy. This viral diffusion or flooding solution, while guaranteeing the best delay induces buffering and network capacity overheads, which make this solution not scalable and impracticable in reality. In the following, for focusing on the impact of contact regularity on routing, we will consider the basic and worst case solution where only one copy of each packet is kept in the whole network.

Let us introduce a class of routing algorithms A that uses only one message copy reach the destination. Let assume that at time t, a node i search an efficient path towards a node j. It creates a message m to j. At each contact with a node k, following the forwarding strategy of A, i will decide whether or not to forward m to k. the delay, the delivery rate and the overhead which are 3 basic metrics to evaluate routing protocols in DTNs. We introduce here two greedy algorithms that exploit the temporal structure. In these algorithms, messages follow either upward or downward the gradient slope of the temporal structure to reach their destination. With the first algorithm named GRAD-DOWN, detailed in Algorithm 3, a node forward the message if the encountered node has a lower delay or an equal delay with a lower hops. Conversely, the GRAD-UP algorithm, detailed in Algorithm 4, consists in forwarding the message as soon as the encountered node has a higher delay or an equal delay with a higher hops. We will study the performance of these algorithms in function of the disorder degree of the network.

Simulation Results & Discussions

To evaluate the performance of these algorithms, we implemented them in the ONE simulator for Delay Tolerant Networks [START_REF] Keränen | The ONE simulator for DTN protocol evaluation[END_REF]. We also compare them with 4 other algorithms: Direct Delivery, First Contact, PROPHET [44] and dLife [START_REF] Moreira | Opportunistic routing based on daily routines[END_REF]. Direct Delivery is the most radical solution in which a node waits until being in contact with the destination to deliver the message. FIRST-CONTACT consists in forwarding systematically the message at the first contact. The more elaborated PROPHET routing protocol is based on the contact history to infer the probability that a node will encounter the destination.

Finally, dLife is a social-based approach that exploits the human daily routines to deliver messages.

For a given rewiring probability p, we generate under MATLAB a regular connection trace of a network of 100 nodes with T max being 10000 time units and rewire it following the model described in Section 6.4. The rewired trace is then fed to the ONE simulator [START_REF] Keränen | The ONE simulator for DTN protocol evaluation[END_REF]. As we want to focus only on measuring the impact of the disorder on these routing algorithms, the connection bandwidth and the buffers are assumed to be infinite. A message between a randomly taken pair of nodes is generated each 5 time units. Because our approach does not rely on an assumed daily routine, to be fair with dLife, we create a favorable simulation setting for this protocol by assigning a contact cycle to a day and a contact to a time slot.

We choose to evaluate the delivery delay, the delivery rate and the overhead (i.e., the number of relays to perform a successful delivery)-three basic performance measuresfor all algorithms. For each value of p, we run each algorithm on 10 generated random traces. The performance is then measured as the average over 10 simulation runs. Figures 6.2 coupled with the 95% confidence intervals. We can see that the algorithms behaves differently as we vary the disorder degree in the network. With a highly regular network, GRAD-UP outperforms all other algorithms while Direct Delivery offers the worst performances among them. GRAD-DOWN and PROPHET perform quite bad in a regular network with a higher delivery rate and a lower overhead for GRAD-DOWN. FIRST-CONTACT and dLife deliver fast but with low delivery rate in a regular network. Moreover, the naive forwarding strategy of FIRST-CONTACT makes that its overheard is much higher than the others (in the order of 10 4 ). For easy-reading, we do not plot this result.

When the disorder degree increases in the network, GRAD-DOWN outperforms all other algorithms by minimizing the delivery delay while maximizing the delivery rate and keeping a low overhead. As expected, the Direct Delivery algorithm performs worst in term of delivery delay and delivery rate due to its radical forwarding strategy. GRAD-UP and FIRST-CONTACT performs bad when the network is disordered. PROPHET also takes advantage of the disorder to deliver faster and with higher delivery rate than GRAD-UP and FIRST-CONTACT. dLife performs well in a highly disordered network, with slightly better performances in term of delivery delay and delivery rate compared to GRAD-DOWN. It's overhead is as good as Direct Delivery. This is a surprising result because dLife is supposed to work well in a regular network.

When the network is totally random, the algorithms have similar performances. In overall, GRAD-DOWN has the best performances over a wide range of network structures compared to the other algorithms. Its sibling GRAD-UP performs in an inverse manner.

This first results show that the temporal structure creates a natural gradient field allowing, when exploited, the messages to reach their destinations with low delay, high delivery rate and low overhead. We will look closer at this phenomenon to understand how the temporal structure is formed and maintained in the network. In the following, we will focus on the delivery delay, which is an important performance measure for a routing algorithm in Human-Centric DTNs.

While varying the disorder degree, we can see the following results for GRAD-UP and GRAD-DOWN:

-They behave in opposite manners face to disorder.

-When a regular network has 10% of rewired contacts, they have the same performances.

-When a regular network has 20% of rewired contacts, GRAD-DOWN achieves its -In a random network, they give the same performances.

These results show that routing performances in DTNs greatly depends on the degree of disorder. Specifically when we introduce a little level of disorder into the network (i.e., 20% rewired links), the network become highly navigable using our approach. But the more disorder increases, the less we can leverage on time structure.

We repeated the same experiment with GRAD-DOWN and a network of 20 and 50 nodes. Figure 4.4 shows the same behavior of delivery delay with the optimum point at p equals to 0.2 regardless the number of nodes. This result suggests that this is a intrinsic property of the dynamic networks.

We draw the evolution of contacts in the network in Figure 4.5. The x-axis depicts the time and the y-axis depicts the node's IDs. A connection between two nodes is represented by a vertical line connecting the corresponding IDs. Figure 4.5 from top to bottom shows 6 realizations during 1000 time units of a 100-nodes network rewired with probability p equals respectively to 0, 0.1, 0.2, 0.5, 0.7 and 1. We can see that, in a totally regular network, the contacts follow the cycle:

n 0 ↔ n 1 , n 1 ↔ n 2 , . . . , n N -1 ↔ n 0 . In consequence,
according to the two previously introduced metrics and then updating procedure, when the contact between node n i and n i+1 happens, n i is always "closer" to the destination k than n i+1 in term of delay and number of hops, and hence has a smaller gradient value.

In that case, GRAD-UP achieves its best performance, as we can see on Figure 6. GRAD-DOWN takes advantage of these shortcuts to make faster deliveries while GRAD-UP is penalized by them. At the other extrema, in a totally disordered network, any contact can happen at any time hence there is no longer interest in leveraging on order in the contacts. Too many shortcuts contribute to suppress the cue to find efficient paths resulting in message converging more slowly towards the destination. The results also shows that when p equals to 0.1 (i.e. the point where GRAD-UP and GRAD-DOWN give the same delay), flowing along the contact cycle and sometimes going backwardly through the shortcuts versus waiting the next cycle and benefiting the shortcuts to go faster, gives the same amount of delay. Intuitively, the optimal point (i.e. p equals to 0.2) corresponds to a network structure in which the contact order is still conserved but the number of injected shortcuts is just enough to reduce the delay until being in contact with a node with smaller gradient value. We illustrate this intuition in Figure 4.6.

We conformed this intuition for GRAD-DOWN by collecting the traces of messages which successfully arrived at their destinations. These traces contain the chains of nodes by which the message passed through and also the time when it was forwarded to these nodes. Figure 4.7 shows 10 chains for p equals to 0, 0.1, 0.2, 0.5, 0.7 and 1. The x-axis depicts the time and the y-axis depicts the node's IDs. A totally regular network makes the nodes holding a message to wait during 100 time units before forwarding it to another node. On the other hand, the algorithm does not perform better in a totally random network because the message goes back and forth between nodes. In consequence the delivery delay is high. A slight disorder improves significantly the performance thanks to the shortcuts that reduce the path length. To be more precise, Figure 4.8 shows the average chain length (i.e. number of nodes on the chain) over 10 simulation runs. It is clear that we achieve the best performance when p equals to 0.2.

Analytical Analysis

In this section, we define an analytical approach to formalize the simulation results

given in the previous section. We consider the navigation as a dynamical process running on a temporal graph. This message passing process is governed by the rewiring process which depends on the rewiring rate of the network model. Considering the model as described in the previous section, we can note that each rewiring cycle is composed of N steps (i.e. rewiring the contact between n 0 and n 1 , n 1 and n 2 , etc). We show these steps and the associated rewiring probabilities for each node pair in Table 4.2.

Without loss of generality, let assume that node n 0 is the destination node. Let denote d i , h i , g i respectively the delay, number of hops, and gradient with respect to the destination node. Assume that a node n i holds a message for n 0 at time t. At this time, the system can be in any of the N steps of the rewiring process and hence there are N

Contact

Probability

n 0 -n 1 1 -p 2p N (N -1) 2p N (N -1) . . . 2p N (N -1) n 1 -n 2 2p N (N -1) 1 -p 2p N (N -1) . . . 2p N (N -1) n 2 -n 3 2p N (N -1) 2p N (N -1) 1 -p . . . 2p N (N -1) . . . . . . . . . . . . . . . . . . n N-2 -n N-1 2p N (N -1) 2p N (N -1) 2p N (N -1) . . . 1 -p n i -n j , ∀j = i + 1 2p N (N -1) 2p N (N -1) 2p N (N -1) . . . 2p N (N -1)
Table 4.2: Probabilities of contacts during the rewiring cycle possible states. As there are N nodes, we have in total N 2 states that m can be in. These states are related to each other via the rewiring probability. In consequence, the message passing process can be represented by a Markov chain with N 2 states.

We first solve the First Contact case. We denote i, r the state in which the message is at node n i and the rewiring process is at step r. Note that to achieve this state, the rewiring process must be at step (n -1) mod N and the message can be at any node in the previous state. Moreover, this message is passed from the node n (i-1) mod N to node n i with probability 1p. For all other nodes, the probabilities are 2p N (N -1) . On the other hand, from the state i, r , the rewiring process passes to step (r+1) mod N . The message is passed to node n (i+1) mod N with probability 1p and to other nodes with probabilities 2p N (N -1) . In consequence, although the number of states is large, the Markov chain is built from the basic block which is illustrated in Figure 4.9. Let t r i be the time to hit S starting from the state i, r . We obtain the following system of linear equations:

   t r 0 = 0 t r i = 1 + N -1 j=0 p j,(r+1) mod N i,r t (r+1) mod N j , ∀i = 0 (4.3)
where p y x denotes the transition probability from state x to state y. Indeed, the second equation expresses the lower part of the building block in Figure 4.9. Starting from state i, r , the message can be forwarded in 1 time unit to any node in the next step of the rewiring process with the corresponding probabilities.

We propose a method to numerically solve the linear system under its matrix form Ax = B. It is straightforward to see that the vector B is full of -1 values which correspond to the term 1 on the right side of the equations. To easily build the matrix A, the linear equations is organized so that the element's indexes of its rows and columns are ordered as follows.

                               t 1 1 ...t 1 N -1 t 2 1 ...t 2 N -1 ... t N -1 1 ...t N -1 N -1 t N 1 ...t N N -1 t N -1 1 . . . M 0 0 . . . 0 -I t N -1 N -1 t 0 1 . . . -I M 1 . . . 0 0 t 0 N -1 . . . . . . . . . . . . . . . . . . t N -3 1 . . . 0 0 . . . M N -2 0 t N -3 N -1 t N -2 1 . . . 0 0 . . . -I M N -1 t N -2 N -1                               
Note that we omit all the terms t n 0 , ∀n ∈ 0, . . . , N -1 and therefore it remains N (N -1) equations. The elements of the matrix A are arranged in such way that the matrix contains blocks that have the same structure. The easiest way to achieve this is to regroup the equations computing the time starting from different nodes at the same rewiring step. For instance, row 1 to row N -1 correspond to the equations computing t 1 1 , . . . , t 1 N -1 , row N to row 2(N -1) correspond to the equations computing t 2 1 , . . . , t 2 N -1 , etc. Consequently, the blocks -I are simply a diagonal matrix having the diagonal values equal to -1 which is relative to the terms on the left side of the equations. Besides, the block M r contains the probabilities in columns r + 1 of Table 4.2. The element (M r ) a,b is the probability of having a contact between the node n a and the node n b at the rewiring step r + 1. Finally, To solve the GRAD-DOWN case, we need to inject in Equation 4.3 the probabilities for a node has a smaller gradient values than another. Therefore, our linear system becomes

         t r 0 = 0 t r i = 1 + N -1 j=0 p j,(r+1) mod N i,r
×pr(g i (r) < g j (r))t where pr(g i (r) < g j (r)) is the probability that the node n i has a smaller gradient value (i.e. smaller delay or equal delay with smaller number of hops) with respect to the destination n 0 than the node n j at the rewiring step r. To compute such probabilities, we formalize the gradient formation and evolution in the network as a dynamical process. According to Algorithm 2, when a node n i i meets a node n j , they exchange their vectors containing the delay and hops values with respect to the known destinations. Let A t be the adjacency matrix summarizing the contacts of the network at time t. Hence the element (A t ) i,j is 1 if there is a contact between the node n i and the node n j at time t + 1 and 0 otherwise.

If such contact exists, the delay of the node n i with respect to the destination n 0 at time t + 1 is then max(d i (t), d j (t)). Consequently, we have

d i (t + 1) = j (A t+1 ) i,j max (d i (t), d j (t)).

The number of hops is calculated based on the delay values

h i (t + 1) = j (A t+1 ) i,j ((h j (t) + 1)f < (d i (t), d j (t)) + h i (t)f ≥ (d i (t), d j (t))),
where f < (a, b) (f ≥ (a, b) respectively) return 1 if a < b (a ≥ b respectively) and 0 otherwise. Indeed, according to Algorithm 2, if the encountered node n j has a higher delay value or f < (d i (t), d j (t)) = 1 then the node n i updates its number of hops to (h j (t) + 1), otherwise it keeps its current hops value. Finally, we get the following dynamical process for the gradient formation and evaluation.

                             d 0 (t + 1) = d 0 (t) + 1 h 0 (t + 1) = 0 d i (t + 1) = j (A t+1 ) i,j max(d i (t), d j (t)), ∀i = 0 h i (t + 1) = j (A t+1 ) i,j ×((h j (t) + 1)f < (d i (t), d j (t)) +h i (t)f ≥ (d i (t), d j (t))), ∀i = 0 (4.5)
The initial conditions of the process are

d 0 (1) = 1, h 0 (1) = 0 and d i (1) = h i (1) = 0, ∀i = 0.
To estimate the probabilities pr(g i (r) < g j (r)), we generate a large number of random traces and compute the dynamical system defined by (4.5) on these traces. We then collect the values of delay and number of hops at time t = r, r + N, r + 2N, . . .. The ratio of the number of times when pr(g i < g j ) over the total number of occurrences gives an estimate of pr(g i (r) < g j (r)).

These probabilities are injected in the linear system (4.4) to compute the final solution.

Conclusion

In this chapter, we have studied the impact of the periodicity and regularity of nodes inter-contacts on information routing in human-centric opportunistic networks. First, we gave a characterization of the spatio-temporal structure of these networks from the notions of spatio-temporal distance between nodes. Then, based on real dynamic network trace analysis, we showed that the inter-contact relations follow some degree of periodicity and regularity. We formalize these notions of regularity and periodicity of contacts via a simple parametric model. From these definitions, we studied the impact of the disorder, expressed as a decrease in the regularity and periodicity of contact patterns, on the performances of routing protocols and showed that a family of routing algorithms can leverage on this disorder to deliver messages efficiently. Especially, we showed that when a dynamic network has a fraction of disorder of about 20%, this algorithm achieves its optimal performance. At the best of our knowledge, this is the first work that studies this aspect of opportunistic networks. However, we are convinced that there are rooms to develop further this research. Especially, the model presented in this research can be extended to be more realistic by considering different frequencies of contact for different nodes. One other possible direction is to combine the two presented routing algorithms to have an adaptive algorithm that performs efficiently in all contexts. In this chapter, based on the properties of dynamic networks analyzed in the previous chapters, we introduce SIR -a Swarm-Intelligence based Routing protocol that aims to efficiently route information in content-centric opportunistic networks. The notion of optimal path in dynamic networks and an algorithm to find such path in a temporal graph have been introduced in Chapter 3. In this chapter, the properties and some invariant features of the optimal path are analyzed and derived from several real traces. We then show how optimal path in content-centric opportunistic networks can be found and used from a fully distributed swarm-intelligence based approach of which the global intelligent behavior (i.e., shortest path discovery and use) emerges from simple peer to peer interactions applied during opportunistic contacts. This leads to the definition of the SIR routing protocol of which the consistency, efficiency and performances are demonstrated from intensive simulations.

Introduction

With billions of increasingly processing and networking efficient nodes at the edge of the Internet, the question to use the fabulous capacity of this "peripheral computing, storage and networking cloud", in complement and independently of the traditional communication infrastructure and services offered by the legacy Internet, makes sense. The efficient use of this pervasive huge cloud of processing, storage and communication resources, potentially available "for free" but underlaid by security, power consumption and performance issues, has lead to a thread of researches in new communication paradigms and protocols adapted to this type of spontaneous and highly dynamic ad-hoc networks.

Specially, two new complementary communication paradigms play a key role in this specific type of communication context, that is, pocket switched [START_REF] Hui | Pocket switched networks and human mobility in conference environments[END_REF] and content centric communication [START_REF] Jacobson | Networking named content[END_REF]. Indeed, according to the dynamic topology, intensive churn, potentially huge space of nodes and nodes diversity intrinsic to this type of networks, classical end-to-end communication paradigms cannot be applied anymore. This leads to consider these networks as a source of content and to replace classical address resolution and management mechanisms by the pivotal concept of content id. In such networking context, the end-to-end paradign can be profitably replaced by the publish/subscribe paradigm.

Moreover, considering that end-to-end connectivity between content providers and users cannot be insured, the store-carry-and-forward paradigm intrinsic to Delay/Disruption Tolerant Networks must be applied in this type of networks. This chapter aims to contribute to the definition and design of new communication architectures, protocols and mechanisms adapted to Content-Centric Disruption Tolerant Networks (CCDTNs) by

proposing a new routing paradigm and protocol for the efficient routing of information between content providers and content users in such networks. Indeed, this original protocol aims to keep track and to follow optimal routes in CCDTN. This protocol, called Swarm Intelligence based Routing (SIR), rests on a "swarm intelligence based approach" of which the collective routing "intelligent" behavior results from the conjunction of nodes' simple individual fully decentralized behaviors.

The rest of this chapter is structured as follows. In Section 5.2, based on the definition of shortest dynamic path introduced in Chapter 3, we analyze several representative real traces to exhibit properties and invariant of these optimal paths. In Section 5.3, we introduce SIR protocol. Via simulation results, Section 5.4 demonstrates the consistency, efficiency and performances of SIR . Section 5.5 reviews the most salient contributions on the issue of routing in DTN. Finally, Section 5.6 concludes the chapter.

Properties of Shortest Dynamic Paths in Opportunistic Networks

In this section, we study the evolution and properties of shortest dynamic paths that can be observed on real mobility traces. The understanding of these properties is important to design efficient routing protocols adapted to opportunistic networks. To study the properties of shortest paths in real opportunistic networks, we analyzed the traces from the Haggle project [START_REF] Chaintreau | Impact of human mobility on opportunistic forwarding algorithms[END_REF] which consists of records of Bluetooth range contacts between devices held by attendees during a conference or within a group of students/researchers in a laboratory. First, temporal snapshots of the network state are taken and the related network adjacency matrix is processed every 200s. The shortest dynamic paths between all pairs of nodes are then computed with the algorithm introduced in Section 3.3.1. Three salient properties of the shortest path length can be observed from these traces.

Periodic Pattern

Symmetry

As defined in Section 3.3.1, paths in opportunistic networks are generally asymmetric due to the temporal ordering of the links constituting the path. It is interesting to verify on real traces if this property entails differences between the shortest dynamic path length of a path and the one simultaneously observed for the reverse path. For each trace, we measured, for each couple of nodes ij, the shortest dynamic path length from i to j and simultaneously the one of the reverse path from j to i. the two time series with the related regression line. Interestingly, the results show a nearly permanent symmetry of the shortest path lengths. In the context of content-centric opportunistic networks, this symmetry means that if the shortest dynamic path is built from a content user to a content publisher and if we assume some stationarity of this length (as observed in the traces during day phases) then the content can be delivered from the publisher to the user along a path with approximately the same length.

Pairwise Inter-contact Time vs the Shortest Dynamic Path

The characterization of the nodes involved in shortest dynamic paths is an important issue. An efficient routing algorithm should take advantage of this characterization to forward content to the best candidate nodes. We use our algorithm to compute the shortest dynamic paths between all nodes and a destination node i. We count the number of occurrences of each node on the shortest dynamic paths to i. At the same time, we compute the pairwise inter-contact time between each node and i. Figure 5.3 shows a correlation between these two measures. Specifically, the shorter is the inter-contact time between a node and the destination, the higher is its frequency of occurrence on the whole set of the shortest dynamic paths. This means, according to the spatiotemporal correlation observed in human mobility patterns [START_REF] González | Understanding individual human mobility patterns[END_REF], that shortest paths have a tendency to converge towards the nodes that the destination

SIR protocol

According to the publish/subscribe communication paradigm, SIR is composed of two phases. 5

Interest Dissemination Phase

In this phase, nodes register their interest for a content by disseminating efficiently the interest message into the network. SIR leverages on this dissemination to dynamically establish a gradient field of which the intensity decreases from the content providers to the content subscribers. We apply the Binary-Spray-and-Wait protocol [START_REF] Spyropoulos | Spray and wait: an efficient routing scheme for intermittently connected mobile networks[END_REF] to the subscription diffusion process for its simplicity and its well known capacity to offer a good tradeoff in term of delay, delivery ratio and resources use. In SIR, a relay node receives not only copies of subscription messages but also the couple of dynamic path metrics defined in Chapter 3 (i.e., delay and number of hops). SIR relay nodes update their utility values via opportunistic contacts according to the delay and number of hops with respect to the content subscriber of their encounters. In consequence, this behavior contributes to establish gradient fields that keep track of the shortest path between content producers and content users. Relay nodes utility is updated according to the following behavior:

-if a relay node meets a content subscriber, the node resets its delay to 0 and updates its number of hops to 1, -if two relay nodes meet each other, the node with the higher delay sets its delay equal to the delay of the other node and its number of hops equal to the number of hops of the other node plus 1 -if two relay nodes meet each other and have the same delay, then they keep theirs metrics unchanged, -otherwise, the delays progresses according to time evolution.

Content Dissemination Phase

When a content provider receives the interest message, the second phase consists in sending back the content to the subscriber by following, ideally, a path as close as 5. We suppose that content has been previously registered via a registration phase not addressed in this contribution. Binary Spray and Wait protocol is also used as the underlying diffusion mechanism. The content forwarding decision consists in always selecting a relay node of which the delay is smaller (i.e., the node closer in time to the content subscriber). If the delays are equal, the content is forwarded if the encountered relay node has a smaller number of hops (i.e., the node is closer to the content subscriber in space).

Simulation Results & Discussion

In this section, we provide an in-depth simulation-based evaluation of the SIR routing protocol. We first verify the hypothesis that the utility function of SIR sums up coherently the proximity of a node to a content subscriber. We run the protocol on real traces and compare the delay of the paths found by SIR with the shortest path found by our all-pair shortest dynamic path algorithm given in Section 3.3.1. This makes it possible to assess how close paths taken by SIR are to shortest dynamic paths. Finally, we compare SIR performances with two classical DTN routing protocols: PROPHET and Spray-and-Wait.

Consistency and Efficiency Issues

Consistency of the Utility Function

As introduced in the previous section, the utility function aims to sum up the proximity of a node to a related content subscriber. Therefore, a positive correlation between these two parameters should entail a linear relationship between the utility value and the shortest dynamic path length. To verify this hypothesis, we have implemented the SIR algorithm in MATLAB and we ran it on Infocom2005 traces which consist of the record of Bluetooth connectivities of 41 handheld devices carried by conference attendees during 3 days. In the selected scenario, one content subscriber diffuses his interest messages for a content to one content provider and then receives the periodically refreshed content from the later. 41 interest message copies, initially disseminated by the subscribing node, allows one to establish a gradient field which is maintained and reinforced by all the nodes during the simulation. On one hand, we measure the evolution of nodes' utility values and on the other hand we process the shortest dynamic path length between the content subscriber and every other nodes. Then, we take the average value over 10 simulation runs. Figure 5.5 shows the correlation between these two time series. One can observe that the utility values and the shortest path length are highly correlated with 68% of correlation coefficient higher than 0.8, which reinforces our hypothesis.

SIR vs Optimal Solution

The goal of this evaluation is to show that by using the gradient field maintained and used by SIR one can achieve a nearly optimal solution. We conduct the same experiment described in the previous section. Then, we measure the content delivery delay at different times of the day. This procedure is repeated with different pairs of subscriber/provider.

On the other hand, we run our all-pairs shortest dynamic path algorithm to compute the shortest dynamic path between these pairs of nodes.

Performance Issues

In this section, we compare SIR routing performances with the ones given by a basic Binary Spray and Wait (BSW) protocol [START_REF] Spyropoulos | Spray and wait: an efficient routing scheme for intermittently connected mobile networks[END_REF] and the ones delivered by PROPHET [44] -an elaborated probabilistic routing protocol. The performances delivered by the BSW routing protocol have to be considered as floor performances that SIR, by extending BSW with We also demonstrated the capacity of this model to reflect at the simulation level the routing performances observed with real traces. In the following scenarios, according to the STEPS model, the network area is modeled as a torus divided in a number of square zones. Inside these zones, nodes move following the Random Waypoint model. Each node is attached to one preferential zone. The movement of nodes between these zones is driven by a parameter of the STEPS model which allows the nodes nomadism to be enforced or reduced according to a power law distribution (i.e. the probability that a mode moving outside his preferential zone has to return to that zone). Figure 5.7 illustrates the initial nodes' spatial distribution and Table 5 The communication protocol stack used in these simulations is simplified and focuses mainly on the network layer. We assume that the connections between nodes have an infinite bandwidth and that nodes have an infinite buffering capacity. The communication channel is modeled as a unicast channel. When two nodes are in communication range, they exchange instantly their buffers containing interest messages, contents and utilities.

We simulate 3 different scenarios to study the impact of three fundamental factors on the protocols: mobility, connectivity and scalability. In these scenarios, we use the average delivery delay and the average delivery ratio (i.e., the ratio between the number of messages received and the number of messages sent) as performance measures.

Scenario A -Impact of Mobility

Mobility is known to have a significant impact on routing performances. In particular, in opportunistic networks, human mobility plays an important role in routing protocol design because it contributes to packets mobility and packet routing. We exposed the three protocols to two different mobility contexts. The first one corresponds to a "sedentary" mobility behavior where people tend to spend the main part of their time in specific locations (e.g., home, workplace) and move barely far from these preferential places. In STEPS, this characteristic is expressed with nodes having a strong attraction towards their preferential zones. The second mobility context corresponds to a more "nomadic one", such as human movements during a social event or in shopping areas. This behavior is modeled with nomadic nodes that are weakly attached to any preferential zone and tend to move quite randomly in the simulation area.

We run each protocol on these two mobility contexts and measure the content delivery delay and the content delivery ratio between different pairs of nodes. In our simulations, the same mobility trace was used to ensure that the different protocols run exactly on the same mobility scenario. In each scenario, contents are sent periodically by providers to the subscriber every 100 seconds. We measure the average delivery delay and average delivery ratio between different pairs of nodes. The final result is averaged over 10 simulation runs. These results show that that in the sedentary mobility context, SIR outperforms the other protocols by significantly decreasing delivery delay and increasing delivery ratio.

It is interesting to see that even in the nomadic context, a-priori less favorable to SIR which leverages on spatio-temporal correlations, SIR still slightly outperforms the other protocols. On the other hand, as intuitively understandable, for the three protocols, the nomadic context contributes to increase routing performances and entails much higher delivery ratio and lower delivery delay than the more sedentary scenario. In the following scenarios, for comparison purpose, we will use the sedentary mobility context only, which conform to real life mobility patterns observed in real traces. Attempts to bring the content-centric paradigm to opportunistic networks include SocialCast [START_REF] Costa | Socially-aware routing for publish-subscribe in delay-tolerant mobile ad hoc networks[END_REF] and TACO-DTN [START_REF] Sollazzo | TACO-DTN: a time-aware contentbased dissemination system for delay tolerant networks[END_REF]. In SocialCast, utility values based on social patterns and mobility are used for message forwarding decision. The evolution of these utility values is predicted with the help of a Kalman filter. TACO-DTN uses temporal information to predict the future contacts between content providers and content users. This prediction is then used to schedule the delivery of messages. By resting on two universal and simple metric values intrinsic to the evolution of every networks (i.e., space with the number of hops and time with the delay), SIR distinguishes from these protocols based on more complex and artificial interaction patterns.

Conclusion

From a formal definition of the notion of shortest dynamic path in dynamic networks and an in-depth analysis of shortest dynamic path properties observed in representative real traces, we have introduced in this paper SIR, a simple and light routing protocol that makes it possible to found and follow efficient routes in dynamic networks. The SIR protocol puts in synergy the Disruption Tolerant Networks and Content-Centric Networks paradigms to found and follow shortest dynamic paths between content providers and content subscribers in Content-Centric Delay Tolerant Networks (CCDTNs). We have shown in this chapter that efficient and high performing routing can emerge from simple individual rules applied by each node during their opportunistic contacts. Simulations, from a parametric mobility model that makes it possible to cover a broad scope of human mobility patterns, show that the proposed protocol, leads to the distributed elaboration of consistently decreasing gradient fields between content subscribers and content providers.

Therefore, routing with SIR simply consists in following the steepest slopes of such fields between content providers and content subscribers. Our simulation results have also shown that SIR performs better than classical information diffusion mechanisms such as Binary Spray and Wait and probabilistic routing. Moreover, SIR increasingly outperforms these protocols when the spatiotemporal correlation between nodes increases. According

Introduction

"Cloud computing" has recently appeared as a buzz word in many medias in which the term refers both to the technology advancement and also to the business model behind. The idea is not new but takes its roots on already developed technologies such as distributed computing, autonomic computing, hardware virtualization and web services.

It's the maturation and convergence of all these technologies that makes cloud computing viable today. By virtualizing the aggregated computing resources in order to offer users on-demand utilities (e.g., computing, storage, software as service) in a pay-as-you-go fashion, much like the power distribution grid system, cloud computing appears as a main actor of information industry today. This can be seen through the explosion of cloud computing services deployed the Internet in recent years.

Besides, with the advances of electronic technologies, mobile wireless devices have gradually become more and more powerful in terms of processing, storage and communication capacity. This potentially leads to the emergence of mobile ad-hoc/opportunistic networks that deliver, without any infrastructure, computing resource complementary to the existing infrastructure-based networks. These "mobile clouds", which leverage on opportunistic contacts between users, can potentially deliver free communication, storage and processing services shared between users according to peer to peer resource sharing policies.

Although the application perspective sounds interesting, the underlying technology challenges are not negligible due to the difficulties raised by dynamic nature of such networks. The first obstacle comes from the mobile nature of such network and raises the question of "how the mobility impacts the distributed processing performances of the mobile clouds?". Indeed, the unstable network topology makes continuous end-to-end communication unguaranteed and hence the service delivery may be disrupted. Indeed, in the context of spontaneous and infrastructureless networks, a kind of disruption/delay tolerant network, nodes must rely on intermittent contacts leading to use the store-carryand-forward communication paradigm for inter-node communication. Therefore, if the role of mobility on communication performances such as end-to-end delay and bandwidth has been already studied [START_REF] Grossglauser | Mobility Increases the Capacity of Ad Hoc Wireless Networks[END_REF], the impact of mobility schemes on the global processing power delivered by a mobile network cloud has not been studied yet.

In this chapter, we address this issue and show that the mobility can enhance significantly the computing capacity of network clouds composed of mobile nodes. Considering a dynamic network as an aggregate distributed computing resource, we use Particle Swarm

State of The Art

Optimization (PSO), an optimization method based on distributed autonomous agents, coupled with the STEPS model introduced in Chapter 2 to assess the impact of node mobility on distributed processing. The questions on service resilience against network churn are also discussed.

The rest of the chapter is structured as follows. First, Section 6.2 discusses the state of the art of mobile cloud computing. In Section 6.3, we study the impact of mobility on the quality of mobile cloud computing services. Section 6.3 studies of the impact of dynamic network structures on mobile cloud computing. In Section 6.5, the question of service resilience is discussed. Finally, Section 6.6 concludes the chapter.

State of The Art

Mobile cloud computing is still a young field and there is still discussion on its definition. In its infancy, mobile cloud computing has been considered as a derived branch of cloud computing with two schools of thought (see [START_REF] Xiaopeng | A Survey of Mobile Cloud Computing[END_REF] for a survey). The first refers to performing computing activities (i.e., data storage and processing) in infrastructured cloud and let mobile devices be simple terminals to access to service. This centralized approach has the advantage that mobile devices don't need to have a powerful computing capacity but the drawback is that users depend strongly on the infrastructure network and on its performances.

The second school of thought defines mobile cloud computing as performing computing activities on mobile platform. Therefore a mobile cloud network is an infrastructureless extension of the traditional infrastructure-based cloud networks. Mobile devices are clients of service but are also part of the cloud, providing hardware and software resources.

The benefit of this distributed approach is the omnipresence and the speed of service accessibility, the support of mobility and locality, the freedom of deployment and use of new services as well as the reduced hardware maintenance costs. Although the approach is promising, its main challenge resides in the network dynamics which poses difficulties in communication and hence service access. In this chapter, we focus on this definition of mobile cloud computing.

To the best of our knowledge, very few contributions have been proposed for mobile cloud computing. Hyrax [57] is a mobile-cloud infrastructure that enables smart-phone applications that are distributed both in terms of data and computation. Hyrax allows applications to conveniently use data and execute computing jobs on smart-phone net-works and heterogeneous networks of phones and servers. Its implementation is based on Hadoop and tested on Android platform. But since Android doesn't support ad-hoc network yet, the phones have to communicate through a WIFI central router.

Satyanarayanan et al. [58] present the cloudlet concept. In this approach a mobile client is seen as a thin client with respect to a service which is customized over a virtual machine in the wireless LAN. Hence the cloudlet is a proxy representation of a real service enhanced for the mobile device. The main motivation is how bandwidth limits and latency over wireless networks impacts on users services.

Impact of Mobility on Mobile Cloud Computing

In this section, we evaluate the impact of mobility on mobile cloud computing. Let us consider that a mobile cloud network created by several human portable devices offers a distributed processing service such as optimizing a function via a Particle Swarm Optimization (PSO) algorithm. According to PSO, each node in the network has a local solution to the optimization problem. Through intermittent contacts, mobile nodes learn others' solution to improve their local optimum and hence accelerate the convergence towards the global optimum. For the sake of simplicity, we make the following assumptions:

1. Each node in the network knows in advance the goal function and its solution.

2. An external system (e.g., WIFI hot-spots) is responsible for results retrieval from mobile nodes.

3. The service is considered delivered when the global optimum reaches a goodness predefined by user.

In practice, the goal function as well as its solution is usually unknown in advance and therefore we have to rely on a diffusion technique to disseminate the information of the goal function into the network. The obtained global optimum and stopping condition in that case will depend on the current solutions found by nodes (e.g., a node stops the computation when its local solution no longer changes for a while). In this theoretical work, we focus only on the impact of mobility on computing delay and therefore the previous assumptions seem reasonable.

Mobility model

In order to reproduce at the simulation level realistic human mobility patterns, we use the STEPS mobility model introduced in Chapter 2. As we have shown in Chapter 2, this flexible parametric model can express a large spectrum of mobility patterns from highly nomadic ones to localized ones. Therefore, STPES makes it possible to evaluate the impact of different mobility contexts on mobile cloud computing. In this evaluation, the network area is modeled as a torus divided in several zones. STEPS implements the notion of preferential attachment usually observed in human mobility in which each node is attached to one or several preferential zones. Inside zones, mobile nodes move according to the Random Waypoint model. The movement of nodes between zones follows a Markov chain of which the transition probability is given by a power law distribution. This distribution is driven by a parameter of the STEPS model which allows the nodes nomadism to be enforced or reduced (i.e., the probability that a mode moving outside his preferential zone has to return to that zone).

Particle Swarm Optimization

The Particle Swarm Optimization (PSO) algorithm [START_REF] Kennedy | Swarm intelligence[END_REF] is an optimization method based on swarm intelligence -a sub-field of artificial intelligence which studies the collective intelligent behavior emerging from the interactions between individuals of a swarm of autonomous agents. Swarm intelligence considers intelligence as the combination of the knowledge acquired by individuals through experiences in the past and the knowledge acquired from the others through social interactions. In PSO algorithm, a set of candidate solutions called particles move around in the search space according to a simple mathematical formula that involves the particle's position and velocity. Each particle's movement is influenced by its local best known position and also by the global best known position found by other particles. The swarm is expected to move collectively towards the optimal solution. Moreover, this method is able to solve a multimodal optimization problem.

In its simplest form, let x i be the multidimensional vector of the particle i position, the position of the particle is updated according to the formula

x i (t + 1) = x i (t) + v i (t) (6.1)
where x i (t) is the position of particle i at time t. The velocity of the particle is updated according to the formula

v i (t) = v i (t -1) + φ 1 [ p i -x i (t -1)] + φ 2 [ p g -x i (t -1)] (6.2)
where φ 1 , φ 2 are uniform random variables taking values in [0, 1]. These variables represent the relativity between the effect of individual experience and of social influence.

p l denotes the best known position of particle i ("l" for local).

p g denotes the best known position of i's neighbors ("g" for global)

This formula entails wider and wider oscillations of particles in the search space. One solution to this issue is based on velocity damping, that is, if v id > V max then v id = V max else if v id < -V max then v id = -V max where v id is the dimension d of v i . In consequence, the particles move only in a restricted search space.

In PSO, agents can be connected each other according to a great number of neighborhood topologies. Figure 6.1 illustrates the most used schemes. Each neighborhood topology, traditionally considered as static conversely to our analysis, results in different behaviors and performances for the PSO algorithm.

In this work, since nodes move, the neighborhood topology is no longer static but dynamic. Indeed, when the mobility degree is low, links between nodes are stable and the network is nearly static. On the contrary, when the mobility is high, links change rapidly over time and so does the neighborhood topology. Therefore the goal of this study is to evaluate the effect of mobility on the convergence delay of the algorithm.

Simulation Results & Discussion

We implemented the mobility model and the PSO algorithm on MATLAB. α of STEPS model. We vary α between 0 and 8 to obtain a large spectrum of mobility patterns. When α = 0 nodes are highly nomadic, moving from a zone to one another in a random manner that makes the network highly dynamic. On the contrary, when α = 8, nodes are highly localized (i.e., sedentary) and therefore there are less information exchange between distant zones.

The PSO algorithm is implemented in every mobile nodes so that each node contains 1 particle. The position of particle is randomly initialized, taking values in range [-x max , x max ]. Particle's position is updated at each contact with another node according to the formula 6.2.

As goal function, we used the Sphere function from the De-Jong test suite [START_REF] De | Analysis of the behavior of a class of genetic adaptive systems[END_REF]. This suite consists of goal functions with different difficulties to measure the performances of optimizers. The Sphere function is the first and easiest function of the suite. It is symmetric, unimodal and is often used to measure the general efficiency of optimizers.

The sphere function is defined as

f ( x) = D i=1 x i 2
where D is the number of components of x. The Sphere function has a global optimum f ( x) = 0 at x = (0, 0, 0, . . . , 0).

We used root-mean-square error to measure the goodness of the solution. The algorithm stops when the error is smaller than a predefined threshold. The simulation settings are summarized in Table 6.1 Figure 6.2 shows the optimization convergence delay according to nodes' locality degree. These results are averaged over 10 simulation runs. On the figure, we can see that the more mobile nodes are, the smaller convergence delay is. This result shows that nodes mobility can increase dramatically the processing capacity of mobile cloud networks. In this section, we evaluate the processing capacity of mobile cloud computing under various dynamic network structures. With the same approach as introduced in Section 6.3, we measure the convergence delay of a PSO algorithm implemented on a mobile cloud network and show that this delay can be significantly minimized if the network has a dynamic small-world structure.

The small-world phenomenon introduced by Watts and Strogatz [START_REF] Watts | Collective dynamics of small-world networks[END_REF] refers to static graphs with high clustering coefficient and low shortest path length. Through a process which consist in rewiring randomly edges of a graph, by varying the rewiring ratio, the authors showed that for an interval a rewiring ration the resulting static graph, exhibits a small world structure which cumulate short path observed in random graphs with high clustering coefficient intrinsic to regular lattices. In Chapter 3, we have shown that this 6.4. Impact of Network Structure on Mobile Cloud Computing small world behavior can be observed in dynamic graphs too. We have shown that in a dynamic networks, the analog of the rewiring process in static graph is done by varying the ratio and intensity of nomadic nodes. Moreover, we have shown that the STEPS model is capable of exhibiting this small-world phenomenon in dynamic networks.

Indeed, starting from the same network configuration as in Section 6.3, we divide mobile nodes in 2 categories. The first consists in highly localized nodes which stay almost all their time in their preferential zones. The second category consists in highly nomadic modes which move constantly from zone to zone. At the beginning of simulation, the nodes are distributed over the network area so that nodes in different preferential zones cannot communicate each other (Figure 6.3 shows the node spatial distribution). We vary the fraction of mobile node p m from 0 to 1. When p m equals to 0, the network consists in disconnected islands with only intra-zone communications that entails a regular structure similar to the one in static graphs. On the contrary, when p m equals to 1, the inter-zones movement of highly mobile nodes makes that the network topology changes constantly which entails a random network structure. We processed the PSO algorithm over all these network structures and then measured the resulting convergence delay. Figure 6.4 shows the results averaged over 10 simulations.

These simulation results show that the convergence delay of PSO decreases rapidly down to an asymptotic part started when the network exhibits a small world structure. This original result is significant because the small-world structure, which as shown in this chapter improves distributed processing, was shown to emerge naturally in the great majority real dynamic networks, as underlined in Chapter 3. for instance DDOS, which can potentialy make unavailable parts of the network. In this section, we evaluate, under various mobility contexts, the resilience of distributed services deployed on such networks.

First, we assume that the evolution of number of inactive nodes (i.e., attacked or out of battery) follows a Poisson process. Therefore, the number of inactive nodes during a time interval τ is distributed according to a Poisson distribution

P [(N (t + τ ) -N (t)) = k] = exp -λτ (λτ ) k k!
where k = 0, 1, 2, . . . and λ is the arrival rate of inactive nodes.

Resilience of Mobile Cloud Computing Service

With the same simulation settings as introduced in Section 6.4, we perform simulations with various values of λ (1/15, 1/12.5, 1/10, 1/5) and under various mobility contexts (i.e., by varying the fraction of mobile nodes). In these simulations, we stop the PSO algorithm when 95 % nodes reach the optimum. If this threshold is not reached before all the nodes become inactive, as there is no recovery possible in this case, the service will never be delivered and hence we assign the simulation duration time to the convergence delay. . These results suggest that a small-world structure not only contribute to enhancing distributed performances but also offers good resilience properties.

Conclusion

In this chapter we not only showed that nodes' mobility enhance the processing capacity of opportunistic network cloud computing but we also show how mobility impacts the performance and the resilience of these mobile clouds. In particular, we have shown that significant performance improvement can be obtained when opportunistic networks exhibit a small-world structure and moreover, this particular structure can improve the resilience of the network against inactive nodes. This means that by introducing even a small percentage of highly mobile (about 10%) nodes in a high localized network, we can improve significantly the processing capacity and resilience of mobile cloud computing.

These results open the way to adaptive strategies that would aim to adapt dynamic network topology and behavior according to their processing load and constraints. Moreover these strategies have to consider also storage and energy consumption which are critical in the context of handheld systems.

Chapter 7

General Conclusion & Perspectives

Throughout this thesis, we have presented an in-depth analysis of the nature of dynamic networks through the modeling, structural analysis and routing performances analysis of such networks. We have first proposed STEPS -a novel human mobility model for dynamic networks. In this model, two intrinsic properties of human mobility are implemented: preferential attachment, i.e., people have very high probability to visit few specific locations and attraction, i.e., they have high probability to return to these locations when moving outside. We define the network are as a torus divided in square zones.

Inside each zone, nodes move according to a random mobility model. The movement between zones is ruled by a power law such that the probability for a node to select a new zone is inversely proportional to the distance between that zone and the preferential zone of the node. By tuning the power law exponent, we vary the nomadic degree of nodes.

We show that this simple parametric model can capture characteristics of human mobility usually observed in real traces. For instance, the contact/inter-contact time distribution follows a power law.

Based on this model, we then study the structure of dynamic networks. We show that dynamic networks exhibit a small-world structure in which nodes are highly clustered while the network diameter is very short. We extend the notion of clustering coefficient and shortest path length in static networks to dynamic networks and use these metrics to investigate real traces. The results show that human contact networks exhibit a high dynamic clustering coefficient and low shortest dynamic path length during day phases, while behaving in the opposite manner in night phases, suggesting the small-world phenomenon in dynamic phases. We demonstrated that highly dynamic nodes are responsible for this phenomenon. Indeed, these nodes play the role of bridges between disconnected components of dynamic networks, hence contributing to reduce significantly the diameter of the network. We model this behavior with STEPS. Starting from a highly localized networks where nodes tend to stay in their preferential locations, we tuned the ratio of nomadic nodes and measured the two metrics. As soon as we have at least 10% of such nodes, the shortest dynamic path length drops as low as in a random network, while the dynamic clustering coefficient still remains as high as in a fully localized network. We then showed that this structure allows information to spread as fast as in a fully dynamic network. These results mean that, to boost up information dissemination speed in a dynamic network, it is enough to inject only 10% dynamic nodes into the network.

The third contribution of this thesis focused on the study of the regularity and periodicity of contacts patterns in dynamic networks and its impacts on routing performances in such networks. Specifically, we showed that the disorder degree, i.e., the randomness in contact patterns, can help to decrease significantly the delivery delay while increasing the delivery ratio of routing algorithms. We proposed a model to capture the disorder degree of dynamic networks. Starting from a regular contact pattern, we rewired links with a probability p which represents the disorder degree. By tuning this parameter, we vary the disorder degree of the network. The analysis of real traces according to this model showed that real human contact networks exhibit a disorder degree that ranges from medium to quite high (the estimated value of p range from 50 to 70%). We then introduced a routing algorithm class for dynamic networks that uses only one copy per message. We proposed two greedy routing algorithms that exploit the natural gradient field formed by the spatiotemporal structure in dynamic networks. We evaluated the algorithms with other classical algorithms under the network model and showed that when we increase the disorder degree of the network up to certain value, the routing performances increases significantly.

Intuitively, the disorder introduces shortcuts into the network which allow nodes to have some "cues" to find destination. But too much disorder seems to suppress these "cues".

Moreover, we showed that our routing algorithms outperforms other approaches in all network contexts.

Leveraging on the previous studies, our fourth contribution consists of a routing protocol that performs efficiently in both address-centric and content-centric networks. From the definition of shortest dynamic path previously introduced, we studied the properties of such paths in real traces and found that the length of the shortest dynamic path is symmetric, which means that the shortest path length from node i to node j is approximately equal to the shortest path length from j to i. Although it is not possible for a node to know in advance the path to the destination, however, the node can have information on the reverse shortest path from the destination and hence deduce the shortest path length to the destination. In our protocol, nodes keep track of two basic metrics of dynamic path to each destination: delay and hops. At each opportunistic contacts, nodes exchange and update vectors containing metric values. The message forwarding decision consists in giving the message to relay nodes with smaller metric values. The message then flows along the steepest slope of the gradient field to reach the destination. In the context of content-centric networks, we extend this protocol by integrating publish/subscribe content dissemination model. The metric values are now considered with respect to the content providers or caches. We also adapted the Spray-and-Wait algorithm to control the number of content copies. Via simulations, we showed that our protocol outperforms classical routing protocols for DTNs and has a good scalability.

In this thesis, we also studied the impact of the mobility on mobile cloud computing processing capacity. By using swarm particle optimization techniques, we use mobile nodes to solve optimization problems. We showed that the mobility can increase dramatically the processing capacity of mobile cloud computing. In particularly, if the network has a dynamic small-world structure, i.e., with around 10% highly mobile nodes, then the processing capacity is as high as random network.

We are convinced that there is still room to improve these researches. We list here some issues that we consider for future work.

-In Chapter 2, we focused only on human mobility, but one can extend this research to study human behavior in social networks by considering a zone as an interest topic. We also showed that the STEPS model than reflect with high accuracy at simulation level routing performances as compared to the ones obtained on real traces. This result can be refined by evaluating different aspects of routing, for instance, delivery ratio, overhead. Finally, a full formal analysis of STEPS can also be derived from our results.

-In Chapter 3, we pointed out that highly mobile nodes are at the origin of the emergence of the small-world phenomenon. Therefore we found a sufficient condition for the emergence of a dynamic small world stucture but research in this direction must be pursued to identify other potential necessary and sufficient conditions.

To highlight this phenomenon in real datasets, we dispose only of small traces.

Therefore, it would be interesting to investigate larger scale traces (i.e., at the scale of a country or the world).

-In Chapter 4, the network model starts from a plain network in which node degrees are uniformly distributed, one can obtain a more realistic model by considering different frequencies of contact for different nodes. One other possible direction is to combine the two presented routing algorithms to have an adaptive algorithm that performs best in all contexts.

From a social network and societal point of view this contribution raises the following question: are social structures implicitly self-adapting their degree of disorder in order to optimize their communication capacity? Indeed, our traces analysis on real dynamic networks would seem to show that the more real dynamic networks are structured around a social activity the more their disorder degree converges towards the point where they reach their intrinsic optimal communication performances. The critical temporal and spatial scale where this property emerges is still one of our ongoing research issues.

-In Chapter 5, the proposed routing scheme can be extended by introducing, for instance, inter-contact and intra-contact delays experienced by each node for the processing and actualization of the utility metric, and by studying the scalability and resource use in response to very large nodes and content spaces. In the contentcentric network context, the routing mechanism for multiple receivers should be understood, e.g., how many content copies are necessary for a number of content users. In this research, to focus on the network layer, some assumptions are made while evaluating the protocol, e.g., assumptions on buffer size and bandwidth. One can remove these hypothesis to evaluate the routing protocol in more realistic network conditions. The bootstrap time of the routing algorithm and its impacts on routing performances should also be studied deeper.

-In Chapter 6, it would be interesting to study adaptive strategies that adapt dynamic network topology and behavior according to their processing load and constraints, network storage and energy consumption.

-Although the analytical and simulation results show good performances, we would like to push forward experimental research by implementing a testbed to test the routing protocol and verify some hypothesis. We redefine in the context of dynamic networks the concept of small world structure and show how such a structure can emerge. In particular, we show that highly dynamic nodes can play the role of bridges between disconnected components, helping to significantly reduce the length of network path and contribute to the emergence of small-world phenomenon in dynamic networks. We propose a way to model this phenomenon in STEPS. From a regular dynamic network in which nodes limit their mobility to their respective preferential areas. We rewire this network by gradually injecting highly nomadic nodes moving between different areas. We show that when the ratio of such nomadic nodes is around 10%, the network has small world structure with a high degree of clustering and a low characteristic path length.

The third contribution of this thesis is the study of the impact of disorder and contact irregularity on the communication capacity of a dynamic network. We analyze the degree of disorder of real opportunistic networks and show that if used correctly, it can significantly improve routing performances. We then introduce a model to capture the degree of disorder in a dynamic network. We propose two simple and efficient algorithms that exploit the temporal structure of a dynamic network to deliver messages with a good tradeoff between resource usage and performance. The simulation and analytical results

show that this type of algorithm is more efficient than conventional approaches. We also highlight also the network structure for which this type of algorithm achieves its optimum performance. Based on this theoretical result, we propose a new efficient routing protocol for content centric opportunistic networks. In this protocol, nodes maintain, through their opportunistic contacts, an utility function that summarizes their spatio-temporal proximity to other nodes. As a result, routing in this context consists in following the steepest slopes of the gradient field leading to the destination node. This property leads to a simple and effective algorithm routing that can be used both in the context of IP networks and content centric networks. The simulation results show that this protocol outperforms traditional routing protocols already defined for opportunistic networks. The last contribution of this thesis is to highlight the potential application of dynamic networks in the context of "mobile cloud computing." Using the particle optimization techniques, we show that mobility can significantly increase the processing capacity of dynamic networks. In addition, we show that the dynamic structure of the network has a strong impact on its processing capacity.

Keywords: opportunistic networks, content-centric networks, mobility model, network structure, small-world, disorder, contact pattern, routing algorithm, gradient field, mobile cloud computing

i" 1 . 1 1 1. 2 2 1. 3 3 1. 4 4 1. 5

 1112233445 I don't know what I may seem to the world, but as to myself, I seem to have been only like a boy playing on the sea-shore and diverting myself in now and then finding a smoother pebble or a prettier shell than ordinary, whilst the great ocean of truth lay all undiscovered before me." Dynamic networks . . . . . . . . . . . . . . . . . . . . . . . . . . Modeling Dynamic Networks . . . . . . . . . . . . . . . . . . . Behavioral and Structural Properties of Dynamic Networks . Routing in Dynamic Networks . . . . . . . . . . . . . . . . . . Organization of this thesis . . . . . . . . . . . . . . . . . . . . . 6

  performance mobile networks. The great majority of mobile network services are actually operated in infrastructure mode provided by Internet Service Providers. Specifically, users can access to services either through Wi-Fi hotspots or cellular network. This poses the problem of disconnection in zones where there is no such infrastructure-based networks. One way to solve this problem is using ad-hoc communication. Mobile Ad-hoc and Delay/Disruption Tolerant Networks fall in this type of network and are still the focus of research and experiments. In these networks, dynamic nodes no longer rely on the infrastructure to communicate but use the store-move-and-forward communication paradigm to deliver information, usually via opportunistic contacts. By freeing user from the infrastructure dependence, these dynamic networks offers potentially free pervasive services which complement the existing infrastructure-based network services. Research envisions the use of spontaneous networks in workspaces, entertainment center, battle field communication, disaster recovery networks, deep space communication among planets, vehicular ad-hoc communication, etc.

Figure 2 .

 2 1(a) illustrates a Markov chain with 4 states which correspond to 4 locations of interest.

Figure 2 . 1 :

 21 Figure 2.1: (a) Human mobility modeling under a markovian view: States represent different localities, e.g., House, Office, Shop and Other places, and transitions represent the mobility pattern. (b) 5 × 5 torus representing the distances from location A to the other locations.

2. 4 .Figure 2 . 2 :

 422 Figure 2.2: Theoretical inter-contact time distribution of STEPS

Figure 2 .

 2 Figure 2.3(a) shows the aggregate CCDF of the inter-contact time 3 for different traces.

Figure 2 . 3 :

 23 Figure 2.3: CCDF of Inter-Contact Time

Figure 2 .

 2 3(b) shows the CCDF of the resulting inter-contact time in

Figure

  Figure 2.4(a). According to this classification, it appears that the more (resp. less) popu-

  trace where a large percentage of nodes have short contacts and a few nodes have long to very long contacts. The CCDFs of contact time of STEPS and Infocom06 trace as shown in Figure 2.4(b) show that STEPS can also capture with a good accuracy this mobility behavior.(a) Social characteristic observed in Infocom06 trace (b) CCDF of contact time of STEPS vs Infocom06 trace

Figure 2 . 4 :

 24 Figure 2.4: Contact time behavior of STEPS vs real trace

Figure 2 . 5 :

 25 Figure 2.5: (a) Epidemic routing delay of STEPS vs Infocom06 trace. (b) Small-world structure in STEPS

Figure 2 .

 2 5(a) shows that STEPS is able to reflect at the simulation level the performance of Epidemic routing when applied on real traces.

,

  Tang et al. first introduced a generalization of Watts and Strogatz's definition for temporal graph. The temporal clustering coefficient of a node during a time interval t is the fraction of existing opportunistic contacts (multiple contacts count once) between the neighbors of the node over the number of possible contacts between them during t.The clustering coefficient of the network is the average of the clustering coefficients of all the nodes. This is simply the application of Watts and Strogatz's definition on a time snapshot of the network. While this definition was shown to better capture temporal characteristics of time varying graph, it depends strongly on the length of the chosen time interval. If this interval tends to infinity, the temporal clustering coefficient tends to 1 as all the nodes meet each other with a high probability. On the other hand, if the interval tends to 0, then conversely the temporal clustering coefficient tends to 0.

Figure 3 .

 3 Figure 3.1 illustrates the influence of the time window size on measures of the clustering coefficient on a real mobility trace.

Figure 3 . 1 :

 31 Figure 3.1: Time window size effect on measure of temporal clustering coefficient (as defined in [11])

Figure 3 . 2 :

 32 Figure 3.2: Small world phenomenon observed in real mobility traces

Figure 3 .Figure 3 . 3 :

 333 Figure 3.3 shows the temporal evolution of the dynamic betweeness for the Infocom05 trace. On the figure, the different areas represent the measured metric (in %) of different nodes. We can observe that the dynamic betweeness of a nodes changes over time and that there are some nodes with very high influence whose removal would dramatically increase the dynamic characteristic path length of the network. Indeed, at the time of the highest pick, redrawing the most influential node would result in an 70% increase of the average shortest dynamic path length of the network. We can also see the abrupt decrease of the average shortest dynamic path length at time 24 hours on Figure3.2(a).The time average of the dynamic betweeness centrality of each network node allows one to rank the influence of each node during a time window. For instance in Figure3.3 the highest value for the daytime period corresponds to node with ID 34.

Figure 3 .

 3 Figure 3.4 shows that node 34 has very high influence on node 31. We then apply our all-

Figure 3 . 4 :Figure 3 . 5 :

 3435 Figure 3.4: Impact of node 34 on the shortest dynamic paths from and to the other nodes at t = 22h (Infocom05 trace)

  simulate in MATLAB an opportunistic network of 1000 nodes. The simulated network area of size 200 × 200 m 2 divided into 20 × 20 zones as shown in Figure 3.6 gives a density of 25000 nodes/km 2 which corresponds to the population density of a large city like Paris. We distribute uniformly nodes over zones and set the radio range to 10 m which corresponds to bluetooth technology. We set a very high value of the power law exponent for sedentary nodes and 0 for nomadic nodes. While varying the fraction of nomadic nodes from 0 to 1, we measure the dynamic clustering coefficient and shortest dynamic path length of resulting networks.

Figure 3 .

 3 Figure 3.7 plots the resulting average over 10 simulations with the corresponding 95%

Figure 3 . 6 :Figure 3 Figure 3

 3633 Figure 3.6: Small-world network configuration

3. 5 .Figure 3

 53 Figure 3.9: Evolution of fraction of infected nodes over time with the complete version of the model (simulation result)

Figure 3 .

 3 8(a) shows the fraction of infected nodes as a function of time for a 10000-nodes network. The 4 curves correspond to 4 values of p m , which are respectively 0.1%, 1%, 10% and 100%. The STEPS parameter α for mobile nodes is set to 0 and the transmission rate β is set to 1. The results show that, for a low fraction of mobile nodes, epidemic spreads very slowly. As soon as the small-world structure emerges, i.e., with 10% of mobile nodes, the epidemic breaks out rapidly.

  Figure 3.8(b) shows the strong accuracy and compliance of our analytical model with the simulation results.

  [START_REF] Clauset | Persistence and periodicity in a dynamic proximity network[END_REF], Clauset et al. investigate real dynamic network traces divided in time snapshots to demonstrate that dynamic networks have a high persistence and periodicity in time. They show that the daily and weekly rhythms of human social behaviors make periodic contacts patterns in the network. Motifs is another aspect of dynamic network which has drawn attention of researchers. In[START_REF] Kovanen | Temporal motifs in time-dependent networks[END_REF], Kovanen et al. formalize the notion of temporal motif as isomorphic connected subgraphs and propose an algorithm to find such motifs in a temporal graph. They apply this algorithm on mobile phone traces to study the behavior of mobile users.

Figure 4 . 1 :

 41 Figure 4.1: Time structure of a DTN

Figure 4 . 2 :

 42 Figure 4.2: Network model

  ,4.3(b) and 4.3(c) depict the resulting three performance measures for all algorithms

Figure 4 . 3 :

 43 Figure 4.3: Performance comparison of all algorithms

Figure 4 . 4 :

 44 Figure 4.4: Delivery delay of GRAD-DOWN with a network of 20, 50 or 100 nodes

Figure 4 . 5 :Figure 4 . 6 :

 4546 Figure 4.5: Contacts map (from the top, p = 0, 0.1, 0.2, 0.5, 1 respectively)

Figure 4 . 7 :

 47 Figure 4.7: Message passing chains (from the top, p = 0, 0.1, 0.2, 0.5, 1 respectively)

Figure 4 .

 4 Figure 4.8: Average message passing chain length

Figure 4 .

 4 Figure 4.9: Building block of the Markov chain modeling the message passing process

Figure 4 . 10 :.

 410 Figure 4.10: Average delivery delay of FIRST-CONTACT in function of rewiring rate for 100-nodes networks (theoretical result)

Figure 4 . 11 :

 411 Figure 4.11: Average delivery delay of GRAD-DOWN algorithm in function of rewiring rate for 100-nodes networks (theoretical result)

Figure 4 .

 4 Figure 4.11 shows the average curve over 100 traces, each lasts 10000 seconds. The curve confirms the simulation result with the same form and the optimum at p = 0.2.

5 . 5

 55 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 5.2 Properties of Shortest Dynamic Paths in Opportunistic Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 5.2.1 Periodic Pattern . . . . . . . . . . . . . . . . . . . . . . . . . . 69 5.2.2 Symmetry . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70 5.2.3 Pairwise Inter-contact Time vs the Shortest Dynamic Path . . 71 5.3 SIR protocol . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 5.3.1 Interest Dissemination Phase . . . . . . . . . . . . . . . . . . . 73 5.3.2 Content Dissemination Phase . . . . . . . . . . . . . . . . . . . 73 5.4 Simulation Results & Discussion . . . . . . . . . . . . . . . . . 75 5.4.1 Consistency and Efficiency Issues . . . . . . . . . . . . . . . . . 75 5.4.2 Performance Issues . . . . . . . . . . . . . . . . . . . . . . . . . 77 Related works . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82 5.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83

Figure 5 .

 5 Figure 5.1 shows the temporal evolution of the average shortest dynamic path length of four different real opportunistic networks. Despite the diversity in term of number of nodes, duration and scale of the traces, the curves show a typical approximately 24-hours period with two opposite phases, each phase lasts approximately 12 hours. Intuitively, this behavior can be explained by the night/day variation in human activities. Indeed, during the day, people's alternate movements and contacts leading to short dynamic paths. On the contrary, during night periods, they are more static and have less chance to meet each other, leading to longer dynamic path

Figure 5 . 1 :

 51 Figure 5.1: Evolution over time of the average shortest path length of real DTNs

  Figure 5.2(a) shows a typical evolution over time of these two measures and Figure 5.2(b) shows the correlation between

  from A to B (s) Shortest dynamic path from B to A (s) y = 1*x -7e+02 (b) Delay correlation

Figure 5 . 2 :

 52 Figure 5.2: Symmetry of the shortest paths in Infocom05 trace

Figure 5 .

 5 Figure 5.4 illustrates graphically this mechanism. On this figure, t and h are respectively the delay and the number of hops. We summarize the detail of the interest dissemination phase in Algorithm 5.

/ 5 :Figure 5 . 4 :

 554 Figure 5.4: Example of the interest dissemination phase

1 :

 1 Vector of correlation coefficients for all nodes (Infocom05 dataset)

Figure 5 .

 5 [START_REF] Nguyen | Swarm-based Intelligent Routing (SIR) -a New Approach for Efficient Routing in Content Centric Delay Tolerant Networks[END_REF] shows the average result over 10 pairs of nodes. These results show that SIR finds paths with delivery delays very close to the optimal paths.

Figure 5 . 5 :

 55 Figure 5.5: Correlation between the utility values of a node and the shortest dynamic path length from that node to the content subscriber

Figure 5 . 6 :

 56 Figure 5.6: Delivery delay of SIR vs optimal solution

Figure 5

 5 Figure 5.7: Initial spatial distribution of nodes in STEPS simulations

Figure 5 .

 5 Figure 5.8 shows the bar plot of these measures. The segment on top of each bar represents the 95% confidence interval of the estimated mean value.

  Impact of mobility on content delivery ratio

Figure 5 .

 5 Figure 5.8: Scenario A -Routing performances of the three routing protocols under different mobility contexts

Figure 6 . 1 :

 61 Figure 6.1: Typical static neighborhood topologies vs dynamic neighborhood topology generated by the mobility model

Figure 6 . 2 :

 62 Figure 6.2: Impact of mobility on the convergence delay of PSO algorithm

Figure 6 . 3 :

 63 Figure 6.3: Node spatial distribution

Figure 6 . 4 :

 64 Figure 6.4: Mobile cloud computing in small-world networks

Figure 6 . 5 :Figure 6 . 5

 6565 Figure 6.5: Resilience of mobile cloud network distributed services under various mobility contexts

Anh-Dung Nguyen ,Argentina 12 .

 Nguyen12 Patrick Sénac, Michel Diaz ACM MSWIM 2012, Paphos, Cyprus 7. How Mobility Increases Mobile Cloud Computing Processing Capacity Anh-Dung Nguyen, Patrick Sénac, Victor Ramiro, Michel Diaz IEEE NCCA 2011, Toulouse, France 8. Pervasive Intelligent Routing in Content Centric Delay Tolerant Networks Anh-Dung Nguyen, Patrick Sénac, Victor Ramiro, Michel Diaz IEEE PICOM 2011, Sydney, Australia 9. Swarm-based Intelligent Routing (SIR) -a New Approach for Efficient Routing in Content Centric Delay Tolerant Networks Anh-Dung Nguyen, Patrick Sénac, Victor Ramiro, Michel Diaz ACM MSWIM MOBIWAC 2011, Miami, USA 10. STEPS -an Approach for Human Mobility Modeling Anh-Dung Nguyen, Patrick Sénac, Victor Ramiro, Michel Diaz IFIP NETWORKING 2011, Valencia, Spain 11. STIgmergy Routing (STIR) for Content-Centric Delay-Tolerant Networks Anh-Dung Nguyen, Patrick Sénac and Michel Diaz Latin-American Workshop on Dynamic Networks (LAWDN) 2010, Buenos Aires, Stigmergy Routing Protocol for Content-Centric Delay-Tolerant Networks (STIR) Anh-Dung Nguyen, Patrick Sénac, Michel Diaz RESCOM 2010, Giens, FranceContributions to Modeling, Structural Analysis, and RoutingPerformance in Dynamic NetworksAbstract: This thesis contributes to the modeling, understanding and efficient communication in dynamic networks populating the periphery of the Internet. By dynamic networks, we refer to networks that can be modeled by dynamic graphs in which nodes and links change temporally. In the first part of the thesis, we propose a new mobility model -STEPS -which captures a wide spectrum of human mobility behavior. STEPS implements two fundamental principles of human mobility: preferential attachment and attractor. We show that this simple parametric model is able to capture the salient statistical properties of human mobility such as the distribution of inter-contact/contact time. In the second part, using STEPS, we analyze the fundamental behavioral and structural properties of opportunistic networks.

  Go linearly to this point with a speed chosen uniformly at random from[v min , v max ] , 0 < v min ≤ v max < +∞;

	zone at a given time is
	6	Choose uniformly at random a staying time t from
		[t min , t max ] , 0 ≤ t min ≤ t max < +∞;
	7	while t has not elapsed do
	8	Perform Random Waypoint movement in z i ;
	9	end
	10 until End of simulation;
		Algorithm 1: STEPS algorithm for a node
	to select z i . If we define the transition probabilities of the Markov chain as a stochas-
	tic matrix, this one will have identical rows. The matrix is then idempotent, i.e., the
	multiplication by itself gives the same matrix. This matrix is given by
				
		  	P (z 0 ) P (z 1 ) . . . P (z N -1 ) . . . . . . . . . . . .	   .	(2.3)
			P (z 0 ) P (z 1 ) . . . P (z N -1 )
		It is straightforward to deduce the stationary state of the Markov chain which is
		Π = P (z 0 ) P (z 1 ) . . . P (z N -1 ) .	(2.4)
		From this result, it is interesting to characterize the inter-contact time 2 of STEPS
	because this network property was shown to have important impacts on forwarding al-
	gorithm in opportunistic networks. To simplify the problem, let assume that a contact
	occurs if and only if two nodes are in the same zone and node's movement is limited to
	jumping between zones. Let two nodes A and B move according to the STEPS model,
	starting initially from the same zone. The probability that the two nodes are in the same

3

Select uniformly at random a zone z i among all zones that are d distance units away from z pref ;

4 Choose uniformly at random a point in z i ; 5

Table 3 .

 3 1: Dataset of real opportunistic network traces pattern of both metrics with a typical period of 24 hours and a phase change every 12

	Trace	Intel	Cambridge Infocom05 Infocom06
	Number of nodes	9	12	41	98
	Duration (days)	6	6	4	4
	Granularity (seconds) 120	120	120	120
	Connectivity	Bluetooth Bluetooth	Bluetooth	Bluetooth
	Environment	Office	Office	Conference Conference

  .2 summarizes the main simulation parameters.

	Characteristic	Value
	Number of nodes	100
	Number of content subscriber 1
	Number of content provider	1
	Network size	300 × 300 m 2
	Number of zones	10 × 10
	Duration	10000 s
	Warm up	2000 s
	Radio range	10 m
	Node speed	[3, 5] km/h
	Content release frequency	100 s
	Number of content copies	10
	(for SIR and BSW)
	Table 5.2: Simulation Configurations

Table 6 .

 6 1: Simulation settings model. The movement of node between zones is driven by the locality degree parameter

The choice of a torus allows to have a homogeneous area.

The time interval between two consecutive contacts of the same node pair.

Acknowledgments

SIR protocol

In Chapter 4, we have demonstrated the performances of a class of greedy algorithms that exploit the temporal structure of dynamic networks to find short dynamic paths with a good resource/performance tradeoff. Leveraging on these findings and the properties of the shortest dynamic path studied in the previous section, we propose Swarm Intelligent based Routing (SIR) -a novel routing protocol inspired by the collective swarm intelligence that can emerge from basic individual behaviors applied by each element of a swarm of autonomous agents. In SIR, via opportunistic contacts, mobile nodes maintain for each content subscription they have heard of an utility function which sums up the proximity of this node to a content subscriber. We will show that the distributed set of scalars associated to a given subscription forms across the network a gradient field in which the maximum values are carried by content providers and the minimum values by content users. Consequently, content routing with SIR simply consists in following the steepest slope towards the minima of the gradient field where content users are located. Such algorithm works in a complete distributed way, so that nodes do not need to maintain any knowledge about the global topology of the network.

Scenario B -Impact of Connectivity

In this scenario, we perform the same experiment as described above but instead of varying the mobility pattern, we vary the connectivity between nodes by increasing their radio range from 10 m to 30 m. Again, the average delivery delay and average delivery ratio are measured for each scenario and for each protocol. Figure 5.9 gives the results obtained from these measures and show that SIR still outperforms the other protocols in all scenarios. Moreover, in the scenario with long range connectivity, which reduces significantly path lengths for all the protocols, SIR delivers still better performances both in term of delay and delivery ratio.

Scenario C -Scalability

Scalability is a very important feature specially for routing protocols that target potentially vast community of mobile users. In this scenario, we aim to test the capacity of SIR to route content efficiently in large-scale networks. For this, we increase the number of nodes in the network while keeping node density constant. The configurations for these scenarios are summarized in Table 5.

Related works

Basically, routing protocols for DTNs can be divided in two categories : non-context and context-based (see [33] for a survey). The first category consists in protocols in which nodes make forwarding decision while ignoring the network context (i.e. mobility or social structure). Protocols falling into this category belong to flooding and constrainedflooding families such as Epidemic Routing [START_REF] Vahdat | Epidemic routing for partially connected ad hoc networks[END_REF] or Spray-And-Wait [START_REF] Spyropoulos | Spray and wait: an efficient routing scheme for intermittently connected mobile networks[END_REF]. In the second category, nodes exploit the context information (e.g. frequency of contact) from their local interactions to find the good candidate to forward the message. PROPHET [44], Bubble Rap [START_REF] Hui | Bubble rap: social-based forwarding in delay tolerant networks[END_REF], HiBOp [START_REF] Boldrini | Hibop: a history based routing protocol for opportunistic networks[END_REF] and Propicman [START_REF] Nguyen | Probabilistic routing protocol for intermittently connected mobile ad hoc network (propicman)[END_REF] fall into this category of routing protocols. In PROPHET, an utility value based on the contact frequency history is used to predict the probability of contact with the destination node. Bubble Rap makes the assumption of a community structure between nodes; messages are first pushed up to the most popular to the strong spatio-temporal correlation frequently observed in real mobility traces, SIR is a promising routing protocol for content centric opportunistic networks. However, we are convinced that there is still a margin of progress for SIR, specially by introducing, for example, inter-contact and intra-contact delays experienced by each node for the processing and actualization of the utility metric, and by studying the scalability and resource use in response to very large nodes and content spaces. In this chapter, we address an important and still unanswered question in mobile cloud computing "how mobility impacts the distributed processing power of network and computing clouds formed from mobile opportunistic networks ?". Indeed, mobile opportunistic networks potentially offer an aggregate cloud of resources delivering collectively processing, storage and networking resources. We demonstrate that the mobility can increase significantly the performances of distributed computation in such networks. In particular, we show that this improvement can be achieved more efficiently with mobility patterns that entail a dynamic small-world network structure on mobile clouds. Moreover, we show that the dynamic small-world structure can improve significantly the resilience of mobile cloud computing services.

List of publications

The results we obtained in this thesis were also presented in the following publications (in reverse chronological order):