Dynamic Approaches to In-Network Aggregation
Preprint
Abstract
Collaboration between small-scale wireless devices hinges on their ability to infer properties shared across multiple nearby nodes. Wireless-enabled mobile devices in particular create a highly dynamic environment not conducive to distributed reasoning about such global properties. This paper addresses a specific instance of this problem: distributed aggregation. We present extensions to existing unstructured aggregation protocols that enable estimation of count, sum, and average aggregates in highly dynamic environments. With the modified protocols, devices with only limited connectivity can maintain estimates of the aggregate, despite \textit{unexpected} peer departures and arrivals. Our analysis of these aggregate maintenance extensions demonstrates their effectiveness in unstructured environments despite high levels of node mobility.Keywords
All Related Versions
This publication has 3 references indexed in Scilit:
- Spatial gossip and resource location protocolsJournal of the ACM, 2004
- Tracking Join and Self-Join Sizes in Limited StorageJournal of Computer and System Sciences, 2002
- Probabilistic counting algorithms for data base applicationsJournal of Computer and System Sciences, 1985