# Approximate Sensory Data Collection: A Survey
## 3 Compressive Sensing Based Approximate Data Collection Algorithms
### Distributed Algorithms for Generating Compression Bases  
The aforementioned centralized algorithms consume much energy since all the bases need to be broadcasted in the network. This motivates the design of distributed algorithms. A typical work is proposed in [24], where the matrix for compressing sensory data during collection is constructed in a distributed manner. The main steps are as follows. First, each node generates random vectors according to its ID and the random seed is broadcasted by the sink. Second, for each sensor, a new data vector is obtained by the multiplication of its sensory values and the random vector. Finally, the sink computes the random vectors based on the random seed and sensors' IDs to derive a random matrix, and the sensory data can be recovered according to the received data vectors and the random matrix. The similar idea is adopted in [25] except that original data is recovered by linear programming. The authors in [26] extended the idea by proposing their own routing scheme. They also analyzed the capacity and delay for both single-sink and multi-sink networks under the proposed routing scheme. Another related work for vehicle networks is proposed in [27]. It is assumed that the sampled data are \(k\)-sparse, where \(k\) is obtained by analyzing historical data. According to \(k\), the number of the seed vehicles, \(m\), is calculated centrally, where \(m\) determines the amount of compressed data that the sink will receive. During in-network transmission, the routing tree having \(m\) seed vehicles as leaf nodes is used. First, a new data collection process is initiated by each seed vehicle, and the distributed compressed sensing based algorithm, such as that shown in [24], is adopted to deal with such a process. After that, the sink will receive \(m\) compressed data. The work in [28] proposed a new compressed sensing based data collection algorithm in order to detect outlier readings and broken links. Since the sparse property of outlier readings is different from that of the normal ones, different identity matrices for compression are used to discover outliers and broken links. However, the work neither provides any theoretical bound to guarantee detection accuracy nor clearly describes the compression rate. Most of the existing compressive sensing based algorithms assume that sensory data have a known constant sparsity, which is not practical in WSNs. Therefore, the authors in [29] proposed an adaptive compressed data collection scheme in WSNs to deal with the situation in which the sparsity of sensory data varies with time and space. However, the computation at each node is complicated, which is also a challenge for sensor nodes since their computation ability and energy are limited. Although the above algorithms save much energy since the compression bases are generated in a distributed manner and need not be broadcasted in a network, they all have the following problems. First, they do not consider the spatial-correlation so that the compression rate is not small enough by using a random matrix. Second, they assume that sensory data can be transformed into a sparse data matrix, which may not be practical for WSNs. Even if this is possible, its sparsity is hard to be obtained by the sink especially for large-scale WSNs. Third, since the random vectors are generated individually by the nodes, they cannot be orthogonal with each other, resulting in redundant information in the compressed data. Fourth, the information loss rate cannot meet an arbitrary user-specified precision requirement, so the dimension of the random matrix cannot be automatically adjusted accordingly. Another compressive sensing based approximate data collection algorithm was proposed by [30]. The algorithm firstly decides the number of the required measurements, denoted by \(M\), according to the sparsity of the sensory data using the compressive sensing technique. Then, \(M\) random walks are initiated to route and aggregate the required measurements to the sink node for further recovery.