Hierarchical Hypercube Based Pairwise Key Establishment Scheme for Sensor Networks ()
Security schemes of pairwise key establishment, which enable sensors to communicate with each other securely, play a fundamental role in research on security issue in wireless sensor networks. A general framework for key predistribution is presented, based on the idea of KDC (Key Distribution Center) and polynomial pool schemes. By utilizing nice properties of H2 (Hierarchical Hypercube) model, a new security mechanism for key predistribution based on such model is also proposed. Furthermore, the working performance of tolerance resistance is seriously inspected in this paper. Theoretic analysis and experimental figures show that the algorithm addressed in this paper has better performance and provides higher possibilities for sensor to establish pairwise key, compared with previous related works.
1. Introduction
The security issue in wireless sensor networks has become research focus because of their tremendous application available in military as well as civilian areas. However, constrained conditions existent in such networks, such as hardware resources and energy consumption, have made security research more challenging compared with that in traditional networks.
Current research focus on such security schemes as authentication and key management issues, which are essential to provide basic secure service on sensor communications. Pairwise key establishment enables any two sensors to communicate secretly with each other. However, due to the characteristics of sensor nodes, it is not feasible to utilize traditional pairwise key establishment schemes.
Eeschnaure et al. [1] presented a probablitic key predistribution scheme for pairwise key establishment. This scheme picks a random pool (set) of keys S out of the total possible key space. For each node, m keys are randomly selected from the key pool S and stored into the node’s memory so that any two sensors have a certain probability of sharing at least one common key. Chan [2] presented two key predistribution techniques: q-composite key predistribution and random pairwise keys scheme. The q-composite scheme extended the performance provided by [1], which requires at least q predistributed keys any two sensor should share. The random scheme randomly pickes pair of sensors and assigns each pair a unique random keys. Liu et al. [3] developed the idea addressed in previous works and proposed a general framework of polynomial pool-based key predistribution. Based on such a framework, they presented random subset assignment and hypercube-based assignment for key predistribution.
However, it still requires further research on key predistribution because of deficiencies existent in those previous works. Since sensor networks may have dramatic varieties of network scale, the q-composite scheme would fail to secure communications as a small number of nodes are compromised. The random scheme may requires each sensor to store a large number of keys, which would be contradicted with hardware constraints of sensor nodes. The random subset assignment would not ensure any two nodes to establish a key path if they do not share a common key. Though the hypercubebased assignment can make sure that there actually exist a key path, however, the possibilities of direct pairwise key establishment are not perfect, leading to large communication overhead.
In order to improve possibilities of direct pairwise key establishment, and depress communication overhead on indirect key establishment, we propose a H2 (Hierarchical Hypercube) framework, combined with a new key predistribution scheme. Moreover two new fault tolerance model and corresponding indirect pairwise key establishment schemes are also proposed, by applying nice properties on tolerance resistance H2 model has provided. The schemes has better working performance on probabilities of pairwise key establishment between any two sensors.
2. Preliminaries
2.1. Notations and Definitions
Definition1(key predistribution): Cryptographic algorithms are pre-loaded in sensors before node deployment phase.
Definition2 (pairwise key): When any two nods share a common key denoted as E, we call that the two nodes share a pairwise key E.
Definition 3 (key path): Given two nodes A0 and Ak, which do not share a pairwise key, if there exists a path in sequence described as A0, A1, A2,……, Ak-1, Ak and any two nodes Ai, Aj (0≤i≤k-1,1≤j≤k) share at least one pairwise key, we call that path as a key path.
Definition 4 (n-dimensional hypercube interconnection network): n-dimensional hypercube interconnection network Hn (abbreviation as n-cube) is a kind of network topology that has the following characteristics: 1) It is consisted with 2n nodes and n·2n-1 links; 2) Each node can be coded with a different binary string with n bits such as b1b2…bn; 3) For any pair of nodes, there is a link between them if there is just one bit different between their corresponding binary strings.
Figure 1 illustrates the topology of a 4-dimensional hypercube interconnection network, which is consisted with 24=16 nodes and 4·24-1=32 links. And the nodes are coded from 0000 to 1111.