Randomized Sequential Algorithms for Data Aggregation

Abstract — We consider distributed algorithms for data ag-gregation in sensor networks. The algorithms are admitted via message passing hence through pairwise computations. Under these algorithms a transmitting node becomes inactive until it is reactivated, yielding to substantial energy gains. We study the per-node message and time complexities of the algorithms in explicit graphs as a function of the network size. The obtained complexities are compared to those of so-called gossip algorithms. The results suggest trade-offs between the number of messages transmitted and the computation times. I