Database Reference
In-Depth Information
by a linear chain of events. Rather they are caused by more complex
event patterns described more generally by
graphs
. For example, in
asensordatafusionsystem,ifafusionstagecollectsdatafromtwo
children (down the fusion tree) that are incompatible or inconsistent in
some way, fusion results may be incorrect. There are many ways such
incompatibility or inconsistency may occur. For instance, if in a target
tracking algorithm two sensors report distances to
different targets
but
give their targets the same ID, a subsequent target triangulation stage
may compute an incorrect target location. If two temperature sensors
report a
35 degree temperature, respectively, but use different
units, if units are not explicitly stated, a subsequent averaging stage will
compute an average that is incorrect in either unit. Here the issue lies
in inconsistent assumptions among nodes (e.g., inconsistent assumptions
regarding target identity, or inconsistent assumptions regarding used
units). Inconsistent assumptions do not mean that one of them is wrong.
For example, reporting the average temperature in either unit would
have been fine, as long as sensors agreed on the reporting unit. Also,
reporting the location of either target would have been fine as long as
nodes agreed on the reported target. It is the fusion of data from nodes
who disagree on assumptions that is the problem. This is not a problem
with the
sequence
of reporting. It is a problem best correlated to the
topology of the reporting
tree
, which includes two incompatible children
who report to the same parent. Hence, debugging such problems calls for
a discriminative pattern mining algorithm that looks for patterns that
are more complex than linear sequences, such as trees or more general
graphs.
PopMine [81] was the first tool in sensor network literature that used
discriminative graph mining
for diagnosing corner-case bugs. The tool
identifies the minimal causal directed acyclic graph (DAG) of events,
spanning multiple nodes, that captures a bug-triggering condition. Be-
ing based on causal order, a global notion of time is not required in
uncovering bug-triggering distributed event patterns. Bug triggering
event DAGs are identified by comparing execution graphs from success-
ful runs to those where bug manifestations are observed, and exposing
the minimal discriminative event DAGs that may be responsible for the
problem.
PopMine significantly extended prior sensor networks debugging tools,
based on data mining. Prior work considered simpler bug-triggering
conditions such as single events, event sets, or ordered chains of events,
as opposed to distributed event graphs.
As is the case with other tools discussed in this chapter, the input
to PopMine is “good” and “bad” execution event traces from runs of
−
31 and
−
