Specifically for topology control, many geometrical
structures have been proposed to be used as the power e?±cient topologies
for sensor networks. Remember, we use a unit disk graph to model the communication
graph for sensor networks. Not every connected subgraph of the
unit disk graph are suitable to be a network topology. One of the perceptible
requirements of topology 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 (power e?±ciency of the path) is captured by the stretch
factor of the subgraph. 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 subsection, we study how to construct a sparse spanner
(as the network topology) e?±ciently for a set of static sensor nodes.
Spanners have been studied intensively in recent years [7??“13]. Let G =
(V,E) be a geometric graph defined on an n-vertex set V with edge set E. The
distance in G between two vertices u, v ??? V is the total length (or 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. For sensor networks,
the communication graph G is modelled by a unit disk graph.
Pages:
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200