{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,20]],"date-time":"2026-06-20T07:21:55Z","timestamp":1781940115914,"version":"3.54.5"},"reference-count":43,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2017,8,29]],"date-time":"2017-08-29T00:00:00Z","timestamp":1503964800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001809","name":"NSFC","doi-asserted-by":"crossref","award":["61528105"],"award-info":[{"award-number":["61528105"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100004731","name":"Zhejiang Provincial Natural Science Foundation","doi-asserted-by":"crossref","award":["LR16F020001"],"award-info":[{"award-number":["LR16F020001"]}],"id":[{"id":"10.13039\/501100004731","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Embed. Comput. Syst."],"published-print":{"date-parts":[[2018,1,31]]},"abstract":"<jats:p>\n            Wireless charging technology has drawn great attention of both academia and industry in recent years, due to its potential of significantly improving the system performance of sensor networks. The emergence of an open-source experimental platform for wireless rechargeable sensor networks, Powercast, has made the theoretical research closer to reality. This pioneering platform is able to recharge sensor nodes much more efficiently and allows different communication protocols to be implemented upon users\u2019 demands. Different from the RFID-based model widely used in the existing works, Powercast designs the charger and sink station separately. This leads to a new design challenge of cooperatively deploying minimum number of chargers and sink stations in wireless rechargeable sensor networks. Such a co-deployment issue is extremely challenging, since the deployments of chargers and sink stations are coupled, and each subproblem is known to be NP-hard. The key to the design is to understand the intrinsic relationship between data flow and energy flow, which is interdependent. In this article, we tackle this challenge by dividing it into two subproblems and optimizing charger and sink station deployment iteratively. Specifically, we first transform each subproblem to a max-flow problem. With this, we are able to select chargers or sink stations according to their contributions to the total flow rate. We design greedy-based algorithms with a guaranteed worst-case bound\n            <jats:italic>ln R\/\u03be<\/jats:italic>\n            for the subproblems of charger deployment and sink station deployment, respectively. Further, we address the original problem by designing an iterative algorithm that solves two subproblems alternatively to achieve a near optimal performance. We corroborate our analysis by extensive simulations under practical coefficient settings and demonstrate the advantage of the proposed algorithm.\n          <\/jats:p>","DOI":"10.1145\/3070721","type":"journal-article","created":{"date-parts":[[2017,8,29]],"date-time":"2017-08-29T17:49:18Z","timestamp":1504028958000},"page":"1-19","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":19,"title":["Near-Optimal Co-Deployment of Chargers and Sink Stations in Rechargeable Sensor Networks"],"prefix":"10.1145","volume":"17","author":[{"given":"Songyuan","family":"Li","sequence":"first","affiliation":[{"name":"Zhejiang University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Lingkun","family":"Fu","sequence":"additional","affiliation":[{"name":"State Key Laboratory of Wind Power System, Zhejiang Windey Co., Ltd."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Shibo","family":"He","sequence":"additional","affiliation":[{"name":"Zhejiang University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Youxian","family":"Sun","sequence":"additional","affiliation":[{"name":"Zhejiang University"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2017,8,29]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFCOM.2004.1354529"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comcom.2014.03.001"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/JSAC.2016.2520181"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/JIOT.2016.2517405"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2015.2388482"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFCOM.2013.6567103"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/VETECS.2011.5956204"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/TMC.2014.2307332"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/TMC.2012.161"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVT.2015.2498281"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/HICSS.2000.926982"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1126\/science.1143254"},{"key":"e_1_2_1_13_1","volume-title":"Proceedings of the 9th Workshop on Wireless, Ad hoc, and Sensor Networks.","author":"Liao J. H.","unstructured":"J. H. Liao , W. T. So , and J. R. Jiang . 2013. Optimized charger deployment for wireless rechargeable sensor networks . In Proceedings of the 9th Workshop on Wireless, Ad hoc, and Sensor Networks. Retrieved from http:\/\/wasn2013.cs.nthu.edu.tw\/paper_result.php. J. H. Liao, W. T. So, and J. R. Jiang. 2013. Optimized charger deployment for wireless rechargeable sensor networks. In Proceedings of the 9th Workshop on Wireless, Ad hoc, and Sensor Networks. Retrieved from http:\/\/wasn2013.cs.nthu.edu.tw\/paper_result.php."},{"key":"e_1_2_1_14_1","unstructured":"H. Liu. 2011. Retrieved from http:\/\/hxhl95.github.io\/media\/ib_ee.pdf.  H. Liu. 2011. Retrieved from http:\/\/hxhl95.github.io\/media\/ib_ee.pdf."},{"key":"e_1_2_1_15_1","first-page":"47","article-title":"An energy-efficient and sink location privacy enhanced scheme for WSNs through ring based routing","volume":"81","author":"Long J.","year":"2016","unstructured":"J. Long , A. Liu , M. Dong , and Z. Li . 2016 . An energy-efficient and sink location privacy enhanced scheme for WSNs through ring based routing . J. Parallel and Distrib. Comput. 81 (2016), 47 -- 65 . J. Long, A. Liu, M. Dong, and Z. Li. 2016. An energy-efficient and sink location privacy enhanced scheme for WSNs through ring based routing. J. Parallel and Distrib. Comput. 81 (2016), 47--65.","journal-title":"J. Parallel and Distrib. Comput."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/COMST.2014.2368999"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFCOM.2005.1498454"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.5772\/25348"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1140103.1140283"},{"key":"e_1_2_1_20_1","unstructured":"UMich Moo. 2011. Retrieved from https:\/\/spqr.eecs.umich.edu\/moo\/.  UMich Moo. 2011. Retrieved from https:\/\/spqr.eecs.umich.edu\/moo\/."},{"key":"e_1_2_1_21_1","unstructured":"Powercast. 2016. Retrieved from http:\/\/www.powercastco.com\/.  Powercast. 2016. Retrieved from http:\/\/www.powercastco.com\/."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICNP.2004.1348117"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/TII.2011.2174249"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/JPROC.2010.2053690"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIM.2008.925019"},{"key":"e_1_2_1_26_1","volume-title":"Proceedings of the 21st Annual International Conference on Mobile Computing and Networking. ACM","author":"Shi L.","unstructured":"L. Shi , Z. Kabelac , D. Katabi , and D. Perreault . 2015. Wireless power hotspot that charges all of your devices . In Proceedings of the 21st Annual International Conference on Mobile Computing and Networking. ACM , Paris. DOI:http:\/\/dx.doi.org\/10.1145\/278918.2790092 10.1145\/278918.2790092 L. Shi, Z. Kabelac, D. Katabi, and D. Perreault. 2015. Wireless power hotspot that charges all of your devices. In Proceedings of the 21st Annual International Conference on Mobile Computing and Networking. ACM, Paris. DOI:http:\/\/dx.doi.org\/10.1145\/278918.2790092"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/SAHCN.2014.6990382"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/2700257"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2013.153"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/1081992.1082018"},{"key":"e_1_2_1_31_1","unstructured":"STLM20. 2016. Retrieved from http:\/\/www.st.com\/content\/st_com\/zh\/products\/mems-and-sensors\/temperature-sensors\/stlm20.html.  STLM20. 2016. Retrieved from http:\/\/www.st.com\/content\/st_com\/zh\/products\/mems-and-sensors\/temperature-sensors\/stlm20.html."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDCS.2010.61"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/PERSER.2007.4283889"},{"key":"e_1_2_1_34_1","unstructured":"J. Wang A. Liu T. Yan and Z. Zeng. 2017a. A resource allocation model based on double-sided combinational auctions for transparent computing. Peer-to-Peer Networking and Applications 2017 to appear (2017).  J. Wang A. Liu T. Yan and Z. Zeng. 2017a. A resource allocation model based on double-sided combinational auctions for transparent computing. Peer-to-Peer Networking and Applications 2017 to appear (2017)."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/TMC.2016.2557792"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/JSAC.2015.2481204"},{"key":"e_1_2_1_37_1","doi-asserted-by":"crossref","unstructured":"G. Xie K. Ota M. Dong F. Pan and A. Liu. 2016. Energy-efficient routing for mobile data collectors in wireless sensor networks with obstacles. Peer to-Peer Networking and Applications 1 12 (2016) 472--483.  G. Xie K. Ota M. Dong F. Pan and A. Liu. 2016. Energy-efficient routing for mobile data collectors in wireless sensor networks with obstacles. Peer to-Peer Networking and Applications 1 12 (2016) 472--483.","DOI":"10.1007\/s12083-016-0529-1"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/MCOM.2017.1600690CM"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVT.2014.2300181"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746285.2746291"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/MASS.2012.6502505"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2015.2425146"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/TMC.2016.2549518"}],"container-title":["ACM Transactions on Embedded Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3070721","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3070721","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T03:30:27Z","timestamp":1750217427000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3070721"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,8,29]]},"references-count":43,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2018,1,31]]}},"alternative-id":["10.1145\/3070721"],"URL":"https:\/\/doi.org\/10.1145\/3070721","relation":{},"ISSN":["1539-9087","1558-3465"],"issn-type":[{"value":"1539-9087","type":"print"},{"value":"1558-3465","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,8,29]]},"assertion":[{"value":"2016-06-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-08-29","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}