Abstract
Large-scale dense sensor networks require mechanisms to extract topology information that can be used for various aspects of sensor network management. Many network properties can be inferred from a relatively low-resolution representation of topology. Different topology resolutions suffice for different management applications to perform at a desired level. In these cases, it is an overkill to retrieve the entire topology of large-scale dense networks particularly because sensor nodes are energy constrained. In this paper, we describe a distributed parameterized algorithm for Sensor Topology Retrieval at Multiple Resolutions (STREAM), which makes a tradeoff between topology details and resources expended. The algorithm retrieves network state at multiple resolutions at proportionate communication cost by adaptive spatial sampling. 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 to approximate actual network properties.