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 / D-78465 Konstanz / Germany
Telefon: +49 (0) 7533
97227 Telefax: +49 (0) 7533 97228
http://www.hartung-gorre.de eMail: verlag@hartung-gorre.de