Aim
Developing lightweight probing schemes for Wireless Sensor Networks to explore and optimise the monitor placement problem for large sensor networks
Figure 1: Example of a small and generic network with three monitors (m1, m2, m3) and five non-monitors (v1, v2, v3, v4, v5), and some measurement paths (dashed lines), i.e., the paths used by the monitors to send probes. The linear equation system on the right describes the nodes observed by each path (same colour of the corresponding path). By checking the behaviour of the probes crossing these paths (e.g., delay) and solving the system of equations, monitors are capable of uniquely identifying a number of simultaneous node failures. The monitor placement problem consists of an optimization problem for minimizing the set of monitors necessary for localizing failures (with the value of being defined by the reliability requirements).
Figure 1: Example of a small and generic network with three monitors (m1, m2, m3) and five non-monitors (v1, v2, v3, v4, v5), and some measurement paths (dashed lines), i.e., the paths used by the monitors to send probes. The linear equation system on the right describes the nodes observed by each path (same colour of the corresponding path). By checking the behaviour of the probes crossing these paths (e.g., delay) and solving the system of equations, monitors are capable of uniquely identifying a number of simultaneous node failures. The monitor placement problem consists of an optimization problem for minimizing the set of monitors necessary for localizing failures (with the value of being defined by the reliability requirements).
Funder
Science Without Borders (Brazilian Scholarship – http://www.cienciasemfronteiras.gov.br/web/csf-eng/)
Main Contributors
Introduction
The recent popularity of different Internet of Things (IoT) applications, such as Digital Twins and Precision Agriculture, has led to the development of various embedded devices and wireless communications protocols to support and improve the deployment of Wireless Sensor Networks (WSN). Unfortunately, WSNs are fault-prone systems, consisting of resource-constrained devices, and unreliable wireless communication links. Additionally, these devices are regularly exposed to the physical world, making WSN more vulnerable to malicious attacks, interference, and physical damage compared to other non-wireless networked systems. Identifying and localising faults in WSN is relevant for the correct operation of these systems. However, it is a challenging task due to the system’s constraints, which resulted in a growing effort to develop efficient and accurate failure localisation methods.
Network tomography, the act of observing end-to-end in-network properties through a subset of nodes known as monitors, is an emerging approach to localise failures in such networks.
This non-intrusive solution can be applied to different applications without requiring knowledge of the underlying system. The efficiency of this method depends on the number and position of the monitors, with recent research proposing algorithms to optimise the monitor placement while accurately localising a number k of simultaneous failures. The state-of-the-art solution solves this problem using a greedy heuristic named maximum node-identifiability monitor placement (MNMP). Initial experiments with different networks show, however, that this approach is too slow and does not scale for large WSN.
This research project develops solutions to optimise the monitor placement problem, making it fast and adaptable to the topology changes common to WSN. For the fast computation of the monitor placement, we propose schemes for both reducing the size of the network analysed and the number of redundant operations. For adapting this placement to topology changes, we develop strategies to minimise the search for new monitors by only analysing the areas of interest. Our experiments show that our fast algorithms compute the best monitor placement 100x faster than the state-of-the-art, while the adaptive algorithm adjusts the initial monitor set 1000x more quickly.
Primary Research
Lightweight and accurate failure localisation and diagnosis methods for wireless sensor networks.