基于ｇｒｏｕｐ－ｂａｓｅｄ模型的無線傳感器網絡密鑰管理方案

摘 要：由于無線傳感器網絡受電源、計算能力、內存容量等方面的限制，傳統的基于公鑰和可信任的密鑰管理方式不再適用。為了進一步提高無線傳感器網絡的安全連通性，在分析DU Wen-liang等人的group-based節點投放模型的基礎上，提出了一種改進的密鑰管理方案：多密鑰空間與多路徑增強相結合的隨機密鑰預分配方案。結果分析表明，該方案需要較少的內存存儲空間，不僅提高了系統的連通性，還降低了節點的被捕獲概率。

關鍵詞：無線傳感器網絡；密鑰管理；隨機密鑰預分配；多路增強

中圖分類號：TP309文獻標志碼：A

文章編號：1001-3695(2009)06-2162-03

doi:10.3969/j.issn.1001-3695.2009.06.049

Key management scheme based on group-based mode for wireless sensor networks

LIU Hui-jing，LI La-yuan， WANG Guo-fang， LI Chun-lin

（Dept. of Computer Science Technology，Wuhan University of Technology， Wuhan 430063， China）

Abstract:Due to limitations of power， computation capability and storage resources ， the traditional trusted key management based on the public-key was not suitable for wireless sensor networks. To further enhance the security and connectivity for wireless sensor networks，proposed an improved key management scheme.Introduced the scheme，a random key predistribution using multiple key spaces and multipath key reinforcement was based on group-based deployment model which in the paper of DU Wen-liang.Analysis and simulations show that the scheme has lower memory and communication overheads， better ability against attacks besides good security performance.

Key words:wireless sensor networks; key management; random key predistribution; multipath key reinforcement

0 引言

無線傳感器網絡具有十分廣闊的應用前景。它已經成為世界許多國家的軍事部門、工業界和學術界關注的焦點。安全問題是無線傳感器網絡中的一個研究熱點。其中，密鑰管理是無線傳感器網絡中消息認證、加密解密等各種安全技術的基礎。由于無線傳感器網絡本身的特點^[1]：通信能力有限、電源不能得到補充、計算存儲能力非常受限等，非對稱密碼學的許多算法、基于公鑰的分配策略都不能很好地解決無線傳感器網絡的安全性、連通性以及優化通信等主要目標之間的矛盾。

目前研究者已經設計了多種密鑰管理方案^[2]，在Eschenauer等人提出的基本的隨機密鑰預分配方案（basic-scheme）中，先產生一個比較大的密鑰池，每個節點擁有密鑰池中的一部分密鑰，任意兩個節點將以一定概率共享至少一個公共密鑰。而DU Wen-liang等人提出的group-based 隨機密鑰預分配方案也是基于basic-scheme的。 DU Wen-liang機制比basic-scheme需要較少的存儲空間，具有更好的連通性^[3]。為了進一步提高無線傳感器網絡的安全連通性，本文提出了一種基于group-based隨機密鑰預分配的改進方案，在本方案中，采用DU Wen-liang等人提出的多密鑰空間機制與多路徑增強模型相結合，從而提高了無線傳感器網絡的連通性和安全性。

1 相關工作

1.1 Basic-scheme方案

Basic-scheme方案的主要思想是^[4]：在密鑰預分配階段，首先要產生一個擁有S個密鑰及密鑰標志符的池，然后從密鑰池中為每個節點隨機地選擇K個密鑰；接著由傳感器節點執行共享密鑰發現協議，為有公共密鑰的節點建立共享密鑰，即每個節點廣播其密鑰標志符列表，并將標志符列表與其密鑰鏈中密鑰標志符進行對比，以發現共享密鑰；最后為沒有共享密鑰的節點對建立共享路徑。

Basic-scheme方案雖然通過使用大的密鑰池，擴展性和可靠性得到了加強，但是一些無線鏈路可能沒有被分配密鑰，不能保證網絡的安全連通性。

1.2 Group-based節點投放機制

在DU Wen-liang等人提出group-based節點投放機制^[5]中，把節點進行分組，假設節點的投放在各個組內是相同的，并且一旦投放完畢，節點將不再移動。具體的模型描述如下：

a)把N個節點劃分成大小為t×n個大小的組，每個組用Gi， j來表示。其中i=1，…，t和j=1，…，n。b）Group-based 機制把節點投放在正方形區域內。注意在真實的場景中投放方式可以是多種多樣的，為了簡單起見采用正方形機制。

c)節點投放的過程，k是組Gi， j內的節點，則組Gi， j節點的PDF（probability density function）密度概率滿足:

fi， jk(x，y|k∈Gi， j)=f(x-xi，y-yj)

其中:f(x，y)=1/2πσ2e-(x2+y2)/2σ2，σ是正態分布標準偏離度。

Group-based節點投放中相鄰組密鑰共享情況如圖1所示。其中：垂直或者水平相鄰兩組之間的重疊因子為a，0≤a≤0.25;對角線上相鄰兩組之間的重疊因子為b，0≤b≤0.25。4a+4b=1，如果兩個組沒有相鄰，則它們之間沒有重疊的密鑰即它們的重疊因子為0。

該模型產生t×n個子密鑰空間，每個子密鑰空間用Si， j來表示，每個節點存放在若干個子密鑰空間中，節點間能直接建立全通道的充要條件是擁有相同的密鑰空間。網絡部署好后，節點首先和與它有相同密鑰空間的節點建立安全通道，只不過密鑰的選取過程不是從大的密鑰池中選取，同一組的密鑰從相對應的子密鑰空間中選取。沒有公共密鑰空間的鄰居節點，可以根據已經建立好的安全連通圖協商一對通信密鑰。通過對至少一個密鑰空間被破解的概率和x個節點被捕獲情況下其他通信信道被破解的分析，group-based節點投放模型在相同的存儲空間支持下，比Bloom的密鑰預分布模型節省資源，具有更好的連通性和抗節點捕獲能力，減少了對節點本身內存存儲和計算的要求。

2 多密鑰空間與多路徑增強模型結合的方案

2.1 密鑰池的劃分

本方案密鑰空間劃分為正三角形的形式，傳感器節點被分為t×n組，每組用Gi，j表示。其中i=1，…，t和j=1，…，n。具體密鑰空間的劃分如圖2所示。

本方案把整個密鑰池S分成t×n個子密鑰池，子密鑰池用Si，j來表示。正三邊形(如圖2加粗的那個)與它邊相鄰的子密鑰池之間的重疊因子均為a，它們之間共享a|SC|個密鑰，與對角線上的每組之間的重疊因子均為b，它們之間共享b|SC|個密鑰，不相鄰的子密鑰池之間沒有共享密鑰。其中|SC|為每組中密鑰的個數，并且3a+9b=1，0≤a≤1/3，0≤b≤1/9。下面描述了密鑰選取算法的詳細實現過程。在這個算法的實現過程中，每個子密鑰池Si，j都是從整個大的密鑰池S中選取密鑰。

1）對于組G1，1 從整個密鑰池S中取出|SC|個密鑰，并且令當前S的值設置為S-SC，即S1，1=|SC|，每次從大的密鑰池S中取完密鑰后，大密鑰池都要去除那些已經選取過的密鑰，所以S=S-SC。

2) 對組G1，j 當j=2，…，n時，S1，j=(a|SC|，Si，j-1)∪（(1-a)SC，S)，每組分配完密鑰之后，都執行S=S-(1-a)SC。

3）對組Gi，1 當i=2，…，t時，Si，1= (b|SC|，Si-1，1)∪（(1-b)SC，S)，每組分配完密鑰之后，都執行S=S（1-b）SC；對組Gi，2，當i=2，…，t時，Si，2= (a|SC|，Si-1，1)∪(a|SC|，Si，1)∪((1-2a)SC，S)，每組分配完密鑰之后，都執行S=S-(1-2a)SC。

4）對組Gi， j 當i=2，…， t，j=3，…，n-1時，j為奇數時Si， j=(b|SC|，Si-1，j-2)∪

(b|SC|，Si-1，j)∪(b|SC|，Si-1，j-1)∪(b|SC|，Si，j-2)∪(a|SC|，Si，j-1)∪((1-4b-a)SC，S)，每組分配完密鑰之后，都執行S=S-(1-4b-a)SC;當j為偶數時Si，j=(b|SC|，Si-1，j-3)∪(b|SC|，Si-1，j-2)∪(a|SC|，Si-1，j-1)∪(b|SC|，Si，j-2)∪

(b|SC|，Si，j-1)∪(1-3b-2a)SC，S)，每組分配完密鑰之后，都執行S=S-（1-2a-3b）SC。

5）對組Gi，n 當i=2，…，t時Si，n=(b|SC|，Si-1，j-2)∪(a|SC|，Si，j-1)∪(b|SC|，Si，j-2)∪(（1-2b-a)SC，S)，最后一個組分配完密鑰后S=S-(1-a-2b)SC。

2.2 確定子密鑰池|SC|的大小

下面就來確定子密鑰池|SC|的大小，由前面子密鑰池選取密鑰算法可知，每一組都從它上方、斜上方，左邊相鄰組中選取a|SC|或b|SC|個密鑰，其余的在大密鑰池|S|中選取。每一組選完后，大密鑰池都要去除那些已經選取過的密鑰。所以各個組從大密鑰池中選取的密鑰個數之和為

sum=1+(1-a)(n-1)+3(t-1)(1-b-a)+(t-1）(n-3)(2-3a-7b)/2」

所以，SC=|S|/tn-sum。

如果|S|＝100 000，t=n=10，a=b=0.083 33，則子密鑰池|SC|的大小約為2 548。

2.3 多路徑增強

本方案初始密鑰的建立過程大致與basic-scheme方案相同。其中的不同點是在密鑰預分配階段每個節點k（k∈Gi， j）從已經分配好的子密鑰池|Si， j|中選取m個密鑰作為該節點的密鑰環，并且保證任何兩個鄰居節點的密鑰環中有一個公共的密鑰。這樣為每個節點建立安全路徑。

建立好了安全路徑之后假設有足夠的路由信息可用，節點A知道所有到達B節點跳數小于h的不相交路徑。任何兩個節點之間都有公共密鑰，并設這樣的路徑存在j，且任何兩條之間不交叉。產生j個隨機數x1，…，xj，每個隨機數與加密解密密鑰有相同的長度。A將這j個隨機數通過j條路徑發送到B。B接收到這j個隨機數以后異或一下作為新的密鑰，即新的密鑰K′=Kx1…xj^[6]。

這種算法路徑越多則安全度越高，但路徑越長安全度越差。對于任何一條路徑，只要路徑中的任一節點被捕獲，整個路徑就等于被捕獲了。考慮到通信開銷與安全度之間的平衡，本文采用兩跳即h=2的多路徑增強，兩跳時它的性能達到最佳^[7]，任何一個路徑只有兩跳且不存在路徑交疊。

3 結果分析

3.1 局部連通性

通信連通性主要是指在無線通信環境下，各個節點與網絡之間的數據互通性。安全連通性主要指網絡建立在安全通道上的連通性。在通信連通的基礎上，節點之間進行安全初始化的建立，或者說各個節點根據預共享知識建立安全通道。如果建立的安全通道能夠把所有節點連接成一個網絡，則認為該網絡是安全連通的。每個分組內的連通性稱為局部連通性。

本文再把整個密鑰空間劃分為若干個子空間，這樣就把一個大的密鑰池劃分為若干個子密鑰池，節點在共享密鑰的發現階段縮小了選擇范圍，即減少了密鑰池S的數值，從而使得節點之間密鑰環m上具有相同密鑰的概率增加。由以下實驗結果（圖3）可知在m<170時本方案的局部連通性比基于group-based的節點投放機制有所提高，而比basic-scheme有了很大程度的提高。

3.2 全局連通性

盡管本方案具有較高的局部連通性，但是仍然不可能所有的節點都是連通的。因為有些節點分在不同的組中，組與組之間可能無法建立安全路徑。當節點和密鑰分布統一時，節點的全局連通性與basic-scheme是一樣的^[8]

Pglocal=1-Cm(|SC)|-m)/Cm|SC|

其中:Pglocal為全局連通性，SC為子密鑰池中的密鑰個數，m為每個節點密鑰環上的密鑰數。但是在實際應用中無論是節點的分配還是密鑰的分配都是不均勻的。由前人的研究結果可知，當m的值在130左右時全局連通性接近1。

3.3 節點的抗捕獲性

由于各個子密鑰池數目的減少提高了局部連通性，但是同時一個節點被捕獲時，整個系統被攻擊的概率也相應地增加了，但是本文在密鑰分配和建立的過程中采用多路徑增強模型，提高了系統的安全性能。

當密鑰池中的x個節點被捕獲時，全部節點被捕獲的概率為1-（1-m/S）x。其中S為整個密鑰池的總的密鑰數，m同上（每個節點密鑰環上的密鑰數）。由圖4的仿真結果可以看出，當被捕獲節點達到50個時，basic-scheme方案整個系統被捕獲的概率為0.072，DU Wen-liang的為0.034，而本方案則為0.019，可知本方案的節點被捕獲概率比其他兩種方案都低，安全性能也就相應地得到了很大的提高。

4 結束語

傳感器網絡與常規的Ad hoc 網絡相比具有無人管理，能量有限等特征，其安全機制有自身的特點，其密鑰分配和管理一直是研究的熱點問題之一。本文在group-based模型的基礎上，提出基于多密鑰空間多路徑增強的無線傳感器網絡密鑰預分配方案，并分析了本方案的局部連通性，節點抗捕性，其性能相比隨機密鑰預分配方案有一定提高。

本方案雖然提高了節點的局部連通性，節點的抗捕性。但是該模型的計算開銷比較大，并且本文沒有詳細分析節點的全局連通概率，這將是筆者在以后的學習中重點要考慮研究的問題。

參考文獻：

［1］孫利民，李建中，陳渝.無線傳感器網絡[M].北京：清華大學出版社，2005:179-217.

[2]蘇忠，林闖，封富均，等.無線傳感器網絡密鑰管理的方案和協議[J].軟件學報，2007，18（5）：1218-1231.

[3]CHEN Hui-fang，YING Bi-di，CHEN Bo.A low-energy key management protocol for wireless sensor networks[D].Hangzhou:Zhejiang University，2006.

[4]ESCHENAUERL，GLIGOR V.A key management scheme for distri-buted sensor networks[C]//Proc of the 9th ACM Conference on Computer and Communication Security.New York:ACM Press，2002：41-47.

[5]DU Wen-liang，DENG Jiang.A key management scheme for wireless sensor networks using deployment knowledge[C]//Proc of IEEE INFOCOM’04.2004：586-597.

[6]ANDERSON R，PERRIG A.Key infection:smart trust for smart dust[C]//Proc of the 12th IEEE International Network Protocols Confe-rence.[S.l.]:IEEE Press，2004:206-215.

[7]CHAN H，PERRIG A，SONG D. Random key predistribution schemes for sensor networks[C]//Procof 2003 IEEE Symposium on Security and Privacy.Washington DC:IEEE Computer Society， 2003：197-213.

[8]JOLLY G，KUSCU M C，KOKATE P，et al.A low-energy key management protocol for wireless sensor networks[C]//Proc of the 8th IEEE International Symposium on Computers and Communication.[S.l.]:IEEE Press，2003.