## 2 Related Work of Compressed Data Gathering  
In non-aggregation data gathering schemes, data packets generated by sensor nodes are directly forwarded to the sink node through a certain topology organization (e.g., the tree-type topology as shown in Figure 2A). These data gathering schemes do not exploit the correlation of network sensed data, resulting in the network forwarding a larger number of original packets; what's more, in addition to sending their own detected data, nodes that are closer to the sink node tend to relay a number of packets from remote nodes (e.g., in Figure 2A, node #5 forwards 11 packets while each leaf node only forwards one packet). Such an imbalance of energy consumption will inevitably lead to the quick failure of the whole network. Thus, the lifetime of nodes which are closer to the sink node forms a bottleneck in these data-gathering schemes. Plain-CDG, as shown in Figure 2B, is the earliest and the most rudumental data gathering scheme which exploits the CS and NC theory. During each data gathering epoch, every node needs to forward a fixed number of packets (denoted as \(M\)) to form \(M\) weighted sums \(Y_{i}\) (we let \(M=3\) in Figure 2B, and \(Y=\varphi_{i1}x_{1}+\varphi_{i2}x_{2}+\cdots+\varphi_{i11}x_{11},i=1,2,3\), where \(x_{j}\) is the reading of node #_j_ and \(\varphi_{ij}\) is its coefficient  
Figure 2: Non-CDG and typical CDG schemes. of this measurement). Note that each weighted sum corresponds to one measurement of network sensed data, and after receiving these measurement results, the sink node can reconstruct the network sensed data by adopting an appropriate CS reconstruction algorithm. Comparing to the Non-CDG schemes, Plain-CDG can reduce the number of transmissions, and balance the transmission load among sensor nodes. The authors in [9] proposed a scheme based on Plain-CDG, called Hybrid-CDG (shown in Figure 2C), to further reduce the number of transmissions. In the Hybrid-CDG scheme, nodes whose degrees are equal to or less than \(M\) will employ the Non-CDG to forward their readings and the others will employ the Plain-CDG scheme to generate \(M\) measurement packets. By comparing Figure 2C to Figure 2B, it is easy to find that the Hybrid-CDG scheme indeed reduces the redundancy transmission of the Plain-CDG (e.g., the leaf node #1 forwards three packets in Plain-CDG while only one packet in Hybrid-CDG). More efficient data gathering schemes using random sparse measurements were first introduced in [15] and developed in [14] as follows: at the beginning of each epoch, \(M\) projection nodes are selected randomly to collect \(M\) measurements (_i.e._, each projection node collects one measurement), meanwhile, each projection node is assigned or generates a sparse vector \(\Phi_{i}\) by itself. Then, projection node #i is obliged to inform all nodes whose coefficient \(\varphi_{ij}\
eq\ 0\) to report their contributions (\(\varphi_{ij}x_{j}\)) back. After receiving all segments of a measurement (\(y_{i}\)), the projection node sends the result to the sink node through the shortest routing path. An example of such measurement-formation process is illustrated in Figure 2D. To form the measurement result \(y_{1}\), as the projection node, node #5 has randomly generated a sparse coefficient vector \(\Phi_{1}=[\varphi_{11}\ 0\ \varphi_{13}\ 0\ 0\ 0\ 0\ 0\ \varphi_{19}\ 0\ 0]\), then, for these non-zero coefficients (\(\varphi_{11}\), \(\varphi_{13}\) and \(\varphi_{19}\)), it sends transmission requests to nodes #1, #3 and #9; these nodes reply to the requests by sending their contributions back (e.g., node #3 will reply \(\varphi_{13}x_{3}\)). Note that, similar to other CDG schemes, those packets can be merged into one single packet on their measurement formation path (e.g., packets can be merged on nodes #3 and #5 for forming measurement \(y_{1}\)--this packet-merging process can be regarded as a network coding process [16]). Similarly, other measurements are formed in the network and forwarded to the sink node.