[Nrg-l] Thesis Proposal Defense: Vijay Erramilli, Thursday 1/24, 11am
crovella at cs.bu.edu
Thu Jan 17 15:05:10 EST 2008
Thesis Proposal Defense
Date: Thursday, 24th Jan 2008
Time: 11 AM
Location: MCS 135
Forwarding Algorithms for Mobile Opportunistic Networks
Mobile opportunistic networks are comprised of human-carried mobile
devices moving in a restricted physical space. Examples include
individuals moving in conferences, university campuses and in social
settings. They are characterized by nodes with heterogeneous contact
rates, unpredictable mobility and limited information. Communication in
such settings takes place by exploiting contact opportunities with other
nodes, and relying on the mobility of intermediate nodes as well as
multihop forwarding to deliver messages to their respective
destinations. Forwarding of messages in such networks is a non-trivial
task and has not been extensively studied. The little previous work on
this problem has focused on design and analysis of algorithms under
unrealistic assumptions (homogeneous contact rates, oversimplified
In this thesis, we design and analyze forwarding algorithms for such
networks. As opposed to previous work we rely on real mobility
measurements to guide us in the design and analysis of algorithms. This
enables us to relax some of the unrealistic assumptions, paving the way
for the design of effective protocols.
We believe that in order to design effective forwarding algorithms, it
is necessary to start by understanding the opportunities for forwarding
While some work has already studied the performance of various
forwarding algorithms in opportunistic networks, there is little
understanding to date on the 'nature'
of the forwarding problem in such settings. In particular, little is
known about the kinds of paths (making use of both mobility and multiple
hops) that exist in such networks. We first study the paths which are
available for forwarding by relying on measurements. We also study the
performance in terms of success rate and delay of previously proposed
algorithms by relying on trace-driven simulations.
One of the main conclusions of our study is that most algorithms perform
similarly in terms of success rate and delay, however they may differ in
terms of cost, where cost is defined as the number of message replicas
in the network per message. We design and analyze algorithms which aim
to reduce cost while maintaining high performance. We draw from optimal
stopping theory principles to design our algorithms.
More generally, forwarding in opportunistic networks can be related to
the question of navigability in complex networks. Navigability is
defined as the success of greedy forwarding/routing in these networks.
While there has been some recent work on this question, navigability has
not been studied in dynamic complex networks, like the networks we are
We aim to extend existing results on navigability on static complex
networks to dynamic networks. In addition, we also like to address the
question of cost of navigability in dynamic complex networks by
combining our earlier results involving optimal stopping theory.
We intend to implement some of our algorithms on actual mobile devices.
The measurement results from our implementation as well as the
comparison with existing algorithms will further aid us in designing
effective and efficient protocols.
Prof. Azer Bestavros
Prof. John Byers
Prof. Mark Crovella (Major Advisor)
Dr. Christophe Diot
More information about the Nrg-l