# Data Gathering Techniques in WSN: A Cross-Layer View
## 3 Compressed Sensing
Specifically, CSF finds a function that maps the sensors' identifiers and their readings, which can be expressed in a very sparse way, and only communicates this function to the sink. After the sink recovers the function, it can recover all the \(N\) sensor readings. [PERSON] et al. [64] show that the CSF approach can provide good recovery accuracy (better than the CDG scheme suggested by [61]) while substantially reducing the message overhead (mainly in tree-structured networks). [PERSON] et al. [65] present a general CS framework for WSNs and IoT and show how the proposed framework can be utilized to reconstruct the compressible information. The suggested framework comprises three phases: (i) information sensing to detect and compressively sample event signals; (ii) compressed sampling, in which the system samples information traversing the networks; and (iii) reconstruction algorithms, in which the system accurately reconstructs the original signal from the compressed samples. Different studies tackle the sampling issue and suggest different approaches to reduce the number of reports sent such that only a subset of the sensors sense the object or phenomenon at a time. Several studies explore how sensed data is conveyed to the sink with the insight that the compression is at least attained along the path to the sink, and is therefore affected by it. For example, [PERSON] et al. [66] show that a random-walk-based sampling, rather than the conventional uniform-sampling-based CS for function recovery, can be used for phenomena awareness either at a sink or at other sensors without a sink, with minimal additional sampling. As the distribution of the samples has a significant effect on the recovery, Ref. [66] suggests an upper bound for the probability of successful recovery with a given error percentage. The derived bound provides an approximate number of samples required to recover a function under a selected basis and a sampling scheme. [PERSON] et al. [67] further argue that random walk provides a more practical approach for the data-gathering application in WSNs and explores the sparsity of collecting non-uniform measurements while sampling along multiple random paths. The paper suggests that the \(M\times N\) measurement matrix will be characterized by \(M\) independent random walks. Specifically, each of the \(M\) matrix rows corresponds to the set of vertices visited by the respective random walk. The paper analyzes the required number of random walks (\(M\)) and their corresponding lengths (how many entries on each row are non-zero) under the proposed random walk algorithm. [PERSON] et al. [68] suggest a cluster-based data-gathering mechanism, in which the terrain is divided into cells; in each cell, a node is randomly selected as the cell head, which collects the data from the cell members and forwards it to the sink. [PERSON] et al. [68] suggest two forwarding mechanisms, one relying on centrally defined tree-based forwarding, and another that is a gossip-based approach. The projection process is similar to [PERSON] et al. [61, 62], being based on random coefficients. Another clustering-based hierarchical data aggregation protocol that relies on CS, termed HDACS, is suggested by [PERSON] et al. [69]. Specifically, HDACS constructs a multilevel hierarchical structure and adaptively sets multiple compression thresholds based on cluster sizes at different levels of the data aggregation tree to optimize the amount of transmitted data. The encoding procedure is adapted from [62], where each cluster-head recovers (decodes) all received messages from its descendants (retrieves the original data) before compressing and sending it to its parent cluster-head. Motivated by reducing power consumption, [PERSON] and [PERSON] [70] also suggest a compressibility-based clustering algorithm for hierarchical compressive data gathering. In this study, the network is decomposed into a logical chain, and sensor nodes are grouped based on the compressibility of their readings instead of by a random clustering approach.