{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,29]],"date-time":"2026-05-29T11:24:26Z","timestamp":1780053866487,"version":"3.54.0"},"reference-count":36,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2011,8,1]],"date-time":"2011-08-01T00:00:00Z","timestamp":1312156800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"DMEA research program","award":["H94003-07-C-0702"],"award-info":[{"award-number":["H94003-07-C-0702"]}]},{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["CCF-0702792SRS-0820034"],"award-info":[{"award-number":["CCF-0702792SRS-0820034"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Sen. Netw."],"published-print":{"date-parts":[[2011,8]]},"abstract":"<jats:p>We study the problem of planning the motion of \u201cdata mules\u201d for collecting the data from stationary sensor nodes in wireless sensor networks. Use of data mules significantly reduces energy consumption at sensor nodes compared to commonly used multihop forwarding approaches, but has a drawback in that it increases the latency of data delivery. Optimizing the motion of data mules, including path and speed, is critical for improving the data delivery latency and making the data mule approach more useful in practice. In this article, we focus on the path selection problem: finding the optimal path of data mules so that the data delivery latency can be minimized. We formulate the path selection problem as a graph problem that is capable of expressing the benefit from larger communication range. The problem is NP-hard and we present approximation algorithms for both single-data mule case and multiple-data mules case. We further consider the case in which we have only partial knowledge of communication range, where we design semionline algorithms that improve the offline plan using online knowledge at runtime. Simulation experiments on Matlab and ns2 demonstrate that our offline and semionline algorithms produce significantly shorter path lengths and data delivery latency compared to previously proposed methods, suggesting that controlled mobility can be exploited much more effectively.<\/jats:p>","DOI":"10.1145\/1993042.1993043","type":"journal-article","created":{"date-parts":[[2011,8,30]],"date-time":"2011-08-30T13:30:18Z","timestamp":1314711018000},"page":"1-27","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":70,"title":["Path Planning of Data Mules in Sensor Networks"],"prefix":"10.1145","volume":"8","author":[{"given":"Ryo","family":"Sugihara","sequence":"first","affiliation":[{"name":"University of California, San Diego"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Rajesh K.","family":"Gupta","sequence":"additional","affiliation":[{"name":"University of California, San Diego"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2011,8]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/RTCSA.2005.28"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0196-6774(03)00047-6"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/MCOM.2006.1668382"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/11523468_90"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/0207017"},{"key":"e_1_2_1_6_1","unstructured":"Ganesan D. Krishnamachari B. Woo A. Culler D. Estrin D. and Wicker S. 2002. Complex behavior at scale: An experimental study of low-power wireless sensor networks. Tech. rep. UCLA\/CSD-TR 02-0013. Department of Computer Science University of California Los Angeles Los Angeles CA. Ganesan D. Krishnamachari B. Woo A. Culler D. Estrin D. and Wicker S. 2002. Complex behavior at scale: An experimental study of low-power wireless sensor networks. Tech. rep. UCLA\/CSD-TR 02-0013. Department of Computer Science University of California Los Angeles Los Angeles CA."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comnet.2006.01.008"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/990064.990080"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(78)90011-0"},{"key":"e_1_2_1_10_1","volume-title":"TR2003-467","author":"Kotz D.","unstructured":"Kotz , D. , Newport , C. , and Elliott , C . 2003. The mistaken axioms of wireless-network research. Tech. rep . TR2003-467 . Dartmouth College Computer Science Department, Darthmouth, NH. Kotz, D., Newport, C., and Elliott, C. 2003. The mistaken axioms of wireless-network research. Tech. rep. TR2003-467. Dartmouth College Computer Science Department, Darthmouth, NH."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/941079.941089"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1236360.1236364"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/11776178_30"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2007.1070"},{"key":"e_1_2_1_15_1","doi-asserted-by":"crossref","unstructured":"Mascarenas D. Flynn E. Lin K. Farinholt K. Park G. Gupta R. Todd M. and Farrar C. 2008. Demonstration of a roving-host wireless sensor network for rapid assessment monitoring of structural health. In Smart Sensor Phenomena Technology Networks and Systems W. Ecke K. J. Peters and N. G. Meyendorf Eds. Proceedings of the SPIE vol. 6933. SPIE Bellingham WA 69330K. Mascarenas D. Flynn E. Lin K. Farinholt K. Park G. Gupta R. Todd M. and Farrar C. 2008. Demonstration of a roving-host wireless sensor network for rapid assessment monitoring of structural health. In Smart Sensor Phenomena Technology Networks and Systems W. Ecke K. J. Peters and N. G. Meyendorf Eds. Proceedings of the SPIE vol. 6933. SPIE Bellingham WA 69330K.","DOI":"10.1117\/12.775592"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1127777.1127788"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/S00361445023685"},{"key":"e_1_2_1_18_1","unstructured":"Pruhs K. Sgall J. and Torng E. 2004. Online scheduling. In Handbook of Scheduling: Algorithms Models and Performance Analysis J. Y.-T. Leung Ed. CRC Press Boca Raton FL. Pruhs K. Sgall J. and Torng E. 2004. Online scheduling. In Handbook of Scheduling: Algorithms Models and Performance Analysis J. Y.-T. Leung Ed. CRC Press Boca Raton FL."},{"key":"e_1_2_1_19_1","volume-title":"Proceedings of the 9th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications. 53--71","author":"Shih C.","unstructured":"Shih , C. , Liu , J. W. S. , and Cheong , I. K . 2003. Scheduling jobs with multiple feasible intervals . In Proceedings of the 9th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications. 53--71 . Shih, C., Liu, J. W. S., and Cheong, I. K. 2003. Scheduling jobs with multiple feasible intervals. In Proceedings of the 9th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications. 53--71."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.32.1.80"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/TMC.2006.109"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/REAL.2004.31"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/TMC.2007.57"},{"key":"e_1_2_1_24_1","volume-title":"Proceedings of IEEE Wireless Communications and Networking Conference.","volume":"4","author":"Stuedi P.","unstructured":"Stuedi , P. , Chinellato , O. , and Alonso , G . 2005. Connectivity in the presence of shadowing in 802.11 ad hoc networks . In Proceedings of IEEE Wireless Communications and Networking Conference. Vol. 4 . 2225--2230. Stuedi, P., Chinellato, O., and Alonso, G. 2005. Connectivity in the presence of shadowing in 802.11 ad hoc networks. In Proceedings of IEEE Wireless Communications and Networking Conference. Vol. 4. 2225--2230."},{"key":"e_1_2_1_25_1","volume-title":"Proceedings of the 28th IEEE International Real-Time Systems Symposium. (Work-in-progress session).","author":"Sugihara R.","unstructured":"Sugihara , R. and Gupta , R. K . 2007. Scheduling under location and time constraints for data collection in sensor networks . In Proceedings of the 28th IEEE International Real-Time Systems Symposium. (Work-in-progress session). Sugihara, R. and Gupta, R. K. 2007. Scheduling under location and time constraints for data collection in sensor networks. In Proceedings of the 28th IEEE International Real-Time Systems Symposium. (Work-in-progress session)."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-69170-9_26"},{"key":"e_1_2_1_27_1","volume-title":"Proceedings of the 28th Annual Joint Conference of the IEEE Computer and Communications Societies. (Miniconference.) 2566--2570","author":"Sugihara R.","unstructured":"Sugihara , R. and Gupta , R. K . 2009. Optimizing energy-latency trade-off in sensor networks with controlled mobility . In Proceedings of the 28th Annual Joint Conference of the IEEE Computer and Communications Societies. (Miniconference.) 2566--2570 . Sugihara, R. and Gupta, R. K. 2009. Optimizing energy-latency trade-off in sensor networks with controlled mobility. In Proceedings of the 28th Annual Joint Conference of the IEEE Computer and Communications Societies. (Miniconference.) 2566--2570."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/TMC.2009.113"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806895.1806899"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/MWC.2009.4804365"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1098918.1098936"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/RTSS.2007.40"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374618.1374650"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2007.1067"},{"key":"e_1_2_1_35_1","volume-title":"Proceedings of the IEEE Workshop on Future Trends in Distributed Computing Systems. 308--314","author":"Zhao W.","unstructured":"Zhao , W. and Ammar , M . 2003. Message ferrying: Proactive routing in highly-partitioned wireless ad hoc networks . In Proceedings of the IEEE Workshop on Future Trends in Distributed Computing Systems. 308--314 . Zhao, W. and Ammar, M. 2003. Message ferrying: Proactive routing in highly-partitioned wireless ad hoc networks. In Proceedings of the IEEE Workshop on Future Trends in Distributed Computing Systems. 308--314."},{"key":"e_1_2_1_36_1","volume-title":"Proceedings of the 24th Annual Joint Conference of the IEEE Computer and Communications Societies. 1407--1418","author":"Zhao W.","unstructured":"Zhao , W. , Ammar , M. , and Zegura , E . 2005. Controlling the mobility of multiple data transport ferries in a delay-tolerant network . In Proceedings of the 24th Annual Joint Conference of the IEEE Computer and Communications Societies. 1407--1418 . Zhao, W., Ammar, M., and Zegura, E. 2005. Controlling the mobility of multiple data transport ferries in a delay-tolerant network. In Proceedings of the 24th Annual Joint Conference of the IEEE Computer and Communications Societies. 1407--1418."}],"container-title":["ACM Transactions on Sensor Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1993042.1993043","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1993042.1993043","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T20:26:39Z","timestamp":1750278399000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1993042.1993043"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,8]]},"references-count":36,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2011,8]]}},"alternative-id":["10.1145\/1993042.1993043"],"URL":"https:\/\/doi.org\/10.1145\/1993042.1993043","relation":{},"ISSN":["1550-4859","1550-4867"],"issn-type":[{"value":"1550-4859","type":"print"},{"value":"1550-4867","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,8]]},"assertion":[{"value":"2009-05-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2010-08-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2011-08-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}