Modeling, Performance Analysis and Design of Wireless Networks for Embedded Sensing Applications

Abstract

The general theme of this thesis is modeling, performance analysis, and design of wireless networks under standardized CSMA/CA MAC protocols. In particular, we consider two widely used MAC protocols, namely, IEEE 802.15.4, and IEEE 802.11. The first two parts of the thesis are devoted to systematic design and analysis of multi-hop wire-less networks under the IEEE 802.15.4 (“ZigBee”) PHY and MAC for embedded sensing and monitoring applications, which are becoming ubiquitous with the advent of the Internet of Things (IoT). In particular, we address the broad problem of designing a multi-hop wireless sensor network at minimum deployment cost, i.e., by placing as few additional relay nodes and base stations as possible, to convey sensed data from a set of given source locations to at least one base station location, while satisfying some given Quality of Service (QoS) objectives such as end-to-end probability of delivery, mean delay, and robustness to node failures. Depending on the deployment area, and tra c requirements of the applications, this problem leads to several design problems. In Part 1 of the thesis, we deal with very low data rate applications such as those encountered in environment or resource monitoring applications (e.g., smart metering). In this case, the contention due to CSMA/CA is negligible, and we show that the problems reduce to one of graph design with various topological constraints. For each of these graph design problems, we provide a mathematical formulation under certain simplifying assumptions, study the computational complexity of the formulation (and show that the problems are NP-hard), and propose polynomial time heuristic approximation algorithms to obtain good solutions within a reasonable computation time. We also provide worst case and average case approximation guarantees for our proposed algorithms. In Part 2, we deal with low to moderate data rate applications such as those encountered in health monitoring. In this case, the contention due to CSMA/CA must be taken into account to accurately predict the network performance. We adopt an approximate, but accurate fixed point analysis for multi-hop tree networks developed in [1] that takes into account collision due to CSMA/CA contention, hidden node effects, etc. We provide a simplification of this analysis for the case of no hidden nodes in a regime where the packet discard probability is low; we then use this simplified model to derive explicit conditions on the topology, and the arrival rate vector to satisfy given QoS objectives. This, in turn, enables us to derive simple design rules for throughput optimal network design for a wide range of QoS objectives. Part 3 of the thesis is devoted to the study of single-hop networks operating under the IEEE 802.11 DCF MAC (“WiFi”). However, unlike the conventional WiFi, we study systems where one or more of the protocol parameters are different from the standard, and/or where the propagation delays among the nodes are not negligible compared to the duration of a backoff slot. We observe that for several classes of protocol parameters, and for large propagation delays, such systems exhibit a certain performance anomaly known as short term unfairness, which may lead to severe performance degradation. The standard fixed point analysis technique (and its simple extensions) do not predict the system behavior well in such cases; a mean field model based asymptotic approach also is not adequate to predict the performance for networks of practical sizes in such cases. We have developed a new approximate, but accurate analytical framework for predicting the performance of such systems. Apart from providing insights into the system behavior, the analytical method is also able to quantify the extent of short term unfairness in the system, and can therefore be used for tuning the protocol parameters to achieve desired throughput and fairness objectives.