Abstract

In wireless sensor networks, sensor nodes are used to collect data from the environment and send it to a data collection point or a sink node using a convergecast tree. Considerable savings in energy can be obtained by aggregating data at intermediate nodes along the way to the sink.

We study the problem of finding a minimum latency aggregation tree and transmission schedule in wireless sensor networks. This problem is referred to as Minimum Latency Aggregation Scheduling (MLAS) in the literature and has been proven to be NP-Complete even for unit disk graphs. We present a new simpler proof of the NP-Completeness of the MLAS Problem for arbitrary networks and unit disk graphs. We give tight bounds for the latency of aggregation convergecast for grids, tori, and trees. For regular unit interval graphs, we provide an algorithm which is guaranteed to have a latency that is within one time slot of the optimal latency. Finally, for unit interval graphs we give a 2-approximation algorithm to solve the same problem.

For arbitrary graphs, we introduce a new algorithm for building an aggregation tree. Furthermore, we propose two new approaches for building a transmission schedule to perform aggregation on a given tree. We evaluate the performance of our algorithms through extensive simulations on randomly generated graphs and we compare them to the previous state of the art. Our results show that one of our algorithms has a latency that is 38% less than the latency of the previous best algorithm.