## 4 Methodology
### Adaptive Scatter Search Algorithm for the MCDS Problem
#### 4.2.3 ASS-MCDS Algorithm
In this experimental section, the effectiveness of ASS-MCDS method is analyzed on several test graphs from the literature [1; 11; 12; 21]. These graphs are given as ad hoc wireless network clustering instances, which are described in Table 1. As shown in Table 1, eight different networks (instances) are used and all of these networks occupy the same area with different number of nodes (vertices) for each network starting from 80 nodes up to 400 nodes. The experiments were run 20 times for variant sizes of networks with the shown transmission ranges \(R\). ### Parameter Setting and Tuning

Table 2 summarizes all parameters used in ASS-MCDS with their assigned values. These values are chosen according to our numerical experiments, or well-known common settings in the literature. \begin{table}
\begin{tabular}{c c c c} \hline \hline
**Network** & **Area (\(L\times L\))** & **No. Vertices (\(V\))** & **Range (R)** \\ \hline Net 1 & \(400\times 400\) & 80 & 120 \\ Net 2 & \(600\times 600\) & 100 & 120 \\ Net 3 & \(700\times 700\) & 200 & 120 \\ Net 4 & \(1000\times 1000\) & 200 & 160 \\ Net 5 & \(1500\times 1500\) & 250 & 160 \\ Net 6 & \(2000\times 2000\) & 300 & 230 \\ Net 7 & \(2500\times 2500\) & 350 & 230 \\ Net 8 & \(3000\times 3000\) & 400 & 240 \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Ad hoc network instances. Figure 1: ASS-MCDS (adaptive scatter search ) flowchart. In parameter tuning, we tried to find the best parameter values with moderate costs and good performance. The performance of the ASS-MCDS with different values of the parameters were studied to demonstrate the relationship between tuning parameter values and the network size. The following settings are tested to identify the best setting of the parameter values. * The population size (\(P_{Size}\)) = 60, 80, 100, 120;
* The number of iterations in local search (\(n_{step}\)) = 4, 8, 10, 14;
* The reference set size (\(Ref_{Size}\)) = 10, 15, 20. The best solutions vary according to the tuning parameter values which significantly affect solution qualities. In Figure 2, when the value of \(P_{Size}\) increases from 60 to 120, the results are improved significantly until a specific limit is reached where the quality of the results is not affected with the increment of the \(P_{Size}\) values. For moderate-size networks Net 1, Net 2, Net 3, and Net 4, the value 60 for \(P_{Size}\) is enough to acquire the best domination number for the networks. However, this value is not enough for Net 5 and Net 6, so it is increased to 80 to acquire the best domination number. This was also applied for Net 7 and Net 8 when the network became bigger, requiring an increment in \(P_{Size}\) values. Consequently, setting \(P_{Size}\) equal to 60 for small-size networks helped the proposed algorithm to obtain results with the same quality as those obtained by higher values of \(P_{Size}\). Maintaining small values for this \(P_{Size}\) contributed to maintaining the computation cost and processing time. However, the \(P_{Size}\) value for large-size networks should gradually be increased according to the size of the network in order to maintain the solution qualities. According to these experimental results, the best value for \(P_{Size}\) could be calculated as the following:

\[P_{Size}= \begin{cases}60,&\text{if }V_{n}\leq 200,\\ 60+(20\times V_{n}/200),&\text{if }V_{n}>200.\end{cases}  \tag{2}\]

where \(V_{n}\) represents the number of vertices in the graph. In Figure 3, when the value of \(n_{step}\) increases from 2 to 14 the results are significantly improved for all networks. As noted, the ASS-MCDS acquires the best domination number for all networks when the number of iterations in local search \(n_{step}\) equals 10. In general, the experiment results proved that choosing the best parameter value increased the efficiency of ASS-MCDS for solving the MCDS problem. According to known common settings in the literature, the value of \(Ref_{Size}\) is typically small, e.g., no more than 20 [5].