Analysis of Multi-path Random Key Pre-distribution for Wireless Sensor Networks

Most wireless sensor networks require that every large enough node contain certain properties. By using the Szemeredi\´s regularity lemma, one can approximate a complex network by a much simpler object in such a way that the approximation is "regular" for most pairs of partitions of this network. After obtaining a more traceable network, we establish bounds for the probability of the property that a random key pre-distribution subgraph satisfies that each node has a path of length ℓ to its ℓ^th-hop neighbors. The end result is a sharp threshold p ≥ C_n^-(ℓ-1)/ℓ that satisfies this property and that can be considered as an application of the sparse Szemeredi\´s regularity lemma.