Distributed Data Aggregation Scheduling in Wireless Sensor Networks

Abstract

Data aggregation is an essential operation in wireless sensor network applications. This paper focuses on the data aggregation scheduling problem. Based on maximal independent sets, a distributed algorithm to generate a collision-free schedule for data aggregation in wireless sensor networks is proposed. The time latency of the aggregation schedule generated by the proposed algorithm is minimized using a greedy strategy. The latency bound of the schedule is 24D + 6 Delta + 16, where D is the network diameter and Delta is the maximum node degree. The previous data aggregation algorithm with least latency has the latency bound (Delta- Delta 1)R, where R is the network radius. Thus in our algorithm Delta contributes to an additive factor instead of a multiplicative factor, which is a significant improvement. To the best of our knowledge, the proposed algorithm is the first distributed algorithm for data aggregation scheduling. This paper also proposes an adaptive strategy for updating the schedule when nodes fail or new nodes join in a network. The analysis and simulation results show that the proposed algorithm outperforms other aggregation scheduling algorithms.