  In deadline-constrained wireless sensor networks (WSNs), quality of
aggregation (QoA) is determined by the number of participating nodes in the
data aggregation process. The previous studies have attempted to propose
optimal scheduling algorithms to obtain the maximum QoA assuming a fixed
underlying aggregation tree. However, there exists no prior work to address the
issue of constructing optimal aggregation tree in deadline-constraints WSNs.
The structure of underlying aggregation tree is important since our analysis
demonstrates that the ratio between the maximum achievable QoAs of different
trees could be as large as O(2^D), where D is the deadline. This paper casts a
combinatorial optimization problem to address optimal tree construction for
deadline-constrained data aggregation in WSNs. While the problem is proved to
be NP-hard, we employ the recently proposed Markov approximation framework and
devise two distributed algorithms with different computation overheads to find
close-to-optimal solutions with bounded approximation gap. To further improve
the convergence of the proposed Markov-based algorithms, we devise another
initial tree construction algorithm with low computational complexity. Our
extensive experiments for a set randomly-generated scenarios demonstrate that
the proposed algorithms outperforms the existing alternative methods by
obtaining better quality of aggregations.
