{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T10:10:16Z","timestamp":1767262216504,"version":"build-2065373602"},"reference-count":26,"publisher":"MDPI AG","issue":"2","license":[{"start":{"date-parts":[[2020,2,4]],"date-time":"2020-02-04T00:00:00Z","timestamp":1580774400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>An efficient routing using a virtual backbone (VB) network is one of the most significant improvements in the wireless sensor network (WSN). One promising method for selecting this subset of network nodes is by finding the minimum connected dominating set (MCDS), where the searching space for finding a route is restricted to nodes in this MCDS. Thus, finding MCDS in a WSN provides a flexible low-cost solution for the problem of event monitoring, particularly in places with limited or dangerous access to humans as is the case for most WSN deployments. In this paper, we proposed an adaptive scatter search (ASS-MCDS) algorithm that finds the near-optimal solution to this problem. The proposed method invokes a composite fitness function that aims to maximize the solution coverness and connectivity and minimize its cardinality. Moreover, the ASS-MCDS methods modified the scatter search framework through new local search and solution update procedures that maintain the search objectives. We tested the performance of our proposed algorithm using different benchmark-test-graph sets available in the literature. Experiments results show that our proposed algorithm gave good results in terms of solution quality.<\/jats:p>","DOI":"10.3390\/a13020035","type":"journal-article","created":{"date-parts":[[2020,2,5]],"date-time":"2020-02-05T03:18:48Z","timestamp":1580872728000},"page":"35","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["Adaptive Scatter Search to Solve the Minimum Connected Dominating Set Problem for Efficient Management of Wireless Networks"],"prefix":"10.3390","volume":"13","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, 25371 Makkah, Saudi Arabia"},{"name":"Department of Computer Science, Faculty of Computers &amp; Information, Assiut University, 71526 Assiut, Egypt"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shada N.","family":"Abdulaziz","sequence":"additional","affiliation":[{"name":"Center for Middle Eastern Studies, Lund University, SE-22100 Lund, Sweden"},{"name":"Department of Mathematics, Faculty of Science, Assiut University, 71516 Assiut, Egypt"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Adel A.","family":"Sewisy","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Faculty of Computers &amp; Information, Assiut University, 71526 Assiut, Egypt"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gamal A.","family":"El-Sayed","sequence":"additional","affiliation":[{"name":"Department of Computer Science in Jamoum, Umm Al-Qura University, 25371 Makkah, Saudi Arabia"},{"name":"Electrical Engineering Department, Assiut University, 71516 Assiut, Egypt"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2020,2,4]]},"reference":[{"key":"ref_1","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_2","doi-asserted-by":"crossref","unstructured":"Lin, G. (2012). Load-balanced virtual backbone construction for wireless sensor networks. Combinatorial Optimization and Applications, Springer.","DOI":"10.1007\/978-3-642-31770-5"},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Nimisha, T., and Ramalakshmi, R. (2015, January 19\u201320). Energy efficient connected dominating set construction using ant colony optimization technique in wireless sensor network. Proceedings of the 2015 International Conference on Innovations in Information, Embedded and Communication Systems (ICIIECS), Coimbatore, India.","DOI":"10.1109\/ICIIECS.2015.7192912"},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Pandurangan, G., Anil, K.V.S., Ming, G., Liu, Y., and Li, Y. (2010). Heuristic algorithms for constructing connected dominating sets with minimum size and bounded diameter in wireless networks. Wireless Algorithms, Systems, and Applications, Springer.","DOI":"10.1007\/978-3-642-14654-1"},{"key":"ref_5","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_6","doi-asserted-by":"crossref","unstructured":"Gendreau, M., and Potvin, J.-Y. (2010). Handbook of Metaheuristics, Springer.","DOI":"10.1007\/978-1-4419-1665-5"},{"key":"ref_7","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_8","unstructured":"Chiarelli, N., and Milanic, M. (2014). Linear Separation of Connected Dominating Sets in Graphs. arXiv, Available online: https:\/\/arxiv.org\/abs\/1610.06539."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"68","DOI":"10.1016\/j.ipl.2008.09.017","article-title":"Parameterized approximation of dominating set problems","volume":"109","author":"Downey","year":"2008","journal-title":"Inform. Process. Lett."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"1098","DOI":"10.1109\/TMC.2008.22","article-title":"On construction of virtual backbone in wireless ad hoc networks with unidirectional links","volume":"7","author":"Thai","year":"2008","journal-title":"IEEE Trans. Mob. Comput."},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Hedar, A.-R., Ismail, R., Sayed, G.A.E., 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 3rd International Conference on Applied Computing and Information Technology\/2nd International Conference on Computational Science and Intelligence, Okayama, Japan.","DOI":"10.1109\/ACIT-CSI.2015.68"},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/s10922-018-9480-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":"2019","journal-title":"J. Netw. Syst. Manag."},{"key":"ref_13","first-page":"53","article-title":"Three connected dominating set algorithms for wireless sensor networks","volume":"21","author":"Zhang","year":"2016","journal-title":"Int. J. Sens. Netw."},{"key":"ref_14","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"},{"key":"ref_15","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_16","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.tcs.2005.08.037","article-title":"Minimum connected dominating sets and maximal independent sets in unit disk graphs","volume":"352","author":"Wu","year":"2006","journal-title":"Theor. Comput. Sci."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"705","DOI":"10.1007\/978-3-642-31869-6_62","article-title":"Two connected dominating set algorithms for wireless sensor networks","volume":"Volume 7405","author":"Wang","year":"2012","journal-title":"Wireless Algorithms, Systems, and Applications"},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"511","DOI":"10.4304\/jnw.4.6.511-519","article-title":"A power aware minimum connected dominating set for wireless sensor networks","volume":"4","author":"Rai","year":"2009","journal-title":"JNW"},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Rai, M., Verma, S., and Tapaswi, S. (2009, January 1\u20136). A heuristic for minimum connected dominating set with local repair for wireless sensor networks. Proceedings of the Eighth International Conference on Networks, Gosier, Guadeloupe.","DOI":"10.4304\/jnw.4.6.511-519"},{"key":"ref_20","first-page":"1045","article-title":"An efficient heuristic for the minimum connected dominating set problem on ad hoc wireless networks","volume":"68","author":"Balaji","year":"2012","journal-title":"Proc. WASET"},{"key":"ref_21","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_22","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_23","doi-asserted-by":"crossref","unstructured":"Laguna, M. (2014). Scatter search. Search Methodologies, Springer.","DOI":"10.1007\/978-1-4614-6940-7_5"},{"key":"ref_24","unstructured":"Laguna, M., and Marti, R. (2012). Scatter Search: Methodology and Implementations in C, Springer Science & Business Media."},{"key":"ref_25","doi-asserted-by":"crossref","unstructured":"Talbi, E.G. (2009). Metaheuristics: From Design to Implementation, John Wiley & Sons.","DOI":"10.1002\/9780470496916"},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1007\/978-3-642-20662-7_2","article-title":"Metaheuristic optimization: algorithm analysis and open problems","volume":"Volume 6630","author":"Pardalos","year":"2011","journal-title":"Experimental Algorithms"}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/13\/2\/35\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T08:54:38Z","timestamp":1760172878000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/13\/2\/35"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,2,4]]},"references-count":26,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2020,2]]}},"alternative-id":["a13020035"],"URL":"https:\/\/doi.org\/10.3390\/a13020035","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2020,2,4]]}}}