一種新的基于部署知識的WSN密鑰分配方案*

袁猷南，楊明慧，游 林(杭州電子科技大學通信與信息系統研究所，杭州310018)

無線傳感器網絡的安全通信中，節點密鑰建立極其重要。由于WSN節點計算能力、能量和存儲空間以及通信帶寬受限等問題，使得傳統的安全技術不能夠很好的應用在無線傳感器網絡中。目前普遍采用密鑰預分配技術進行密鑰分配，即在傳感器部署前由離線服務器將密鑰或產生密鑰的信息預先存儲在節點中。

文獻［1］中，Eschenauer和Gligor提出了基本的概率密鑰分配方案，在此基礎上出現了該方案的一系列改進［2－3］，文獻［2］要求節點間至少有 q 個共同密鑰才能建立對密鑰，抗俘獲能力有所改善，文獻［3］利用哈希函數不可逆性提高了E－G方案的抗毀性。文獻［4］提出了Blom方案，它具有安全門限等特點，只要被俘節點不超過這個安全閾值，則節點對捕獲免疫。文獻［5］把組合設計引入到無線傳感器網絡中，利用組合設計的不完全區組設計(Balanced Incomplete Block Design，BIBD)以及有限射影平面(FPP)構造節點密鑰，優點是網絡中任何兩個節點之間能夠直接建立對密鑰，降低了通信負荷，缺點是抗毀性差。文獻［6－10］提出了一種基于部署信息的密鑰方案，利用節點部署時同一區域內節點成為鄰居節點的概率高而不同區域內節點為鄰居節點的概率小的特點，網絡性能明顯改善。

為了改善網絡的本地連接概率和抗毀性能，本文在基于部署知識的基礎上，利用Blom矩陣、t次多項式和哈希鏈，提出了一個新的適合無線傳感器網絡密鑰分配方案——KD－DK。

1 背景介紹

1．1 節點部署模型

假設節點從高空投放后靜止不動，同一批次投放的節點容易落在一個區域，將該區域稱為Cell，則同一個Cell或相鄰Cell的節點之間成為鄰居節點的概率更高。設投放區域總面積為X×Y，X為長，Y為寬，將其劃分為M×T個Cell。常用的Cell有矩形或是正六邊形。設節點的發射半徑為R，則矩形所覆蓋面積為R2/8，正六邊形覆蓋面積可達3R2/26，約為矩形的1．598 8倍，因此本文采用正六邊形。圖1所示，每個Cell按＜i，j＞編號作為其 ID，其中1≤i≤M，1≤j≤T。設節點實際部署服從二維高斯分布，記節點 node∈Cell＜i，j＞為事件 A，則 A 的概率密度函數 f(A)滿足式(1)，其中 ＜xi，yi＞為Cell＜i，j＞的實際部署坐標，＜ x，y ＞ 為 node的實際部署坐標，σ為節點部署的標準方差。

圖1 節點的部署模型

圖2 網絡密鑰池的分配

1．2 Blom 矩陣

Blom矩陣利用素域GF(q)上形成的密鑰對生成矩陣A×G來定義節點間的密鑰對，其中q是能夠支持網絡節點數的最小的素數，G是一個(λ+1)×N的公共矩陣，N可認為是網絡節點數目，λ為網絡安全閾值，即只要網絡中被俘的節點數不大于λ，就不會對現有節點構成威脅。G通常由范德蒙矩陣生成，因此每個節點只需存儲每列的第二個元素就可以衍生出整個列，可以減少節點的存儲空間。

令A=(D×G)T，D為一個保密的隨機對稱矩陣，D=(λ+1)×(λ+1)，則 A×G對應一個N×N的對稱矩陣。若記Kmn為A×G中的第m行和第n列的值，則有:Kij=Kji。每個節點根據自己的編號i存儲矩陣A的第i行和矩陣G的第i列。當節點i和j要生成共享密鑰時，彼此交換自己所存儲的G的列，然后根據矩陣乘法計算各自的Kij和Kji，由于Kij=Kji，這樣節點i和j建立起了對密鑰。

1．3 二元對稱t多項式

1．4 哈希鏈

定義2 (哈希鏈)給定一個種子Seed和哈希函數H(X)(如SHA-1或MD5)，按照下面過程構造一系列哈希值:Vn=H(Seed)，Vi=H(Vi+1)，n為哈希鏈長度，1≤i≤n。

2 密鑰分配方案KD－DK

2．1 KD－DK密鑰池的構造

網絡部署之初，密鑰分發服務器(Key Distribution Sever，KDS)需要為每個節點分配一些密鑰信息，文中常用符號如表1所示。

為分析方便，考慮將鄰近的6個Cell劃分為3組:GP1、GP2和 GP3，如上圖1所示。其中。KDS 產生 3 個子密鑰池 S1、S2和 S3(互不重疊)分別分配給 GP1、GP2和 GP3，|Si|=SC，i=1，2，3。網絡中的每個節點分別從相鄰的三個組的密鑰池中選出m/3個密鑰，因此每個節點就保存了mR個密鑰。這樣網絡中不同Cell的節點間總能找來自同一個子密鑰池的元素。例如圖1所示，GP1、GP2和GP3共同的分別從S1、S2和S3選出m/3個密鑰。根據上述原理，可得圖1所示的網絡密鑰池的配置如圖2所示，其中節點中的數字表示密鑰池的序號。可以看出任意兩個相鄰Cell必定擁有一個共同的密鑰池。

表1 文中常用符號

2．2 KD－DK方案描述

KD－DK方案中，Cell內采用改進的Blom矩陣，Cell間采用改進的隨機密鑰方案以達到不同Cell間鄰節點建立直接對密鑰以保證良好的抗毀性。該方案基于以下假設前提:網絡節點部署開始很短的一段時間Tmin內沒有節點被敵方物理俘獲。該方案包含三個階段:①密鑰預分配;②密鑰對建立;③路徑密鑰建立。

2．2．1 密鑰預分配

根據密鑰池構造和密鑰分配原理，網絡中的每個節點預配置mR個密鑰，同時存儲同一個二元t次對稱多項式f(x，y)產生的份額f(u，y)，u為中節點自身ID。

2．2．2 密鑰對的建立

為保證節點安全通信，鄰節點間必須建立對密鑰。下面是鄰節點的對密鑰的建立過程:

(1)同一Cell內鄰節點間對密鑰建立

設 Cell＜i，j＞中節點 u 和 v分配的哈希值及下標如表2所示，對密鑰建立步驟如下:

Step1: u— ＞*: { u，hide＜ i，j，x＞} ，u 為node＜ i，j，u ＞的ID。

Step2: v— ＞*: { v，hide＜ i，j，y＞}，v 為node＜ i，j，v＞的ID。

Step3: 接收到來自v的廣播信息后，u 也接收到了節點v 的hide＜ i，j，y＞值。如果hide＜ i，j，y＞≤hide＜ i，j，x＞，節點u 計算V＜ i，j，y＞，V＜ i，j，y＞= Hx － y( V＜ i，j，x＞) ，x － y = hide＜ i，j，x＞－ hide＜ i，j，y＞，同時計算V＜ i，j，y＞°A＜ i，j ＞(u) 作為節點u 新的行向量A'(u); 如果hide＜ i，j，y＞＞hide＜ i，j，x＞，則V＜ i，j，x＞°A＜ i，j ＞(u) 作為節點u 新的行向量A'(u) 。最后由Blom 方案原理計算對密鑰K＜ i，j ＞(u，v) = A'( u)·G＜ i，j ＞(v) 。

Step4: 同理v 計算V＜ i，j，x＞，將V＜ i，j，x＞°A＜ i，j ＞( v) 作為節點v新的行向量。最后計算對密鑰)。

(2)鄰Cell鄰節點間對密鑰的建立

該過程與前一個過程同時進行，網絡節點部署后，按照隨機密鑰分配方案進行分配。設節點和，共同密鑰為，這時 u和 v計算 x值，按一定順序連接。u和v采用t次多項式xf(x，y)進行彼此密鑰的分配。得共享密鑰對為，有在計算出對密鑰后，所有節點包括同一Cell內的節點立即刪除所有存儲的隨機密鑰。

2．2．3 路徑密鑰建立

該方案中同一個Cell中的鄰節點總是能夠直接建立對密鑰的，因此路徑密鑰的建立主要指不同Cell間對密鑰的建立，可以采用普通路徑密鑰建立方法來建立本方案的路徑密鑰。

3 性能分析

3．1 本地連通概率分析

本地連接概率(Local Connectivity)是指任意兩個鄰節點建立直接對密鑰的概率，記為PLC，其中PLC=P(B(u，v)|A(u，v))，事件 A(u，v)表示 u，v是鄰節點，事件B(u，v)表示直接建立對密鑰。KDDK方案中能夠保證同一個Cell內的任意鄰節點建立直接對密鑰，則同一Cell內的本地連接概率為1。由于任意兩個不同Cell鄰節點擁有從同一個密鑰池中產生的 mR/3個密鑰，因此可以得出

本文將與基于蜂窩的 Beibei Kong方案［11］和q-composite進行比較，本地連接概率分析結果如圖3所示。Kong是Du［12］基礎上提出的一個正六邊形的基于部署知識的密鑰分配方案，且在本地連接概率方面優于Du方案。本文如不特別聲明默認網絡由10×10的cell組成，即M=10，T=10。當Sc=2 000，4 000，Kong方案中兩個相鄰蜂窩間密鑰池重疊因子 γ=0．125時，圖3中可以看出KD－DK方案的本地連通概率方面略低于Kong提出的方案(僅局限于初始存儲密鑰數mR相同的前提下)，但遠高于 q-composite方案。與 Kong和q-composite方案不同，本方案節點中存儲的隨機密鑰在建立對密鑰后被刪除，因此網絡初始化時存儲密鑰數mR對安全性和后面的存儲空間幾乎無影響，因而可以通過增加mR來提高節點本地連接概率。

假設節點在存儲了Blom矩陣及其相關的數據后剩余存儲空間為 C，設C=250，則可令 mR=C。當Sc=2 000，4 000時，KD－DK的本地連接概率分別可達到0．972 5和0．827 7。達到相同概率時Kong和q-composite方案各自需存儲的密鑰數mR如表3所示。雖然部署時Kong所需存儲的密鑰比KDDK小，但這耗盡了節點的大部分資源同時威脅到網絡安全，這將嚴重影響節點后期功能，在實際中幾乎不可能實現。而KD－DK中存儲的隨機密鑰在后期將被刪除，對安全性和存儲空間幾乎無影響，因此KD－DK可以實現Kong和q-composite方案不可能實現的更高的本地連接概率。

表3 Sc=2 000，4 000時，C=250時Kong和 q-composite所需存儲的密鑰數

圖3 本地連接概率分析

3．2 安全性分析

同一Cell哈希鏈的同一個哈希值分配給節點的個數不會超過λ，意味著同一個哈希值與矩陣A進行“°”運算產生同一個Blom矩陣的個數也不會超過λ個，說明同一Cell內節點間鏈路無法破解。而相鄰Cell鄰節點采用隨機密鑰的方案，由x=H(r1‖r2‖…‖rm)，可知，當相同的多項式 xf(x，y)個數超過t且被俘節點超過t個時，該多項式存在被攻破的可能。當且僅當超過t個節點共同含有相同的m個密鑰，且這些節點共同的密鑰數有且只有這m個密鑰時，才滿足上述被破解的前提條件。

定義3 概率p(i，k)p(i，k)表示有k個節點共同擁有且只擁有相同i個密鑰的概率。由分配過程可推導出式(2):

其中 i=1，2，…，mR/3，0≤k≤NC，NC為網絡節點數。當且僅當k≥(t+1)時安全鏈路才有可能破解。p(i，k)越小則網絡越難破解，網絡的安全性也就越高。圖4所示為SC=2000，mR=300p(i，k)的圖形。

圖 4 Sc=2 000，p(i，k)圖形

當 SC=2000，mR=300 時，對所有的 i，p(i，2)＜1e－5，因此圖4可以近似的認為 k＞3時，p(i，k)≈0，即有k個節點同時共享相同的i個且恰好只有共同的i個密鑰的概率幾乎為零，如圖4中網格部分所示。也就是說產生k＞3個由相同數目的密鑰產生而來的t次多項式的個數幾乎不可能;當0≤k＜2，0≤i≤10 時，如圖 4 斜面所示，p(i，k)在 i=5 時取得最大值，其中p(5，k)最大等于0．1847。但是網絡安全鏈路只有當k≤(t+1)時才有被破解的可能，而前面已指出時k＞3，p(i，k)≈0。通常t的值可以設的更大，一般的網絡只要t的不是太小(一般t＞20)，網絡幾乎不可攻破。

當 SC=2000，t=30，PLC分別為 0．33 和 0．5 時，KD－DK與Kong和q-composite的抗毀性能如圖5和圖6所示，其中Kong方案利用多項式在抗毀性上有改進［11］，為更清楚地表述，改進前后的方案分別用Kong1和Kong2標記。圖5和圖6中可以清楚地看到，KD－DK抗毀性明顯優于Kong和q-composite方案，在這兩種情況下節點被捕對鏈路安全性幾乎沒有影響。由圖可得鏈路安全優劣存在有以下關系:KD－DK＞Kong＞q-compostie。在 q-compostie方案中當被捕節點數小于一個臨界值時，q=2優于q=1時的方案;當被捕節點大于臨界值時安全性劣于q=1時的方案，其中PLC=0．33該臨界值約為700，PLC=0．5臨界值約為600。理由是當q=2時達到相同的本地連接概率節點需要存儲更多的密鑰，因此大量節點被捕時，容易將主密鑰池攻破。例如SC=2 000，PLC=0．33時，q-composite主密鑰池大小等于SC×M×N=2×105，當q=1時節點只需存儲約，282個密鑰，而q=2時需要存儲約483個密鑰，密鑰數量大幅增加，因而當捕獲大量節點時主密鑰池易攻破。

圖5 PLC=0．33鏈路安全分析

圖6 PLC=0．5鏈路安全分析

3．3 空間開銷

網絡部署前節點需存儲((λ+1)logq+1+mmR+(t+1)logp)bit密鑰，節點對密鑰建立后，由于節點刪除了相關的隨機密鑰，則只需存儲((λ+1)logq+1+(t+1)logp)bit密鑰，m為單個預分配密鑰的大小。這樣在節點在對密鑰建立后可以節約許多空間以存儲其他的一些信息。因此網絡可以通過調節mR以提高不同Cell鄰節點建立對密鑰的概率，而在后期又對節點的存儲空間不產生影響，有較好的靈活性。

4 總結及工作展望

無線傳感器網絡的安全問題當限制當前傳感器網絡發展和應用的一個重要因素。本文在基于部署知識的基礎上對Blom矩陣和隨機密鑰方案進行了改進，提出了一種新的密鑰分配方案。對該方案進行了詳細的闡述，并其性能進行了詳細的分析。通過與Kong和q-composite方案比較，該方案在本地連接概率和抗毀性方面有顯著改善。若節點在Tmin較小時有節點被捕獲，密鑰分配的安全性能仍需進一步研究。

［1］ Eschenauer L，Gligor V D．A Key-Management Scheme for Distributed Sensor Networks［C］//Proceedings of the 9th ACM Conference on Computer and Communications Security．ACM:Washington，DC，USA，2002:41 －47．

［2］ Chan H，Perrig A，Song D．Random Key Predistribution Schemes for Sensor Networks［C］//Proceedings of the 2003 IEEE Symposium on Security and Privacy．IEEE Computer Society，2003:197．

［3］ Tzu-Hsuan S，Chuan-Ming L．In Enhancing the Key Pre-distribution Scheme on Wireless Sensor Networks［C］//Asia-Pacific Services Computing Conference，2008．APSCC’08．IEEE，2008:1127－1131．

［4］ Du W，Deng J，Han Y S，et al．A Pairwise Key Pre-Distribution Scheme for Wireless Sensor Networks［C］//Proceedings of the 10th ACM Conference on Computer and Communications Security．Washington D．C，USA:ACM，2003:42 －51．

［5］ Camtepe S A，Yener B．Combinatorial Design of Key Distribution Mechanisms for Wireless Sensor Networks［J］．Networking，IEEE/ACM Transactions on，2007，15(2):346 －358．

［6］ Liu D，Ning P．Location-Based Pairwise Key Establishments for Static Sensor Networks［C］．//Proceedings of the 1st ACM Workshop on Security of Ad Hoc and Sensor Networks Fairfax，Virginia:ACM．2003:72 －82．

［7］ Taekyoung K，Jonghyup L，Jooseok S．Location-Based Pairwise Key Predistribution for Wireless Sensor Networks［J］．Wireless Communications，IEEE Transactions on，2009，8(11):5436 －5442．

［8］ Nguyen Xuan Q，Kumar V，Yunjung P，et al．A High Connectivity Pre-Distribution Key Management Scheme in Grid-Based Wireless Sensor Networks［C］//Convergence and Hybrid Information Technology，2008．ICHIT’08．International Conference on，2008:35 －42．

［9］ 彭保．無線傳感器網絡中利用部署知識的組合密鑰預分發算法設計［J］．傳感技術學報，2007，20(6):1376 －1380．

［10］姚宣霞．一種基于蜂窩模型的無線傳感器網絡密鑰分配方案［J］．傳感技術學報，2008，21(11):1923 －1928．

［11］ Beibei K，Hongyang C，Xiaohu T，et al．Key Pre-Distribution Schemes for Large-Scale Wireless Sensor Networks Using Hexagon Partition［C］．//Wireless Communications and Networking Conference(WCNC)，2010:1 －5．

［12］ Wenliang D，Jing D，Han Y．S，et al．In A Key Management Scheme for Wireless Sensor Networks Using Deployment Knowledge［C］//INFOCOM 2004．Twenty-third AnnualJoint Conference of the IEEE Computer and Communications Societies，2004:597．