Adaptive spatiotemporal node selection in dynamic networks

Pradip Hari, John B.P. McCabe, Jonathan Banafato, Marcus Henry, Kevin Ko, Emmanouil Koukoumidis, Ulrich Kremer, Margaret Martonosi, Li Shiuan Peh

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations

Abstract

Dynamic networks - spontaneous, self-organizing groups of devices - are a promising new computing platform. Writing applications for such networks is a daunting task, however, due to their extreme variability and unpredictability, with many devices having significant resource limitations. Intelligent, automated distribution of work across network nodes is needed to get the most out of limited resource budgets. We propose a novel framework for distributing computations across a dynamic network, in which applications specify their spatiotemporal properties at a very high level. The underlying system makes node selection decisions to exploit these properties, producing high quality results within a fixed resource budget. A distributed computation is expressed as a semantically parallel loop over a geographic area and time period. Feedback from the application about the quality of node selection decisions is used to guide future decisions, even while the loop is still in progress. This simplifies the process of writing dynamic network applications by allowing programmers to focus on the goals of their applications, rather than on the topology and environment of the network. Our framework implementation consists of extensions to the Java language, a compiler for this extended language, and a run-time system that work together to provide a simple, powerful architecture for dynamic network programming. We evaluate our system using 11 Nokia N810 tablet PC devices and 14 Neo FreeRunner (Openmoko) smartphones, as well as a simulation environment that models the behavior of up to 500 devices. For three representative applications, we obtain significant improvements in the number of useful results obtained when compared with baseline node selection algorithms: up to 745% (measured), 117% (simulated) for an Amber Alert application; 38% (measured), 142% (simulated) for a Bird Tracking application; and 86% (measured), 209% (simulated) for a Crowd Estimation application.

Original languageEnglish (US)
Title of host publicationPACT'10 - Proceedings of the 19th International Conference on Parallel Architectures and Compilation Techniques
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages227-236
Number of pages10
ISBN (Print)9781450301787
DOIs
StatePublished - 2010

Publication series

NameParallel Architectures and Compilation Techniques - Conference Proceedings, PACT
Volume2010
ISSN (Print)1089-795X

All Science Journal Classification (ASJC) codes

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture

Keywords

  • ad hoc networks
  • adaptive scheduling
  • dynamic networks
  • feedback-directed scheduling
  • location-awareness
  • node selection
  • quality of result
  • resource-awareness
  • spatial programming
  • spatiotemporal programming

Fingerprint Dive into the research topics of 'Adaptive spatiotemporal node selection in dynamic networks'. Together they form a unique fingerprint.

  • Cite this

    Hari, P., McCabe, J. B. P., Banafato, J., Henry, M., Ko, K., Koukoumidis, E., Kremer, U., Martonosi, M., & Peh, L. S. (2010). Adaptive spatiotemporal node selection in dynamic networks. In PACT'10 - Proceedings of the 19th International Conference on Parallel Architectures and Compilation Techniques (pp. 227-236). (Parallel Architectures and Compilation Techniques - Conference Proceedings, PACT; Vol. 2010). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1145/1854273.1854304