MAP: Multiconstrained Anypath Routing in Wireless Mesh Networks
Authors:
- 19 July 2012
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Mobile Computing
- Vol. 12 (10) , 1893-1906
Abstract
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 concentrated on finding an anypath, which optimizes a single quality of service (QoS) parameter. In this paper, we study anypath routing subject to multiple constraints. We first prove that the problem is NP-hard when the number of constraints is larger than one. We then present a polynomial time K--approximation algorithm MAP, where K is the number of constraints. Our algorithm is as simple as Dijkstra's shortest path algorithm. Therefore, it is suitable for implementation in wireless routing protocols.Keywords
This publication has 30 references indexed in Scilit:
- Exploiting path diversity in the link layer in wireless ad hoc networksAd Hoc Networks, 2008
- On End-to-End Throughput of Opportunistic Routing in Multirate and Multihop Wireless Networks2008
- On selection of candidates for opportunistic anypath forwardingACM SIGMOBILE Mobile Computing and Communications Review, 2006
- Wireless Communications2005
- Geographic random forwarding (geraf) for ad hoc and sensor networks: multihop performanceIEEE Transactions on Mobile Computing, 2003
- An overview of constraint-based path selection algorithms for QoS routingIEEE Communications Magazine, 2002
- Heuristic algorithms for multiconstrained quality-of-service routingIEEE/ACM Transactions on Networking, 2002
- Selection diversity forwarding in a multihop packet radio network with fading channel and captureACM SIGMOBILE Mobile Computing and Communications Review, 2001
- A randomized algorithm for finding a path subject to multiple QoS requirementsComputer Networks, 2001
- Algorithms for finding paths with multiple constraintsNetworks, 1984