Randomized Sequential Algorithms for Data Aggregation in Sensor Networks

We consider distributed algorithms for data aggregation 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.