An improved approximation algorithm for data aggregation in multi-hop wireless sensor networks

Abstract

Data aggregation is an efficient primitive in wireless sensor network (WSN) applications. This paper focuses on data aggregation scheduling problem to minimize the latency. We propose an efficient distributed method that produces a collision-free schedule for data aggregation in WSNs. We prove that the latency of the aggregation schedule generated by our algorithm is at most 16R+Δ--14 time-slots. Here R is the network radius and Δ is the maximum node degree in the communication graph of the original network. Our method significantly improves the previously known best data aggregation algorithm [3], that has a latency bound of 24D+6Δ+16 time-slots, where D is the network diameter (Note that D can be as large as 2R). We conduct extensive simulations to study the practical performances of our proposed data aggregation method. Our simulation results corroborate our theoretical results and show that our algorithms perform better in practice.