research-article

On energy-efficient trap coverage in wireless sensor networks

Authors:

Youxian SunAuthors Info & Claims

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

Article No.: 2, Pages 1 - 29

https://doi.org/10.1145/2529973

Published: 06 December 2013 Publication History

Abstract

In wireless sensor networks (WSNs), trap coverage has recently been proposed to trade off between the availability of sensor nodes and sensing performance. It offers an efficient framework to tackle the challenge of limited resources in large-scale sensor networks. Currently, existing works only studied the theoretical foundation of how to decide the deployment density of sensors to ensure the desired degree of trap coverage. However, practical issues, such as how to efficiently schedule sensor node to guarantee trap coverage under an arbitrary deployment, are still left untouched. In this article, we formally formulate the Minimum Weight Trap Cover Problem and prove it is an NP-hard problem. To solve the problem, we introduce a bounded approximation algorithm, called Trap Cover Optimization (TCO) to schedule the activation of sensors while satisfying specified trap coverage requirement. We design Localized Trap Coverage Protocol as the localized implementation of TCO. The performance of Minimum Weight Trap Coverage we find is proved to be at most O(ρ) times of the optimal solution, where ρ is the density of sensor nodes in the region. To evaluate our design, we perform extensive simulations to demonstrate the effectiveness of our proposed algorithm and show that our algorithm achieves at least 14% better energy efficiency than the state-of-the-art solution.

References

[1]

Bai, X., Kumar, S., Xuan, D., Yun, Z., and Lai, T. 2006. Deploying wireless sensors to achieve both coverage and connectivity. In Proceedings of the 7th ACM International Symposium on Mobile Ad Hoc networking and Computing (MobiHoc). 131--142.

Digital Library

[2]

Balasubramanian, R., Ramasubramanian, S., and Efrat, A. 2006. Coverage time characteristics in sensor networks. In Proceedings of the IEEE International Conference on Mobile Adhoc and Sensor Systems (MASS). 566--569.

[3]

Balister, P. and Kumar, S. 2009. Random vs. deterministic deployment of sensors in the presence of failures and placement errors. In Proceedings of the IEEE International Conference on Computer Communications (INFOCOM). 2896--2900.

[4]

Balister, P., Zheng, Z., Kumar, S., and Sinha, P. 2009. Trap coverage: Allowing coverage holes of bounded diameter in wireless sensor networks. In Proceedings of the IEEE International Conference on Computer Communications (INFOCOM). 136--144.

[5]

Berman, P., Calinescu, G., Shah, C., and Zelikovsky, A. 2005. Efficient energy management in sensor networks. Ad Hoc Sen. Wirel. Netw. Net.

[6]

Cao, Q., Abdelzaher, T., He, T., and Stankovic, J. 2005. Towards optimal sleep scheduling in sensor networks for rare-event detection. In Proceedings of the 4th International Symposium on Information Processing in Sensor Networks (IPSN). 20--27.

Digital Library

[7]

Cao, X., Chen, J., Zhang, Y., and Sun, Y. 2008. Development of an integrated wireless sensor network micro-environment monitoring system. ISA Trans. 47, 3, 247--255.

[8]

Cardei, M. and Du, D. 2005. Improving wireless sensor network lifetime through power aware organization. Wirel. Netw. 11, 333--340.

Digital Library

[9]

Cardei, M., Thai, T., Li, Y., and Wu, W. 2005. Energy-efficient target coverage in wireless sensor networks. In Proceedings of the IEEE International Conference on Computer Communications (INFOCOM). 1976--1984.

[10]

Chen, J., Li, J., He, S., Sun, Y., and Chen, H. 2010. Energy-efficient coverage based on probabilistic sensing model in wireless sensor networks. IEEE Commun. Lett. 14, 9, 833--835.

Digital Library

[11]

Cheng, W., Li, M., Liu, K., Liu, Y., Li, X., and Liao, X. 2008. Sweep coverage with mobile sensors. In Proceedings of the IEEE International Symposium on Parallel and Distributed Processing (IPDPS). 1--9.

[12]

Chvatal, V. 1979. A greedy heuristic for the set-covering problem. Math. Oper. Res. 4, 3, 233--235.

Digital Library

[13]

Cormen, T., Leiserson, C., Rivest, R., and Stein, C. 2001. Data structures for disjoint sets. In Introduction to Algorithms, MIT Press and McGraw-Hill, 498--524.

[14]

Dong, D., Liu, Y., Liu, K., and Liao, X. 2010. Distributed coverage in wireless ad hoc and sensor networks by topological graph approaches. In Proceedings of the IEEE International Conference on Distributed Computing Systems. 106--115.

Digital Library

[15]

Gui, C. and Mohapatra, P. 2004. Power conservation and quality of surveillance in target tracking sensor networks. In Proceedings of the 10th Annual International Conference on Mobile Computing and Networking (MobiCom). 129--143.

Digital Library

[16]

He, S., Chen, J., and Sun, Y. 2012a. Coverage and connectivity in duty-cycled wireless sensor network for event monitoring. IEEE Trans. Parallel Distrib. Syst. 23, 3, 475--482.

Digital Library

[17]

He, S., Chen, J., Yau, D., Shao, H., and Sun, Y. 2012b. Energy-efficient capture of stochastic events under periodic network coverage and coordinated sleep. IEEE Trans. Parallel Distrib. Syst. 23, 6, 1090--1102.

Digital Library

[18]

Hwang, J., He, T., and Kim, Y. 2007. Exploring in-situ sensing irregularity in wireless sensor networks. In Proceedings of the 5th International Conference on Embedded Networked Sensor Systems (SenSys). 289--303.

Digital Library

[19]

Jeong, J., Gu, Y., He, T., and Du, D. 2009. Visa: Virtual scanning algorithm for dynamic protection of road networks. In Proceedings of the IEEE International Conference on Computer Communications (INFOCOM). 927--935.

[20]

Karp, R. M. 2010. Reducibility among combinatorial problems. In 50 Years of Integer Programming 1958-2008, Springer, Berlin, 219--241.

[21]

Kasbekar, G., Bejerano, Y., and Sarkar, S. 2009. Lifetime and coverage guarantees through distributed coordinate-free sensor activation. In Proceedings of the 15th Annual International Conference on Mobile Computing and Networking (MobiCom). 169--180.

Digital Library

[22]

Ko, J., Lu, C., Srivastava, M., Stankovic, J., Terzis, A., and Welsh, M. 2010. Wireless sensor networks for healthcare. Proc. of IEEE 98, 11, 1947--1960.

[23]

Kumar, S., Lai, T., and Arora, A. 2005. Barrier coverage with wireless sensors. In Proceedings of the 11th Annual International Conference on Mobile Computing and Networking (MobiCom). 284--298.

Digital Library

[24]

Kumar, S., Lai, T., Posner, M., and Sinha, P. 2010. Maximizing the lifetime of a barrier of wireless sensors. IEEE Trans. Mobile Comput. 9, 8, 1161--1172.

Digital Library

[25]

Li, J., Chen, J., He, S., He, T., Gu, Y., and Sun, Y. 2011. On energy-efficient trap coverage in wireless sensor networks. In Proceedings of the IEEE Real-Time Systems Symposium (RTSS). 139--148.

Digital Library

[26]

Li, J., Chen, J., and Lai, T. 2012. Energy-efficient intrusion detection with a barrier of probabilistic sensors. In Proceedings of the IEEE International Conference on Computer Communications (INFOCOM). 118--126.

[27]

Liu, B. and Towsley, D. 2004. A study of the coverage of large-scale sensor networks. In Proceedings of the IEEE International Conference on Mobile Ad-hoc and Sensor Systems (MASS). 475--483.

[28]

Liu, Y. and Liang, W. 2005. Approximate coverage in wireless sensor networks. In Proceedings of the IEEE International Conference on Local Computer Networks (LCN). 68--75.

Digital Library

[29]

Mao, G., Fidan, B., and Anderson, B. 2007. Wireless sensor network localization techniques. Comput. Netw. 51, 10, 2529--2553.

Digital Library

[30]

Meguerdichian, S., Koushanfar, F., Potkonjak, M., and Srivastava, M. 2001. Coverage problems in wireless ad-hoc sensor networks. In Proceedings of the IEEE International Conference on Computer Communications (INFOCOM). 1380--1387.

[31]

Patwari, N., Ash, J., Kyperountas, S., Hero, A., Moses, R., and Correal, N. 2005. Locating the nodes: Cooperative localization in wireless sensor networks. IEEE Signal Proces. Mag. 22, 4, 54--69.

[32]

Ren, S., Li, Q., Wang, H., Chen, X., and Zhang, X. 2007. Design and analysis of sensing scheduling algorithms under partial coverage for object detection in sensor networks. IEEE Trans. Parallel Distrib. Syst. 18, 3, 334--350.

Digital Library

[33]

Sankararaman, S., Efrat, A., Ramasubramanian, S., and Taheri, J. 2009. Scheduling sensors for guaranteed sparse coverage. http://arxiv.org/abs/0911.4332.

[34]

Slijepcevic, S. and Potkonjak, M. 2001. Power efficient organization of wireless sensor networks. In Proceedings of the IEEE International Conference on Communications (ICC). 472--476.

[35]

Wang, G., Cao, G., and Porta, T. 2004. Movement-assisted sensor deployment. In Proceedings of the IEEE International Conference on Computer Communications (INFOCOM). 2469--2479.

[36]

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

Digital Library

[37]

Yan, T., Gu, Y., He, T., and Stankovic, J. 2008. Design and optimization of distributed sensing coverage in wireless sensor networks. ACM Trans. Embed. Comput. Syst. 7, 1--40.

Digital Library

[38]

Yang, S., Dai, F., Cardei, M., and Wu, J. 2005. On multiple point coverage in wireless sensor networks. In Proceedings of the IEEE International Conference on Mobile Adhoc and Sensor Systems Conference (MASS).

[39]

Zahedi, S., Srivastava, M., Bisdikian, C., and Kaplan, L. 2010. Quality tradeoffs in object tracking with duty-cycled sensor networks. In Proceedings of the IEEE Real-Time Systems Symposium (RTSS). 160--169.

Digital Library

Cited By

Shao YWang QLu XWang ZZhao EFang SChen JKong LGhafoor K(2023)AutoBar: Automatic Barrier Coverage Formation for Danger Keep Out Applications in Smart CitySensors10.3390/s2318778723:18(7787)Online publication date: 10-Sep-2023
https://doi.org/10.3390/s23187787
Zhang ZZhang HHe SCheng P(2020)Bilateral Privacy-Preserving Utility Maximization Protocol in Database-Driven Cognitive Radio NetworksIEEE Transactions on Dependable and Secure Computing10.1109/TDSC.2017.278124817:2(236-247)Online publication date: 1-Mar-2020
https://doi.org/10.1109/TDSC.2017.2781248
Niemiec GBatista LSchaeffer-Filho ANazar G(2020)A Survey on FPGA Support for the Feasible Execution of Virtualized Network FunctionsIEEE Communications Surveys & Tutorials10.1109/COMST.2019.294369022:1(504-525)Online publication date: 9-Mar-2020
https://dl.acm.org/doi/10.1109/COMST.2019.2943690
Show More Cited By

Index Terms

On energy-efficient trap coverage in wireless sensor networks
1. Networks
  1. Network types
    1. Mobile networks
    2. Wireless access networks

Recommendations

On Energy-Efficient Trap Coverage in Wireless Sensor Networks
RTSS '11: Proceedings of the 2011 IEEE 32nd Real-Time Systems Symposium

In wireless sensor networks (WSNs), trap coverage has recently been proposed to tradeoff between the availability of sensor nodes and sensing performance. It offers an efficient framework to tackle the challenge of limited resources in large scale ...
Coverage and connectivity aware energy efficient scheduling in target based wireless sensor networks: an improved genetic algorithm based approach

Energy efficient scheduling of sensor nodes is one of the most efficient techniques to extend the lifetime of the wireless sensor networks (WSNs). Instead of activating all the deployed sensor nodes, a set of sensor nodes are activated or scheduled to ...
Sensor scheduling for p-percent coverage in wireless sensor networks

We study sensor scheduling problems of p-percent coverage in this paper and propose two scheduling algorithms to prolong network lifetime due to the fact that for some applications full coverage is not necessary and different subareas of the monitored ...

Comments

Information & Contributors

Information

Published In

cover image ACM Transactions on Sensor Networks

ACM Transactions on Sensor Networks Volume 10, Issue 1

November 2013

559 pages

ISSN:1550-4859

EISSN:1550-4867

DOI:10.1145/2555947

Issue’s Table of Contents

Copyright © 2013 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

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: 06 December 2013

Accepted: 01 January 2013

Revised: 01 October 2012

Received: 01 March 2012

Published in TOSN Volume 10, Issue 1

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

National Natural Science Foundation of China
Ministry of Science and Technology of the People's Republic of China
SRFDP
Singapore-MIT International Design Center IDG31000101
SUTD SRG ISTD 2010 002
Ministry of Education of the People's Republic of China

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

28
Total Citations
View Citations
475
Total Downloads

Downloads (Last 12 months)6
Downloads (Last 6 weeks)4

Reflects downloads up to 24 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Shao YWang QLu XWang ZZhao EFang SChen JKong LGhafoor K(2023)AutoBar: Automatic Barrier Coverage Formation for Danger Keep Out Applications in Smart CitySensors10.3390/s2318778723:18(7787)Online publication date: 10-Sep-2023
https://doi.org/10.3390/s23187787
Zhang ZZhang HHe SCheng P(2020)Bilateral Privacy-Preserving Utility Maximization Protocol in Database-Driven Cognitive Radio NetworksIEEE Transactions on Dependable and Secure Computing10.1109/TDSC.2017.278124817:2(236-247)Online publication date: 1-Mar-2020
https://doi.org/10.1109/TDSC.2017.2781248
Niemiec GBatista LSchaeffer-Filho ANazar G(2020)A Survey on FPGA Support for the Feasible Execution of Virtualized Network FunctionsIEEE Communications Surveys & Tutorials10.1109/COMST.2019.294369022:1(504-525)Online publication date: 9-Mar-2020
https://dl.acm.org/doi/10.1109/COMST.2019.2943690
Bhandayker Y(2019)An Overview of Diverse Techniques on Mobile Charging in the Wireless Rechargeable NetworksInternational Journal of Scientific Research in Science and Technology10.32628/IJSRST1962142(767-771)Online publication date: 15-Apr-2019
https://doi.org/10.32628/IJSRST1962142
Han GWu JWang HGuizani MAnsere JZhang W(2019)A Multicharger Cooperative Energy Provision Algorithm Based on Density Clustering in the Industrial Internet of ThingsIEEE Internet of Things Journal10.1109/JIOT.2019.29285576:5(9165-9174)Online publication date: Oct-2019
https://doi.org/10.1109/JIOT.2019.2928557
Guo WZhu WYu ZWang JGuo B(2019)A Survey of Task Allocation: Contrastive Perspectives From Wireless Sensor Networks and Mobile CrowdsensingIEEE Access10.1109/ACCESS.2019.28962267(78406-78420)Online publication date: 2019
https://doi.org/10.1109/ACCESS.2019.2896226
Man DYang WTian G(2018)Multi-pattern Matching Algorithm based on Variable Step SizeProceedings of the 8th International Conference on Communication and Network Security10.1145/3290480.3290482(125-128)Online publication date: 2-Nov-2018
https://dl.acm.org/doi/10.1145/3290480.3290482
Rahili SLu JRen WAl-Saggaf U(2018)Distributed Coverage Control of Mobile Sensor Networks in Unknown Environment Using Game Theory: Algorithms and ExperimentsIEEE Transactions on Mobile Computing10.1109/TMC.2017.276135117:6(1303-1313)Online publication date: 1-Jun-2018
https://doi.org/10.1109/TMC.2017.2761351
Deng RHe SChen J(2018)An Online Algorithm for Data Collection by Multiple Sinks in Wireless-Sensor NetworksIEEE Transactions on Control of Network Systems10.1109/TCNS.2016.25784605:1(93-104)Online publication date: Mar-2018
https://doi.org/10.1109/TCNS.2016.2578460
Han GYang XLiu LZhang W(2018)A Joint Energy Replenishment and Data Collection Algorithm in Wireless Rechargeable Sensor NetworksIEEE Internet of Things Journal10.1109/JIOT.2017.27844785:4(2596-2604)Online publication date: Aug-2018
https://doi.org/10.1109/JIOT.2017.2784478
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.

Media

Figures

Other

Tables

View Issue’s Table of Contents