# Approximate Sensory Data Collection: A Survey
## 3 Compressive Sensing Based Approximate Data Collection Algorithms
### Centralized Algorithms for Generating Compression Bases  
This group of algorithms generate the bases of the subspace for compression in a central manner. The common advantage of these algorithms is that they guarantee that the bases are orthogonal with each other so that redundant information can be minimized after compression. The details are as follows.  
The work in [18] introduced a method by assuming that the sink has already received partial sensory data. Furthermore, the sampled data are assumed to be compressible and the optimal basis used for compression is known beforehand. In order to collect additional data, the algorithm first randomly samples some data from the network. Then, a vector \(p\) indicating the set of additional nodes that need to transmit their data is determined centrally according to the received data and the optimal compressing basis. \(p\) is then broadcasted in the network, and data are transmitted and aggregated from the nodes specified in \(p\) toward the sink. Obviously, the assumption of obtaining the optimal compressing basis without any knowledge on data distribution is too strong. Even if we can obtain the optimal compressing basis according to historical data, updating the basis incurs a huge amount of energy in WSNs. Furthermore, the delay of data collection is large since \(p\) needs to be determined iteratively, and a complicated computation needs to be carried out. Therefore, the algorithm is not suitable for large-scale WSNs with frequently varied data.  
The works in [19; 20] indicate that the \(K\)-restricted isometry property should be satisfied if we want to recover \(N\) sensory values from \(M\) compressed data in polynomial time, where \(N\) is the total number of sensory values, \(K\) denotes the sparsity of these values and \(M\) (\(M<N\)) can be determined by \(K\). In order to satisfy the above conditions, the work in [21] constructs a matrix to compress sensory data during transmission. A chain network is used as an example and it is proved that \([I\;\;R]\) is the matrix guaranteeing the \(K\)-restricted isometry property, where \(I\) is the \(M\times M\) unit matrix and \(R\) is an \(M\times(N-M)\) random matrix. This work is also extended to the spanning tree based networks.  
Another work considering the \(k\)-restricted isometry property for compressed sensing [22] intends to recover original sensory data efficiently. The adopted network is an energy harvesting WSN, where the sensors can gain energy from the environment, e.g., wind or solar energy. However, in order to guarantee the \(k\)-restricted isometry property, the compression size must be determined centrally. Meanwhile, many parameters such as sparsity of data and transmit probabilities must be known by the sink in advance, which is almost impossible for large-scale networks.  
The algorithm in [23] uses a function to denote the relationship between sensory data and a sensor node ID, where the base of the function is constructed through a Discrete Cosine Transform. It is assumed that the coefficient of the function is sparse according to the base, such that the compressed sensing technique can be used to compress these coefficients. However, this assumption is too strong for WSNs. Moreover, the accuracy for recovering the original data cannot be guaranteed. Furthermore, the considered topology in this work is not practical for real WSNs.