Connected sensor cover: self-organization of sensor networks for efficient query execution

ABSTRACT

Spatial query execution is an essential functionality of a sensor network, where a query gathers sensor data within a specific geographic region. Redundancy within a sensor network can be exploited to reduce the communication cost incurred in execution of such queries. Any reduction in communication cost would result in an efficient use of the battery energy, which is very limited in sensors. One approach to reduce the communication cost of a query is to self-organize the network, in response to a query, into a topology that involves only a small subset of the sensors sufficient to process the query. The query is then executed using only the sensors in the constructed topology.In this article, we design and analyze algorithms for such self-organization of a sensor network to reduce energy consumption. In particular, we develop the notion of a connected sensor cover and design a centralized approximation algorithm that constructs a topology involving a near-optimal connected sensor cover. We prove that the size of the constructed topology is within an log n factor of the optimal size, where n is the network size. We also develop a distributed self-organization version of our algorithm, and propose several optimizations to reduce the communication overhead of the algorithm. Finally, we evaluate the distributed algorithm using simulations and show that our approach results in significant communication cost reduction.

REFERENCES

• 1: Khaled M. Alzoubi , Peng-Jun Wan , Ophir Frieder, Message-optimal connected dominating sets in mobile ad hoc networks, Proceedings of the 3rd ACM international symposium on Mobile ad hoc networking & computing, June 09-11, 2002, Lausanne, Switzerland [doi>10.1145/513800.513820]
• 2: B. Badrinath, M. Srivastava, K. Mills, J. Sholtz, and K. Sollins, editors.Special Issue on Smart Spaces and Environments, IEEE Personal Communications 2000.
• 3: Piotr Berman , Viswanathan Ramaiyer, Improved approximations for the Steiner tree problem, Journal of Algorithms, v.17 n.3, p.381-408, Nov. 1994
• 4: Philippe Bonnet , Johannes Gehrke , Praveen Seshadri, Towards Sensor Database Systems, Proceedings of the Second International Conference on Mobile Data Management, p.3-14, January 08-10, 2001
• 5: H.Bonnimann and M.Goodrich. Almost optimal set covers in finite vc-dimension.Discrete Computational Geometry 14,1995.
• 6: A. Cerpa and D. Estrin. Ascent: Adaptive self-configuring sensor networks topologies.In Proc. of the Conf. on Computer Communications (INFOCOM),2002.
• 7: Yuanzhu Peter Chen , Arthur L. Liestman, Approximating minimum size weakly-connected dominating sets for clustering mobile ad hoc networks, Proceedings of the 3rd ACM international symposium on Mobile ad hoc networking & computing, June 09-11, 2002, Lausanne, Switzerland [doi>10.1145/513800.513821]
• 8: Thomas H. Cormen , Clifford Stein , Ronald L. Rivest , Charles E. Leiserson, Introduction to Algorithms, McGraw-Hill Higher Education, 2001
• 9: Bevan Das , Raghupathy Sivakumar , Vaduvur Bharghavan, Routing in Ad Hoc Networks Using a Spine, Proceedings of the 6th International Conference on Computer Communications and Networks, p.34, September 22-25, 1997
• 10: Mark de Berg , Marc van Kreveld , Mark Overmars , Otfried Schwarzkopf, Computational geometry: algorithms and applications, Springer-Verlag New York, Inc., Secaucus, NJ, 1997
• 11: B. Deb, S. Bhatnagar, and B. Nath. Multiresolution state retrieval in sensor networks. In Proceedings of International Workshop on Sensor Network Protocols and Applications (SNPA), 2003.
• 12: Deborah Estrin , Ramesh Govindan , John Heidemann, Embedding the Internet: introduction, Communications of the ACM, v.43 n.5, p.38-41, May 2000 [doi>10.1145/332833.332836]
• 13: R. Govindan, J. Hellerstein, W. Hong, S. Madden, M. Franklin, and S. Shenker. The sensor network as a database. Technical report, University of Southern California, Computer Science Department, 2002.
• 14: S. Guha and S. Khuller. Approximation algorithms for connected dominating sets. Algorithmica 20(4), 1998.
• 15: Wendi Rabiner Heinzelman , Anantha Chandrakasan , Hari Balakrishnan, Energy-Efficient Communication Protocol for Wireless Microsensor Networks, Proceedings of the 33rd Hawaii International Conference on System Sciences-Volume 8, p.8020, January 04-07, 2000
• 16: V. S. Anil Kumar , Sunil Arya , H. Ramesh, Hardness of Set Cover with Intersection 1, Proceedings of the 27th International Colloquium on Automata, Languages and Programming, p.624-635, July 09-15, 2000
• 17: V. S. Anil Kumar , H. Ramesh, Covering rectilinear polygons with axis-parallel rectangles, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.445-454, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301369]
• 18: A. Laouiti, A. Qayyum, and L. Viennot. Multipoint relaying: An effcient technique for flooding in mobile wireless networks. In Proc.of the Hawaii Intl.Conf. on System Sciences (HICSS), 2002.
• 19: K. Lieska, E. Laitinen, and J. Lahteenmaki. Radio coverage optimization with genetic algorithms. In Proc. of IEEE Int. Symp. on Personal, Indoor, and Mobile Radio Communications (PIMRC), 1998.
• 20: M. Marengoni, B. Draper, A. Hanson, and R. Sitaraman. System to place observers on a polyhedral terrain in polynomial time. Image and Visual Computing, 1996.
• 21: S. Meguerdihian, F. Koushanfar, M. Potkonjak, and M. Srivastava. Coverage problems in wireless ad-hoc sensor networks. In Proc.of the Conf. on Computer Communications (INFOCOM), 2001.
• 22: Seapahn Meguerdichian , Farinaz Koushanfar , Gang Qu , Miodrag Potkonjak, Exposure in wireless Ad-Hoc sensor networks, Proceedings of the 7th annual international conference on Mobile computing and networking, p.139-150, July 2001, Rome, Italy [doi>10.1145/381677.381691]
• 23: G. Pottie and W. Kaiser. Wireless sensor networks. Communications of the ACM 43, 2002.
• 24: S. Shakkottai, R. Srikant, and N. Shroff. Unreliable sensor grids: Coverage, connectivity and diameter. In Proceedings of INFOCOM (to appear), 2003.
• 25: S. Slijepcevi and M. Potkonjak. Power efficient organization of wireless sensor networks. In Proc. of IEEE Intl. Conf. on Communications (ICC), 2001.
• 26: J. Wu and H. Li. A dominating-set-based routing scheme in ad hoc wireless networks. Telecommunication Systems Journal 3, 2001.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems
          Subjects: Distributed applications

General Terms:
Algorithms, Performance

Keywords:
connected sensor cover, query optimization, sensor connectivity, sensor coverage, sensor networks