基于分層的傳感器網絡密鑰預分配方案*

周波清， 李素君， 羊四清

(1.中南大學 信息科學與工程學院，湖南 長沙 410083；2.湖南人文科技學院 信息科學與工程系，湖南 婁底 417000)

0 引 言

在軍事和商業的應用中，傳感器網絡的安全問題是必須解決的核心問題之一[1]。近年來，相關學者提出了許多密鑰管理方案[2～12]。

Du W等人第一次將部署知識模型化[8]，基于這個部署模型提出了一個密鑰預分配方案。Zhou B等人將部署知識和密鑰鏈結合起來[9]，提高了文獻[8]所提方案的性能。Yu Z等人提出了一個新密鑰預分配方案[10],此方案將部署區域劃分成六邊形的單元格，與基于二維單元格的方案[8]相比，其性能有所提高。Fanian A等人將六邊形的部署知識進行一步劃分，并使用主從密鑰機制為節點建立共享密鑰[11]，此方案具有完美地對抗節點俘獲的彈性性能，但是存儲開銷隨著六邊形區域的增大而增加，新部署的節點很難與已部署在網絡中的節點建立共享密鑰。

與不利用部署知識的密鑰管理方案[2～7]相比，利用部署知識的密鑰管理方案[8～11]具有如下優點：1)存儲開銷減少；2)局部連通率和抗節點俘獲的彈性性能顯著提高。但是這些方案沒有考慮部署誤差，隨著節點的實際位置與其期望位置之間誤差的增加，其局部連通率將顯著下降，最終導致全局部連通率的下降。

為了減輕因部署誤差而引起的方案性能的顯著下降，本文提出了一種基于分層的密鑰預分配方案(KPS-L)，并在此基礎上提出了一種密鑰預分配方案，此方案將整個部署區域劃分成六邊形的單元格，每個單元格都是基本單元，每個基本單元都有聯系單元，聯系單元根據離基本單元的遠近分層。基本單元使用獨立的基本密鑰池，然后基于分層和基本密鑰池創建基本單元的聯系密鑰池。部署點位于基本單元格的節點不僅要從本單元格的基本密鑰池中選取密鑰，還需從本單元的聯系密鑰池中選取一些密鑰，與文獻[10]相比，其局部連通率和全局連通率都有顯著提高。

1 對密鑰建立方案KPS-L

1.1 部署模型

與文獻[10]一樣，KPS-L方案使用基于群的部署模型，具體描述如下：

1)整個網絡被劃分成正六邊形的網格，如圖1所示；

2)每個網格有一個部署點，在圖1中，部署點位于單元格的中心；

3)部署點相同的節點組織成群，群內節點在網絡中的實際位置服從以部署點為中心的二維正態分布。

圖1 區域劃分圖(其中“●”代表部署點)

1.2 密鑰管理模型

每個網格都是基本單元，基本單元的鄰居單元根據離基本單元的遠近分層。

圖1例舉了以(3,2)為基本單元的2層聯系單元。其中深色的6個單元為(3,2)的第1層聯系單元；淺色的12個單元為(3,2)的第2層聯系單元。

定義2 基本密鑰池:系統為基本單元格(r,c)產生大小為m的密鑰池BK(r,c)，網絡中的基本密鑰池都相互獨立。

1.3 密鑰預分配

部署點位于單元(r,c)的群中的節點預分配如下密鑰信息：

1)從BK(r,c)中選取t0個密鑰,這部分密鑰稱為基本密鑰。

1.4 共享密鑰建立階段

節點部署好后，進入共享密鑰建立階段。下面以節點a,b為例來講解對密鑰的建立過程。

如果節點a和b的部署點相同，且它們之間存在如下y(y≤t0)個共同密鑰k1,…,ky，則它們之間的共享密鑰為kab=H(k1?…?ky,IDa?IDb)，其中,?為異或操作。

共享密鑰建立成功之后，來自基本密鑰池的密鑰經過Hash變換后的才存儲到節點中，即對于任何基本密鑰k，共享密鑰建立成功之后，節點a存儲如下密鑰：k′=H(k,IDa)。

1.5 路徑密鑰建立階段

本方案路徑密鑰可以使用文獻[8～11]中的方法建立，在此就不再詳細地介紹。

2 性能分析與模擬

定義4 相鄰節點：如果節點a和b都在對方的通信范圍內，則稱a和b為相鄰節點。

定義5 局部連通率(local connectivity)：網絡中任意兩相鄰節點能夠建立共享密鑰的概率。

定義6 全局連通率(global connectivity)：密鑰連通分量中的節點數與物理連通分量中的節點數之比。密鑰連通子圖是指圖中的節點通過相鄰節點建立的共享密鑰相互連通；物理連通分量是指圖中的節點通過相鄰節點相互連通。

定義7 抗毀性(resilience)：沒有被俘獲的相鄰節點之間建立的對密鑰被破譯的概率(在本文的模擬過程中，沒有考慮路徑密鑰被破譯的概率)。

2.1 節點能夠建立對密鑰的概率

節點a和b能夠建立對密鑰的概率與它們的部署位置有關。

如果a和b的部署點相同，則它們之間能夠建立共享密鑰的概率為

(1)

如果a和b的部署點不同，但兩節點的部署點都位于對方的第i(1≤i≤L)層聯系單元內，則它們之間能夠建立共享密鑰的概率為

(2)

如果a和b的部署點不同，且兩節點的部署點都超出了對方的聯系單元，則它們之間能夠建立共享密鑰的概率為0。

2.2 性能模擬

在本文的模擬中，KPS-L方案主要參數設置如下：

1)部署區域為700 m×700 m；

2)部署區域被劃分成正六邊形的網格，正六形的邊長為50 m，部署點位于正六邊形的中心；

3)節點被劃分成群，每群有40個節點，節點在網絡中的實際位置服從以部署點為中心，以σ為方差的二維正態分布；

4)最大的聯系層數L為2；

5)每個獨立密鑰池的大小m為600；

6)t0,t1和t2的值分別為40,60和60。

KPS-L方案的網絡模型、密鑰池的大小、每個節點預分配的密鑰數都與YG方案[10]相同。為了確保比較的公平性，在共享密鑰建立成功后，YG方案也對預分配的密鑰進行了Hash處理。

從圖2中可以得出：兩方案的局部連通率隨著二維正態分布標準方差σ的增加而下降。但是YG方案下降得過快,如當σ=110時，YG方案的局部連通率僅為52%，下降了31 %;而KPS-L方案的局部連通率為62%，僅下降了20 %,與YG方案相比，其局部連通率提高了18 %。

圖2 局部連通率對比示意圖

在YG方案中，部署點位于基本單元中的節點只能與部署點位于它的鄰居單元格中的節點建立共享密鑰。隨著部署誤差的增加，不僅導致局部連通率的顯著下降，而且也導致全局連通率的下降。如圖3所示，當σ=110時，YG方案的全局連通率為97.3%，也就是說，部署到網絡的1000個節點中，有23個節點由于不能與它周圍的鄰居節點建立共享密鑰而被浪費。但是，在相同的情況下，KPS-L方案僅浪費了4個節點。

圖3 全局連通率對比示意圖

圖4中的參數cc表示敵手在共享密鑰建立階段俘獲的節點數。從圖4可以得出，KPS-L方案和YG方案都具有很好的彈性性能。如，當cc=20時，KPS-L方案和YG方案兩方案中節點間建立的共享密鑰被破譯的概率分別約為0.7%和0.3%。Gu W等人在文獻[12]中提出了一個新的性能參數：抗毀局部連通率PRC=(1-PR)×PC，其中PR,PC分別表示抗毀性、局部連通率,此參數更具實際意義。一個方案如果能夠達到很高的局部連通率，但是節點間建立的安全鏈路基本被破譯，則這個方案也就失效了。當σ=110，cc=20時，KPS-L方案和YG方案的抗毀局部連通率分別為61.8%和52.6%。

3 結束語

針對利用部署知識的方案因部署誤差而引起的方案性能的顯著下降的問題，提出了一種基于分層的密鑰管理方案。與基本單元只與相鄰單元相聯系的方案(YG方案)相比，其局部連通率和全局部連通率都顯著提高。

圖4 抗毀性對比示意圖

參考文獻:

[1] Perrig A,Szewczyk R,Tygar J D,et al.SPINS:Security protocols for sensor networks[J].Wireless Networks,2002,8:521-534.

[2] Eschenauer L,Gligor V D.A key-management scheme for distri-buted sensor networks[C]∥Proc ACM CCS,Washington,DC,USA,2002:41-47.

[3] Chan H,Perrig A,Song D.Random key predistribution schemes for sensor networks[C]∥Proc IEEE S & P,Berkeley,USA,2003.

[4] Das A K.An efficient random key distribution scheme for large-scale distributed sensor networks[J].Security and Comm Networks,2011,4(2):162-180.

[5] 袁 珽,馬建慶,鐘亦平,等.基于時間部署的無線傳感器網絡密鑰管理方案[J].軟件學報,2010,21(3):516-527.

[6] Bechkit W.New key management schemes for resource constrain-ed wireless sensor networks[C]∥Proc IEEE WoWMoM,Lucca,Italy,2011.

[7] 李素君,周波清,羊四清.傳感器網絡高效密鑰建立方案[J].計算機工程與應用,2013,49(2):134-136.

[8] Du W,Deng J,Han Y S,et al.A key management scheme for wireless sensor networks using deployment knowledge[J].IEEE Trans on Dependable and Secure Computing,2006,3(1):62-77.

[9] Zhou B,Li S,Li Q,et al.An efficient and scalable pairwise key pre-distribution scheme for sensor networks using deployment knowledge[J].Computer Communications,2009,32(1):124-133.

[10] Yu Z,Guan Y.A key management scheme using deployment knowledge for wireless sensor networks[J].IEEE Trans on Para-llel and Distributed Systems,2008,19(10):1411-1425.

[11] Fanian A,Berenjkoub M,Saidi H,et al.A high performance and intrinsically secure key establishment protocol for wireless sensor networks[J].Computer Networks,2011,55:1849-1863.

[12] Gu W,Chellappan S,Bai X,et al.Scaling laws of key predistribution protocols in wireless sensor networks[J].IEEE Trans on Information Forensics and Security,2011,6(4):1370-1382.