|
Abstract:
|
In this paper, we study efficient data collection for wireless sensor networks. We present efficient distributed algorithms with approximately the minimum delay, or the minimum messages to be sent by all nodes, or the minimum total energy costs by all nodes. We analytically proved that all our methods are either optimum or are 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 $\cal A$ for data collection %for a task $\cal T$ (data collection), let $\ratio_T$, $\ratio_M$, and $\ratio_E$ be the approximation ratio of $\cal A$ in terms of time complexity, message complexity, and energy complexity respectively. We then show that, for data collection, there are networks of $n$ nodes and maximum degree $\maxdeg$, such that $\ratio_M \ratio_E =\Omega(\maxdeg)$ for \emph{any} algorithm.
|
