MAP: Multi-Constrained Anypath Routing in Wireless Mesh Networks
Anypath routing has been proposed to improve the performance of unreliable wireless networks by exploiting the spatial diversity and broadcast nature of the wireless medium. Previous studies on anypath routing have been concentrated on finding an anypath which optimizes a single Quality of Service (QoS) parameter. In this paper, the authors study anypath routing subject to multiple constraints. They first prove that the problem is NP-hard when the number of constraints is larger than one. They then present a polynomial time K-approximation algorithm MAP (Multi-constrained Any-Path), where K denotes the number of constraints. Their algorithm is as simple as Dijkstra's shortest path algorithm. Therefore it is suitable for implementation in wireless routing protocols.