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

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

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

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

1 背景介紹

1．1 節(jié)點部署模型

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

圖1 節(jié)點的部署模型

圖2 網(wǎng)絡密鑰池的分配

1．2 Blom 矩陣

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

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

1．3 二元對稱t多項式

1．4 哈希鏈

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

2 密鑰分配方案KD－DK

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

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

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

表1 文中常用符號

2．2 KD－DK方案描述

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

2．2．1 密鑰預分配

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

2．2．2 密鑰對的建立

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

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

設 Cell＜i，j＞中節(jié)點 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 也接收到了節(jié)點v 的hide＜ i，j，y＞值。如果hide＜ i，j，y＞≤hide＜ i，j，x＞，節(jié)點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) 作為節(jié)點u 新的行向量A'(u); 如果hide＜ i，j，y＞＞hide＜ i，j，x＞，則V＜ i，j，x＞°A＜ i，j ＞(u) 作為節(jié)點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) 作為節(jié)點v新的行向量。最后計算對密鑰)。

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

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

2．2．3 路徑密鑰建立

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

3 性能分析

3．1 本地連通概率分析

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

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

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

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

圖3 本地連接概率分析

3．2 安全性分析

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

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

其中 i=1，2，…，mR/3，0≤k≤NC，NC為網(wǎng)絡節(jié)點數(shù)。當且僅當k≥(t+1)時安全鏈路才有可能破解。p(i，k)越小則網(wǎng)絡越難破解，網(wǎng)絡的安全性也就越高。圖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個節(jié)點同時共享相同的i個且恰好只有共同的i個密鑰的概率幾乎為零，如圖4中網(wǎng)格部分所示。也就是說產(chǎn)生k＞3個由相同數(shù)目的密鑰產(chǎn)生而來的t次多項式的個數(shù)幾乎不可能;當0≤k＜2，0≤i≤10 時，如圖 4 斜面所示，p(i，k)在 i=5 時取得最大值，其中p(5，k)最大等于0．1847。但是網(wǎng)絡安全鏈路只有當k≤(t+1)時才有被破解的可能，而前面已指出時k＞3，p(i，k)≈0。通常t的值可以設的更大，一般的網(wǎng)絡只要t的不是太小(一般t＞20)，網(wǎng)絡幾乎不可攻破。

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

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

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

3．3 空間開銷

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

4 總結及工作展望

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

［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］ 彭保．無線傳感器網(wǎng)絡中利用部署知識的組合密鑰預分發(fā)算法設計［J］．傳感技術學報，2007，20(6):1376 －1380．

［10］姚宣霞．一種基于蜂窩模型的無線傳感器網(wǎng)絡密鑰分配方案［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．