. 35
( 87 .)


of neighbors. The primary goal of topology control in wireless networks is to maintain
network connectivity, optimize network lifetime and throughput, and make it possible to
design power-efficient routing. Not every connected subgraph of the unit disk graph plays
the same important role in network design. One of the perceptible requirements of topolo-
gy control is to construct a subgraph such that the shortest path connecting any two nodes
in the subgraph is not much longer than the shortest path connecting them in the original
unit disk graph. This aspect of path quality is captured by the stretch factor of the sub-
graph. A subgraph with constant stretch factor is often called a spanner, and a spanner is
called a sparse spanner if it has only a linear number of links. In this chapter we review
and study how to construct a sparse network topology efficiently for a set of static wire-
less nodes.
Restricting the size of the network has been found to be extremely important in reduc-
ing the amount of routing information. The notion of establishing a subset of nodes that
perform the routing has been proposed in many routing algorithms [2“5]. These methods
often construct a virtual backbone by using the connected dominating set [6“8], which is
often constructed from a dominating set or a maximal independent set. For a full review
of the state of the art in constructing the backbone, see Li [9].
The other imperative requirement for network topology control in wireless ad hoc net-
works is the fault tolerance. To guarantee a good fault tolerance, the underlying network
structure must be k-connected for some k > 1, i.e., given any pair of wireless nodes, there
need to be at least k disjoint paths to connect them. By setting the transmission range suf-
ficiently large, the induced unit disk graph will be k-connected without doubt. Since ener-
gy conservation is important to increase the life of the wireless device, the question is how

to find the minimum transmission range such that the induced unit disk graph is multiply
Many routing algorithms [3, 5, 11“14] have been proposed recently for wireless ad hoc
networks. The routing protocols proposed may be categorized as table-driven protocols or
demand-driven protocols. A good survey may be found in [15]. Route discovery can be
very expensive, thus reducing the response time of the network. On the other hand, explic-
it route maintenance can be even more costly in the explicit communication of substantial
routing information and the usage of scarce memory of wireless network nodes. The geo-
metric nature of the multihop ad-hoc wireless networks allows a promising solution: lo-
calized routing protocols.
Localized routing does not require the nodes to maintain routing tables, a distinct ad-
vantage given the scarce storage resources and the relatively low computational power
available to the wireless nodes. More importantly, given the numerous changes in topolo-
gy expected in ad-hoc networks, no recomputation of the routing tables is needed and,
therefore, we expect a significant reduction in overhead. Thus, localized routing is scal-
able. Localized routing is also uniform, in the sense that all the nodes execute the same
protocol when deciding to which other node to forward a packet.
But localized routing is challenging to design, as even guaranteeing the successful ar-
rival at the destination of the packet is a nontrivial task. This task was successfully solved
by Bose et al. [16] (see also [17]). Mauve et al. [18] conducted an excellent survey of po-
sition-based localized routing protocols.

6.1.1 Organization
The rest of the chapter is organized as follows. In Section 6.2, we review in detail the
geometry structures that are suitable for topology control in wireless ad hoc networks, es-
pecially the structures with bounded stretch factors, bounded node degree, or planar struc-
tures. We also review the current status of controlling the transmission power so the total
or maximum transmission power is minimized without sacrificing the network connectiv-
ity. After reviewing the geometric structures, we review the so-called localized routing
methods in Section 6.3. Location service protocols are also discussed. In Section 6.4, we
review the current status of applying stochastic geometry to study the connectivity, capac-
ity, and so on of wireless networks. We conclude in Section 6.5 by pointing out some pos-
sible research questions.


We consider a wireless ad hoc network consisting of a set V of n wireless nodes distrib-
uted in a two-dimensional plane. By a proper scaling, we assume that all nodes have the
maximum transmission range equal to one unit. These wireless nodes define a unit disk
graph UDG(V) in which there is an edge between two nodes if and only if their Euclidean
distance is at most one. In this chapter, we concentrate on how to apply some structural
properties of a point set for wireless networks as we treat wireless devices as two-dimen-
sional points.
Due to the limited resources of the wireless nodes, it is preferred that the underlying
network topology be constructed in a localized manner. Stojmenovic et al. first defined
what a localized algorithm is in [16, 19]. Here, a distributed algorithm constructing a

graph G is a localized algorithm if every node u can exactly decide all edges incident on u
based only on the information of all nodes within a constant number of hops of u (plus a
constant number of additional nodes™ information if necessary).
Energy conservation is a critical issue in ad hoc wireless network for the node and net-
work life, as the nodes are powered by batteries only. In the most common power-attenua-
tion model, the power, denoted by p(e), needed to support a link e = uv is ||uv|| , where ||uv||
is the Euclidean distance between u and v, and is a real constant between 2 and 5, de-
pending on the wireless transmission environment. This power consumption is typically
called path loss. Practically, there is some other overhead cost for each device to receive and
then process the signal. For simplicity, this overhead cost can be integrated into one cost c,
which is almost the same for all nodes. Without specification, it is assumed that c = 0.
Let G = (V, E) be a n-vertex connected weighted graph over V. The distance in G be-
tween two vertices u, v V is the total weight of the shortest path between u and v and is
denoted by dG(u, v). A subgraph H = (V, E ), where E E, is a t-spanner of G if for
every u, v V, dH(u, v) t · dG(u, v). The value of t is called the stretch factor. If the
weight is the length of the link, then t is called the length stretch factor; if the weight is the
power to support the communication of the link, then t is called the power stretch factor.
Recently, topology control for wireless ad hoc networks has attracted considerable at-
tention [20“28]. Rajaraman [29] conducted an excellent survey recently.

6.2.1 Known Structures
Several geometrical structures have been studied recently both by computational geome-
try scientists and network engineers. Here we review the definitions of some of them that
could be used in wireless networking applications.
Let V be the set of wireless nodes in a two dimensional plane. The relative neighbor-
hood graph, denoted by RNG(V), is a geometric concept proposed by Toussaint [30]. It
consists of all edges uv such that there is no point w V with uw and wv satisfying ||uw||
< ||uv|| and ||wv|| < ||uv||. Let disk(u, v) be the disk with diameter uv. Then, the Gabriel
graph [31] GG(V) contains an edge uv from G if and only if disk(u, v) contains no other
vertex w V inside. It is easy to show that RNG(V) is a subgraph of the Gabriel graph
GG(V). For the unit disk graph, the relative neighborhood graph and the Gabriel graph
only contain the edges in UDG satisfying the respective definitions.
The relative neighborhood graph has length stretch factor as large as n “ 1 [32]. Li et
al. [33] showed that its power stretch factor could also be as large as n “ 1. The Gabriel
graph has length stretch factor between n/2 and 4 2n “ 4/3 [32]. Li et al. [33]
showed that the power stretch factor of any Gabriel graph is exactly one when the over-
head cost c = 0.
The Yao graph with an integer parameter k 6, denoted by YGk(V), is defined as fol-
lows. At each node u, any k equally separated rays originated at u define k cones. In each
cone, choose the shortest edge uv, if there is any, and add a directed link uv . Ties are bro-
ken arbitrarily or by the smallest ID. The resulting directed graph is called the Yao graph.
See Figure 6.1 for an illustration. Let YGk(V) be the undirected graph by ignoring the di-
rection of each link in YGk(V). If we add the link vu instead of the link uv , the graph is de-
noted by YGk(V), which is called the reverse of the Yao graph. Some researchers used a
similar construction called a -graph [34]. The difference is that, in each cone, it chooses
the edge that has the shortest projection on the axis of the cone instead of the shortest
edge. Here, the axis of a cone is the angular bisector of the cone. For more detail, please

u v
u v u


Figure 6.1. The definitions of RNG, GG, and Yao on point set. Left: The lune using uv is empty for
RNG. Middle: The diametric circle using uv is empty for GG. Right: The shortest edge in each cone
is added as a neighbor of u for Yao.

refer to [34]. Recently, the Yao structure has been rediscovered by several researchers for
use in topology control in wireless ad hoc networks of directional antennas.
The Yao graph YGk(V) has length stretch factor 1/(1 “ 2 sin /k). Li et al. [33] proved
that the power stretch factor of the Yao graph YGk(V) is at most 1/[1 “ (2 sin /k) ].
Li et al. [35] extended the definitions of these structures on top of any given graph G.
They proposed to apply the Yao structure on top of the Gabriel graph structure [the result-

ing graph is denoted by YGGk(V)], and apply the Gabriel graph structure on top of the Yao

structure [the resulting graph is denoted by GYGk(V)]. These structures are sparser than
the Yao structure and the Gabriel graph and they still have a constant bounded-power
stretch factor. These two structures are connected graphs. Wattenhofer et al. [28] also pro-
posed a two-phased approach that consists of a variation of the Yao graph followed by a
variation of the Gabriel graph. Unfortunately, there are some bugs in their proofs, which
were discussed in detail in [33].
Li et al. [23] proposed a structure that is similar to the Yao structure for topology con-
trol. Each node u finds a power pu, such that in every cone of degree surrounding u,
there is some node that u can reach with power pu, . Here, nevertheless, we assume that
there is a node reachable from u by the maximum power in that cone. Notice that the num-
ber of cones to be considered in the traditional Yao structure is a constant k. However, un-
like the Yao structure, for each node u, the number of cones needed to be considered in the
method proposed in [23] is about 2n, where each node v could contribute two cones on
both sides of segment uv. Then the graph G contains all edges uv such that u can com-
municate with v using power pu, . They proved that, if 5 /6 and the UDG is connect-
ed, then graph G is a connected graph. On the other hand, if > 5 /6, they showed that
the connectivity of G is not guaranteed by giving some counterexample [23]. Unlike the
Yao structure, the final topology G is not necessarily a bounded degree graph.

6.2.2 Bounded Node Degree
“ “
Notice that although the directed graphs YGk(V), GYGk(V), and YGGk(V) have a bounded
power-stretch factor and a bounded out-degree k for each node, some nodes may have a
very large in-degree. The node configuration given in Figure 6.2 will result a very large in-
degree for node u. The bounded out-degree gives us advantages when applied to several
routing algorithms. However, an unbounded in-degree at node u will often cause large over-



u ±
± v1


Figure 6.2. Node u has degree (or in-degree) n “ 1.

head at u. Therefore, it is often imperative to construct a sparse network topology such that
both the in-degree and the out-degree are bounded by a constant so as to be power-efficient.

Sink Structure. Arya et al. [36] gave an ingenious technique to generate a bounded de-
gree graph with constant length-stretch factor. In [33], Li et al. applied the same technique
to construct a sparse network topology with a bounded degree and a bounded power-
stretch factor from YG(V). The technique is to replace the directed star consisting of all
links toward a node u by a directed tree T(u) of a bounded degree with u as the sink. Tree
T(u) is constructed recursively. The algorithm is as follows.

Algorithm: Constructing-T(u) Tree[u, I(u)]
1. Choose k equal-sized cones C1(u), C2(u), · · · , Ck(u), centered at u.
2. Node u finds the nearest node yi I(u) in Ci(u), for 1 i k, if there is any. Link yiu
is added to T(u) and yi is removed from I(u). For each cone Ci(u), if I(u) Ci(u) is not
empty, call Tree[yi, I(u) Ci(u)] and add the created edges to T(u).

The union of all trees T(u) is called the sink structure YG *(V). Node u constructs the
tree T(u) and then broadcasts the structure of T(u) to all nodes in T(u). Since the total
number of edges in the Yao structure is at most k · n, where k is the number of cones di-
vided, the total number of edges of T(u) of all node u is also at most k · n. Thus, the total
communication cost is at most k · n. Li et al. [33] proved that its power stretch factor is at
most {1/[1 “ (2 sin /k) ]}2, the maximum degree of the graph YG *(V) is at most (k + 1)2
“ 1, and the maximum out-degree is k.
Notice that the sink structure and the Yao graph structure do not have to have the same
number of cones, and the cones centered at different nodes do not need to be aligned. For
setting up a power-efficient wireless network, each node u finds all its neighbors in
YGk(V), which can be done in linear time proportional to the number of nodes within its
transmission range.

YaoYao Structure. Li et al. [35] proposed another structure called YaoYao. Assume
that each node vi of V has a unique identification number ID(vi) = i. The identity of a di-
rected link uv is defined as ID(uv ) = (||uv||, ID(u), ID(v)).

Node u chooses a node v from each cone, if there is any, so the directed link vu has the
smallest ID(vu ) among all directed links wu in YG(V) in that cone. The union of all cho-
sen directed links is the final network topology, denoted by YYk(V). If the directions of all
links are ignored, the graph is denoted as YYk(V). They [35] proved that the directed graph
YYk(V) is strongly connected if UDG(V) is connected and k > 6.
It was proved in [37] that YYk(V) is a spanner in a civilized graph. Here a unit disk
graph is a civilized graph if the distance between any two nodes in this graph is larger than
a positive constant . In [38], the civilized unit disk graph is called the -precision unit
disk graph. Notice that the wireless devices in wireless networks can not be too close or
overlapped. Thus, it is reasonable to model the wireless ad hoc networks as a civilized unit
disk graphs.
The experimental results obtained by Li et al. [35] showed that this sparse topology has
a small power-stretch factor in practice. They [35] conjectured that YYk(V) also has a con-
stant bounded power-stretch factor theoretically in any unit disk graph. The proof of this
conjecture or the construction of a counterexample remain to be determined.

Symmetric Yao Graph. In [35], Li et al. also considered another undirected structure
called a symmetric Yao graph YSk(V). An edge uv is selected to graph YSk(V) if and only if
both directed edges uv and vu are in the Yao graph YG k(V). Then it is obvious that the
maximum node degree is k.
Li et al. [33] showed that the graph YSk(V) is strongly connected if UDG(V) is connect-
ed and k 6. The experiment by Li et al. also showed that YSk(V) has a small power-
stretch factor in practice. However, it was shown recently in [21] that YSk(V) is not a span-
ner theoretically. The basic idea of the counterexample is similar to the counterexample
for RNG proposed by Bose et al. [32].

High-Degree Yao Graph. Recently, Li et al. [39] proposed an efficient scatternet for-
mation method based on the Yao structure.
The first step, which is optional, of the scatternet formation algorithm is to construct
some subgraph satisfying some properties such as planar properties. In the second step,


. 35
( 87 .)