Threshold Functions for Embedding Secure Paths into Random Key Pre-Distribution Based Wireless Sensor Networks

Abstract

Many random key pre-distribution based schemes have been developed to enhance security. Most of these schemes need to guarantee the existence of specific properties, such as disjoint secure paths or disjoint secure cliques, to achieve a secure cooperation among nodes. Which conditions ensure that large-scale sensor networks have a certain structure? The most well-known solutions of this kind of problems are probably Szemerédi's regularity lemma for embedding and perfect matching. The Szemerédi's Embedding lemma allows one to embed a small graph H into an underlying graph, when a network is sufficiently large. Perfect matching is generalized by perfect H-packing, which covers G by disjoint copies of a small graph H instead of covering all vertices of G with disjoint edges. However, analyzing such a structure or combinatorial problem is complicated in classical wireless network models such as percolation theories or random geometric graphs. Particularly, proof of results in geometric setting models often blend stochastic geometric and combinatorial techniques and is more technically challenging. To overcome this problem, our objective is to use an approximate quasi-random graph in order to eliminate some properties that are difficult to handle.
In this work, we analyzes the question of the threshold probability function for the property that ”every pair of vertices lies in a secure path” with respect to a security parameter p. In other words, the goal is to obtain a threshold function p0 (n), such that if given p＜＜p0 (n) then the probability that a security subgraph has above property is close to 1 and if p is slightly small then p0, then this probability is close to 0. To be more precise, we first obtain a ε-regular partition of the sensor network by using the Szemerédi regularity lemma. Then, cover each pair of nodes that is regular by a secure path P of length . Finally, a threshold can be obtained for almost pair of nodes (regularity nodes), and then one can match remaining irregular pairs using an appropriate control for those irregular nodes. Nevertheless, the main difference is that in a random graph the dependence/disjointness of certain events comes naturally, whereas in an ε-regular graphs, one needs to work on it. We show that in almost all security graphs the number of secure paths of length ℓ is close to its expectation provided ε is sufficiently small, p＞＞n(ℓ -1)/(ℓ+o(1), and n is sufficiently large.