Title :
Bandwidth reservation in multihop wireless networks: complexity and mechanisms
Author :
Georgiadis, Leonidas ; Jacquet, Philippe ; Mans, Bernard
Author_Institution :
Dept. of Electr. & Comput. Eng., Aristotelian Univ. of Thessaloniki, Greece
Abstract :
We show that link interferences in multihop wireless networks make the problem of selecting a path satisfying bandwidth requirements an NP-complete problem, even under simplified rules for bandwidth reservation. This is in sharp contrast to path selection in wireline networks where efficient polynomial algorithms exist. We also describe a distributed mechanism for the problem of slot allocation according to bandwidth reservation in a wireless slotted environment.
Keywords :
ad hoc networks; bandwidth allocation; computational complexity; mobile computing; quality of service; telecommunication links; wireless LAN; NP-complete problem; bandwidth reservation; multihop wireless networks; polynomial algorithms; slot allocation; wireline networks; Admission control; Bandwidth; Communication system traffic control; Electronic mail; Intelligent networks; Interference; Mobile ad hoc networks; Network topology; Quality of service; Spread spectrum communication;
Conference_Titel :
Distributed Computing Systems Workshops, 2004. Proceedings. 24th International Conference on
Print_ISBN :
0-7695-2087-1
DOI :
10.1109/ICDCSW.2004.1284119
