Abstract
Large-scale sensor networks require mechanisms to extract topology information that can be used for various aspects of sensor network management. It is critical for any topology discovery algorithm in sensor networks to adhere to the resource constraints of bandwidth and energy. In this paper, we describe a distributed parameterized algorithm for Sensor Topology Extraction at Multiple Resolutions (STEM), which makes a tradeoff between topology details and resource expended. The algorithm retrieves network state at multiple resolutions at a proportionate communication cost. We also define various classes of topology queries and show how the parameters in the algorithm can be used to support queries specific to sensor networks. We show that the topology determined, albeit at a low resolution, is sufficient for approximating actual network properties. Finally we show how STEM can be used for generalpurpose multi-resolution information retrieval in sensor networks.