Skip to main content

Robust Connectivity in the Presence of Insecure and Unreliable Links in Ad-Hoc Networks

Researchers: Virgil Gligor, Osman Yagan

Research Area: Next Generation Secure and Available Networks


This research project will focus on the connectivity and robustness properties of secure wireless ad-hoc networks by combining techniques from network science (e.g., graph theory), stochastic geometry, and probability theory. The main expected outcomes are practical design guidelines (in terms of network parameter choices) that can provably ensure the desired level of connectivity, security, and robustness in a network in the presence insecure and unreliable links. In particular, this research is motivated by the observation that current modeling techniques, which are predominantly based on random geometric graphs (RGGs), are insufficient to accurately model a real-world network. For instance, in an RGG nodes are placed in a Euclidian plane and two nodes are joined by a link if they are within a certain distance of each other. However, in wireless networks that utilize random key pre-distribution, two nodes that are close to each other in the RGG may not be able to communicate securely since they do not necessarily share a key. Furthermore, RGGs fail to model realistic wireless communication where links may also fail due to the presence of physical barriers between nodes or because of harsh environmental conditions severely impairing transmission.

A realistic model of robust wireless networks will have to address connectivity, security, and reliability of communication using intersection graphs, for example (1) the intersection of a RGG and a random key graph, to analyze the connectivity of secure wireless networks, and (2) the intersection of a RGG and an Erdös-Rényi graph, to analyze the connectivity in wireless ad-hoc networks where links are unreliable and may fail independently with a certain probability. Our research will investigate the properties of intersection graphs using advanced methods and tools of random graph theory and stochastic geometry, and will develop conditions on the network parameters (e.g., number of nodes, density of nodes in the deployed area, link failure probability, number of keys per node, key pool size), which will ensure that the resulting networks are k−connected with very high probability.