Interference‐aware routing and bandwidth allocation for QoS provisioning in multihop wireless networks

Abstract

Abstract In this paper, we study the bandwidth guaranteed routing and timeslot allocation (BANDRA) in TDMA‐based multihop wireless networks with dynamic traffic. We formally model BANDRA as an optimization problem and present an integer linear programming (ILP) formulation to provide optimal solutions. This problem turns out to be a hard problem because of the impact of interference. Therefore, we propose a two‐step scheme, i.e., seeking a path for routing first and then allocating bandwidth along the found path. We present two routing algorithms to compute interference‐optimal cost‐bounded paths. In addition, we present an optimal bandwidth allocation algorithm to allocate timeslots along the found paths for connection requests with unit bandwidth requirements. For the general case where the bandwidth requirement is larger than one, we present an effective heuristic algorithm. Our simulation results show that the average difference between solutions given by our efficient scheme and optimal ones in terms of call‐blocking ratio is only 7%. Compared with the shortest path routing, our interference‐aware routing algorithms combined with our bandwidth allocation algorithm always reduce call‐blocking ratios. Copyright © 2005 John Wiley & Sons, Ltd.