# A Guaranteed Approximation Algorithm for QoS Anypath Routing in WMNs
## 2 Problem Description and Related Works  
This paper is based on the weight of node v in the network, and the weight on the edge represents the forwarding probability. In the existing study of routing protocol [22; 23; 24], there are at least three Media Access Control (MAC) layer protocols that can support anypath routing. The anypath routing for WMNs and the Expected Weight of Anypath Transmissions (EWATX) were modeled in [16], based on which the research of this paper is carried out. First, the basic anypath routing DMCAP is introduced, and then the MCOAP studied in this paper is proposed. Frequently used notations are shown in Table 1.  
Definition 1: DMCAP Problem. Consider a directed and connected graph \(\mathbf{G}(\mathbf{V},\widetilde{\mathbf{W}},\widetilde{\mathbf{L}}, \widetilde{\mathbf{p}})\), where \(|\mathbf{V}|=n\) is the set of vertices in the figure, \(|\mathbf{E}|=m\) is the set of edges, \(p(e)\in(0,1]\) is the probability of packet forwarding on one edge, the ith weight on a node \(v\in\mathbf{V}\) is \(w_{i}(v)\), \(\widetilde{\mathbf{W}}=\{w_{i}(v)\}|w_{i}(v)\geq 0\) is the set of total weights on node \(v\); the positive matrix \(\widetilde{\mathbf{L}}=(L_{1},L_{2},\ldots,L_{K})\) is a set of \(\mathbf{K}(\mathbf{K}\geq 3)\) QoS constraints. The DMCAP problem is to find an anypath routing from \(s\) to \(t\) to satisfy the condition. \[w_{i}(s,P_{s})\leq L_{i},\forall 1\leq i\leq K. \tag{1}\]  
An anypath routing that satisfies formula (1) is called a feasible solution to the DMCAP problem, thus all feasible anypath routing in graph G are expressed as \(\{P_{s}\}\). However, a feasible solution to the DMCAP problem is computationally very complex, and the literature [16] proves that it is a NP-hard problem. \begin{table}
\begin{tabular}{c c} \hline \(s\), \(t\) & the source node and the destination node, respectively \\ \(m\), \(n\) & the edge and the node number of graph \(\mathbf{G}\), respectively \\ \(w_{i}(v)\) & ith weight of node \(v\) \\ \(p(v,u)\) & forwarding probability from node \(v\) to node \(u\) \\ \(F\) & forwarding sets of node \(v\) \\ \(p(v,\mathbf{F})\) & forwarding probability from node \(v\) to forwarding sets \(\mathbf{F}\) \\ K & the number of QoS requirements \\ \(\widetilde{\mathbf{W}}\) & the set of weights of the edges \\ \(\widetilde{\mathbf{L}}\) & the set of constraints \\ \(L_{i}\) & ith QoS requirement \\ \(P_{s}\) & the anypath routing from source node \(s\) to destination node \(t\) \\ \(p_{s}\)\({}^{opt}\) & the optimal anypath routing \\ \(P_{s}\)\({}^{*}\) & the approximate optimal anypath routing \\ \(w_{i}(v,P_{s})\) & ith weight from node \(v\) to destination node \(t\) along \(P_{s}\) \\ \(w_{\mathbf{M}}(v)\) & the maximum weight of node \(v\) \\ \(w_{u}(v,P_{s})\) & the maximum weight from node \(v\) to destination node \(t\) along \(P_{s}\) \\ \(w_{u}(\mathbf{F},P_{s})\) & the maximum weight from forwarding sets \(\mathbf{F}\) to destination node \(t\) along \(P_{s}\) \\ \hline \end{tabular}
\end{table} 
Table 1: Frequently used notations. **Definition 2**. : _MCOAP Problem. The MCOAP problem is to find an optimal anypath among all the anypath routing \(\{P_{s}\}\) from \(s\) to \(t\) that satisfies the constraints and minimizes the other values of the anypath routing._  
The computing performance of the routing adapters in WMNs is limited, so it seems unrealistic to run an intelligent algorithm and spend a lot of time on finding a feasible solution to the DMCAP problem. In wireless multimedia applications, more and more business application requirements turn out to be mandatory to meet a QoS constraint while approximating the remaining QoS constraints from an approximate perspective. This paper introduces the anypath auxiliary length value \(\hat{w}(v,P_{s})\) shown in Equation (2)  
\[\hat{w}(v,P_{s})=\max_{2\leq i\leq\mathrm{K}}\frac{w_{i}(v,P_{s})}{L_{i}}. \tag{2}\]  
**Definition 3**. : \(\alpha(\alpha\geq 1)\) _approximation algorithm.