Scheduling in wireless cellular data networks

This thesis studies the performance of scheduling policies in a wireless cellular data network. We consider a cell within the network. The cell has a single base station serving a given number of users in the cell. Time is slotted and the base station can serve at most one user in a given time slot. The users are mobile and therefore the data transfer rate available to each user changes from time slot to time slot depending on the distance from the base station and the terrain of the user.;There are two conflicting objectives for the base station: maximize the data throughput per time slot, and maintaining "fairness". To maximize the data throughput, the base station would like to serve the user with the highest available data rate, but this can lead to starvation of some users. To ensure "fairness", no user should be unserved for a "long" time, i.e., users should be served in a round-robin manner. Although this problem has been studied in the literature to some extent, existing methods to do this are ad-hoc. Our goal is to derive policies that have a sound theoretical basis, and at the same time are computationally tractable, are easy to implement, are fair to all the users and beneficial for the service providers.;We formulate the problem of finding an optimal scheduling policy as a Markov Decision Process (MDP) and prove some characteristics of the optimal policy. Since solving the MDP to optimality is infeasible, given the huge size of the problem, we develop heuristic policies called "index policies". These policies are based on a closed form "index" for every user that depends only its own current state. We derive this index using a policy improvement approach based on Markov Decision Processes. We also compare their performance with existing policies through simulation. We develop such index policies in two settings: when every user always has ample data waiting for it to be served (the infinitely backlogged case), and when data arrives for every user in every time slot according to some distribution (the external data arrival case).;Further, we consider the case of users entering and leaving the cell as well, but only from a simulation perspective.