Efficient Decentralized Approximation via Selective Gossip

Recently, gossip algorithms have received much attention from the wireless sensor network community due to their simplicity, scalability and robustness. Motivated by applications such as compression and distributed transform coding, we propose a new gossip algorithm called Selective Gossip. Unlike traditional randomized gossip which computes the average of scalar values, we run gossip algorithms in parallel on the elements of a vector. The goal is to compute only the entries which are above a defined threshold in magnitude, i.e., significant entries. Nodes adaptively approximate the significant entries while abstaining from calculating the insignificant ones. Consequently, network lifetime and bandwidth are preserved. We show that with the proposed algorithm nodes reach consensus on the values of the significant entries and on the indices of insignificant ones. We illustrate the performance of our algorithm with a field estimation application. For regular topologies, selective gossip computes an approximation of the field using the wavelet transform. For irregular network topologies, we construct an orthonormal transform basis using eigenvectors of the graph Laplacian. Using two real sensor network datasets we show substantial communication savings over randomized gossip. We also propose a decentralized adaptive threshold mechanism such that nodes estimate the threshold while approximating the entries of the vector for computing the best m -term approximation of the data.