Voronoi Scoping in Sensor Networks


Henri Dubois-Ferrière


A driving scenario for sensor networks is environmental monitoring: nodes gather data and send it back to a sink (i.e., a basestation with an internet connection or persistent storage) via a multi-hop tree topology. In order to form the data-gathering tree, and in order to configure the sensor nodes, the sink periodically disseminates messages into the network. For scaling, robustness, and load-balancing reasons, it is desirable to introduce multiple sinks and have nodes send data to their closest sink (under a metric such as hop-count or energy cost) rather than all nodes sending to a unique sink. With multiple sinks, it becomes important to constrain dissemination of queries so that each sink does not flood the whole network.

Main contributions

In this work we propose Voronoi scoping, a distributed algorithm to constrain the dissemination of messages from different sinks. It has the property that a query originated by a given sink will be forwarded only to the nodes for which that sink is the closest sink (under the chosen metric). Thus each query is forwarded to the smallest possible number of nodes, and per-node dissemination overhead does not grow with network size or with number of sinks. The algorithm has a simple distributed implementation and requires only a few bytes of state at each node. Experiments over a network of 55 motes confirm the algorithm’s effectiveness.

Current and Future Research

This work focuses on the application of Voronoi scoping to sensor networks. Other applications are possible. As possible future work, we envision the application of this technique to multihop wireless networks where a subset of nodes serve as internet gateways, and each wishes to broadcast route advertisements to those non-gateway nodes which are closest to it.


Deborah Estrin (UCLA).


June 2003 – October 2003


Swiss National Competence Center in Research for Mobile Information and Communication Systems.

Major publications

H. Dubois-Ferrière and D. Estrin, Efficient and Practical Query Scoping in Sensor Networks, Technical Report, 2004.
[detailed record] [bibtex]