WSN中基于鄰居發現的動態密鑰管理方案

尚鳳軍，周永奎

（重慶郵電大學 計算機科學與技術學院，重慶400065）

0 引 言

無線傳感器網絡 （WSN）是集微電子技術，傳感器技術，通信技術于一體而組建的網絡，可廣泛應用于軍事和商業等領域［1］。無線傳感器網絡往往部署在無人監管或容易受損被俘獲的環境中，保證無線傳感器網絡的安全是應用中首先考慮的問題［2］，其中密鑰管理機制是保證無線傳感器網絡安全的核心機制［3，4］。但是由于節點資源有限，無固定基礎設施支持，節點易受損等問題，傳統網絡中的密鑰管理機制往往不能直接應用于無線傳感器網絡中，安全問題一直是學術界研究的重點［5］。

近年來，研究人員提出了大量應用于無線傳感器網絡的動態密鑰管理方案，Moharrum和Eltoweissy提出了基于EBS的動態密鑰管理方案，但該方案屬于集中式密鑰管理方案［6］，不能適用于節點數目較多的大規模網絡；Elwoweissy等人提出了基于EBS動態密鑰管理方案LOCK （localized combinatorial keying）［7］，在分簇的基礎上為簇內普通傳感節點動態分配管理密鑰，具有節點刪除，密鑰更新等功能，但存在共謀攻擊的問題；Younis在層次式 WSN里提出基于位置信息的EBS動態密鑰管理方案SHELL（scalable，hierarchical，efficient，socation－aware and lightweight）［8］，該方案能夠有效抵御節點共謀攻擊，但是該方案需要節點具有定位能力獲得節點的具體位置，且網絡拓撲結構發生變化后，該方案抵抗共謀攻擊的能力下降。

針對以上方案的缺點，為提高網絡的安全性能，減少節點開銷，本文提出一種基于鄰居發現的動態密鑰管理方案 （NDDK）具有以下優點：

（1）該方案通過鄰居發現過程在簇首中形成整個簇的拓撲結構模型，進一步生成密鑰分配方案，不需要通過GPS等定位技術獲取節點的位置信息；

（2）該方案采用節點分層算法用于生成EBS矩陣進行密鑰分配，與SHELL中啟發式搜索算法相比減少了簇首節點的計算開銷，增強了網絡抵抗共謀攻擊的性能；

（3）該方案引入同化二元同化多項式［9］代替普通密鑰，提高了節點抵抗俘獲攻擊性能；

（4）該方案在網絡拓撲結構發生變化之后仍能保證節點分配密鑰組合最佳，總體上提高了網絡抵抗共謀攻擊的性能。

1 系統介紹

EBS是由Eltoweissy等于2004年提出的一種分層式的基于組合優化原理的應用于無線傳感器網絡中的組通信密鑰管理方案［10］。EBS系統通常表示為集合 （n，k，m），其中n為每一組傳感器節點的數量，k＋m表示每一組傳感節點所擁有的管理密鑰的總量，k表示每個節點分配的管理密鑰的數量，m為密鑰更新的信息數。EBS系統是由包含部分節點的子集 （A1，A2，A3……）構成的集合Г。每個子集A是由一系列含有同一管理密鑰的節點構成的集合。

定理1 當Ckk＋m≥n時k＋m中的任意k＋m個組合均可以構成EBS（n，k，m），從而形成一個EBS動態密鑰分配方案。

定理2 通過廣播最多m個數據包動態取消或更新任意節點所有的k個密鑰，從而實現節點的刪除。

假設傳感節點N1被捕獲，則需要通過密鑰k4和k5取消并更新節點N1擁有的密鑰k1，k2，k3刪除節點N1：

（1）Ek4（S′，Ek1（k1′），Ek2（k2′），Ek3（k3′））

（2）Ek5（S′，Ek1（k1′），Ek2（k2′），Ek3（k3′））

其中Eki（x）表示數據x用密鑰ki進行加密，密鑰ki更新為ki′，si′ 為更新后的 會話密鑰。

2 NDDK方案

本文提出的是基于鄰居發現的EBS動態密鑰管理方法，首先利用節點的一跳鄰居節點發現過程在簇首中建立整個簇的拓撲結構模型，簇首根據整個簇的拓撲模型進行動態密鑰管理。主要研究內容包括：網絡初始化，EBS矩陣的生成，管理密鑰的分配，節點添加和密鑰更新等方面的內容。

2.1 網絡初始化階段

在網絡部署前，每個節點預載入僅與基站共享的節點密鑰KI，一個全網唯一的ID和一個統一的單向密鑰生成函數F。節點部署后，開始進行網絡初始化。本文假設網絡在初始化階段是安全，攻擊者不能俘獲并破解任何傳感節點。具體步驟如下：

步驟1 網絡部署之后，節點進行一跳鄰居發現過程，節點u在一跳范圍內廣播鄰居節點發現信息：

其中ADV－discovery為節點鄰居發現消息標志。接收到NMu的節點v將節點u及其ID保存在自己的鄰居列表ID－listv中。

步驟2 本文在分簇的基礎上進行動態密鑰的管理，以簇為單位進行動態密鑰管理。分簇不是本文研究的重點，本文采用已有的分簇方式進行分簇［11］。

步驟3 分簇完成后，普通傳感節點u將ID－listu發送至u所在簇的簇首CHi：

在簇首中形成整個簇的拓撲結構模型。

2.2 EBS矩陣的生成

網絡初始化完成之后，為保證鄰居節點分配的密鑰組合漢明距離最小，本文采用節點分層算法決定普通傳感節點SN的密鑰組合即在簇首CH中形成EBS矩陣。我們采用無向圖G（V，E）說明算法，如圖1所示。V表示所有頂點的集合V＝ ｛A，B，C…，G｝。E表示所有邊的集合，邊的存在代表兩個節點在彼此的通信范圍內互為鄰居節點。

圖1 簇拓撲結構模型

（1）首先計算所有節點度數，選取度數最大的節點作為根節點，根節點的鄰居節點處在第二層，依次類推。

（2）根據層數優先，同層節點中度數較大的節點優先分配密鑰的準則，劃分節點分配密鑰的優先次序。如圖1所示B，F處在同一層中，B的度數為4，E的度數為3，優先對B進行分配。

（3）根據簇內節點數量n選取合適的k和m的值，在k＋m值最小的前提下，保證k的值最小。

（4）根據節點分配次序，依次指定節點密鑰組合，并保證鄰居節點中分配的密鑰組合漢明距離最小，在對節點分配密鑰時只挑選未使用的密鑰組合。本文選擇EBS參數k＝2，m＝3對圖1中節點進行密鑰分配，生成EBS矩陣如表1所示。

表1 EBS（8，2，3）的密鑰子集

2.3 管理密鑰分配

EBS矩陣生成之后，簇首節點CH從鄰居節點中選擇密鑰生成節點KGN，KGN的數量為t且t＞ （k＋m）／k，這樣保證部分KGN的俘獲不會導致全部管理密鑰泄漏。首先，CH向基站申請用于分配管理密鑰的種子seed，SEED是用于申請種子的標志，簇首利用seed生成分配密鑰ks＝F（seed）［12］；然后，CH在簇內廣播seed和利用ks加密的EBS矩陣，簇內節點SN收到消息后根據seed生成密鑰ks同時解密得到EBS矩陣；其次，KGN生成同化多項式［10］密鑰ka，并利用ks加密后發送給簇首，簇首在簇內逐個廣播ka；最后，SN利用ks和EBS矩陣接收僅屬于自己的k個密鑰多項式。密鑰多項式的分配過程描述見表2。

表2 密鑰多項式分配過程

KGN生成的同化二元多項式［10］如式 （1）所示

其中l∈ ［1，2，…，k＋m］，對于分配了同一個同化多項式的一組節點可以形成相同的共享密鑰。密鑰分配完成之后，CH銷毀其存儲的全部管理密鑰，SN銷毀其存儲的EBS矩陣。

2.4 節點添加

在網絡的運行過程中，由于節點能量耗盡或者節點俘獲被刪除等原因，需要向網絡中添加新的節點。新添加節點部署前預載入節點發現密鑰ksg，同時基站BS向網絡中所有的簇首發送新添加節點的ID和節點發現密鑰ksg。以圖2為例子說明節點u的添加過程：

（1）節點u部署后向其鄰居節點廣播鄰居發現消息：

（2）收到鄰居發現消息的傳感節點v，將新加入的節點u及其ID添加在自己的鄰居列表中，同時v向u發送回復消息，回復消息包括該節點的ID和其所在的簇的簇首ID：

（3）收到回復消息的后u形成節點鄰居列表，向合適簇首CHi發送節點加入請求消息：

其中join為新節點加入請求標志。

（4）簇首CHi收到節點加入請求消息后，通過ksg和節點ID驗證u身份。驗證成功后為u分配與鄰居節點漢明距離最小的管理密鑰組合。節點添加成功后刪除ksg：

圖2 節點添加

2.5 密鑰更新

為提高網絡的安全性能，動態密鑰管理系統需要周期性的進行密鑰更新。本文假設網絡為靜態網絡即節點在部署之后位置不發生變化。由于網絡在運行過程中由于節點的刪除和添加等原因，網絡的拓撲結構可能會發生變化。本文以簇為單位進行的密鑰管理，所以根據簇的拓撲結構是否發生變化將密鑰更新分為兩個不同的方案：

（1）簇的拓撲結構不發生變化：簇首向KGN發送密鑰更新請求，KGN生成新的管理密鑰多項式ka’并將ka’用ka加密得到E （ka’，ka），并進一步用ks加密得到E （E（ka’，ka），kS）發送給簇首，簇首使用ks解密，得到E（ka’，ka），同時在簇內廣播 E （ka’，ka），普通傳感節點收到后用ka解密的到新的管理密鑰ka’，刪除更新前的管理密鑰ka。

（2）簇的拓撲結構發生變化：有于節點能量耗盡或節點被俘獲等原因，網絡中需要進行節點的刪除和添加，此時簇的拓撲結構發生變化。簇首根據更新后的拓撲結構按照2.3所示方法重新進行管理密鑰分配。

3 性能分析與比較

下面從網絡安全性和節點開銷等方面對本方案進行分析，并與SHELL方案進行對比，兩種方案均為基于EBS的動態密鑰管理方法。SHELL［8］方案中節點分為普通傳感節點SN和網關節點Gateway，對Gateway需要更大的存儲空間和計算能力，同時要求節點具有定位能力。本文提出的方案，所有的節點均為普通傳感節點，且不需要節點具有定位能力，對節點要求更低，適用性更強。

3.1 節點抗俘獲性能

本文與SHELL均以簇為單位進行動態密鑰管理，我們以簇為單位分析節點的抗俘獲攻擊的性能。假設網絡中存在n個節點，每個節點分配k個同化二元多項式，更新密鑰的數量為m，被捕獲節點的數量為Nc，同化多項式Fi被捕獲的概率為pFi，如式 （2）所示

由式 （2）可知t＋1階同化二元多項式是t－安全的。當俘獲不超過t個擁有同一個多項式的節點時，該多項式是不可破解的。本文使用同化多項式密鑰作為節點的管理密鑰，節點的抗俘獲性能優于SHELL。

3.2 節點抵抗共謀攻擊的性能

在密鑰分配的過程中，本文提出的方案利用節點數量信息和簇拓撲結構信息對簇內傳感節點進行管理密鑰的分配。在節點添加和密鑰更新的過程，簇首節點根據簇拓撲結構的變化，為節點動態分配管理密鑰，保證網絡抵抗共謀攻擊的性能。為了驗證本文提出方案對共謀攻擊的抵抗性能，我們針對不同的網絡規模進行仿真實驗，并將本文方法與SHELL［8］進行比較。如圖3所示。

圖3 共謀鏈長度比較

圖3描述了不同網絡規模下整個網絡被捕獲時SHELL和NKKD最短共謀鏈的長度的比較。由于本文采用節點分層算法進行密鑰分配，由圖3可知在不同網絡規模下，NKKD的最短共謀鏈的長度較SHELL更長，NKKD對抵抗共謀攻擊的性能更好。隨著網絡規模的增大，最短共謀鏈的長度總體上不斷增大。

3.3 節點開銷

（1）生成EBS矩陣的計算開銷

在SHELL和本文的方案中，簇首首先根據網絡的拓撲結構，決定簇內節點的密鑰組合即形成EBS矩陣。在SHELL采用啟發式算法［8］進行密鑰分配，節點在分配密鑰過程中需要不斷的同上層節點交換密鑰組合，以保證與相鄰節點的密鑰組合的漢明距離最小。本文采用節點分層算法，首先劃分節點分配密鑰的順序，不需要密鑰分配節點與上層節點反復交換密鑰，密鑰分配算法的時間復雜度大大降低。若網絡中存在n個節點，本文算法時間復雜度為O （n），SHELL采用啟發式算法時間復雜度為O（n2），如表3所示。

（2）SN存儲開銷

本文使用的管理密鑰為多項式密鑰，節點存儲k個t階多項式密鑰需要的密鑰存儲空間為k（t＋1），SHELL中節點使用普通密鑰需要存儲空間為k。雖然多項式密鑰的使用增加了節點的存儲空間，但是節點抵抗俘獲攻擊的能力大大增強，提高了網絡的安全性能。

（3）密鑰分配通信開銷

SHELL在密鑰分配過程中簇首為簇內節點逐個分配K個管理密鑰，每個密鑰分配消息中包含k個管理密鑰，則需要的總的通信開銷為nk，n為簇內SN節點的數量。本方案中CH逐個廣播管理密鑰，每個管理密鑰僅需廣播一次，需要的總的通信開銷僅為k＋m，遠遠小于nk。本方案中通信開銷顯著降低。

表3 節點開銷

4 結束語

本文針對傳感器網絡容易受到節點俘獲攻擊和共謀攻擊的問題，提出了基于鄰居發現的動態密鑰管理方案。該方案中的節點均為普通傳感節點，節點通過鄰居發現過程而不需要通過節點定位，形成網絡的拓撲結構，降低了對節點的要求和功耗；通過節點分層生成EBS矩陣進行管理密鑰分配，降低簇首節點的計算開銷和分配開銷，同時增強了網絡抵抗共謀攻擊的性能；在節點添加和密鑰更新的過程，簇首根據節點的鄰居列表動態更新網絡的拓撲結構，從而使節點獲得最優的密鑰組合，提高網絡抵抗共謀攻擊的性能。分析結果表明，與相關文獻比較，該方案增強了網絡安全性能，整體上降低了網絡開銷。

［1］Aronti P，Pillai P，Chook V.WIRELESS sensor networks：A survey on the state of the art and the 802.15.4and ZigBee standards［D］.Pisa：Department of Computer Science，University of Pisa，2006.

［2］CHEN X，Makki K，Yen K，et al.Sensor network security：A survey［J］.IEEE Communications Survey ＆ Tutorials，2009，11 （2）：52－73.

［3］PEI Qingqi，SHEN Yulong，MA Jianfeng.Survey of wireless sensor networks security techniques［J］.Journal on Communications，2007，28 （8）：113－122（in Chinese）.［裴慶祺，沈玉龍，馬建峰.無線傳感器安全技術綜述 ［J］.通信學報，2007，28 （8）：113－122.］

［4］SU Zhong，LIN Chuang，REN Fujun，et al.Key management schemes and protocols for wireless sensor networks［J］.Journal of Software，2007，18 （5）：1218－1231（in Chinese）.［蘇忠，林闖，任富君，等.無線傳感器網絡密鑰管理的方案和協議 ［J］.軟件學報，2007，18 （5）：1218－1231.］

［5］WEN Tao，ZHANG Yong，GUO Quan，et al.Dynamic group key management scheme for homogeneous wireless sensor networks［J］.Journal on Communications，2012，33 （6）：164－173（in Chinese）.［溫濤，張永，郭權，等.WSN中同構模型下動態組密鑰管理方案 ［J］.通信學報，2012，33 （6）：164－173.］

［6］Mohamum M，Eltoweissy M.A study of static versus dynamic keying schemes in sensor networks ［C］／／Montreal：Proc of 2nd ACM International Workshop on Performance Evaluation of Wireless Ad Hoc，Sensor Networks，and Ubiquitous Networks，2005：122－129.

［7］Mohanum M，Elwoweissy M，Mukkamala R.Dynamic key management in sensor networks ［J］.IEEE Communications Magazine，2006，44 （4）：122－130.

［8］Younis M，Ghummank，Elwoeissy M.Location－aware combinatorial key management scheme for clustered sensor networks［J］.IEEE Transaction on Parallel and Distributed System，2006，17 （8）：865－882.

［9］KONG Fanrui，LI chunwen，DING Qingqing.Dynamic key management scheme for wireless sensor networks based on polynomial keys ［J］.Journal of Tsinghua University，2009，49（10）：21－24（in Chinese）.［孔繁瑞，李春文，丁青青.基于多項式的傳感器網絡動態密鑰管理方法 ［J］.清華大學學報，2009，49 （10）：21－24.］

［10］Eltowieissy M，Heydari H，Morales L，et al.Combinatorial optimization of key management in group communications［J］.Journal of Network and Systems Management，2004，12 （1）：33－50.

［11］YU Lei，LI Jianzhong，LUO Jizhou.Distributed secure clustering protocol in wireless sensor networks［J］.Journal of Software，2009，20 （10）：2705－2720（in Chinese）.［余磊，李建中，駱吉洲.一種無線傳感器網絡分布式安全成簇協議 ［J］.軟件學報，2009，20 （10）：2705－2720.］

［12］ZHONG Jin，LUO Jun，JIANG Rong，et al.Routing based two－level key management scheme in wireless sensor networks［J］.Application Research of Computers，2011，28 （2）：738－741（in Chinese）.［鐘進，羅軍，江榮，等.無線傳感器網絡基于路由的兩級密鑰管理方案 ［J］.計算機應用研究，2011，28（2）：738－741.］