And the quad-tree can also be pruned to form a non-uniform
rectangular domain as shown in Figure 17.
A consequent question is: how can the pruning process be implemented
in the sensor network? Let Pn denote the set of all possible pruned trees,
then for each p 2 Pn, p has a corresponding quad-tree structure where each
non-leaf node has four children nodes that represent a square region. Consider
171
Ren-Shiou Liu, Lifeng Sang, and Prasun Sinha
Fig. 17. An illustration of non-uniform rectangular domain.
these squares as clusters, where each cluster has a clusterhead which collects
information from the other nodes (here nodes represent sub-partitions) in the
region. Consider all potential pruning p 2 Pn, each sensor node belongs to a
nested hierarchy of side length: 1, 2, 4, . . . ,pn (totally 1
2 log2n levels).
Since the raw data {xi,j} might be noisy, and transmission of raw data
would require a maximum amount of energy for message passing, locally processed
data would have a better performance considering accuracy and energy
consumption. There could be various methods for the local processing. In [9],
for instance, the authors compute the average information from sensors in the
square, denoted by !(p) for pruning p, so the sum-of-squared errors between
average and raw data for pruning p is,
E(!, x) =
pn
Xi,j=1
(!(i, j) ??’ xi,j)2. (27)
To decrease the e?®ect of unnecessarily high resolution partitions, they also
define a complexity penalized estimator as
?†pn = arg min!(p):p2PnE(!(p), x) + 2??2f(n)|!(p)|.
Pages:
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293