This thesis examines the problem of scheduling with incomplete and/or local information in wireless systems. With large numbers of users and limited feedback resources, wireless systems require good scheduling algorithms to attain their performance limits. Classical studies on wireless scheduling investigate in much detail settings where the full state of the system is available when scheduling users. In contrast, this thesis focuses on the case where valuable network state information is lacking at the scheduler, and studies its resulting effect on system performance. The insights gained from the analysis are used to develop efficient wireless scheduling algorithms that operate with limited state information, and that guarantee high throughput and delay performance. The first part of the thesis considers scheduling for stability in a wireless downlink system, where a base station or server schedules transmissions to users, while acquiring channel state information from only subsets of users. It is shown that the system’s throughput region is completely characterized by the marginal channel statistics over observable channel subsets. Effective, queue-length based joint sampling and scheduling algorithms are developed that observe appropriate subsets of channels and schedule users, and the algorithms are shown to be optimal in the sense of throughput. Next, the thesis studies the queue-length performance of wireless scheduling algorithms that use only partial, subset-based channel state information. The chief objective here is to design partial information-based scheduling algorithms that keep the packet queues in the system short, and in this regard, the contributions of this thesis are twofold. First, from the algorithmic perspective, wireless scheduling algorithms using partial channel state information are designed that minimize the likelihood of queue overflow, in a suitable sense, across all partial information scheduling algorithms. The second key contribution is technical, by the development of novel analytical techniques to study the stochastic dynamics of partial state information-based algorithms. These techniques are not only instrumental in showing the optimality results above, but are also of independent interest in understanding the behavior of algorithms which rely on partially sampled system state. The second part of the thesis investigates coordinated inter-cell wireless scheduling across multiple base stations, each possessing only local and partial channel state information for its own users. Coordinated scheduling is necessary to mitigate interference between users in adjacent cells, but information sharing between the base stations is limited by high latencies in the backhauls that interconnect them. A class of distributed scheduling algorithms is developed in which the base stations share only delayed queue length information with each other, and locally acquire partial channel state information, to schedule users. These algorithms are shown to be throughput-optimal, and their average backlog performance in terms of the inter-base station latency is quantified. / text

Cognitive radio technology is a promising technology to solve the wireless spectrum scarcity problem by intelligently allowing secondary, or unlicensed, users access to the primary, licensed, users' frequency bands. Cognitive technology involves two main tasks: 1) sensing the wireless medium to assess the presence of the primary users and 2) designing secondary spectrum access techniques that maximize the secondary users' benefits while maintaining the primary users' privileged status. On the spectrum sensing side, we make two contributions. First, we maximize a utility function representing the secondary throughput while constraining the collision probability with the primary below a certain value. We optimize therein the channel sensing time, the sensing decision threshold, the channel probing time, together with the channel sensing order for wideband primary channels. Second, we design a cooperative spectrum sensing technique termed sensing with equal gain combining whereby cognitive radios simultaneously transmit their sensing results to the fusion center over multipath fading reporting channels. The proposed scheme is shown to outperform orthogonal reporting systems in terms of achievable secondary throughput and to be robust against phase and synchronization errors. On the spectrum access side, we make four contributions. First, we design a secondary scheduling scheme with the goal of minimizing the secondary queueing delay under constraints on the average secondary transmit power and the maximum tolerable primary outage probability. Second, we design another secondary scheduling scheme based on the spectrum sensing results and the primary automatic repeat request feedback. The optimal medium access probabilities are obtained via maximizing the secondary throughput subject to constraints that guarantee quality of service parameters for the primary. Third, we propose a three-message superposition coding scheme to maximize the secondary throughput without degrading the primary rate. Cognitive relaying is employed as an incentive for the primary network. The scheme is shown to outperform a number of reference schemes such as best relay selection. Finally, we consider a network of multiple primary and secondary users. We propose a three-stage distributed matching algorithm to pair the network users. The algorithm is shown to perform close to an optimal central controller, albeit at a reduced computational complexity.