EE 381K Advanced Telecommunication Networks - Fall 2007
Stochastic Geometry and Comparisons with Applications to Network Analysis
- Instructor: Gustavo de Veciana
- Class: M W 9:30-11 in ENS 116
- Office : ACES 3.120
- Office hours: MTW 11-12 and by appointment
- Email: gustavo@ece.utexas.edu, WWW: http://www.ece.utexas.edu/~gustavo
Description
This course introduces stochastic geometric tools and their applications
to modeling and analysis of spatial and mobile characteristics of communication
and sensor networks. We will exhibit powerfull techniques, based on
spatial point processes and induced geometric structures, e.g.,
tessellations, which can be used to model and study communication networks
and traffic. The course will begin by introducing
some of the tools of the trade, and then explain how they are used to study:
hierarchical optimization of traditional wireline networks;
coverage capacity tradeoffs and handoff traffic in cellular systems;
connectivity, capacity and energy burdens in random ad hoc networks.
If time permits we will also consider some tools used to study spatial-temporal
dynamics, and evaluate distributed algorithms for resource allocation.
I also intend to cover some topics in stochastic majorization, which I think will
be useful to you in your graduate studies.
This topic list is a bit ambitious, we will go at whatever pace is appropriate so
that the material covered in the class is of use to you, and try to be judicious
on where to spend time on technical details.
Course Contents
- Introduction: Geometric structures/hierarchies in communication networks. What is a point
process and a tesseslation?
- Review of selected foundations: Sets, topology and operations; Hitting probabilities and geometrical measures;
Measure and integration theory;
- Integral geometry primer: Linear Subspaces, Functionals of Convex Bodies
- Introduction to point processes: Bernoulli Point Processes; Stationary and Inhomogenous
Poisson Point Process; Constructing other processes (poissson process of disks, lines, Marked
Point processes ); Conditioning on a typical point, understanding what
are Palm distribution and Slivnyak's Theorem.
- General point processes: Campbell's Theorem, Marked Point Processes, Palm Distributions,
Mecke's Theorem, Slivnyak's Theorem.
- The Boolean model and shot noise processes: Poisson germ-grain models;
Capacity functional or hitting distribution.
- Tesselations: we formally define what is a tessellation/mosaic. Discuss some examples
thereof and then focus on the geometry of Voronoi and Delaunay tesselations.
- Stochastic Tesselations: we discuss stationary random tesselations focusing on
Voronoi and Delaunay. We prove some key relationships that follow from Palm probabilties
and Campbell's Theorem.
- Applications:
- Modeling and optimization of hierarchical telecommunication networks.
- Coverage and capacity tradeoffs and handoff traffic in cellular systems.
- Poisson clumping heuristic.
- Connectivity, routing, capacity and energy burdens in random ad hoc networks.
- Simulation techniques and challenges.
- Spatial dynamics and algorithm design.
- Stochastic Comparisons: we will introduce some of the basic tools in majorization
and stochastic comparisons and their uses an analysing smoothness of random variables, vectors
and comparing point processes. My goal is to introduce these ideas to a point where you will be able to know
when they are appropriate to use in your research
Course web page
Prerequisites
You will need to have had a Graduate Level course in Probability and Random Processes,
know a significant amount about Telecommunication and Wireless Network technology, and
to have taken a course; exposing you to the basics of Queueing theory
or Performance Evaluation. In addition some background
in Optimization would also be useful. This is an advanced course,
which for the most part should be taken by 2nd-3rd year graduate students in ECE, CS or
OR. Expect it to be quite challenging but hopefully rewarding too!
Some Texts and Selected Papers
My course notes/lectures will cover the (sometimes heavy) background required
to reach a point where you understand and can use these tools. This is a bit of a mix of
topics!
- Stochastic Geometry and its Applications, D. Stoyan, W. Kendall and J. Mecke, J. Wiley & Sons, 1995.
- Lectures on Random Voronoi Tessellations, J. Moeller, Springer-Verlag, 1994.
- Poisson Processes, J.F.C. Kingman, Clarendon Press - Oxford, 1993.
- Stochastic geometry and architecture of communication networks, F. Baccelli et. al, J. Telecom. Systems, No 7, pp 209-227, 1997.
- Comparison methods for stochastic models and risks, A. Muller and D. Stoyan, Wiley 2002.
- Probability Approximations via the Poisson Clumping Heuristic , David Aldous, Springer Verlag, 1989
- A collection of papers related to recent applications will be available on the course web site
Format/Evaluation
You will be responsible for all material presented in class and strongly encouraged
to participate in class discussions. There will be some homework, and I will
give you a few quizzes to check you are learning/digesting what we have discussed
in class.
You will be required to do a small project for the class. I will provide general problem
areas and support papers to help you get started. You can work in teams of no more than two.
You will be required to make two presentations.
The first presentation, will be a problem/research statement plus an overview
of the state of the art on your topic.
The final presentation
a follow on explaining what results
you were able to obtain. All students will be expected to present.
The final presentations will be part of a class "mini-symposium" that will take
place at the end of the term. We will
run it like a formal conference, with strict time deadlines, and invite faculty
and students to attend.
Your grade will be based 30% on two quizzes, 20% homework and class participation,
and 50% on your presentations and project.
Where does course fit in?
This course is intended to build on your own background and interests as well as
material in Probability and Random Processes,
Communication Networks: Analysis and Design, Information Theory and Optimization.
Note: All departmental, college and university regulations
concerning drops will be followed. The University of Texas at Austin provides
upon request appropriate academic accommodations for qualified students
with disabilities. For more information, contact the Office of the Dean
of Students at 471-6259, 471-4641 TTY.