Cost-aware compressive sensing for networked sensing systems
Authors:
Open Access
- 13 April 2015
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 130-141
Abstract
Compressive Sensing is a technique that can help reduce the sampling rate of sensing tasks. In mobile crowdsensing applications or wireless sensor networks, the resource burden of collecting samples is often a major concern. Therefore, compressive sensing is a promising approach in such scenarios. An implicit assumption underlying compressive sensing -- both in theory and its applications -- is that every sample has the same cost: its goal is to simply reduce the number of samples while achieving a good recovery accuracy. In many networked sensing systems, however, the cost of obtaining a specific sample may depend highly on the location, time, condition of the device, and many other factors of the sample. In this paper, we study compressive sensing in situations where different samples have different costs, and we seek to find a good trade-off between minimizing the total sample cost and the resulting recovery accuracy. We design Cost-Aware Compressive Sensing (CACS), which incorporates the cost-diversity of samples into the compressive sensing framework, and we apply CACS in networked sensing systems. Technically, we use regularized column sum (RCS) as a predictive metric for recovery accuracy, and use this metric to design an optimization algorithm for finding a least cost randomized sampling scheme with provable recovery bounds. We also show how CACS can be applied in a distributed context. Using traffic monitoring and air pollution as concrete application examples, we evaluate CACS based on large-scale real-life traces. Our results show that CACS achieves significant cost savings, outperforming natural baselines (greedy and random sampling) by up to 4x.Keywords
Funding Information
- National Natural Science Foundation of China (61033001, 61361136003)
- National Basic Research Program of China (2011CBA00300, 2011CBA00301)
This publication has 29 references indexed in Scilit:
- Cost-aware compressive sensing for networked sensing systems2015
- Matrices With Small Coherence Using $p$-Ary Block CodesIEEE Transactions on Signal Processing, 2011
- Explicit constructions of RIP matrices and related problemsDuke Mathematical Journal, 2011
- Energy-Aware Sparse Approximation Technique (EAST) for Rechargeable Wireless Sensor NetworksLecture Notes in Computer Science, 2010
- CoSaMP: Iterative signal recovery from incomplete and inaccurate samplesApplied and Computational Harmonic Analysis, 2009
- Uniform Uncertainty Principle and Signal Recovery via Regularized Orthogonal Matching PursuitFoundations of Computational Mathematics, 2008
- Weighted Random Sampling2008
- Deterministic constructions of compressed sensing matricesJournal of Complexity, 2007
- Stable signal recovery from incomplete and inaccurate measurementsCommunications on Pure and Applied Mathematics, 2006
- Randomized rounding: A technique for provably good algorithms and algorithmic proofsCombinatorica, 1987