Recent research has shown that interference can make a significant impact on the performance of multihop wireless networks. Researchers have studied interference-aware topology control recently [M. Burkhart et al., 2004]. In this paper, we study routing problems in a multihop wireless network using directional antennas with dynamic traffic. We present new definitions of link and path interference that are suitable for designing better routing algorithms. We then formulate and optimally solve two power constrained minimum interference single path routing problems. Routing along paths found by our interference-aware algorithms tends to have less channel collisions and higher network throughput. Our simulation results show that, compared with the minimum power path routing algorithm, our algorithms can reduce average path interference by 40% or more at the cost of a minor power increase. We also extend our work towards survivable routing by formulating and solving the power constrained minimum interference node-disjoint path routing problem.

Throughput is an important performance consideration for multihop wireless networks. In this paper, we study the joint link scheduling and power control problem, focusing on maximizing the network throughput. We formulate the maximum throughput link scheduling with power control (MATH-SPC) problem, and present a mixed integer linear programming (MILP) formulation to provide optimal solutions. However, simply maximizing the throughput leads to a severe bias on bandwidth allocation among all links. In order to enhance both throughput and fairness, we define a new parameter, the demand satisfaction factor (DSF), to characterize the fairness of bandwidth allocation. We formulate the maximum throughput fair link scheduling with power control (MATA-SPC) problem and present an MILP formulation for this problem. We also present an effective polynomial time heuristic algorithm, namely, the serial LP rounding (SLPR) heuristic. Our numerical results show that bandwidth can be fairly allocated among all links/flows by solving our MATA-SPC formulation or using our heuristic algorithm at the cost of a minor reduction of network throughput.

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.