## 5 Optimized Node Sampling for Energy Efficient Data Collection  
The LRMA based data collection depends on the random sampling measurements \(\mathbf{M}\). From the low rank completion theory [13], to get good recovery accuracy, the elements in \(\mathbf{M}\) should better have a uniform distribution. Therefore, the selected nodes for sensing data should have uniform distribution in the deployed area, which is also the request for completely sensing the physical phenomena. However, as the many-to-one data collection pattern, this uniform node sampling method will bring unbalance energy distribution of the network and shorten its lifetime. To realize an energy efficient node selection at each data collection round, we propose an optimized node sampling method considering both the uniform random sampling and the network energy balance. In this method, we use Gini Index to measure the evenness of a random node sampling scheme and the network energy status and then find the optimized node sampling solution to meet the two-fold requests. Gini index is often used for evaluating data inequality according to frequency distributions. There is a demonstration of Gini Index shown in Figure 2a, where \(l_{1}\) represents the perfect equal cumulative ratio, \(l_{2}\) represents the actual cumulative ratio, and the area of shaded part \(F\) represents the Gini Index. If \(l_{2}\) got closer to \(l_{1}\), the area of \(F\), the Gini Index, will get smaller. In our method, given the sampling nodes number \(n\) (determined by the sampling rate) of one data collection round, the node sampling scheme can be denoted by a binary vector \(\mathbf{q}=(q_{1},...,q_{N})^{T}\), which is a column of \(\mathbf{Q}\) in Equation (2), where \(q_{i}=1\) representing the \(i\)th node is selected for sensing data and \(\sum_{i=1}^{N}q_{i}=n\). For each unselected node in the network, we denote the distance of the node to its nearest selected node by \(d_{j}\). Then we sort the distances and get an ascending sequence \(d_{1}\leq d_{2}\leq...\leq d_{N-n}\). From the sequence, we define the evenness measurement for the desired random sampling scheme by Gini Index in the following form:  
\[G_{1}(\mathbf{q})=1-\frac{1}{N-n}(2\sum_{j=1}^{N-n}d_{j}^{\prime}-1). \tag{16}\]  
where \(d_{j}^{\prime}=\frac{\sum_{k=1}^{j}d_{k}}{\sum_{i=1}^{N-n}d_{i}}\) is the cumulative ratio of distances. By minimization of \(G_{1}(\mathbf{q})\), we obtain the optimized \(\mathbf{q}\) representing the best spatial uniform node selection scheme. As the distances among nodes are unknown for a practical network, we use the spatial correlation weights in Equation (10) to replace the distances \(d_{j}\) and compute the \(G_{1}(q)\) in Equation (16). We give a concrete example. As shown in Figure 2. Figure 2b shows a simulated grid network with \(21\times 21\) node, and Figure 2c,d show two node sampling schemes in the simulated grid network, where the red nodes represent the nodes selected for sensing data. Figure 2e and Figure 2f show their Gini Index of Figure 2c and Figure 2d respectively. Apparently, the area of \(F\) in Figure 2e is much smaller than the one in Figure 2f as the distribution of the selected nodes in Figure 2c is more uniform than it in Figure 2d. So from the measurement of Gini Index, we could obtain the optimized nodes sampling scheme. **Figure 2.** Two nodes sampling schemes in simulative networks and their Gini Index. (**a**) A demonstration of Gini Index; (**b**) A grid simulated network; (**c**) A uniformly sampling scheme in simulated networks; (**d**) A non-uniform sampling scheme in simulated networks; (**e**) The Gini Index of the scheme in Figure 2c; (**f**) The Gini Index of the scheme in Figure 2d. Implementing the data collection round given the node sampling scheme \(\mathbf{q}\), the energy consumption in the data sensing and delivering will result in a new energy status for the network. We denote the remaining energy of each node by \(e_{i}\), \(i=1,...,N\). They also are sorted as an ascending sequence \(e_{1}\leq e_{2}\leq...\leq e_{N}\).