TY - JOUR
T1 - Bandwidth-constrained routing problem in wireless Ad Hoc networks
AU - Chiu, Chun Yuan
AU - Kuo, Yu Liang
AU - Wu, Eric Hsia Kuang
AU - Chen, Gen Huey
PY - 2008/1
Y1 - 2008/1
N2 - The bandwidth-constrained routing problem (BCRP) asks for a route that has sufficient bandwidth for data transmission. When BCRP is defined for wired networks, it can be solved in polynomial time. On the other hand, when it is defined for wireless ad-hoc networks, it is NP-complete if the underlying MAC protocol is TDMA-based or CDMA-over-TDMA-based. In this paper, we show that BCRP is still NP-complete, even if CSMA-based or contention-based CDMA MAC protocols areused. Besides, we show that BCRP is polynomial-time solvable if the channel model is collision-free and the scheduling policy is FIFO. In wireless ad-hoc networks, no MAC protocol was designed before which would lead to a polynomial-time solution to BCRP. The results of this paper suggest a design principle for MAC protocols that can support QoS routing well.
AB - The bandwidth-constrained routing problem (BCRP) asks for a route that has sufficient bandwidth for data transmission. When BCRP is defined for wired networks, it can be solved in polynomial time. On the other hand, when it is defined for wireless ad-hoc networks, it is NP-complete if the underlying MAC protocol is TDMA-based or CDMA-over-TDMA-based. In this paper, we show that BCRP is still NP-complete, even if CSMA-based or contention-based CDMA MAC protocols areused. Besides, we show that BCRP is polynomial-time solvable if the channel model is collision-free and the scheduling policy is FIFO. In wireless ad-hoc networks, no MAC protocol was designed before which would lead to a polynomial-time solution to BCRP. The results of this paper suggest a design principle for MAC protocols that can support QoS routing well.
KW - Algorithm/protocol design and analysis
KW - Mobile communication systems
KW - Reducibility and completeness
KW - Routing protocols
UR - http://www.scopus.com/inward/record.url?scp=37149033380&partnerID=8YFLogxK
U2 - 10.1109/TPDS.2007.70713
DO - 10.1109/TPDS.2007.70713
M3 - 期刊論文
AN - SCOPUS:37149033380
SN - 1045-9219
VL - 19
SP - 4
EP - 14
JO - IEEE Transactions on Parallel and Distributed Systems
JF - IEEE Transactions on Parallel and Distributed Systems
IS - 1
ER -