{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T04:30:47Z","timestamp":1760243447861,"version":"build-2065373602"},"reference-count":37,"publisher":"MDPI AG","issue":"4","license":[{"start":{"date-parts":[[2013,4,12]],"date-time":"2013-04-12T00:00:00Z","timestamp":1365724800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/3.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Sensors"],"abstract":"<jats:p>Broadcasting is a common and basic operation used to support various network protocols in wireless networks. To achieve energy-efficient broadcasting is especially important for ad hoc wireless sensor networks because sensors are generally powered by batteries with limited lifetimes. Energy consumption for broadcast operations can be reduced by minimizing the number of relay nodes based on the observation that data transmission processes consume more energy than data reception processes in the sensor nodes, and how to improve the network lifetime is always an interesting issue in sensor network research. The minimum-energy broadcast problem is then equivalent to the problem of finding the minimum Connected Dominating Set (CDS) for a connected graph that is proved NP-complete. In this paper, we introduce an Efficient Minimum CDS algorithm (EMCDS) with help of a proposed ordered sequence list. EMCDS does not concern itself with node energy and broadcast operations might fail if relay nodes are out of energy. Next we have proposed a Minimum Energy-consumption Broadcast Scheme (MEBS) with a modified version of EMCDS, and aimed at providing an efficient scheduling scheme with maximized network lifetime. The simulation results show that the proposed EMCDS algorithm can find smaller CDS compared with related works, and the MEBS can help to increase the network lifetime by efficiently balancing energy among nodes in the networks.<\/jats:p>","DOI":"10.3390\/s130404922","type":"journal-article","created":{"date-parts":[[2013,4,12]],"date-time":"2013-04-12T12:19:57Z","timestamp":1365769197000},"page":"4922-4946","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":18,"title":["Energy-Efficient Algorithm for Broadcasting in Ad Hoc Wireless Sensor Networks"],"prefix":"10.3390","volume":"13","author":[{"given":"Naixue","family":"Xiong","sequence":"first","affiliation":[{"name":"School of Information Technology, Jiangxi University of Finance and Economics,  Nanchang 330013, China"},{"name":"School of Computer Science, Colorado Technical University, Colorado Spring, CO 80907, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xingbo","family":"Huang","sequence":"additional","affiliation":[{"name":"College of Mathematics and Computer Science, Fuzhou University, Fuzhou 350108, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hongju","family":"Cheng","sequence":"additional","affiliation":[{"name":"College of Mathematics and Computer Science, Fuzhou University, Fuzhou 350108, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zheng","family":"Wan","sequence":"additional","affiliation":[{"name":"School of Information Technology, Jiangxi University of Finance and Economics,  Nanchang 330013, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2013,4,12]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"62","DOI":"10.1109\/54.914626","article-title":"Dynamic power management in wireless sensor networks","volume":"18","author":"Sinha","year":"2001","journal-title":"Des. Test Comput."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1023\/A:1013763825347","article-title":"The broadcast storm problem in a mobile ad hoc network","volume":"8","author":"Tseng","year":"2002","journal-title":"Wirel. Netw."},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Williams, B., and Camp, T. (2002, January 9\u201311). Comparison of Broadcasting Techniques for Mobile Ad HocNetworks. Lausanne, Switzerland.","DOI":"10.1145\/513800.513825"},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"220","DOI":"10.1016\/j.jpdc.2004.09.006","article-title":"Dynamic probabilistic broadcasting in MANETs","volume":"65","author":"Zhang","year":"2005","journal-title":"J. Parallel Distrib. Comput."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"364","DOI":"10.1016\/j.simpat.2008.09.012","article-title":"Performance evaluation of dynamic probabilistic broadcasting for flooding in mobile ad hoc network","volume":"17","author":"Hanashi","year":"2009","journal-title":"Simul. Model. Pract. Theory"},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"5952","DOI":"10.3390\/s110605952","article-title":"Adaptive broadcasting method using neighbor type information in wireless sensor networks","volume":"11","author":"Jeong","year":"2011","journal-title":"Sensors"},{"key":"ref_7","unstructured":"Wieselthier, J.E., Nguyen, G.D., and Ephremides, A. (2000, January 26\u201330). On the Construction of Energy-Efficient Broadcast and Multicast Trees in Wireless Networks. Tel Aviv, Israel."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"653","DOI":"10.1016\/j.ins.2009.11.016","article-title":"Broadcast routing in wireless sensor networks with dynamic power management and multi-coverage backbones","volume":"180","author":"Sausen","year":"2010","journal-title":"Inform. Sci."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"298","DOI":"10.1007\/978-3-642-04383-3_22","article-title":"A decentralized approach to minimum-energy broadcasting in static ad hoc networks","volume":"5793","author":"Miller","year":"2009","journal-title":"Lect. Note. Comput. Sci."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"1104","DOI":"10.1007\/978-3-642-03869-3_102","article-title":"Optimal and near-optimal energy-efficient broadcasting in wireless networks","volume":"5704","author":"Papageorgiou","year":"2009","journal-title":"Lect. Note. Comput. Sci."},{"key":"ref_11","unstructured":"Ruiz, P., and Bouvry, P. (July, January 28). Enhanced Distance Based Broadcasting Protocol with Reduced Energy Consumption. Caen, France."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"1213","DOI":"10.1007\/s11227-011-0564-x","article-title":"Optimisation of the enhanced distance based broadcasting protocol for MANETs","volume":"62","author":"Ruiz","year":"2012","journal-title":"J. Supercomput."},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"Li, L., Ramjee, R., Buddhikot, M., and Miller, S. (2007, January 6\u201312). Network Coding-Based Broadcast in Mobile Ad-HocNetworks. Anchorage, AK, USA.","DOI":"10.1109\/INFCOM.2007.203"},{"key":"ref_14","unstructured":"Fang, W., Liu, F., Liu, Z., Shu, L., and Nishio, S. (2011, January 10\u201315). Reliable Broadcast Transmission in Wireless Networks Based on Network Coding. Shanghai, China."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"148","DOI":"10.1109\/TPDS.2009.44","article-title":"Efficient broadcasting using network coding and directional antennas in MANETs","volume":"21","author":"Yang","year":"2010","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"788","DOI":"10.1016\/j.adhoc.2010.09.009","article-title":"R-Code: Network coding-based reliable broadcast in wireless mesh networks","volume":"9","author":"Yang","year":"2011","journal-title":"Ad Hoc Netw."},{"key":"ref_17","unstructured":"Das, A.K., Marks, R.J., El-Sharkawi, M., Arabshahi, P., and Gray, A. (April, January 30). Minimum Power Broadcast Trees for Wireless Networks: Integer Programming Formulations. San Franciso, CA, USA."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"696","DOI":"10.1016\/j.adhoc.2007.06.006","article-title":"Minimum-energy broadcast and multicast in wireless networks: An integer programming approach and improved heuristic algorithms","volume":"6","author":"Yuan","year":"2008","journal-title":"Ad Hoc Netw."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1007\/s10852-010-9146-9","article-title":"A linear programming-based evolutionary algorithm for the minimum power broadcast problem in wireless sensor networks","volume":"10","author":"Montemanni","year":"2011","journal-title":"J. Math. Model. Algorithm"},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"1401","DOI":"10.1007\/s11276-011-0344-9","article-title":"Minimum power multicast algorithms for wireless networks with a Lagrangian relaxation approach","volume":"17","author":"Wen","year":"2011","journal-title":"Wirel. Netw."},{"key":"ref_21","doi-asserted-by":"crossref","unstructured":"Wu, X., Wang, X., and Liu, R. (2008, January 5\u20138). Solving Minimum Power Broadcast Problem in Wireless Ad-HocNetworks Using Genetic Algorithm. Halifax, NS, USA.","DOI":"10.1109\/CNSR.2008.91"},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"667","DOI":"10.1016\/j.asoc.2009.12.027","article-title":"A hybrid genetic algorithm for the minimum energy broadcast problem in wireless ad hoc networks","volume":"11","author":"Singh","year":"2011","journal-title":"Appl. Soft Comput."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1007\/978-3-540-87527-7_3","article-title":"Ant colony optimization for energy-efficient broadcasting in ad-hoc networks","volume":"5217","author":"Blum","year":"2008","journal-title":"Lect. Note. Comput. Sci."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"5684","DOI":"10.1016\/j.asoc.2011.03.023","article-title":"Minimum energy broadcasting in wireless sensor networks: An ant colony optimization approach for a realistic antenna model","volume":"11","author":"Blum","year":"2011","journal-title":"Appl. Soft Comput."},{"key":"ref_25","unstructured":"Hsiao, P.-C., Chiang, T.C., and Fu, L.C. (2012, January 10\u201315). Particle Swarm Optimization for the Minimum Energy Broadcast Problem in Wireless Ad-HocNetworks. Brisbane, QLD, Australia."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"148","DOI":"10.1109\/TMC.2007.31","article-title":"Toward broadcast reliability in mobile Ad Hoc networks with double coverage","volume":"6","author":"Lou","year":"2007","journal-title":"IEEE Trans. Mob. Comput."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1016\/j.adhoc.2009.06.003","article-title":"Efficient broadcast for wireless ad hoc networks with a realistic physical layer","volume":"8","author":"Xu","year":"2010","journal-title":"Ad Hoc Netw."},{"key":"ref_28","first-page":"27","article-title":"Computing connected dominated sets with multipoint relays","volume":"1","author":"Adjih","year":"2005","journal-title":"Ad Hoc Sens. Wirel. Netw."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"334","DOI":"10.1109\/TC.2006.40","article-title":"Extended multipoint relays to determine connected dominating sets in MANETs","volume":"55","author":"Wu","year":"2006","journal-title":"IEEE Trans. Comput."},{"key":"ref_30","unstructured":"Han, B., Fu, H., Lin, L., and Jia, W. (2004, January 25\u201327). Efficient Construction of Connected Dominating Set in Wireless Ad Hoc Networks. Fort Lauderdale, FL, USA."},{"key":"ref_31","first-page":"875","article-title":"Efficient approximation algorithm for minimum connected dominating set","volume":"29","author":"Liao","year":"2008","journal-title":"J. Chin. Comput. Syst."},{"key":"ref_32","doi-asserted-by":"crossref","unstructured":"Ghasemi, V., Hashemi, S.N., and Mozaffari, M. (2010, January 1\u20133). Connected Dominating Set Construction Using an Efficient Pruning Method in Ad Hoc Networks. Singapore.","DOI":"10.4108\/ICST.WICON2010.8525"},{"key":"ref_33","first-page":"530","article-title":"Efficient broadcast protocol in mobile ad hoc networks","volume":"12","author":"Peng","year":"2001","journal-title":"J. Softw."},{"key":"ref_34","unstructured":"Rappaport, T.S. (1996). Wireless Communications: Principles and Practice, Prentice Hall. [2nd ed.]."},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"325","DOI":"10.1016\/j.tcs.2004.08.013","article-title":"A greedy approximation for minimum connected dominating sets","volume":"329","author":"Ruan","year":"2004","journal-title":"Theor. Comput. Sci."},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"1842","DOI":"10.1016\/j.comcom.2007.12.001","article-title":"Efficient placement of proxies for hierarchical reliable multicast","volume":"31","author":"Tan","year":"2008","journal-title":"Comput. Commun."},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"374","DOI":"10.1007\/PL00009201","article-title":"Approximation algorithms for connected dominating sets","volume":"20","author":"Guha","year":"1998","journal-title":"Algorithmica"}],"container-title":["Sensors"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1424-8220\/13\/4\/4922\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T21:46:06Z","timestamp":1760219166000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1424-8220\/13\/4\/4922"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,4,12]]},"references-count":37,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2013,4]]}},"alternative-id":["s130404922"],"URL":"https:\/\/doi.org\/10.3390\/s130404922","relation":{},"ISSN":["1424-8220"],"issn-type":[{"type":"electronic","value":"1424-8220"}],"subject":[],"published":{"date-parts":[[2013,4,12]]}}}