# A Novel QoS Provisioning Algorithm for Optimal Multicast Routing in WMNs
## 4 The Simulation Experiments  
This section shall evaluate both the performance of NMHA and the performance of an experimentally obtained multicast routing tree. To evaluate its efficiency, NMHA is implemented and conducted in a performance study. An example of the NMHA algorithm is shown in Figure 1. Figure 1a is a simple topology graph \(\mathbf{G}\) of a static undirected network, in which the nodes in blue are the set of destination nodes \(\mathbf{D}\) and others are non-multicast destination nodes. The numbers marked between two nodes are linked to cost or distance. The node is originally added to the generating tree \(T_{0}=\{\text{A}\}\). In order to find the multicast generating tree with the NMHA algorithm (Lines 10-11), the first node \(\mathrm{U}_{1}\) is selected, and then it is added to the tree A-\(\mathrm{U}_{1}\) in Figure 1b (Lines 12-20) with the total cost of the generating tree 3. In the following phase of the algorithm, destination nodes \(\mathrm{U}_{2}\) and \(\mathrm{U}_{3}\) are added to the tree, respectively, and the multicast destination nodes are sorted as \(\mathrm{U}_{1}\)-\(\mathrm{U}_{2}\)-\(\mathrm{U}_{3}\). The final multicast tree obtained, whose total cost is 7, is shown in Figure 1c. According to the NMHA algorithm proposed in this paper, the generating graph is found. To examine the performance of NMHA, we use the famous Waxman model to generate a large-size Random Network (RNET). The random static network RNET, is used in these experiments, which runs on an Intel Core Duo CPU 1.66 GHz PC with 2 GB memory (Lenovo, Beijing, China). There are 60 nodes and 100 edges in RNET as shown in Figure 2, and other parameters for the network were  
Figure 1: An example of the novel multicast heuristic approximation (NMHA) algorithm. (**a**), (**b**) and (**c**) are the step 1, step 2 and step 3 of NMHA, respectively. produced randomly by Waxman model. Each link of RNET has three weights, which correspond to Cost, Delay and Jitter. All the red points denote the nodes of the network, the black wires denote the links, the green circles denote the source node \(s\) (No. 1) and the green stars denote the set of destination nodes \(\mathbf{D}\) (No. 30, 51 and 55) in the network RNET, which is shown in Figure 3. Comparison with the costs from the source node \(s\) to every destination node by [PERSON]'s deterministic algorithm, the minimal-cost node (No. 30) is selected first. Figure 4 shows the minimal-cost path from source node (No. 1) to destination nodes (No. 30), which is selected first by NMHA in the network. The blue paths in these figures indicate the minimal or the optimal paths from source to destination. Figure 5 illustrates that the following node (No. 55) is added to the tree by NMHA. As expected, the optimal multicast routing tree with three constraints added by the algorithm NMHA can be found after the last node (No. 51) is added to the multicast tree. At last, the optimal multicast routing tree described in Figure 6 shows the corresponding multicast tree from the source node (No. 1) to the set of destination nodes \(\mathbf{D}\) (No. 30, 51 and 55). Figure 3: The multicast destination nodes. Figure 2: The network topology of Random Network (RNET). In these simulation experiments, the approximating Steiner tree could be found by the NMHA algorithm presented in this paper. Following that the efficiency of the NMHA algorithm would be verified. Table 2 shows the comparisons of average time consuming for Steiner trees (ATCS) generated via the NMHA to [PERSON]'s deterministic algorithm in the simulation experiments, respectively. With the two algorithms, q destination nodes in the RNET network are randomly generated, and then the Steiner trees are obtained and the corresponding times are recorded. The simulations experiments are  
Figure 4: The No. 30 node connected to the multicast tree. Figure 5: The No. 55 node connected to the multicast tree. Figure 6: The No. 51 node connected to the multicast tree. made to calculate the average values for ten times.