A Survey of Key Pre-Distribution and Overlay Routing in Unstructured Wireless Networks


1 Department of Computer Science, Institute for Research in Fundamental Sciences, Tehran, Iran

2 Center for Pervasive Communications and Computing, University of California Irvine

3 Department of Computer Engineering, Sharif University of Technology, Tehran, Iran


Unstructured wireless networks such as mobile ad hoc networks and wireless sensor networks have been rapidly growing in the past decade. Security is known as a challenging issue in such networks in which there is no fixed infrastructure or central trusted authority. Further, node  limitations in processing power, storage, and energy consumption add further complexity to addressing security in such networks. While cryptography has proven as an effective solution capable of satisfying most network security requirements, it requires the use of efficient key pre-distribution algorithms compatible with the limitation of unstructured wireless networks. Typically, a key pre-distribution algorithm forms a cryptographic overlay layer above the network routing layer and as such introduces the need for relying on two layers of routing for secure delivery of information. In this paper, we conduct a categorical review of key pre-distribution methods for unstructured wireless networks. We also compare different key pre-distribution schemes in terms of performance and security strength. Finally, we provide an overview of recent overlay routing algorithms relying on key pre-distribution.