## 4 Methodology
### Adaptive Scatter Search Algorithm for the MCDS Problem
#### 4.2.3 ASS-MCDS Algorithm
Figure 7 displays the comparison results of applying different methods on the networks with a large sizes. Although the proposed method performance was close to the other methods, it achieved better results in some networks. On the other hand, the other methods were partially better in some small size networks. In general, the ASS-MCDS method was more practical and promising than other methods in designing and managing wireless networks. \begin{table}
\begin{tabular}{c c c c c c c c c} \hline \hline
**Network** & \multicolumn{2}{c}{**ACO+PCS**} & \multicolumn{2}{c}{**GRASP**} & \multicolumn{2}{c}{**MA-MCDS**} & \multicolumn{2}{c}{**ASS-MCDS**} \\
**ID** & **Avg. ** & **Min. ** & **Avg. ** & **Min. ** & **Avg. ** & **Min. ** & **Avg. ** & **Min. ** \\ \hline \(Net_{1,60}\) & 21.2 & 19 & 19.8 & 19 & 18.0 & 17 & 17.2 & **16** \\ \(Net_{1,70}\) & 16



Figure 7: Comparison of results for big-size networks. ## 6 Conclusions

In this paper, the MCDS problem and its application in wireless sensor network management was investigated. A new algorithm to compute the MCDS was proposed, called the adaptive scatter search algorithm for solving the MCDS problem (ASS-MCDS). Additionally, an extended fitness function with multiple objectives used by the algorithm to evaluate the solutions qualities and achieve a better performance was invoked. In general, numerical experiments on ad hoc wireless networks showed that the proposed method outperformed other methods, particularly in large size wireless networks by identifying the wireless network virtual backbone structure by reformulating it to the MCDS problem. Test results demonstrated that ASS-MCDS was very efficient in finding solutions with high quality to identify MCDS using different standard benchmarks test graphs. Conceptualization, A.-R.H., G.A.E.-S.; Methodology, A.-R.H., S.N.A., A.A.S., G.A.E.-S.; Programming and implementation, A.-R.H., S.N.A., G.A.E.-S.; Writing--original draft preparation, A.-R.H., S.N.A., G.A.E.-S.; Writing--review and editing, A.-R.H., A.A.S., G.A.E.-S.; Funding acquisition, A.-R.H. All authors have read and agreed to the published version of the manuscript. This work was funded by the National Plan for Science, Technology, and Innovation (MAARIFAH), King Abdulaziz City for Science and Technology, the Kingdom of Saudi Arabia, award number (13-INF544-10). The authors would like to thank King Abdulaziz City for Science and Technology, the Kingdom of Saudi Arabia, for supporting project number (13-INF544-10). The authors declare no conflict of interest. ## References

* [PERSON] and [PERSON] (2013) [PERSON]; [PERSON] Ant colony optimization algorithm with pheromone correction strategy for the minimum connected dominating set problem. _Comput. Sci. Inf. Syst._**2013**, _10_, 133-149. [CrossRef]
* [PERSON] et al. (2012) [PERSON]; [PERSON]; [PERSON]; [PERSON] Load-balanced virtual backbone construction for wireless sensor networks. In _Combinatorial Optimization and Applications_; [PERSON], [PERSON]; Springer: Berlin, Germany, 2012; pp. 1-12. * [PERSON] and [PERSON] (2015) [PERSON]; [PERSON] Energy efficient connected dominating set construction using ant colony optimization technique in wireless sensor network. In Proceedings of the 2015 International Conference on Innovations in Information, Embedded and Communication Systems (ICIIECS), Coimbatore, India, 19-20 March 2015; pp. 1-5. * [PERSON] et al. (2010) [PERSON]; [PERSON]; [PERSON] Heuristic algorithms for constructing connected dominating sets with minimum size and bounded diameter in wireless networks. In _Wireless Algorithms, Systems, and Applications_; [PERSON], [PERSON], [PERSON], [PERSON], [PERSON], [PERSON]; Springer: Berlin, Germany, 2010; pp. 11-20. * [PERSON] et al. (2006) [PERSON]; [PERSON]; [PERSON] Principles of scatter search. _Eur. J. Oper. Res._**2006**, _169_, 359-372. [CrossRef]
* [PERSON] and [PERSON] (2010) [PERSON]; [PERSON] _Handbook of Metaheuristics_; Springer: New York, NY, USA, 2010; Volume 2.