Sensors 2015, 15 15039
dense in some sub-regions of the network, while they are sparse in the others. In fact, sensor nodes are
distributed unevenly in real-world applications, including bridge or traffic monitoring scenarios [3]. An
example of sensor nodes in a skewed distribution is shown in Figure 2, where sensor nodes located in
the upper center and the right bottom of the network region are dense, while the others are sparse. A
sensor node is assumed accompanied by one sensing equipment for sensing a certain attribute, such as
humidity, temperature, gas flow, etc. Various sensor nodes with different sensing equipment are able to
sense diverse attributes. The index tree construction algorithm proposed by Algorithm 1 in our previous
work [33] works as follows:
• The network region is divided into square grid cells whose side-length is set to
√
2r, and an inverted
file [37] is attached to each grid cell for specifying the attributes to be sensed by the sensor nodes
therein. An example of grid cell division is shown in Figure 2, where the network is divided into
25 grid cells, and a two-dimensional matrix is adopted to represent the coordinates of these grid
cells. Actually, grid cells correspond to the leaf nodes of the index tree to be constructed.
• The weight between two neighboring grid cells or sub-regions is calculated according to the
mechanism proposed by the Algorithm 2 in our previous work [33]. This weight specifies the
energy consumption of forwarding the same size of message between neighboring grid cells.
Intuitively, sensor nodes in neighboring grid cells contribute to this weight calculation when the
Euclidean distance between them is no more than the communication radius of sensor nodes r.
• Neighboring grid cells or sub-regions are merged in a pair-wise fashion when the weight between
the candidates is the greatest, and the inverted file is processed accordingly. This merging
procedure iterates until the root node of the index tree, which is a binary tree in shape, is
constructed. Note that this merging strategy makes adjacent sub-regions, which may induce
relatively larger energy consumption when forwarding messages in between, to be included by
different children. Consequently, the energy consumption for routing data packets along the paths
specified by this index tree is balanced somehow.
Generally, the Algorithm 1 in our previous work [33] constructs a tree that may be unbalanced,
especially when sensor nodes are distributed unevenly in the network. Since [33] does not cache sensory
data in leaf head nodes, leaf head nodes gather sensory data from sensor nodes and route these data to
the SN. An unbalanced tree for a skewed distribution of sensor nodes prolongs the network lifetime, as
evidenced by the experimental evaluation conducted in [33]. On the other hand, leaf head nodes require
caching sensory data locally, as presented by Section 4 in this article, and sensory data, whose variation
is beyond an allowed threshold, are not required to be routed to the SN. Therefore, when sensory data
of most sensor nodes do not vary dramatically, the effort for routing sensory data to the SN should be
lighter than that of [33] in the network, but the effort of leaf head nodes should be heavier due to the
caching of sensory data locally. Intuitively, an unbalanced tree should a have much greater number of
head nodes whose children include sensor nodes and head nodes, while all head nodes should be leaf
head nodes for a half tree [38]. Therefore, more hops are to be involved when routing sensory data to the
sink node in a hop-by-hop manner, especially when the path is longer in hops. To facilitate the caching
mechanism upon leaf head nodes as presented in Section 4, a relatively balanced tree is constructed for
organizing sensor nodes in this article.