20130816133014151

Secure connectivity of wireless
sensor networks
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) > ec/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)  (1r2K2/P)N
 exp( r2NK2/P)  ec/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 nm
– 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/P0
• 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/(2P) = 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 mKj keys between
them
• Then
– j ≥ m 1
– None of the other nm nodes in the square has
one of these mKj 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 mKj keys between them, for some j
– there is no edge between the remaining Nm
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