Database Reference
In-Depth Information
sor networks is
recurrent
. Code repeatedly visits the same states
(perhaps not strictly periodically), repeating the same actions over
time. Hence, a single problem, such as a node reboot or a race
condition that pollutes a data structure, often results in multi-
ple manifestations of the same unusual symptom (such as multiple
subsequent message losses or multiple subsequent false alarms).
Catching these recurrent symptoms by a frequent pattern mining
algorithm is much easier due to their larger frequency. With such
symptoms identified, the search window can be narrowed to the
neighborhood of those frequent patterns, and it becomes easier
to correlate them with other less frequent preceding event occur-
rences.
Event frequencies and sampling:
One diculty in debugging sen-
sor network software is that the amount of logged events and the
corresponding frequency of patterns can be different from run to
run depending on factors such as length of execution and system
load. A higher sampling rate at sensors, for example, may gen-
erate more messages and cause more events to be logged. Many
logged event patterns in this case will appear to be more frequent.
This is problematic when it is desired to compare the frequency of
patterns found in “good” and “bad” data piles for purposes of iden-
tifying those correlated with bad behavior. To address this issue,
one needs to normalize the frequency count of events in the log.
Note, however, that often the amount of load itself is a contribut-
ing factor to the cause of a bug manifestation. Hence, the best
normalization is application specific. This issue has been recently
discussed (in the specific context of sensor network debugging) in
Dr. Khan's Ph.D. thesis [46].
Handling multi-parameter events:
There are also issues with han-
dling event parameters. Since event parameter values may be dif-
ferent, calling each possible combination of parameter values of
an event a different name will cause a combinatorial explosion
of the alphabet. To address the problem, continuous or fine-
grained parameters need to be discretized into a smaller number
of ranges. Multi-parameter events need to be converted into se-
quences of single-parameter events each listing one parameter at a
time. Hence, the exponential explosion is reduced to linear growth
in the alphabet. Techniques for dealing with event parameter lists
were introduced in [48].
An example bug that Dustminer was reported to diagnose using se-
quence mining is a problem with a multichannel MAC protocol that
