Skip to main content

Technical Reports: CMU-CyLab-14-002

Title:Topological Properties of Wireless Sensor Networks Under the Q-Composite Key Predistribution Scheme With Unreliable Links
Authors:Jun Zhao, Osman Yagan and Virgil Gligor
Publication Date:January 24, 2014


The seminal q-composite key predistribution scheme [3] (IEEE S&P 2003) is used prevalently for secure communications in large-scale wireless sensor networks (WSNs). Ya˘gan [12] (IEEE IT 2012) and we [15] (IEEE ISIT 2013) explore topological properties of WSNs employing the q-composite scheme in the case of q = 1 with unreliable communication links modeled as independent on/off channels. However, it is challenging to derive results for general q under such on/off channel model. In this paper, we resolve such challenge and investigate topological properties related to node degree in WSNs operating under the q-composite scheme and the on/off channel model. Our results apply to general q, yet there has not been any work in the literature reporting the corresponding results even for q = 1, which are stronger than those about node degree in [12], [15]. Specifically, we show that the number of nodes with an arbitrary degree asymptotically converges to a Poisson distribution, present the asymptotic probability distribution for the minimum node degree of the network, and establish the asymptotically exact probability for the property that the minimum node degree is at least an arbitrary value. Numerical experiments confirm the validity our analytical findings.


[3] H. Chan, A. Perrig, and D. Song. Random key predistribution schemes for sensor networks. In Proc. of IEEE Symposium on Security and Privacy, May 2003.

[12] O. Ya˘gan. Performance of the Eschenauer-Gligor key distribution scheme under an on/off channel. IEEE Transactions on Information Theory, 58(6):3821–3835, June 2012

[15] J. Zhao, O. Ya˘gan, and V. Gligor. Secure k-connectivity in wireless sensor networks under an on/off channel model. In Proc. of IEEE ISIT, pages 2790–2794, 2013

Full Report: CMU-CyLab-14-002