article

Redundancy and coverage detection in sensor networks

Authors:

Bogdan Cărbunar,

Octavian CărbunarAuthors Info & Claims

ACM Transactions on Sensor Networks (TOSN), Volume 2, Issue 1

Pages 94 - 128

https://doi.org/10.1145/1138127.1138131

Published: 01 February 2006 Publication History

Abstract

We study the problem of detecting and eliminating redundancy in a sensor network with a view to improving energy efficiency, while preserving the network's coverage. We also examine the impact of redundancy elimination on the related problem of coverage-boundary detection. We reduce both problems to the computation of Voronoi diagrams, prove and achieve lower bounds on the solution of these problems, and present efficient distributed algorithms for computing and maintaining solutions in cases of sensor failures or insertion of new sensors. We prove the correctness and termination properties of our distributed algorithms, and analytically characterize the time complexity and traffic generated by our algorithms. Using detailed simulations, we also quantify the impact of system parameters such as sensor density, transmission range, and failure rates on network traffic.

References

[1]

Basagni, S., Chlamtac, I., Syrotiuk, V. R., and Woodward, B. A. 1998. A distance routing effect algorithm for mobility (DREAM). In MobiCom '98: Proceedings of the 4th annual ACM/IEEE international conference on Mobile computing and networking. ACM Press, New York, NY, USA, 76--84.

[2]

Cardei, M. and Wu, J. 2004. Coverage in Wireless Sensor Networks. Handbook of Sensor Networks. CRC Press.

[3]

Carle, J. and Simplot-Ryl, D. 2004. Energy efficient area monitoring for sensor networks. IEEE Comput. 37, 2 (Feb.), 40--46.

[4]

Choset, H. 2001. Coverage for robotics---a survey of recent results. Annals of Mathematics and Artificial Intelligence 31, 113--126.

[5]

Dai, F. and Wu, J. 2003. Distributed dominant pruning in ad hoc wireless networks. In ICC '03: Proceedings of IEEE International Conference on Communications.

[6]

Devillers, O., Meiser, S., and Teillaud, M. 1992. Fully dynamic Delaunay triangulation in logarithmic expected time per operation. Comput. Geom. Theory Appl. 2, 2, 55--80.

[7]

Gupta, H., Das, S. R., and Gu, Q. 2003. Connected sensor cover: self-organization of sensor networks for efficient query execution. In MobiHoc '03: Proceedings of the 4th ACM International Symposium on Mobile Ad Hoc Networking & Computing. ACM Press, 189--200.

[8]

Haas, Z. May 1997. On the relaying capability of the reconfigurable wireless networks. In VTC: Proceedings of 47th IEEE Vehicular Technology Conference 2, 1148--1152.

[9]

Hu, L. 1993. Topology control for multihop packet radio networks. IEEE Trans. Comm. 41, 10 (Oct.), 1474--1481.

[10]

Huang, C.-F. and Tseng, Y.-C. 2003. The coverage problem in a wireless sensor network. In WSNA '03: Proceedings of the 2nd ACM International Conference on Wireless Sensor Networks and Applications. ACM Press, 115--121.

[11]

Jiang, J. and Dou, W. 2004. A coverage-preserving density control algorithm for wireless sensor networks. In Proceedings of ADHOC-NOW.

[12]

Karp, B. and Kung, H. T. 2000. GPSR: Greedy perimeter stateless routing for wireless networks. In MobiCom '00: Proceedings of the 6th Annual International Conference on Mobile Computing and Networking. ACM Press, New York, NY, USA, 243--254.

[13]

Ko, Y.-B. and Vaidya, N. H. 1998. Location-aided routing (LAR) in mobile ad hoc networks. In MobiCom '98: Proceedings of the 4th Annual ACM/IEEE International Conference on Mobile Computing and Networking. ACM Press, New York, NY, USA, 66--75.

[14]

Luby, M. 1985. A simple parallel algorithm for the maximal independent set problem. In STOC '85: Proceedings of the Seventeenth Annual ACM Symposium on Theory of Computing. ACM Press, 1--10.

[15]

Meguerdichian, S., Koushanfar, F., Qu, G., and Potkonjak, M. 2001. Exposure in wireless ad-hoc sensor networks. In MobiCom '01: Proceedings of the 7th Annual International Conference on Mobile Computing and Networking. ACM Press, New York, NY, USA, 139--150.

[16]

Muthukrishnan, S. and Pandurangan, G. 2003. The bin-covering technique for thresholding random geometric graph properties. Tech. Rep. 2003-39, DIMACS. November.

[17]

Shakkottai, S., Srikant, R., and Shroff, N. 2003. Unreliable sensor grids: Coverage, connectivity and diameter. In Proceedings of IEEE INFOCOM. 2, 1073--1083.

[18]

Slijepcevic, S. and Potkonjak, M. 2001. Power efficient organization of wireless sensor networks. In ICC '01: Proceedings of IEEE International Conference on Communications.

[19]

Stojmenovic, I. 1999. Voronoi diagram and convex hull based geocasting and routing in wireless networks. Tech. Rep. TR-99-11, University of Ottawa. December.

[20]

Tian, D. and Georganas, N. D. 2002. A coverage-preserving node scheduling scheme for large wireless sensor networks. In WSNA '02: Proceedings of the 1st ACM International Workshop on Wireless Sensor Networks and Applications. ACM Press, 32--41.

[21]

Wang, X., Xing, G., Zhang, Y., Lu, C., Pless, R., and Gill, C. 2003. Integrated coverage and connectivity configuration in wireless sensor networks. In SenSys '03: Proceedings of the 1st International Conference on Embedded Networked Sensor Systems. ACM Press, 28--39.

[22]

Ye, F., Zhong, G., Lu, S., and Zhang, L. 2003. PEAS: A robust energy conserving protocol for long-lived sensor networks. In ICDCS '03: Proceedings of the 23rd IEEE International Conference on Distributed Computing Systems.

[23]

Zhang, H. and Hou, J. 2004. Maintaining coverage and connectivity in large sensor networks. In International Workshop on Theoretical and Algorithmic Aspects of Sensor, Ad hoc Wireless and Peer-to-Peer Networks.

Cited By

Mazaheri HGoli SNourollah A(2024)A survey of 3D Space Path-Planning Methods and AlgorithmsACM Computing Surveys10.1145/367389657:1(1-32)Online publication date: 7-Oct-2024
https://dl.acm.org/doi/10.1145/3673896
Sungvornyothin TThammawichai M(2024)On Solving Area Coverage for Heterogeneous Directional Sensor Networks2024 21st International Conference on Electrical Engineering/Electronics, Computer, Telecommunications and Information Technology (ECTI-CON)10.1109/ECTI-CON60892.2024.10594891(1-6)Online publication date: 27-May-2024
https://doi.org/10.1109/ECTI-CON60892.2024.10594891
Nurcan-Atceken DAltin-Kayhan ATavli B(2024)A novel differentiated coverage-based lifetime metric for wireless sensor networksAd Hoc Networks10.1016/j.adhoc.2024.103636(103636)Online publication date: Aug-2024
https://doi.org/10.1016/j.adhoc.2024.103636
Show More Cited By

Index Terms

Redundancy and coverage detection in sensor networks

Recommendations

Coverage breach problems in bandwidth-constrained sensor networks

Recent research in sensor networks highlights the low-power mode operation of sensor networks. In wireless sensor networks, network lifetime can be extended by organizing sensors into mutually exclusive subsets and alternatively activating each subset. ...
Boundary coverage and coverage boundary problems in wireless sensor networks

The extent of coverage of a Wireless Sensor Network (WSN) is of fundamental importance and determines the utility and effectiveness of the deployment. Determining the least number of sensors required to cover the boundary of a region (boundary coverage) ...
An efficient cluster-based communication protocol for wireless sensor networks

A wireless sensor network is a network of large numbers of sensor nodes, where each sensor node is a tiny device that is equipped with a processing, sensing subsystem and a communication subsystem. The critical issue in wireless sensor networks is how ...

Comments

Information & Contributors

Information

Published In

cover image ACM Transactions on Sensor Networks

ACM Transactions on Sensor Networks Volume 2, Issue 1

February 2006

153 pages

ISSN:1550-4859

EISSN:1550-4867

DOI:10.1145/1138127

Issue’s Table of Contents

Copyright © 2006 ACM.

Publisher

Association for Computing Machinery

New York, NY, United States

Journal Family

ACM Journals for the Design of Smart and Connected Systems

Publication History

Published: 01 February 2006

Published in TOSN Volume 2, Issue 1

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

126
Total Citations
View Citations
2,201
Total Downloads

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

Reflects downloads up to 03 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Mazaheri HGoli SNourollah A(2024)A survey of 3D Space Path-Planning Methods and AlgorithmsACM Computing Surveys10.1145/367389657:1(1-32)Online publication date: 7-Oct-2024
https://dl.acm.org/doi/10.1145/3673896
Sungvornyothin TThammawichai M(2024)On Solving Area Coverage for Heterogeneous Directional Sensor Networks2024 21st International Conference on Electrical Engineering/Electronics, Computer, Telecommunications and Information Technology (ECTI-CON)10.1109/ECTI-CON60892.2024.10594891(1-6)Online publication date: 27-May-2024
https://doi.org/10.1109/ECTI-CON60892.2024.10594891
Nurcan-Atceken DAltin-Kayhan ATavli B(2024)A novel differentiated coverage-based lifetime metric for wireless sensor networksAd Hoc Networks10.1016/j.adhoc.2024.103636(103636)Online publication date: Aug-2024
https://doi.org/10.1016/j.adhoc.2024.103636
V S RSiddaraju D(2023)A Novel Buffer Packet Delivery Strategy for High Throughput and Better Health (HTBH) Method in Wireless Sensor NetworksInternational Journal of Electrical and Electronics Research10.37391/ijeer.11033411:3(866-876)Online publication date: 30-Sep-2023
https://doi.org/10.37391/ijeer.110334
Chenait MBenzaïd CZebbane B(2023)Linear Complexity for k-Coverage Sensor Redundancy Determination in IoT2023 International Symposium on Networks, Computers and Communications (ISNCC)10.1109/ISNCC58260.2023.10324000(1-6)Online publication date: 23-Oct-2023
https://doi.org/10.1109/ISNCC58260.2023.10324000
Bläsius TFriedrich TGöbel ALevy JRothenberger R(2023)The impact of heterogeneity and geometry on the proof complexity of random satisfiabilityRandom Structures & Algorithms10.1002/rsa.21168Online publication date: 28-Jun-2023
https://doi.org/10.1002/rsa.21168
V S RSiddaraju (2022)Defective Motes Uncovering and Retrieval for Optimized Network2022 6th International Conference on Computing Methodologies and Communication (ICCMC)10.1109/ICCMC53470.2022.9754109(303-313)Online publication date: 29-Mar-2022
https://doi.org/10.1109/ICCMC53470.2022.9754109
Nematzadeh STorkamanian-Afshar MSeyyedabbasi AKiani F(2022)Maximizing coverage and maintaining connectivity in WSN and decentralized IoT: an efficient metaheuristic-based method for environment-aware node deploymentNeural Computing and Applications10.1007/s00521-022-07786-135:1(611-641)Online publication date: 18-Sep-2022
https://dl.acm.org/doi/10.1007/s00521-022-07786-1
Bläsius TFriedrich TGöbel ALevy JRothenberger RMarx D(2021)The impact of heterogeneity and geometry on the proof complexity of random satisfiabilityProceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3458064.3458068(42-53)Online publication date: 10-Jan-2021
https://dl.acm.org/doi/10.5555/3458064.3458068
Chaturvedi PDaniel A(2021)Priority Encoding-Based Cluster Head Selection Approach in Wireless Sensor NetworksEvolution of Software-Defined Networking Foundations for IoT and 5G Mobile Networks10.4018/978-1-7998-4685-7.ch007(113-138)Online publication date: 2021
https://doi.org/10.4018/978-1-7998-4685-7.ch007
Show More Cited By

View Options

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.

Figures

Tables

Media

View Issue’s Table of Contents