Efficient Path Reconstruction for Wireless Sensor Network

Abstract

Recent wireless sensor networks (WSNs) are becoming increasingly complex with the growing network scale and the dynamic nature of wireless communications. Many measurement and diagnostic approaches depend on per-packet routing paths for accurate and fine-grained analysis of the complex network behaviors. In this paper, we propose a Path, a novel path inference approach to reconstructing the per-packet routing paths in dynamic and large-scale networks. The basic idea of the Path is to exploit high path similarity to iteratively infer long paths from short ones. The Path starts with an initial known set of paths and performs path inference iteratively.
In order to further improve the inference capability as well as the execution efficiency, it includes a fast bootstrapping algorithm to reconstruct the initial set of paths. We also implement the Path and evaluate its performance using traces from large-scale WSN deployments as well as extensive simulations. Results show that it achieves much higher reconstruction ratios under different network settings compared to other state-of- the-art approaches.