First, let two dominators u and v be neighboring dominators
if they are at most three hops away, i.e., they are neighbors in the graph
V irtG. For every pair of neighboring dominators u and v, their method will
find the shortest path with at most three hops to connect them. To bound
the total weight, they also run a distributed algorithm to build a MST on
graph V irtG. The nodes on this shortest path in the MST will be assigned a
role of connector. For the detailed algorithm, refer to [91]. Then they proved
that the connectors selected by their algorithm have a total cost no more
than 10 times the optimum for networks modelled by UDG. Therefore, the
constructed weighted connected dominating set has total cost no more than
min(18 log??, 4??+1)+10 times of the optimum. The advantage of this WCDS
is that the total cost is small compared with the optimum when either the
costs of wireless nodes are smooth, i.e., two neighboring nodes??™ cost di?®er by
a small constant factor, or the network density is low.
5 Others
For geometric structures, besides the spanner and low-weight properties, there
are many other research issues and challenges. For example, fault tolerance is
one of the central challenges in designing the wireless sensor networks. A sensor
node may be battery constrained or subject to hostile environments, so
individual node failure will be a regular or common event. To make fault tolerance
possible, first of all, the underlying network topology must have multiple
disjoint paths to connect any two given sensor devices.
Pages:
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243