Research On Pairwise Key Establishment Algorithms In Sensor Networks

As one of newly-arisen networks, WSN will exert its immensurable effect on such applied fields as military affairs, environment, health care, home use and etc. Largely different from traditional networks, WSN has its own characteristics, including self-organized properties of networking, very limited energy resources, low abilities to resist physical attacks, and lack of feedback mechanisms for abnormal cases off-line. The key management issue of WSN has attracted much attention of researchers all along, as it is essential of WSN security architecture. Focusing on the establishment of pairwise key between any two nodes in a network, this thesis analyzes and presents algorithms of pairwise key establishment, for purpose of achieving nice performance on such metrics as scalability, deterministic key path, and resilience. It is summarized as follows.(1) The characteristics of WSN, such as networking properties, security goals, node's resources are analyzed synthetically, a multi-level security architecture of WSN is proposed, and performance metrics of key management are inspected.(2) It is known that nodes are pre-loaded definite key information before deployment, to ensure that nodes can establish pairwise key during deployment phase. Error-tolerant models in the field of parallel procession are adopted. As nodes are distributed randomly, those nodes that are not within each other's signal range may failed to establish pairwise key, even though they share a common key. That situation is modeled as "failed link" in a error-tolerant model. Weak connectivity in subsection of hypercube model is presented. Different from other weak connectivities, it has two advantages as follows. 1). It only deals with the case of failed links, while that of node failure is ignored. And the connected property is only issued by inspecting node's connectivity in a subcube. 2). That kind of connectivity can be described as a sequence identification and also can be distinguished by localized processions. That is, a specific identification is corresponding to a unique connected component, and a node can determine if it belongs to a component by information exchange in a very limited area.Focusing on the diversity of network topologies in practical deployment, a set of identifications on isomorphic connectivity in subsection is constructed. Compared with a single case of that kind of connectivity, it supports much more cases of connected relationships, making a further approach on connectivity modeling in practical situations. Moreover, a connectivity set based polymorphic network is described. With respect to the two neighboring (permuted or exchanged) identification, the interconnection issue of the corresponding components are analyzed theoretically, thus a comprehensive description on interconnection properties of a polymorphic network is completed. (3) Based on hypercube model, a series of node key pre-distribution model and corresponding algorithms on pairwise key establishment are proposed. Examples are expanded pre-distribution algorithm, k-dimensional weak connectivity in subsection based key establishment algorithm, and location-aware based key path establishment.Based on the basic hypercube pre-distributtion model, the first one improves t-subsection pre-distribution model with length of 3 in each subsection. It achieves much shorter key path for those two nodes with long hamming distance, and it has higher resilience. Based on theoretic anlysis on the weak connectivity in subsection, a leveled connection if defined, by utilizing m-storage units. A framework of pairwise key establishment based on a polymorphic network in weak connectivity is provided. Correspondingly, the algorithm based on k-dimensional weak connectivity in subsection is presented. The algorithm has nice performance such as localized procession, deterministic path establishment, and high local connectivity. Based on the assumption that it is reasonable to predetermine node's location to some degree in practical use, the third one distributes key information according to the node's expected area. Thus it achieves higher and more stable probability of direct key establishment, fairly low storage requirement of key pre-distribution, and nice performance on resilience.(4) Different from traditional networks, the essential concern in WSN research focuses on the performance of the whole network. Given the information of local connectivity of single nodes, the random graph model is an effective means to analyze geometry of network in macroscopic way. The issue of connectivity and boundary effect of the improved Bernoulli model are addressed, according to the requirement of direct key establishment. With respect to large scale of sensor networks, the feasibility and the effectiveness of flat random graph model are doubted, for analysis on the pairwise key issue in sensor networks. And hierarchical random graph model is firstly presented to the best of the author's knowledge. Also edge effect of that kind of model is addressed. Correspondingly, a framework of leveled pre-distribution model is provided. Figures show that it has nice scalability.(5) As an instance the framework of composite pre-distribution model, the key pre-distribution scheme of multi-finite field multi-key space is presented. In addition, security requirements on communications among high-level nodes are considered seriously, such as group or cluster headers. In order to make shorter the key path between those nodes, node's self-learning algorithm is proposed, enable those nodes to compute paiwise key with each other, by utilizing available key path information.(6) Due to the tradeoff of the requirements of performance metrics such as security, resilience and local connectivity, currently used schemes of key pre-distribution would make available a number of isolated components. In order to make schemes more effective, it is essential to find a new mechanism to construct key path between those components. Theoretic analysis on edge nodes of components is addressed. Trust model on multiple nodes is provided, performing authentication in a trust field by credible nodes. The protocol of key path establishment is constructed based on presented trust model. Compared with other kind of path establishment such as network decoupling, figures show that the proposed protocol has better resilience, and can achieve interconnection of components effectively.