基于六邊形的無線傳感器網(wǎng)絡(luò)密鑰管理方案

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

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

0 引 言

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

自Eschenauer和Glogor提出基于概率的E－G 方案［3］以來，許多類似的密鑰管理方案如q－composite［4］、多密鑰空間［5］、對稱多項(xiàng)式［6］、組合設(shè)計(jì)理論［7］等方案相繼被 提出。網(wǎng)絡(luò)的連通性和安全性［8］是評定WSN 密鑰管理方案的性能的兩個(gè)主要標(biāo)準(zhǔn)。但是上述方案抵御敵手俘獲節(jié)點(diǎn)攻擊的能力并不強(qiáng)，例如對于Du等人的多密鑰空間方案，當(dāng)400個(gè)節(jié)點(diǎn)被捕獲時(shí)，網(wǎng)絡(luò)中受影響鏈路數(shù)達(dá)到100% （m＝200，w＝7，t＝2）；在Chan 等人的q－composite方案中，150個(gè)節(jié)點(diǎn)被俘獲后 （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］增強(qiáng)了節(jié)點(diǎn)抵御攻擊的能力。但這些方案抵御敵手選擇性攻擊的能力并不強(qiáng)，在Yu和Guan方案中，b＝3，w＝3時(shí)，敵手選擇性的攻擊某一網(wǎng)格，一旦俘獲節(jié)點(diǎn)數(shù)目超過門限值，鄰近的26 個(gè)網(wǎng)格密鑰都會(huì)被攻陷。

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

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

1.1 多密鑰空間方案

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

1.2 組合設(shè)計(jì)理論

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

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

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

2 本文方案

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

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

2.1 密鑰預(yù)分配

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

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

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

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

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

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

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

每個(gè)節(jié)點(diǎn)用一個(gè)三維向量（i，j，k）（i＝1，2…4 m，j＝1，2…，m，k＝1，2，…，4 Nc）來唯一地表征。其中，i代表節(jié)點(diǎn)所處的密鑰網(wǎng)格標(biāo)志號(hào)，j代表節(jié)點(diǎn)所處的群組網(wǎng)格標(biāo)志號(hào)，k代表在群組網(wǎng)格中節(jié)點(diǎn)的ID。部署完成后，每個(gè)節(jié)點(diǎn)廣播其三維序列號(hào)（i，j，k），同時(shí)接收鄰居節(jié)點(diǎn)廣播的序列號(hào)。假定節(jié)點(diǎn)A（i1，j1，k1）與節(jié)點(diǎn)B（i2，j2，k2）是鄰居節(jié)點(diǎn)，A，B之間的密鑰建立分為如下情形：①若j1＝j(luò)2，A，B處于同一群組網(wǎng)格中。A，B檢查彼此是否共享對稱矩陣Di，若二者共享至少一個(gè)對稱矩陣，則能夠建立成對密鑰；②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時(shí)，這類鏈路的比例僅為5%，因此在下文的分析中忽略這類鏈路。

3 方案性能分析

3.1 局域連通率

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

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

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

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

圖2 組間鏈路的比例

3.1.2 局域連接率

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

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

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

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

3.2.1 局域安全性分析

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

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

敵手間接攻陷的組間鏈路

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

3.2.2 全局安全性分析

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

4 仿真模擬分析

4.1 場景建立

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

4.2 本地連通率的模擬

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

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

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

4.3 安全性模擬

4.3.1 局域安全性模擬

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

表1 模擬過程中各項(xiàng)參量

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

圖4 局域安全性的模擬

4.3.2 全局安全性模擬

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

圖5 全局安全性模擬

5 結(jié)束語

本文結(jié)合部署理論，多密鑰空間方案和組合設(shè)計(jì)理論，提出了一種新的無線傳感器網(wǎng)絡(luò)密鑰管理方案。其核心思想是將節(jié)點(diǎn)部署區(qū)域劃分為兩種類型的六邊形網(wǎng)格，不同網(wǎng)格內(nèi)的節(jié)點(diǎn)采用不同的方式建立密鑰。理論分析和仿真結(jié)果表明，該方案不僅能夠有效地抵御敵手攻擊尤其是選擇性攻擊，還能維持較高的網(wǎng)絡(luò)連通率。在傳感器節(jié)點(diǎn)存儲(chǔ)空間有限的情形下，本方案支持的網(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é)報(bào)，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ò)的隨機(jī)密鑰預(yù)分配方案 ［J］.計(jì)算機(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é)報(bào)，2008，22 （5）：48－52.］