Paper Info
Title
On the construction of maximum-quality aggregation trees in deadline-constrained WSNs
Abstract
In deadline-constrained data aggregation in wireless sensor networks (WSNs), the imposed sink deadline in an interference-limited network hinders participation of all sensor nodes in data aggregation. Thus, a subset of nodes can contribute in aggregation and quality of aggregation (QoA) increases with the growth of the number of participating nodes. Scheduling the nodes' transmissions is a central problem, which aims to maximize the QoA, while satisfying the sink deadline, i.e., on-time delivery of the sensed data to the sink node. Although the previous studies have proposed optimal scheduling algorithms to this problem given a particular aggregation tree, there is no work on constructing optimal tree in this context. The underlying aggregation tree can make a big difference on QoA since we demonstrate that the ratio between the maximum achievable QoAs of different trees could be as large as O(2 <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">D</sup> ), where D is the sink deadline. In this paper, we cast an optimization problem to address optimal tree construction for deadline-constrained data aggregation in WSNs. The problem is combinatorial in nature and difficult to solve as we prove its NP-hardness. We employ Markov approximation framework and devise two distributed algorithms with different computation overheads to find bounded close-to-optimal solutions. Simulation experiments in a set of representative randomly-generated scenarios show that the proposed algorithms significantly improve QoA by 101% and 93% on average compared to the best, to our knowledge, existing alternative methods.
Year
DOI
Venue
2015
10.1109/INFOCOM.2015.7218386
2015 IEEE Conference on Computer Communications (INFOCOM)
Keywords
Field
DocType
maximum-quality aggregation trees,deadline-constrained WSN,deadline-constrained data aggregation,wireless sensor networks,interference-limited network,imposed sink deadline,quality of aggregation,QoA,optimal scheduling algorithms,optimization problem,Markov approximation framework,distributed algorithms,NP-hardness problem
Scheduling (computing),Computer science,Markov chain,Distributed algorithm,Optimization problem,Wireless sensor network,Data aggregator,Sink (computing),Bounded function,Distributed computing
Conference
Volume
ISSN
Citations 
abs/1405.0597
0743-166X
4
PageRank 
References 
Authors
0.40
20
3
Name
Order
Citations
PageRank
Bahram Alinia1203.02
Mohammad H. Hajiesmaili28717.99
Ahmad Khonsari321042.43