Name
Abstract | ||
|---|---|---|
The bandwidth-constrained routing problem (BCRP) asks for a route that has sufficient bandwidth for datatransmission. When BCRP is defined for wired networks, it can be solved in polynomial time. On the other hand, when it isdefined for wireless ad-hoc networks, it is NP-complete if the underlying MAC protocol is TDMA-based or CDMA-over-TDMAbased.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 isFIFO. 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. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1109/TPDS.2007.70713 | IEEE Trans. Parallel Distrib. Syst. |
Keywords | Field | DocType |
bandwidth-constrained routing problem,polynomial-time solvable,channel model,wireless ad-hoc network,design principle,underlying mac protocol,contention-based cdma mac protocol,mac protocol,wireless ad hoc networks,qos routing,polynomial-time solution,ad hoc networks,quality of service,data transmission,communication complexity,polynomials,routing protocols,mobile ad hoc networks,np complete problem,polynomial time,time division multiple access,bandwidth,wireless application protocol,wireless ad hoc network,routing protocol,cdma | Mobile ad hoc network,Dynamic Source Routing,Computer science,Computer network,Wireless Routing Protocol,Adaptive quality of service multi-hop routing,Ad hoc wireless distribution service,Optimized Link State Routing Protocol,Wireless ad hoc network,Routing protocol,Distributed computing | Journal |
Volume | Issue | ISSN |
19 | 1 | 1045-9219 |
Citations | PageRank | References |
5 | 0.41 | 23 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Chun-Yuan Chiu | 1 | 41 | 4.36 |
| Yu-liang Kuo | 2 | 91 | 8.81 |
| Wu, E.H.-K. | 3 | 339 | 39.53 |
| guihai chen | 4 | 3537 | 317.28 |