Minimum-Time Aggregation Scheduling in Duty-Cycled Wireless Sensor Networks

Aggregation is an important and commonplace operation in wireless sensor networks. Due to wireless interfe- rences, aggregation in wireless sensor networks often suffers from packet collisions. In order to solve the collision problem, aggregation scheduling is extensively researched in recent years. In many sensor network applications such as real-time monitoring, aggregation time is the most concerned performance. This paper considers the minimum-time aggregation scheduling problem in duty-cycled wireless sensor networks for the first time. We show that this problem is NP-hard and present an approximation algorithm based on connected dominating set. The theoretical analysis shows that the proposed algorithm is a nearly-constant approximation. Simulation shows that the scheduling algorithm has a good performance.