Notice that the sensor devices
in wireless sensor networks can not be too close or overlapped. Thus,
it is reasonable to model the sensor network as a civilized unit disk graph.
The experimental results by Li et al [35, 40] showed that this sparse topology
has a small power stretch factor in practice. They [35, 40] conjectured that
??’??’?†’ Y Y k(V ) also has constant-bounded length and power stretch factors theoretically
in any unit disk graph. Recently Jia et al [42] and Schindelhauer
et al [43] proved that ??’??’?†’ Y Y k(V ) has a constant bounded power stretch factor
theoretically. However, it is still an open problem whether it is a length
spanner.
Symmetric Yao Graph
In [30, 40, 44], Li et al also considered another undirected structure, called a
symmetric Yao graph Y Sk(V ), which guarantees that the node degree is at
most k. Each node u divides the region into k equal angular regions centered
at the node, and chooses the closest node in each region, if any. An edge uv is
selected to graph Y Sk(V ) if and only if both directed edges ??’?†’uv and ??’?†’vu are in
the ??’??’?†’ Y Gk(V ). Then it is obvious that the maximum node degree is k. In [30,44],
the authors proved that Y Sk(V ) is strongly connected if UDG(V ) is connected
and k ?‰? 6. The experiment in [30,40,44] also showed that it has a small power
stretch factor in practice. However, it was shown in [38] recently that Y Sk(V )
is not a spanner theoretically.
Pages:
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215