Efficient data collection for wireless networks: Delay and energy tradeoffs

We study efficient data collection in wireless sensor networks. We present efficient distributed algorithms with approximately the minimum delay, or the minimum number of messages to be sent by all nodes, or the minimum total energy costs by all nodes. We analytically prove that all proposed methods are either optimum or within constants factor of the optimum. We then investigate the possibility of designing one universal method such that the delay, the messages sent by nodes, and the total energy costs by all nodes are all optimum or within constants factor of optimum. Given a method A for data collection let ρ_T, ρ_M, and ρ_E be the approximation ratios of A in terms of time complexity, message complexity, and energy complexity respectively. We show that, for data collection, there are networks of n nodes and maximum degree Δ, such that ρ_Mρ_E = Ω(Δ) for any algorithm.