Database Reference
In-Depth Information
send the pair
<v
i
,h
i
>
to the aggregator. On receiving all pairs from
sensors, the aggregator computes the maximum value
v
m
. For any other
value
v
i
<v
m
, the aggregator further applies
H
by
v
m
v
i
times on
h
i
and get the new digest, which is the result of applying
H
by
v
m
times on
s
i
. SECOA then defines folding function
F
that combines all digest into
one,
h
. The aggregator sends the pair
<v
m
,h >
to the portal. Since
the portal is aware of all
k
i
, it can compute the corresponding
s
i
and the
digests by applying
Hv
m
times on
s
i
.Using
F
to combine the digest
together, the portal will get identical
h
if the aggregator did not cheat.
Assume that node
n
j
has the maximum value
v
m
and the aggregator
reports a value
v
m
<v
m
. Since the aggregator does not know
k
j
and
H
is applied in one-way, it is not able to generate the correct digest for
n
j
and
h
. Thus, by this one-way chain technique, the completeness of the
aggregation is ensured in a communication-ecient way.
−
5.4 E
cient Algorithms for Specific
Aggregations
As discussed in previous sections, COUGAR is a general framework
for both acquisition and aggregation queries. TAG is optimized for ag-
gregation queries, while TinyDB is acquisition-query oriented. CONCH
further explores the spatial-temporal correlation among sensor readings
to reduce the communication cost. However, for some specific aggre-
gations, more ecient algorithms exist. This section surveys energy-
e
cient algorithms for continuous extreme and top-k value monitoring.
5.4.1 Extreme Value Monitoring.
Extreme value monitor-
ing in a WSN is extensively studied recently. TAG [8] supports MAX
queries in a straightforward way. When a query comes, each leaf node
in the routing tree sends its parent the current reading. An intermedi-
ate node sends its parent the maximum reading among all its children
and itself. In the end, the maximum value propagates to the base sta-
tion, which is the root of the routing tree. For a continuous query, such
procedure is repeated in every cycle.
Rather than TAG, A. Silberstein et al. [11] propose a set of threshold-
based algorithms for extreme value monitoring. The Hierarchical Adap-
tive Thresholds (HAT), which follows the tree topology, is the most
energy-ecient. HAT maintains a threshold for each node, indicating
the upper bound of the maximum value in its sub-tree. It is satisfied
that a parent's threshold never falls below those of its children and the
root's threshold is the current maximum value. For continuous queries,
the root periodically issues signals requesting updates from the nodes.
