A Guaranteed Approximation Algorithm for QoS Anypath Routing in WMNs

Abstract

Anypath routing is a hot research topic for QoS guarantee in wireless mesh networks (WMNs). According to time-varying characteristics of WMNs and the idea of anypath routing, a system network modeling method is proposed to address the multiple constrained optimization anypath problem. It focuses on the application of WMNs; under various QoS constraints, it satisfies a specific constraint and approaches other QoS constraints from an approximate perspective. A heuristic multi-constrained anypath algorithm with a time complexity as Dijkstra is proposed for the problem, and the algorithm is proved to be a K-1 approximation algorithm. The feasibility of the algorithm is verified, then its computational efficiency and performance are evaluated through simulation experiments, respectively. According to the application characteristics of wireless networks, the algorithm is suitable for WMNs and has good compatibility with existing routing protocols.

Keywords

• wireless mesh networks
• anypath routing
• multi-constrained QoS
• approximation algorithm