{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T04:11:24Z","timestamp":1760242284896,"version":"build-2065373602"},"reference-count":27,"publisher":"MDPI AG","issue":"2","license":[{"start":{"date-parts":[[2017,2,22]],"date-time":"2017-02-22T00:00:00Z","timestamp":1487721600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"the Natural Science Foundation of China","award":["61601157"],"award-info":[{"award-number":["61601157"]}]},{"name":"Chinese Scholarship Council","award":["201208330096"],"award-info":[{"award-number":["201208330096"]}]},{"name":"the Scienti\ufb01c Research Foundation for the Returned Overseas Chinese Scholars (State Education Ministry, China)"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Sensors"],"abstract":"<jats:p>In addition to the traditional densely deployed cases, widely distributed wireless sensor networks (WDWSNs) have begun to emerge. In these networks, sensors are far away from each other and have no network connections. In this paper, a special application of data collection for WDWSNs is considered where each sensor (Unmanned Ground Vehicle, UGV) moves in a hazardous and complex terrain with many obstacles. They have their own work cycles and can be accessed only at a few locations. A mobile sink cruises on the ground to collect data gathered from these UGVs. Considerable delay is inevitable if the UGV and the mobile sink miss the meeting window or wait idly at the meeting spot. The unique challenge here is that, for each cycle of an UGV, there is only a limited time window for it to appear in front of the mobile sink. Therefore, we propose scheduling the path of a single mobile sink, targeted at visiting a maximum number of UGVs in a timely manner with the shortest path, according to the timing constraints bound by the cycles of UGVs. We then propose a bipartite matching based algorithm to reduce the number of mobile sinks. Simulation results show that the proposed algorithm can achieve performance close to the theoretical maximum determined by the duty cycle instance.<\/jats:p>","DOI":"10.3390\/s17020421","type":"journal-article","created":{"date-parts":[[2017,2,22]],"date-time":"2017-02-22T11:36:58Z","timestamp":1487763418000},"page":"421","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Efficient Data Collection in Widely Distributed Wireless Sensor Networks with Time Window and Precedence Constraints"],"prefix":"10.3390","volume":"17","author":[{"given":"Peng","family":"Liu","sequence":"first","affiliation":[{"name":"Key Laboratory of Complex Systems Modeling and Simulation, School of Computer Science, Hangzhou Dianzi University, Hangzhou 310018, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tingting","family":"Fu","sequence":"additional","affiliation":[{"name":"Key Laboratory of Complex Systems Modeling and Simulation, School of Computer Science, Hangzhou Dianzi University, Hangzhou 310018, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jia","family":"Xu","sequence":"additional","affiliation":[{"name":"Key Laboratory of Complex Systems Modeling and Simulation, School of Computer Science, Hangzhou Dianzi University, Hangzhou 310018, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yue","family":"Ding","sequence":"additional","affiliation":[{"name":"Key Laboratory of Complex Systems Modeling and Simulation, School of Computer Science, Hangzhou Dianzi University, Hangzhou 310018, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2017,2,22]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"334","DOI":"10.1007\/s11704-010-0123-2","article-title":"Long-term large-scale sensing in the forest: Recent advances and future directions of GreenOrbs","volume":"4","author":"Liu","year":"2010","journal-title":"Front. Comput. Sci. China"},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"42","DOI":"10.1109\/MNET.2013.6616114","article-title":"CitySee: Not only a wireless sensor network","volume":"27","author":"Liu","year":"2013","journal-title":"IEEE Netw."},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Zheng, H., and Wu, J. (2015, January 22\u201325). Data Collection and Event Detection in the Deep Sea with Delay Minimization. Proceedings of the 2015 12th Annual IEEE International Conference on Sensing, Communication, and Networking (SECON), Seattle, WA, USA.","DOI":"10.1109\/SAHCN.2015.7338335"},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"292","DOI":"10.1109\/TRO.2006.870627","article-title":"Moth-inspired chemical plume tracing on an autonomous underwater vehicle","volume":"22","author":"Li","year":"2006","journal-title":"IEEE Trans. Robot."},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Calvo, O., Sousa, A., Rozenfeld, A., and Acosta, G. (2009, January 23\u201326). Smooth path planning for autonomous pipeline inspections. Proceedings of the 6th International Multi-Conference on Systems, Signals and Devices, Sharjah, UAE.","DOI":"10.1109\/SSD.2009.4956800"},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1016\/j.adhoc.2005.01.004","article-title":"Underwater acoustic sensor networks: Research challenges","volume":"3","author":"Akyildiz","year":"2005","journal-title":"Ad Hoc Netw."},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Tokekar, P., Hook, J.V., Mulla, D., and Isler, V. (2013, January 3\u20137). Sensor planning for a symbiotic UAV and UGV system for precision agriculture. Proceedings of the 2013 IEEE\/RSJ International Conference on Intelligent Robots and Systems (IROS), Tokyo, Japan.","DOI":"10.1109\/IROS.2013.6697126"},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"1920","DOI":"10.1109\/TMC.2012.152","article-title":"Distributed Algorithm for Lifetime Maximization in a Delay-Tolerant Wireless Sensor Network with a Mobile Sink","volume":"12","author":"Yun","year":"2013","journal-title":"IEEE Trans. Mob. Comput."},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Nesamony, S., Vairamuthu, M., and Orlowska, M. (2007, January 6\u20138). On Optimal Route of a Calibrating Mobile Sink in a Wireless Sensor Network. Proceedings of the Fourth International Conference on Networked Sensing Systems (INSS \u201907), Braunschweig, Germany.","DOI":"10.1109\/INSS.2007.4297389"},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Alnabelsi, S.H., Almasaeid, H.M., and Kamal, A.E. (2010, January 22\u201325). Optimized sink mobility for energy and delay efficient data collection in FWSNs. Proceedings of the IEEE Symposium on Computers and Communications (ISCC 2010), Riccione, Italy.","DOI":"10.1109\/ISCC.2010.5546655"},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Shi, Y., Xie, L., Hou, Y.T., and Sherali, H.D. (2011, January 10\u201315). On renewable sensor networks with wireless energy transfer. Proceedings of the The 30th IEEE International Conference on Computer Communications (INFOCOM 2011), Shanghai, China.","DOI":"10.1109\/INFCOM.2011.5934919"},{"key":"ref_12","unstructured":"Kindervater, G.A.P., Lenstra, J.K., and Savelsbergh, M.W.P. (1990). Sequential and Parallel Local Search for the Time-Constrained Travelling Salesman Problem, Technische Universiteit Eindhoven. Technical Report."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"231","DOI":"10.1111\/j.1475-3995.2000.tb00196.x","article-title":"A Travelling Salesman Problem with Allocation, Time window and Precedence constraints\u2014An application to ship scheduling","volume":"7","author":"Fagerholt","year":"2000","journal-title":"Int. Trans. Oper. Res."},{"key":"ref_14","unstructured":"Zhu, Y. (2000). The Multi-Traveling Salesman Problem with Time Window and Precedence Constraints and Its Algorithm. [Master\u2019s Thesis, Fudan University]."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"690","DOI":"10.1109\/TMC.2015.2424430","article-title":"Maximizing Data Collection Throughput on a Path in Energy Harvesting Sensor Networks Using a Mobile Sink","volume":"15","author":"Mehrabi","year":"2016","journal-title":"IEEE Trans. Mob. Comput."},{"key":"ref_16","doi-asserted-by":"crossref","unstructured":"Rasul, A., and Erlebach, T. (2015, January 19\u201322). An Energy Efficient and Restricted Tour Construction for Mobile Sink in Wireless Sensor Networks. Proceedings of the 2015 IEEE 12th International Conference on Mobile Ad Hoc and Sensor Systems (MASS), Dallas, TX, USA.","DOI":"10.1109\/MASS.2015.41"},{"key":"ref_17","first-page":"3177","article-title":"On Maximizing the Lifetime of Wireless Sensor Networks in Event-Driven Applications With Mobile Sinks","volume":"64","author":"Tashtarian","year":"2015","journal-title":"IEEE Trans. Veh. Technol."},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Tang, J., Guo, S., and Yang, Y. (2015, January 8\u201312). Delivery latency minimization in wireless sensor networks with mobile sink. Proceedings of the IEEE International Conference on Communications (ICC), London, UK.","DOI":"10.1109\/ICC.2015.7249357"},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"871","DOI":"10.1109\/TNET.2009.2033472","article-title":"Joint Sink Mobility and Routing to Maximize the Lifetime of Wireless Sensor Networks: The Case of Constrained Mobility","volume":"18","author":"Luo","year":"2010","journal-title":"IEEE\/ACM Trans. Netw."},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"Jo, Y. (2015). Communication Availability-Based Scheduling for Fair Data Collection with Path-Constrained Mobile Sink in Wireless Sensor Networks. Int. J. Distrib. Sens. Netw., 2015.","DOI":"10.1155\/2015\/287935"},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"2019","DOI":"10.1109\/ACCESS.2016.2558196","article-title":"Cluster-Based Routing for the Mobile Sink in Wireless Sensor Networks With Obstacles","volume":"4","author":"Xie","year":"2016","journal-title":"IEEE Access"},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"Aldabbas, O., Abuarqoub, A., Hammoudeh, M., Raza, U., and Bounceur, A. (2016). Unmanned Ground Vehicle for Data Collection in Wireless Sensor Networks: Mobility-aware Sink Selection. Open Autom. Control Syst. J., 2016.","DOI":"10.2174\/1874444301608010035"},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Basagni, S., B\u00f6l\u00f6ni, L., Gjanci, P., Petrioli, C., Phillips, C.A., and Turgut, D. (May, January 27). Maximizing the value of sensed information in underwater wireless sensor networks via an autonomous underwater vehicle. Proceedings of the IEEE INFOCOM 2014\u2014IEEE Conference on Computer Communications, Toronto, ON, Canada.","DOI":"10.1109\/INFOCOM.2014.6848028"},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1016\/j.orl.2005.01.009","article-title":"The multiple TSP with time windows: Vehicle bounds based on precedence graphs","volume":"34","author":"Krishnamurti","year":"2006","journal-title":"Oper. Res. Lett."},{"key":"ref_25","first-page":"39","article-title":"Precedence and Time Windows Constrained Travelling Salesman Problem (TSP) in Maritime Surveillance","volume":"17","author":"Ng","year":"2014","journal-title":"J. Battlef. Technol."},{"key":"ref_26","unstructured":"Assignment Problem and Hungarian Algorithm. Available online: https:\/\/www.topcoder.com\/community\/data-science\/data-science-tutorials\/assignment-problem-and-hungarian-algorithm\/."},{"key":"ref_27","doi-asserted-by":"crossref","unstructured":"Bondy, J., and Murty, U. (1976). Graph Theory with Applications, Elsevier Science Publishing Co., Inc.. [1st ed.].","DOI":"10.1007\/978-1-349-03521-2"}],"container-title":["Sensors"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1424-8220\/17\/2\/421\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T18:28:51Z","timestamp":1760207331000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1424-8220\/17\/2\/421"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,2,22]]},"references-count":27,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2017,2]]}},"alternative-id":["s17020421"],"URL":"https:\/\/doi.org\/10.3390\/s17020421","relation":{},"ISSN":["1424-8220"],"issn-type":[{"type":"electronic","value":"1424-8220"}],"subject":[],"published":{"date-parts":[[2017,2,22]]}}}