Database Reference
In-Depth Information
graph of events that causes failure (rather than a single component to
blame). These approaches are described in Section 3.
Finally, for completeness, we briefly survey in Section 4 the remaining
debugging techniques in sensor networks that do not use data mining
tools.
2. Classification-based Bug Localization
A popular category of diagnostic tools in sensor networks, that takes
inspiration from data mining and machine learning literature, is based
on classifiers. These tools label the current state of the network as either
normal or abnormal, and recognize different types of abnormal behav-
ior. The used classifiers typically fall into one of three general types
presented in the subsections below; namely,
simple rule-based classifiers
(where classification rules are input by domain experts),
supervised clas-
sifiers
(that need examples of good and bad behavior to learn to recog-
nize bugs), and
unsupervised classifiers
that learn to detect anomalous
behavior and relate the anomaly to small pieces of code that are easy to
inspect manually.
2.1 Simple Rule-based Classifiers
One of the earliest classification-based approaches in sensor network
troubleshooting literature was implemented in a tool, called Sympa-
thy [78] that uses a set of prespecified rules for root cause analysis and
failure source localization. The tool diagnoses root causes of commu-
nication problems. In this framework, nodes proactively exchange di-
agnostic information such as connectivity and flow states. When nodes
receive fewer messages than normal, they run a diagnostic tree fault-
classification algorithm that utilizes received information to localize the
problem. A contribution of the tool lies in understanding the most
probable cause of failure among different alternative explanations. For
example, a base-station that collects data from a sensor network is triv-
ially aware of the reachability of all nodes. When a number of nodes
suddently stop reporting, it is not immediately clear what the reason
is. It could, for example, be attributed to the failure of only one node
that is the parent of the disconnected subtree in the data collection tree.
By inspecting node connectivity information (e.g., previously received
node neighbor tables), Sympathy is able to reason about such failures
and come up with the most likely explanation of the primary failure.
For example, it could identify which particular node died (which is the
primary failure), isolating an entire subtree (which is a secondary, de-
pendent failure), as opposed to suspecting the whole subtree of dying.
