. 37
( 87 .)


EMST(V) be the Euclidean minimum spanning tree over a point set V. Both [26] and [51]
use the power assignment induced by EMST(V). It was proved in [26] that the longest
edge of the Euclidean minimum spanning tree EMST(V) is always the critical link for
min“max assignment. Here, for an optimum transmission power assignment fopt, call a
link uv the critical link if ||uv|| + c = mc( fopt). Both algorithms presented in [26] and [51]
compute the minimum spanning tree from the fully connected graph with possible very
large communication cost. Notice that the best distributed algorithm [52“54] can compute
the minimum spanning tree in O(n) rounds using O(m + n log n) communications for a
general graph with m edges and n nodes. Using the fact that the relative neighborhood
graph, the Gabriel graph, and the Yao graph all have O(n) edges and contain the Euclidean
minimum spanning tree, a simple O(n log n) time-complexity centralized algorithm can
be developed and can be implemented efficiently in a distributed manner.
The min“total assignment problem was studied by Kiroustis et al. [55] and by Clemen-
ti et al. [56“58]. Kiroustis et al. [55] first proved that the min“total assignment problem is
NP-hard when the mobile nodes are deployed in a three-dimensional space. A simple two-
approximation algorithm based on the Euclidean minimum spanning tree was also given
in [55]. The algorithm guarantees the same approximation ratio in any dimensions.

Clementi et al. [56“58] proved that the min“total assignment problem is still NP-hard
when nodes are deployed in a two-dimensional space.
So far, we have generated asymmetric communication graphs from the power assign-
ment. For the symmetric communication, several methods also guarantee a good perfor-
mance. It is easy to show that the minimum spanning tree method still gives the optimum
solution for the min“max assignment and a two-approximation for the min“total assign-
ment. Recently, Calinescu et al. [59] gave a method that achieves a better approximation
ratio (5/3) by using ian dea from the minimum Steiner tree. Like the minimum spanning
tree method, it works for any power definition.


The geometric nature of the multihop ad hoc wireless networks allows a promising idea:
localized routing protocols. A routing protocol is localized if the decision to which node
to forward a packet is based only on:

The information in the header of the packet. This information includes the source
and the destination of the packet, but more data could be included, provided that its
total length is bounded.
The local information gathered by the node from a small neighborhood. This infor-
mation includes the set of one-hop neighbors of the node, but a larger neighborhood
set could be used provided it could be collected efficiently.

Randomization is also used in designing the protocols. A routing is said to be memory-
less if the decision as to which node to forward a packet is solely based on the destination,
current node, and its neighbors within some constant hops. Localized routing is some-
times called in the literature stateless [17], online [60, 61], or distributed [62].

6.3.1 Location Service
In order to make the localized routing work, the source node has to learn the current (or
approximately current) location of the destination node. Notice that for sensor networks
collecting data, the destination node is often fixed; thus, location service is not needed in
these applications. However, the help of a location service is needed in most application
scenarios. Mobile nodes register their locations to the location service. When a source
node does not know the position of the destination node, it queries the location service to
get that information. In cellular networks, there are dedicated position severs. It will be
difficult to implement the centralized approach of location services in wireless ad-hoc
networks. First, for centralized approach, each node has to know the position of the node
that provides the location services, which is a chicken-and-egg problem. Second, the dy-
namic nature of the wireless ad hoc networks makes it very unlikely that there is at least
one location server available for each node. Thus, we will concentrate on distributed loca-
tion services.
For the wireless ad hoc networks, the location service provided can be classified into
four categorizes: some-for-all, some-for-some, all-for-some, and all-for-all. Some-for-all
service means that some wireless nodes provide location services for all wireless nodes.
Other categorizations are defined similarly.

An example of all-for-all services is the location services provided in the Distance
Routing Effect Algorithm for Mobility (DREAM) by Basagni et al. [63]. Each node stores
a database of the position information for all other nodes in the wireless networks. Each
node will regularly flood packets containing its position to all other nodes. A frequency of
the flooding and the range of the flooding is used as a control of the cost of updating and
the accuracy of the database.
Using the idea of quorum developed in the databases and distributed systems, Hass and
Liang [64] and Stojmenovic [65] developed quorum-based location services for wireless
ad hoc networks. Given a set of wireless nodes V, a quorum system is a set of subset (Q1,
Q2, · · · , Qk) of nodes whose union is V. These subsets could be mutually disjoint or often
have equal numbers of intersections. When one of the nodes requires the information of
the other, it suffices to query one node (called the representative node of Qi) from each
quorum Qi. A virtual backbone is often constructed between the representative nodes us-
ing a nonposition-based methods such as those in [7, 6]. The updating information of a
node v is sent to the representative node (or the nearest if there are many) of the quorum
containing v. The difficulty of using quorums is that the mobility of the nodes requires the
frequent updating of the quorums. The quorum-based location service is often of the
some-for-some type.
The other promising location service is based on the quadtree partition of the two-di-
mensional space [66]. It divides the region containing the wireless network into a hier-
archy of squares. The partition of the space in [66] is uniform. However, we notice that
the partition could be nonuniform if the density of the wireless nodes were not uniform
for some applications. Each node v will have the position information of all nodes with-
in the same smallest square containing v. This position information of v is also propa-
gated to up-layer squares by storing it in the node with the nearest identity to v in each
up-layer square containing v. Using the nearest identity over the smallest identity can
avoid the overload of some nodes. The query is conducted accordingly. It is easy to
show that it takes about O(log n) time to update the location of v and to query another
node™s position information.

6.3.2 Localized Routing Protocols
We summarize some localized routing protocols proposed in the networking and compu-
tational geometry literature (see Figure 6.6).
The following routing algorithms on the graphs were proposed recently.

Compass Routing. Let t be the destination node. Current node u finds the next relay
node v such that the angle vut is the smallest among all neighbors of u in a given
topology. See [67].
Random Compass Routing. Let u be the current node and t be the destination node.
Let v1 be the node on the above of line ut such that v1ut is the smallest among all
such neighbors of u. Similarly, we define v2 to be nodes below line ut that mini-
mizes the angle v2ut. Then node u randomly chooses v1 or v2 to forward the pack-
et. See [67].
Greedy Routing. Let t be the destination node. Current node u finds the next relay
node v such that the distance ||vt|| is the smallest among all neighbors of u in a given
topology. See [16].

v v1
t t t
u u u


v v
t t t
± ±
u u u

Figure 6.6. Various localized routing methods. Shaded area is empty and v is next node.

Most Forwarding Routing (MFR). Current node u finds the next relay node v such
that ||v t|| is the smallest among all neighbors of u in a given topology, where v is
the projection of v on segment ut. See [62].
Nearest Neighbor Routing (NN). Given a parameter angle , node u finds the nearest
node v as forwarding node among all neighbors of u in a given topology such that
vut .
Farthest Neighbor Routing (FN). Given a parameter angle , node u finds the far-
thest node v as forwarding node among all neighbors of u in a given topology such
that vut .
Greedy“Compass. Current node u first finds the neighbors v1 and v2 such that v1
forms the smallest counterclockwise angle tuv1 and v2 forms the smallest clock-
wise angle tuv2 among all neighbors of u with the segment ut. The packet is for-
warded to the node of {v1, v2} with minimum distance to t. See [61, 68]

Notice that it is shown in [16, 67] that compass routing, random compass routing, and
greedy routing guarantee to deliver the packets from the source to the destination if De-
launay triangulation is used as the network topology. They proved this by showing that the
distance from the selected forwarding node v to the destination node t is less than the dis-
tance from current node u to t. However, the same proof cannot be carried over when the
network topology is Yao graph, Gabriel graph, relative neighborhood graph, and localized
Delaunay triangulation. When the underlying network topology is a planar graph, the
right-hand rule is often used to guarantee the packet delivery after simple localized rout-
ing heuristics fail [16, 62, 17].
It was proved in [68] that greedy routing guarantees the delivery of the packets if the
Delaunay triangulation is used as the underlying structure. Compass routing guarantees
the delivery of the packets if the regular triangulation is used as the underlying structure.
There are triangulations (not Delaunay) that defeat these two schemes. Greedy“compass

routing guarantees the delivery of the packets as long as there is a triangulation used as
the underlying structure. Every oblivious routing method is defeated by some convex sub-
Localized routing protocols support mobility by eliminating the communication-inten-
sive task of updating the routing tables. But mobility can affect the localized routing pro-
tocols, in both the performance and the guarantee of delivery. There has been no work so
far to design protocols with guaranteed delivery when the network topology changes dur-
ing the routing.

6.3.3 Quality Guaranteed Protocols
With respect to localized routing, there are several ways to measure the quality of the pro-
tocol. Given the scarcity of the power resources in wireless networks, minimizing the total
power used is imperative. A stronger condition is to minimize the total Euclidean distance
traversed by the packet. Morin et al. [61, 68] also studied the performance ratio of previ-
ously studied localized routing methods. They proved that none of the previous proposed
heuristics guarantees a constant ratio of the traveled distance of a packet compared with
the minimum. They gave the first localized routing algorithm such that the traveled dis-
tance of a packet from u to v is at most a constant factor of ||uv|| when the Delaunay trian-
gulation is used as the underlying structure.
Bose and Morin [68] basically use the binary search method to find which path of the
tunnel connecting the source u and the destination v is better. However, their algorithm
(called DTR hereafter) needs the Delaunay triangulation, which is expensive to construct
in wireless ad hoc networks, as the underlying structure. In [69], they further extend their
method to any triangulations satisfying the diamond property. Let G(V, rn) be the graph
defined over V, which has an edge uv iff ||uv|| rn. Li et al. [70] showed that the sum of
all edges in Del(V) is no more than rn with high probability, where rn is the transmission
radius needed by each node so the induced unit disk graph G(V, rn) is connected with high
To make G(V, rn) connect with probability 1 “ (1/n), we need n rn 2 ln n, see [71].
They [70] showed that, with probability at least 1 “ (1/ ), the longest edge Dn of Delaunay
triangulation is Dn 3(ln n + ln + ln 3)/(n ). Thus, the required transmission range
so that local Delaunay triangulation PLDel equals the Delaunay triangulation Del is just
3/2 of the minimum transmission range to have a connected network with high proba-
bility. This implies that the localized Delaunay triangulation can be used to approximate
the Delaunay triangulation almost always when the network G(V, rn) is connected and
when V is randomly deployed. Consequently, the method by Bose et al. [68] can be used
on local Delaunay triangulation almost always.
Table 6.1 illustrates the delivery rates. For routing methods NN and FN, we choose the
next node within /3 of the destination direction. Interestingly, we found that when the
Yao graph is used, the delivery rates are high in all methods. The reason these methods de-
livered the packets when the Yao structure is used could be that there is a node within the
transmission range in the direction of the destination with high probability when N1(u) is
large enough. Table 6.2 illustrates the maximum spanning ratios of the path traversed by
the packet from source s to destination t to ||st||. Although the maximum spanning ratio by
DTR is larger than most previous methods, DTR is the only known method guaranteeing a
constant spanning ratio.

Table 6.1. The Delivery Rate
Yao RNG GG Del PLDel
NN 100 20.4 83.3 100 100 98.4
FN 94.5 25.8 70.2 94.6 100 95.2
MFR 98.6 54.5 90 97.4 95 97.2
Cmp 97.1 23.2 66.2 100 100 100
RCmp 95.4 51.4 66.2 85.7 86.9 89.9
Grdy 100 78.3 100 100 100 100
GCmp 95 26.5 76.6 100 98.4 100
DTR 100 100 100

Table 6.2. The Maximum Spanning Ratio
Yao RNG GG Del PLDel
NN 1.7 1.3 1.6 1.5 1.6 1.6
FN 3.3 1.6 1.8 1.9 2.3 2.4
MFR 4.7 1.7 2.3 1.8 1.8 3.1
Cmp 11 2.2 6.2 16 18 18
RCmp 27 20 19 31 27 21
Grdy 1.7 2.0 1.8 1.6 1.5 1.6
GCmp 2.5 1.6 2.7 1.9 1.9 1.9
DTR 8.6 8.6 8.4


One of the remaining fundamental and critical issues is to have multiple disjoint paths
connecting every pair of nodes without sacrificing the spectrum-reusing property. As
power is a scarce resource in wireless networks, it is important to save the power con-
sumption without losing the network connectivity. The universal minimum power used by
all wireless nodes such that the induced network topology is connected is called the criti-
cal power. Although determining the critical power for static wireless ad hoc networks has
been well studied [26, 51, 72], it remains to study the critical power for connectivity for
mobile wireless networks. As the wireless nodes move around, it is impossible to have a
unanimous critical power to guarantee the connectivity for all instances of the network
configuration. Thus, we need to find a critical power, if possible, at which each node has
to transmit to guarantee the connectivity of the network almost surely, i.e., with high prob-
ability of almost one.


. 37
( 87 .)