article

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

Authors:

Himanshu Gupta,

Quinyi GuAuthors Info & Claims

IEEE/ACM Transactions on Networking (TON), Volume 14, Issue 1

Pages 55 - 67

https://doi.org/10.1109/TNET.2005.863478

Published: 01 February 2006 Publication History

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. The self-organization technique is beneficial for queries that run sufficiently long to amortize the communication cost incurred in self-organization.In this paper, we design and analyze algorithms for suchself-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 O(log n) factor of the optimal size, where n is the network size. We develop a distributed self-organization version of the approximation algorithm, and propose several optimizations to reduce the communication overhead of the algorithm. We also design another distributed algorithm based on node priorities that has a further lower communication overhead, but does not provide any guarantee on the size of the connected sensor cover constructed. Finally, we evaluate the distributed algorithms using simulations and show that our approaches results in significant communication cost reductions.

References

[1]

{1} Commun. ACM, Special Issue on Embedding the Internet, vol. 43, no. 5, 2000. D. Estrin, R. Govindan, and J. Heidemann, Eds.]]

[2]

{2} IEEE Pers. Commun., Special Issue on Smart Spaces and Environments, vol. 7, no. 5, Oct. 2000. B. Badrinath, M. Srivastava, K. Mills, J. Scholtz, and K. Sollins, Eds.]]

[3]

{3} P. Bonnet, J. Gehrke, and P. Seshadri, "Toward sensor database systems," in Proc. 2nd Int. Conf. Mobile Data Management, Hong Kong, 2001, pp. 3-14.]]

[4]

{4} R. Govindan, J. Hellerstein, W. Hong, S. Madden, M. Franklin, and S. Shenker, "The sensor network as a database," Comput. Sci. Dept., Univ. Southern California, Los Angeles, Tech. Rep., 2002.]]

[5]

{5} G. Pottie and W. Kaiser, "Wireless integrated sensor networks," Commun. ACM, vol. 43, no. 5, pp. 51-58, May 2000.]]

[6]

{6} V. S. A. Kumar, S. Arya, and H. Ramesh, "Hardness of set cover with intersection 1," Automata, Languages and Programming, pp. 624-635, 2000.]]

[7]

{7} S. Slijepcevic and M. Potkonjak, "Power efficient organization of wireless sensor networks," in Proc. IEEE Int. Conf. Commun. (ICC), 2001, pp. 472-476.]]

[8]

{8} S. Shakkottai, R. Srikant, and N. Shroff, "Unreliable sensor grids: coverage, connectivity and diameter," in Proc. IEEE INFOCOM, 2003, pp. 1073-1083.]]

[9]

{9} S. Meguerdichian, F. Koushanfar, G. Qu, and M. Potkonjak, "Exposure in wireless ad hoc sensor networks," in Proc. Int. Conf. Mobile Computing and Networking (MobiCom), 2001, pp. 139-150.]]

[10]

{10} H. Gupta, S. Das, and Q. Gu, "Connected sensor cover: self-organization of sensor networks for efficient querying," in Proc. Int. Symp. Mobile Ad Hoc Networking and Computing (MobiHoc), 2003, pp. 189-200.]]

[11]

{11} P. Berman and V. Ramaiyer, "Improved approximation algorithms for the Steiner tree problem," J. Algorithms, vol. 17, pp. 381-408, 1994.]]

[12]

{12} V. S. Anil Kumar and H. Ramesh, "Covering rectilinear polygons with axis-parallel rectangles," in Proc. ACM-SIAM Symp. Theory of Computing , 1999, pp. 445-454.]]

[13]

{13} H. Bronnimann and M. Goodrich, "Almost optimal set covers in finite VC-dimension," Discrete Comput. Geom., vol. 14, pp. 263-279, 1995.]]

[14]

{14} Z. Zhou, S. Das, and H. Gupta, "Variable radii connected sensor cover in sensor networks," in Proc. IEEE Int. Conf. Sensor and Ad Hoc Communications and Networks (SECON), 2004, pp. 387-396.]]

[15]

{15} J. Wu and F. Dai, "Broadcasting in ad hoc networks based on self-pruning," in Proc. IEEE INFOCOM, 2003, pp. 2240-2250.]]

[16]

{16} Z. Abrams, A. Goel, and S. Plotkin, "Set k-cover algorithms for energy efficient monitoring in wireless sensor networks," in Proc. Int. Workshop on Information Processing in Sensor Networks (IPSN), 2004, pp. 424-432.]]

[17]

{17} F. Ye, G. Zhong, J. Cheng, S. Lu, and L. Zhang, "PEAS: a robust energy conserving protocol for long-lived sensor networks," in Proc. Int. Conf. Distributed Computing Systems, 2003, pp. 28-37.]]

[18]

{18} K. Chakrabarty, S. S. Iyengar, H. Qi, and E. Cho, "Grid coverage for surveillance and target location in distributed sensor networks," IEEE Trans. Comput., vol. 51, no. 12, pp. 1448-1453, Dec. 2002.]]

[19]

{19} C.-F. Huang and Y.-C. Tseng, "The coverage problem in a wireless sensor network," in Proc. ACM Int. Conf. Wireless Sensor Networks and Applications (WSNA), 2003, pp. 115-121.]]

[20]

{20} Z. Zhou, S. Das, and H. Gupta, "Connected k-coverage problem in sensor networks," in Proc. Int. Conf. Computer Communications and Networks (ICCCN), 2004, pp. 373-378.]]

[21]

{21} S. Meguerdichian, F. Koushanfar, M. Potkonjak, and M. Srivastava, "Coverage problems in wireless ad hoc sensor networks," in Proc. IEEE INFOCOM, 2001, pp. 1380-1387.]]

[22]

{22} S. Guha and S. Khuller, "Approximation algorithms for connected dominating sets," Algorithmica, vol. 20, no. 4, pp. 374-387, 1998.]]

[23]

{23} B. Das, R. Sivakumar, and V. Bhargavan, "Routing in ad hoc networks using a spine," in Proc. Int. Conf. Computer Communications and Networks (ICCCN), 1997, pp. 34-39.]]

[24]

{24} A. Laouiti, A. Qayyum, and L. Viennot, "Multipoint relaying: an efficient technique for flooding in mobile wireless networks," in Proc. Hawaii Int. Conf. System Sciences, 2002.]]

[25]

{25} J. Wu and H. Li, "A dominating-set-based routing scheme in ad hoc wireless networks," Telecommun. Syst. J., vol. 3, 2001.]]

[26]

{26} K. M. Alzoubi, P.-J. Wan, and O. Frieder, "Message-optimal connected dominating sets in mobile ad hoc networks," in Proc. ACM Int. Symp. Mobile Ad Hoc Networking and Computing (MobiHoc), 2002, pp. 157-164.]]

[27]

{27} Y. Chen and A. Liestman, "Approximating minimum size weakly-connected dominating sets for clustering mobile ad hoc networks," in Proc. Int. Symp. Mobile Ad Hoc Networking and Computing (MobiHoc), 2002, pp. 165-172.]]

[28]

{28} Y. Xu, J. S. Heidemann, and D. Estrin, "Geography-informed energy conservation for ad hoc routing," in Proc. Int. Conf. Mobile Computing and Networking (MobiCom), 2001, pp. 70-84.]]

[29]

{29} B. Chen, K. Jamieson, H. Balakrishnan, and R. Morris, "Span: an energy-efficient coordination algorithm for topology maintenance in ad hoc wireless networks," in Proc. Int. Conf. Mobile Computing and Networking (MobiCom), 2001, pp. 85-96.]]

[30]

{30} A. Cerpa and D. Estrin, "Ascent: adaptive self-configuring sensor networks topologies," in Proc. IEEE INFOCOM, 2002, pp. 1278-1287.]]

[31]

{31} B. Deb, S. Bhatnagar, and B. Nath, "Multi-resolution state retrieval in sensor networks," in Proc. IEEE Int. Workshop on Sensor Network Protocols and Applications, 2003, pp. 19-29.]]

[32]

{32} M. Marengoni, B. Draper, A. Hanson, and R. Sitaraman, "A system to place observers on a polyhedral terrain in polynomial time," Image Vis. Comput., vol. 18, pp. 773-780, 2000.]]

[33]

{33} M. de Berg, M. van Kreveld, M. Overmans, and O. Schwarzkopf, Computational Geometry: Algorithms and Applications. Berlin, Germany: Springer-Verlag, 2000.]]

Cited By

Ammari H(2023)A Computational Geometry-based Approach for Planar k-Coverage in Wireless Sensor NetworksACM Transactions on Sensor Networks10.1145/356427219:2(1-42)Online publication date: 3-Feb-2023
https://dl.acm.org/doi/10.1145/3564272
Liu XChen XYang QZhang SGuo SLuo JLi K(2023)More Than Scheduling: Novel and Efficient Coordination Algorithms for Multiple Readers in RFID SystemsIEEE Transactions on Mobile Computing10.1109/TMC.2022.316784322:9(5375-5388)Online publication date: 1-Sep-2023
https://dl.acm.org/doi/10.1109/TMC.2022.3167843
Karaliopoulos MKoutsopoulos IBoukerche ASun P(2022)Empowering Synergies of Communities with Service Providers for the Bottom-up Deployment of Network InfrastructuresProceedings of the 18th ACM International Symposium on QoS and Security for Wireless and Mobile Networks10.1145/3551661.3561368(105-114)Online publication date: 24-Oct-2022
https://dl.acm.org/doi/10.1145/3551661.3561368
Show More Cited By

Index Terms

Recommendations

Connected sensor cover: self-organization of sensor networks for efficient query execution
MobiHoc '03: Proceedings of the 4th ACM international symposium on Mobile ad hoc networking & computing

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 ...
Connected sensor cover for area information coverage in wireless sensor networks

Coverage is an important issue in wireless sensor networks (WSNs) and is often used to measure how well a sensor field is monitored by the deployed sensors. If the area covered by a sensor can also be covered by some other sensors, this sensor can go ...
Sensor coverage in wireless ad hoc sensor networks

We present our solutions to the general sensor coverage problem in wireless ad hoc sensor networks, where the sensors are heterogeneous in terms of sensing, communication and motion capabilities. We propose an integrated framework to accommodate such ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE/ACM Transactions on Networking

IEEE/ACM Transactions on Networking Volume 14, Issue 1

February 2006

231 pages

ISSN:1063-6692

Issue’s Table of Contents

Publisher

IEEE Press

Publication History

Published: 01 February 2006

Published in TON Volume 14, Issue 1

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

49
Total Citations
View Citations
1,158
Total Downloads

Downloads (Last 12 months)1
Downloads (Last 6 weeks)0

Reflects downloads up to 14 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Ammari H(2023)A Computational Geometry-based Approach for Planar k-Coverage in Wireless Sensor NetworksACM Transactions on Sensor Networks10.1145/356427219:2(1-42)Online publication date: 3-Feb-2023
https://dl.acm.org/doi/10.1145/3564272
Liu XChen XYang QZhang SGuo SLuo JLi K(2023)More Than Scheduling: Novel and Efficient Coordination Algorithms for Multiple Readers in RFID SystemsIEEE Transactions on Mobile Computing10.1109/TMC.2022.316784322:9(5375-5388)Online publication date: 1-Sep-2023
https://dl.acm.org/doi/10.1109/TMC.2022.3167843
Karaliopoulos MKoutsopoulos IBoukerche ASun P(2022)Empowering Synergies of Communities with Service Providers for the Bottom-up Deployment of Network InfrastructuresProceedings of the 18th ACM International Symposium on QoS and Security for Wireless and Mobile Networks10.1145/3551661.3561368(105-114)Online publication date: 24-Oct-2022
https://dl.acm.org/doi/10.1145/3551661.3561368
Adasme PDehghan Firoozabadi A(2020)Degree-Constrained k-Minimum Spanning Tree ProblemComplexity10.1155/2020/76281052020Online publication date: 1-Jan-2020
https://dl.acm.org/doi/10.1155/2020/7628105
Su XZhang MBai Q(2019)An Innovative Approach for Ad Hoc Network Establishment in Disaster Environments by the Deployment of Wireless Mobile AgentsACM Transactions on Autonomous and Adaptive Systems10.1145/333779513:4(1-22)Online publication date: 19-Jul-2019
https://dl.acm.org/doi/10.1145/3337795
Tan CJi SGui ZShen JFu DWang J(2018)An effective data fusion-based routing algorithm with time synchronization support for vehicular wireless sensor networksThe Journal of Supercomputing10.1007/s11227-017-2145-074:3(1267-1282)Online publication date: 1-Mar-2018
https://dl.acm.org/doi/10.1007/s11227-017-2145-0
Adasme PSoto ISeguel F(2018)Finding Degree Constrained k-Cardinality Minimum Spanning Trees for Wireless Sensor NetworksMobile Web and Intelligent Information Systems10.1007/978-3-319-97163-6_5(51-62)Online publication date: 6-Aug-2018
https://dl.acm.org/doi/10.1007/978-3-319-97163-6_5
(2017)Target coverage maximisation for directional sensor networksInternational Journal of Sensor Networks10.5555/3141297.314130224:4(253-263)Online publication date: 1-Jan-2017
https://dl.acm.org/doi/10.5555/3141297.3141302
Gong HFu LFu XZhao LWang KWang X(2017)Distributed Multicast Tree Construction in Wireless Sensor NetworksIEEE Transactions on Information Theory10.1109/TIT.2016.262331763:1(280-296)Online publication date: 1-Jan-2017
https://dl.acm.org/doi/10.1109/TIT.2016.2623317
Rebai MAfsar HSnoussi H(2016)Exact methods for sensor deployment problem with connectivity constraint in wireless sensor networksInternational Journal of Sensor Networks10.1504/IJSNET.2016.07832421:3(157-168)Online publication date: 1-Jan-2016
https://dl.acm.org/doi/10.1504/IJSNET.2016.078324
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents