ñòð. 36 |

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

182 TOPOLOGY CONTROL IN WIRELESS AD HOC NETWORKS

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-

gle.

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

y

y

x x

w

v

v

u u

u v w

w

RNG GG Yao

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.

183

6.2 NETWORK TOPOLOGY CONTROL

6.2.3.1 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

triangles.

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

LDel(2)(V).

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.

6.2.3.2 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).

184 TOPOLOGY CONTROL IN WIRELESS AD HOC NETWORKS

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).

6.2.3.3 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 =

uwv.

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

185

6.2 NETWORK TOPOLOGY CONTROL

w

w Î± v

u

Î± v

u

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-

186 TOPOLOGY CONTROL IN WIRELESS AD HOC NETWORKS

Figure 6.5. Different topologies from UDG(V).

187

6.2 NETWORK TOPOLOGY CONTROL

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 |