We call a sub-rectangle Z of R a zone, if
Z is obtained by dividing R k times, k ?? 0, using a procedure that satisfies
the following property:
1. After the i-th division, 0 ?? i ?? k, R is partitioned into 2i equal sized
rectangles;
2. If i is an odd number, the i-th division is parallel to the y-axis; otherwise
the division is parallel to the x-axis.
Following is the procedure by which a zone is constructed. The bounding
rectangle R is first sub-divided into two zones at level 0 by a vertical line that
splits R into two equal pieces, each of these sub-zones can be split into two
zones at level 1 by a horizontal line, and so on. For each zone Z, there is a
non-negative integer k that indicates the level of zone Z, i.e., level(Z) = k.
As a result of this division process, each zone is assigned a bit string, called
its zone code that reflects its position in the splitting process. The splitting
process can itself be represented as a binary tree, called the zone tree.
308
Chapter 12 Data Management in Sensor Networks
In DIM, each network node is mapped to a unique zone. If the sensor
network is deployed in a grid-like fashion, then it is easy to see that there
exists a k such that each node maps into a distinct level-k zone. In general,
however, the node placements within a sensor field are likely to be less regular
than the grid. For a given k, some zones may be empty and other zones might
have more than one node situated within them.
Pages:
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496