Adaptive Spatiotemporal Node Selection in Dynamic Networks
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. Intelligen...
| Main Authors: | , , , , , , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Association for Computing Machinery
2011
|
| Online Access: | http://hdl.handle.net/1721.1/64736 https://orcid.org/0000-0001-9010-6519 |
| _version_ | 1811074685527392256 |
|---|---|
| author | Hari, Pradip McCabe, John B. P. Banafato, Jonathan Henry, Marcus Ko, Kevin Koukoumidis, Emmanouil Kremer, Ulrich Martonosi, Margaret Peh, Li-Shiuan |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Hari, Pradip McCabe, John B. P. Banafato, Jonathan Henry, Marcus Ko, Kevin Koukoumidis, Emmanouil Kremer, Ulrich Martonosi, Margaret Peh, Li-Shiuan |
| author_sort | Hari, Pradip |
| collection | MIT |
| description | 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. |
| first_indexed | 2024-09-23T09:53:44Z |
| format | Article |
| id | mit-1721.1/64736 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T09:53:44Z |
| publishDate | 2011 |
| publisher | Association for Computing Machinery |
| record_format | dspace |
| spelling | mit-1721.1/647362022-09-30T17:30:31Z Adaptive Spatiotemporal Node Selection in Dynamic Networks Hari, Pradip McCabe, John B. P. Banafato, Jonathan Henry, Marcus Ko, Kevin Koukoumidis, Emmanouil Kremer, Ulrich Martonosi, Margaret Peh, Li-Shiuan Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Peh, Li-Shiuan Peh, Li-Shiuan 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. National Science Foundation (U.S.) (CNS-EHS #0615175) National Science Foundation (U.S.) (#0614949) 2011-06-30T20:26:13Z 2011-06-30T20:26:13Z 2010-09 Article http://purl.org/eprint/type/ConferencePaper 9781450301787 http://hdl.handle.net/1721.1/64736 Hari, Pradip et al. “Adaptive Spatiotemporal Node Selection in Dynamic Networks.” Proceedings of the 19th International Conference on Parallel Architectures and Compilation Techniques, September 11-15, Vienna, Austria: ACM, 2010. 227-236. https://orcid.org/0000-0001-9010-6519 en_US http://dx.doi.org/10.1145/1854273.1854304 Proceedings of the Nineteenth International Conference on Parallel Architectures and Compilation Techniques, PACT '10 Creative Commons Attribution-Noncommercial-Share Alike 3.0 http://creativecommons.org/licenses/by-nc-sa/3.0/ application/pdf Association for Computing Machinery MIT web domain |
| spellingShingle | Hari, Pradip McCabe, John B. P. Banafato, Jonathan Henry, Marcus Ko, Kevin Koukoumidis, Emmanouil Kremer, Ulrich Martonosi, Margaret Peh, Li-Shiuan Adaptive Spatiotemporal Node Selection in Dynamic Networks |
| title | Adaptive Spatiotemporal Node Selection in Dynamic Networks |
| title_full | Adaptive Spatiotemporal Node Selection in Dynamic Networks |
| title_fullStr | Adaptive Spatiotemporal Node Selection in Dynamic Networks |
| title_full_unstemmed | Adaptive Spatiotemporal Node Selection in Dynamic Networks |
| title_short | Adaptive Spatiotemporal Node Selection in Dynamic Networks |
| title_sort | adaptive spatiotemporal node selection in dynamic networks |
| url | http://hdl.handle.net/1721.1/64736 https://orcid.org/0000-0001-9010-6519 |
| work_keys_str_mv | AT haripradip adaptivespatiotemporalnodeselectionindynamicnetworks AT mccabejohnbp adaptivespatiotemporalnodeselectionindynamicnetworks AT banafatojonathan adaptivespatiotemporalnodeselectionindynamicnetworks AT henrymarcus adaptivespatiotemporalnodeselectionindynamicnetworks AT kokevin adaptivespatiotemporalnodeselectionindynamicnetworks AT koukoumidisemmanouil adaptivespatiotemporalnodeselectionindynamicnetworks AT kremerulrich adaptivespatiotemporalnodeselectionindynamicnetworks AT martonosimargaret adaptivespatiotemporalnodeselectionindynamicnetworks AT pehlishiuan adaptivespatiotemporalnodeselectionindynamicnetworks |