## 5 Adaptive Termination Rule of the Measurement-Formation  
As we mentioned before, after choosing a reconstruction algorithm (such as BP, or MP), the sink node can reconstruct the \(K\)-sparse original signal with the probability close to 1 as long as it receives a certain number of measurement results (theoretically, \(O(KlogN)\)). However, as shown in Section 3, this bound cannot be applied to our method directly, because it requires prior knowledge of the sparsity information of the network sensed data. By using the conclusion from \"sequential compress sensing [20]\", an adaptive termination condition of measurement procedure was proposed in literature [21]. Specifically, assume that we can obtain measurement result of a \(K\)-sparse signal \(x\) (\(x\in\mathbb{R}^{N}\), \(K\) is unknown) step by step (each step gets one measurement result and we denote the measurement on step \(i\) as \(y_{i}=\varphi_{i}x\)); if the reconstruction result on step \(M\) is \(\hat{x}^{M}\) and \(\hat{x}^{M}=\hat{x}^{M-1}\), then \(\hat{x}^{M}\) is the result which we need (_i.e._, \(\hat{x}^{M}=x\)) with probability 1. Although this termination rule is very concise, it still has some limitations when applied it to CDG for WSNs. Because this rule is based on the dense measurement method (each measurement coefficients vector \(\varphi_{i}\) obey Gaussian distribution), as shown in Section 2, each measurement formation  
Figure 8: Piggyback nodes recovery and NAck packets loss. will concern every node in the network, which will lead to more energy consumption than the sparse measurement method. On the other hand, coefficients in the measurement vector of this termination rule are continuous; thus, it is very difficult to generate on cheap WSN sensor nodes. Therefore, we need to find a termination rule for the sparse measurement method in this study. The difference emerging from the dense Gaussian measurement method is that the probability of being nonsingular for each submatrix of the measurement coefficient matrix is no longer 0. In order to meet our specific demands, we modified the termination rule in [20] to obtain agreement for a certain number of consecutive measurements (denoted as \(\Delta M\)) (as shown in Proposition 1). Note that, we assume that the sink node can obtain and reconstruct the sparse Bernoulli measurement results step by step, and \(x\) represents the \(N\)-dimensional data vector which is desired by the sink node in each data-gathering epoch. **Lemma 1**. : _Let \(v\) be an \(n\)-dimensional sparse Bernoulli vector (\(v\in\{-1,0,1\}^{n}\)) and \(\mid\!\!\mid v_{0}\!\mid\!\mid\!\mid=\lambda\)\((0<\lambda\leqslant\ n)\). Let \(W\) be a deterministic \(w\)-dimensional subspace of \(\mathbb{R}^{n}(0<\lambda<w\leqslant n)\), then \(Prob(v\in W)\leqslant 3^{w-n}\)._  
Proof. : Given \(W\) being a \(w\)-_dimensional_ subspace, there exist \(w\) coordinates \(c_{i1},\ldots,c_{iw}\) that determine all the other \(n\)-\(w\) coordinates of an arbitrary vector \(c=(c_{1},\ldots,c_{n})\in\ W\). Thus, if we condition on the coordinates \(c_{i1},\ldots,c_{iw}\) of \(v\), there is at most one case to make \(v\in W\) in the other \(n\)-\(w\) coordinates. Hence the probability of \(v\in W\) is at most \(3^{-(n-w)}\). **Proposition 1**. : _Suppose that the sink node has got \(M-\ 1\) measurement results in previous \(M-1\) steps, and at step \(M\), if the sink node have got the measurement result \(y^{M}\) from the network, it can get a reconstruction result of network sensed data (denote as \(\hat{x}^{M}\)) from these received measurement results; if \(\hat{x}^{M}=\hat{x}^{M-1}=\ldots=\hat{x}^{M-\Delta M}\), \(\hat{x}^{M}\) is the reconstruction result which we need with probability no less than \(1-3^{-\Delta M}\)._  
Proof. : We prove this proposition by using _argumentum ad absurdum_. We denote the measurement coefficient vector at Step \(i\) as \(\varphi^{i}\), and the measurement result of Step \(i\) as \(y^{i}\).