A Compressibility-Based Clustering Algorithm for Hierarchical Compressive Data Gathering

Data gathering in wireless sensor networks (WSNs) is one of the major sources for power consumption. Compression is often employed to reduce the number of packet transmissions required for data gathering. However, conventional data compression techniques can introduce heavy in-node computation, and thus, the use of compressive sensing (CS) for WSN data gathering has recently attracted growing attention. Among existing CS-based data gathering approaches, hierarchical compressive data gathering (HCDG) methods currently offer the most transmission-efficient architectures. When employing HCDG, clustering algorithms can affect the number of data transmissions. Most existing HCDG works use the random clustering (RC) method as a clustering algorithm, which can produce significant number of transmissions in some cases. In this paper, we present a compressibility-based clustering algorithm (CBCA) for HCDG. In CBCA, the network topology is first converted into a logical chain, similar to the idea proposed in PEGASIS [1], and then the spatial correlation of the cluster nodes' readings are employed for CS. We show that CBCA requires significantly less data transmission than the RC method with a little recovery accuracy loss. We also identify optimal parameters of CBCA via mathematical analysis and validate them by simulation. Finally, we used water level data collected from a real-world flood inundation monitoring system to drive our simulation experiments and showed the effectiveness of CBCA.