Exact distributed Voronoi cell computation in sensor networks

ABSTRACT

Distributed computation of Voronoi cells in sensor networks, i.e. computing the locus of points in a sensor field closest to a given sensor, is a key building block that supports a number of applications in both the data and control planes. For example, knowledge of Voronoi cells facilitates efficient methods for computing the piece-wise approximation of a field, whereby each sensor acts as a representative for the set of points in its Voronoi cell; awareness of Voronoi boundaries and Voronoi neighbors is also useful in load balancing and energy conservation. The methods currently advocated for distributed Voronoi computation in sensor networks are heuristic approximations that can introduce significant inaccuracies that are difficult to rigorously quantify; we demonstrate that these methods may err by a factor of 5 or more in some circumstances. We present and prove an exact method which eliminates these inaccuracies, at the cost of increased messaging overhead, but without necessitating contact with the entire network. To our knowledge, this is the first distributed algorithm that computes accurate Voronoi cells without requiring all-to-all communication. We implement it as a TinyOS module and quantitatively analyze its performance.

References

1. D. Aguayo, J. Bicket, S. Biswas, G. Judd, and R. Morris. Link-level measurements from an 802.11b mesh network. In Proc. of SIGCOMM, Aug. 2004.
2. B. A. Bash, J. W. Byers, and J. Considine. Uniform random sampling in sensor networks. In Proc. of DMSN, Aug. 2004.
3. J. Byers, J. Considine, and M. Mitzenmacher. Geometric generalizations of the power of two choices. In Proc. of the 16th ACM Symp. on Parallel Algorithms and Architectures, June 2004.
4. B. Carbunar, A. Grama, and J. Vitek. Distributed and dynamic voronoi overlays for coverage detection and distributed hash tables in ad-hoc networks. In Proc. of IEEE International Conference on Parallel and Distributed Systems (ICPADS), July 2004.
5. W.-P. Chen, J. C. Hou, and L. Sha. Dynamic clustering for acoustic target tracking in wireless sensor networks. IEEE Trans. on Mobile Computing, 3(3):258--271, 2004.
6. T. Clausen and P. Jacquet. Optimized Link State Routing Protocol (OLSR), October 2003. IETF RFC 3626.
7. Crossbow Corporation. Stargate Gateway (SPB400). Available at: http://www.xbow.com/Support/Support pdf files/Stargate Manual.pdf, 2004.
8. M. de Berg, O. Schwarzkopf, M. van Kreveld, and M. Overmars. Computational Geometry: Algorithms and Applications. Springer-Verlag, 2nd edition, 2000.
9. M. Demirbas and H. Ferhatosmanoglu. Peer-to-peer spatial queries in sensor networks. In Proc. of 3rd IEEE International Conference on Peer-to-Peer Computing, Sept. 2003.
10. P. Desnoyers, D. Ganesan, and P. Shenoy. TSAR: A Two Tier Storage Architecture Using Interval Skip Graphs. In Third ACM Conference on Embedded Networked Sensor Systems (SenSys)., November 2005.
11. D. Ganesan, S. Ratnasamy, H. Wang, and D. Estrin. Coping with irregular spatio-temporal sampling in sensor networks. In Proc. of HotNets-II, November 2003.
12. R. H. Guting. An introduction to spatial database systems. VLDB Journal, 3(4):357--399, 1994.
13. C.-C. Han, S. Ganeriwal, A. Boulis, and M. Srivastava. Going beyond nodal aggregates: Spatial average of a physical process in sensor networks. Poster in ACM SenSys, Nov. 2003.
14. B. Harrington and Y. Huang. In-network surface simplification for sensor fields. In GIS'05: Proceedings of the 13th annual ACM international workshop on Geographic information systems, pages 41--50, New York, NY, USA, 2005. ACM Press.
15. J. Hill and D. Culler. Mica: A Wireless Platform for Deeply Embedded Networks. IEEE Micro, 22(6):12--24, Nov/Dec 2002.
16. B. Karp and H. Kung. GPSR: Greedy perimeter stateless routing for wireless networks. In ACM MobiCom, Aug. 2000.
17. Y.-J. Kim, R. Govindan, B. Karp, and S. Shenker. Geographic routing made practical. In USENIX NSDI, May 2005.
18. P. Levis, N. Lee, M. Welsh, and D. Culler. TOSSIM: Accurate and scalable simulation of entire TinyOS applications. In ACM SenSys, 2004.
19. Moteiv Corporation. TMote Sky Datasheet, 2005.
20. J. A. Peterson. SENS: A simple, extensible sensor network simulator for exploring approximate aggregation techniques. Master's thesis, Boston University, 2005.
21. N. B. Priyantha, A. Chakraborty, and H. Balakrishnan. The cricket location-support system. In MobiCom '00: Proceedings of the 6th annual international conference on Mobile computing and networking, pages 32--43, New York, NY, USA, 2000. ACM Press.
22. A. Rao, S. Ratnasamy, C. Papadimitriou, S. Shenker, and I. Stoica. Geographic routing without location information. In ACM MobiCom, Sept. 2003.
23. S. Ratnasamy, B. Karp, S. Shenker, D. Estrin, R. Govindan, L. Yin, and F. Yu. Data-centric storage in sensornets with GHT, a geographic hash table. Mobile Networks and Applications, 8(4):427--442, 2003.
24. P. Samar, M. R. Pearlman, and Z. J. Haas. The handbook of ad hoc wireless networks, chapter Hybrid routing: the pursuit of an adaptable and scalable routing framework for ad hoc networks, pages 245--262. CRC Press, Inc., Boca Raton, FL, USA, 2003.
25. M. Sharifzadeh and C. Shahabi. Supporting spatial aggregation in sensor network databases. In Proc. of 12th International Symposium of ACM GIS, Nov. 2004.
26. I. Stanoi, M. Riedwald, D. Agrawal, and A. E. Abbadi. Discovery of in uence sets in frequently updated databases. In Proc. of 27th VLDB Conference, 2001.
27. USC Embedded Networks Laboratory. CLDP+GFR ver-0.2 for the motes. Available at: http://enl.usc.edu/software.html.
28. Z. Zhou, S. Das, and H. Gupta. Variable radii connected sensor cover in sensor networks. In Proc. of IEEE SECON, 2004.

Index Terms

• Information systems

  • Data management systems

    • Data structures

  • Information storage systems

    • Record storage systems

  • World Wide Web

    • Web applications

      • Internet communications tools

• Software and its engineering

  • Software notations and tools

    • General programming languages

      • Language features

        • Data types and structures

• Theory of computation

  • Design and analysis of algorithms

    • Data structures design and analysis

  • Theory and algorithms for application domains

    • Database theory

      • Data structures and algorithms for data management