Revenue Maximization in Resource Allocation:
Applications in Wireless
Nilo Casimiro Ericsson
PhD Thesis, Uppsala University,
Sept. 2004, 214 pp.
Dissertation in Signal Processing to be publicly examined
in room K23, Magistern, Dag Hammarskjölds väg 31,
Uppsala on October 22, 2004 at 10.15 a.m.
Professor Jens Zander, KTH, Stockholm.
The thesis available in
Paper copies of the thesis can be obtained from
Signals and Systems Group, Uppsala University,
Box 534, SE-75121 Uppsala, Sweden.
This material is presented to ensure timely dissemination
of scholarly and technical work. Copyright and all rights
therein are retained by authors.
All persons copying this information are expected to
adhere to the terms and constraints invoked by each authors
copyright. This work may not be reposted
without the explicit permission of the copyright holders.
We consider the problem of distributing a limited
amount of shared resources among a number of clients,
in a fashion that optimizes a revenue-based criterion.
More specifically, we consider the problem of service
resource scheduling to a population of clients with
different and time-varying service requirements
and also different and time-varying resource
utilization per service unit. Furthermore, the
clients generate different revenue for the owner
of the server. The question we try to answer is:
How do we decide who should use the shared resource when?
This problem is found in wireless mobile communications,
where different mobile hosts are travelling at
different speeds and directions, and at different
distances to a radio signal transmitting base station.
The mobile hosts therefore experience different and
varying signal qualities, affecting the capacity
of the resource they utilize for transmission of
information. Since different users may run
different applications on the mobile hosts, they
also have varying service demands.
Revenue maximization for network operators is considered
as a criterion for resource allocation in
wireless cellular networks.
A business model encompassing service level
agreements between network operators and
service providers is presented. Admission control,
through price model aware admission policing
and service level control, is critical for the provisioning
of useful services over a general purpose wireless network.
A technical solution consisting of a fast resource
scheduler taking into account service requirements
and wireless channel properties, a service level
controller that provides the scheduler with a
reasonable load, and an admission policy to uphold
the service level agreements and maximize
revenue, is presented.
Two different types of
service level controllers are presented and
implemented. One is based on a scalar PID controller,
that adjusts the admitted data rates for all
active clients. The other one is obtained with
linear programming methods, that optimally
assign data rates to clients, given their
channel qualities and price models.
scheduling criteria, and algorithms based on
them, are presented and evaluated in a simulated
wireless environment. One is based on a quadratic
criterion, and is implemented through
approximative algorithms, encompassing a
search based algorithm and two diffterent
linearizations of the criterion. The second
one is based on statistical measures of the
service rates and channel states, and is
implemented as an approximation of the joint
probability of achieving the delay limits while
utilizing the available resources effently.
Two scheduling algorithms, one based on each criterion,
are tested in combination with each of the
service level controllers, and evaluated in terms
of throughput, delay, and computational
complexity, using a target test system.
Results show that both schedulers can, when feasible,
meet explicit throughput and delay requirements,
while at the same time allowing the service level
controller to maximize revenue by allocating
the surplus resources to less demanding services.
Wireless resource, scheduling, admission control,
service level control, service level agreement.
Table of Contents:
- Revenue -the Criterion
- Admission Control
- Scheduling Algorithms
- Power-n Scheduling Criteria
- Probability based Scheduling Criteria
- Case Study
- Conclusions and Future Work.
by Nilo Casimiro Ericsson, June 2001.
Future Telecom Conf. Dec. 2001
on Scheduling and adaptive transmission for the downlink
in 4G Systems.
on Hybrid type-II ARQ/AMS supported by channel predictive
scheduling in a multi-user scenario.
on adaptive modulation and scheduling.