We are standing on the threshold of an era of widely distributed but limited sensors: low-power, low-speed devices that collect data about their environment, both physical and virtual. The multihop wireless sensor network (WSN) is a widely applicable model for these, and that is what the authors of this paper examine. It is natural to imagine that the data generated by such a network is sparse, due to factors such as spatial or temporal correlation, leading to many redundancies. Sparse data is the natural realm for compressed sensing [1,2], a new technique that promises good or even exact reconstruction of sparse signals from very small samples.

The authors apply ideas from compressed sensing to WSNs in an interesting way. After concise but complete introductions to both ideas, they turn to the key issue in any compressed sensing application: the choice of a good sensing matrix. Such matrices are often random in practice. Since a random sparse (0,1) matrix is an adjacency matrix for a bipartite expander graph (with high probability), such a matrix defines a set of designated sensors that each sum their inputs before reporting to a fusion center. The fusion center implements the compressed sensing recovery process to determine all of the sensor readings.

After considering communication cost, the authors compare this scheme to other compressed sensing schemes and generally obtain favorable results.

The implementation depends on a solution to the all-pairs shortest path problem, which is well known, so one can excuse the failure to mention it. Also, the paper does not explicitly address the space complexity of the algorithm, although the information to determine it is there. It seems to me that there is a time-space tradeoff for low-capacity sensors that should be addressed.

There are several broken and incomplete references, although it is easy to find what’s needed with an online search.