Supervision : Serge FDIDA

Co-supervision : DIOT Christophe

Social Forwarding In Opportunistic Ad-hoc Networks

In opportunistic ad hoc networks, multi-hop data transfer over contemporaneous paths is unlikely since the devices are often disconnected from each other. However, data can still be stored and forwarded over time in an opportunistic hop-by-hop manner. In such opportunistic networks a device has to decide whether or not to forward data to an intermediate node that it encounters. Such forwarding decisions are typically guided by the desire to reduce the number of replicas of data items in the network to conserve bandwidth as well as by the desire to reduce end-to-end delay. Previous work has considered how the availability of various types of information about the network can be used to guide and improve forwarding decisions. In general, it is difficult to design an opportunistic forwarding algorithms, as their performance depends extensively on the characteristic of the mobility present in the network. We claim that it is critical to study first the properties of the paths made available between nodes by opportunistic contacts and mobility. This dissertation contributes to a better understanding of the performance of all opportunistic forwarding algorithms with regard to hops and delays. It proves analytically and validate empirically that there exist paths that are short both in terms of delay and hop-number in such opportunistic networks. This result has important impacts on how to design forwarding algorithms in opportunistic networks. In particular, it indicates that messages can be discarded after a few number of hops without occurring more than a marginal performance cost. This dissertation shows, also, that opportunistic contacts relate with social properties. It shows expected and unexpected similarities between social interaction between individuals and their mobility patterns, which confirm that classifying nodes based on their social properties could be relevant for the temporal network as well. We develop a systematic approach for the use of social interaction information as a means to guide forwarding decisions in this type of network. Our main insight is that social interaction information alone is not sufficient and needs to be augmented in some way with information about contact statistics. We address this challenge by developing the PeopleRank approach in which nodes are ranked using a tunable weighted combination of social and contact information. Our technique gives higher weight to the social information in cases where there is correlation between that information and the contact trace information. We develop centralized and distributed variants for the computation of PeopleRank. We present an evaluation using real mobility traces of nodes and their social interactions to show that PeopleRank manages to deliver messages with near optimal success rate (i.e., close to Epidemic Routing) while reducing the number of message retransmissions by 50% compared to epidemic routing.

2010 Publications

• 2010
  • A. Mtibaa : “Étude et caractérisation des chemins dans les réseaux ad hoc opportunistes”, thesis, phd defence 06/29/2010, supervision Fdida, Serge, co-supervision : Diot, Christophe (2010)