Scheduling algorithms for next generation cellular networks

Official URL: http://192.168.1.20/record=b1505284 (Table of Contents)

Next generation wireless and mobile communication systems are rapidly evolving to satisfy the demands of users. Due to spectrum scarcity and time-varying nature of wireless networks, supporting user demand and achieving high performance necessitate the design of efficient scheduling and resource allocation algorithms. Opportunistic scheduling is a key mechanism for such a design, which exploits the time-varying nature of the wireless environment for improving the performance of wireless systems. In this thesis, our aim is to investigate various categories of practical scheduling problems and to design efficient policies with provably optimal or near-optimal performance. An advantage of opportunistic scheduling is that it can effectively be incorporated with new communication technologies to further increase the network performance. We investigate two key technologies in this context. First, motivated by the current under-utilization of wireless spectrum, we characterize optimal scheduling policies for wireless cognitive radio networks by assuming that users always have data to transmit. We consider cooperative schemes in which secondary users share the time slot with primary users in return for cooperation, and our aim is to improve the primary systems performance over the non-cooperative case. By employing Lyapunov Optimization technique, we develop optimal scheduling algorithms which maximize the total expected utility and satisfy the minimum data rate requirements of the primary users. Next, we study scheduling problem with multi-packet transmission. The motivation behind multi-packet transmission comes from the fact that the base station can send more than one packets simultaneously to more than one users. By considering unsaturated queueing systems we aim to stabilize user queues. To this end, we develop a dynamic control algorithm which is able to schedule more than one users in a time slot by employing hierarchical modulation which enables multi-packet transmission. Through Lyapunov Optimization technique, we show that our algorithm is throughput-optimal. We also study the resulting rate region of developed policy and show that it is larger than that of single user scheduling. Despite the advantage of opportunistic scheduling, this mechanism requires that the base station is aware of network conditions such as channel state and queue length information of users. In the second part of this thesis, we turn our attention to the design of scheduling algorithms when complete network information is not available at the scheduler. In this regard, we study three sets of problems where the common objective is to stabilize user queues. Specifically, we first study a cellular downlink network by assuming that channels are identically distributed across time slots and acquiring channel state information of a user consumes a certain fraction of resource which is otherwise used for transmission of data. We develop a joint scheduling and channel probing algorithm which collects channel state information from only those users with su±ciently good channel quality. We also quantify the minimum number of users that must exist to achieve larger rate region than Max-Weight algorithm with complete channel state information. Next, we consider a more practical channel models where channels can be time-correlated (possibly non-stationary) and only a fixed number of channels can be probed. We develop learning based scheduling algorithm which tracks and predicts instantaneous transmission rates of users and makes a joint scheduling and probing decision based on the predicted rates rather than their exact values. We also characterize the achievable rate region of these policies as compared to Max-Weight policy with exact channel state information. Finally, we study a cellular uplink system and develop a fully distributed scheduling algorithm which can perform over general fading channels and does not require explicit control messages passing among the users. When continuous backoff time is allowed, we show that the proposed distributed algorithm can achieve the same performance as that of centralized Max-Weight algorithm in terms of both throughput and delay. When backoff time can take only discrete values, we show that our algorithm can perform well at the expense of low number of mini-slots for collision resolution.