Delay-sensitive data gathering in wireless sensor networks

In this paper, we study data gathering in wireless sensor networks where intermediary nodes perform data aggregation with total fusion. We focus on gathering tree construction (from a general network topology) and transmission scheduling in order to minimize gathering delay. We first propose an algorithm that calculates an optimal transmission schedule and the minimal delay, for any given gathering tree. Then, we prove a lower bound, in terms of the number of nodes in the network, on the optimal gathering delay for any graph. After analyzing the gathering trees formed by several popular tree constructing algorithms, we propose an algorithm that constructs the optimal gathering tree for a complete graph. We then conduct extensive simulations to show that the proposed algorithm is also a promising approximation algorithm for arbitrary graphs. We also propose an approximation algorithm that constructs a gathering tree that achieves a maximum-degree-optimal solution.