Threshold behavior of multi‐path random key pre‐distribution for sparse wireless sensor networks

Wireless sensor network (WSN) has been an active research topic because its application encompasses various domains. In particular, a lot of attention have been paid to the common feature of WSN to show that every node in a large enough network contains certain properties. Real‐world applications of random key pre‐distribution naturally involve geometric and combinatorial techniques and are even more challenging technically. This paper presents an efficient scheme, which can approximate a complex network by a much simpler object such that the approximation is ‘regular’ between most pairs of partition of this network. Once a more traceable network is obtained, bounds for the probability of the property that a random key pre‐distribution subgraph satisfies that each node has a path of length $l$ to its $l\text{th}$ ‐hop neighbors are established. Then, by using the sparse version of Szemerédi’s regularity lemma and letting $C$ be a constant, $n$ the number of vertices, $p$ the probability of any two nodes sharing at least one common key, a sharp threshold $p=C{n}^{‐(l‐1)/l}$ that satisfies this property is shown. Moreover, computer simulations are also given to show the performance of the proposed scheme.