Title: Forwarding in Mobile Opportunistic Networks (PhD Thesis)
Author: Vijay Erramilli
Abstract:
Date: December 19, 2008
Recent advances in processor speeds, mobile communications and battery
life have enabled computers to evolve from completely wired to
completely mobile. In the most extreme case, all nodes are mobile and
communication takes place at available opportunities -- using both
traditional communication infrastructure as well as the mobility of
intermediate nodes. These are \emph{mobile opportunistic} networks.
Data communication in such networks is a difficult problem, because of
the dynamic underlying topology, the scarcity of network resources
and the lack of global information.
Establishing end-to-end routes in such networks is usually not feasible.
Instead a store-and-carry forwarding paradigm is better suited for such
networks. This dissertation describes and analyzes algorithms
for forwarding of messages in such networks.
In order to design effective forwarding algorithms for mobile
opportunistic networks, we start by first building an understanding of the
set of all paths between nodes, that represent the available
opportunities for any forwarding algorithm. Relying on real measurements,
we enumerate paths between nodes and uncover what we refer to as the
\emph{path explosion} effect. The term path explosion refers to the fact
that the number of paths between a randomly
selected pair of nodes increases exponentially with time. We draw from the
theory of epidemics to model and explain the path explosion effect. This
is the first contribution of the thesis, and is a key observation that
underlies subsequent results.
Our second contribution is the study of forwarding algorithms. For this,
we rely on trace driven simulations of different algorithms that span a
range of design dimensions. We compare the performance (success rate and average delay)
of these algorithms. We make the surprising observation that most
algorithms we consider have roughly similar performance. We explain this result
in light of the path explosion phenomenon.
While the performance of most algorithms we studied was roughly the same,
these algorithms differed in terms of cost. This prompted us to focus on
designing algorithms with the explicit intent of reducing costs. For this,
we cast the problem of forwarding as an optimal stopping problem.
Our third main contribution is the design of strategies based on optimal
stopping principles which we refer to as \emph{Delegation} schemes.
Our analysis shows that using a delegation scheme reduces cost over naive
forwarding by a factor of $O(\sqrt N)$, where $N$ is
the number of nodes in the network. We further validate this result on
real traces, where the cost reduction observed is even greater.
Our results so far include a key assumption, which is unbounded buffers on
nodes. Next, we relax this assumption, so that the
problem shifts to one of prioritization of messages for transmission and
dropping. Our fourth contribution is the study of message prioritization
schemes, combined with forwarding. Our main result is that one achieves higher
performance by assigning higher priorities to young messages in the
network. We again interpret this result in light of the path explosion
effect.