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
| Identifer | oai:union.ndltd.org:UTEXAS/oai:repositories.lib.utexas.edu:2152/ETD-UT-2011-12-4478 |
| Date | 31 January 2012 |
| Creators | Gopalan, Aditya |
| Source Sets | University of Texas |
| Language | English |
| Detected Language | English |
| Type | thesis |
| Format | application/pdf |
Page generated in 0.0089 seconds