Alharbi, Alwaleed (2021) Towards accurate predicate detection in wireless sensor networks. PhD thesis, University of Warwick.

Preview

PDF WRAP_Theses_Alharbi_2021.pdf - Submitted Version - Requires a PDF viewer. Download (2747Kb) | Preview

Request Changes to record.

Abstract

Wireless sensor networks (WSNs) have enabled a large class of novel applications such as environment monitoring and tracking. The size and cost of the WSN devices have made it that such devices can be deployed on a large scale. However, WSNs are often deployed in harsh environments where the network may not be reliable. As such, applications may not run as intended, thereby requiring run-time monitoring to determine when applications are deviating from their intended behaviour. The monitoring of the system takes the form of detecting whether a given predicate holds true during the execution of the system, where the predicate captures a notion of correctness of the system, i.e., there is a need to monitor when a predicate turns true or false. However, the process of monitoring and debugging wireless sensor networks has many challenges. One of the challenges is that the network may not be reliable. Another challenge is the resource constraints imposed on the devices such as energy. Another one of the major challenges is that overhead and the size of the monitoring system must both be kept to a minimum. The monitoring system should not interfere with any running application that needs to be monitored since the monitoring system needs to run independently. Many monitoring systems implement various methods for debugging their applications; all techniques invariably contain a sensor data collection step at monitors. Typically, it has either been assumed that the network sink is the monitor or every node is a monitor. However, in this thesis, we address the problem of monitor selection and provide a novel formalisation of the problem. Adopting a different perspective of the predicate detection problem, we refactor the problem into two important problems: (i) monitor selection problem and (ii) predicate detection problem. As such, the main works performed in this research are: (i) we show that the problem of Monitor Selection Problem (MSP) is NP-complete and (ii) to circumvent the inherent complexity associated with monitoring, we develop a number of heuristics to support data collection for debugging. The application that will be used to showcase the framework is a TDMA slot assignment. We define the predicate that captures the correctness for TDMA and use the heuristics to monitor it. Four main contributions are presented. First, a novel formalisation of monitor selection model is presented, allowing for comparison of the existing and different approaches. Second, once the monitor selection problem has been formalized, a heuristic is presented and developed for WSN to circumvent the complexity of selecting monitors. Third, different frameworks are presented with multiple algorithms in WSN that disseminate messages throughout the network. Finally, extensive simulation and real hardware (i.e., testbed) experiments are conducted in order to investigate the overall performance and accuracy of each implemented infrastructure and algorithm. Our results show that our protocols can outperform state-of-the-art protocols for predicate detection at much lower overhead.

Item Type:	Thesis (PhD)
Subjects:	Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software
Library of Congress Subject Headings (LCSH):	Wireless sensor networks, Wireless sensor networks -- Reliability, Predicate (Logic), Information integrity, Debugging in computer science., Computer programs -- Correctness
Official Date:	March 2021
Dates:	Date Event March 2021 UNSPECIFIED
Institution:	University of Warwick
Theses Department:	Department of Computer Science
Thesis Type:	PhD
Publication Status:	Unpublished
Supervisor(s)/Advisor:	Jhumka, Arshad, 1974-
Sponsors:	Taif University ; Royal Embassy of Saudi Arabia Cultural Bureau
Format of File:	pdf
Extent:	xvii, 144 leaves : illustrations
Language:	eng

Request changes or add full text files to a record

Repository staff actions (login required)

View Item

Downloads