Network Robustness Analysis for IoT Networks Using Regular Graphs

Internet of Things (IoT) is envisioned as a large collection of smart devices that are connected to the Internet and communicate with the goal of realizing a diverse range of applications. These smart devices range from typical home appliances to sophisticated industrial instruments. IoT has numerous applications, such as precision farming, health care, and smart cities. An issue that is prevalent in IoT networks is that due to limited resources, environmental factors, and malicious attacks, some nodes or links fail and adversely affect the functioning of IoT networks. Hence, robustness against the failure of nodes or links is a topic of considerable interest in the area of IoT networks. The robustness of a network is quantified using various spectral graph theoretic measures in network science. One such measure is network criticality which effectively quantifies the robustness against the failure of nodes or communication links. However, this measure can not be used to study the effect of different network parameters for large-scale IoT networks due to huge computational complexity of $O(n^{3})$ . In this work, we derive the explicit formulas of network criticality for IoT networks using $r$ -nearest neighbor graphs and show the effect of nearest neighbors and network size on robustness. Our theoretical expressions substantially reduce the computational complexity as compared to existing graph theory-based metrics. We observe that network robustness decreases with the network size and exponentially increases with nearest neighbors. Our work reduces the time complexity of network criticality evaluation from $O(n^{3})$ to $O(n)$ for static topologies and to $O(1)$ for switching topologies. Furthermore, we extend our study to random geometric graphs (RGGs) and real-world network data sets. Finally, we study the effect of asymmetric and dynamic topologies on robust IoT networks.