Sequence Mining Based Debugging of Wireless Sensor Networks

Wireless Sensor Network (WSN) applications are prone to bugs and failures due to their typical characteristics, such as extensively distributed, heavily concurrent and resources restricted. It becomes critical to develop efficient debugging systems for WSN applications. A flexible and generic debugger for WSN applications is highly demanded. In this thesis, I proposed and developed a flexible and iterative WSN debugging system based on sequence analyzing and data mining techniques. At first, I developed vectorized Probabilistic Suffix Tree (vPST), a variable memory length model to extract and store sequential information from program runtime traces in compact suffix tree based vectors, based on original Probabilistic Suffix Tree (PST). Then I built a novel WSN debugging system by integrating vPST with Support Vector Machine (SVM), a robust and generic classifier for both linear and nonlinear data classification. The vPST-SVM debugging system enables developers to target at any hot spots they know might be problematic in the program source codes. They simply need insert trace points into the hot spots, collect runtime traces, then iteratively analyze the traces and finally locate real bugs. At last, I studied three different test cases, two on LiteOS and one on TinyOS, to evaluate the proposed WSN debugging system. It is demonstrated to be an efficient, flexible, generic and portable WSN debugger by the case studies. In addition, the vPST-SVM sequence analyzing methodology provides researchers with an inspiring angle of view on extracting sequential features and obtaining meaningful insights from sequences by appropriate transformation of sequential data.