Routing in Wireless Networks

Autor: 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}