When the size of the boundary R stops
167
Ren-Shiou Liu, Lifeng Sang, and Prasun Sinha
d d
Fig. 14. One move in the Growing Phase.
increasing, the nodes at the other side of the region have the complete boundary
information. Then the final boundary set information is passed back. This
is called the Feedback Phase. At the end of this phase, all the nodes in the
square have the same set of region nodes.
??? Running Time:
Suppose there are n ?— n nodes in the square, then in the worst case, the
running time of the growing algorithm is 2n, since the detected region
boundary R first moves forward at the Growing Phase, and the final information
is passed back to update the local region boundary at previously
visited nodes in the Feedback Phase.
??? Number of Messages:
Let the length of square side be unit 1. The distance between neighboring
nodes is d = 1/n. Let the radio range be in the range (1/n, 2/n), i.e.,
sensors would only send messages to its nearest neighbors, and the power
required per transmission would be proportional to the area of reception,
i.e., kd2. At the end of the ith iteration, all the sensors within i hops have
updated to their final value. So the total transmission power required is
[10]:
Power = kd2[
n??’1
Xi=0
(n2 ??’
i
Xj=0
j) +
n??’1
Xi=1
i
Xj=1
j] = kd2n3 = kn. (24)
This means that the total power needed for transmission is proportional
to the square root of the number of nodes deployed in the grid.
Pages:
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287