Hartung-Gorre Verlag
Inh.: Dr.
Renate Gorre D-78465
Konstanz Fon:
+49 (0)7533 97227 Fax: +49 (0)7533 97228 www.hartung-gorre.de
|
S
|
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
Series in Distributed Computing
Direkt bestellen
bei / to order directly from:
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