## 4 Measurement Formation Process
### Construction of the Measurement-Formation Path (Tree)  
According to the perspective of graph theory, this measurement-formation process comes down to constructing a sink-rooted path which covers all interested nodes. To improve the efficiency of measurement formation, the total length of this tree should be minimized. Thus, the construction of such optimal tree is a typical Steiner minimum tree problem [17]. Unfortunately, it has been proved to be a kind of NP-complete problem [18]. To solve this problem, a heuristic method based on the All-Pair-Shortest-Paths (APSP) [14] algorithm has been proposed for CDG applications. However, APSP tries to form a line-shape measurement-formation path which does not consider the wireless transmission characteristics of WSNs. For example, the total lengths of both the left and right trees in Figure 6 are 6, but if we consider the eavesdropping characteristics of the wireless channels used in WSNs, the actual transmission overheads of the left and right trees are 6 and 4, respectively. From this example, we can find that the overhead of the construction of this tree depends on the number of non-leaf nodes, namely the number of relay nodes. Thus, this is a Maximum Leaf Nodes-Minimum Steiner Nodes (MLMS) problem, _i.e._, we need to build a sink-rooted minimum Steiner tree (denoted by \(T\)) that covers all interested nodes (denoted by \(I\)). Note that not all interested nodes are located on the leaf nodes, some can also act as non-leaf nodes. MLMS tree has the requirement to minimize the number of introduced non-interested nodes (or called Steiner nodes), and maximum number of leaf nodes. In the next subsection, we will present the mathematical model of this problem, and after that, a global approximation algorithm is designed to solve this problem. Note that, classical converge-cast protocols can be a good candidate for data aggregation schemes as well as those CDG applications which do not consider the measurement coefficients generation/distribution (these CDG applications assume that nodes in network have already been assigned the measurement coefficients). Through this local gradient-routing mechanism, measurement results can be safely reported to the sink node. We proposed our MLMS tree-shape method based on an overall consideration of path generation, coefficients generation/distribution and the measurement results' formation, and the measurement-formation path is created at the time of the global seed distribution. Figure 5: Global seed distribution and measurement result packet merge on node #3.  
associated nodes or groups to form a new group; and we repeat this process until find out all groups. Next, in order to make group leader nodes and the remaining interested nodes be connected with the sink node, an optimal Steiner tree approximation algorithm is required. Since this problem is NP-complete, we proposed an alternative algorithm which is built upon the minimum spanning tree (MST) algorithm. The scope to run the MST is the closure that takes the sink node as a fulcrum and contains all the remaining interested nodes. Then, we perform the Graham scan algorithm to obtain a convex hull of all remaining groups. At last, we perform the MST algorithm to connect these nodes in convex hull. Detailed description of this algorithm is shown in Algorithm 2. It is easy to see that for each measurement formation tree, maximum iterations times for group formation is \(\rho/2\); and for the node-sparse graph, the proposed algorithm has a complexity of \(O\left(\rho^{2}d^{2}\right)\), and for the edge-sparse graph is \(O\left(\rho^{2}d^{2}+nlogn+n^{2}\right)\), where \(d\) is the average degree of the nodes in network, \(n\) is the number of edges and \(\rho\) is the number of interested nodes. ```
Input: Sparse measurement coefficients vectors \(\Phi_{1},\Phi_{2}\ldots,\Phi_{M}\) each with \(n\) i.i.d.