Toward <inline-formula> <tex-math notation="LaTeX">k </tex-math></inline-formula>-Connectivity of the Random Graph Induced by a Pairwise Key Predistribution Scheme With Unreliable Links

DOI10.1109/TIT.2015.2471295zbMATH Open1359.94632arXiv1405.5193MaRDI QIDQ2977136FDOQ2977136

Authors: Faruk Yavuz, Jun Zhao, Osman Yaǧan, Virgil Gligor

Publication date: 28 April 2017

Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)

Abstract: We study the secure and reliable connectivity of wireless sensor networks. Security is assumed to be ensured by the random pairwise key predistribution scheme of Chan, Perrig, and Song, and unreliable wireless links are represented by independent on/off channels. Modeling the network by an intersection of a random

K

-out graph and an ErdH{o}s-R'enyi graph, we present scaling conditions (on the number of nodes, the scheme parameter

K

, and the probability of a wireless channel being on) such that the resulting graph contains no nodes with degree less than

k

with high probability, when the number of nodes gets large. Results are given in the form of zero-one laws and are shown to improve the previous results by Yau{g}an and Makowski on the absence of isolated nodes (i.e., absence of nodes with degree zero). Via simulations, the established zero-one laws are shown to hold also for the property of

k

-connectivity; i.e., the property that graph remains connected despite the deletion of any

k - 1

nodes or edges.

Full work available at URL: https://arxiv.org/abs/1405.5193

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Cryptography (94A60)

Cited In (2)

This page was built for publication: Toward <inline-formula> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula>-Connectivity of the Random Graph Induced by a Pairwise Key Predistribution Scheme With Unreliable Links

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2977136)