Adaptive Power, Adaptive Rate Scheduling in Spatial-TDMA Wireless Networks
Nov 17, 2011
from 01:00 PM to 03:00 PM
|Where||Maxwell Room 57-124, Engineering IV Building|
|Add event to calendar||
Advisor, Professor Izhak Rubin
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 levels at
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 and show that the latter yields a solution that consists of transmit power levels that are strongly Pareto Optimal. 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 an extended interference graph. The desired schedule is then derived by using a
greedy algorithm to construct an independence set from this graph. We show, for smaller illustrative networks, the performance of the heuristic algorithms to generally be in the 75 percentile of those attained by the optimal schedule. We also show that performance of our heuristic algorithm to be better than the existing scheduling algorithms that use fixed transmit power and rate.We then present a distributive heuristic algorithm for link scheduling in adaptive power and rate spatial-TDMA wireless mesh networks. At each step of our algorithm, the link with highest receive Signal-to-
Interference-and-Noise-Ratio in its neighborhood is included in the schedule for the underlying time slot to transmit at the highest feasible power and rate level. We show the performance of the distributive algorithm to be within 5-10% of the 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 present a class of heuristic algorithms for adaptive power, adaptive rate multicast scheduling in a cellular system, 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 then extend the basic algorithm such that, in addition to the 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 even compared to the complex LTE MBSFN schemes studied in other papers, while it consume less energy.
Kian Hedayati received his B.S. in Electrical engineering and Computer Science from UC Berkeley in 2004. He got his M.S. in Electrical Engineering from UCLA in 2006. From 2006 to 2008 he worked for Cisco Systems as an ASIC design engineer. Since 2008 he has been working toward his Ph.D. in electrical engineering at UCLA. His research area is link scheduling and resource allocation in TDMA wireless networks.