direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

Publications by Type: Book Chapters

Path Formation in Human Contact Networks
Citation key SH-PFHCN-11
Author Sastry, Nishanth and Hui, Pan
Title of Book Handbook of Optimization in Complex Networks, Part 3
Pages 349–385
Year 2012
ISBN 978-1-4614-0856-7
Online ISBN 978-1-4614-0857-4
ISSN 1931-6828
DOI http://dx.doi.org/10.1007/978-1-4614-0857-4_12
Address Berlin / Heidelberg, Germany
Volume 58
Note Chapter 12
Publisher Springer
Series Springer Optimization and Its Applications
Abstract The Pocket Switched Network (PSN) is a radical proposal to take advantage of short-range connectivity afforded by human face-to-face contacts, and create longer paths by having intermediate nodes ferry data on behalf of the sender. The Pocket Switched Network creates paths over time using transient social con- tacts. This chapter explores the achievable connectivity properties of this dynamically changing mileu, and gives a community-based heuristic to find efficient routes. We first employ empirical traces to examine the effect of the human contact process on data delivery. Contacts between a few node pairs are found to occur too frequently, leading to inadequate mixing of data, while the majority of contacts occur rarely, but are essential for global connectivity. We then examine all successful paths found by flooding and show that though delivery times vary widely, randomly sampling a small number of paths between each source and destination is sufficient to yield a delivery time distribution close to that of flooding over all paths. Thus, despite the apparent fragility implied by the reliance on rare edges, the rate at which the network can deliver data is remarkably robust to path failures. We then give a natural heuristic that finds routes by exploiting the latent social structure. Previous methods relied on building and updating routing tables to cope with dynamic network conditions. This has been shown to be cost ineffective due to the partial capture of transient network behavior. A more promising approach would be to capture the intrinsic characteristics of such networks and utilize them for routing decsions. We design and evaluate BUBBLE, a novel social-based forwarding algorithm, that utilizes the centrality and community metrics to enhance delivery performance. We empirically show that BUBBLE can efficiently identify good paths using several real mobility datasets.
Link to publication Download Bibtex entry

Zusatzinformationen / Extras

Quick Access:

Schnellnavigation zur Seite über Nummerneingabe