Series in Distributed Computing
edited by Roger Wattenhofer
Vol. 11

Roland Flury,

Routing on the Geometry of Wireless Ad Hoc Networks

1st edition/1. Aufl. 2009, X, 144 pages/Seiten, 64,00.
ISBN 3-86628-280-X and 978-3-86628-280-3

 

 


The routing of messages is one of the basic operations any computer network needs to provide. In this thesis, we consider wireless ad hoc and sensor networks and present several routing protocols that are tailored to the limited hardware capabilities of network participants such as sensor nodes. The constraint memory and computing power as well as the limited energy of such devices requires simplified routing protocols compared to the IP based routing of the Internet. The challenge is to build light routing protocols that still find good routing paths, such as to minimize not only the number of forwarding steps but also the energy consumption.

In the first part of this work we focus on the protocol design and analyze the properties of our routing algorithms under simplifying network models. In particular, we describe a location service that supports geographic routing even if the destination node is constantly moving. Such a location service is important as the geographic routing technique bases each routing step on the position of the destination node by repeatedly forwarding a message to the neighbor which is geographically closest to its destination. If there is no such neighbor, the message has reached a local minimum. This is a node at the boundary of a network hole around which the message needs to be led before it can continue its greedy path. We extend the classic notion of network holes to 3-dimensional unit ball graphs and propose several randomized recovery techniques to escape from local minima in such networks. In addition, we show that it is possible to forward messages greedily without ever falling in a local minimum. We do so by embedding the network into an higher-dimensional space such that there is a greedy path between any two nodes. Similarly, we describe a renaming technique in combination with small routing tables that ensures good routing paths not only for unicast, but also for anycast and multicast.

In the second part of this thesis, we examine the design of applications and come up with a programming technique to efficiently translate protocols to the limited hardware of sensor networks. We describe the slotted programming paradigm that fosters modular programming and decouples unrelated software components temporally. We demonstrate the advantages of our approach with two case studies: (1) an efficient clock synchronization module, and (2) an alarming module through which all nodes of a network can be awaken efficiently and reliably.

About the author:
Roand Flury received his M.Sc. degree in computer science from EPFL, the Swiss Federal Institute of Technology in Lausanne, Switzerland in 2005. In the same year, he joined the Distributed Computing Group of Professor Roger Wattenhofer at ETH Zurich as a Ph.D. student and research assistant. In 2009 he earned his Ph.D. degree for his work on routing on the geometry of wireless ad hoc networks.

 

Keywords: Routing, Wireless Ad Hoc Networks, Greedy Routing, Geographic Routing, Sensor Network

Direkt bestellen bei / to order directly from: Hartung.Gorre@t-online.de
Series in Distributed Computing in http://www.hartung-gorre.de

Direkt bestellen bei / to order directly from: Hartung.Gorre@t-online.de

Hartung-Gorre Verlag

Hartung-Gorre Verlag / D-78465 Konstanz / Germany

Telefon: +49 (0) 7533 97227 Telefax: +49 (0) 7533 97228
http://www.hartung-gorre.de eMail: verlag@hartung-gorre.de