# A Guaranteed Approximation Algorithm for QoS Anypath Routing in WMNs
## 1 Introduction  
In the process of the rapid development of the Internet of Things, new wireless mesh networks (WMNs) are generated by the convergence of WLAN and ad-hoc networks due to the presence of a large number of sensors and corresponding communication methods [1; 2; 3]. In recent years, a large number of applications of WMNs have appeared in people's life, such as wireless telemedicine, wireless online shopping, wireless video on demand, wireless multi-party voice conferences, and so on. As a result, people are very concerned about the quality of service (QoS) of WMNs, such as the delay, delay jitter, cost, bandwidth, and so on. In WMNs, to find the optimal path (minimum delay, minimum cost, or maximum bandwidth) from the source node to the destination node, many researchers have continued to conduct relevant studies [4; 5; 6; 7; 8; 9; 10; 11; 12]. In [13], the lowest cost anypath routing (LCAR) method was discussed, which was applied to low-power and low-rate wireless communications, then a new wireless link layer technology with high stability and robustness was introduced in combination with anypath routing to reduce transmission costs. On this basis, a new paradigm of wireless multi-hop network anypath routing was proposed [14]. They were all concerned about the guarantee of a certain QoS and mainly used unicast routing algorithms. In multi-rate routing, each node uses a set of next hops and a selected transmission rate to forward packets; thus, two polynomial time algorithms proved to be optimal and suitable for deployment in routing protocols are proposed. The LCAR method was extended to support multicast anypath routing from one source to multiple destinations [15], which can be used to calculate the multicast cost metrics and determine the forwarding policy for the forwarding set, so that the packets can effectively reach all destination nodes. Furthermore,the spatial diversity and broadcast properties of wireless media were used to improve the performance of unreliable wireless networks [16]. Considering the anypath routing with multiple constraints, a K approximation algorithm was proposed to approximate all constraints simultaneously [16]. The advantage of this method is that it runs very fast; however, on a small-scale network, the error of the optimal solution could not be guaranteed. Recently, the anypath routing method was proposed to improve the reliability of multi-hop vehicular ad-hoc network (vanet) communication [17]. It was the first time to solve the link stability firstly and propose a stable life path of the long lifecycle of the anypath routing method, which was better than the classic Shortest Anypath First (SAF) method. Considering that the spatial reusability of wireless communication media can greatly improve the end-to-end throughput of multi-hop wireless networks, a spatial reusable awareness of single-path routing and anypath routing protocol was proposed in [18], which significantly improved the performance on the basics of an existing protocol. Unfortunately, there was no literature on QoS guarantee algorithm for wireless multimedia applications based on this protocol. Moreover, the routing problem in a multi-hop cognitive network (CR) with the newly proposed CR as an example was studied in [19]. Considering the typical spectrum uncertainties of CR and the unreliable transmission of wireless media, an anypath routing scheme based on spectrum recognition was proposed. In the above research on WMNs, hot research on anypath routing is emerging, which aims to find an anypath routing method which ensures the optimal performance of one or more QoS metrics (such as delay, bandwidth, and power consumption). Previous research on anypath routing focused on considering a QoS metric constraint, calculating anypath routing with the minimum delay or minimum power consumption, or searching for anypath routing to ensure that one of the QoS parameters is optimal [17; 18; 19].