# A Novel QoS Provisioning Algorithm for Optimal Multicast Routing in WMNs
## 4 The Simulation Experiments
In order to evaluate the efficiency of two algorithms, we define the following metrics:  
\[\text{ATCS}=\frac{\text{Total time consuming for each Steiner tree with q destination nodes}}{\text{Number of running}} \tag{23}\]  
The units of ATCS in Table 2 is in milliseconds. Analyzing the experimental results, it shows that the consuming time by Xue's is larger than that by NMHA, no matter what the number of destination nodes is, because the novel NMHA algorithm in this paper is devised to deal with the MCOMR problem in feasible time, different from the previous [PERSON]'s deterministic algorithm. At the same time, it could be easily found that when the value of \(q\) is getting larger from 2 to 54, the ATCS by NMHA is multiplied with the increase of destination nodes, while the ATCS by Xue's grows exponentially. The simulation experimental results also show that the NMHA algorithm has the lower time complexity level. Following that, the performance of the NMHA algorithm would be verified, compared with the previous algorithm FMPH by the authors [20], which is finding for the approximation solution for MCOMR problem in WMNs as fast as possible. As for random networks, the topologies are generated by Waxman model. Each link of random networks has the same three weights as the RNET network. Ten topologies for random networks are generated randomly, each of which has 50 nodes or 500 nodes. On each topology, 10 routing requests are also generated at the source node. It defines the metrics, Average Weigh Occupying (AWO) to evaluate the performance. Tables 3 and 4 show the AWO of Steiner trees with different destination nodes generated via the NMHA and FMPH algorithm in the simulation experiments, respectively:  
\[\text{AWO}=\frac{\text{Total weigh occupying for each Steiner tree with q destination nodes}}{\text{Numbers of running}} \tag{24}\] \begin{table}
\begin{tabular}{c c c c c c c c c} \hline \hline NO. & \(q=2\) & \(q=5\) & \(q=8\) & \(q=11\) & \(q=14\) & \(q=17\) & \(q=20\) & \(q=23\) \\ \hline NMHA & 42 & 107 & 163 & 233 & 297 & 366 & 419 & 492 \\ Xue’s & 58 & 751 & 1850 & 3611 & 4443 & 8772 & 12,054 & 15,779 \\ \hline NO. & \(q=26\) & \(q=30\) & \(q=34\) & \(q=38\) & \(q=42\) & \(q=46\) & \(q=50\) & \(q=54\) \\ \hline NMHA & 569 & 627 & 725 & 799 & 889 & 963 & 1052 & 1138 \\ Xue’s & 21,136 & 28,412 & 33,689 & 39,956 & 51,896 & 63,512 & 75,412 & 87,512 \\ \hline \hline \end{tabular}
\end{table} 
Table 2: A comparison of the performance of novel multicast heuristic approximation (NMHA) algorithm and Xue’s algorithm [16] in the random network. \begin{table}
\begin{tabular}{c c c c c c c c c} \hline \hline NO. & \(q=2\) & \(q=5\) & \(q=8\) & \(q=11\) & \(q=14\) & \(q=17\) & \(q=20\) & \(q=23\) \\ \hline NMHA & 24 & 33 & 34 & 56 & 58 & 59 & 70 & 59 \\ FMPH & 24 & 35 & 38 & 64 & 66 & 69 & 80 & 75 \\ \hline NO. & \(q=26\) & \(q=29\) & \(q=32\) & \(q=35\) & \(q=38\) & \(q=42\) & \(q=46\) & \(q=47\) \\ \hline NMHA & 72 & 80 & 81 & 90 & 95 & 101 & 109 & 110 \\ FMPH & 85 & 98 & 105 & 103 & 117 & 124 & 134 & 136 \\ \hline \hline \end{tabular}
\end{table} 
Table 3: Average Weigh Occupying (AWO) (\(10^{-3}\)) for NMHA algorithm and Fast Minimum Path Cost Heuristic (FMPH) algorithm with 50 nodes. The results in Table 3 show that when there are 50 nodes in the random network, no matter how many destination nodes are involved, the AWO obtained from NMHA is always less than that from FMPH. In Table 4, when the total number of nodes in the random network reaches up to 500, the outcome is still the same. It is consistent with our analysis that the NMHA algorithm presented in this paper is looking for the approximate optimal solution in feasible time, while FMPH tends to find the approximate optimal solution as soon as possible according to the time-varying characteristics of wireless networks. From the above results and analysis, it could be concluded that, with certain destination nodes, the proposed NMHA can find a better solution compared with FMPH in feasible time.