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

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 Szemeredi's regularity lemma for embedding and perfect matching The Szemeredi'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 p(0)(n), such that if given p << p(0)(n) then the probability that a security subgraph has above property is close to 1 and if p is slightly small then P-0, then this probability is close to 0 To be more precise, we first obtain a epsilon-regular partition of the sensor network by using the Szemeredi regularity lemma Then, cover each pair of nodes that is regular by a secure path P-l of length l 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 epsilon-regular graphs, one needs to work on it We show that in almost all security graphs the number of secure paths of length l is close to its expectation provided e is sufficiently small, p >> n((l 1)/l+o(1)) and n is sufficiently large