2017/12/08 by Magnús M. Halldórsson, Halldorsson, Magnus M., Tigran Tonoyan +1
Computer Science · #Complexity and Algorithms in Graphs #Energy Efficient Wireless Sensor Networks #FOS: Computer and information sciences #Mobile Ad Hoc Networks #Networking and Internet Architecture (cs.NI)
paper · pdf · doi:10.48550/arxiv.1712.03053
openalex publication_date 2017/12/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
One of the most fundamental tasks in sensor networks is the computation of a (compressible) aggregation function of the input measurements. What rate of computation can be maintained, by properly choosing the aggregation tree, the TDMA schedule of the tree edges, and the transmission powers? This can be viewed as the convergecast capacity of a wireless network. We show here that the optimal rate is effectively a constant. This holds even in arbitrary networks, under the physical model of interference. This compares with previous bounds that are logarithmic (e.g., Ω(1/log n)). Namely, we show that a rate of Ω(1/log^* Δ) is possible, where Δ is the length diversity (ratio between the furthest to the shortest distance between nodes). It also implies that the scheduling complexity of wireless connectivity is O(log^* Δ). This is achieved using the natural minimum spanning tree (MST). Our method crucially depends on choosing the appropriate power assignment for the instance at hand, since without power control, only a trivial linear rate can be guaranteed. We also show that there is a fixed power assignment that allows for a rate of Ω(1/loglog Δ). Surprisingly, these bounds are best possible. No aggregation network can guarantee a rate better than O(1/loglog Δ) using fixed power assignment. Also, when using arbitrary power control, there are instances whose MSTs cannot be scheduled in fewer than Ω(1/log^* Δ) slots.