Some Properties Of Random Key Graphs

A wireless sensor network (WSN) is composed of a large number of tiny sensor nodes with transmitting and computing power, which are connected in a wireless way to construct an ad-hoc system. In WSN, sensor nodes are deployed in an untouched and even hostile environment, the nodes will be faced with a variety of attacks. Therefore, how to ensure the secure communications of WSN is an extremely important content in the research field. Among them, key management is the foundation to secure the network, the main purpose of which is to establish a shared key for sensor nodes to provide secure links for network security;Due to the limitation in computing power, storage space, energy and network bandwidth, the traditional key encryption schemes are not suitable for WSN. The Eschenauer-Gligor (E-G) key pre-distribution scheme is the first key distribution scheme for WSN in key management research field. The topological structure of the E-G key pre-distribution scheme is called random key graph. Although the properties of secure WSN employing the E-G key pre-distribution scheme, have been extensively studied in many researches, but most existing research unreal-istically assumes unconstrained sensor-to-sensor communications, and this is not suitable for the actual network.This thesis focuses on some properties of random key graph, especially the edge probability threshold for perfect matching in a random key graph. Moreover, we manage to obtain the edge probability threshold for the distribution of the number of isolated nodes and the connectivity in secure WSN under transmission constraints. The paper consists of five chapters.In chapter 1, the research background of random key graph and the primary results relating to the thesis are introduced.In chapter 2, we study perfect matching in random key graph and in random key bipartite graph. Firstly, according to the Hall theorem, we get the edge prob-ability threshold for perfect matching in a random key bipartite graph. And then using the moment method and constructional technique to get the edge probability threshold for the random key graph to have a perfect matching. We found that the edge probability thresholds for existing a perfect matching of random key graph and random key bipartite graph which meet that of random graph and random bipartite graph respectively.In chapter 3, by employing geometric probabilistic, coupling and the standard Poissonization technique, we obtain the asymptotic distribution of the number of isolated nodes in secure WSN under transmission constraints converges to a Poisson distribution. In such network, n sensor nodes are Poissonly or uniformly distributed over a unit square.In chapter 4, we study connectivity property in the intersection graph of ran-dom key graph and random geometric graph. We use a large number of small disks which coverage throughout the unit square to substitute for the two overlapping tessellations on the unit square introduced by B. S. Krishnan et at. in 2013, and improve the result for graph connectivity, we find that the intersection graph of random key graph and random geometric graph, the intersection graph of random graph and random geometric graph have the similar connectivity properties when they are matched through edge probability.In chapter 5, we study the distribution of the number of isolated nodes in the intersection graph of random intersection graph and random geometric graph. We use the Stein-Chen method to get the distribution of the number of isolated nodes in this graph which converges to a Poisson distribution.The main innovations of this thesis are as follows:1. Compared with the method introduced by M. Bloznelis et al., we use a different method to obtain the edge probability threshold for the random key graph to have a perfect matching.(1) Using probabilistic method to prove that there exists a giant component, with the exception of isolated nodes;(2) Constructing a matching which covers all but at most one of the noniso- lated vertices in the giant component.2. By employing geometric probabilistic, coupling and the standard Pois-sonization technique, we obtain the distribution of the number of isolated nodes in secure WSN under transmission constraints converges to a Poisson distribution.(1) Whether n sensor nodes are Poissonly or uniformly distributed over a unit square, the distribution of the number of isolated nodes in secure WSN under transmission constraints converges to a Poisson distribution. While the existing literatures only considered n sensor nodes Poissonly distributed on the unit disk.(2) Because the sensor nodes are distributed over a unit square, boundary effect must be considered in our analysis, and we get the vanishing small impact of the boundary effect on the number of isolated nodes.(3) By using Stein-Chen method, the standard Poissonization technique and coupling method to get the the distribution of the number of isolated nodes in secure WSN under transmission constraints.3. Compared with the method introduced by B. S. Krishnan et al, we study the zero-one law for connectivity in the intersection graph of random key graph and random geometric graph.(1) By using a large number of small disks which coverage throughout the unit square to substitute for the two overlapping tessellations on the unit square introduce by Krishnan et al. in 2013.(2) Improve the result about the zero-one law for connectivity in the intersec-tion graph of random key graph and random geometric graph.