A Distributed Algorithm for Multi-Constrained Anypath Routing in Wireless Mesh Networks

Anypath routing, a new routing paradigm, has been proposed to improve the performance of wireless networks by exploiting the spatial diversity and broadcast nature of the wireless medium. In this paper, we study the problem of finding an anypath subject to multiple (K) constraints, which has been proved to be NP-hard. We present a polynomial distributed K-approximation routing algorithm. Our algorithm is as simple as Bellman-Ford´s shortest path algorithm. Extensive experiments show that our algorithm is very efficient and its result is as good as that obtained by the best centralized algorithm which requires the global information.