ñòð. 35 |

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

177

6.2 NETWORK TOPOLOGY CONTROL

to find the minimum transmission range such that the induced unit disk graph is multiply

connected.

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.

6.2 NETWORK TOPOLOGY CONTROL

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

178 TOPOLOGY CONTROL IN WIRELESS AD HOC NETWORKS

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

179

6.2 NETWORK TOPOLOGY CONTROL

u v

u v u

RNG GG Yao

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-

180 TOPOLOGY CONTROL IN WIRELESS AD HOC NETWORKS

vn-2

vn-1

vi+1

u Î±

Î± v1

vi

Î±

v2

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

k

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

k

â€“ 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)).

181

6.2 NETWORK TOPOLOGY CONTROL

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 |