Then [48, 50] presents some new algorithms that improve the computational
complexity of each node while still maintaining low communication costs.
Low-Weight Structure Based on LMST
The new method in [48, 50] uses a structure called local minimum spanning
tree. It was first introduced by Li, Hou and Sha [52]. Each node u first
collects its one-hop neighbors N1(u). Node u then computes the minimum
spanning tree MST(N1(u)) of the induced unit disk graph on its one-hop
neighbors N1(u). Node u keeps a directed edge uv if and only if uv is an edge
in MST(N1(u)). They call the union of all directed edges of all nodes the local
minimum spanning tree, denoted by LMST1. They prove that the graph is
connected, and has bounded degree 6. In [48,50], Li et al further showed that
graph LMST1 is actually planar but not low weight. Then they extend the
definition to k-hop neighbors, the union of all edges of all minimum spanning
trees MST(Nk(u)) is the k local minimum spanning tree, denoted by LMSTk.
For example, the two local minimum spanning trees can be constructed
as follows. Each node u collects its two-hop neighbors??™ information N2(u).
Each node u computes the Euclidean MST MST(N2(u)) of all nodes N2(u),
including u itself. For each edge uv ??? MST(N2(u)), node u tells node v
about this directed edge. Node u keeps an edge uv if uv ??? MST(N2(u)) or
vu ??? MST(N2(v)). Let LMST+
2 be the final structure formed by all edges
kept.
Pages:
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226