Robust Computation of Aggregates in Wireless Sensor Networks: Distributed Randomized Algorithms and Analysis

摘要: A wireless sensor network consists of a large number small, resource-constrained devices and usually operates in hostile environments that are prone to link node failures. Computing aggregates such as average, minimum, maximum sum is fundamental various primitive functions network, system monitoring, data querying, collaborative information processing. In this paper, we present analyze suite randomized distributed algorithms efficiently robustly compute aggregates. Our random grouping (DRG) algorithm simple natural uses probabilistic progressively converge the aggregate value. DRG local naturally robust against dynamic topology changes from link/node Although our simple, it nontrivial show converges correct value bound time needed for convergence. analysis eigenstructure underlying graph novel way convergence running algorithms. We also simulation results compare its performance other known Simulations needs far fewer transmissions than localized schemes