Revisting Random Key Pre distribution Schemes for Wireless Sensor Network By Joengmin Hwang and Yongdae Kim Computer Science and Engineering University of Minnesota Goal of Authors Re visit random graph theory and use giant component theory by Erdos and Renyi to show that even if the node degree is small most of the nodes in the network can be connected Evaluate relationship between connectivity memory size and security to show that they can reduce the amount of memory required or improve security by trading off a very small number of isolated nodes Outline Introduction Notation Background of Existing key pre distribution schemes based on random graph theory Evaluation of Giant component theory for key pre distribution scheme Utilizing sensor hardware to control transmission range Author s solution for efficient path key identification algorithm compared to existing schemes Notation d the expected degree of a node i e the expected number of secure links a node can establish during key set up k number of keys in a node s key ring n network size in nodes r communication radius n the expected number of neighbor nodes within communication radius of a given node p probability that 2 nodes share a key Pc probability that graph is connected B ratio of largest component size to network size P size of the key pool A area of the field w number of key spaces constructed in networks T number of key spaces carried by each nodes x number of nodes captured Key pre distribution in wireless sensor networks Eschenauer and Gligor EG In EG each node randomly picks a subset called a key ring of keys from a large key pool and any pair of nodes can establish a secure connection if they share at least one common key The three phases are 1 initialization 2 key set up and 3 Path key identification Chan Perrif and Song CPS Extends EG and developed 2 key pre distribution techniques q composite key pre distribution and a random pair wise keys scheme 1 q composite in this case requires any 2 nodes to share at least q common keys to establish a secure link 2 Random pair wise keys in this case uses pair wise scheme based on the observation that not all n 1 keys need to be stored in the node s key ring to have a connected random graph with high probability Du Deng Han and Varshney DDHV Combined basic scheme with Blom s scheme Allows that any pair of n 1 nodes finds a secret pair wise key between them with much smaller number of keys than the actual number of nodes The tradeoff is that unlike the n 1 pairwise key scheme Blom s scheme is not perfectly resilient against node capture In all of the above schemes it is not certain that two nodes can generate a pair wise key Instead they have only a guarantee with probability p that this will be possible To find p so that n nodes in the sensor network are connected they use a random graph theory Random Graph Theory and Key Pre distribution scheme Erdos and Renyi provided a theory how to determine p so that Pc is almost 1 i e the graph is almost surely connected This is called Global connectivity For a network to be connected with probability Pc p as determined by the key information key ring or pool size should be greater than p as obtained from Erdos and Reny s Theory P required is from Erdos and Reny s Theory d n P actual actual local connectivity is determined by key ring size and key pool size in EB by the key space in DDHV and by the number of pairwise keys stored in each node in CPS Theorem 1 P required d n Attempts to get entire graph connected n is the expected number of neighbors within the wireless communication range of a node D is the average number of nodes p n 1 EG Pactual 1 P k 2 DDHV Pactual 1 w t 2 P 2k P CPS Pactual m n Desirable Node Degree Desired node degree is discussed in the context of network connectivity network capacity and energy consumption by controlling transmission power The node degree is controlled by adjusting the transmission power Higher node degree requires higher transmission power which increases the energy consumption All we have to do is crank up the power right No With a high node degree the network connectivity increases but the interference between the neighboring nodes increases and therefore the network capacity decreases If the node degree is decreased the connectivity decreases which in the extreme case results in the network being disconnected The low degree reduces the communication interference but since the connectivity is poor the number of hops will be increased which will decrease the network capacity Not to mention power consumption issues Desired Node Degree CON T The optimal node degree to maximize the network capacity has been considered as a GUESSTIMATE in recent literature The exact constant remains as an open problem If each node is connected to less than 074 log n nearest neighbors then the network is asymptotically disconnected with probability 1 as n increases while if each node is connected to more than 5 1774 log n nearest neighbors then the network is asymptotically connected with probability approaching 1 as n increases It s 6 no it s 8 not it s 5 6 no it s New Theory A random graph G n p is a graph of n nodes for which the probability that a link exists between two nodes is p In a large sensor network with size n p denotes the probability that two neighboring nodes share a common key or key information Erdos and Renyi provided a theory how to determine p so that Pc is almost 1 i e the graph is almost surely connected as opposed to fully connected Required Local Connectivity Revisted Theorem 2 When node Degree is 6 B is Close to 1 When node Degree is 14 Pc approaches 1 This means that even with a very small node degree most Their Goal is to utilize the transmission power control feature to bridge the gap of the nodes are connected to each other Increasing the node degree between network transmission range and secure transmission range to make Pc very close to 1 causes only a small number of isolated nodes to be connected Revisiting Random Graph Theory to re evaluate pre distribution schemes Varies by k Theorem 1 P required d n Erdos Renyi Attempts to get whole graph connected Theorem 2 P required a n Erdos Renyi Attempts to get sufficiently large Giant component For EG where P size of key pool 100000 and n network size in nodes 10000 Theorem 1 To make P actual Prequired k 214 when Prequired 3664 Theorem 2 To make P actual larger than Prequired 0794 k 91 Comparison of this estimation for the