The best keying protocol for sensor networks

Abstract

Many sensor networks, especially mobile networks or those networks that are deployed to monitor crisis situations, are deployed in an arbitrary and unplanned fashion. Thus, any sensor in such a network may end up being adjacent to any other sensor in the network. To secure the communications between every two adjacent sensors in such a network, each sensor x in the network needs to store n − 1 symmetric keys that x shares with the other sensors, where n is the number of sensors in the network. This storage requirement of the keying protocol is rather severe, especially when n is large and the available storage in each sensor is modest. Earlier efforts to redesign this keying protocol and reduce the number of keys to be stored in each sensor have produced protocols that are vulnerable to collusion. In this paper, we present a collusion-proof keying protocol where each sensor needs to store (n+1)/2 keys, which is much less than the n−1 keys in the original keying protocol. We also show that in any collusion-proof keying protocol, each sensor needs to store at least (n−1)/2 keys.