王小康，李佩玥，隋永新，楊懷江

（1.中國科學(xué)院 長春光學(xué)精密機械與物理研究所 應(yīng)用光學(xué)國家重點實驗室，吉林 長春130033；2.中國科學(xué)院大學(xué)，北京100049）

0 引 言

近年來，無線傳感器網(wǎng)絡(luò)［1］（WSN）在各領(lǐng)域都發(fā)揮著日益重要的作用，有效的密鑰管理［2］機制是WSN 進(jìn)行安全通信的基礎(chǔ)，因此密鑰管理的研究對于WSN 的實際應(yīng)用有著重要意義。

自Eschenauer和Glogor提出基于概率的E－G 方案［3］以來，許多類似的密鑰管理方案如q－composite［4］、多密鑰空間［5］、對稱多項式［6］、組合設(shè)計理論［7］等方案相繼被 提出。網(wǎng)絡(luò)的連通性和安全性［8］是評定WSN 密鑰管理方案的性能的兩個主要標(biāo)準(zhǔn)。但是上述方案抵御敵手俘獲節(jié)點攻擊的能力并不強，例如對于Du等人的多密鑰空間方案，當(dāng)400個節(jié)點被捕獲時，網(wǎng)絡(luò)中受影響鏈路數(shù)達(dá)到100% （m＝200，w＝7，t＝2）；在Chan 等人的q－composite方案中，150個節(jié)點被俘獲后 （q＝1），網(wǎng)絡(luò)受影響的鏈路就達(dá)到25%。為提高WSN 密鑰分配方案的性能，Du等人將網(wǎng)格部署理論［9］應(yīng)用到WSN 的密鑰管理中，Du將網(wǎng)絡(luò)劃分為一系列的正方形網(wǎng)格，利用相鄰分組間的密鑰重疊因子［10］構(gòu)建網(wǎng)絡(luò)的連通性。Yu和Guan［11］改進(jìn)了Du的方案，利用正六邊形網(wǎng)格分組［12］增強了節(jié)點抵御攻擊的能力。但這些方案抵御敵手選擇性攻擊的能力并不強，在Yu和Guan方案中，b＝3，w＝3時，敵手選擇性的攻擊某一網(wǎng)格，一旦俘獲節(jié)點數(shù)目超過門限值，鄰近的26 個網(wǎng)格密鑰都會被攻陷。

為進(jìn)一步改善WSN 的安全性能，本文利用網(wǎng)格部署理論將網(wǎng)絡(luò)區(qū)域劃分為兩種類型的六邊形網(wǎng)格，分組網(wǎng)格和密鑰網(wǎng)格。每個分組網(wǎng)格中的節(jié)點利用多密鑰空間方案建立密鑰，而相同密鑰網(wǎng)格中的節(jié)點則利用組合設(shè)計理論建立通信密鑰。依據(jù)節(jié)點通信范圍確定網(wǎng)格規(guī)模，使得只有相鄰分組中的節(jié)點才能有效通信。模擬分析結(jié)果表明，相較于其它密鑰管理方案，本方案的安全性更高。

1 相關(guān)方案回顧

1.1 多密鑰空間方案

Du等人在E－G 和Blom 密鑰分配的基礎(chǔ)上提出了一種在WSN 中建立成對密鑰的方案。在Blom 方案中，基站首先創(chuàng)建一個有限域GF （q）上的（λ＋1）×N 階的矩陣G，其中N 是網(wǎng)絡(luò)節(jié)點數(shù)目。接著，基站創(chuàng)建一個有限域GF（q）上的（λ＋1）×（λ＋1）階對稱矩陣D，并計算A＝（D×G）T。矩陣G 對全節(jié)點公開，其任意λ 列線性無關(guān)，矩陣D 則對各節(jié)點保密。由于D 是對稱矩陣，K ＝A＊G 也是對稱矩陣，選取Kij＝Kji作為節(jié)點i和j之間的通信密鑰?？梢酝ㄟ^如下操作實現(xiàn)該方案，對于節(jié)點k：①存儲矩陣A的第k行；②存儲矩陣G 的第k列。Blom 證明在不超過λ個節(jié)點被俘獲時，攻擊者無法恢復(fù)出矩陣D，網(wǎng)絡(luò)密鑰是安全的，一旦被俘獲的節(jié)點數(shù)目超過λ，網(wǎng)絡(luò)的安全性就會崩潰。為提高網(wǎng)絡(luò)抗攻擊的能力，Du，Deng 等人結(jié)合E－G 方案與Blom 方案，提出多密鑰空間密鑰預(yù)分配方案：每個節(jié)點從ω個對稱矩陣中隨機選擇t個，兩個節(jié)點如果共享對稱矩陣D 則可以建立彼此間的密鑰。與Blom 方案和E－G 方案相比，Du等人的方案抵御敵手俘獲節(jié)點攻擊的能力明顯增強。

1.2 組合設(shè)計理論

Camtepe等人將組合設(shè)計理論應(yīng)用于WSN 密鑰預(yù)分配方案：假定網(wǎng)絡(luò)的節(jié)點總數(shù)為N，用q 階有限投影空間（finite projective plane）生成一個對稱BIBD（q2＋q＋1，q＋1，1），其中q是滿足q2＋q＋1≥N 的素數(shù)。在該設(shè)計中，網(wǎng)絡(luò)共生成q2＋q＋1個密鑰，每個節(jié)點擁有q＋1個密鑰，其中任意兩個節(jié)點共享一個密鑰。在基于組合論的BIBD 方案中，網(wǎng)絡(luò)的連通率為1。

1.3 基于節(jié)點部署理論的方案

Du等人將節(jié)點部署理論應(yīng)用到密鑰預(yù)分配中，將節(jié)點部署區(qū)域劃分為一系列的網(wǎng)格，同一網(wǎng)格內(nèi)的節(jié)點間，以及鄰近網(wǎng)格內(nèi)的節(jié)點間將以很大概率共享密鑰，而相距較遠(yuǎn)的網(wǎng)格內(nèi)的節(jié)點間共享密鑰的概率很低。該方案不僅大幅度提高了網(wǎng)絡(luò)的連通性，還有效地增強了無線傳感器網(wǎng)絡(luò)抵御敵手攻擊的能力。

2 本文方案

本文以Liu等人的分組密鑰預(yù)分配方案為基礎(chǔ)上，結(jié)合多密鑰空間方案和組合設(shè)計理論，提出一種新的基于正六邊形部署的密鑰管理方案。與Du等人的重疊因子方案不同，本文提出的方案將目標(biāo)區(qū)域劃分為兩種網(wǎng)格，密鑰網(wǎng)格和群組網(wǎng)格。如圖1所示，每一個小六邊形網(wǎng)格代表密鑰網(wǎng)格，陰影區(qū)域的大六邊形網(wǎng)格代表群組網(wǎng)格；每個群組網(wǎng)格包含一個完整的密鑰網(wǎng)格和6 個 “半－密鑰網(wǎng)格”，相鄰的群組網(wǎng)格均分一個密鑰網(wǎng)格。每個密鑰網(wǎng)格和群組網(wǎng)格都有唯一的標(biāo)識符。群組網(wǎng)格邊長的選擇依賴于節(jié)點的通信半徑，假定群組網(wǎng)格邊長為l，節(jié)點通信半徑為r，為確保只有相鄰群組網(wǎng)格內(nèi)的節(jié)點才能進(jìn)行通信，必須滿足l≥2r。每個群組網(wǎng)格和密鑰網(wǎng)格都擁有自己的密鑰池，不同網(wǎng)格之間的密鑰池交集為空集。每個密鑰網(wǎng)格利用組合設(shè)計理論BIBD（q2＋q＋1，q＋1，1）構(gòu)建自身的密鑰池，每個群組網(wǎng)格內(nèi)的節(jié)點利用多密鑰空間方案建立通信密鑰。

圖1 群組網(wǎng)格與密鑰網(wǎng)格的劃分

2.1 密鑰預(yù)分配

假定目標(biāo)區(qū)域被劃分為m 個群組網(wǎng)格，則有4m 個密鑰網(wǎng)格。節(jié)點在每個密鑰網(wǎng)格內(nèi)均勻分布，每個密鑰網(wǎng)格內(nèi)有Nc個節(jié)點。用二維參量（i，j）（i＝1，2…4 m，j＝1，2…，m）來唯一地表征一個網(wǎng)格區(qū)域，其中i代表所屬密鑰網(wǎng)格的標(biāo)志號，j代表所屬群組網(wǎng)格的標(biāo)志號。具體步驟如下：

（1）基站生成4 m 個BIBD（q2＋q＋1，q＋1，1）密鑰池，分別定義標(biāo)識符k（k＝1，2，…，4 m）。每個密鑰池包含q2＋q＋1個密鑰，組合成q2＋q＋1組，每組包含q＋1個密鑰且任意兩組共享一個密鑰，其中q是滿足q2＋q＋1≥Nc的最小素數(shù)。

（2）基站生成有限域GF（q）上的（λ＋1）×Nm（Nm≥4 Nc）階的矩陣G，G 的任意λ 列線性無關(guān)。

（3）基站生成m 組對稱矩陣，每組包含w 個Nm階對稱矩陣D1，D2，…，Dw，并分別計算Ai＝（Di×G）T。矩陣G 對網(wǎng)絡(luò)公開，矩陣Di對各節(jié)點保密。

（4）將所有節(jié)點 （假定總數(shù)為N）劃分為4m 組，每組賦予標(biāo)識符l（l＝1，2…，4 m）。選取密鑰池l的q2＋q＋1組密鑰中的Nc組分別賦予每個節(jié)點。

（5）基站從第j（j＝1，2…，m）組對稱矩陣組生成的矩陣A1，A2，…，Aw中隨機選取t個，并將矩陣Ai的第k行賦予群組網(wǎng)格j中標(biāo)識符為k（k＝1，2，…，4 Nc）的節(jié)點。

2.2 共享密鑰的發(fā)現(xiàn)

每個節(jié)點用一個三維向量（i，j，k）（i＝1，2…4 m，j＝1，2…，m，k＝1，2，…，4 Nc）來唯一地表征。其中，i代表節(jié)點所處的密鑰網(wǎng)格標(biāo)志號，j代表節(jié)點所處的群組網(wǎng)格標(biāo)志號，k代表在群組網(wǎng)格中節(jié)點的ID。部署完成后，每個節(jié)點廣播其三維序列號（i，j，k），同時接收鄰居節(jié)點廣播的序列號。假定節(jié)點A（i1，j1，k1）與節(jié)點B（i2，j2，k2）是鄰居節(jié)點，A，B之間的密鑰建立分為如下情形：①若j1＝j(luò)2，A，B處于同一群組網(wǎng)格中。A，B檢查彼此是否共享對稱矩陣Di，若二者共享至少一個對稱矩陣，則能夠建立成對密鑰；②j1≠j2，i1＝i2，A，B處于同一密鑰網(wǎng)格，不同的群組網(wǎng)格，依據(jù)BIBD（q2＋q＋1）的性質(zhì)，A，B以概率1共享一對密鑰；③若j1≠j2，i1≠i2，A，B不在同一密鑰網(wǎng)格，也不在同一群組網(wǎng)格中。A，B無法直接建立共享密鑰，與基于柵格的密鑰預(yù)分配方案類似，A，B通過路徑查找建立共享密鑰?？梢酝ㄟ^調(diào)整網(wǎng)格的大小來減小這類鏈路，當(dāng)l＝2r時，這類鏈路的比例僅為5%，因此在下文的分析中忽略這類鏈路。

3 方案性能分析

3.1 局域連通率

局域連通率plocal的定義參見文獻(xiàn) ［9］。假定ni，nj是WSN中兩個傳感器節(jié)點；事件A（ni，nj）表示節(jié)點ni，nj是鄰居節(jié)點；事件B（ni，nj）表示二者共享密鑰或密鑰空間，則局域連通率為

3.1.1 組內(nèi)鏈路與組間鏈路

為計算網(wǎng)絡(luò)中任意兩節(jié)點ni，nj之間的連通率，需計算組間鏈路與組內(nèi)鏈路的比例。組間鏈路是指處于不同群組網(wǎng)格內(nèi)的節(jié)點之間的鏈路，組內(nèi)鏈路是指同一群組網(wǎng)格內(nèi)節(jié)點構(gòu)建的鏈路。

隨機節(jié)點A 的組間鏈路所占比例近似為

圖2 組間鏈路的比例

3.1.2 局域連接率

3.2 網(wǎng)絡(luò)安全性分析

無線傳感器網(wǎng)絡(luò)的安全性是由x 個節(jié)點被敵手俘獲后受影響的鏈路的百分比來表征的。但是對于基于部署理論的方案而言，情況稍有復(fù)雜：攻擊者可以隨機地從網(wǎng)絡(luò)中俘獲若干節(jié)點，也可以針對性地從某一網(wǎng)格俘獲節(jié)點。本文討論兩種情形，局域安全性和全局安全性。局域安全性是指一個群組網(wǎng)格中x 個節(jié)點被俘獲后對鏈路造成的影響，全局安全性是指整個網(wǎng)絡(luò)中的x 個節(jié)點被俘獲后對網(wǎng)絡(luò)鏈路的影響。

如果x 個節(jié)點被俘獲，將會有3種受影響的鏈路：①直接被俘獲節(jié)點相關(guān)的鏈路；②俘獲x 個節(jié)點后，敵手中能夠攻陷的間接的組內(nèi)鏈路；③俘獲x 個節(jié)點后，敵手中能夠攻陷的間接的組間鏈路。假定網(wǎng)絡(luò)共N 個節(jié)點，每個節(jié)點周圍有d 個鄰居節(jié)點，敵手俘獲x 個節(jié)點，則受影響的鏈路的比例為

其中，pinf是敵手俘獲x 個節(jié)點后能夠攻陷間接鏈路的概率。

3.2.1 局域安全性分析

假定每個群組網(wǎng)格內(nèi)有Nm個節(jié)點，其中x 個節(jié)點被敵手俘獲，則受影響的鏈路計算如下：

直接相連的鏈路n1＝xd／2敵手間接攻陷的組內(nèi)鏈路

敵手間接攻陷的組間鏈路

因此局域鏈路的安全性可以用式 （6）表示

3.2.2 全局安全性分析

考慮到各個群組網(wǎng)格節(jié)點被俘獲個數(shù)相互獨立，全局安全性pgsec可以用式 （8）表示

4 仿真模擬分析

4.1 場景建立

假定N 個節(jié)點 （N＝10000）均勻部署在1000mⅹ1000m 的區(qū)域內(nèi)，每個節(jié)點的通信半徑為r＝40m，并擁有50個鄰居節(jié)點。選取全局連通率Pc＝0.9999。由上述參數(shù)可以計算出網(wǎng)絡(luò)深度d＝18，門限連通率prequired＝0.36。選取群組網(wǎng)格六邊形邊長l＝80m，部署區(qū)域共有m＝64個群組網(wǎng)格。每個群組網(wǎng)格包含156個節(jié)點，每個密鑰網(wǎng)格包含39個節(jié)點，選取q＝7。為了更好地與不同方案進(jìn)行比較，我們假定每個節(jié)點的最大存儲空間為200。

4.2 本地連通率的模擬

網(wǎng)絡(luò)的本地連通性為plocal＝（1－p）×p1＋p×1，當(dāng)l＝2r時p＝0.2034。每個節(jié)點的存儲容量為M＝200，故t＊（λ＋1）＋（q＋1）＝200。該方案與Du等人的多密鑰空間方案的本地連通率的比較如圖3所示。

圖3 不同t對應(yīng)的本地連接率

為滿足plocal≥prequired，我們需要t＝2時w ≤17，t＝3時w ≤42。本方案的本地連通率在0.5到0.8之間。一個很高的一跳連通率并不是必需的，因為Deng等人提出的多跳路徑查找可以有效地增強節(jié)點間的連通率。

4.3 安全性模擬

4.3.1 局域安全性模擬

本文通過一個群組網(wǎng)格中的x 個節(jié)點被俘獲后對網(wǎng)絡(luò)鏈路的影響來研究不同方案的局域安全性。模擬中各參量見表1，其中N 代表節(jié)點總數(shù)，sf 代表部署面積，Pc是全局連通率，r是節(jié)點的廣播半徑，l是六邊形網(wǎng)格邊長，m 是節(jié)點最大存儲容量，λ是門限值。

表1 模擬過程中各項參量

本方案與Yu，Guan等人方案的局域安全性的比較如圖4所示。在Yu等人的方案中，俘獲節(jié)點數(shù)未達(dá)到門限值時，鏈路受影響的比率近似線性增加，但是一旦節(jié)點數(shù)超過門限值，整個網(wǎng)格的密鑰就完全被敵手破解；在本方案中，每個網(wǎng)格節(jié)點數(shù)目不足以使敵手破解一個密鑰空間（w＝10，t＝2時，大約需要攻陷400個節(jié)點才能破解一組密鑰空間，但每個群組網(wǎng)格僅有156個節(jié)點）。

圖4 局域安全性的模擬

4.3.2 全局安全性模擬

不同方案的全局安全性的比較如圖5所示。圖中 “Du deployment”指Du 等人的部署理論方案， “Basic scheme”指多密鑰空間方案。在本方案和多密鑰空間方案中選取m＝200，t＝2；Du等人的部署理論中，S＝100000，m＝46，因為較小的m 能夠增強網(wǎng)絡(luò)抗攻擊的能力。圖5顯示我們的方案相較于其它幾種密鑰管理機制有著更強的安全性。當(dāng)少于400個節(jié)點被俘獲時，該方案與多密鑰空間方案性能類似，二者都優(yōu)于Du的部署方案。但是超過2.5%的節(jié)點被俘獲后，該方案的優(yōu)越性開始體現(xiàn)。當(dāng)1000個節(jié)點被俘獲后，受影響的鏈路僅為12%，即使考慮到計算過程中p的誤差，受影響的鏈路也不會超過20%。

圖5 全局安全性模擬

5 結(jié)束語

本文結(jié)合部署理論，多密鑰空間方案和組合設(shè)計理論，提出了一種新的無線傳感器網(wǎng)絡(luò)密鑰管理方案。其核心思想是將節(jié)點部署區(qū)域劃分為兩種類型的六邊形網(wǎng)格，不同網(wǎng)格內(nèi)的節(jié)點采用不同的方式建立密鑰。理論分析和仿真結(jié)果表明，該方案不僅能夠有效地抵御敵手攻擊尤其是選擇性攻擊，還能維持較高的網(wǎng)絡(luò)連通率。在傳感器節(jié)點存儲空間有限的情形下，本方案支持的網(wǎng)絡(luò)規(guī)模更大，更適用于大規(guī)模部署的無線傳感器網(wǎng)絡(luò)。

［1］Stankovic J A.Wireless sensor networks ［J］.Computer，2008，41 （10）：92－95.

［2］Barati A，Dehghan M，Barati H，et al.Key management mechanisms in wireless sensor networks ［C］／／SENSORCOMM，2008：81－86.

［3］Manivannan D，Neelamegam P.WSN：Key issues in key management schemes－A review ［J］.Research Journal of Applied Science，Engineering and Technology，2012，4 （18）：3188－3200.

［4］Xiaomin G W L.Research and improvement for q－composite key management scheme ［J］.Electronic Measurement Technology，2010，33 （6）：37.

［5］Zhang J，Varadharajan V.Wireless sensor network key management survey and taxonomy［J］.Journal of Network and Computer Applications，2010，33 （2）：63－75.

［6］Fanian A，Berenjkoub M.An efficient end to end key establishment protocol for wireless sensor networks［C］／／9th International ISC Conference on Information Security and Cryptology，2012：73－79.

［7］Brubaker B，Bump D，F(xiàn)riedberg S.Weyl group multiple dirichlet series：Type a combinatorial theory （AM－175）［M］.Princeton University Press，2011：201－232.

［8］SU Zhong，LIN Chuang，F(xiàn)ENG Fujun.Key management schemes and protocols for wireless sensor networks［J］.Journal of Software，2007，18 （5）：1218－1231 （in Chinese）.［蘇忠，林闖，封富君.無線傳感器網(wǎng)絡(luò)密鑰管理的方案和協(xié)議 ［J］.軟件學(xué)報，2007，18 （5）：1218－1231.］

［9］Liu D，Ning P，Du W.Group－based key predistribution for wireless sensor networks ［J］.ACM Transactions on Sensor Networks，2008，4 （2）：11.

［10］YAN Xueli，YE Xiaohui.Random key predistribution scheme for sensor networks based on hexagon deployment model［J］.Application Research of Computers，2012，29 （4）：1457－1461 （in Chinese）.［嚴(yán)雪莉，葉曉慧.一種基于六邊形部署模型的面向傳感器網(wǎng)絡(luò)的隨機密鑰預(yù)分配方案 ［J］.計算機應(yīng)用研究，2012，29 （4）：1457－1461.］

［11］Yu Z，Guan Y.A key management scheme using deployment knowledge for wireless sensor networks［J］.IEEE Transactions on Parallel and Distributed Systems，2008，19 （10）：1411－1425.

［12］DAI Hangyang，XU Hongbing.Key management in sensor network based on hexagon grid deployment model［J］.Journal of Electronic Measurement and Instrument，2008，22（5）：48－52 （in Chinese）.［代航陽，徐紅兵.基于六邊形網(wǎng)格部署模型的傳感器網(wǎng)絡(luò)密鑰管理 ［J］.電子測量與儀器學(xué)報，2008，22 （5）：48－52.］