2014/05/03 by Bahram Alinia, Mohammad Hajiesmaili, Alinia, Bahram +4 · 1 citation
Computer Science · #Data Management and Algorithms #Energy Efficient Wireless Sensor Networks #FOS: Computer and information sciences #Mobile Ad Hoc Networks #Networking and Internet Architecture (cs.NI) #cs.NI
paper · pdf · doi:10.48550/arxiv.1405.0597
This paper has been withdrawn by the author due to a crucial sign error in equation 1
openalex publication_date 2014/05/03 · arxiv created 2014/07/31 · arxiv updated 2014/08/01 · openalex created_date 2022/10/03 · openalex updated_date 2026/07/28
In deadline-constrained data aggregation in wireless sensor networks (WSNs), the imposed sink deadline along with the interference constraint hinders participation of all sensor nodes in data aggregation. Thus, exploiting the wisdom of the crowd paradigm, the total number of participant nodes in data aggregation determines the quality of aggregation (QoA). Although the previous studies have proposed optimal algorithms to maximize QoA under an imposed deadline and a given aggregation tree, there is no work on constructing optimal tree in this context. In this paper, we cast an optimization problem to address optimal tree construction for deadline-constrained data aggregation in WSNs. We demonstrate that the ratio between the maximum achievable QoAs of the optimal and the worst aggregation trees is as large as O(2D), where D is the sink deadline and thus makes devising efficient solution of the problem an issue of paramount value. However, the problem is challenging to solve since we prove that it is NP-hard. We apply the recently-proposed Markov approximation framework to devise two distributed algorithms with different computation overheads that converge to a bounded neighborhood of the optimal solution. Extensive simulations in a set of representative randomly-generated scenarios show that the proposed algorithms significantly improve QoA by %101 and %93 in average compared to the best, to our knowledge, existing alternative methods.