{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T04:12:37Z","timestamp":1760242357512,"version":"build-2065373602"},"reference-count":39,"publisher":"MDPI AG","issue":"6","license":[{"start":{"date-parts":[[2017,5,25]],"date-time":"2017-05-25T00:00:00Z","timestamp":1495670400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Sensors"],"abstract":"<jats:p>Coverage is a fundamental issue in the research field of wireless sensor networks (WSNs). Connected target coverage discusses the sensor placement to guarantee the needs of both coverage and connectivity. Existing works largely leverage on the Boolean disk model, which is only a coarse approximation to the practical sensing model. In this paper, we focus on the connected target coverage issue based on the probabilistic sensing model, which can characterize the quality of coverage more accurately. In the probabilistic sensing model, sensors are only be able to detect a target with certain probability. We study the collaborative detection probability of target under multiple sensors. Armed with the analysis of collaborative detection probability, we further formulate the minimum \u03f5-connected target coverage problem, aiming to minimize the number of sensors satisfying the requirements of both coverage and connectivity. We map it into a flow graph and present an approximation algorithm called the minimum vertices maximum flow algorithm (MVMFA) with provable time complex and approximation ratios. To evaluate our design, we analyze the performance of MVMFA theoretically and also conduct extensive simulation studies to demonstrate the effectiveness of our proposed algorithm.<\/jats:p>","DOI":"10.3390\/s17061208","type":"journal-article","created":{"date-parts":[[2017,5,30]],"date-time":"2017-05-30T04:35:42Z","timestamp":1496118942000},"page":"1208","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":9,"title":["A Max-Flow Based Algorithm for Connected Target Coverage with Probabilistic Sensors"],"prefix":"10.3390","volume":"17","author":[{"given":"Anxing","family":"Shan","sequence":"first","affiliation":[{"name":"School of Computer Science, Hangzhou Dianzi University, Hangzhou 310018, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xianghua","family":"Xu","sequence":"additional","affiliation":[{"name":"School of Computer Science, Hangzhou Dianzi University, Hangzhou 310018, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zongmao","family":"Cheng","sequence":"additional","affiliation":[{"name":"School of Science, Hangzhou Dianzi University, Hangzhou 310018, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Wensheng","family":"Wang","sequence":"additional","affiliation":[{"name":"College of Economics, Hangzhou Dianzi University, Hangzhou 310018, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2017,5,25]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","unstructured":"Han, K., Xiang, L., Luo, J., and Liu, Y. (2012, January 11\u201314). Minimum-energy connected coverage in wireless sensor networks with omni-directional and directional features. Proceedings of the ACM international symposium on Mobile Ad Hoc Networking and Computing, Hilton Head, SC, USA.","DOI":"10.1145\/2248371.2248386"},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Tsai, H.W., Jhong, J.J., and Lin, M.R. (2013, January 2\u20134). The angle coverage algorithm of mobile object in wireless camera sensor networks. Proceedings of the International Joint Conference on Awareness Science and Technology & Ubi-Media Computing, Aizuwakamatsu, Japan.","DOI":"10.1109\/ICAwST.2013.6765477"},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Wu, M.C., and Lu, W.F. (2013, January 3\u20135). On Target Coverage Problem of Angle Rotatable Directional Sensor Networks. Proceedings of the Seventh International Conference on Innovative Mobile and Internet Services in Ubiquitous Computing, Taichung, Taiwan.","DOI":"10.1109\/IMIS.2013.107"},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Yan, T., He, T., and Stankovic, J.A. (2003, January 5\u20137). Differentiated Surveillance for Sensor Networks. Proceedings of the International Conference on Embedded Networked Sensor Systems, Los Angeles, CA, USA.","DOI":"10.1145\/958491.958498"},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"1971","DOI":"10.1109\/TPDS.2014.2333011","article-title":"Minimizing movement for target coverage and network connectivity in mobile sensor networks","volume":"26","author":"Liao","year":"2015","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"key":"ref_6","first-page":"1","article-title":"Efficient and Adaptive Node Selection for Target Tracking in Wireless Sensor Network","volume":"2016","author":"Feng","year":"2016","journal-title":"J. Sens."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"2077","DOI":"10.1109\/JSEN.2013.2248144","article-title":"Coverage-Enhancing Algorithm Based on Overlap-Sense Ratio in Wireless Multimedia Sensor Networks","volume":"13","author":"Chen","year":"2013","journal-title":"IEEE Sens. J."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"1267","DOI":"10.1109\/TPDS.2013.137","article-title":"Localized Movement-Assisted SensorDeployment Algorithm for HoleDetection and Healing","volume":"25","author":"Senouci","year":"2014","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"1812","DOI":"10.1109\/TC.2013.45","article-title":"Optimal Camera Placement for Providing Angular Coverage in Wireless Video Sensor Networks","volume":"63","author":"Yildiz","year":"2014","journal-title":"IEEE Trans. Comput."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"1988","DOI":"10.3390\/s140201988","article-title":"Surveillance of a 2D Plane Area with 3D Deployed Cameras","volume":"14","author":"Fu","year":"2014","journal-title":"Sensors"},{"key":"ref_11","first-page":"222","article-title":"Barrier Coverage in Hybrid Directional Sensor Networks","volume":"13","author":"Wang","year":"2013","journal-title":"IEEE Trans. Mob. Comput."},{"key":"ref_12","first-page":"470","article-title":"Barrier Coverage in Wireless Sensor Networks: From Lined-Based to Curve-Based Deployment","volume":"12","author":"He","year":"2013","journal-title":"INFOCOM"},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"4742","DOI":"10.1109\/TW.2013.072313.122083","article-title":"Energy-Efficient Intrusion Detection with a Barrier of Probabilistic Sensors: Global and Local","volume":"12","author":"Chen","year":"2013","journal-title":"IEEE Trans. Wirel. Commun."},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"DeWitt, J., and Shi, H. (2014, January 8\u201312). Maximizing lifetime for k-barrier coverage in energy harvesting wireless sensor networks. Proceedings of the 2014 IEEE Global Communications Conference, Austin, TX, USA.","DOI":"10.1109\/GLOCOM.2014.7036824"},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Wang, Z., Chen, H., Cao, Q., Qi, H., and Wang, Z. (2014). Fault tolerant barrier coverage for wireless sensor networks. INFOCOM, 1869\u20131877.","DOI":"10.1109\/INFOCOM.2014.6848126"},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1016\/j.cor.2014.11.002","article-title":"Sensor deployment optimization methods to achieve both coverage and connectivity in wireless sensor networks","volume":"59","author":"Rebai","year":"2015","journal-title":"Comput. Oper. Res."},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Jehan, C., and Punithavathani, D.S. (2016). Potential position node placement approach via oppositional gravitational search for fulfill coverage and connectivity in target based wireless sensor networks. Wirel. Netw., 1\u201314.","DOI":"10.1007\/s11276-016-1262-7"},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Shan, A., Xu, X., and Cheng, Z. (2016). Target Coverage in Wireless Sensor Networks with Probabilistic Sensors. Sensors, 16.","DOI":"10.3390\/s16091372"},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Kim, C.M., Kim, Y., Kang, I.S., Lee, K., and Han, Y.H. (2012, January 28\u201330). A scheduling algorithm for connected target coverage under probabilistic coverage model. Proceedings of the International Conference on Information Networking, Bangkok, Thailand.","DOI":"10.1109\/ICOIN.2012.6164355"},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"1039","DOI":"10.1016\/j.comcom.2012.07.021","article-title":"Prolonging network lifetime under probabilistic target coverage in wireless mobile sensor networks","volume":"36","author":"Zorbas","year":"2013","journal-title":"Comput. Commun."},{"key":"ref_21","doi-asserted-by":"crossref","unstructured":"Willson, J., Zhang, Z., Wu, W., and Du, D.Z. (2015). Fault-tolerant coverage with maximum lifetime in wireless sensor networks. Comput. Commun., 1364\u20131372.","DOI":"10.1109\/INFOCOM.2015.7218513"},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"262","DOI":"10.1109\/TMC.2007.70708","article-title":"Efficient Placement and Dispatch of Sensors in a Wireless Sensor Network","volume":"7","author":"Wang","year":"2008","journal-title":"IEEE Trans. Mobile Comput."},{"key":"ref_23","unstructured":"Hefeeda, M., and Ahmadi, H. (2005, January 17). Probabilistic coverage in wireless sensor networks. Proceedings of the Conference on Local Computer Networks (LCN), Sydney, Australia."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1145\/1978802.1978811","article-title":"Coverage problems in sensor networks: A survey","volume":"43","author":"Wang","year":"2011","journal-title":"Acm Comput. Surv."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"1378","DOI":"10.1109\/TNET.2007.911432","article-title":"Lifetime Maximization for Connected Target Coverage in Wireless Sensor Networks","volume":"16","author":"Zhao","year":"2008","journal-title":"IEEE\/ACM Trans. Netw."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1504\/IJAHUC.2009.024516","article-title":"Energy-Efficient Connected Coverage of Discrete Targets in Wireless Sensor Networks","volume":"4","author":"Lu","year":"2009","journal-title":"Int. J. Ad Hoc Ubiq. Comput."},{"key":"ref_27","doi-asserted-by":"crossref","unstructured":"Gupta, S.K., Kuila, P., and Jana, P.K. (2016, January 14\u201317). Genetic Algorithm for k-Connected Relay Node Placement in Wireless Sensor Networks. Proceedings of the Second International Conference on Computer and Communication Technologies, Chengdu, China.","DOI":"10.1007\/978-81-322-2517-1_69"},{"key":"ref_28","first-page":"858021","article-title":"M-Connected Coverage Problem in Wireless Sensor Networks","volume":"2012","author":"Mini","year":"2012","journal-title":"Int. Sch. Res. Netw."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"1412","DOI":"10.1016\/j.comnet.2010.12.023","article-title":"Connected coverage in WSNs based on critical targets","volume":"55","author":"Zorbas","year":"2011","journal-title":"Comput. Netw."},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"866","DOI":"10.1016\/j.jnca.2009.01.002","article-title":"On target coverage in wireless heterogeneous sensor networks with multiple sensing units","volume":"32","author":"Shih","year":"2009","journal-title":"J. Netw. Comput. Appl."},{"key":"ref_31","unstructured":"Zhao, N.Q., and Gurusamy, M. (2006, January 19\u201321). Maximizing Network Lifetime for Connected Target Coverage in Wireless Sensor Networks. Proceedings of the IEEE International Conference on Wireless and Mobile Computing, NETWORKING and Communications, Wimob 2006, Montreal, QC, Canada."},{"key":"ref_32","doi-asserted-by":"crossref","unstructured":"Carter, B., and Ragade, R. (2009, January 17\u201319). A probabilistic model for the deployment of sensors. Proceedings of the Sensors Applications Symposium, 2009 (SAS), New Orleans, LA, USA.","DOI":"10.1109\/SAS.2009.4801767"},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1016\/j.ins.2014.08.067","article-title":"Probabilistic coverage based sensor scheduling for target tracking sensor networks","volume":"292","author":"Shi","year":"2015","journal-title":"Inf. Sci."},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1145\/1055959.1055971","article-title":"A study on object tracking quality under probabilistic coverage in sensor networks","volume":"9","author":"Ren","year":"2005","journal-title":"ACM Sigmobile Mobile Comput. Commun. Rev."},{"key":"ref_35","doi-asserted-by":"crossref","unstructured":"Wu, Y., Yin, J., Li, M., and Zhu, E. (2008, January 15\u201318). Efficient algorithms for probabilistic k-coverage in directional sensor networks. Proceedings of the International Conference on Intelligent Sensors, Sensor Networks and Information Processing, Sydney, Australia.","DOI":"10.1109\/ISSNIP.2008.4762053"},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1145\/972627.972631","article-title":"Sensor deployment and target localization in distributed sensor networks","volume":"3","author":"Zou","year":"2004","journal-title":"ACM Trans. Embed. Compu. Syst. (TECS)"},{"key":"ref_37","unstructured":"Toussaint, G. (2014, January 9\u201311). The rotating calipers: An efficient, multipurpose, computational tool. Proceedings of the International Conference on Computing Technology and Information Management (ICCTIM), Dubai, UAE."},{"key":"ref_38","doi-asserted-by":"crossref","unstructured":"Edmonds, J., and Karp, R.M. (1972). Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems, Springer-Verlag.","DOI":"10.1145\/321694.321699"},{"key":"ref_39","first-page":"754","article-title":"Algorithm for solution of a problem of maximal flow in a network with power estimation","volume":"194","author":"Dinic","year":"1970","journal-title":"Dokl. Akad. Nauk SSSR"}],"container-title":["Sensors"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1424-8220\/17\/6\/1208\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T18:36:58Z","timestamp":1760207818000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1424-8220\/17\/6\/1208"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,5,25]]},"references-count":39,"journal-issue":{"issue":"6","published-online":{"date-parts":[[2017,6]]}},"alternative-id":["s17061208"],"URL":"https:\/\/doi.org\/10.3390\/s17061208","relation":{},"ISSN":["1424-8220"],"issn-type":[{"type":"electronic","value":"1424-8220"}],"subject":[],"published":{"date-parts":[[2017,5,25]]}}}