Adaptive Power, Adaptive rate Scheduling in Spatial TDMA Wireless Networks

The purpose of this dissertation is to study the problem of scheduling with power control and rate adaption in TDMA wireless networks. First, we study the problem of adaptive power, adaptive rate link scheduling in TDMA wireless mesh networks and develop a mathematical model to solve the problem and analyze its characteristics. We then extend our model to a cellular wireless network and study the problem of multicast scheduling with adaptive power and adaptive rate in cellular networks.;Power control and link scheduling in wireless mesh network have been the topic of many research works in the last decade. However, we have found no published papers that present effective algorithms that solve the link scheduling problem jointly with power control and rate adaptation. The underlying problem entails the optimal joint scheduling of transmissions across multi-access communication links combined with the simultaneous allocation of transmit power levels and data rates across active links, while meeting required Signal-to-Interference-plus-Noise Ratio (SINR) levels at intended receivers.;To study this problem, we first develop a new mathematical programming model for minimizing the schedule length in adaptive power and adaptive rate link scheduling in spatial-TDMA wireless networks. We prove that the problem can be modeled as a Mixed Integer-Linear Programming (MILP) and show that the latter yields a solution that consists of transmit power levels that arc strongly Pareto Optimal. We note this problem to be NP-complete. Then we proceed to develop and investigate centralized heuristic algorithm of polynomial complexity for solving the problem in a computationally effective manner. The algorithm is based on the construction of a Power Controlled Rate adaptation Interference Graph. The desired schedule is then derived by using a greedy algorithm to construct an independence set from this graph. Based on system analyses, we show, for smaller illustrative networks, the performance behavior realized by the heuristic algorithms to generally he in the 75 percentile of those attained by the optimal schedule. We also show that performance of our heuristic algorithm is on average 20% better than that attained under prior algorithms that were developed for use under fixed transmit power and fixed rate link scheduling.;We then present a distributive heuristic algorithm for maximizing the network throughput in adaptive power and adaptive rate spatial-TDMA wireless mesh networks. At each step of our algorithm, the link kith highest receive Signal-to-Interference and Noise Ratio in its neighborhood is included in the schedule for the underlying time slot, configuring its Modulation/Coding Scheme so that it transmits at the highest feasible power and rate levels. We show the performance of this distributive algorithm to be within 5-10% of that exhibited by our centralized algorithm, while inducing a much lower computational complexity. We also demonstrate the robustness and energy efficiency of our distributive algorithm by applying it to schedule a new set of links on top of an existing schedule.;We then study the problem of multicast scheduling jointly with power control and rate adaptation in cellular wireless networks. We present a class of heuristic algorithms for adaptive power, adaptive rate scheduling for multicasting in a cellular wireless network, where members of the multicast group are scattered across the area cells. The presented basic algorithm strives to achieve a high receive throughput by scheduling, in each time-slot, certain base stations to multicast at selected transmit power and rate levels. We extend the basic algorithm such that, in addition to base stations, mobile stations can be elected to relay multicast messages, which they have received from their base stations. We study the performance of our algorithms, and show that our relay-aided algorithm achieves better performance, while it consumes less energy. We also demonstrate the robustness of our relay-aided algorithm by applying it to multicast packets in a network where some of the base stations have failed.