Consider any
unicast ? (u, v) in G from a node u ??? V to another node v ??? V : ? (u, v) =
v0v1 ?· ?· ?· vh??’1vh, where u = v0, v = vh. Here h is the number of hops of
the path ? . The total transmission power p(? ) consumed by this path ? is
defined as
p(? ) =
h
X
i=1
kvi??’1vik??.
Let pG(u, v) be the least energy consumed by all paths connecting nodes u
and v in G. Let H be a subgraph of G. The power stretch factor of the graph
H with respect to G is then defined as
??H(G) = max
u,v???V
pH(u, v)
pG(u, v)
.
If G is a unit disk graph, we use ??H(V ) instead of ??H(G). If the ??H(V )
is bounded by a constant for all unit disk graphs, we call the graph H a
power spanner. Similarly, we can define the length stretch factors ?„“H(G) and
116
Chapter 5 Topology Control for Wireless Sensor Networks
?„“H(V ) by setting ?? = 1. And we say a graph H is a length spanner if the
?„“H(V ) is bounded by a constant. It is not di?±cult to show that, for any
H ??† G with a length stretch factor ??, its power stretch factor is at most
???? for any graph G. In particular, a graph with a constant bounded length
stretch factor must also have a constant bounded power stretch factor, but
the reverse is not true. Finally, the power stretch factor has the following
monotonic property: If H1 ??‚ H2 ??‚ G, then the power stretch factors of H1
and H2 satisfy ??H1 (G) ?‰? ??H2 (G).
Several geometrical spanners have been studied recently both by computational
geometers and network engineers.
Pages:
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201