We introduce a new random key predistribution scheme for securing heterogeneous wireless sensor networks. Each of the @math sensors in the network is classified into @math classes according to some probability distribution @math . Before deployment, a class- @math sensor is assigned @math cryptographic keys that are selected uniformly at random from a common pool of @math keys. Once deployed, a pair of sensors can communicate securely if and only if they have a key in common. We model the communication topology of this network by a newly defined inhomogeneous random key graph. We establish scaling conditions on the parameters @math and @math so that this graph: 1) has no isolated nodes and 2) is connected, both with high probability. The results are given in the form of zero-one laws with the number of sensors @math growing unboundedly large; critical scalings are identified and shown to coincide for both graph properties. Our results are shown to complement and improve those given by and for the same model, therein referred to as the general random intersection graph.
We now compare our results with those established in the literature. Our main argument is that previous results for the connectivity of inhomogeneous random key graphs are constrained to very narrow parameter ranges that are impractical for wireless sensor network applications. In particular, we will argue below that the result by @cite_16 is restricted to very large key ring sizes, rendering them impractical for resource-constrained sensor networks. On the other hand, the results by @cite_20 @cite_4 focus on fixed key ring sizes that do not grow with the network size @math . As a consequence, in order to ensure connectivity, their result requires a key pool size @math that is much smaller than typically prescribed for security and resiliency purposes.
@cite_16 @cite_4 @cite_20
2060271434 188357332
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. Graph concepts generally are usefulfor defining and detecting clusters. We consider basic properties of random intersection graphs generated by a random bipartite graph BG n, m on n+m vertices. In particular, we focus on the distr ibution of the number of isolated vertices, and on the distribution of the vertex degrees. These results are applied to study the asymptotic properties of such random intersection graphs for the special case that the distribution P (m) is degenerated. The application of this model to find clusters and to test their randomness especially for non-metric data is discussed.