Integrated Power Controlled Adaptive Rate Link Scheduling in Wireless Mesh Networks

In this paper, two new heuristic algorithms are developed for maximizing the network throughput in adaptive power and adaptive rate spatial-TDMA wireless networks. The underlying problem entails the optimal joint link scheduling combined with the simultaneous assignment of transmit power levels and data rates across active links. We note this problem to be NP-complete and proceed to develop and investigate two heuristic algorithms of polynomial complexity for solving the problem in a computationally effective manner. The first 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. The second algorithm, in each time-slot, picks the transmission with highest SINR level at its intended receiver; then it iterates through the remaining transmissions and tries to fit as many simultaneous transmissions with each operating at the highest feasible data rate. Based on system analyses, we observe, for illustrative simulated networks, the performance behavior realized by the second heuristic algorithm to be generally better than that attained by using the first heuristic algorithm.