|
Authors: | Andreea Picu, Thrasyvoulos Spyropoulos |
Group: | Communication Systems |
Type: | Techreport |
Title: | Distributed Optimization in DTNs: Towards Understanding Greedy and Stochastic Algorithms |
Year: | 2010 |
Month: | July |
Pub-Key: | PS10TR |
Keywords: | DTN, modeling, performance analysis |
Rep Nbr: | 326 |
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. |
Resources: | [BibTeX] [Paper as PDF] |