Routing topology inference for wireless sensor networks

Yao Liang, Rui Liu
Appears in: 
CCR April 2013

We consider an important problem of wireless sensor network (WSN) routing topology inference/tomography from indirect measurements observed at the data sink. Previous studies on WSN topology tomography are restricted to static routing tree estimation, which is unrealistic in real-world WSN time-varying routing due to wireless channel dynamics. We study general WSN routing topology inference where routing structure is dynamic. We formulate the problem as a novel compressed sensing problem. We then devise a suite of decoding algorithms to recover the routing path of each aggregated measurement. Our approach is tested and evaluated though simulations with favorable results. WSN routing topology inference capability is essential for routing improvement, topology control, anomaly detection and load balance to enable effective network management and optimized operations of deployed WSNs.

Public Review By: 
Augustin Chaintreau

If large scale wireless ad-hoc networks ever get deployed, and they use various dynamic routing schemes to operate, what sort of tools would be needed to infer topology and potentially monitor performance using only information at the sink? And what would this ever have to do with compressed sensing? Connecting these two questions, and providing a first step towards an answer to both is what this paper is all about. By considering an hypothetical network of sensors in which routing is time varying and exhibits various wireless channel dynamics, this paper explains why previous tomography techniques might be restrictive, but also that the problem can be formulated as a variant of compressive sensing. The authors provide in particular two heuristics that exploit sparsity and properties of labels of paths to show one way to approach this problem. Many questions remain after these first steps are shown, as mentioned by reviewers: Is compressive sensing truly necessary to improve on a lower bound? Since labeling introduce some overhead, in which case would this technique be superior? One could in fact use a more naive approach (such as Collection Tree protocol) where information is simply encoded and node signed the packed they forward. While in some cases a compressive sensing appears to do better, would these cases be in anyway practical. Can this technique be used for more than tree inference (by estimating metric such as delay and loss rate)? This paper offers an interesting connection and an original viewpoint on the general use of inference techniques, that have become important in networking, we wanted to share this idea with the community and open the room for more research in this domain. We hope you will enjoy reading the paper.