| Abstract: |
Opportunistic or Delay Tolerant Networks is a new networking paradigm that is envisioned to complement existing wireless technologies (cellular, WiFi) by exploiting a "niche" performance-cost
tradeoff. Wireless peers communicate when in contact, forming a network "on the fly" whose connectivity graph is highly dynamic and only partially connected. This gives rise to a number of
challenging optimization problems, such as end-to-end routing, resource allocation, content placement etc. While globally optimal solutions are normally sought in network optimization, node
actions and decisions in this context are inherently local. As a result, most solutions proposed rely on local heuristics without any guarantees about their convergence properties towards a
desired global outcome. In this paper, we look deeper into the problem of Distributed Optimization in the context of Opportunistic Networks. We propose an analytical framework and use it to study
deterministic (Greedy) and stochastic utility ascent (Markov Chain Monte Carlo) algorithms. Using this framework, we prove necessary and sufficient conditions for their correctness, and derive
closed form solutions for their performance (convergence probability and delay), in generic mobility scenarios. We use real and synthetic mobility traces to validate our findings, and examine the
impact of mobility properties in more depth. |
