Bandwidth Reservation in Multihop Wireless Networks: Complexity and Mechanisms

Leonidas Georgiadis (1) , Philippe Jacquet (1) , Bernard Mans (1)

1 HIPERCOM - High performance communication

We show that link interferences in wireless networks make multihop bandwidth reservation in such an environment an NP-complete problem. This is in sharp contrast to bandwidth reservation in wireline networks where efficient polynomial algorithms exist. We also consider the problem of slot allocation according to bandwidth requirements in a wireless slotted environment. In the context of Mobile Ad Hoc Networks, we propose simple heuristics applicable to the OLSR routing protocol in order to find routes that satisfies requirements without impairing the performance of other connections.

Mots clés: rather than a base station as in cellular systems; noise and interference than wireline networks. This is especially true in wireless ad hoc networks; where packets are relayed by mobile nodes; rather than a base station as in cellular systems.; MOBILE AD HOC; BANDWIDTH RESERVATION; QOS; COMPLEXITY; NP COMPLETENESS MULTIMEDIA FLOWS NEED TO SATISFY CERTAIN PERFORMANCE REQUIREMENTS; SUCH AS; BANDWIDTH GUARANTEES AND UPPER BOUNDS ON PACKET LOSSES AND END-TO-END DELAY IN ORDER TO FUNCTION PROPERLY. THESE REQUIREMENTS ARE GENERALLY KNOWN as Quality of Service (QoS) guarantees. Satisfaction of QoS guarantees has been an active area of research in wireline networks for several years. The same issue becomes more challenging in radio mobile networks where capacity is a scarce resource and packet transmissions are more prone to errors

Domaines: Autre [cs.OH]

Leonidas Georgiadis, Philippe Jacquet, Bernard Mans. Bandwidth Reservation in Multihop Wireless Networks: Complexity and Mechanisms. [Research Report] RR-4876, INRIA. 2003. ⟨inria-00071707⟩