Ph.D Thesis

Ph.D StudentKatzir Liran
SubjectScheduling Algorithms for Efficient Delivery of Synchronous
Traffic in Wireless Access Networks
DepartmentDepartment of Computer Science
Supervisor PROF. Reuven Cohen
Full Thesis textFull thesis text - English Version


Scheduling algorithms are an integral part of network design. They are essential for reducing the congestion in the network, for enforcing fairness, for controlling the delay and jitter, and for saving scarce resources like energy and bandwidth. In wireless networks, scheduling algorithms are critical, because bandwidth is usually limited and it is shared by multiple nodes, and transmission errors are likely to take place. In this research we identify issues in wireless networks that must be addressed using efficient scheduling algorithms. We develop such algorithms, and test the schedulability of various applications under different network conditions.

In wireless networks many factors come into play when designing an efficient scheduler, including channel condition, channel load, and information due date. The increase in the number of factors that should be considered makes these schedulers more and more complicated. We proposed a new approach that is quantitative rather than qualitative. All relevant factors are translated into a merit function, and a schedule that maximizes the aggregated profit is then chosen.

The modulation of choice for IEEE 802.16 (WiMax) and IEEE 802.11 (WiFi) standards is Orthogonal Frequency Division Multiple Access (OFDMA). In these systems the downlink frame has a complex 2D structure. This structure incurs an overhead for a set of packets that share the transmission parameters. Therefore, a scheduler should take all previous considerations that deal with a wireless link and these new OFDMA constraints. We developed efficient algorithms that address the OFDMA scheduling problem that use the quantitative approach.

The broadcast push-based system for mobile users is a typical example of a system where time-critical data has to be sent to multiple receivers over a broadcast channel. In these systems a sent packet is shared by many users, unlike typical voice communication. We developed a quantitative scheduler that addresses the broadcast nature of these systems.

As a part of developing and applying the quantitative approach, we found some generic context-free theoretical computer science results. We found an efficient algorithm for a well-established theoretical problem in computer science known as the generalized assignment problem. In another result, we define a new theoretical problem called generalized maximum coverage. This problem is an extension of the budgeted maximum coverage problem, which in turn is an extension of the well-known maximum coverage problem. We provide an algorithm for this problem with a tight performance guarantee.