. 36
( 87 .)


which is mandatory, of the algorithm, the degree of each node is limited to seven by ap-
plying the Yao structure, and the master“slave relations are formed in created subgraphs.
Each node creates a key, which could be identity (ID), or degree, or the combination of
both, for comparison with its neighbors.
In each iteration, undecided nodes with higher keys than any of their undecided neigh-
bors (such nodes are referred as active nodes in the following) apply the Yao structure to
limit the degree. They [39] described in detail how to assign master“slave relations. The
active node then switches to a decided state. Assume that an active node u is a node that
applies the Yao construction. Then node u divides the region surrounding it into seven
equal angles centered at u, and chooses the closest node from each region, if there is any,
with ties broken arbitrarily. All remaining connections at u are simply deleted from the
graph. Notice that the elimination of any such edge uv by u immediately reduces the de-
gree of v, that is, node v has to remove link uv also. However, in order to avoid excessive
information exchange between neighbors, the originally decided keys (that is, original de-
grees) are used in all comparisons. We call the final structure as YHk(S).
This structure YHk(S) is different from all previous structures. First of all, YSk(S)
YHk(S) since any edge uv from YSk(S) will not be removed by either node u or node v in
the construction of YHk(S). It is not difficult to construct an example, for example, that in

Figure 6.3, such that YSk(S) YHk(S). The right two figures of Figure 6.3 also show that
YHk(S) is different from YYk(S).

6.2.3 Planar Spanner
The Gabriel graph was used as a planar subgraph in the Face routing protocol [16, 40, 41]
and the GPSR routing protocol [17]. The right-hand rule is used to guarantee the delivery
of the packet in [16]. The relative neighborhood graph RNG was used for efficient broad-
casting (minimizing the number of retransmissions) in the one-to-one broadcasting model
in [42]. Since RNG and GG have large stretch factors in the worst case, some other struc-
ture is needed if we want to bound the distance traveled from the source to the destination.
One of the known planar spanners is the Delaunay triangulation.
Assume that there are no four vertices of V that are cocircular. A triangulation of V is a
Delaunay triangulation, denoted by Del(V), if the circumcircle of each of its triangles
does not contain any other vertices of V in its interior. A triangle is called the Delaunay
triangle if its circumcircle is empty of vertices of V. The Voronoi region, denoted by
Vor(p), of a vertex p V, is a collection of two-dimensional points such that every point
is closer to p than to any other vertex of V. The Voronoi diagram for V is the union of all
Voronoi regions Vor(p), where p V. The Delaunay triangulation Del(V) is also the dual
of the Voronoi diagram: two vertices p and q are connected in Del(V) if and only if Vor(p)
and Vor(q) share a common boundary. The shared boundary of two Voronoi regions Vor(p)
and Vor(q) is on the perpendicular bisector line of segment pq. The boundary segment of a
Voronoi region is called the Voronoi edge. The intersection point of two Voronoi edges is
called the Voronoi vertex. The Voronoi vertex is the circumcenter of some Delaunay trian-
Given a set of nodes V, it is well known that the Delaunay triangulation Del(V) is a pla-
nar t-spanner of the completed graph K(V) [43“45]. However, it is not appropriate to re-
quire the construction of the Delaunay triangulation in the wireless communication envi-
ronment because of the possible massive communications it requires. Given a set of points
V, let UDel(V) be the graph formed by edges of Del(V) with length at most one unit, that
is, UDel(V) = Del(V) UDG(V). Li et al. [46] considered the unit Delaunay triangula-
tion UDel(V) for the planar spanner of UDG. Using the approach from [45], Li et al. [46]
proved that UDel(V) is a t-spanner of the unit disk graph UDG(V).

x x
u u
u v w


Figure 6.3. Left: The graph YHk(S) (represented by four solid lines) is different from YSk(S) (repre-
sented by three thick solid lines). Here the dashed lines define some cones around the nodes. Mid-
dle and Right: The graph YHk(S) is different from YYk(S). Here the node degrees are in decreasing
order as w, u, v, x, and y.
6.2 NETWORK TOPOLOGY CONTROL Localized Delaunay Triangulation. Li et al. [46] gave a localized algo-
rithm that constructs a sequence graphs, called a localized Delaunay graph LDel(1)(V),
which are supergraphs of UDel(V). We begin with some necessary definitions before pre-
senting the algorithm. Triangle uvw is called a k-localized Delaunay triangle if the inte-
rior of the circumcircle of uvw, denoted by disk(u, v, w) hereafter, does not contain any
vertex of V that is a k-neighbor of u, v, or w; and all edges of the triangle uvw have
length no more than one unit. The k-localized Delaunay graph over a vertex set V, denot-
ed by LDel(k)(V), has exactly all unit Gabriel edges and edges of all k-localized Delaunay
When it is clear from the context, we will omit the integer k in our notation of
LDel(k)(V). As shown in [46], the graph LDel(1)(V) may contain some edges intersecting,
although they showed that LDel(1)(V) can be decomposed to two planar graphs, that is, has
thickness 2. They proved that LDel(k)(S) is a planar graph for any k 2. Although the
graph UDel(V) is a t-spanner for UDG(V), it is unknown how to construct it locally. Li et
al. [46] present an efficient algorithm to extract a planar graph PLDel(V) out of
LDel(1)(V). They provide a novel algorithm to construct LDel(1)(V) using linear communi-
cations and then make it planar in linear communication cost. The final graph still con-
tains UDel(V) as a subgraph. Thus, it is a t-spanner of the unit-disk graph UDG(V).
The basic approach of their method is to let each node u compute the Delaunay trian-
gulation Del[N1(u)] of its 1-neighbors N1(u), including u itself. Node u then sends mes-
sages to its neighbors asking if the triangles in Del[N1(u)] can be accepted by LDel(1)(V).
Its neighbor v accepts the triangle if it is in Del[N1(v)]. The novel part is to bound the
communications by only letting u query for triangle vuw if vuw is at least /3. It was
proved that the graph constructed by the above algorithm is LDel(1)(V). As Del[N1(u)] is a
planar graph, and a proposal is made only if wuv /3, node u broadcasts at most six
proposals. And each proposal is replied to by at most two nodes. Therefore, the total com-
munication cost is O(n). They also gave an algorithm to extract from LDel(1)(V) a planar
subgraph, denoted by PLDel(V). They showed that PLDel(V) is a supergraph of
Recently, C“alinescu [47] proposed an efficient approach to collect N2(u) using total
O(n) communications based an efficient construction of the connected dominating set [7,
37]. Using the collected two-hop information, we then can construct the local Delaunay
triangulation LDel(2)(V), which is guaranteed to be a planar graph. The cost of updating
the structure LDel(2)(V) in a mobile environment could be more expensive than that of up-
dating the structure LDel(1)(V) from the definition of these two structures. It remains open
whether we can update these two structures using asymptotically same communication
costs. Restricted Delaunay Graph. Gao et al. [48] also proposed another struc-
ture, called a restricted Delaunay graph RDG, and showed that it has good spanning ratio
properties and is easy to maintain locally. A restricted Delaunay graph of a set of points in
the plane is a planar graph and contains all the Delaunay edges with length at most one. In
other other words, they call any planar graph containing UDel(V) a restricted Delaunay
graph. They described a distributed algorithm to maintain the RDG such that at the end of
the algorithm, each node u maintains a set of edges E(u) incident to u. Those edges E(u)
satisfy that (1) each edge in E(u) has length at most one unit; (2) the edges are consistent,
that is, an edge uv E(u) if and only if uv E(v); (3) the graph obtained is planar; and
(4) UDel(V) is in the union of all edges E(u).

The algorithm works as follows. First, each node u acquires the position of its one-hop
neighbors N1(u) and computes the Delaunay triangulation Del[N1(u)] on N1(u), including
u itself. In the second step, each node u sends Del[N1(u)] to all of its neighbors. Let E(u) =
{uv | uv Del[N1(u)]}. For each edge uv E(u), and for each w N1(u), if u and v are in
N1(w) and uv Del[N1(w)] then node u deletes edge uv from E(u).
They proved that when the above steps are finished, the resulting edges E(u) satisfy the
four properties listed above. However, unlike the local Delaunay triangulation, the compu-
tation cost and communication cost of each node needed to obtain E(u) is not optimal
within a small constant factor. The communication cost could be as large as (n2), and the
computation cost could be as large as (n3). Partial Delaunay Triangulation. Stojmenovic and Li [39] also proposed a
geometry structure, namely the partial Delaunay triangulation (PDT), that can be con-
structed in a localized manner. Partial Delaunay triangulation contains a Gabriel graph as
its subgraph, and itself is a subgraph of the Delaunay triangulation; more precisely, the
subgraph of the unit Delaunay triangulation UDel(V). The algorithm for the construction
of PDT goes as follows.
Let u and v be two neighboring nodes in the network. Edge uv belongs to Del(V) if and
only if there exists a disk with u and v on its boundary, which does not contain any other
point from the set V. First test whether disk(u, v) contains any other node from the net-
work. If it does not, the edge belongs to GG and therefore to PDT. If it does, check
whether nodes exist on both sides of line uv or on only one side. If both sides of line uv
contain nodes from the set inside disk(u, v) then uv does not belong to Del(V).
Suppose now that only one side of line uv contains nodes inside the circle disk(u, v), and
let w be one such point that maximizes the angle uwv. Let = uwv. Consider now the
largest angle uxv on the other side of the mentioned circle disk(u, v), where x is a node
from the set S. If uwv + uxv > , then edge uv is definitely not in the Delaunay triangu-
lation Del(V). The search can be restricted to common neighbors of u and v, if only one-hop
neighbor information is available, or to neighbors of only one of the nodes if two-hop in-
formation (or exchange of the information for the purpose of creating PDT is allowed) is
available. Then whether edge uv is added to PDT is based on the following procedure.
Assume that only N1(u) is known to u, and there is one node w from N1(u) that is inside
disk(u, v) with the largest angle uwv. Edge uv is added to PDT if the following condi-
tions hold: (1) there is no node from N1(u) that lies on the different side of uv with w and
inside the circumcircle passing through u, v, and w; (2) sin > d/R, where R is the trans-
mission radius of each wireless node, d is the diameter of the circumcircle disk(u, v, w),
and = uwv (here /2).
Assume only one-hop neighbors are known to u and v, and there is one node w from
N1(u) N1(v) that is inside disk(u, v) with the largest angle uwv (Figure 6.4). Edge uv is
added to PDT if the following conditions hold: (1) there is no node from N1(u) N1(v)
that lies on the different side of uv with w and inside the circumcircle passing u, v, and w;
(2) cos /2 > d/2R, where R is the transmission radius of each wireless node and =
Obviously, the partial Delaunay triangulation is a subgraph of UDel(V). The spanning
ratio of the partial Delaunay triangulation could be very large.
Hu [22] proposed a structure using the Delaunay triangulation to bound the node de-
gree of each wireless node to be at most . The centralized algorithm starts with the De-
launay triangulation Del(S) of the set of wireless nodes and then removes the edges in

w ± v
± v

Figure 6.4. Left: Only one-hop information is known to u. Then disk(u, v, w) must be covered by
the transmission range of u (denoted by the shaded region) and is empty of neighbors of u. Right:
Node u knows N1(u) and node v knows N1(v). The circumcircle disk(u, v, w) is covered by the union
of the transmission ranges of u and v and is empty of other vertices.

Del(S) that are longer than the transmission range (normalized to one unit here). Then it
processes the remaining edges in the order of the decreasing length and removes an edge
if it causes either end node to have degree larger than . Finally, it processes in the order
of increasing length all possible edges that are not in the graph, and adds an edge if it does
not cause a violation of the degree constraint. The worst time complexity of the above ap-
proach is O(n2 log n). In [22], a distributed implementation was also proposed. Unfortu-
nately, it is not correct since it requires each node u to find Delaunay edges uv with ||uv||
1. However, if we replace the computation of the Delaunay edges with length at most
one unit by the computation of the local Delaunay triangulation, the method still produce
a planar structure with bounded degree.
Recently, Li and Wang [49] proposed a novel localized method to construct a bounded-
degree planar spanner for wireless ad hoc networks using O(n) total communications.
Although all the structures discussed so far are flat structures, there are another set of
structures, called hierarchical structures, that are used in wireless networks. Instead of all
nodes being involved in relaying packets for other nodes, the hierarchical routing proto-
cols pick a subset of nodes that serve as the routers, forwarding packets for other nodes.
The structure used to build this virtual backbone is usually the connected dominating set.
See a recent survey [9] on methods of constructing connected dominating sets efficiently
in wireless ad hoc networks.
Figure 6.5 gives some concrete examples of the geometry structures introduced before.
Here we randomly generate 100 nodes in a 200 m by 200 m square. The transmission ra-
dius of each node is set as 50 m. Notice that the graph LDel shown in Figure 6.5 is not a
planar graph.

6.2.4 Transmission Power Control
In the previous sections, we have assumed that the transmission power of every node is
equal and is normalized to one unit. We relax this assumption for a moment in this sub-

Figure 6.5. Different topologies from UDG(V).

section. In other words, we assume that each node can adjust its transmission power ac-
cording to its neighbors™ positions for possible energy conservation. A natural question is
then how to assign the transmission power for each node such that the wireless network is
connected with optimization criteria being minimizing the maximum or total transmission
power assigned.
A transmission power assignment on the vertices in V is a function f from V into real
numbers. The communication graph, denoted by Gf, associated with a transmission pow-

er assignment f, is a directed graph with V as its vertices and has a directed edge vivj if
and only if ||vivj|| + c f(vi). We call a transmission power assignment f complete if the
communication graph Gf is strongly connected. Recall that a directed graph is strongly
connected if, for any given pair of ordered nodes s and t, there is a directed path from s
to t.
The maximum cost of a transmission power assignment f is defined as mc( f ) = maxvi V
f (vi). And the total cost of a transmission power assignment f is defined as sc( f ) = vi V
f (vi). The min“max assignment problem is then to find a complete transmission power as-
signment f whose cost mc( f ) is the least among all complete assignments. The min“total
assignment problem is to find a complete transmission power assignment f whose cost
sc( f ) is the least among all complete assignments.
Given a graph H, we say the power assignment f is induced by H if

f(v) = max ||vu|| + c
(v,u) E

where E is the set of edges of H. In other words, the power assigned to a node v is the
largest power needed to reach all neighbors of v in H.
Transmission power control has been well studied by peer researchers in the recent
years. Monks et al. [50] conducted simulations that show that implementing power control
in a multiple access environment can improve the throughput of the nonpower-controlled
IEEE 802.11 by a factor of 2. Therefore it provides a compelling reason for adopting the
power controlled MAC protocol in wireless networks.
The min“max assignment problem was studied by several researchers [26, 51]. Let


. 36
( 87 .)