Scalable Performance Analysis of Wireless Sensor Networks

Mahmoud Talebi

first promotor: prof.dr.ir. Jan Friso Groote (TU/e)
second promotor: prof.dr.ir. Jean-Paul Linnartz (TU/e)
Eindhoven University of Technology
Date: 25 October 2018
Thesis: PDF

Summary

The problem of state space explosion is one of the main challenges in verifying the correctness of software designs. This problem extends itself to the analysis and verification of wireless sensor network protocols as well. As such, there have been many developments for tackling this specific problem, one of which is the employment of the mean field approximation. The mean field approximation and its generalisation, the moment closure approximation (together called deterministic approximations), have been widely used in the analysis of stochastic models involving a large number of identical components.

This thesis deals with the application of deterministic approximations to the performance analysis of wireless sensor networks. In particular, the analysis focuses on MAC layer protocols such as ALOHA and CSMA/CA, the latter being the main focus of the research. In the first part of the thesis we lay the mathematical foundations of the applied techniques. We give a detailed description of the mean field approximation theorem and provide a proof on the proposed error of the approximation. Next, generalizations of this approximation technique, which are commonly called the moment closure approximations, are discussed. We introduce the Poisson and binomial moment closure approximations. An investigation of the accuracy of several moment closure approximations then follows, in which we conclude that binomial and Poisson moment closures can be accurate ways of approximating the behaviour of systems, and we study the properties of the models which affect this accuracy.

In the second part of the thesis we employ the methods above to analyse the performance of MAC layer protocols. We first consider a simple ALOHA network, and then move to a more complex lighting network involving a simple CSMA/CA communication model. Through this, we explore the challenges to model the phenomena that are present in wireless communication: i.e. interference (in carrier sensing and multi-packet reception), noise and spatial diversity. Next, we move to a thorough study of coexistence of ZigBee and Wi-Fi networks by developing a system of differential equations which captures the dynamics of the ZigBee network, and we compare the results with data from a real test bed to show the validity of the analysis. The third part of the thesis briefly discusses a more ad hoc study of scalability of a wireless network protocol, to show that investigating the interaction of a few nodes can often lead to deep insights about how protocols scale.