Report

Secure connectivity of wireless sensor networks Ayalvadi Ganesh University of Bristol Joint work with Santhana Krishnan and D. Manjunath Problem statement • • • • N nodes uniformly distributed on unit square Pool of P cryptographic keys Each node is assigned K keys at random Two nodes can communicate if they are within distance r of each other and share a key Q: For what values of N, K, P and r is the communication graph fully connected? Background: Random key graphs Eschenauer and Gligor (2002): Key distribution scheme for wireless sensor networks Yagan and Makowski (2012): Analysis of the full visibility case Theorem: Suppose P=(N). Let K2/P = (log N+N)/N Then, P(connected) 1 if N + and P(connected) 0 if N Heuristic explanation • Probability of an edge between two nodes is approximately K2/P • Mean degree of a node is approximately NK2/P = log N + N • Edges are not independent but, if they were: – key graph would be an Erdos-Renyi random graph – has connectivity threshold at mean node degree of log N Background: Random geometric graphs • N nodes uniformly distributed on unit square • Edge probability g(x/rN) for node pairs at distance x from each other • Boolean model: g(x) = 1(x<1) Penrose: Let NrN2 = log N + N P(connected) 1 if N, and 0 if N Generalisations • Mao and Anderson: – Similar model but with Poisson process of nodes on infinite plane. – Same scaling of rN – Under suitable conditions on g, show a threshold between having isolated nodes in unit square, and no components of finite order in unit square Results for geometric key graphs • Mean node degree r2K2/P • If r2K2/P = log N + c, then P(graph is disconnected) > ec/4 • If r2K2/P = c log N and c>1, then P(graph is connected) 1 • Upper bound on connection probability • Graph is disconnected if there is an isolated node P(node j is isolated) (1r2K2/P)N exp( r2NK2/P) ec/N • Bonferroni inequality: P(there is an isolated node) ≥ i P(i is isolated) i<j P(i and j are isolated) Isolation of pairs of nodes Lower bound on connection probability • Approach for ER graphs – Compute probability that there is a connected component of m nodes isolated from other nm – Take union bound over all ways of choosing m nodes out of n, and over all m between 1 and n/2 Approach for geometric key graphs • Tesselate unit square with overlapping squares of side r/2 Approach for geometric key graphs • Are there disconnected components of different sizes in the unit square? • Are there “locally” disconnected components of different sizes within the small squares of side r/2, considering only nodes within that square? Big picture of proof • There are no small – size O(1) – components in the unit square disconnected from rest • There are no large – size > 6 – locally disconnected components in any small square • Can also bound the number of nodes in small components within a small square : very few of them • So how might the graph be disconnected? Notation • • • • • N: number of nodes in unit square r: communication radius of a node P: size of key pool K: number of keys assigned to each node n=r2N: expected number of nodes within communication range • p=K2/P: approximate probability that two nodes share a key Assumptions • N,K,P, K2/P0 • nK2/P c log N for some c>1 • K > 2 log N • Corollary: – Number of nodes in each small square is (log N) – concentrates near its mean value of n/(2) – uniformly over all squares Within a small square • n/(2) nodes, full visibility • Mean degree is nK2/(2P) = c/(2) log N • Even if edges were independent, expect to see local components of size up to 2, somewhere in the unit square Show there are no bigger components, taking edge dependence into account Within a small square • Say there is a connected component of size m isolated from the rest • Say these m nodes have mKj keys between them • Then – j ≥ m 1 – None of the other nm nodes in the square has one of these mKj keys Number of keys among m nodes • Assign K distinct keys to first node • Assign subsequent keys randomly with replacement • P(collision at (i+1)th step) i/P, independent of the past • P(j collisions) P(≥j collisions) ? Collision probability bounds • X1, X2, … , Xn independent Bernoulli random variables • Xi ~ Bern(pi) • Y = X1+…+Xn • Z is Poisson with the same mean as Y • Hoeffding (1956): Z dominates Y in the convex stochastic order Within the big square • Say nodes 1,2,…,m form a connected component isolated from the rest. Then – for some permutation of 1,2,…,m there is an edge between each node and the next – they hold mKj keys between them, for some j – there is no edge between the remaining Nm nodes and these m Putting the pieces together • Most nodes belong to a giant component • Each small square may contain some nodes that are locally isolated or within small components • These must either be connected to the giant component in a neighbouring cell, or to another small component • Latter is unlikely, doesn’t percolate