Deterministic distributed data aggregation under the SINR model

Abstract

Given a set of nodes ν, where each node has some data value, the goal of data aggregation is to compute some aggregate function in the fewest timeslots possible. Aggregate functions compute the aggregated value from the data of all nodes; common examples include maximum or average. We assume the realistic physical (SINR) interference model and no knowledge of the network structure or the number of neighbors of any node; our model also uses physical carrier sensing. We present a distributed protocol to compute an aggregate function in O(D+Δlogn) timeslots, where D is the diameter of the network, Δ is the maximum number of neighbors within a given radius and n is the total number of nodes. Our protocol contributes an exponential improvement in running time compared to that in [18]. © 2012 Springer-Verlag.