@inproceedings{139661a31cdd4c5aa1763a5fe423ff30,
title = "Bandwidth constrained routing problem in multi-hop wireless networks",
abstract = "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 multi-hop wireless 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 are used. Besides, we show that BCRP is polynomial-time solvable if the underlying MAC protocol adopts CDMA channel model and FIFO scheduling policy. In multi-hop wireless 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.",
keywords = "Bandwidth, MAC, Multi-hop wireless network, NP-complete, QoS routing",
author = "Chiu, {Chun Yuan} and Kuo, {Yu Liang} and Wu, {Hsiao Kuang} and Chen, {Gen Huey}",
year = "2006",
doi = "10.1145/1164717.1164779",
language = "???core.languages.en_GB???",
isbn = "1595934774",
series = "ACM MSWiM 2006 - Proceedings of the 9th ACM Symposium on Modeling, Analysis and Simulation of Wireless and Mobile Systems",
publisher = "Association for Computing Machinery",
pages = "365--369",
booktitle = "ACM MSWiM 2006 - Proceedings of the Ninth ACM Symposium on Modeling, Analysis and Simulation of Wireless and Mobile Systems",
note = "ACM MSWiM 2006 - 9th ACM Symposium on Modeling, Analysis and Simulation of Wireless and Mobile Systems ; Conference date: 02-10-2006 Through 06-10-2006",
}