基于分層的傳感器網(wǎng)絡(luò)密鑰預(yù)分配方案*

周波清， 李素君， 羊四清

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

0 引 言

在軍事和商業(yè)的應(yīng)用中，傳感器網(wǎng)絡(luò)的安全問(wèn)題是必須解決的核心問(wèn)題之一[1]。近年來(lái)，相關(guān)學(xué)者提出了許多密鑰管理方案[2～12]。

Du W等人第一次將部署知識(shí)模型化[8]，基于這個(gè)部署模型提出了一個(gè)密鑰預(yù)分配方案。Zhou B等人將部署知識(shí)和密鑰鏈結(jié)合起來(lái)[9]，提高了文獻(xiàn)[8]所提方案的性能。Yu Z等人提出了一個(gè)新密鑰預(yù)分配方案[10],此方案將部署區(qū)域劃分成六邊形的單元格，與基于二維單元格的方案[8]相比，其性能有所提高。Fanian A等人將六邊形的部署知識(shí)進(jìn)行一步劃分，并使用主從密鑰機(jī)制為節(jié)點(diǎn)建立共享密鑰[11]，此方案具有完美地對(duì)抗節(jié)點(diǎn)俘獲的彈性性能，但是存儲(chǔ)開(kāi)銷隨著六邊形區(qū)域的增大而增加，新部署的節(jié)點(diǎn)很難與已部署在網(wǎng)絡(luò)中的節(jié)點(diǎn)建立共享密鑰。

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

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

1 對(duì)密鑰建立方案KPS-L

1.1 部署模型

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

1)整個(gè)網(wǎng)絡(luò)被劃分成正六邊形的網(wǎng)格，如圖1所示；

2)每個(gè)網(wǎng)格有一個(gè)部署點(diǎn)，在圖1中，部署點(diǎn)位于單元格的中心；

3)部署點(diǎn)相同的節(jié)點(diǎn)組織成群，群內(nèi)節(jié)點(diǎn)在網(wǎng)絡(luò)中的實(shí)際位置服從以部署點(diǎn)為中心的二維正態(tài)分布。

圖1 區(qū)域劃分圖(其中“●”代表部署點(diǎn))

1.2 密鑰管理模型

每個(gè)網(wǎng)格都是基本單元，基本單元的鄰居單元根據(jù)離基本單元的遠(yuǎn)近分層。

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

定義2 基本密鑰池:系統(tǒng)為基本單元格(r,c)產(chǎn)生大小為m的密鑰池BK(r,c)，網(wǎng)絡(luò)中的基本密鑰池都相互獨(dú)立。

1.3 密鑰預(yù)分配

部署點(diǎn)位于單元(r,c)的群中的節(jié)點(diǎn)預(yù)分配如下密鑰信息：

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

1.4 共享密鑰建立階段

節(jié)點(diǎn)部署好后，進(jìn)入共享密鑰建立階段。下面以節(jié)點(diǎn)a,b為例來(lái)講解對(duì)密鑰的建立過(guò)程。

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

共享密鑰建立成功之后，來(lái)自基本密鑰池的密鑰經(jīng)過(guò)Hash變換后的才存儲(chǔ)到節(jié)點(diǎn)中，即對(duì)于任何基本密鑰k，共享密鑰建立成功之后，節(jié)點(diǎn)a存儲(chǔ)如下密鑰：k′=H(k,IDa)。

1.5 路徑密鑰建立階段

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

2 性能分析與模擬

定義4 相鄰節(jié)點(diǎn)：如果節(jié)點(diǎn)a和b都在對(duì)方的通信范圍內(nèi)，則稱a和b為相鄰節(jié)點(diǎn)。

定義5 局部連通率(local connectivity)：網(wǎng)絡(luò)中任意兩相鄰節(jié)點(diǎn)能夠建立共享密鑰的概率。

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

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

2.1 節(jié)點(diǎn)能夠建立對(duì)密鑰的概率

節(jié)點(diǎn)a和b能夠建立對(duì)密鑰的概率與它們的部署位置有關(guān)。

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

(1)

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

(2)

如果a和b的部署點(diǎn)不同，且兩節(jié)點(diǎn)的部署點(diǎn)都超出了對(duì)方的聯(lián)系單元，則它們之間能夠建立共享密鑰的概率為0。

2.2 性能模擬

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

1)部署區(qū)域?yàn)?00 m×700 m；

2)部署區(qū)域被劃分成正六邊形的網(wǎng)格，正六形的邊長(zhǎng)為50 m，部署點(diǎn)位于正六邊形的中心；

3)節(jié)點(diǎn)被劃分成群，每群有40個(gè)節(jié)點(diǎn)，節(jié)點(diǎn)在網(wǎng)絡(luò)中的實(shí)際位置服從以部署點(diǎn)為中心，以σ為方差的二維正態(tài)分布；

4)最大的聯(lián)系層數(shù)L為2；

5)每個(gè)獨(dú)立密鑰池的大小m為600；

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

KPS-L方案的網(wǎng)絡(luò)模型、密鑰池的大小、每個(gè)節(jié)點(diǎn)預(yù)分配的密鑰數(shù)都與YG方案[10]相同。為了確保比較的公平性，在共享密鑰建立成功后，YG方案也對(duì)預(yù)分配的密鑰進(jìn)行了Hash處理。

從圖2中可以得出：兩方案的局部連通率隨著二維正態(tài)分布標(biāo)準(zhǔn)方差σ的增加而下降。但是YG方案下降得過(guò)快,如當(dāng)σ=110時(shí)，YG方案的局部連通率僅為52%，下降了31 %;而KPS-L方案的局部連通率為62%，僅下降了20 %,與YG方案相比，其局部連通率提高了18 %。

圖2 局部連通率對(duì)比示意圖

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

圖3 全局連通率對(duì)比示意圖

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

3 結(jié)束語(yǔ)

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

圖4 抗毀性對(duì)比示意圖

參考文獻(xiàn):

[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] 袁 珽,馬建慶,鐘亦平,等.基于時(shí)間部署的無(wú)線傳感器網(wǎng)絡(luò)密鑰管理方案[J].軟件學(xué)報(bào),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] 李素君,周波清,羊四清.傳感器網(wǎng)絡(luò)高效密鑰建立方案[J].計(jì)算機(jī)工程與應(yīng)用,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.