Title:Distributed Aggregation in the Physical Model
Abstract:Given a set of nodes V, where each node has somedata value, the goal of data aggregation is to compute someaggregate function in the fewest timeslots possible. Aggregatefunctions compute the aggregated value from the data of allnodes; common examples include maximum or average. Weassume the realistic physical (SINR) interference model and no knowledge of the network structure or the number of neighbors of any node.We present a deterministic, distributed protocol to compute anaggregate function in O(D+ ∆log n) timeslots, where D is thediameter of the network, ∆ is the maximum number of neighborswithin a given radius and n is the total number of nodes. Inspite of operating under stricter limitations on the knowledgeof the initial state of the network, we demonstrate that our protocol can arbitrarily outperform even the best state-of-the-art approach in [H. Li et al., Ad Hoc networks, 2012].

Joint work with Nathaniel Hobbs, Yuexuan Wang, Dongxiao Yu and Francis C.M. Lau.