{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,10]],"date-time":"2026-01-10T19:02:20Z","timestamp":1768071740816,"version":"3.49.0"},"reference-count":54,"publisher":"MDPI AG","issue":"12","license":[{"start":{"date-parts":[[2020,6,21]],"date-time":"2020-06-21T00:00:00Z","timestamp":1592697600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100004919","name":"King Abdulaziz City for Science and Technology","doi-asserted-by":"publisher","award":["13-INF544-10"],"award-info":[{"award-number":["13-INF544-10"]}],"id":[{"id":"10.13039\/501100004919","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Sensors"],"abstract":"<jats:p>In wireless sensor\/ad hoc networks, all wireless nodes frequently flood the network channel by transmitting control messages causing \u201cbroadcast storm problem\u201d. Thus, inspired by the physical backbone in wired networks, a Virtual Backbone (VB) in wireless sensor\/ad hoc networks can help achieve efficient broadcasting. A well-known and well-researched approach for constructing virtual backbone is solving the Connected Dominating Set (CDS) problem. Furthermore, minimizing the size of the CDS is a significant research issue. We propose a new parallel scatter search algorithm with elite and featured cores for constructing a wireless sensor\/ad hoc network virtual backbones based on finding minimum connected dominating sets of wireless nodes. Also, we addressed the problem of VB node\/nodes failure by either deploying a previously computed VBs provided by the main pSSEF algorithm that does not contain the failed node\/nodes, or by using our proposed FT-pSSEF algorithm repairing the broken VBs. Finally, as nodes in a VB incur extra load of communication and computation, this leads to faster power consumption compared to other nodes in the network. Consequently, we propose the virtual backbone scheduling algorithm SC-pSSEF which aims to find multiple VBs using the VBs provided by the pSSEF algorithm and switch between them periodically to prolong the network life time.<\/jats:p>","DOI":"10.3390\/s20123509","type":"journal-article","created":{"date-parts":[[2020,6,23]],"date-time":"2020-06-23T09:05:33Z","timestamp":1592903133000},"page":"3509","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":14,"title":["Wireless Sensor Networks Fault-Tolerance Based on Graph Domination with Parallel Scatter Search"],"prefix":"10.3390","volume":"20","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9936-5987","authenticated-orcid":false,"given":"Abdel-Rahman","family":"Hedar","sequence":"first","affiliation":[{"name":"Department of Computer Science in Jamoum, Umm Al-Qura University, Makkah 25371, Saudi Arabia"},{"name":"Department of Computer Science, Faculty of Computers &amp; Information, Assiut University, Assiut 71526, Egypt"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shada N.","family":"Abdulaziz","sequence":"additional","affiliation":[{"name":"Center for Middle Eastern Studies, Lund University, SE-22362 Lund, Sweden"},{"name":"Department of Mathematics, Faculty of Science, Assiut University, Assiut 71516, Egypt"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8039-0728","authenticated-orcid":false,"given":"Emad","family":"Mabrouk","sequence":"additional","affiliation":[{"name":"Department of Mathematics, Faculty of Science, Assiut University, Assiut 71516, Egypt"},{"name":"College of Engineering and Technology, American University of the Middle East, Kuwait, Kuwait"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6136-421X","authenticated-orcid":false,"given":"Gamal A.","family":"El-Sayed","sequence":"additional","affiliation":[{"name":"Department of Computer Science in Jamoum, Umm Al-Qura University, Makkah 25371, Saudi Arabia"},{"name":"Electrical Engineering Department, Assiut University, Assiut 71516, Egypt"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2020,6,21]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"1703201","DOI":"10.1177\/155014771703201","article-title":"A Greedy Algorithm on constructing the minimum connected dominating set in wireless network","volume":"12","author":"Fu","year":"2016","journal-title":"Int. J. Distrib. Sens. Netw."},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"He, J.S., Ji, S., Pan, Y., and Cai, Z. (2012, January 5\u20139). Load-balanced virtual backbone construction for wireless sensor networks. Proceedings of the International Conference on Combinatorial Optimization and Applications, COCOA 2012, Banff, AB, Canada.","DOI":"10.1007\/978-3-642-31770-5_1"},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Mnif, K., Rong, B., and Kadoch, M. (2005). Virtual Backbone Based on Mcds for Topology Control in Wireless ad Hoc Networks, Association for Computing Machinery.","DOI":"10.1145\/1089803.1089991"},{"key":"ref_4","unstructured":"Asgarnezhad, R., and Torkestani, J.A. (2011, January 23\u201329). Connected dominating set problem and its application to wireless sensor networks. Proceedings of the First International Conference on Advanced Communications and Computation, INFOCOMP 2011, Barcelona, Spain."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"20","DOI":"10.1016\/j.eswa.2016.04.018","article-title":"Bio inspired computing\u2013A review of algorithms and scope of applications","volume":"59","author":"Kar","year":"2016","journal-title":"Expert Syst. Appl."},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Wang, J., Hedar, A.R., and Wang, S. (2007, January 14\u201317). Scatter Search for Rough Set Attribute Reduction. Proceedings of the 2007 Second International Conference on Bio-Inspired Computing: Theories and Applications, Zhengzhou, China.","DOI":"10.1109\/BICTA.2007.4806458"},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1007\/s11424-014-3298-z","article-title":"A rough set approach to feature selection based on scatter search metaheuristic","volume":"27","author":"Wang","year":"2014","journal-title":"J. Syst. Sci. Complexity"},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Martins, S.L., Ribeiro, C.C., and Rosseti, I. (2004, January 29\u201331). Applications and parallel implementations of metaheuristics in network design and routing. Proceedings of the Asian Applied Computing Conference, AACC 2004, Kathmandu, Nepal.","DOI":"10.1007\/978-3-540-30176-9_27"},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Shyama, M., and Pillai, A.S. (2019). Fault-Tolerant Techniques for Wireless Sensor Network\u2014A Comprehensive Survey. Innovations in Electronics and Communication Engineering, Springer.","DOI":"10.1007\/978-981-13-3765-9_27"},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Zhao, Y., Wu, J., Li, F., and Lu, S. (2010, January 15\u201319). VBS: Maximum lifetime sleep scheduling for wireless sensor networks using virtual backbones. Proceedings of the 2010 Proceedings IEEE INFOCOM, San Diego, CA, USA.","DOI":"10.1109\/INFCOM.2010.5462212"},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1016\/j.comcom.2012.10.005","article-title":"Connected dominating sets in wireless ad hoc and sensor networks\u2014A comprehensive survey","volume":"36","author":"Yu","year":"2013","journal-title":"Comput. Commun."},{"key":"ref_12","unstructured":"Blum, J., Ding, M., Thaeler, A., and Cheng, X. (2004). Connected dominating set in sensor networks and MANETs. Handbook of Combinatorial Optimization, Springer."},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"Du, D.Z., and Wan, P.J. (2012). Connected Dominating Set: Theory and Applications, Springer.","DOI":"10.1007\/978-1-4614-5242-3"},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"387","DOI":"10.1109\/TNET.2019.2963361","article-title":"Adaptive Algorithm for Finding Connected Dominating Sets in Uncertain Graphs","volume":"28","author":"Fukunaga","year":"2020","journal-title":"IEEE\/ACM Trans. Netw."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"9189645","DOI":"10.1155\/2020\/9189645","article-title":"On Constructing Strongly Connected Dominating and Absorbing Set in 3-Dimensional Wireless Ad Hoc Networks","volume":"2020","author":"Liang","year":"2020","journal-title":"Complexity"},{"key":"ref_16","unstructured":"Cheng, X., Ding, M., and Chen, D. (2004, January 11\u201312). An approximation algorithm for connected dominating set in ad hoc networks. Proceedings of the International Workshop on Theoretical Aspects of Wireless Ad Hoc, Sensor, and Peer-to-Peer Networks (TAWN 2004), Chicago, IL, USA."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1186\/1687-1499-2012-83","article-title":"An energy efficient MCDS construction algorithm for wireless sensor networks","volume":"2012","author":"Tang","year":"2012","journal-title":"EURASIP J. Wirel. Commun. Netw."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"427","DOI":"10.1002\/wcm.547","article-title":"A novel distributed MCDS approximation algorithm for wireless sensor networks","volume":"9","author":"Xie","year":"2009","journal-title":"Wirel. Commun. Mob. Comput."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"33130","DOI":"10.1109\/ACCESS.2019.2903920","article-title":"Wireless sensor network MCDS construction algorithms with energy consideration for extreme environments healthcare","volume":"7","author":"Tang","year":"2019","journal-title":"IEEE Access"},{"key":"ref_20","first-page":"652","article-title":"CDS-based virtual backbone construction with guaranteed routing cost in wireless sensor networks","volume":"24","author":"Du","year":"2012","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"102023","DOI":"10.1016\/j.adhoc.2019.102023","article-title":"Minimum connected dominating sets in heterogeneous 3D wireless ad hoc networks","volume":"97","author":"Bai","year":"2020","journal-title":"Ad Hoc Netw."},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"Li, R., Hu, S., Liu, H., Li, R., Ouyang, D., and Yin, M. (2019). Multi-Start Local Search Algorithm for the Minimum Connected Dominating Set Problems. Mathematics, 7.","DOI":"10.3390\/math7121173"},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"292","DOI":"10.1109\/TPDS.2009.78","article-title":"Minimum connected dominating set using a collaborative cover heuristic for ad hoc sensor networks","volume":"21","author":"Misra","year":"2009","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"17527","DOI":"10.1109\/ACCESS.2018.2819083","article-title":"Dominating set algorithms for wireless sensor networks survivability","volume":"6","author":"Pino","year":"2018","journal-title":"IEEE Access"},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"451","DOI":"10.1007\/s10898-008-9384-9","article-title":"A PTAS for minimum connected dominating set in 3-dimensional wireless sensor networks","volume":"45","author":"Zhang","year":"2009","journal-title":"J. Glob. Optim."},{"key":"ref_26","unstructured":"Zhang, D., Xu, M., Xiao, W., Gao, J., and Tang, W. (2007, January 21\u201323). Minimization of the redundant sensor nodes in dense wireless sensor networks. Proceedings of the International Conference on Evolvable Systems, Wuhan, China."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"1059","DOI":"10.1007\/s00521-016-2429-y","article-title":"GRASP for connected dominating set problems","volume":"28","author":"Li","year":"2017","journal-title":"Neural Comput. Appl."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"133","DOI":"10.2298\/CSIS110927038J","article-title":"Ant colony optimization algorithm with pheromone correction strategy for the minimum connected dominating set problem","volume":"10","author":"Jovanovic","year":"2013","journal-title":"Comput. Sci. Inf. Syst."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"644","DOI":"10.1016\/j.asoc.2017.06.023","article-title":"Two population-based optimization algorithms for minimum weight connected dominating set problem","volume":"59","author":"Dagdeviren","year":"2017","journal-title":"Appl. Soft Comput."},{"key":"ref_30","doi-asserted-by":"crossref","unstructured":"Hedar, A.R., Ismail, R., El Sayed, G.A., and Khayyat, K.M.J. (2015, January 12\u201316). Two meta-heuristics for the minimum connected dominating set problem with an application in wireless networks. Proceedings of the 2015 3rd International Conference on Applied Computing and Information Technology\/2nd International Conference on Computational Science and Intelligence (ACIT-CSI), Okayama, Japan.","DOI":"10.1109\/ACIT-CSI.2015.68"},{"key":"ref_31","doi-asserted-by":"crossref","unstructured":"Hedar, A.R., and El-Sayed, G.A. (2018, January 26\u201327). Parallel genetic algorithm with elite and diverse cores for solving the minimum connected dominating set problem in wireless networks topology control. Proceedings of the 2nd International Conference on Future Networks and Distributed Systems, ACM, Amman, Jordan.","DOI":"10.1145\/3231053.3231080"},{"key":"ref_32","first-page":"1785","article-title":"Fault tolerance in wireless sensor network","volume":"5","author":"Mannan","year":"2015","journal-title":"Int. J. Res. Appl. Sci. Eng. Technol."},{"key":"ref_33","doi-asserted-by":"crossref","unstructured":"Liu, H., Nayak, A., and Stojmenovi\u0107, I. (2009). Fault-tolerant algorithms\/protocols in wireless sensor networks. Guide to Wireless Sensor Networks, Springer.","DOI":"10.1007\/978-1-84882-218-4_10"},{"key":"ref_34","first-page":"1511","article-title":"Fault Tolerance Review in Wireless Sensor Networks","volume":"5","author":"Neeraja","year":"2017","journal-title":"Int. J. Res. Appl. Sci. Eng. Technol."},{"key":"ref_35","doi-asserted-by":"crossref","unstructured":"Tiwari, R., and Thai, M.T. (2012). On enhancing fault tolerance of virtual backbone in a wireless sensor network with unidirectional links. Sensors: Theory, Algorithms, and Applications, Springer.","DOI":"10.1007\/978-0-387-88619-0_1"},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"3487","DOI":"10.1109\/TNET.2017.2740328","article-title":"Fault-tolerant virtual backbone in heterogeneous wireless sensor network","volume":"25","author":"Zhou","year":"2017","journal-title":"IEEE\/ACM Trans. Netw."},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"828","DOI":"10.1109\/COMST.2017.2650979","article-title":"A survey of network lifetime maximization techniques in wireless sensor networks","volume":"19","author":"Yetgin","year":"2017","journal-title":"IEEE Commun. Surv. Tutor."},{"key":"ref_38","doi-asserted-by":"crossref","unstructured":"Zhang, J., Xu, L., and Yang, H. (2015, January 23\u201325). A novel sleep scheduling algorithm for wireless sensor networks. Proceedings of the 2015 International Conference on Intelligent Information Hiding and Multimedia Signal Processing (IIH-MSP), Adelaide, Australia.","DOI":"10.1109\/IIH-MSP.2015.37"},{"key":"ref_39","first-page":"186","article-title":"Connected Dominant Set Based Virtual Backbone Path Routing For Wireless Sensor Network","volume":"1","author":"Malini","year":"2015","journal-title":"Int. J."},{"key":"ref_40","doi-asserted-by":"crossref","unstructured":"Wei, X., Liu, Y., and Bai, X. (2016). Maximizing Lifetime of CDS-Based Wireless Ad Hoc Networks. J. Commun., 11.","DOI":"10.12720\/jcm.11.4.365-373"},{"key":"ref_41","doi-asserted-by":"crossref","first-page":"5100","DOI":"10.1109\/TVT.2019.2906234","article-title":"An active mobile charging and data collection scheme for clustered sensor networks","volume":"68","author":"Liu","year":"2019","journal-title":"IEEE Trans. Veh. Technol."},{"key":"ref_42","doi-asserted-by":"crossref","unstructured":"Jin, Y., Kwak, K.S., and Yoo, S.J. (2020). A Novel Energy Supply Strategy for Stable Sensor Data Delivery in Wireless Sensor Networks. IEEE Syst. J.","DOI":"10.1109\/JSYST.2019.2963695"},{"key":"ref_43","doi-asserted-by":"crossref","first-page":"73096","DOI":"10.1109\/ACCESS.2020.2987920","article-title":"The Charging Strategy of Mobile Charging Vehicles in Wireless Rechargeable Sensor Networks With Heterogeneous Sensors","volume":"8","author":"Tian","year":"2020","journal-title":"IEEE Access"},{"key":"ref_44","doi-asserted-by":"crossref","unstructured":"Tian, M., Jiao, W., Liu, J., and Ma, S. (2019). A Charging Algorithm for the Wireless Rechargeable Sensor Network with Imperfect Charging Channel and Finite Energy Storage. Sensors, 19.","DOI":"10.3390\/s19183887"},{"key":"ref_45","doi-asserted-by":"crossref","unstructured":"Hedar, A.R., Abdulaziz, S.N., Sewisy, A.A., and El-Sayed, G.A. (2020). Adaptive Scatter Search to Solve the Minimum Connected Dominating Set Problem for Efficient Management of Wireless Networks. Algorithms, 13.","DOI":"10.3390\/a13020035"},{"key":"ref_46","first-page":"1","article-title":"Two Meta-Heuristics Designed to Solve the Minimum Connected Dominating Set Problem for Wireless Networks Design and Management","volume":"27","author":"Hedar","year":"2018","journal-title":"J. Netw. Syst. Manag."},{"key":"ref_47","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1007\/s13042-011-0043-y","article-title":"Simulated annealing with stochastic local search for minimum dominating set problem","volume":"3","author":"Hedar","year":"2012","journal-title":"Int. J. Mach. Learn. Cybern."},{"key":"ref_48","doi-asserted-by":"crossref","unstructured":"Hedar, A.R., and Ismail, R. (2010, January 23\u201326). Hybrid genetic algorithm for minimum dominating set problem. Prccceedings of the International Conference on Computational Science and Its Applications, Fukuoka, Japan.","DOI":"10.1007\/978-3-642-12189-0_40"},{"key":"ref_49","doi-asserted-by":"crossref","first-page":"6123","DOI":"10.1016\/j.eswa.2011.11.011","article-title":"Rough set and scatter search metaheuristic based feature selection for credit scoring","volume":"39","author":"Wang","year":"2012","journal-title":"Expert Syst. Appl."},{"key":"ref_50","doi-asserted-by":"crossref","unstructured":"Burke, E.K., and Kendall, G. (2014). Scatter search. Search Methodologies, Springer.","DOI":"10.1007\/978-1-4614-6940-7"},{"key":"ref_51","doi-asserted-by":"crossref","first-page":"359","DOI":"10.1016\/j.ejor.2004.08.004","article-title":"Principles of scatter search","volume":"169","author":"Laguna","year":"2006","journal-title":"Eur. J. Oper. Res."},{"key":"ref_52","unstructured":"Laguna, M., and Marti, R. (2012). Scatter Search: Methodology and Implementations in C, Springer Science & Business Media."},{"key":"ref_53","doi-asserted-by":"crossref","unstructured":"Bettstetter, C. (2002, January 9\u201311). On the minimum node degree and connectivity of a wireless multihop network. Proceedings of the 3rd ACM International Symposium on Mobile Ad Hoc Networking Computing, Lausanne, Switzerland.","DOI":"10.1145\/513800.513811"},{"key":"ref_54","doi-asserted-by":"crossref","first-page":"881","DOI":"10.1080\/08839510600940132","article-title":"An enhanced ant colony optimization metaheuristic for the minimum dominating set problem","volume":"20","author":"Ho","year":"2006","journal-title":"Appl. Artif. Intell."}],"container-title":["Sensors"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1424-8220\/20\/12\/3509\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T09:41:25Z","timestamp":1760175685000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1424-8220\/20\/12\/3509"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6,21]]},"references-count":54,"journal-issue":{"issue":"12","published-online":{"date-parts":[[2020,6]]}},"alternative-id":["s20123509"],"URL":"https:\/\/doi.org\/10.3390\/s20123509","relation":{},"ISSN":["1424-8220"],"issn-type":[{"value":"1424-8220","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,6,21]]}}}