High Level Definition of Event-Based Applications for Pervasive Systems - Advanced Design Approaches to Emerging Software Systems - page 154

or subtrees of the EDT cannot be evaluated by
the node itself. In that case, sensor nodes need to
collaborate to exchange information about sensor
readings or partial evaluation results.
The exchange of sensed raw data, which is done
by most approaches, is very inefficient from two
points of view. First, permanent exchange of sensor
readings leads to a huge number of transmissions
and hence, consumes much energy and reduces
network performance. Second, transmitting raw
sensor data requires to use rather large data pack-
ages, depending on the number of readings and
their accuracy, i.e., the size of each value usually
varies from two to four bytes. Since a conceptual
main goal is to remain very energy efficient, we
focus on minimizing the number of transmissions
and the amount of data to be exchanged. Instead of
exchanging raw sensor readings at each detection
interval, sensor readings are locally processed first
and only one bit is eventually submitted, which
is the Boolean value of a particular EDT node.
Other existing approaches that share information
in a comparable style state the complete detec-
tion result only, i.e., the Boolean value of the root
node. This concept focuses on efficiently sharing
information about both, complete and partial EDT
evaluation results.
In case of using EDT, the Boolean value of
only one particular EDT node has to be transferred.
Missing node values may be delivered by neigh-
boring nodes that share the specified collaboration
region. To prepare these data exchanges, every
sensor node has to determine which EDT node
information is missing at the local EDT. Therefore
the following algorithm prunes the established
EDT until it contains the minimum required EDT
for local event processing:

or both child nodes are marked as pruned
in that case.
a. Mark node as pruned, if
i. It represents an algebraic opera-
tion or
ii. The unmarked child represents a
constant or
iii. All child nodes are marked as
pruned.
3. Repeat step 2 until no new nodes are marked.
After that, all undecidable subtrees are
marked.
4. Prune all marked nodes except for the root
nodes of the marked subtrees.
5. Declare all left marked nodes as undecidable .

After pruning, the EDT may contain nodes,
which are marked as undecidable . Respective
Boolean node values must be obtained by other
nodes in the collaboration region. Let us assume
to use two different types of nodes (A and B) for
the introduced fire detection example. Nodes of
type A provide carbon monoxide and temperature
sensors, whereas type B nodes provide sensing
facilities for carbon monoxide and smoke. Hence,
the initial EDTs generated at these nodes must
be pruned with respect to the available sensing
capabilities.
Accordingly, type A nodes cut the branch
containing the smoke readings and type B nodes
respectively cut the branch containing the tem-
perature readings. That results in two different
EDTs at the sensing devices, each containing one
node marked as undecidable . Thus, type A nodes
require information about tree node number 9,
whereas type B nodes require information about
tree node number 6. Both resulting EDTs are dis-
played in Figure 9. At regular evaluation, the EDT
also checks the status of the sensing devices. If
sensing devices fail during application the sensor
node runs the pruning again to locally self-adapt
the EDT to the current situation. In addition,
sensing devices may fail transiently only. In that
case, the sensing device becomes available again

1. Mark each leave as pruned that represents
an unsupported sensing capability.
2. Search all nodes that possess at least one
marked child excluding the root node. Since
an EDT is a binary tree, every node possesses
at most two child nodes. Hence, either one