We consider the network reliability problem in wireless sensor networks secured by the heterogeneous random key predistribution scheme. This scheme generalizes Eschenauer-Gligor scheme by considering the cases when the network comprises sensor nodes with varying level of resources; e.g., regular nodes vs. cluster heads. The scheme induces the inhomogeneous random key graph, denoted @math . We analyze the reliability of @math against random link failures. Namely, we consider @math formed by deleting each edge of @math independently with probability @math , and study the probability that the resulting graph i) has no isolated node; and ii) is connected. We present scaling conditions on @math , @math , and @math such that both events take place with probability zero or one, respectively, as the number of nodes gets large. We present numerical results to support these in the finite-node regime.
@cite_13: Random intersection graphs have received much attention for nearly two decades, and currently have a wide range of applications ranging from key predistribution in wireless sensor networks to modeling social networks. In this paper, we investigate the strengths of connectivity and robustness in a general random intersection graph model. Specifically, we establish sharp asymptotic zero-one laws for k-connectivity and k-robustness, as well as the asymptotically exact probability of k-connectivity, for any positive integer k. The k-connectivity property quantifies how resilient is the connectivity of a graph against node or edge failures. On the other hand, k-robustness measures the effectiveness of local diffusion strategies (that do not use global graph topology information) in spreading information over the graph in the presence of misbehaving nodes. In addition to presenting the results under the general random intersection graph model, we consider two special cases of the general model, a binomial random intersection graph and a uniform random intersection graph, which both have numerous applications as well. For these two specialized graphs, our results on asymptotically exact probabilities of k-connectivity and asymptotic zero-one laws for k-robustness are also novel in the literature.
Another notable work that is related to ours is by @cite_13 , who studied the @math -connectivity and @math -robustness in the inhomogeneous random key graph. A graph is said to be @math -connected if it remains connected after removal (i.e., ) of any @math nodes. Thus, the results obtained in @cite_13 ensure the reliability of the network against the failure of any @math nodes, for some integer constant @math . Since @math -vertex-connectivity implies @math -edge-connectivity, the network is ensured to be reliable against the failure of at least @math edges, for some integer constant @math . Our work complements these results by considering the case when edge fails with probability @math , so that the total number of failed links is possibly infinite; e.g., as many as @math links may fail.