For the detailed
algorithm and proofs, refer to [56]. The authors also claimed they could
in their method.
1
132
build a bounded degree planar length-spanner by using LDel instead of GG
tion. The only problem here is the last step ??” a greedy method can not be
Here the constant factor depends on . ?«
Chapter 5 Topology Control for Wireless Sensor Networks
4 Virtual Backbones
While all the geometric structures discussed so far are flat structures, another
set of structures, called hierarchical structures, is used in wireless sensor networks
as network topologies. Instead of all nodes being involved in relaying
packets for other nodes, the hierarchical routing protocols pick a subset of
nodes that serve as the backbone routers, forwarding packets for other nodes.
The notion of establishing a subset of nodes which perform the routing has
been proposed in many routing algorithms [57??“60]. These methods often construct
the virtual backbone by using the connected dominating set, which is
often constructed from a dominating set or a maximal independent set.
A subset S of V is a dominating set if each node u in V is either in S
or is adjacent to some node v in S. Nodes from S are called dominators,
while nodes not in S are called dominatees. A subset C of V is a connected
dominating set (CDS) if C is a dominating set and C induces a connected
subgraph. Consequently, the nodes in C can communicate with each other
without using nodes in V ??’C.
Pages:
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232