skip to main content
article

Distributed protocols for ensuring both coverage and connectivity of a wireless sensor network

Published: 01 March 2007 Publication History

Abstract

Wireless sensor networks have attracted a lot of attention recently. Such environments may consist of many inexpensive nodes, each capable of collecting, storing, and processing environmental information, and communicating with neighboring nodes through wireless links. For a sensor network to operate successfully, sensors must maintain both sensing coverage and network connectivity. This issue has been studied in wang et al. [2003] and Zhang and Hou [2004a], both of which reach a similar conclusion that coverage can imply connectivity as long as sensors' communication ranges are no less than twice their sensing ranges. In this article, without relying on this strong assumption, we investigate the issue from a different angle and develop several necessary and sufficient conditions for ensuring coverage and connectivity of a sensor network. Hence, the results significantly generalize the results in Wang et al. [2003] and Zhang and Hou [2004a]. This work is also a significant extension of our earlier work [Huang and Tseng 2003; Huang et al. 2004], which addresses how to determine the level of coverage of a given sensor network but does not consider the network connectivity issue. Our work is the first work allowing an arbitrary relationship between sensing ranges and communication distances of sensor nodes. We develop decentralized solutions for determining, or even adjusting, the levels of coverage and connectivity of a given network. Adjusting levels of coverage and connectivity is necessary when sensors are overly deployed, and we approach this problem by putting sensors to sleep mode and tuning their transmission powers. This results in prolonged network lifetime.

References

[1]
Abrams, Z., Goel, A., and Plotkin, S. 2004. Set K-cover algorithms for energy efficient monitoring in wireless sensor networks. In International Symposium on Information Processing in Sensor Networks (IPSN). 424--432.
[2]
Bahl, P. and Padmanabhan, V. N. 2000. RADAR: An in-building RF-based user location and tracking system. In IEEE INFOCOM. 775--784.
[3]
Braginsky, D. and Estrin, D. 2002. Rumor routing algorithm for sensor networks. In ACM International Workshop on Wireless Sensor Networks and Applications (WSNA).
[4]
Burkhart, M., von Rickenbach, P., Wattenhofer, R., and Zollinger, A. 2004. Does topology control reduce interference? In ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHOC). 9--19.
[5]
Chen, B., Jamieson, K., Balakrishnan, H., and Morris, R. 2002. Span: An energy-efficient coordination algorithm for topology maintenance in ad hoc wireless networks. ACM Wireless Netw. 8, 5 (Sep.), 481--494.
[6]
Ganesan, D., Govindan, R., Shenker, S., and Estrin, D. 2001. Highly resilient, energy efficient multipath routing in wireless sensor networks. ACM Mobile Comput. Comm. Rev. 5, 4 (Oct.), 11--25.
[7]
Gupta, H., Das, S. R., and Gu, Q. 2003. Connected sensor cover: Self-organization of sensor networks for efficient query execution. In ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHOC). 189--200.
[8]
Heinzelman, W. R., Chandrakasan, A., and Balakrishnan, H. 2000. Energy-efficient communication protocols for wireless microsensor networks. In Hawaii International Conference on Systems Science (HICSS).
[9]
Huang, C.-F. and Tseng, Y.-C. 2003. The coverage problem in a wireless sensor network. In ACM International Workshop on Wireless Sensor Networks and Applications (WSNA). 115--121.
[10]
Huang, C.-F., Tseng, Y.-C., and Lo, L.-C. 2004. The coverage problem in three-dimensional wireless sensor networks. In IEEE Global Telecommunications Conference (Globecom).
[11]
Inanc, M., Magdon-Ismail, M., and Yener, B. 2003. Power optimal connectivity and coverage in wireless sensor networks. Tech. rep. TR-03-06 (July). Department of Computer Science, Rensselaer Polytechnic Institute.
[12]
Li, N. and Hou, J. C. 2004. FLSS: A fault-tolerant topology control algorithm for wireless networks. In ACM International Conference on Mobile Computing and Networking (MobiCom).
[13]
Li, X.-Y., Wan, P.-J., and Frieder, O. 2003. Coverage in wireless ad hoc sensor networks. IEEE Trans. Comput. 52, 6 (June), 753--763.
[14]
Lu, M., Wu, J., Cardei, M., and Li, M. 2005. Energy-efficient connected coverage of discrete targets in wireless sensor networks. In International Conference on Computer Networks and Mobile Computing (ICCNMC).
[15]
Meguerdichian, S., Koushanfar, F., Potkonjak, M., and Srivastava, M. B. 2001. Coverage problems in wireless ad-hoc sensor networks. In IEEE INFOCOM. 1380--1387.
[16]
Meguerdichian, S., Koushanfar, F., Qu, G., and Potkonjak, M. 2001. Exposure in wireless ad-hoc sensor networks. In ACM International Conference on Mobile Computing and Networking (MobiCom). 139--150.
[17]
Pottie, G. J. and Kaiser, W. J. 2000. Wireless integrated network sensors. Comm. ACM 43, 5 (May), 51--58.
[18]
Savvides, A., Han, C.-C., and Strivastava, M. B. 2001. Dynamic fine-grained localization in ad-hoc networks of sensors. In ACM International Conference on Mobile Computing and Networking (MobiCom). 166--179.
[19]
Shakkottai, S., Srikant, R., and Shroff, N. 2003. Unreliable sensor grids: Coverage, connectivity and diameter. In IEEE INFOCOM. 1073--1083.
[20]
Shih, E., Cho, S.-H., Ickes, N., Min, R., Sinha, A., Wang, A., and Chandrakasan, A. 2001. Physical layer driven protocol and algorithm design for energy-efficient wireless sensor networks. In ACM International Conference on Mobile Computing and Networking (MobiCom). 272--287.
[21]
Sohrabi, K., Gao, J., Ailawadhi, V., and Pottie, G. J. 2000. Protocols for self-organization of a wireless sensor network. IEEE Person. Comm. 7, 5 (Oct.), 16--27.
[22]
Tian, D. and Georganas, N. D. 2003. A node scheduling scheme for energy conservation in large wireless sensor networks. Wireless Comm. Mobile Comput. 3, 271--290.
[23]
Tseng, Y.-C., Kuo, S.-P., Lee, H.-W., and Huang, C.-F. 2003. Location tracking in a wireless sensor network by mobile agents and its data fusion strategies. In International Symposium on Information Processing in Sensor Networks (IPSN).
[24]
Veltri, G., Huang, Q., Qu, G., and Potkonjak, M. 2003. Minimal and maximal exposure path algorithms for wireless embedded sensor networks. In ACM International Conference on Embedded Networked Sensor Systems (SenSys). 40--50.
[25]
Wang, X., Xing, G., Zhang, Y., Lu, C., Pless, R., and Gill, C. 2003. Integrated coverage and connectivity configuration in wireless sensor networks. In ACM International Conference on Embedded Networked Sensor Systems (SenSys). 28--39.
[26]
Wattenhofer, R., Li, L., Bahl, P., and Wang, Y.-M. 2001. Distributed topology control for power efficient operation in multihop wireless ad hoc networks. In IEEE INFOCOM. 1388--1397.
[27]
Woo, A. and Culler, D. E. 2001. A transmission control scheme for media access in sensor networks. In ACM International Conference on Mobile Computing and Networking (MobiCom). 221--235.
[28]
Xu, Y., Heidemann, J., and Estrin, D. 2001. Geography-informed energy conservation for ad hoc routing. In ACM International Conference on Mobile Computing and Networking (MobiCom). 70--84.
[29]
Yan, T., He, T., and Stankovic, J. A. 2003. Differentiated surveillance for sensor networks. In ACM International Conference on Embedded Networked Sensor Systems (SenSys). 51--62.
[30]
Ye, W., Heidemann, J., and Estrin, D. 2002. An energy-efficient MAC protocol for wireless sensor networks. In IEEE INFOCOM. 1567--1576.
[31]
Zhang, H. and Hou, J. C. 2004a. Maintaining sensing coverage and connectivity in large sensor networks. In NSF International Workshop on Theoretical and Algorithmic Aspects of Sensor, Ad Hoc Wireless, and Peer-to-Peer Networks.
[32]
Zhang, H. and Hou, J. C. 2004b. On deriving the upper bound of lifetime for large sensor networks. In ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHOC). 121--132.

Cited By

View all
  • (2024)Multi-Objective Optimization for Coverage and Connectivity in Wireless Sensor Networks2024 13th International Conference on Modern Circuits and Systems Technologies (MOCAST)10.1109/MOCAST61810.2024.10615606(1-7)Online publication date: 26-Jun-2024
  • (2024)Transit search algorithm based on oscillation exploitation factor and Roche limit for wireless sensor network deployment optimizationArtificial Intelligence Review10.1007/s10462-024-10951-858:1Online publication date: 27-Nov-2024
  • (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
  • Show More Cited By

Index Terms

  1. Distributed protocols for ensuring both coverage and connectivity of a wireless sensor network

        Recommendations

        Comments

        Information & Contributors

        Information

        Published In

        cover image ACM Transactions on Sensor Networks
        ACM Transactions on Sensor Networks  Volume 3, Issue 1
        March 2007
        171 pages
        ISSN:1550-4859
        EISSN:1550-4867
        DOI:10.1145/1210669
        Issue’s Table of Contents

        Publisher

        Association for Computing Machinery

        New York, NY, United States

        Journal Family

        Publication History

        Published: 01 March 2007
        Published in TOSN Volume 3, Issue 1

        Permissions

        Request permissions for this article.

        Check for updates

        Author Tags

        1. Ad hoc network
        2. connectivity
        3. coverage
        4. energy conservation
        5. power control
        6. sensor network
        7. wireless network

        Qualifiers

        • Article

        Contributors

        Other Metrics

        Bibliometrics & Citations

        Bibliometrics

        Article Metrics

        • Downloads (Last 12 months)14
        • Downloads (Last 6 weeks)2
        Reflects downloads up to 16 Feb 2025

        Other Metrics

        Citations

        Cited By

        View all
        • (2024)Multi-Objective Optimization for Coverage and Connectivity in Wireless Sensor Networks2024 13th International Conference on Modern Circuits and Systems Technologies (MOCAST)10.1109/MOCAST61810.2024.10615606(1-7)Online publication date: 26-Jun-2024
        • (2024)Transit search algorithm based on oscillation exploitation factor and Roche limit for wireless sensor network deployment optimizationArtificial Intelligence Review10.1007/s10462-024-10951-858:1Online publication date: 27-Nov-2024
        • (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
        • (2023)Logic Separation: Discrete Modelling of Pattern RecognitionPattern Recognition and Image Analysis10.1134/S105466182304007733:4(902-936)Online publication date: 1-Dec-2023
        • (2023)Energy Efficient Adaptive Mobile Wireless Sensor Network in Smart Monitoring ApplicationsInnovations in Intelligent Computing and Communication10.1007/978-3-031-23233-6_17(222-235)Online publication date: 1-Jan-2023
        • (2022)Balancing the trade-off between cost and reliability for wireless sensor networks: a multi-objective optimized deployment methodApplied Intelligence10.1007/s10489-022-03875-953:8(9148-9173)Online publication date: 5-Aug-2022
        • (2021)A Modified Approach to Sleep Scheduling Mechanism Using Particle Swarm Optimization for Wireless Sensor Network2021 2nd International Conference for Emerging Technology (INCET)10.1109/INCET51464.2021.9456337(1-5)Online publication date: 21-May-2021
        • (2021)Connected k-coverage in two-dimensional wireless sensor networks using hexagonal slicing and area stretchingJournal of Parallel and Distributed Computing10.1016/j.jpdc.2020.12.008Online publication date: Mar-2021
        • (2019)An Enhanced Virtual Force Algorithm for Diverse k-Coverage Deployment of 3D Underwater Wireless Sensor NetworksSensors10.3390/s1916349619:16(3496)Online publication date: 9-Aug-2019
        • (2019)A Comprehensive Approach for Implementation of Randomly Deployed Wireless Sensor NetworksJournal of Communications10.12720/jcm.14.10.915-925(915-925)Online publication date: 2019
        • Show More Cited By

        View Options

        Login options

        Full Access

        View options

        PDF

        View or Download as a PDF file.

        PDF

        eReader

        View online with eReader.

        eReader

        Figures

        Tables

        Media

        Share

        Share

        Share this Publication link

        Share on social media