The message UpdateN includes all unselected neighbors.
Once the node u receives the message UpdateN for deleting edge vu from
its neighbor v, it deletes the node v from its local list NOY GG(u). When all
nodes are processed, all the remaining edges {uv|v ??? NOY GG(u)} form the
final network topology OrdY aoGG.
It is proved in [46] that OrdY aoGG is a bounded-degree planar power
spanner. The power stretch factor is at most 1
1??’(2 sin ??
k )?? while the node degree
is bounded from above by a positive constant k+5 where k > 6 is an adjustable
126
Chapter 5 Topology Control for Wireless Sensor Networks
parameter. Moreover, by assuming that the node ID and its position can be
represented in O(log n) bits each for a sensor network of n nodes, they showed
that the structure can be constructed using at most 24n messages, where each
message is O(log n) bits.
Furthermore, Song et al. [46] proposed another method to build a degreebounded
planar power spanner, which can be constructed easier and demands
less communication cost during construction.
Algorithm 2 Construct Degree-k Planar Power Spanner
1. First, each node self-constructs the Gabriel graph GG locally.
2. All nodes together self-form the final topology as follows. Initially, each
node u is marked withWhite, i.e., unprocessed, and initializes NSY GG(u)
as the set of all the neighbor nodes in GG.
a) If a White node u has the smallest ID among its White neighbors in
GG, it divides its transmission range into k equal-sized cones where
k > 8 is an adjustable parameter.
Pages:
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220