Paper Info
Title
Performance of Distributed Algorithms in DTNs: Towards an Analytical Framework for Heterogeneous Mobility
Abstract
Opportunistic or Delay Tolerant Networks (DTNs) are envisioned to complement existing wireless technologies (cellular, WiFi). Wireless peers communicate when in contact, forming a network "on the fly", whose connectivity graph is highly dynamic and only partly connected. Because of this stringent environment, solutions to common networking problems (routing, congestion control, etc.) in this context are greedy, choosing the best solution among the locally available ones. This shared trait motivates the common treatment of such greedy algorithms for DTNs and raises some interesting questions: Do they converge? How fast are they? Yet, existing models study individual solutions. Moreover, they often assume homogeneous node mobility. The study of real world traces reveals considerable heterogeneity and non-trivial structure in human mobility. While algorithms have been proposed, accounting for this heterogeneity, their analytical tractability is still a challenge. In this paper, we propose a new model for greedy DTN algorithms, supporting the full heterogeneity of node mobility. We provide closed form solutions for crucial performance metrics (delivery probability and delay) and prove necessary and sufficient conditions for algorithm convergence. For illustration, we apply our model to the content placement problem, a variant of distributed caching. We use real and synthetic mobility traces to validate our findings and examine the impact of mobility properties in depth.
Year
DOI
Venue
2011
10.1109/GLOCOM.2011.6134354
Global Telecommunications Conference
Keywords
Field
DocType
delay tolerant networks,distributed algorithms,mobility management (mobile radio),analytical framework,connectivity graph,content placement problem,delay tolerant networks,distributed algorithm,distributed caching,greedy DTN algorithm,greedy algorithm,heterogeneous mobility,homogeneous node mobility,human mobility,opportunistic networks,synthetic mobility traces,tractability,wireless peers,wireless technology
Convergence (routing),Graph,Markov process,Wireless,Algorithm design,Computer science,Computer network,Real-time computing,Greedy algorithm,Distributed algorithm,Network congestion,Distributed computing
Conference
ISSN
ISBN
Citations 
1930-529X E-ISBN : 978-1-4244-9267-1
978-1-4244-9267-1
3
PageRank 
References 
Authors
0.39
11
2
Name
Order
Citations
PageRank
Andreea Picu130.39
Spyropoulos, Thrasyvoulos294137.38