Routing in Wireless Networks
Ponente(s): Jorge Urrutia Galicia
\documentclass[11pt]{article}
\usepackage{graphicx}
\usepackage{amssymb}
\usepackage{epstopdf}
\textwidth = 6.5 in
\textheight = 9 in
\oddsidemargin = 0.0 in
\evensidemargin = 0.0 in
\topmargin = 0.0 in
\headheight = 0.0 in
\headsep = 0.0 in
\parskip = 0.2in
\parindent = 0.0in
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{definition}{Definition}
\title{Routing in Wireless Networks}
\author{Jorge Urrutia\\
Instituto de Matem\'aticas, UNAM, M\'exico.}
\begin{document}
\maketitle
In this talk we will review some results on routing algorithms for wireless networks.
The nature of networks such as the Internet (which are highly dynamic, that is nodes
are constantly appearing and disappearing, and the amount of traffic they handle is
vary large and is increasing rapidly) dictate that current well known
routing schemes such as routing tables and broadcast be further optimized or
replaced altogether. We will review methods using Computational Geometry that
resulted in the development of a new breed of routing algorithms specifically targeted for
wireless networks, such as cellular networks, ad-hoc networks, sensor networks
and others.
The main ideas here involve the use of algorithms that take advantage
of the geographic positions of the nodes of a network
as well as properties of geometric graphs. The result
is a new class of \emph{local algorithms} for routing in wireless networks.
Loosely speaking, we could picture a traveler that has to go from a node
of a network located at a point $p$ on the plane to a node located at point $q$.
This traveler knows the
positions of $p$ and $q$, and at each node $w$ he visits, the location of $w$.
In addition, at $w$ the traveler has some \emph{local information} which tells him only about
the neighbors
of $w$. At no point in time does our traveler have any further information on the network.
Based solely on the positions of $p$, $q$ and the information available at $w$,
our traveler has to decide (in a deterministic manner) which node to visit next to reach his destination.
This process has to be repeated until our traveler (we hope) arrives at $q$.
To make things more interesting, the traveler is not allowed to leave markers along his
way, and has a poor memory (that is, a constant amount of memory). This means that if he
returns to a node already visited, chances are that he will not remember that he has already been there.
Can our traveler reach his destination?
Key words: Gabriel Graphs, Delaunay Triangulations, Cellular Networks, Spanners, Sensor Networks, Compass Routing, Face Routing, Greedy Routing.
Partially supported by PAPIIT IN102117 from UNAM
\end{document}