{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,26]],"date-time":"2025-09-26T00:13:45Z","timestamp":1758845625970,"version":"3.41.0"},"reference-count":34,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2015,7,23]],"date-time":"2015-07-23T00:00:00Z","timestamp":1437609600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Central Institutions of China","award":["20620140515"],"award-info":[{"award-number":["20620140515"]}]},{"name":"ANR\/RGC Joint Research Scheme","award":["A-PolyU505\/12"],"award-info":[{"award-number":["A-PolyU505\/12"]}]},{"name":"NSF","award":["CNS-1239108, CNS-1218718 and IIS-1231680"],"award-info":[{"award-number":["CNS-1239108, CNS-1218718 and IIS-1231680"]}]},{"name":"NSF of Jiangsu Province","award":["BK20141319"],"award-info":[{"award-number":["BK20141319"]}]},{"name":"the State Key Development Program for Basic Research of China","award":["2012CB316201"],"award-info":[{"award-number":["2012CB316201"]}]},{"name":"NUPTSF","award":["NY214169"],"award-info":[{"award-number":["NY214169"]}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"crossref","award":["61472252, 61321491, 61133006, 61373130 and 61422208"],"award-info":[{"award-number":["61472252, 61321491, 61133006, 61373130 and 61422208"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"name":"CCF-Tencent Open Fund"},{"name":"EU FP7 CROWN","award":["PIRSES-GA-2013-610524"],"award-info":[{"award-number":["PIRSES-GA-2013-610524"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Sen. Netw."],"published-print":{"date-parts":[[2015,12,23]]},"abstract":"<jats:p>Multihop broadcasting in low-duty-cycle Wireless Sensor Networks (WSNs) is a very challenging problem, since every node has its own working schedule. Existing solutions usually use unicast instead of broadcast to forward packets from a node to its neighbors according to their working schedules, which is, however, not energy efficient. In this article, we propose to exploit the broadcast nature of wireless media to further save energy for low-duty-cycle networks, by adopting a novel broadcasting communication model. The key idea is to let some early wake-up nodes postpone their wake-up slots to overhear broadcasting messages from its neighbors. This model utilizes the spatiotemporal locality of broadcast to reduce the total energy consumption, which can be essentially characterized by the total number of broadcasting message transmissions. Based on such model, we aim at minimizing the total number of broadcasting message transmissions of a broadcast for low-duty-cycle WSNs, subject to the constraint that the broadcasting latency is optimal. We prove that it is NP-hard to find the optimal solution, and design an approximation algorithm that can achieve a polylogarithmic approximation ratio. Extensive simulation results show that our algorithm outperforms the traditional solutions in terms of energy efficiency.<\/jats:p>","DOI":"10.1145\/2753763","type":"journal-article","created":{"date-parts":[[2015,7,27]],"date-time":"2015-07-27T13:33:00Z","timestamp":1438003980000},"page":"1-31","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":30,"title":["Optimizing Energy Efficiency for Minimum Latency Broadcast in Low-Duty-Cycle Sensor Networks"],"prefix":"10.1145","volume":"11","author":[{"given":"Lijie","family":"Xu","sequence":"first","affiliation":[{"name":"Nanjing University of Posts and Telecommunications, Nanjing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Guihai","family":"Chen","sequence":"additional","affiliation":[{"name":"Nanjing University, Nanjing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jiannong","family":"Cao","sequence":"additional","affiliation":[{"name":"The Hong Kong Polytechnic University, Kowloon, Hong Kong"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shan","family":"Lin","sequence":"additional","affiliation":[{"name":"Stony Brook University, NY, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Haipeng","family":"Dai","sequence":"additional","affiliation":[{"name":"Nanjing University, Nanjing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xiaobing","family":"Wu","sequence":"additional","affiliation":[{"name":"Nanjing University, Nanjing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Fan","family":"Wu","sequence":"additional","affiliation":[{"name":"Shanghai Jiao Tong University, Shanghai, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2015,7,23]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.5555\/1147685.1147691"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFCOM.2013.6566933"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comcom.2014.03.001"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/VETECF.2010.5594513"},{"volume-title":"Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). Society for Industrial and Applied Mathematics, 253--259","author":"Garg Naveen","key":"e_1_2_1_5_1","unstructured":"Naveen Garg , Goran Konjevod , and R. Ravi . 1998. A polylogarithmic approximation algorithm for the group Steiner tree problem . In Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). Society for Industrial and Applied Mathematics, 253--259 . Naveen Garg, Goran Konjevod, and R. Ravi. 1998. A polylogarithmic approximation algorithm for the group Steiner tree problem. In Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). Society for Industrial and Applied Mathematics, 253--259."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1322263.1322294"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1614320.1614336"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICNP.2011.6089078"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2012.2212452"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/MCOM.2013.6553686"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2491288.2491326"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.5555\/820264.820485"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVT.2009.2030203"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDCS.2010.20"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/MOBHOC.2006.278671"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.5555\/1833515.1833749"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-13651-1_12"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1498915.1498916"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2512448"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICPP.2011.56"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2012.216"},{"key":"e_1_2_1_22_1","volume-title":"CitySee: Not only a wireless sensor network","author":"Liu Yunhao","year":"2013","unstructured":"Yunhao Liu , Xufei Mao , Yuan He , Kebin Liu , Wei Gong , and Jiliang Wang . 2013b. CitySee: Not only a wireless sensor network . IEEE Network ( 2013 ), 42--47. Yunhao Liu, Xufei Mao, Yuan He, Kebin Liu, Wei Gong, and Jiliang Wang. 2013b. CitySee: Not only a wireless sensor network. IEEE Network (2013), 42--47."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1031495.1031501"},{"key":"e_1_2_1_24_1","volume-title":"Proceedings of IEEE Wireless Communications and Networking Conference (WCNC). IEEE, 1261--1266","author":"Niu Jianwei","year":"2013","unstructured":"Jianwei Niu , Long Cheng , Yu Gu , Junghyun Jun , and Qingquan Zhang . 2013 . Minimum-delay and energy-efficient flooding tree in asynchronous low-duty-cycle wireless sensor networks . In Proceedings of IEEE Wireless Communications and Networking Conference (WCNC). IEEE, 1261--1266 . Jianwei Niu, Long Cheng, Yu Gu, Junghyun Jun, and Qingquan Zhang. 2013. Minimum-delay and energy-efficient flooding tree in asynchronous low-duty-cycle wireless sensor networks. In Proceedings of IEEE Wireless Communications and Networking Conference (WCNC). IEEE, 1261--1266."},{"volume-title":"Graph-Theoretic Concepts in Computer Science","author":"Reich Gabriele","key":"e_1_2_1_25_1","unstructured":"Gabriele Reich and Peter Widmayer . 1990. Beyond Steiner\u2019s problem: A VLSI oriented generalization . In Graph-Theoretic Concepts in Computer Science . Springer , 196--210. Gabriele Reich and Peter Widmayer. 1990. Beyond Steiner\u2019s problem: A VLSI oriented generalization. In Graph-Theoretic Concepts in Computer Science. Springer, 196--210."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICNP.2009.5339689"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1644038.1644044"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1460412.1460414"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFCOM.2009.5061952"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2012.207"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/SAHCN.2006.288433"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/MASS.2013.47"},{"key":"e_1_2_1_33_1","volume-title":"2013 IEEE Global Communications Conference (GLOBECOM). IEEE, 7--12","author":"Xu Lijie","year":"2013","unstructured":"Lijie Xu and Guihai Chen . 2013 . LBcast: Load-balanced broadcast scheduling for low-duty-cycle wireless sensor networks . In 2013 IEEE Global Communications Conference (GLOBECOM). IEEE, 7--12 . Lijie Xu and Guihai Chen. 2013. LBcast: Load-balanced broadcast scheduling for low-duty-cycle wireless sensor networks. In 2013 IEEE Global Communications Conference (GLOBECOM). IEEE, 7--12."},{"key":"e_1_2_1_34_1","volume-title":"Proceedings of NSDI. USENIX, 49--64","author":"Zhu Ting","year":"2010","unstructured":"Ting Zhu , Ziguo Zhong , Tian He , and Zhi-Li Zhang . 2010 . Exploring link correlation for efficient flooding in wireless sensor networks . In Proceedings of NSDI. USENIX, 49--64 . Ting Zhu, Ziguo Zhong, Tian He, and Zhi-Li Zhang. 2010. Exploring link correlation for efficient flooding in wireless sensor networks. In Proceedings of NSDI. USENIX, 49--64."}],"container-title":["ACM Transactions on Sensor Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2753763","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2753763","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T06:16:39Z","timestamp":1750227399000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2753763"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,7,23]]},"references-count":34,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2015,12,23]]}},"alternative-id":["10.1145\/2753763"],"URL":"https:\/\/doi.org\/10.1145\/2753763","relation":{},"ISSN":["1550-4859","1550-4867"],"issn-type":[{"type":"print","value":"1550-4859"},{"type":"electronic","value":"1550-4867"}],"subject":[],"published":{"date-parts":[[2015,7,23]]},"assertion":[{"value":"2014-05-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-07-23","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}