Database Reference
In-Depth Information
ceiving a query, the base station propagates it to its children. This query
continues propagating level by level between parent-child links until it
reaches the leaf nodes. Suppose the query never affects parts of the net-
work, it is energy-e
cient to stop the query from being propagated into
leaf levels as early as possible. TinyDB [7] achieves this by building the
semantic routing tree, SRT, to guide the query dissemination. SRT is a
routing tree embedded with a semantic index, which is an index on each
node
n
i
built according to the sensor readings in the sub-tree rooted at
n
i
. In particular, the user specifies the queried sensors by restricting
their attribute(s),
A
, e.g., ID, location, etc. Conceptually, SRT is an
overlay index upon
T
and is maintained over time. In order to build
SRT, for each attribute
a
x
in A, a node
n
i
collects and keeps
a
x
's range
(i.e., an aggregation of
a
x
readings in the sub-tree rooted at
n
i
)asthe
index. When a query arrives,
n
i
checks whether the ranges kept in the
index intersects with the query range. If there is no intersection, the
query does not overlap with the range represented by its sub-tree and
it is dropped at
n
i
. On receiving the query, a node senses the environ-
ment retrieves the physical readings and performs local computation.
The query results are transmitted bottom up on
T
.Ifthequeryasks
for an aggregation, e.g., maximum value, sum, average, etc., in-network
aggregation is performed in order to reduce the sizes of the transmitted
messages [4 13]. The advantage of tree-based topology is energy e-
ciency, since each node sends messages only to its parent.
Figure 3.1(a)
gives a tree-based WSN topology, where the black node represents the
base station and gray nodes are sensors. The solid and dashed lines con-
necting nodes are bidirectional physical radio connections. However, the
latter are conceptually removed by the routing protocol, i.e., there are
no data transmissions on those connections. Several works aim at en-
hancing the robustness of tree-based topologies. A common approach is
to make the routing tree recoverable when some nodes stop functioning.
Specifically, each node
n
i
maintains a table of neighboring nodes and
it periodically examines the link quality with its current parent. Once
the link is broken,
n
i
sends requests to its neighbors asking for a new
parent and reports to the new parent once the request is accepted. How-
ever, algorithms have to consider the possible duplications of the sensor
readings during the handing over stage. Another approach to partially
overcome the vulnerability of the tree-based topology is to build multi-
ple trees on the wireless sensors. Each piece of data is able to reach the
base station through multiple paths. Obviously, this approach sacrifices
energy eciency for robustness.
The routing tree can be optimized according to different criteria [15
16 17], e.g., link quality, energy eciency, responsiveness, etc. However,
