2009 · 73 citations · 27 references
ComputingComputer ScienceComputer NetworksSchedulingWireless CommunicationsDistributed ComputingInterference ManagementLatency OptimizationSensor NetworksWireless NetworksWireless Sensor NetworksAggregationData SchedulingEnergy-efficient Wireless Sensor NetworksGraph-based Interference ModelsNode DegreeNode Scheduling
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.
27
Approximate aggregation techniques for sensor databases
Jeffrey Considine, Fanrong Li, George Kollios et al. · 2004 · 564 citations
Nisheeth Shrivastava, Chiranjeeb Buragohain, Divyakant Agrawal et al. · 2004 · 487 citations