Asymptotically optimal geometric mobile ad-hoc routing.
In this paper we present AFR, a new geometric mobile ad-hoc routing algorithm. The algorithm is completely distributed; nodes need to communicate only with direct neighbors in their transmission range. We show that if a best route has cost c, AFR finds a route and terminates with cost &Ogr;(c2) in the worst case. AFR is the first algorithm with cost bounded by a function of the optimal route. We also give a tight lower bound by showing that any geometric routing algorithm has worst-case cost $Ogr;(c2). Thus AFR is asymptotically optimal. We give a non-geometric algorithm that also matches the lower bound, but needs some memory at each node. This establishes an intriguing trade-off between geometry and memory.
INTRODUCTION
A mobile ad-hoc network consists of mobile nodes equipped
with a wireless radio. We think of mobile nodes as points in
the Euclidean plane. Two nodes can directly communicate
with each other if and only if they are within transmission
range of each other. Throughout this paper we assume that
all nodes have the same transmission range R 1 . Two nodes
with distance greater than R can communicate by relaying
their messages through a series of intermediate nodes; this
process is called multi-hop routing.
In this paper we study so-called geometric routing; in
networks that support geometric routing a) each node is
equipped with a location service, i.e. each node knows its
Euclidean coordinates, b) each node knows all the neighbor
nodes (nodes within transmission range R) and their coordi-
nates, and c) the sender of a message knows the coordinates
of the destination.
In addition to the standard assumptions a), b) and c), we
take for granted that mobile nodes are not arbitrarily close
to each other, i.e. d) there is a positive constant d0 such that
the distance between any pair of nodes is at least d0 . This
is motivated by the fact that there are physical limitations
on how close to each other two mobile nodes can be placed.
Further, distances between neighboring nodes in an ad-hoc
network will typically be in the order of the transmission
range. 2
In this paper we present a new geometric routing algorithm
which borrows from the eminent Face Routing algorithm
by Kranakis, Singh, and Urrutia [14]. As it is the
tradition in the community, we give our algorithm a name:
AFR which stands for Adaptive Face Routing 3 . Our algorithm
is completely local; nodes only exchange messages
with their direct neighbors, i.e. nodes in their transmission
range R. We show that if a best route has cost c, our algorithm
finds a route and terminates with cost O(c 2 ) in the
worst case. This bound holds for many prominent cost models
such as distance, energy, or the link metric. Note that
the distance of the best route (the sum of the distances of
the single hops) can be arbitrarily larger than the Euclidean
distance of source and destination. Our algorithm is the
first algorithm that is bounded by a function of the optimal
route; the original Face Routing algorithm and all other geo-
1 In the technical part of the paper we simplify the presentation
by scaling the coordinates of the system such that
Meanwhile, we have achieved similar results without assumption
d) in [15].
3 Is it a coincidence that AFR also reflects our first names?
metric routing algorithms are only bounded by a function
of the number of nodes.
Moreover we show that any geometric routing algorithm
has
This tight lower bound proves that our algorithm
is asymptotically optimal 4 . The lower bound also
holds for randomized algorithms. Apart from the theoretical
relevance of our results, we feel that our algorithm has
practical potential, especially as a fall-back mechanism for
greedy geometric routing algorithms (which are e#cient in
an average case).
It is surprising that the cost of geometric routing algorithms
is quadratic in the cost of the best route. We show
that this bound can also be achieved by a simple non-geometric
routing algorithm. In exchange for the missing location
service we give the algorithm some extra memory at each
node. We show that this algorithm also has cost O(c 2 ),
which, contrary to intuition, proves that in the worst case a
GPS is about as useful as some extra bits of memory.
The paper is organized as follows. In the next section we
discuss the related work. In Section 3 we formally model
mobile ad-hoc networks and geometric routing algorithms.
In Section 4 we present and analyze our geometric routing
algorithm AFR. We give a matching lower bound in Section
5. Section 6 concludes and discusses the paper.
2. RELATED WORK
Traditionally, multi-hop routing for mobile ad-hoc networks
can be classified into proactive and reactive algo-
rithms. Proactive routing algorithms copycat the behavior
of wireline routing algorithms: Each node in the mobile
ad-hoc network maintains a routing table that lays down
how to forward a message. Mobile nodes locally change the
topology of the network, which in turn provokes updates
to the routing tables throughout the network. Proactive
routing algorithms are e#cient only if the ratio of mobility
over communication is low. If the nodes in the network
are reasonably mobile, the overhead of control messages to
update the routing tables becomes unacceptably high. Also
storing large routing tables at cheap mobile nodes might be
prohibitively expensive. Reactive routing algorithms on the
other hand find routes on demand only. The advantage is
that there is no fixed cost for bureaucracy. However, whenever
a node needs to send a message to another node, the
sender needs to flood the network in order to find the receiver
and a route to it. Although there are a myriad of
(often obvious and sometimes helpful) optimization tricks,
the flooding process can still use up a significant amount of
scarce wireless bandwidth. Reviews of routing algorithms in
mobile ad-hoc networks in general can be found in [4] and
[21].
Over a decade ago researchers started to advocate equipping
every node with a location information system [7, 11,
23]; each node knows its geometric coordinates [10]. If the
(approximate) coordinates of the destination are known too,
a message can simply be sent/forwarded to the "best" di-
rection. This approach is called directional, geometric, ge-
ographic, location-, or position-based routing. With the
growing availability of global positioning systems (GPS or
Galileo), it can easily be imagined to have a corresponding
4 The constant between the lower and the upper bound depends
on the cost model, but can generally become quite
large.
receiver at each node [12]. Even if this is not the case, one
can conceive that nodes calculate their position with a local
scheme; a research area that has recently been well studied
[22]. Geometric routing only works if nodes know the
location of the destination. Clearly, the (approximate) location
of the destination changes much less frequently than
the structure of the underlying graph. In this sense it is
certainly less expensive to keep the approximate locations
of the destinations than the whole graph. In the area of
peer-to-peer networking a lot of data structures have been
presented that store this type of information in an e#cient
way. It would be possible to use an overlay peer-to-peer net-work
to maintain the position of all destinations [16]. Last
but not least one could imagine that we want to send a message
to any node in a given area, a routing concept that is
known as geocasting [13, 19]. Overviews of geometric routing
algorithms are given in [9, 18, 20].
s

Figure

1: Greedy routing fails with nodes distributed
on the letter "C".
The first geometric routing algorithms were purely greedy:
The message is always forwarded to the neighboring node
that is closest to the destination [7, 11, 23]. It was shown
that even simple location configurations do not guarantee
that a message will reach its destination when forwarded
greedily. For example, we are given a network with nodes
that are distributed "on" the letter "C" (see figure 1). Assume
that the northernmost node s of "C" wants to send a
message to destination t (the southeastern tip of "C"). With
greedy routing the message is forwarded from the source to
the best neighbor, i.e. in the southeastern direction. At node
(the north eastern tip of "C") there is no neighbor node
closer to the destination, and the routing algorithm fails.
To circumvent the gap of the "C", the source should have
sent the message to the west. It has been shown that many
other definitions of "best" neighbor (e.g. best angle a.k.a.
Compass Routing in [14]) do not guarantee delivery either.
The first geometric routing algorithm that guarantees delivery
is the Face Routing algorithm, proposed in a seminal
paper by Kranakis, Singh, and Urrutia [14] (in their short
paper they call the algorithm Compass Routing II ). The
Face Routing algorithm is a building block of our routing
algorithm AFR and will therefore be discussed in more detail
later. The Face Routing algorithm guarantees that the
message will arrive at the destination and terminates in O(n)
steps, where n is the number of nodes in the network. This
is not satisfactory, since already a very simple flooding algorithm
will terminate in O(n) steps. In case the source and
the destination are close, we would like to have an algorithm
that terminates earlier. In particular, we are interested in
the competitive ratio of the route found by the algorithm
over the best possible route.
There have been other suggestions for geometric routing
algorithms with guaranteed delivery [3, 5], but in the
worst case (to the best of our knowledge) none of them
is better than the original Face Routing algorithm. Other
(partly non-deterministic) greedy routing algorithms have
been shown to find the destination on special planar graphs,
such as triangulations or convex subdivisions [2], without
any performance guarantees.
It has been shown that the shortest path between two
nodes on a Delaunay triangulation is only a small constant
factor longer than their distance [6]. It has even been shown
that indeed there is a competitive routing algorithm for Delaunay
triangulations [1]. However, nodes can only communicate
within transmission range R: Delaunay triangulation
is not applicable since edges can be arbitrarily long in Delaunay
triangulations. Accordingly, there have been attempts
to approximate the Delaunay triangulation locally [17] but
no better bound on the performance of routing algorithms
can be given for such a construction.
A more detailed discussion of geometric routing can be
found in [25].
3. MODEL
This section introduces the notation and the model we use
throughout the paper. We consider routing algorithms on
Euclidean graphs, i.e. weighted graphs where edge weights
represent Euclidean distances between the adjacent nodes
in a particular embedding in the plane. As usual, a graph
G is defined as a pair G := (V, E) where V denotes the set
of nodes and denotes the set of edges. The number
of nodes is called | and the Euclidean length of an
denoted by cd (e). A path p := v1 , . , vk for
is a list of nodes such that two consecutive nodes
are adjacent in G, i.e. (v i , that edges can
be traversed multiple times when walking along p. Where
convenient, we also denote a path p by the corresponding
list of edges.
As mentioned in the introduction, we consider the standard
model for ad-hoc networks where all nodes have the
same limited transmission ranges. This leads to the definition
of the unit disk graph (UDG).
Definition 1. (Unit Disk Graph) Let V # R 2 be a set
of points in the 2-dimensional plane. The Euclidean graph
with edges between all nodes with distance at most 1 is
called the unit disk graph.
We also make the natural assumption that the distance between
nodes is limited from below.
Definition
2.(# (1)-model) If the distance between any
two nodes is bounded from below by a term of order #der i.e.
there is a positive constant d0 such that d0 is a lower bound
on the distance between any two nodes, this is referred to
as
del.
This paper mainly focuses on geometric ad-hoc routing algorithms
which can be defined as follows.
Definition 3.
(Geometric Ad-Hoc Routing Algorithm)
E) be a Euclidean graph. The aim of a geometric
ad-hoc routing algorithm A is to transmit a message
from a source s # V to a destination t # V by sending packets
over the edges of G while complying with the following
conditions:
. Initially all nodes v # V know their geometric positions
as well as the geometric positions of all of their
neighbors in G.
. The source s knows the position of the destination t.
. The nodes are not allowed to store anything except for
temporarily storing packets before transmitting them.
. The additional information which can be stored in
a packet is limited by O(log n) bits, i.e. information
about O(1) nodes is allowed.
In the literature geometric ad-hoc routing has been given
various other names, such as O(1)-memory routing algorithm
in [1, 2], local routing algorithm in [14] or position-based
routing. Due to the storage restrictions, geometric
ad-hoc routing algorithms are inherently local.
For our analysis we are interested in three di#erent cost
models: the link distance metric (the number of hops), the
Euclidean distance metric (the total traversed Euclidean dis-
tance) and the energy metric (the total energy used). Each
cost model implies an edge weight function. As already de-
fined, the Euclidean length of an edge is denoted by cd (e). In
the link distance metric all edges have weight 1
and the energy weight of an edge is defined as the square of
the Euclidean length (cE (e) := cd 2 (e)). The cost of a path
defined as the sum of the costs of its edges:
c# (p) :=
The cost c# (A) of an algorithm A is defined analogously
as the sum over the costs of all edges which are traversed
during the execution of an algorithm on a particular graph
G 5 .
Lemma 3.1. In the #e -model, the Euclidean distance,
the link distance, and the energy metrics of a path
e1 , . , ek are equal up to a constant factor on the unit disk
graph 6 .
Proof. The cost of p in the link distance metric is c #
k. We have that d0 # cd
fore, the Euclidean distance and the energy costs of p are
upper-bounded by k and lower-bounded by cd (p) # d0k and
4. AFR: ADAPTIVE FACE ROUTING
In this section, we describe our algorithm AFR which is
asymptotically optimal for unit disk graphs in
model. Our algorithm is an extension of the Face Routing
algorithm introduced by Kranakis et al. [14] (in the original
paper the algorithm is called Compass Routing II ).
5 For the energy metric it is usually assumed that a node
can send a message simultaneously to di#erent neighbors
using only the energy corresponding to the farthest of those
neighbors. We neglect this because it does not change our
results.
6 More generally, all metrics whose edge weight functions are
polynomial in the Euclidean distance weight are equal up to
a constant factor on the unit disk graph in
the#e504 del.
This formulation would include hybrid models as well as
energy metrics with exponents other than 2.
Figure

2: The faces of a planar graph (the white
region is the infinite outer face).
Face Routing and AFR work on planar graphs. We use
the term planar graph for a specific embedding of a planar
graph, i.e. we consider Euclidean planar graphs. In this
case, the nodes and edges of a planar graph G partition the
Euclidean plane into contiguous regions called the f faces of
G (see

Figure

2 as an illustration). Note that we get f - 1
finite faces in the interior of G and one infinite face around
G.
The main idea of the Face Routing algorithm is to walk
along the faces which are intersected by the line segment st
between the source s and the destination t. For completeness
we describe the algorithm in detail (see Figure 3).
s

Figure

3: The Face Routing algorithm
Face Routing
0. Start at s and let F be the face which is incident to s
and which is intersected by st in the immediate region
of s.
1. Explore the boundary of F by traversing its edges and
remember the intersection point p of st with the edges
of F which is nearest to t. After traversing all edges, go
back to p. If we reach t while traversing the boundary
of F , we are done.
2. p divides st into two line segments where pt is the not
yet "traversed" part of st. Update F to be the face
which is incident to p and which is intersected by the
line segment pt in the immediate region of p. Go back
to step 1.
In order to simplify the subsequent proofs, we show that
Face Routing terminates in linear time.
Lemma 4.1. The Face Routing algorithm reaches the destination
after traversing at most O(n) edges where n is the
number of nodes.
Proof. First we show that the algorithm terminates. By
the choices of the faces F in step 0 and 2, respectively, we
see that in step 1 we always find a point p which is nearer
to t than the previous p where we start the tour around
F . Therefore we are coming nearer to t with each iteration,
and since there are only finitely many intersections between
st and the edges of G, we reach t in a finite number of
iterations.
For the performance analysis, we see that by choosing p as
the st-"face boundary" intersection which is nearest to t, we
will never traverse the same face twice. Now, we partition
the edges E into two subsets E1 and E2 where E1 are the
edges which are incident to only one face (the same face lies
on both sides of the edge) and E2 are the edges which are
incident to two faces (the edge lies between two di#erent
faces). During the exploration of a face F in step 2, an
edge of E2 is traversed at most twice and an edge of E1 is
traversed at most four times. Since the edges of E1 appear
in only one face and the edges of E2 appear in two faces, all
edges of E are traversed at most four times during the whole
algorithm. Each face in a planar connected graph (with at
least 4 nodes) has at least three edges on its boundary. This
together with the Euler polyhedral formula (n -m+
yields that the number of edges m is bounded by m # 3n-6
which proves the lemma.
In order to obtain our new algorithm AFR, we are now going
to change Face Routing in two steps. In a first step we
assume that an upper-bound b
cd on the (Euclidean) length
cd (p # ) of a shortest route p # from s to t on graph G is
known to s at the beginning. We present a geometric ad-hoc
routing algorithm which reaches t with link distance cost
at most O( b
Bounded Face Routing (BFR[c cd ]). Let E be the ellipse
which is defined by the locus of all points the sum of whose
distances from s and t is b
cd , i.e. E is an ellipse with foci s
and t. By the definition of E , the shortest path (in R 2 ) from
s to t via a point q outside E is longer than b
cd . Therefore,
the best path from s to t on G is completely inside or on E .
We change step 1 of Face Routing such that we always stay
0. Start at s and let F be the face which is incident to s
and which is intersected by st in the immediate region
of s.

Figure

4: Bounded Face Routing (no success: b
cd is
chosen too small)

Figure

5: Successful Bounded Face Routing
1. As before, we explore the face F and remember the
best intersection between st and the edges of F in p.
We start the exploration of F as in Face Routing by
starting to walk into one of the two possible directions.
We continue until we come around the whole face F
as in the normal Face Routing algorithm or until we
would cross the boundary of E . In the latter case, we
turn around and walk back until we get to the boundary
of E again. In any case we are then going back
to p. If the exploration of F does not yield a better
has the same value as in the previous itera-
tion, Bounded Face Routing does not find a route to t
and we restart BFR to find a route back from p to the
source s. Otherwise, proceed with step 2.
2. p divides st into two line segments where pt is the not
yet "traversed" part of st. Update F to be the face
which is incident to p and which is intersected by the
line segment pt in the immediate region of p. Go back
to step 1.

Figure

4 shows an example where b
cd is chosen too small,

Figure

5 shows a successful execution of the Bounded Face
Routing algorithm.
Lemma 4.2. If the length of an optimal path p # (w.r.t. the
Euclidean distance metric) between s and t in graph G in
the #e -model is upper-bounded by a constant b
Bounded Face Routing finds a path from s to t. If Bounded
Face Routing does not succeed in finding a route to t, it
does succeed in returning to s. In any case, Bounded Face
Routing terminates with link distance cost at most O( b
c d
Proof. We show that whenever there is a path from s to
t which is completely inside or on E , Bounded Face Routing
finds a route from s to t by traversing at most O( b
The lemma then follows.
F
r
q'
A
p'

Figure

If there is a path from s to t inside E, BFR
succeeds in routing from s to t (E is not drawn on
the picture).
Suppose that there is a path r from s to t where r lies
inside or on E . First we show that in this case BFR finds
a route from s to t. Consider a point p on st from which
we start to traverse a face F . We have to show that we find
a point p # on st which is nearer to t than p while exploring
face F . Assume that F does not completely lie inside the
ellipse E since otherwise we find p # as in the normal Face
Routing algorithm. Let q be the last intersection between
path r and st before p and let q # be the first intersection
between r and st after p (see Figure 6 as an illustration).
The part of the path r which is between q and q # and the
line segment qq # together define a polygon. We denote the
area which is covered by this polygon by A. To traverse
the boundary of F we can leave p in two possible directions
where one of them points into A. During the traversal we
will in any case take both directions. While walking along
the boundary of F , we cannot cross the path r because the
edges of r are part of the planar graph of which F is a face.
In order to leave A, we therefore have to cross st at a point
must be nearer to t than p because otherwise the
boundary of F would cross itself.
As a second step we show that each edge inside E is traversed
at most four times during the execution of the BFR
algorithm. In order to prove this, we consider the graph G #
which is defined as follows. Prune everything of G which is
outside the ellipse E . At the intersections between edges of
G and E , we introduce new nodes and we take the segments
of E between those new nodes as additional "edges" 7 . As
an illustration, all edges of G # are drawn with thick lines in

Figure

5. Now consider step 1 of BFR as exploring a face F
of G # instead of exploring a face of G. Let p be the intersection
between F and st where we start the traversal of F and
let p # be the st-"face boundary"-intersection which is closest
to t. If there is a path from s to t inside E , there must also
be a path between p and p # which is inside E . Assume that
this is not the case. The part of the boundary of F which
includes p and the part of the boundary of F which includes
would then only be connected by the additional edges on
E in G # . Thus, F would then separate E into two parts, one
of which containing s, the other one containing t. Therefore
step 1 of our algorithm BFR yields p # as a new point on
st, i.e. BFR is in a sense equivalent to Face Routing on G # .
Hence, in an execution of BFR each face of G # is visited at
most once. During the exploration of a face F in step 1 of
BFR each edge is traversed at most twice, no matter if we
walk around F as in the normal Face Routing algorithm or
if we hit E and have to turn around (the edges whose sides
belong to the same face can again be traversed four times).
Therefore, we conclude that each edge inside E is traversed
at most four times.
As a last step, we have to prove that there are only O( b
edges of G inside E . Since G is a planar graph, we know
that the number of edges is linear in the number of nodes
as shown in the proof of Lemma 4.1). We conside

del where the Euclidean distance between
any pair of nodes is at least d0 . Thus, the circles of radius
d0/2 around all nodes do not intersect each other. Since the
length of the semimajor axis a of the ellipse E is b
c d /2, and
since the area of E is smaller than #a 2 , the number of nodes
bounded by
d 2+ O(a) # O b
We have now proven that if there is a path from s to t
after traversing at
7 We do not consider that those additional edges are no
straight lines. By adding some additional new nodes on E
and connecting all new nodes by straight line segments, we
could also construct G # to be a real Euclidean planar graph.
most O( b
edges. The only thing which remains open in
order to conclude the proof of Lemma 4.2 is that an unsuccessful
execution of BFR also terminates after traversing at
most O( b
k, be the faces which
are visited during the execution of the algorithm. Fk is the
face where we do not find a better point on st, i.e. Fk is
the face which divides E into two parts. From the above
analysis it is clear that the first k - 1 faces are only visited
once. Fk is explored at most twice, once to find the best accessible
intersection with st and once to see that no further
improvement can be made. Hence, all edges are traversed at
most eight times until we arrive at the point p on st where
we have to turn around 8 . For our way back we know that
there is a path from p to s which lies inside E and therefore
we arrive at s after visiting every edge at most another four
times.
We are now coming to the definition of AFR. The problem
with Bounded Face Routing is that usually no upper-bound
on the length of the best route is known. In AFR we apply
a standard trick to get around this.
AFR Adaptive Face Routing. We begin by determining
an estimate e
cd for the unknown value cd (p # ), e.g. e
cd := 2st.
The algorithm then runs Bounded Face Routing with exponentially
growing e
cd until eventually the destination t is
reached:
1. Execute BFR[ e
cd ].
2. If the BFR execution of step 1 succeeded, we are done;
otherwise, we double the estimate for the length of the
shortest path ( e
cd ) and go back to step 1.
Lemma 4.3. Let p # be a shortest path from node s to node
t on the planar graph G. Adaptive Face Routing finds a path
from s to t while traversing at most O(c 2
edges.
Proof. We denote the first estimate e
cd on the optimal
path length by ec d,0 and the consecutive estimates by ec d,i :=
Furthermore, we define k such that ec d,k-1 < cd (p #
ec d,k . For the cost of BFR[ e
cd ] we have c # (BFR[ e
cd
and therefore
cd
for a constant # (and su#ciently large e
cd ). The total cost
of algorithm AFR can therefore be bounded by
d,0
For the remainder of this section we show how to apply AFR
to the unit disk graph. We need a planar subgraph of the
unit disk graph, since AFR requires a planar graph. There
8 It is possible to explore face Fk only once as well but for
our asymptotic analysis, we ignore this optimization.
are various suggestions on how to construct a planar sub-graph
of the unit disk graph in a distributed way. Often
the intersection between the UDG and the Relative Neighborhood
Graph (RNG [24]) or the Gabriel Graph (GG [8]),
respectively, have been proposed. In the RNG an edge between
nodes u and v is present i# no other node w is closer
to u and to v than u is to v. In the Gabriel Graph an edge
between u and v is present i# no other node w is inside or
on the circle with diameter uv. The Relative Neighborhood
Graph and the Gabriel Graph are easily constructed in a distributed
manner. There have been other suggestions, such
as the intersection between the Delaunay triangulation and
the unit disk graph [17]. All mentioned graphs are connected
provided that the unit disk graph is connected as well. We
use the Gabriel Graph, since it meets all requirements as
shown in the following lemma.
Lemma 4.4. In the #e -model the shortest path for any
of the considered metrics (Euclidean distance, link distance,
and energy) on the Gabriel Graph intersected with the unit
disk graph is only by a constant longer than the shortest path
on the unit disk graph for the respective metric.
e"
e

Figure

7: The unit disk graph contains an energy
optimal path.
Proof. We show that at least one best path with respect
to the energy metric on the UDG is also contained in GG#
UDG. Suppose that is an edge of an energy
optimal path p on the UDG. For the sake of contradiction
suppose that e is not contained in GG # UDG. Then there
is a node w in or on the circle with diameter uv (see Figure
7). The edges e are also edges of
the UDG and because w is in the described circle, we have
e #2 +e #2 # e 2 . If w is inside the circle with diameter uv, the
energy for the path p # := p \ {e} # {e # , e # } is smaller than
the energy for p and p no energy-optimal path. If w is on
the above circle, p # is an energy-optimal path as well and
the argument applies recursively. Using Lemma 3.1, we see
that the optimal path costs with respect to the Euclidean
and the link distance metrics are only by a constant factor
greater than the energy cost of p. This concludes the proof.
Lemma 4.4 directly leads to Theorem 4.5.
Theorem 4.5. Let p # for # {d, #, E} be an optimal path
with respect to the corresponding metric on the unit disk
graph in
the#1 -model. We have
when applying AFR on GG # UDG in the #e -model.
Proof. The theorem directly follows from Lemma 3.1,
Lemma 4.3, and Lemma 4.4.
5. LOWER BOUND
In this section we give a constructive lower bound for geometric
ad-hoc routing algorithms.

Figure

8: Lower bound graph
Theorem 5.1. Let the cost of a best route for a given
source destination pair be c. Then any deterministic (ran-
domized) geometric ad-hoc routing algorithm has (expected)
link, distance, or energy cost.
Proof. We construct a family of networks as follows. We
are given a positive integer k and define a Euclidean graph
G (see

Figure

On a circle we evenly distribute 2k nodes
such that the distance between two neighboring points is exactly
thus, the circle has radius r # k/#. For every second
node of the circle we construct a chain of #r/2# - 1 nodes.
The nodes of such a chain are arranged on a line pointing
towards the center of the circle; the distance between two
neighboring nodes of a chain is exactly 1. Node w is one
arbitrary circle node with a chain: The chain of w consists
of #r# nodes with distance 1. The last node of the chain of
w is the center node; note that the edge to the center node
does not need to have distance 1.
Please note that the unit disk graph consists of the edges
on the circle and the edges on the chains only. In particular,
there is no edge between two chains because all chains except
the w chain end strictly outside radius r/2. Note that the
graph has k chains with #(k) nodes each.
We route from an arbitrary node on the circle (the source
s) to the center of the circle (the destination t). An optimal
route between s and t follows the shortest path on the circle
until it hits node w, and then directly follows w's chain to
t with link cost c # k routing
algorithm with routing tables at each node will find this best
route.
A geometric ad-hoc routing algorithm needs to find the
"correct" chain w. Since there is no routing information
stored at the nodes, this can only be done by exploring the
chains. Any deterministic algorithm needs to explore the
chains in a deterministic order until it finds the chain w.
Thus, an adversary can always place w such that w's chain
will be explored as the last one. The algorithm will therefore
explore #(k 2 ) (instead of only O(k)) nodes.
The argument is similar for randomized algorithms. By
placing w accordingly (randomly!), an adversary forces the
randomized algorithm to
explore# chains before chain
w with constant factor probability. Then the expected link
cost of the algorithm is # k 2 ).
Because all edges (but one) in our construction have length
1, the costs in the Euclidean distance, the link distance, and
the energy metrics are equal. Thus,
holds for all three metrics.
Note that our lower bound does hold generally, not only
for
#6479-461 However, if the graph is not
there might be a higher (worse) lower bound.
To conclude this section, we present the main theorem of
this paper stating that AFR is asymptotically optimal for
unit disk graphs in
del.
Theorem 5.2. Let c be the cost of an optimal path for
a given source destination pair on a unit disk graph in the
#he -model. In the worst case the cost for applying AFR
to find a route from the source to the destination is #(c 2 ).
This is asymptotically optimal.
Proof. Theorem 5.2 is an immediate consequence of Theorem
4.5 and of Theorem 5.1.
6. CONCLUSION
In this paper we proved a lower bound for geometric ad-hoc
routing algorithms on the unit disk graph. Specifically,
we showed that in the worst case the cost of any geometric
ad-hoc routing algorithm is quadratic in the cost of an optimal
path. This result holds for the Euclidean distance, the
link distance, and the energy metric. Furthermore, we gave
an algorithm (AFR) which matches this lower bound and is
therefore optimal.
It is interesting to see that if we allow the nodes to store
O(log n) bits, we can achieve the same results even if the
source does not know anything about the coordinates of
the destination. The lower bound still holds and the upper
bound can be achieved by a simple flooding algorithm.
The source floods the network (we again take GG # UDG)
with an initial time to live ttl 0 , i.e. all nodes up to depth
ttl 0 are reached. The result of the flood (destination reached
or not reached) is then echoed back to the source along the
same paths in the reverse direction. We iterate the process
with exponentially growing time to live until we reach the
destination. All nodes which are reached by flooding with
TTL ttl are in a circle with radius ttl around the source.
In this circle there are O(ttl 2 ) nodes and hence also O(ttl 2 )
edges each of which is traversed at most 4 times (including
the echo process). Therefore, the cost of iteration i (with
and the cost of the whole algorithm is
quadratic in the cost of the best path for any of the three
considered metrics. We find it intriguing that a few storage
bits in each node appear to be as good as the geometric
information about the destination.
7.



--R

Online routing in triangulations.
Online routing in convex subdivisions.
Routing with guaranteed delivery in ad hoc wireless networks.
A performance comparison of multi-hop wireless ad hoc network routing protocols
Internal node and shortcut based routing with guaranteed delivery in wireless networks.
Delaunay graphs are almost as good as complete graphs.
Routing and addressing problems in large metropolitan-scale internetworks
A new statistical approach to geographic variation analysis.
Position based routing algorithms for ad hoc networks: a taxonomy
Location systems for ubiquitous computing.
Transmission range control in multihop packet radio networks.

Geocasting in mobile ad hoc networks: Location-based multicast algorithms
Compass routing on geometric networks.
Geometric ad-hoc routing for unit disk graphs and general cost models
A scalable location service for geographic ad-hoc routing
Distributed construction of planar spanner and routing for ad hoc wireless networks.
A survey on position-based routing in mobile ad-hoc networks

A survey of routing techniques for mobile communications networks.
A review of current routing protocols for ad-hoc mobile wireless networks
Dynamic fine-grained localization in ad-hoc networks of sensors
Optimal transmission ranges for randomly distributed packet radio terminals.
The relative neighborhood graph of a finite planar set.
Routing with guaranteed delivery in geometric and wireless networks.
--TR
Delaunay graphs are almost as good as complete graphs
GeoCastMYAMPERSANDmdash;geographic addressing and routing
A survey of routing techniques for mobile communications networks
A performance comparison of multi-hop wireless ad hoc network routing protocols
Routing with guaranteed delivery in <italic>ad hoc</italic> wireless networks
A scalable location service for geographic ad hoc routing
Dynamic fine-grained localization in Ad-Hoc networks of sensors
Routing with guaranteed delivery in geometric and wireless networks
Location Systems for Ubiquitous Computing
Online Routing in Triangulations
Online Routing in Convex Subdivisions
Internal Node and Shortcut Based Routing with Guaranteed Delivery in Wireless Networks
Location-Aided Routing (LAR) in Mobile Ad Hoc Networks

--CTR
Qing Fang , Jie Gao , Leonidas J. Guibas, Locating and bypassing holes in sensor networks, Mobile Networks and Applications, v.11 n.2, p.187-200, April 2006
Stefan Funke, Topological hole detection in wireless sensor networks and its applications, Proceedings of the 2005 joint workshop on Foundations of mobile computing, September 02-02, 2005, Cologne, Germany
Roland Flury , Roger Wattenhofer, MLS:: an efficient location service for mobile ad hoc networks, Proceedings of the seventh ACM international symposium on Mobile ad hoc networking and computing, May 22-25, 2006, Florence, Italy
Jongkeun Na , Chong-kwon Kim, GLR: a novel geographic routing scheme for large wireless ad hoc networks, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.50 n.17, p.3434-3448, 5 December 2006
Wen-Zhan Song , Yu Wang , Xiang-Yang Li , Ophir Frieder, Localized algorithms for energy efficient topology in wireless ad hoc networks, Proceedings of the 5th ACM international symposium on Mobile ad hoc networking and computing, May 24-26, 2004, Roppongi Hills, Tokyo, Japan
Minimizing recovery state In geographic ad-hoc routing, Proceedings of the seventh ACM international symposium on Mobile ad hoc networking and computing, May 22-25, 2006, Florence, Italy
Wen-Zhan Song , Yu Wang , Xiang-Yang Li , Ophir Frieder, Localized algorithms for energy efficient topology in wireless ad hoc networks, Mobile Networks and Applications, v.10 n.6, p.911-923, December 2005
Young-Jin Kim , Ramesh Govindan , Brad Karp , Scott Shenker, On the pitfalls of geographic face routing, Proceedings of the 2005 joint workshop on Foundations of mobile computing, September 02-02, 2005, Cologne, Germany
Ittai Abraham , Dahlia Malkhi, Compact routing on euclidian metrics, Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing, July 25-28, 2004, St. John's, Newfoundland, Canada
Wang , Xiang-Yang Li, Localized construction of bounded degree and planar spanner for wireless ad hoc networks, Proceedings of the joint workshop on Foundations of mobile computing, p.59-68, September 19, 2003, San Diego, CA, USA
Vishakha Gupta , Gaurav Mathur , Anil M. Shende, Wireless ad hoc lattice computers (WAdL), Journal of Parallel and Distributed Computing, v.66 n.4, p.531-541, April 2006
Fabian Kuhn , Roger Wattenhofer , Aaron Zollinger, Worst-Case optimal and average-case efficient geometric ad-hoc routing, Proceedings of the 4th ACM international symposium on Mobile ad hoc networking & computing, June 01-03, 2003, Annapolis, Maryland, USA
Wang , Xiang-Yang Li, Localized construction of bounded degree and planar spanner for wireless ad hoc networks, Mobile Networks and Applications, v.11 n.2, p.161-175, April 2006
Leszek Gsieniec , Chang Su , Prudence W. H. Wong , Qin Xin, Routing of single-source and multiple-source queries in static sensor networks, Journal of Discrete Algorithms, v.5 n.1, p.1-11, March, 2007
Fabian Kuhn , Roger Wattenhofer , Yan Zhang , Aaron Zollinger, Geometric ad-hoc routing: of theory and practice, Proceedings of the twenty-second annual symposium on Principles of distributed computing, p.63-72, July 13-16, 2003, Boston, Massachusetts
Ittai Abraham , Danny Dolev , Dahlia Malkhi, LLS: a locality aware location service for mobile ad hoc networks, Proceedings of the 2004 joint workshop on Foundations of mobile computing, October 01-01, 2004, Philadelphia, PA, USA
Fabian Kuhn , Aaron Zollinger, Ad-hoc networks beyond unit disk graphs, Proceedings of the joint workshop on Foundations of mobile computing, p.69-78, September 19, 2003, San Diego, CA, USA
Bharat Bhargava , Xiaoxin Wu , Yi Lu , Weichao Wang, Integrating heterogeneous wireless technologies: a cellular aided mobile Ad Hoc network (CAMA), Mobile Networks and Applications, v.9 n.4, p.393-408, August 2004
Radha Poovendran , Loukas Lazos, A graph theoretic framework for preventing the wormhole attack in wireless ad hoc networks, Wireless Networks, v.13 n.1, p.27-59, January 2007
Xiang-Yang Li , Wen-Zhan Song , Weizhao Wang, A unified energy-efficient topology for unicast and broadcast, Proceedings of the 11th annual international conference on Mobile computing and networking, August 28-September 02, 2005, Cologne, Germany
Gady Kozma , Zvi Lotker , Micha Sharir , Gideon Stupp, Geometrically aware communication in random wireless networks, Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing, July 25-28, 2004, St. John's, Newfoundland, Canada
Fabian Kuhn , Roger Wattenhofer , Aaron Zollinger, An algorithmic approach to geographic routing in ad hoc and sensor networks, IEEE/ACM Transactions on Networking (TON), v.16 n.1, p.51-62, February 2008
routing;geometric routing;face routing;wireless communication;unit disk graphs;ad-hoc networks