## 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

## 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.