PhD proposal (for WNE students)

[Muhammad Israr Qadir]

PhD thesis proposal

Title: Optimal routing policies and network coding for mobile social networks

Advisors: Lucile SASSATELLI (Assistant professor, contact: sassa...@i3s.unice.fr, http://www.i3s.unice.fr/~sassatelli/)

Funding: This PhD thesis is proposed in the framework of the ANR JCJC project TRouP WilMA, and will be done at the I3S laboratory, CNRS/University Nice Sophia Antipolis, France.

The salary will amount to 1450 euros per month after tax, for 3 years.

Application: Send CV, motivation and recommendation letters, as well as referees and master marks.

Description:

The traditional infrastructure-centric networking paradigm has already proven inadequate to stand the growing demand for contents and updates generated by widespread mobile applications [N09,V09]. A promising alternative to overloading the telecommunication operators’ systems lies in the exploitation of user interactions through the design of smart decisions to convey information. Such approach therefore considers Mobile Ad Hoc Networks (MANETs or Delay Tolerant Networks - DTNs), which are meant to allow communication between mobile users without any infrastructure.

In DTNs, owing to high-speed mobility and possible disruptions, a big challenge is that of routing. Conventional Internet routing protocols (e.g., RIP and OSPF) as well as routing schemes for MANETs, such as DSR, AODV, assume that a complete instantaneous path exists between a source and a destination. Thus, if no end-to-end paths exist most of the time, these protocols fail to deliver data. Several proposals try to address this routing problem, and have all been optimized for mobility models in which nodes scatter uniformly over the whole space along time, such as in the independent identically distributed (i.i.d.) model, random walk and random waypoint (RWP). Such models fail to capture the real nature of MANETs, driven by space and social acquaintances. Recently, a clustered mobility model with heterogeneous nodes with anisotropic mobility patterns [GGL08], as typically encountered in realistic mobility traces, has been introduced. For such general model, we want to propose solutions to the opportunistic routing problem, assuming that nodes are not aware of the network topology.

The goal of the PhD thesis is to devise optimal routing policies and identify delay/energy trade-offs when the mobile nodes are oblivious of their own and other nodes' motion, for nodes with heterogeneous physical layer and clustered mobility, with the help of network coding. Network coding is a new network paradigm that has emerged in the last ten years. It consists in allowing intermediate nodes to modify information packets before forwarding them, and has proven to bring great advantages for several metrics in various network scenarii.

First, we will consider that a node has a single home-point, that there is a single unicast connection in the network. The optimal forwarding policies will be investigated, building on [ABP10], both theoretically and from simulations. Specifically, we will assess the performance of such policies with synthetic and real-world contact traces. How to fit such routing policies to real-world mobility will be addressed with the help of state-of-the-art clustering algorithms.

One step ahead, the PhD student will tackle the more intricate case of multiple home points, i.e., when a node belongs to several communities. Furthermore, the gain using intra-session network coding will be studied, and the model will be extended to the general case with network coding, multiple session, general buffer sizes and managements and contact bandwidths.

The third step will address the design of smart inter-session coding schemes for multi-session DTNs. Inter-session network coding is an active field of research, and effective routing schemes taking advantage of it are still to be found. Additionally, delay/throughput trade-offs under such model and routing scheme will be derived.

Pre-requisites:

Background in wireless communications, networking and statistics.

References:
[N09] www.nytimes.com/2009/09/03/technology/companies/03att.html
[V09] venturebeat.com/2009/05/11/iphone-users-eating-up-atts-network
[AGL09] G. Alfano, M. Garetto and E. Leonardi, "Capacity scaling of wireless networks with inhomogeneous node density: Upper bounds," IEEE Journal on Selected Areas in Communications, 27(7):1147-1157, 2009.
[ABP10] E. Altman, T. Basar, and F. De Pellegrini, “Optimal Monotone Forwarding Policies in Delay Tolerant Mobile Ad-Hoc Networks”, Elsevier Performance Evaluation, issue 67 (2010) pp. 299-317.

Best wishes and good luck,

Muhammad Israr Qadir