# A Guaranteed Approximation Algorithm for QoS Anypath Routing in WMNs
## 3 An An Anypath Routing Approximation Algorithm for QoS
### Design of HMAA Algorithm
#### 3.1.3 An Example of HMAA Algorithm  
The implementation process of HMAA algorithm is described by an example. As shown in Figure 1, the source node \(s\) and the destination node \(t\) are in WMNs, then the anypath routing \({P_{s}}^{*}\) is calculated by HMAA algorithm. The system initializes the constraint value \(L_{1}=18\) for a given mandatory QoS. Figure 0(a)-f demonstrate the operation of the algorithm, where Figure 0(f) shows the anypath routing \({P_{s}}^{*}\) in WMNs found by HMAA. According to the operation of HMAA, we introduce the process of adding each node to anypath P:  
(a) In system initialization, the first node \(t\) is cleared to zero, then added to the anypath P;2. After the node \(t\) is added to the queue \(P_{i}\), \(\hat{w}_{i}(v)\) and \(\hat{w}_{m}(v)\) of the neighbors of node \(t\) (cyan nodes \(u_{4}\), \(u_{3}\) and \(u_{5}\)) are updated by the red dotted arrows, respectively, so that \(\hat{w}_{2}(u_{4})=\frac{2}{0.5}+0=4\), \(\hat{w}_{3}(u_{4})=\frac{2}{0.5}+0=4\) and \(\hat{w}_{m}(u_{4})=4\). Thus, the values of the other two nodes (blue font marked next to the node) can be obtained in the same way; 3. Compare the values of nodes (\(u_{3}\), \(u_{4}\), \(u_{5}\)), the smallest node is \(u_{4}\), which is added to queue P, then the determined edge link is updated as shown in bold arrows. Update \(\hat{w}_{i}(v)\) and \(\hat{w}_{m}(v)\) of neighbor nodes (\(u_{1}\), \(u_{3}\)) of \(u_{4}\), it can obtain \(\hat{w}_{2}(u_{1})=\frac{1}{0.2}+4=9,\hat{w}_{3}(u_{1})=\frac{2}{0.2}+4=14, \hat{w}_{m}(u_{1})=14\), \(\hat{w}_{2}(u_{3})=\frac{2+0.5+0.4(-10.5).4}{1-(1-0.4)(1-0.5)}=4\), \(\hat{w}_{3}(u_{3})=5.43\), \(\hat{w}_{m}(u_{3})=5.43\); 4. Compare the values of nodes (\(u_{1}\), \(u_{3}\)), the smallest node is \(u_{3}\), which is added to queue P. Update \(\hat{w}_{i}(v)\) and \(\hat{w}_{m}(v)\) of neighbor node \(u_{1}\), it can obtain \(\hat{w}_{2}(u_{1})=\frac{1+0.5+0.2(-1.05).4}{1-(1-0.2)(1-0.5)}=5.67\), \(\hat{w}_{3}(u_{1})=8.52\), \(\hat{w}_{m}(u_{1})=8.52\). Thus, the values of node \(u_{2}\) can also be obtained (blue font marked above the node); 5. Compare the values of nodes (\(u_{1}\), \(u_{2}\)), the smallest node is \(u_{1}\), which is added to queue P. Update \(\hat{w}_{i}(v)\) and \(\hat{w}_{m}(v)\) of neighbor node s, it can obtain \(\hat{w}_{2}(s)=\frac{3}{0.5}+5.67=11.67\), \(\hat{w}_{3}(s)=\frac{3}{0.5}+8.52=14.52\), \(\hat{w}_{m}(s)=14.52\); 6. Through the reverse order search, the source node s is finally added to the queue P, and the anypath routing \(P=\{s,u_{1},u_{3},u_{4},t\}\) is found. Thus, the first weight can be obtained by \(\hat{w}_{1}(u_{4})=8,\hat{w}_{1}(u_{3})=\frac{46}{7},\hat{w}_{1}(u_{1})=13 \frac{10}{21}\) and \(\hat{w}_{1}(s)=\frac{2}{0.5}+13\frac{10}{21}=17\frac{10}{21}\). Check the first constraint that \(\hat{w}_{1}(s,P)=17\frac{10}{21}\leq L_{1}=18\), then the HMAA algorithm ends and the anypath routing \(P_{s}^{*}=P\) is found, where \(\hat{w}_{m}(s,P_{s}^{*})=14.52\).  
**Remark 2**.: _As shown in Figure 2a, the anypath routing \(P_{s}^{*}\) found by HMAA algorithm can calculate the AAW value of \(14.52\); Figure 2b shows the actual optimal anypath routing\(P_{s}^{opt}\) in WMNs, thus the AAW value can be calculated by \(\hat{w}_{m}(s,P_{s}^{opt})=12.85\). According to Definition 3,  
Figure 1: An example of the anypath computed by HMAA algorithm.  
we can observe that \(=\vartheta_{m}(s,P_{s}{}^{*})/\vartheta_{m}(s,P_{s}{}^{opt})=14.52/12.85\approx 1.13\), so the solution found in this example by HMAA is a 1.13-approximation optimal anypath routing._