Efficient data aggregation in multi-hop wireless sensor networks under physical interference model

Efficient aggregation of data collected by sensors is crucial for a successful application of wireless sensor networks (WSNs). Both minimizing the energy cost and reducing the time duration (or called latency) of data aggregation have been extensively studied for WSNs. Algorithms with theoretical performance guarantees are only known under the protocol interference model, or graph-based interference models generally. In this paper, we study the problem of designing time efficient aggregation algorithm under the physical interference model. To the best of our knowledge, no algorithms with theoretical performance guarantees are known for this problem in the literature. We propose an efficient algorithm that produces a data aggregation tree and a collision-free aggregation schedule. We theoretically prove that the latency of our aggregation schedule is bounded by O(R+Δ) time-slots. Here R is the network radius and Δ is the maximum node degree in the communication graph of the original network. In addition, we derive the lower-bound of latency for any aggregation scheduling algorithm under the physical interference model. We show that the latency achieved by our algorithm asymptotically matches the lower-bound for random wireless networks. Our extensive simulation results corroborate our theoretical analysis.