A Distributed Algorithm for Multi-Constrained Anypath Routing
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, the authors study the problem of finding an anypath subject to multiple (K) constraints, which has been proved to be NP-hard. They present a polynomial time distributed K-approximation routing algorithm. The algorithm is as simple as Bellman-Ford's shortest path algorithm. Extensive experiments show that the algorithm is very efficient and its result is as good as that obtained by the best centralized algorithm which however requires global information.