Another option is to keep an edge uv only if both nodes u and v want
to keep it. Let LMST??’2 be the structure formed by such edges.
In [50], they proved that structures LMST2 (LMST+
2 and LMST??’2 ) are
connected, planar, low-weight, and have bounded node degree at most 6. In
[48], they generalized the results to a k local minimum spanning tree. They
proved that (1) LMSTk is connected, for all k ?‰? 1; (2) LMSTk are planar
graphs and with bounded node degree at most 6, for all k ?‰? 1; and (3)LMSTk
is low-weight, for all k ?‰? 2.
Although the constructed structure LMST2 has several nice properties
such as being of bounded degree, planar, and low-weight, the communication
cost of the algorithm could be very large to save the computational cost of
each node. The large communication costs are from collecting the two-hop
neighbors??™ information N2(u) for each node u.
Low-Weight Structure Based on Combining RNG??? and LMST
We could improve the communication cost of collecting N2(u) by using
a subset of two hop information without sacrificing any properties. Define
NRNG???
2 (u) = {w | vw ??? RNG??? and v ??? N1(u)} ??? N1(u). The modified algorithm
[48, 50] works as follows.
All nodes together construct the graph RNG???. Each node u locally broadcasts
its incident edges in RNG??? to its one-hop neighbors. Each node u computes
the Euclidean MST MST(NRNG???
2 (u)) of all nodes NRNG???
2 (u), includ-
130
Chapter 5 Topology Control for Wireless Sensor Networks
ing u itself.
Pages:
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227