{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T04:26:00Z","timestamp":1760243160224,"version":"build-2065373602"},"reference-count":41,"publisher":"MDPI AG","issue":"12","license":[{"start":{"date-parts":[[2015,12,11]],"date-time":"2015-12-11T00:00:00Z","timestamp":1449792000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100001809","name":"NSFC","doi-asserted-by":"publisher","award":["61033015","60933001"],"award-info":[{"award-number":["61033015","60933001"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"name":"National Grand Fundamental Research 973 Program","award":["2012CB316200"],"award-info":[{"award-number":["2012CB316200"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Sensors"],"abstract":"<jats:p>Multicasting is a fundamental network service for one-to-many communications in wireless sensor networks. However, when the sensor nodes work in an asynchronous duty-cycled way, the sender may need to transmit the same message several times to one group of its neighboring nodes, which complicates the minimum energy multicasting problem. Thus, in this paper, we study the problem of minimum energy multicasting with adjusted power (the MEMAP problem) in the duty-cycled sensor networks, and we prove it to be NP-hard. To solve such a problem, the concept of an auxiliary graph is proposed to integrate the scheduling problem of the transmitting power and transmitting time slot and the constructing problem of the minimum multicast tree in MEMAP, and a greedy algorithm is proposed to construct such a graph. Based on the proposed auxiliary graph, an approximate scheduling and constructing algorithm with an approximation ratio of                                        4               l               n               K                                  is proposed, where K is the number of destination nodes. Finally, the theoretical analysis and experimental results verify the efficiency of the proposed algorithm in terms of the energy cost and transmission redundancy.<\/jats:p>","DOI":"10.3390\/s151229860","type":"journal-article","created":{"date-parts":[[2015,12,14]],"date-time":"2015-12-14T02:57:29Z","timestamp":1450061849000},"page":"31224-31243","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":18,"title":["Energy-Efficient Algorithm for Multicasting in Duty-Cycled Sensor Networks"],"prefix":"10.3390","volume":"15","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3589-648X","authenticated-orcid":false,"given":"Quan","family":"Chen","sequence":"first","affiliation":[{"name":"School of Computer Science and Technology, Harbin Institute of Technology, 92 West Dazhi Street, Harbin 150001, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1263-9907","authenticated-orcid":false,"given":"Siyao","family":"Cheng","sequence":"additional","affiliation":[{"name":"School of Computer Science and Technology, Harbin Institute of Technology, 92 West Dazhi Street, Harbin 150001, China"}]},{"given":"Hong","family":"Gao","sequence":"additional","affiliation":[{"name":"School of Computer Science and Technology, Harbin Institute of Technology, 92 West Dazhi Street, Harbin 150001, China"}]},{"given":"Jianzhong","family":"Li","sequence":"additional","affiliation":[{"name":"School of Computer Science and Technology, Harbin Institute of Technology, 92 West Dazhi Street, Harbin 150001, China"}]},{"given":"Zhipeng","family":"Cai","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Georgia State University, Atlanta, GA 30303, USA"}]}],"member":"1968","published-online":{"date-parts":[[2015,12,11]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","unstructured":"Chen, Q., Cheng, S.Y., Gao, H., and Cai, Z.P. (2015, January 22\u201323). Approximate Scheduling and Constructing Algorithms for Minimum-Energy Multicasting in Duty-Cycled Sensor Networks. Proceedings of the International Conference on Identification, Information, and Knowledge in the Internet of Things (IIKI), Beijing, China.","DOI":"10.1109\/IIKI.2015.42"},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1138127.1138128","article-title":"VigilNet: An Integrated Sensor Network System for Energy-Efficient Surveillance","volume":"2","author":"He","year":"2006","journal-title":"ACM TOSN"},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"417","DOI":"10.1109\/TNSM.2014.2346080","article-title":"A Biology-Based Algorithm to Minimal Exposure Problem of Wireless Sensor Networks","volume":"11","author":"Song","year":"2014","journal-title":"IEEE Trans. Netw. Service Manag."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"2292","DOI":"10.1016\/j.comnet.2008.04.002","article-title":"Wireless Sensor Network Survey","volume":"52","author":"Yick","year":"2008","journal-title":"Comput. Netw."},{"key":"ref_5","unstructured":"Gao, J., Li, J., Cai, Z., and Gao, H. (May, January 26). Composite Event Coverage in Wireless Sensor Networks with Heterogeneous Sensors. Proceedings of the 34th IEEE International Conference on Computer Communications (IEEE INFOCOM), Hong Kong, China."},{"key":"ref_6","unstructured":"Cheng, S., Cai, Z., Li, J., and Fang, X. (May, January 26). Drawing Dominant Dataset From Big Sensory Data in Wireless Sensor Networks. Proceedings of the 34th IEEE International Conference on Computer Communications (IEEE INFOCOM), Hong Kong, China."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"5415","DOI":"10.1016\/j.tcs.2009.05.013","article-title":"A 3.4713-approximation algorithm for the capacitated multicast tree routing problem","volume":"410","author":"Cai","year":"2009","journal-title":"Theor. Comput. Sci."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"240","DOI":"10.1016\/j.tcs.2009.05.031","article-title":"Size-constrained tree partitioning: Approximating the multicast k-tree routing problem","volume":"412","author":"Cai","year":"2011","journal-title":"Theor. Comput. Sci."},{"key":"ref_9","first-page":"136","article-title":"Improved Approximation Algorithms for the Capacitated Multicast Routing Problem","volume":"8881","author":"Cai","year":"2005","journal-title":"COCOON"},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"381","DOI":"10.1016\/j.tcs.2015.07.056","article-title":"Approximate Aggregation for Tracking Quantiles in Wireless Sensor Networks","volume":"607","author":"He","year":"2015","journal-title":"Theor. Comput. Sci."},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Zheng, X., Li, J., Gao, H., and Cai, Z. (2014, January 11\u201314). Capacity of Wireless Networks with Multiple Types of Multicast Sessions. Proceedings of the 25th ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc), Philadelphia, PA, USA.","DOI":"10.1145\/2632951.2632985"},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Yao, Y.J., and Cao, Q. (2013, January 14\u201316). EDAL: An Energy-Efficient, Delay-Aware, and Lifetime-Balancing Data Collection Protocol for Wireless Sensor Networks. Proceedings of the 10th IEEE International Conference on Mobile Ad-Hoc and Sensor Systems (IEEE MASS), Hangzhou, China.","DOI":"10.1109\/MASS.2013.44"},{"key":"ref_13","unstructured":"Liu, X., Luo, J., and Vasilakos, A. (2011, January 27\u201330). Compressed Data Aggregation for Energy Efficient Wireless Sensor Networks. Proceedings of the 8th Annual IEEE Communications Society Conference on Sensor, Mesh and Ad Hoc Communications and Networks (SECON), Salt Lake City, UT, USA."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"2188","DOI":"10.1109\/TPDS.2014.2345257","article-title":"CDC: Compressive Data Collection for Wireless Sensor Networks","volume":"26","author":"Liu","year":"2015","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1109\/MCOM.2013.6553686","article-title":"Algorithm Design for Data Communications in Duty-Cycled Wireless Sensor Networks: A survey","volume":"51","author":"Han","year":"2013","journal-title":"IEEE Commun. Mag."},{"key":"ref_16","doi-asserted-by":"crossref","unstructured":"Gu, Y., He, T., Lin, M., and Xu, J. (2009, January 1\u20134). Spatiotemporal Delay Control for Low-Duty-Cycle Sensor Networks. Proceedings of the 30th Real-Time Systems Symposium (RTSS), Washington, DC, USA.","DOI":"10.1109\/RTSS.2009.12"},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"1741","DOI":"10.1109\/TMC.2010.266","article-title":"Dynamic Switching-Based Data Forwarding for Low-Duty-Cycle Wireless Sensor Networks","volume":"10","author":"Gu","year":"2011","journal-title":"IEEE Trans. Mob. Comput."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"767","DOI":"10.1109\/TMC.2011.94","article-title":"On Reliable Broadcast in Low Duty-Cycle Wireless Sensor Networks","volume":"11","author":"Wang","year":"2012","journal-title":"IEEE Trans. Mob. Comput."},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Cheng, L., Gu, Y., He, T., and Niu, J. (2013, January 14\u201319). Dynamic Switching-Based Reliable Flooding in Low-Duty-Cycle Wireless Sensor Networks. Proceedings of the 32nd IEEE International Conference on Computer Communications (IEEE INFOCOM), Turin, Italy.","DOI":"10.1109\/INFCOM.2013.6566933"},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1007\/s11276-012-0457-9","article-title":"Directional routing and scheduling for green vehicular delay tolerant networks","volume":"19","author":"Zeng","year":"2013","journal-title":"Wirel. Netw."},{"key":"ref_21","doi-asserted-by":"crossref","unstructured":"Meng, T., Wu, F., and Yang, Z. (2015). Spatial Reusability-Aware Routing in Multi-Hop Wireless Networks. IEEE Trans. Comput.","DOI":"10.1109\/TC.2015.2417543"},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"1270","DOI":"10.1109\/TC.2011.145","article-title":"Approximating Congestion + Dilation in Networks via \u201cQuality of Routing\u201d Games","volume":"61","author":"Busch","year":"2012","journal-title":"IEEE Trans. Comput."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"3264","DOI":"10.1109\/TPDS.2013.2297105","article-title":"Reliable Multicast with Pipelined Network Coding Using Opportunistic Feeding and Routing","volume":"25","author":"Li","year":"2014","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"2238","DOI":"10.1016\/j.mcm.2010.10.008","article-title":"Flooding-limited and multi-constrained QoS multicast routing based on the genetic algorithm for MANETs","volume":"53","author":"Yen","year":"2011","journal-title":"Math. Comput. Model."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"1205","DOI":"10.1109\/TMC.2009.17","article-title":"Dynamic Multiresolution Data Dissemination in Wireless Sensor Networks","volume":"8","author":"Xing","year":"2009","journal-title":"IEEE Trans. Mob. Comput."},{"key":"ref_26","unstructured":"Wieselthier, J., Nguyen, G., and Ephremides, A. (2000, January 26\u201330). On the construction of energy-efficient broadcast and multicast trees in wireless networks. Proceedings of the 19th IEEE International Conference on Computer Communications (IEEE INFOCOM), Tel Aviv, Israel."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"507","DOI":"10.1109\/TNET.2004.828940","article-title":"Minimum-power multicast routing in static ad hoc wireless networks","volume":"12","author":"Wan","year":"2004","journal-title":"IEEE\/ACM Trans. Netw."},{"key":"ref_28","doi-asserted-by":"crossref","unstructured":"Cagalj, M., Phubaux, J., and Enz, C. (2002, January 23\u201328). Minimum-Energy Broadcast in All-Wireless Networks: NP-Completeness and Distribution Issues. Proceedings of the 8th Annual International Conference on Mobile Computing and Networking (MOBICOM), Atlanta, GA, USA.","DOI":"10.1145\/570645.570667"},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"377","DOI":"10.1109\/TMC.2006.1599406","article-title":"Approximate minimum-energy multicasting in wireless ad hoc networks","volume":"5","author":"Liang","year":"2006","journal-title":"IEEE Trans. Mob. Comput."},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"5490","DOI":"10.1109\/TWC.2009.070602","article-title":"Minimum-energy all-toall multicasting in wireless ad hoc networks","volume":"8","author":"Liang","year":"2009","journal-title":"IEEE Trans. Wirel. Commun."},{"key":"ref_31","unstructured":"Qiu, C., Shen, H., and Yu, L. (May, January 27). Energy-efficient cooperative broadcast in fading wireless networks. Proceedings of the 33rd IEEE International Conference on Computer Communications (IEEE INFOCOM), Toronto, ON, Canada."},{"key":"ref_32","doi-asserted-by":"crossref","unstructured":"Baghaie, M., and Krishnamachari, B. (2011, January 10\u201315). Delay constrained minimum energy broadcast in cooperative wireless networks. Proceedings of the 30th IEEE International Conference on Computer Communications (IEEE INFOCOM), Shanghai, China.","DOI":"10.1109\/INFCOM.2011.5935310"},{"key":"ref_33","doi-asserted-by":"crossref","unstructured":"Lai, S., and Ravindran, B. (2010, January 21\u201323). On multihop broadcast over adaptively duty-cycled wirelss sensor network. Proceedings of the 6th IEEE International on Distributed Computing in Sensor Systems(DCOSS), Santa Barbara, CA, USA.","DOI":"10.1007\/978-3-642-13651-1_12"},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"307","DOI":"10.1109\/TVT.2009.2030203","article-title":"Minimum-transmission broadcast in uncoordinated duty-cycled wireless ad hoc networks","volume":"59","author":"Hong","year":"2010","journal-title":"IEEE Trans. Veh. Technol."},{"key":"ref_35","doi-asserted-by":"crossref","unstructured":"Su, L., Ding, B., Yang, Y., Abdelzaher, T.F., Cao, G., and Hou, J.C. (2009, January 13\u201316). Ocast: Optimal multicast routing protocol for wireless sensor networks. Proceedings of the 17th annual IEEE International Conference on Network Protocols (ICNP), Princeton, NJ, USA.","DOI":"10.1109\/ICNP.2009.5339689"},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"910","DOI":"10.1109\/TNET.2012.2212452","article-title":"Duty-Cycle-Aware Minimum-Energy Multicasting in Wireless Sensor Networks","volume":"21","author":"Han","year":"2013","journal-title":"IEEE Trans. Netw."},{"key":"ref_37","unstructured":"Gerharz, M., de Waal, C., Martini, P., and James, P. (2003, January 20\u201322). A Cooperative Nearest Neighbours Topology Control Algorithm for Wireless Ad Hoc Networks. Proceedings of the 12th International Conference on Computer Communications and Networks, Dallas, TX, USA."},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"104","DOI":"10.1006\/jagm.1995.1029","article-title":"A nearly best-possible approximation algorithm for node-weighted Steiner tree","volume":"19","author":"Klein","year":"1995","journal-title":"J. Algorithms"},{"key":"ref_39","doi-asserted-by":"crossref","first-page":"818","DOI":"10.1109\/TC.2013.229","article-title":"Physarum Optimization: A Biology-Inspired Algorithm for the Steiner Tree Problem in Networks","volume":"64","author":"Liu","year":"2013","journal-title":"IEEE Trans. Comput."},{"key":"ref_40","unstructured":"Chipcon, CC2420 Data Sheet. Available online: http:\/\/www.ti.com\/."},{"key":"ref_41","doi-asserted-by":"crossref","first-page":"3182","DOI":"10.1109\/TWC.2006.04861","article-title":"Randomly duty-cycled wireless sensor networks: Dynamics of coverage","volume":"5","author":"Hsin","year":"2006","journal-title":"IEEE Trans. Wirel. Commun."}],"container-title":["Sensors"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1424-8220\/15\/12\/29860\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T20:53:57Z","timestamp":1760216037000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1424-8220\/15\/12\/29860"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,12,11]]},"references-count":41,"journal-issue":{"issue":"12","published-online":{"date-parts":[[2015,12]]}},"alternative-id":["s151229860"],"URL":"https:\/\/doi.org\/10.3390\/s151229860","relation":{},"ISSN":["1424-8220"],"issn-type":[{"type":"electronic","value":"1424-8220"}],"subject":[],"published":{"date-parts":[[2015,12,11]]}}}