# Approximate Sensory Data Collection: A Survey
## 3 Compressive Sensing Based Approximate Data Collection Algorithms
### Hybrid Algorithms  
Some researchers proposed combining the compressive sensing based algorithms with other ones, such as the straightforward packet forward method without compression. The works in [33; 34; 35] proposed three hybrid algorithms in WSNs. In [33], the sensor nodes in the form of a spanning tree are grouped into two subsets, and only the ones that receive enough data apply a compressive sensing based method to compress data before transmitting them along the spanning tree towards the sink. In [34], the nodes are clustered based on the assumption that the distribution of nodes follows the Poisson point process. A compressive sensing based technique is applied at cluster-heads during the transmission. In [35], a packet forward strategy without compression is adopted during data collection. The aforementioned algorithms can reduce energy consumption to some extent. However, they all have many drawbacks. For example, the algorithm in [33] requires that each node needs to hold the random vectors for other nodes, resulting in storage waste. The algorithm in [34] consumes lots of energy to cluster the nodes and broadcast the locations of clusters. The algorithm in [35] requires each parent node to wait for all of its children's nodes' data before transmitting, which increases the delay of data collection. Furthermore, the energy consumption could still be large since some sensory data are not compressed at the beginning and the additional information, such as sensor ID, still needs to be transmitted during data collection. Finally, these algorithms lead to imbalanced energy consumptions among the nodes in a network because the computation and transmission costs of some nodes are much larger than those of the other nodes. The work in [36] studied how to combine the compressive sensing based technique with the principle component analysis technique, and proposed a novel data collection framework. It is assumed that sensory data can be converted to an \(L\)-sparse vector by the principle component analysis;thus, it only needs to sample data with probability \(L/N\) during data collection, where \(N\) is the size of the network and the compressive sensing based technique is used to forward data. Since the sparsity of sensory data varies, the authors also provided a method for adjusting the sampling probability as follows. First, since all sensory data from a network can be estimated by the compressed bases, the relative difference between the real collected values and their estimations can be calculated. If such a relative difference is larger than a given bound, the sampling probability is enlarged \(C_{1}\) times; otherwise, it decreases \(C_{2}/N\), where \(C_{1}\) and \(C_{2}\) are constants. The above data collection framework takes the advantages of both the compressive sensing based techniques and the principle component analysis techniques. However, it still has the following drawbacks. First, the randomly sampled data cannot guarantee to recover the original data even if the data are \(L\)-sparse. For example, if all the samples fall in one cluster, the data of the other clusters cannot be acquired and recovered. Second, the principle component analysis is based on historical data, which may be invalid at the current time when the sensory values vary frequently. Third, to estimate relative errors, the matrix used by the compressed sensing technique also needs to be transmitted in the network, resulting in more energy consumption. Fourth, the principle component analysis, the relative error computation and the sampling probability estimation are implemented centrally, which is not suitable for WSNs. Fifth, the sampling probability needs to be updated and broadcasted in every time slot, which increases energy consumption. Finally, the theoretical error bound of the above method is not provided, and the information loss rate cannot meet an arbitrary precision requirement. In [37], the algorithms integrating compressive sensing and clustering were proposed based on block diagonal matrices.