Mathias Johansson

PhD Thesis, Uppsala University, ISBN 91-506-1770-2 Sept. 2004, 221 pp.

Dissertation in Signal Processing to be publicly examined in room K23, Magistern, Dag Hammarskjölds väg 31, Uppsala on October 8, 2004 at 10.15 a.m.

Faculty Opponent: Professor Vikram Krishnamurthy, The University of British Columbia, Canada,

The thesis available in Pdf: 1474KB.

Paper copies of the thesis can be obtained from Ylva Johansson, Signals and Systems Group, Uppsala University, Box 534, SE-75121 Uppsala, Sweden.

See also the thesis homepage at the Uppsala University database for Ph.D. theses.

Outline:

In this thesis we consider a number of problems with the common feature that they all require decisions on how to allocate resources among different tasks under uncertainty concerning the demand and potentially also the supply of resources.

We first study a model problem from the manufacturing industry in which a plant manager has a number of production units which are used to produce different sorts of widgets. The manager's aim is to meet the order intake, but the task is complicated by uncertainty concerning the future order intakes as well as possibly uncertain production capacities. We then consider the customer perspective in an auctioning situation. With only limited information concerning other customers' bids, what amount should an individual customer bid? The answer obviously depends on what the expected benefit of the customer will be from winning, and we therefore investigate a few different scenarios.

Based on the general ideas that we formulate in connection to these two problems, we then consider a number of specific problems which are of current interest in digital mobile cellular communications. The objective is to increase the resource efficiency, or to maximize the useful work performed by the resources, over a given time horizon and thereby achieve a more cost-efficient cellular network.

Abstract:

This thesis is concerned with scheduling the use of resources, or allocating resources, so as to meet future demands for the entities produced by the resources. We consider applications in mobile communications such as scheduling users' transmissions so that the amount of transmitted information is maximized, and scenarios in the manufacturing industry where the task is to distribute work among production units so as to minimize the number of missed orders.

The allocation decisions are complicated by a lack of information concerning the future demand and possibly also about the capacities of the available resources. We therefore resort to using probability theory and the maximum entropy principle as a means for making rational decisions under uncertainty.

By using probabilities interpreted as a reasonable degree of belief, we find optimum decision rules for the manufacturing problem, bidding under uncertainty in a certain type of auctions, scheduling users in communications with uncertain channel qualities and uncertain arrival rates, quantization of channel information, partitioning bandwidth between interfering and non-interfering areas in cellular networks, hand-overs and admission control. Moreover, a new method for making optimum approximate Bayesian inference is introduced.

We further discuss reasonable optimization criteria for the mentioned applications, and provide an introduction to the topic of probability theory as an extension to two-valued logic. It is argued that this view unifies a wide range of resource-allocation problems, and we discuss various directions for further research.

Keywords:

Resource allocation, uncertainty, probability theory as logic, scheduling, mulytiuser diversity, Jaynes, maximum entropy, Bayesian probability theory.

Table of Contents:

1. Introduction
2. Probability Theory as Logic
3. Controlling Production Resources to Meet Customer Demands
4. Bidding under Uncertainty in a Certain Type of Auctions
5. Scheduling for Maximum Througput under Uncertainty
6. Implications of Limited Feedback for Scheduling and Adaptive Modulation - Througput, Sensitivity, Fairness and A Way Out
7. Inter-Cell Scheduling, Access Control and Hand-Overs
8. A New Method for Adaptive Approximation of Non-Stationary Posterior Distributions and Expectations.

Related publications:

IEEE Trans. VT 2008 on dynamic reuse partitioning within cells based on local channel and arrival rate fluctuations.
IEEE Trans. IT 2005 on Resource allocation under unceratinty using the Maximum Entropy principle.
IEEE SP Letters 2007 on Bayesian model selection for Markov, Hidden Markov, and Multinomial models.
MAXENT05 on approximate Bayesian inference by adaptive quantization of the hypothesis space.
SPAWC04 on Diversity-Enhanced Equal Access.
SPAWC03 on benefits of multiuser diversity with limited feedback.
RVK02 on multiuser diversity and maximum entropy scheduling.
Globecom01 on probabilistic resource allocation and scheduling.