Browsing by Subject "Scheduling algorithms"
Now showing 1 - 2 of 2
- Results Per Page
- Sort Options
Item High-performance scheduling algorithms for wireless networks(2010-12) Bodas, Shreeshankar Ravishankar; Vishwanath, Sriram; Shakkottai, Sanjay; Caramanis, Constantine; de Veciana, Gustavo; Hasenbein, John; Srikant, R.The problem of designing scheduling algorithm for multi-channel (e.g., OFDM-based) wireless downlink networks is considered, where the system has a large bandwidth and proportionally large number of users to serve. For this system, while the classical MaxWeight algorithm is known to be throughput-optimal, its buffer-overflow performance is very poor (formally, it is shown that it has zero rate function in our setting). To address this, a class of algorithms called iHLQF (iterated Heaviest matching with Longest Queues First) is proposed. The algorithms in this class are shown to be throughput-optimal for a general class of arrival/channel processes, and also rate-function optimal (i.e., exponentially small buffer overflow probability) for certain arrival/channel processes, where the channel-rates are 0 or 1 packets per timeslot. iHLQF however has higher computational complexity than MaxWeight (n⁴ vs. n² computations per timeslot respectively). To overcome this issue, a new algorithm called SSG (Server-Side Greedy) is proposed. It is shown that SSG is throughput-optimal, results in a much better per-user buffer overflow performance than the MaxWeight algorithm (positive rate function for certain arrival/channel processes), and has a computational complexity (n²) that is comparable to the MaxWeight algorithm. Thus, it provides a nice trade-off between buffer-overflow performance and computational complexity. For multi-rate channel processes, where the channels can serve multiple packets per timeslot, new Markov chain-based coupling arguments are used to derive rate-function positivity results for the SSG algorithm. Finally, an algorithm called DMEQ is proposed and shown to be rate-function optimal for certain multi-rate channel scenarios, whose definition characterizes the sufficient conditions for rate-function optimality in this regime. These results are validated by both analysis and simulations.Item On distributed scheduling for wireless networks with time-varying channels(2013-05) Reddy, Akula Aneesh; Shakkottai, SanjayWireless scheduling is a fundamental problem in wireless networks that involves scheduling transmissions of multiple users in order to support data flows with as high rates as possible. This problem was first addressed by Tassuilas and Ephremides, resulting in the celebrated Back-Pressure network scheduling algorithm. This algorithm schedules network links to maximize throughput in an opportunistic fashion using instantaneous network state information (NSI), i.e., queue and channel state knowledge across the entire network. However, the Back-Pressure (BP) algorithm suffers from various drawbacks - (a) it requires knowledge of instantaneous NSI from the whole network, i.e. feedback about time-varying channel and queue states from all links of the network, (b) the algorithm requires solving a global optimization problem at each time to determine the schedule, making it highly centralized. Further, Back-pressure algorithm was originally designed for wireless networks where interference is modeled using protocol interference model. As recent break-throughs in full-duplex communications and interference cancelation techniques provide greatly increased capacity and scheduling flexibility, it is not clear how BP algorithm can be modified to improve the data rates and reduce the delay. In this thesis, we address the drawbacks of Back-Pressure algorithm to some extent. In particular, our first work provides a new scheduling algorithm (similar to BP) that allows users to make individual decisions (distributed) based on heterogeneously delayed network state information (NSI). Regarding the complexity issue, in our second work, we analyze the performance of the greedy version of BP algorithm, known as Greedy Maximal Scheduling (GMS) and understand the effect of channel variations on the performance of GMS. In particular, we characterize the efficiency ratio of GMS in wireless networks with fading. In our third and fourth work, we propose and analyze new scheduling algorithms that can benefit from new advancements in interference cancelation techniques.