Formal methods for the analysis of wireless network protocols

Thesis

In this thesis, we present novel software technology for the analysis of wireless networks, an emerging area of computer science. To address the widely acknowledged lack of formal foundations in this field, probabilistic model checking, a formal method for verification and performance analysis, is used. Contrary to test and simulation, it systematically explores the full state space and therefore allows reasoning about all possible behaviours of a system.

This thesis contributes to design, modelling, and analysis of ad-hoc networks and randomised distributed coordination protocols.

First, we present a new hybrid approach that effectively combines probabilistic model checking and state-of-the-art models from the simulation community in order to improve the reliability of design and analysis of wireless sensor networks and their protocols. We describe algorithms for the automated generation of models for both analysis methods and their implementation in a tool.

Second, we study spatial properties of wireless sensor networks, mainly with respect to Quality of Service and energy properties.

Third, we investigate the contention resolution protocol of the networking standard ZigBee. We build a generic stochastic model for this protocol and analyse Quality of Service and energy properties of it. Furthermore, we assess the applicability of different interference models.

Fourth, we explore slot allocation protocols, which serve as a bandwidth allocation mechanism for ad-hoc networks. We build a generic model for this class of protocols, study real-world protocols, and optimise protocol parameters with respect to Quality of Service and energy constraints. We combine this with the novel formalisms for wireless communication and interference models, and finally we optimise local (node) and global (network) routing policies.

This is the first application of probabilistic model checking both to protocols of the ZigBee standard and protocols for slot allocation.

Authors: Fruth, M

• Publication date: 2011
• Type of award: DPhil
• Level of award: Doctoral
• Awarding institution: University of Oxford
• Language: English
• Keywords: quantitative analysis; formal methods; wireless network protocols; probabilistic model checking
• Subjects: Computer science (mathematics); Program development and tools; Theory and automated verification