# A Guaranteed Approximation Algorithm for QoS Anypath Routing in WMNs
## 4 Simulation Experiment and Performance Evaluation
### Experiment and Analysis of HMAA Algorithm  
In the network, the source node \(s\) and the destination node \(t\) are randomly selected, then the anypath routing is found by MAP, HMAA and SAF, respectively (SAF with the single metric \"time\"), in order to compare and analyze the efficiency of the three algorithms. As shown in Figure 3, according to the experimental steps, three networks with a different number of nodes are generated randomly, so are the constraints, the source node \(s\) and the destination node \(t\) subsequently. Then, the three algorithms are run and the anyypath routing is recorded (run for 10 times on average). For simplicity, the weights of nodes in the network are normalized (equivalent to 1), thus the recorded data is shown in Figure 5.  
As shown in Figure 5, the QoS constraints of each network are random. The number of normalized network nodes has no effect on the length of anypath routing. In the same network, the length of the anypath routing by three algorithms are compared. The length of MAP is the smallest, followed by HMAA, and SAF is the largest. Since MAP approximates all of the constraints of the OMCAP problem, the length of anypath routing obtained is minimal. HMAA approximates the constraint when K\(-\)1 = 2, and its length is slightly larger than MAP. SAF is a metric used to find an anypath routing, which cannot guarantee any other constraints on the anypath routing, so it has a larger length compared to the other two algorithms. 3 When the anypath routing found by MAP satisfies the constraints, anypath routing found by HMAA also meets the constraints, while SAF cannot guarantee other QoS constraints. Figure 5: Anypath Length vs. number of nodes for MAP, HMAA and SAF. The following approximation rate IAR (ratio of optimal value to the sub-optimal value) [21] is used to evaluate the performance of HMAA proposed in this paper. In other words, if the approximation rate IAR is equal to 1, it means that the optimal anypath is found, and if the approximation rate is less than 1, it means that the solution found is sub-optimal. Therefore, the approximation rate IAR indicates the quality of the solution found by HMAA. As we know that finding the optimal solution to MCOAP is NP-hard, \(P_{s}^{opt}\) is replaced by the solution obtained by the intelligent algorithm proposed in [20]. Therefore, IAR is obtained by comparing the value \(P_{s}^{s}\) calculated by HMAA with that by [20]. The network with different nodes is calculated 20 times, respectively, thus the approximation rate IAR (blue dot) is recorded in Figure 6.  
As can be seen from Figure 6, no more than 70% of IAR fall between [0.75, 0.95], and all the IAR fall within the range of [0.5,1] regardless of how many nodes there are in the network. HMAA proposed in this paper focuses on the MCOAP problem and finds the anypath routing in a reasonable time from an approximate perspective. Theorem 2 proves that the upper bound of HMAA is the K-1 approximation (here it is the 2 approximation), then the following simulation experiments also show that its approximation to the optimal solution is very high, so it is reasonable and feasible in wireless multimedia applications. HMAA has a slightly longer running time than SAF, but the quality of the solution is good for multiple QoS constraints. MAP is a solution to OMCAP problem and tries to satisfy all constraints in an ideal state, but HMAA guarantees a specific QoS constraint while approaching other QoS constraints, so it is more in line with the business requirements in wireless multimedia applications. For example, if real-time voice services have strict delay jitter constraints, HMAA can guarantee its performance, but MAP cannot. To sum up, in our network simulation experiment above, we compare the proposed algorithm HMAA with the best SAF and MAP algorithms. These three algorithms are oriented to different wireless multimedia applications. SAF focuses on the running time of the algorithm, and MAP focuses on the quality of all of the solutions.