Therefore, we want the network broadcast topology to be a
low-weight structure. Given a structure G over a set of points, let ?‰(G) be the
total length of the links in G and ?‰??(G) be the total power needed to support
all links in G, i.e., ?‰??(G) = Puv???G kuvk??. Then, a structure G is called low
weight if ?‰(G) is within a constant factor of ?‰(MST).
Unfortunately, the total weight of any graph structures mentioned above
could be arbitrarily larger than MST theoretically [35, 48]. In [35, 48], an
instance of a wireless network with n nodes is given, and the total weight of
the relative neighborhood graph on the network could be n times the ?‰(MST).
In addition, all other graph structures described previously contain RNG as
a subgraph for that node configuration. It then implies our previous claim.
In this section we will discuss how to design algorithms achieving low
weight, and (possibly) in addition to some other properties such as spanner,
bounded degree, and planar.
128
Chapter 5 Topology Control for Wireless Sensor Networks
3.1 Localized Low-Weight Structures
Notice that it is well-known that the communication complexity of constructing
a minimum spanning tree of an n-vertex graph G with m edges
is O(m + n log n); while the communication complexity of constructing MST
for UDG is O(n log n) even under the local broadcasting communication model
in wireless networks. It was shown in [49] that it is impossible to construct
a low-weight structure using only one hop neighbor information.
Pages:
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223