Zero-One Laws for Connectivity in Random Key Graphs

被引：68
作者：
Yagan, Osman [1 ,2 ]
Makowski, Armand M. [1 ,2 ]
机构：
[1] Univ Maryland, Dept Elect & Comp Engn, College Pk, MD 20742 USA
[2] Univ Maryland, Syst Res Inst, College Pk, MD 20742 USA
来源：
IEEE TRANSACTIONS ON INFORMATION THEORY | 2012年 / 58卷 / 05期
基金：
美国国家科学基金会;
关键词：
Graph connectivity; key predistribution; random key graphs; wireless sensor networks (WSNs); zero-one laws; SECURITY; DIAMETER;
D O I：
10.1109/TIT.2011.2181331
中图分类号：
TP [自动化技术、计算机技术];
学科分类号：
0812 ;
摘要：
The random key graph is a random graph naturally associated with the random key predistribution scheme introduced by Eschenauer and Gligor in the context of wireless sensor networks (WSNs). For this class of random graphs, we establish a new version of a conjectured zero-one law for graph connectivity as the number of nodes becomes unboundedly large. The results reported here complement and strengthen recent work on this conjecture by Blackburn and Gerke. In particular, the results are given under conditions which are more realistic for applications to WSNs.
引用
收藏
页码：2983 / 2999
页数：17
相关论文
共 27 条
[1]  
[Anonymous], 2001, CAMBRIDGE STUDIES AD
[2]  
[Anonymous], 2010, LONDON MATH SOC LECT
[3]   Connectivity of the uniform random intersection graph [J].
Blackburn, Simon R. ;
Gerke, Stefanie .
DISCRETE MATHEMATICS, 2009, 309 (16) :5130-5140
[4]  
Cayley Arthur, 1889, Q. J. Pure Appl. Math., V23, P376
[5]   The diameter of sparse random graphs [J].
Chung, F ;
Lu, LY .
ADVANCES IN APPLIED MATHEMATICS, 2001, 26 (04) :257-279
[6]  
Di Pietro R., 2006, P 2 IEEE CREATENET I
[7]   Redoubtable sensor networks [J].
Di Pietro, Roberto ;
Mancini, Luigi V. ;
Mei, Alessandro ;
Panconesi, Alessandro ;
Radhakrishnan, Jaikumar .
ACM TRANSACTIONS ON INFORMATION AND SYSTEM SECURITY, 2008, 11 (03)
[8]  
Eschenauer L., 2002, ACM CCS2002, DOI DOI 10.1145/586110.586117
[9]  
Godehardt E, 2003, STUD CLASS DATA ANAL, P67
[10]   Random intersection graphs and classification [J].
Godehardt, Erhard ;
Jaworski, Jerzy ;
Rybarczyk, Katarzyna .
ADVANCES IN DATA ANALYSIS, 2007, :67-+
123