OPTIMIZATION OF NODE AND LINK CONNECTIVITY FOR RESILIENCY IN WIRELESS MULTI-HOP NETWORKS

Abstract

Wireless Multi-hop networks are expected to become an integral part of the future mobile communications. These networks are highly scalable, self-organizing, dynamic, and share spectrum with others while operating in highly resource-constrained environments requiring a high degree of topological resiliency. The nodes comprising these networks are often mobile, lightweight and power constrained. As a result, these networks can be highly susceptible to node and link failure. A holistic view of the network constructing models with measurable metrics is required to not only properly quantify the resiliency, but also to provide insight as to how to improve the performance and resiliency. In this dissertation, we develop an analytical model that uniquely utilizes elements of graph theory and is well suited to analyze resiliency metrics. These models, corroborated by simulation, are then utilized to develop unique solutions that increase the link and node resilience of the network. Link resilience is measured using the graph theoretic concept of edge-connectivity, which quantifies the degree of resistance a network has to link failure. A traditional ad hoc network model where all nodes share a single channel and use some form of carrier sense multiple access technique is assumed. We also assume that other similar networks coexist both spatially as well as spectrally, and that nodes belonging to these other networks are interference sources. Channel interference across the network results in link degradation and eventually link removal, thus decreasing edge-connectivity. In order to make the network more resilient to link removal, we develop a novel channel allocation algorithm using the concept of graph coloring. To enable proper resource allocation based on observed interference, we propose a novel bivariate spectrum sensing approach, and develop a threshold metric based on the Kullback-Leibler divergence that can be scaled to support multivariate sensing. The spectral diversity introduced by this approach decreases the susceptibility of the network to link removal, thus maintaining a high level of edge-connectivity. Similarly, node resilience is measured using vertex-connectivity, which quantifies the resistance a network has to node failure. First, a random node removal model is analyzed and demonstrated, where a decrease in node density results in a decrease in the network’s vertex-connectivity. We then analyze how focused node removal, which prioritizes nodes to be removed (or attacked) based on their relative importance in the network, impacts the network’s vertex-connectivity. Specifically, we investigate the impact of eigenvector centrality and degree centrality-based node removal. We finally compare the resilience of networks under both focused and random node removal and discuss how vertex connectivity can be improved by managing the transmit power level based on the relative importance of the node in the network. Our results indicate that the proposed graph coloring-based spectrum allocation approach significantly increases link resilience by introducing spectral diversity based on spec- trum sensing. We also show that the node resilience problem can be addressed by selectively reducing the transmit power level of certain selected nodes. We conclude that combining our channel allocation algorithm along with node power control can significantly increase the resilience of a wireless ad hoc multi-hop network.