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 sub graph satisfies that each node has a path of length l to its l-th-hop neighbors. The end result is a sharp threshold p >= Cn^-(l-1)/| that satisfies this property and that can be considered as an application of the sparse Szemeredi's regularity lemma.
展开▼
