Bandwidth Reservation in Multihop Wireless Networks: Complexity, Heuristics and Mechanisms
Géraud Allard, Leonidas G. Georgiadis, Philippe Jacquet, Bernard Mans · 2004
We prove 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 propose three heuristics to compute Quality of Service (QoS) routes in a multihop wireless networks considering interferences constraints. Our heuristics are based on Dijkstra’s shortest path algorithm in which we integrate the notion of node capacity in order to satisfy flow requirements. We show with several simulations that these heuristics allow computation of routes that save bandwidth of nodes with low capacity and thus result in increased number of QoS-flows accepted by the network. Finally, we also describe a distributed mechanism for the problem of slot allocation according to bandwidth reservation in a wireless slotted environment.