An Energy-Efficient Distributed Algorithm for Minimum-Latency Aggregation Scheduling in Wireless Sensor Networks
Yingshu Li, Longjiang Guo, Sushil K. Prasad · 2010
Data aggregation is an essential yet time-consuming task in wireless sensor networks (WSNs). This paper studies the well-known Minimum-Latency Aggregation Schedule (MLAS) problem and proposes an energy-efficient distributed scheduling algorithm named Clu-DDAS based on a novel cluster-based aggregation tree. Our approach differs from all the previous schemes where Connected Dominating Sets or Maximal Independent Sets are employed. We prove that Clu-DDAS has a latency bound of 4R' + 2Delta - 2, where Δ is the maximum degree and R' is the inferior network radius which is smaller than the network radius R. Clu-DDAS has comparable latency as the previously best centralized algorithm E-PAS, while Clu-DDAS consumes 78% less energy as shown by the simulation results. Clu-DDAS outperforms the previously best distributed algorithm DAS whose latency bound is 16R' + Δ - 14 on both latency and energy consumption. On average, Clu-DDAS transmits 67% fewer total messages than DAS does. We also propose an adaptive strategy for updating the schedule to accommodate dynamic network topology.