{'fraction_non_alphanumeric': 0.03444498777506112, 'fraction_numerical': 0.00702200488997555, 'mean_word_length': 4.355751099937146, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 13, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Maximum-Quality Tree Construction for Deadline-Constrained Aggregation in WSNs

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.


A. Motivation
Nowadays, monitoring and tracking applications are intrinsically intertwined with a plethora of Wireless Sensor Networks (WSNs). To accomplish monitoring effectively, data gathering is witnessed as a fundamental operation in such applications. In addition, limited battery of sensors emphasizes the need for energy-aware data gathering design. However, packet transmission as the major source of energy depletion turns energy conservation in data gathering into an acute problem [2].
To reduce the energy depletion of sensors due to excessive packet transmission, data aggregation [2], [3] has been proposed as a promising energy conservation mechanism to eliminate the necessity of redundant transmission. In a typical data aggregation scenario, a data aggregation tree is constructed over the underlying WSN topology [4] and some intermediate nodes are solicited to aggregate/fuse the gathered data of different sensors by in-network computation and transmit a single packet to the next hop. Consequently, the amount of packet transmission is significantly reduced, thereby the overall energy consumption decreases.
Despite its apparent benefits in reducing overall energy usage, data aggregation, however, can impose additional delay toward sending the data to the sink since the intermediate nodes in aggregation tree must wait to gather enough data from the predecessors and then aggregate and forward the data to the next hop. This additional data aggregation waiting time might be intolerable for many real-time and surveillance applications that are sensitive to the amount of the latency of the receiving data. For example in target tracking application, the detected location of a moving object may has perceptible error with the actual location if data aggregation process takes too long [5]. Thus, the delay contribution of a data aggregation algorithm must be taken into account in an efficient design so as to respect the delay constraint of the application. Some previous researches have considered participation of all sensor nodes in data aggregation and aimed to minimize the aggregation delay as the objective [6], [7]. However, participation of all sensor nodes introduces severe interference and may lead to terminating data aggregation in a time that is beyond the application's tolerable delay even attempting in delay minimization.
Consequently, these designs fail to guarantee a maximum application-specific tolerable delay for data aggregation.

B. Deadline-Constrained Data Aggregation Scenario and Challenges
As a promising alternative, the idea of deadline-constrained data aggregation has been advocated in the recent studies [4], [8]. The general idea is to incorporate a maximum applicationspecific tolerable delay, namely deadline, as a hard constraint, and try to improve the Quality of Aggregation (QoA) by participating the sensor nodes as much as possible before the aggregation time exceeds the deadline. Subsequently, the problem turns into maximizing QoA, subject to the application-specific deadline constraint [4], [8]. Toward this goal, the following two critical challenges should be addressed appropriately: 1) the scheduling policy, and 2) the structure of aggregation tree.
(1) Scheduling policy. Delay in data aggregation is originated from two sources: (i) waiting time to gather the data of predecessor nodes in data aggregation tree, and (ii) waiting time due to the interference issue which is an inherent challenge in wireless networks. In this way, if overall waiting time of a node exceeds a specific value, its data cannot be delivered to the sink before the deadline. Devising an efficient policy that schedules the nodes' waiting time while preventing degradation of the QoA and meeting the delay constraint of the application is a challenging problem. The previous research has tried to find an efficient scheduling such that QoA is maximized [4]. The details are explained in Section. II.
(2) The structure of aggregation tree. The structure of data aggregation tree is another important factor such that the number of participant nodes in data aggregation could be further improved by constructing a proper data aggregation tree. For data aggregation, a tree rooted at the sink node is the common structure since it simplifies design of routing and aggregation protocols and also helps to avoid problems such as double counting [9]. Without constructing an appropriate aggregation tree, we may not be able to achieve a desired level of QoA even by designing the scheduling algorithm optimally. We show that even with optimal scheduling policy, the structure of underlying aggregation tree can make a big difference on achievable QoA.
While the first critical challenge on how to schedule the sensors is tackled in the previous studies [4], [8], the ultimate optimal design, however, cannot be fully achieved without taking into account the second critical challenge on how to construct an optimal underlying data aggregation tree. The goal of this paper is to address the second challenge.

C. Summary of Contributions
In this paper, we aim to construct an optimal aggregation tree and run an optimal treespecific scheduling algorithm on the tree to maximize QoA. However, constructing the optimal aggregation tree given the network topology is nontrivial even in centralized manner. This is more problematic when we seek an appropriate solution amenable to distributed realization so as the sensor nodes choose their parents just using local information. We address this problem in single-sink WSNs setting through the following contributions: • We demonstrate the impact of data aggregation tree structure on QoA by theoretical discussion and explanatory example. We show that the ratio between the maximum achievable QoAs of two data aggregation trees is O(2 D ) in the worst case where D is the aggregation deadline. This observation makes the problem of constructing maximum QoA tree intriguing. Besides, we prove that the problem of optimal tree construction belongs to the class of NP-hard problems.
• After formulating the underlying tree construction problem, we leverage the recently proposed Markov approximation framework [10] as a general framework toward solving combinatorial network problems in distributed fashion. By addressing the unique challenges devoted to our problem, we devise two close-to-optimal algorithms in which the sensor nodes contribute to migrating toward the optimal tree in an iterative manner. The highlights are distributed implementation, bounded approximation gap, and robustness against the error of global estimation of sensor nodes by local information.
• To further improve the obtained QoA and convergence of Markov approximtion framework, we propose an initial tree construction algorithm, called FastInitTree, as the initialization step of our main algorithm. The algorithm features are low computational complexity and close-to-optimal estimate for the initial tree construction, i.e., the QoA obtained by initial tree constructed by FastInitTree is close to the QoA achieved when the main algorithm converges. We also analyze the validity of constructed trees when the deadline value is changed by the application and we prove that for the cases that the deadline decreases there is no need to executed the algorithms again and construct a new tree.
• Through extensive experiments, we show the superiority of our algorithms and compare them to the previous work [4]. Results demonstrate that four different versions of our algorithm (two algorithms which start from random tree and two algorithms which use FastInitTree's output as initial Markov chain state) greatly increase the QoA of the proposed algorithm in [4] (that is only by finding optimal scheduling without optimal tree construction).

D. Paper Organization
The rest of this paper is organized as follows. We review the related work in Section II. In Section III, the system model is introduced and by motivating examples and theoretical analysis the impact of aggregation tree on QoA is investigated. Problem formulation and NP-hardness analysis are explained in Section IV. In Section V, we devise two distributed algorithms for the problem. In Section VI, we explain our tree initialization algorithm. Simulation results are described in Section VII. Finally, concluding remarks and future directions are mentioned in Section VIII.

A. Minimum delay and deadline-constrained aggregation
The problem of minimum delay data aggregation tackled intensively in the literature. In [11], it is proved that the Minimum Latency Aggregation Scheduling (MLAS) problem is NP-hard and a (∆ − 1)-approximation algorithm has been presented where ∆ is the maximum node degree in the network. The current best approximation algorithms in [7], [12] achieve an upper bound of O(∆+R) on data aggregation delay where R is the network radius. While most studies consider a protocol interference model, the studies in [6], [13] assume a physical interference model that is more practical than the former. In [13], a scheduling algorithm for tree-based data aggregation is designed that achieves a constant approximation ratio by bounding the delay at O(∆ + R).
The work is extended in [6] for any arbitrary network topology. A connected dominating set or maximum independent sets are employed in [14] to provide a latency bound of 4R + 2∆ − 2 where R is inferior network radius.
Within the context of deadline-constrained data aggregation models, the goal is not to minimize the delay as an objective of the problem. Rather, the objective is to maximize the number of sensor nodes participating in aggregation while respecting the application-specific deadline. This type of real-time data aggregation has recently gained attention in some works [4], [5], [8], [15], [16]. In this regard, [4] presented a polynomial time optimal algorithm for the problem under the deadline and one-hop interference constraints. The problem is extended in [5] for a network with unreliable links under an additional constraint on nodes' energy level. In [5], the authors proved that in a network with V nodes, the problem is NP-hard when the maximum node degree of the aggregation tree is ∆. They proposed a polynomial-time exact algorithm when ∆ = O(log V ).
In [8], the authors considered the same problem of [4] by taking into account the effect of data redundancy and spatial dispersion of the participants in the quality of final aggregation result and proposed an approximate solution for proved NP-hard problem. In a more general case, [16] tackles the utility maximization problem in deadline constrained data aggregation and collection then provides efficient approximation solutions. A main drawback of the aforementioned studies is that they all have tried to maximize the quality of data aggregation on a given tree and neglect the impact of the data aggregation tree structure.

B. Optimum Aggregation Tree Construction
Several studies have tackled the problem of constructing optimal data aggregation tree [17]- [21] where all have been shown to be NP-hard. [18] extends the problem for multi-sink WSNs.
The problem of constructing an aggregation tree in order to minimize the total energy cost is addressed in [21]. As solution, a constant factor approximation algorithm is proposed. In [17], the problem of constructing a minimum cost aggregation tree under Information Quality (IQ) constraint has been tackled. The authors considered event-detection WSNs and defined IQ as detection accuracy. [22] shows that for the shortest path trees, the problem of building maximum lifetime data aggregation tree can be solved in polynomial time and propose two centralized and distributed algorithms. In this paper, however, we aim to construct maximum quality aggregation tree under deadline constraint. This problem has not been addressed yet by the research community. Moreover, our solution method in solving the problem is completely different from the previous research and is based on a recently-proposed theoretical foundation, namely Markov approximation that may be considered as a potential solution for the same category of problems.

A. WSN System Model
Consider a WSN whose topology is a graph G = (V ∪ {S}, ξ) where S is the sink node, V is the set of sensor nodes with |V| V , and ξ is the set of links between sensor nodes. We assume that all nodes have a fixed communication range and (i, j) ∈ ξ if nodes i and j are adjacent, i.e., they are in the communication range of each other. Without loss of generality, we assume that each link has a unit capacity. Moreover, we suppose that the system is time-slotted and synchronized and a transmission takes exactly one time slot. In deadline-constrained scenario, the data has to be received by the sink by the end of at most D time slots, where the value of D is specified by the deadline requirement of the applications. The interference model is one-hop such that two active links having a node in common cause an interference [4], [8], [15].
The data aggregation is done using an overlay spanning tree ψ ∈ T (G) (rooted at the sink node) on top of the underlying WSN topology where T (G) is the set of all spanning trees in the graph G. Let H ψ (i) ⊆ V be the set that consists of node i and all its predecessors (except the sink) in aggregation tree ψ.
We consider two types of nodes, source nodes and relay nodes. Source nodes can sense their own data and forward/aggregate the other nodes' data. Relay nodes just forward/aggregate the data of other nodes. To illustrate this, we use binary variable F i , where F i = 1 if node i is a source and F i = 0, otherwise. Moreover, binary variable n ψ i with n ψ i = 1 indicates that node i in tree ψ is allowed to send data to its parent and n ψ = [n ψ i , i ∈ V]. Indeed, n ψ i = 1 indicates that node i participates in data aggregation. In this case, if F i = 1 then node i is a source participant, otherwise node i participates in data aggregation as a relay node, i.e., it just aggregates the received data from its successors and forwards to its parent.
Let V ψ leaf ⊆ V be the set of all leaf nodes and V ψ sel-src ⊆ V be the set of source nodes selected for data aggregation in tree ψ. Indeed, i ∈ V ψ sel-src , if i is a source and all of its predecessors are selected for aggregation, i.e., V ψ sel-src = i ∈ V : F i = 1 and j∈H ψ (i) n ψ j = 1 . To devise a feasible aggregation scheme, we assign a waiting time of W ψ i , 0 ≤ W ψ i ≤ D time slots to each participant node i in aggregation tree ψ and W ψ = [W ψ i , i ∈ V]. The notion QoA ψ ( W ) denotes the quality of aggregation in tree ψ under assigned waiting times determined by W . We follow the definition in [4] for QoA ψ ( W ) as the number of source nodes that participate in data aggregation, i.e., For notational convenience, we define QoA ψ ( W i ) as QoA of the sub-tree of tree ψ rooted at node i with assigned waiting time of W i . Hereafter, we use QoA and W i instead of QoA ψ ( W i ) and W ψ i when the corresponding tree and scheduling are obvious, or a specific tree or scheduling is not the matter of concern. The summary of notations are listed in Table I.

B. Optimal Scheduling Policy
Now, we proceed to explain by example how to find the maximum QoA in a given tree in simple and tractable cases. The examples also clarify the data aggregation model for the reader.
Not selected (n i =0) process, in the first time slot, node 1 and node 5 send their packets to their parents in parallel.
In the second time slot, node 2 aggregates its own packet with the received data from node 5 and sends the aggregated data to the sink. It is not hard to see that this scheduling policy is optimal, i.e., it achieve the maximum QoA given the fixed aggregation tree. As a non-optimal waiting time assignment, consider the assignment of W 1 = 1, W 2 = 0. In this case, the final QoA is 2 with participant nodes 1 and 2. With D = 3, the maximum QoA is 7 and the optimal In [4], an algorithm is proposed to achieve the maximum QoA ψ ( W ) in a given tree ψ. The scheduling algorithm in [4] is optimal given a fixed tree as input and it does not change the structure of the tree for further improvement of QoA.

C. Investigating The impact of Aggregation Tree
We argue that the aggregation tree structure may significantly impact QoA. Firstly, we claim that the optimal aggregation does not follow any regular pattern. For example, the structure of the optimal tree should not follow chain-like long trees. The reason is that when sink imposes a deadline D, all nodes with height "≥ D" cannot participate in data aggregation due to the delay constraint. Consequently, the height of the tree is limited to D and long trees cannot be proper structures. Instead, one might suggest a tree so as the height of the majority of nodes is QoA. Roughly speaking, an aggregation tree which is neither so long nor so fat is suitable. It is important to stress that the above conditions cannot bring significant insights to devise an algorithm to construct the optimal tree. In the next example, we demonstrate that maximum QoA of two aggregation trees of a same network can be large even using optimal scheduling of [4].  Fig. 2b shows a random tree with the maximum QoA of 9. Finally, the optimal data aggregation tree is shown in Fig. 2c where all nodes are participants. The optimal tree in this toy example is obtained by trial and error. We emphasize that finding the optimal aggregation tree is not straightforward even in our tractable topology with only 12 nodes, while in practice the scale of the network is much larger than that of this example. Proof: It is proved in [8] that QoA is bounded to 2 D − 1 regardless of the aggregation tree structure. The bound is touchable when the network graph is dense enough where an obvious case is a complete graph (for more details, refer to Section VI). Therefore, we proceed to calculate the upper bound in the worst case. Indeed, the worst case occurs when we construct a chain-like tree with sink as the head of the chain. Observe that for a node i, |H ψ (i)| is equal to the distance of i to the sink in aggregation tree ψ. In a chain tree, there is only one possible way of scheduling where each node i having the property |H ψ (i)| ≤ D assigned a waiting time of D − |H ψ (i)| and is a participant. There are D such nodes and therefore the maximum QoA of the tree is D.
The motivating example 2 and Theorem 1 clearly signify the importance of aggregation tree structure on the final QoA. In the next section, we formally formulate the optimal aggregation tree construction as an optimization problem.

IV. PROBLEM FORMULATION
Having defined the system model notations in Section III-A, we proceed to formulate the joint aggregation tree construction and scheduling problem to find the optimal tree as follows: where M ψ i = min j:(j,i)∈C W ψ j is the minimum waiting time of the children of node i on tree ψ. Constraints (2c)-(2e) enforce the feasible set of waiting times according to the definitions. The most important constraint is given by Equation (2b) to ensure that the deadline and interference constraints are not violated. Constraint (2b) states that in a feasible scheduling, the summation of number of participant children of a parent node i and the minimum waiting time of its children should be less than or equal to node i's waiting time, W ψ i . We explain this constraint in detail. Observe that a selected children of i can only be assigned a waiting time of W ψ i − 1, . . . , 0 due to deadline constraint in the parent node. Moreover, no two children of i can have a same waiting time otherwise, their simultaneous transmissions will be interfered in the parent node.
Therefore, parent i can choose at most W ψ i children with distinct assigned waiting times chosen from the set {W ψ i − 1, . . . , 0}. In addition, the value of M ψ i is not always zero because in some cases number of selected children of i is less than W ψ i . Therefore, transmissions can only occur in time slots M ψ i , M ψ i + 1, . . . , W ψ i − 1 which gives a total of W ψ i − M ψ i time slots. Since in each time slot we have at most one transmission (interference constraint), the total number of selected children cannot exceeds W ψ i − M ψ i .

A. NP-hardness
The problem of finding the optimal tree is hard to solve as the number of trees in the network is extremely large in reality. For example, in a complete network graph with V nodes and a sink, the number of feasible trees is V V −2 . We prove that problem Z is at least as hard as a variant of classical Maximum Coverage Problem (MCP) called Maximum Coverage Problem with Group Budget Constraint (MCPG) which is known to be NP-hard [23].
Maximum Coverage Problem (MCP). Given a collection of n sets U = {S 1 , S 2 , . . . , S n } and a number l, the goal of MCP is to form set U by choosing at most l sets from U such that the union of selected sets has the maximum cardinality: Maximum Coverage Problem with Group Budget Constraint (MCPG). In [23], MCPG is introduced as a general case of MCP. In MCPG, n sets S 1 , . . . , S n at MCP are partitioned to L groups G 1 , . . . , G L . MCPG has two versions namely cost and cardinality versions where the latter is our interest. In the cardinality version of MCPG, given number l, we should select at most l sets from U such that the cardinality of union of the selected sets is maximized. Moreover, we are permitted to choose at most one set of each group. MCPG is clearly NP-hard because MCP which is known to be NP-hard [23] is a special case of MCPG where each set in U is considered as a group.
The similarity between our tree construction problem and MCPG is that in both cases the objective is to maximize the cardinality. In MCPG we can choose at most one set from each group. Similarly, in problem Z, each node can subscribe (cover) different set of sensor nodes based on its deadline and we are allowed to choose at most one set according to the assigned deadline.
Theorem 2. Problem Z is NP-hard.
Proof: To prove, we reduce MCPG to problem Z with a polynomial time algorithm. To this end, we construct network graph G such that the sink is directly connected to L non-source sensor nodes C 1 , . . . , C L where L is the number of groups in MCPG. There are V other sensor nodes all considered as source nodes connected to C 1 , . . . , C L either directly or indirectly where V is equal to the total number of distinct elements in all groups. That is, where |g ij | is the cardinality of j th set in group i and |G i | is the number of sets in group i.
Then, we set the sink deadline to D ≥ N where N is the total number of sets in L groups, i.e., N = L i=1 |G i |. We connect V sensor nodes to C 1 , . . . , C L and to each other such that if we assign a deadline of D − (( i−1 k=1 |G k |) + j − 1) to the sink's neighbor C i , j th set of G i , 1 ≤ j ≤ |G i | denotes the maximum cardinality set of the sensor nodes who will participate in data aggregation as the successors of C i in a sub-tree rooted at this node in aggregation tree. An optimal assignment of deadlines to C 1 , . . . , C L is equal to select at most one set from each group of MCPG where this optimal assignment results in maximizing both the number of participants in data aggregation tree as well as the number of covered elements in MCPG.
Therefore, a polynomial time optimal algorithm of problem Z leads to a polynomial solution of MCPG which completes the proof.

V. MARKOV-BASED APPROXIMATE SOLUTION
Since problem Z is NP-hard, it is not possible to devise a computationally-efficient algorithm for the optimal solution even in a centralized manner. As such, we pursue approximate solutions.
Among different approximation methods, we leverage Markov approximation framework [10] to propose an efficient near-optimal solution for the problem. Generally, in this framework the goal is to tackle combinatorial optimization problems in distributed manner so as 1) to construct a class of problem-specific Markov chains with a target steady-state distribution and 2) to investigate a particular structure of Markov chain that is amenable to distributed implementation. We first begin with a brief primer of the theoretical approximation framework [10] in the next subsection.

A. Markov Approximation
Recall that T denotes the set of all possible trees (configurations) of the network. For notational convenience, let us define Φ D ψ = max(QoA ψ ( W )) , i.e., when the network relies on tree ψ ∈ T for data aggregation and sink deadline is D, the maximum data aggregation quality is Φ D ψ . We note that Φ D ψ is obtained by running the optimal scheduling algorithm subject to all the constraints in problem Z. In other words, all possible trees are feasible configurations in our tree construction algorithm and the scheduling policy ensures the feasibility in terms of respecting the interference and deadline constraints in Equation (2b). Denote p ψ as the percentage of time that configuration ψ is employed to accomplish data aggregation. Using these notations we can rewrite problem Z as follows: To derive a closed-form of the optimal solution of problem Z eq and to open new design space for exploring a distributed algorithm, we formulate problem Z β as an approximate version of Z eq using log-sum-exp approximation [10] Z β : max s.t.
where β is a large enough positive constant that controls the accuracy of the approximation.
Problem Z β is an approximated version of problem Z off by an entropy term − 1 β ψ∈T p ψ log p ψ and it is a convex optimization problem so by solving KKT conditions, its optimal solution is obtained by Moreover, the optimal value is Finally, the approximation gap is characterized as: where the approximation gap approaches to zero as β approaches to infinity. This means that with larger values of β the approximation model is more accurate.
In the next step, our endeavor is to obtain the solution of problem Z β by time-sharing among different tree configurations according to p * ψ in Eq. (6). According to the basic framework, the key is to investigate a well-structured and distributed-friendly Markov chain whose stationary distribution is p * ψ .

B. Markov Chain Design
We design a time-reversible Markov chain with states space being T and the stationary distribution being p * ψ . Then, we use this Markov chain structure to hop (migrate) among different states (trees) such that a tree with high QoA has more chances to be visited by Markov random walks. The problem is solved when the Markov chain converges to the ideal steady-state distribution.
Given the Markov chain state space, the next step is to construct the transition rate between two states. Let ψ, ψ ∈ T be two states of Markov chain and q ψ,ψ be the transition rate from ψ to ψ . Herein, the theoretical framework enriches us by two degrees of freedom. It turns out that the key in designing distributed algorithms is to design a Markov chain such that (i) the Markov chain is irreducible (i.e., any two states are reachable from each other) and (ii) the detailed balance equation is satisfied (i.e., p * ψ q ψ,ψ = p * ψ q ψ ,ψ , ∀ψ, ψ ∈ T ). Consequently, we are allowed to set the transition rates between any two states to be zero if they are still reachable from any other states. We refer the reader to [10] for further explanation.
In practice, however, direct transition between two states means migration between two tree structures. To derive a distributed algorithm, we only allow direct transitions between two states if the current and the target trees can be transformed to each other by only one parent changing operation in one of the trees. Namely, two states ψ and ψ are directly reachable from each other if we can construct tree ψ by deleting an edge (i, j) ∈ ξ from ψ and adding edge (i, k) ∈ ξ to ψ. Using this transition structure the next step is to set the transition rate as follows: where α ≥ 0 is a constant and q ψ ,ψ is defined symmetrically.

C. Algorithm Design
Our goal is to realize a distributed implementation of the Markov chain proposed in the previous section. In this part, we detail our implementation.
To compute transition rate between the states, the maximum QoA of both the current (Φ D ψ ) and the target (Φ D ψ ) states are required. To calculate these values we employ the scheduling algorithm proposed in [10], namely "Waiting-Assignment" algorithm. "Waiting-Assignment" is a distributed polynomial time algorithm to find the optimal waiting time of the nodes and hence Φ D ψ in tree ψ. Our algorithm runs as follows. Given initial aggregation tree ψ and deadline D, we first run "Waiting-Assignment" algorithm to obtain Φ D ψ . Then, based on the underlying Markov chain design and in an iterative manner, we proceed to migrate to a target aggregation tree ψ with (probably) better Φ D ψ than Φ D ψ . To realize this end, each sensor node individually runs "Parent-Changing" algorithm which is summarized as Algorithm 1.
The detailed description of Algorithm 1 is as follows. In Line 3, an exponentially distributed random number with mean λ i = 1 |N ≥i | is generated as the timer value in which this setting is required to ensure the convergence of the corresponding Markov chain. In Line 4, node i selects a new parent P i such that W P i ≥ W i . This ensures that after the parent changing, the data structure still remains a tree since the new structure is not a tree only if node i chooses its new parent from its successors where all have a less waiting time than node i's waiting time.
Meanwhile, this strategy is also rational because finding a new parent with a shorter waiting time declines node i's new waiting time which probably reduces QoA. In Lines 5-7, node i Algorithm 1: "Parent-Changing" algorithm for node i ∈ V Input: α, β Output: New parent of node i Node i generates a timer τ i ∼ exp(λ i ) with mean λ i = 1 |N ≥i | and starts to count down 4 When τ i expires, node i randomly selects one of its neighbors P i ∈ N ≥i . 5 Φ prev ← node i's estimation of Φ D ψ in Equation (9), i.e., the maximum QoA of the current tree 6 Node i changes its parent to P i 7 Φ next ← node i's estimation of Φ D ψ in Equation (9), i.e., the maximum QoA of the new tree 8 With probability q ψ,ψ , node i keeps the new tree configuration and with probability 1 − q ψ,ψ switches back and connects to the previous parent P i 9 if i changed its parent in Step 8 then 10 P i invokes "Waiting-Assignment" algorithm on its sub-tree 11 P i invokes "Waiting-Assignment" algorithm on its sub-tree 12 Node i refreshes the timer and begins counting down temporarily changes its parent and estimates the impact of this change on the maximum QoA of data aggregation. Based on the estimation and transition rate given by Equation (9), in Line 8, node i decides whether to keep its new parent or not. If the new state is established, then nodes P i and P i should run "Waiting-Assignment" algorithm to update waiting time of their successors because of their sub-tree changes. It is worthy to note that the parameter β not only affects the accuracy of the approximation, but also with large values of β, the algorithm migrates towards better configurations more greedily, whereas it may lead to premature convergence and trap into local optimum trees. Proof: The designed Markov chain is finite space state ergodic Markov chain where each tree configuration in state space is reachable from any other state by one or more parent changing process. We proceed to prove that the stationary state of designed Markov chain is Equation (6). Let ψ → ψ denote transition from state ψ to ψ at a timer expiration and . Moreover, Pr(ψ → ψ ) is the probability of this transition. This probability can be calculated as follows: Pr(ψ → ψ ) = Pr(i chooses P |i's timer expires).Pr(i's timer expires) In the algorithm, node i counts down with rate |N ≥i |. Therefore, the rate of leaving state ψ is j∈V |N ≥j |. We can calculate transition rate q ψ,ψ as follows: We can see that p * ψ .q ψ,ψ = p * ψ .q ψ ,ψ . Therefore, the detailed balance equation holds and the stationary distribution of constructed Markov chain is Equation (6) [24].
"Parent-Changing" algorithm is distributed if we can estimate Φ next and Φ prev in the algorithm in a distributed manner. By exact calculation of these values, the designed Markov chain will converge to stationary distribution in Equation (6). Hence, "Parent-Changing" algorithm can give us a near-optimal solution of problem Z. However, exact calculation of Φ next and Φ prev is not possible in nodes locally since they can only be calculated in the sink by running "Waiting-Assignment" algorithm. Therefore, we need to estimate their values. We estimate the values by two different methods.
Approx-1: First method of estimating Φ next and Φ prev . When node i wants to modify its parent from P i to P i (and subsequently tree ψ to ψ ), one possible way of estimation is running "Waiting-Assignment" algorithm by nodes P i and P i on their sub-trees. Let Φ prev [s] and Φ next [s] denote the maximum achievable QoAs in a sub-tree rooted at node s before and after the sub-tree change, respectively. Then, we have the following estimation: When node i changes its parent from P i to P i , only sub-trees rooted at P i and P i change and all other parts of the tree remain intact and so the estimation accuracy is expected to be high.
This estimation comes with the overhead of running "Waiting-Assignment" algorithm at nodes P i and P i to calculate Φ next and Φ prev .
Approx-2: Second method of estimating Φ next and Φ prev . Another way of estimation is just using waiting times of nodes P i and i: A larger value of W P i indicates that node i probably will be assigned a greater waiting time if it joins to sub-tree of P i and vice versa. In Section VII, we evaluate the efficiency of both mentioned methods by simulation.

D. Perturbation Analysis
In "Parent-Changing" algorithm, if we obtain the accurate value of Φ D ψ to calculate transition rates, the designed Markov chain converges to the stationary distribution given by Equation (6). Thus, we have a near-optimal solution of problem Z with optimality gap determined in Equation (8). In distributed fashion, however, we estimate the optimal tree-specific QoAs by Equations (12) and (13). Consequently, the designed Markov chain may not converge to the stationary distribution in Equation (6). Fortunately, our employed theoretical approach can provide a bound on the optimality gap due to the perturbation errors of the inaccurate estimation using a quantization error model.
We assume that in a tree configuration ψ, the corresponding perturbation error is bounded to In order to simplify the approach, we further assume that Φ D ψ takes only one of the following 2n ψ + 1 values: where n ψ is a positive constant. Moreover, with probability η j,ψ , the maximum quality of aggregation is equal to Φ D ψ + j n ψ ∆ ψ , ∀j ∈ {−n ψ , . . . , n ψ } and n ψ j=−n ψ η j,ψ = 1. Letp denote the stationary distribution of the states in the perturbed Markov chain [24]. We also denote stationary distribution of the configurations in the original and perturbed Markov chains by p * : {p * ψ , ψ ∈ T } andp : {p ψ , ψ ∈ T }, respectively. Then, we have [24] p Using total variance distance [25] we can measure the distance of p * ψ andp ψ as Theorem 3. a) The total variance distance between p * ψ andp ψ is bounded by For proof and remarks, we refer to [24].
Finally, we highlight that the convergence (mixing time) of the algorithm based on Markov approximation framework is studied in [24] and [26]. Overall, this framework, in its basic setting suffers from slow rate of convergence. To mitigate this, a promising solution is to find a "good" initial aggregation tree as the input for the iterative Alg. 1, thereby its convergence time can be improved. In this regard, the goal in the next section is to develop an algorithm to construct a fast initial aggregation tree.

VI. INITIAL TREE CONSTRUCTION ALGORITHM
We proceed to develop an initial tree construction algorithm to identify a good starting feasible solution for bootstrapping the Markov approximation-based algorithms. The intuition is that if Alg. 1 starts from a tree which already has a good quality, not only high-quality data aggregation experience can be provided starting from the beginning, but also fast convergence of the algorithm proposed in the previous section can be achieved. Alg. 2 outputs a near optimal feasible aggregation tree which is a spanning tree over the underlying WSN topology.
In a nutshell, Alg. 2 aims to find an appropriate unique parent for each node (except the sink) in the graph. By doing so, a feasible aggregation tree is indeed constructed. In particular, V done includes the nodes that their parents are chosen and initially defined as an empty set. Alg. 2 calls behind this is that a parent with less children is more likely to be able to participate its new  deadline D if the optimal tree in G is an optimal tree in a complete graph with V nodes where Alg. 3 is the main part of the FastInitTree algorithm. It works recursively on the input parent P to develop a tree. Note that the maximum number of participant nodes with deadline D is 2 D − 1 (see [8] for the proof) that is achievable if the graph is well-structured for deadline D, thereby its structure allows to construct a tree with the maximum feasible QoA of 2 D − 1. We emphasize that if a graph is well-structured, it does not imply that the number of communication links in the graph is equal (or even close) to the number of links in the corresponding complete graph. For further illustration, let's consider the well-structured graph in Fig. 3a with 7 (i.e., 2 3 − 1) nodes and 12 links. Despite more connectivity among the nodes in the graph of Fig. 3b, it is not a well-structured graph and its optimal QoA is less than the optimal QoA in Fig. 3a.
Finally, we call the optimal tree of a well-structured graph G = {V ∪ {S}, E} as ideal tree for deadline D while its maximum QoA is 2 D − 1. Now, we turn back to explain the main idea behind developing Alg. 2. In Alg. 2 we assume that the network graph is well-structured and try to build an aggregation tree such that its structure is as close as possible to the corresponding ideal tree. It is not difficult to see that in ideal tree, the number of children of each node (including sink) is equal to its waiting time (as in Fig.   3a). Based on this fact, Alg. 2 starts from the sink node and by calling Alg. 3 tries to find top D most powerful neighbors of sink, where the power of a node is defined as the number of its neighbors (Line 5 in Alg. 3). Indeed, the algorithm assumes that these D nodes will have waiting times {D − 1, . . . , 0} according to their ability to communicate with the other nodes, i.e., their power. Then, the algorithm considers these nodes as the sink's children in the final tree. Alg. 3 is called recursively on sink's children to build the rest of the tree. The wisdom of the algorithm in selecting children of each node makes it as a promising method.

A. Discussions on the Optimality and Complexity of Alg. 2
Theorem 4 proves that Alg. 2 outputs the optimal tree, given that the underlying graph is complete.
Theorem 4. Alg. 2 generates an optimal aggregation tree given that the underlying graph is a complete graph G k with k ≥ 2 D − 1.
Proof: Note that in an ideal tree for deadline D, we have this key property that after running optimal scheduling algorithm [4] on the tree, each node having waiting time w, 0 ≤ w ≤ D, has exactly w children with waiting times {w − 1, . . . , 0}. By following the steps of Alg. 2, it can be seen that the algorithm preserves the key property of the ideal tree while constructing the aggregation tree. The recursive tree construction process starts from the sink node. Since  N v log v). Alg. 2 goes over nodes who are not in V done to assign them to a parent which costs O(N ). Therefore, the total cost of the Alg. 2 is O (N v log v).

B. Remarks on the Time-varying Deadline in the Sink
Data aggregation is a periodic action in WSNs and in each period, the sink may change aggregation parameters such as deadline. When deadline changes, the previously constructed aggregation tree in the last period may not produce the same level of QoA. In this situation, a new tree structure is needed to maximize QoA under the new deadline. A naïve approach in this situation is running the tree construction algorithm with the new deadline. However, the following theorem shows that the optimal tree does not need to be changed for the case that the deadline is decreased as compared to its previous value. Second, the number of participant nodes in the new scheduling, namely X, can be calculated by subtracting total number of nodes with waiting time less than D from 2 D − 1 since with the new scheduling, these nodes' waiting times will be negative which has no meaning and makes them non-participant nodes. Therefore, we can sum up all nodes in the previous scheduling having waiting time greater than or equal to D to find X. Formally, we have X = f (D − D ) + f (D − D + 1) + · · · + f (D) where, f (i) denotes the number of nodes in the previous scheduling with assigned waiting time i. Note that we have f (i) = f (i + 1) + f (i + 2) + · · · + f (D) and By solving the above equation Theorem 6 implies that if we construct a near optimal tree for a specific deadline, then the same tree can be used for all shorter deadlines. Most importantly, the new scheduling is straightforward and needs no cost. This can help to avoid the overhead of running the tree construction and scheduling algorithm when deadline changes.

VII. SIMULATION RESULTS
In this section, we evaluate our proposed algorithms through extensive simulations. Unless otherwise specified, the settings are as follows: 100 sensor nodes uniformly dispersed in a square field with side length of 300m. Sink node is located at the center of the top side of the square field i.e., its position is (150,300). Communication range of nodes is 75m, i.e., two nodes are connected in the network if their distance is "≤ 75m". After deployment, sensor nodes construct an initial data aggregation tree. Except for the experiments that use initial tree built by FastInitTree algorithm, the tree is constructed based on Greedy Incremental Tree (GIT) algorithm [27]. We let α = 0.2 and β = 2, and choose 80% of nodes randomly as the sources.
Each data point of the figures belongs to the average value of 50 runs with the 95% confidence interval where each run is a different random topology. Moreover, for each topology, sink imposes a deadline in terms of time slots uniformly and randomly selected from interval [10,20]. We report the results of approximation algorithms after 50 iterations where an iteration is defined as a timer expiration of a sensor node.

A. Performance Comparison with the Optimal Solution
In this section, we compare the performance of the proposed methods to the optimal solution.
Since calculating optimal solution is computationally infeasible in large scale networks, we set

Z-Optimal
The optimal solution of problem Z implemented using exhaustive search Approx-1 Approximation algorithm that estimates the current QoA using Equation (12) in each node (has some overheads) Approx-2 Approximation algorithm that estimates the current QoA using Equation (13) and in each node (has no overheads) Algorithm of [4] Optimal algorithm presented in [4] to maximize QoA in a given tree Approx-1H Approx-1 starting from initial tree constructed by FastInitTree Approx-2H Approx-2 starting from initial tree constructed by FastInitTree   dispersed in a field with side length of 40m and sink coordinate is (20,40). Moreover, due to small network size, we consider all sensors as the source nodes. Fig. 4 portrays QoA of markov based algorithms against sink deadline. The main purpose is to compare our schemes with the optimal. The result for the algorithms "Approx-1", "Approx-2", "Approx-1H" and "Approx-2H" are very close to each other. "Approx-1H" is 93% close to optimal in this case which is slightly better than the other algorithms. We believe that in realworld scenarios with the higher number of sensor nodes, the performance difference between the markov based algorithms is more visible than that of the small scenario. To scrutinize this claim in more detail, we set up another set of experiments to investigate the improvements against various deadlines in the next subsection.

B. The Effect of the Deadline
We now study the effect of sink deadline on QoA. Based on Fig. 5, the trend is that QoA improves as deadline increases. This is in line with the fact that by increasing the deadline, more sensor nodes have the opportunity to participate in data aggregation.
A notable observation is that FastInitTree shows a better performance compared to both "Approx-1" and "Approx-2" when the deadline is less than 17. Its result is also 96% of the "Approx-1H". There is also a small difference between "Approx-1" and "Approx-2". On average, "Approx-2" is 98% close to "Approx-1". Based on these observations, FastInitTree seems a proper choice with respect to its low overhead and low cost. "Approx-1H" has the best performance among all algorithms and improves "Algorithm of [4]" by 106%, on average. The poor quality of "Algorithm of [4]" is a result of ignoring the impact of data aggregation tree structure.

C. The Effect of Parameter β
As it is stated in Section IV.A, the approximation gap theoretically decreases while β increases.
This parameter is an input for the proposed Markov based approximation algorithms and has a big impact on convergence rate of the algorithms. We depict the effect of β by simulation in Fig. 6. Since "Algorithm of [4]" and FastInitTree are independent of the value of β, Fig. 6 only portrays the amount of improvements by Markov based algorithms to "Algorithm of [4]". By increasing β, in addition to achieving higher improvements, we observe that the improvement momentum of Markov based schemes to "Algorithm of [4]" degrades while β grows. This is a consequence of fast convergence of approximation schemes to the optimal where in the proximity of optimal solution improvements are smaller. The experimental results of Fig. 6 confirm the theory.

E. The Effect of FastInitTree on the Convergence Rate
Since the transition rates are set wisely to improve the maximum QoA of the aggregation tree, we expect to obtain a better QoA as the number of transitions increases. Each transition can only occur after a node's timer expiration. However, all timer expiration does not lead to a transition. A key point here is that a desired level of QoA can be achieved with a fewer number of transitions if the initial tree provided by FastInitTree algorithm is chosen wisely. Fig.   8 demonstrates how the four Markov-based approximation algorithms improve as the number of iterations increases. Note that the only difference between "Approx-1" and "Approx-1H" is in their initial state. The difference between "Approx-2" and "Approx-2H" is also similar. Then, a key point here is the effect of FastInitTree algorithm on the convergence rate of Markov approximation. "Approx-2H" with 10 iterations reaches the same level of QoA that "Approx-2" Finally, in a microscopic view in Fig. 9, we demonstrate the evolution of the maximum achieved QoA after each transition, i.e., migrating to a new aggregation tree, for a randomly selected sample topology.

VIII. CONCLUSION
In this paper, we addressed the NP-hard problem of constructing data aggregation tree in WSNs, with the goal of maximizing the number of nodes that the sink receives their data within an application-specific aggregation deadline. Two successive algorithms were proposed: first, a distributed algorithm that runs in iterative manner and eventually converges to a bounded neighborhood of the optimum, and second, a bootstrapping algorithm with low complexity that can be served as a good initial point for the former. Observations on experiments corroborated our analysis on the importance of constructing the optimal aggregation tree. Moreover, experimental results demonstrated that our methods not only achieved a close-to-optimal solution, but also significantly outperformed the existing methods that rely on fixed underlying data aggregation trees. Last but not the least, this work is the first attempt on leveraging Markov approximation as a general framework to tackle tree construction in WSNs and we believe that this solution approach can be used in several other applications for constructing trees in distributed manner.
Obtained results open several important future directions. It would be interesting to incorporate energy consumption and turn the problem to an energy-aware QoA maximization one. This is important because the data aggregation is a periodic operation in the network and hence, relying on a fixed aggregation tree for a long time may lead to energy depletion of some specific nodes and degrade the network performance and lifetime. A wise policy might be to try to follow a uniform distribution of nodes' contribution in data aggregation, while keeping the QoA at the desired level. The second line is to tackle forest construction problem for multi-sink networks. This is a challenging problem, since even the single sink scenario, as the special case of a multi-sink network, has been proved to be NP-hard.