# A Guaranteed Approximation Algorithm for QoS Anypath Routing in WMNs
## 3 An An Anypath Routing Approximation Algorithm for QoS
### Analysis of HMAA Algorithm  
In this paper, we first discuss the time complexity of the proposed HMAA algorithm, which can find a feasible solution to the MCOAP problem in a reasonable time. Secondly, we prove that HMAA is a K-1 approximation algorithm for the MCOAP problem. **Theorem 1**. : _The time complexity of HMAA algorithm is \(\mathrm{O}(n\log n+\mathrm{K}m)\)._  
Proof. : The proof of this theorem and the problems studied in [6] are somewhat different, but the logic between them is consistent. There are three stages for HMAA algorithm:  
In the first stage, AAW is calculated for each node in graph \(\mathrm{G}\) and the data structure is initialized (Lines 1-8 of HMAA) with a time complexity of \(\mathrm{O}(\mathrm{K})\). In the second phase, it calculates the AAW value (Lines 9-25 of HMAA) of the shortest anypath from all of the nodes to the destination node t, and the same time complexity as the traditional Dijkstra algorithm is \(\mathrm{O}(n\log n+\mathrm{K}m)\). In the third stage, it checks if the AAW value of the anypath routing \(\mathbf{P}\) found by HMAA satisfies the first mandatory constraint (Lines 26-29 of HMAA), where the time complexity is \(\mathrm{O}(m)\). The time complexity of HMAA above three stages is \(\mathrm{O}(\mathrm{K}+n\log n+\mathrm{K}m+m)=\mathrm{O}(n\log n+\mathrm{K}m)\), so Theorem 1 is proven. The proposed HMAA algorithm has the same time complexity as the traditional Dijkstra algorithm. On one hand, it has good compatibility with existing routing protocols. On the other hand, it is faster and computationally suitable for time-varying WMNs to find a feasible solution in a reasonable time. Theorem 1 indicates that \(P_{s}{}^{*}\) is the shortest AAW anypath. In other words, the forwarding set of each node calculated by HMAA algorithm is actually the optimal forwarding set based on AAW value. The HMAA algorithm is proposed in this chapter to identify the efficiency of the solution. **Theorem 2**. : _The anypath found by HMAA algorithm is at least a K-1 approximation solution and subject \(t\bar{w}(s,P_{s}^{*})\leq(\mathrm{K}-1)\cdot\bar{w}(s,P_{s}^{opt}),s.t.w_{1}( v,P_{s}^{opt})\leq L_{1}\)._  
Proof. : According to the implementation steps of HMAA algorithm, the nodes join the queue \(\mathrm{P}\) one by one. All of the nodes are indexed on the path \(P_{p}^{*}\) in this order, the index value of node \(t\) is 0, and node \(v\) with maximum index value finally joins queue \(\mathrm{P}\). It will be proved that the formula (4) is established for all of the nodes \(v\) by mathematical induction  
Figure 2: (a) Anypath \(P_{s}{}^{*}\) by HMAA and (b) optimal Anypath \(P_{s}{}^{opt}\). \[\hat{w}(v,P^{*}_{v})\leq w_{m}(v,P^{*}_{v}). \tag{4}\]  
For a node \(v_{1}\), only the destination node \(t\) is its forwarding set, so  
\[w_{m}(v_{1},P^{*}_{v})=\frac{w_{m}(v_{1})}{p(v_{1},t)}+w_{m}(<t>,P^{*}_{v})= \frac{w_{m}(v_{1})}{p(v_{1},t)}=\max_{2\leq i\leq\mathrm{K}}\frac{w_{i}(v_{1})} {p(v_{1},t)}. \tag{5}\]  
On the other hand, according to the definition of anypath routing length AAW, it can obtain  
\[\hat{w}(v_{1},P^{*}_{v})=\max_{2\leq i\leq\mathrm{K}}w_{i}(v_{1},P^{*}_{v})= \max_{2\leq i\leq\mathrm{K}}\frac{w_{i}(v_{1})}{p(v_{1},t)}+w_{m}(<t>,P^{*}_{v} )=\max_{2\leq i\leq\mathrm{K}}\frac{w_{i}(v_{1})}{p(v_{1},t)}. \tag{6}\]  
Thus, a node \(v_{1}\) satisfying the Formula (7)  
\[\hat{w}(v_{1},P^{*}_{v})\leq w_{m}(v_{1},P^{*}_{v}). \tag{7}\]  
Assuming that all nodes with subscripts [1, r], the following inequality holds  
\[\hat{w}(v_{r},P^{*}_{v})\leq w_{m}(v_{r},P^{*}_{v}). \tag{8}\]  
Next prove that it is also satisfied for \(v_{r+1}\).