成簇階段惡意節(jié)點識別與剔除模型研究及實現(xiàn)

李小慶，袁一方，何冰

（1.武漢大學電氣工程學院，湖北武漢430072；2.武漢大學經(jīng)濟與管理學院，湖北武漢430072；3.武漢大學測繪學院，湖北武漢430072）

隨著傳感器技術、嵌入式技術以及低功耗無線通信技術的發(fā)展，生產(chǎn)具備感應、無線通信以及信息處理能力的微型無線傳感器已成為可能。這些廉價的、低功耗的傳感器節(jié)點共同組織成無線傳感器網(wǎng)絡（WSN，wireless sensor network），通過節(jié)點間的相互協(xié)作，將其監(jiān)測和感應的多種環(huán)境信息（如溫度、濕度等）傳回到遠程基站進行處理[1]。由于受到成本、體積等因素的限制，傳感器節(jié)點的處理能力、無線帶寬，以及電池容量等資源非常有限。并且在很多應用中，傳感器節(jié)點都被部署在環(huán)境惡劣的地區(qū)，節(jié)點的能量無法得到補充，于是如何延長傳感器網(wǎng)絡的生存時間和實現(xiàn)安全的數(shù)據(jù)通信成為設計上需要考慮的一個難題。

將傳感器節(jié)點安全分簇是目前解決這一問題的重要方法。分簇的基本思想是通過簇首對簇內(nèi)節(jié)點間的相關信息融合及轉(zhuǎn)發(fā)機制減少數(shù)據(jù)的傳輸量和距離，進而降低通信能量，達到網(wǎng)絡節(jié)能的目的。傳感器網(wǎng)絡的主要任務是將網(wǎng)絡中傳感器節(jié)點收集的數(shù)據(jù)傳送給基站。實現(xiàn)該任務的一種最簡單方法是使用直接傳送[2]，即網(wǎng)絡中的每個節(jié)點把收集到的數(shù)據(jù)直接傳送給基站。然而，對于遠離基站的傳感器節(jié)點，節(jié)點直接傳送數(shù)據(jù)消耗的能量代價太高將使節(jié)點很快死亡。為解決這個問題，目前已經(jīng)提出了許多以節(jié)約能量為目的的分布式成簇算法，如LEACH[3]，PEGASIS等。

LEACH（low energy adaptive clustering hierarchy）協(xié)議是MIT學者Heinzelman等人為無線傳感器網(wǎng)絡設計的低功耗自適應聚類路由算法，其出發(fā)點主要是考慮一簇節(jié)點內(nèi)的能量消耗問題，目的是為了延長節(jié)點的工作時間，并且實現(xiàn)節(jié)點的能耗平衡[4]。它以輪換的簇首選擇方式，將簇首的繁重轉(zhuǎn)發(fā)任務交由各個節(jié)點均衡分擔，從而達到節(jié)點能量消耗均衡的效果，延長網(wǎng)絡的整體存活壽命。然而此算法的分簇原理雖然可行但是每個簇中仍存在惡意節(jié)點的問題，因此從節(jié)點到基站傳輸數(shù)據(jù)的安全問題和能量高效問題依舊是安全敏感的無線傳感器網(wǎng)絡應用面臨的主要問題。

本文在網(wǎng)絡分簇階段應用SECA（Secure Encryption Clustering Algorithm）安全密鑰成簇算法[5]，實現(xiàn)在成簇階段及時對惡意節(jié)點進行識別和剔除，盡可能減小惡意節(jié)點對網(wǎng)絡的破壞。它借鑒了LEACH算法的簇首輪轉(zhuǎn)思想，在分簇階段就引入密鑰預分布方案，從而保證網(wǎng)絡節(jié)點之間的通信安全性，同時優(yōu)化每一輪生成的簇內(nèi)結(jié)構，使得每一輪的能耗盡可能小，以達到延長網(wǎng)絡壽命的目的。

1 模型假設

假設n個傳感器節(jié)點隨機均勻地分布在一個L×L的正方形區(qū)域內(nèi)，并且該傳感器網(wǎng)絡具有如下的性質(zhì)：

1）在傳感器節(jié)點區(qū)域較遠的地方固定有一個基站sink；

2）區(qū)域內(nèi)的所有傳感器節(jié)點都是同構（傳輸半徑和傳輸角相同）的，節(jié)點能量有限為Eo，具有相似的處理和通信的能力，并對網(wǎng)絡具有相同的重要性；

3）節(jié)點分布之前是安全的，未受到任何入侵行為引起的篡改和破壞；

4）數(shù)據(jù)的采樣周期長，采集到的數(shù)據(jù)通過數(shù)據(jù)融合技術進行綜合處理；

5）每個節(jié)點都可以通過單跳方式與基站進行直接通信；

6）節(jié)點通信是對稱的，即從節(jié)點x傳送消息m到y(tǒng)消耗的能量和從y傳送消息m到x所消耗的能量是相同的；

7）節(jié)點ID在出廠后是不可以更改的；

8）每個傳感器節(jié)點都攜帶有一個相同的主密鑰，節(jié)點間的任何通信都須用主密鑰基于AES對稱密碼算法進行加密和解密處理來識別網(wǎng)絡中的惡意節(jié)點所阻撓數(shù)據(jù)通信。

9）假設節(jié)點進行通信工作時，按照LEACH算法的層次模型進行，即是簇內(nèi)普通節(jié)點只能與本簇內(nèi)其他節(jié)點以及簇首通信，簇間信息交換由簇首來完成，簇首可以直接將數(shù)據(jù)包融合后發(fā)給基站。

10）惡意節(jié)點通過密鑰不匹配被識別，并告之其他網(wǎng)絡內(nèi)節(jié)點，在下一輪成簇的過程中將被識別的惡意節(jié)點剔除，不允許其加入任何一個簇，排除在有效網(wǎng)絡之外。

2 關鍵變量說明

表1 部分變量說明Tab.1Part of the variable declaration

3 數(shù)學模型建立

模型設定初始的成為簇首的概率為p=0.05，然后模型按照T（n）的概率計算方案計算各個節(jié)點的被選擇為簇首的概率。

由于LEACH算法是以t為周期進行新一輪分簇，而每一輪分簇都會識別并剔除惡意節(jié)點和已經(jīng)消耗完能量死去的節(jié)點，故每一輪網(wǎng)絡中剩余的有用節(jié)點數(shù)目會不斷遞減。引入布爾變量bool（i）來記錄是否網(wǎng)絡可以正常工作。判斷標準定義為：現(xiàn)存活的有用節(jié)點數(shù)目不少于原始總節(jié)點數(shù)n的一半。Liv為bool的累加和。由于重新分簇具有周期性，故統(tǒng)計網(wǎng)絡有效工作期間已進行的重新分簇輪數(shù)即可以等效描述網(wǎng)絡的存活時間。數(shù)學表達公式如下：

等效存活時間Liv=Σbool（i）

4 MATLAB仿真模型的建立

算法流程描述如下：

1）假定初始狀態(tài)各個節(jié)點都是正常的、安全。由基站根據(jù)初始概率p和公式T（n）的計算結(jié)果初始確定第一輪簇首。

2）各個簇首向整個網(wǎng)絡廣播自己被選為簇首的信息，其他節(jié)點接收到廣播信息以后，分別計算自己與各個簇首的距離，選擇最近的簇首就近加入其所在簇。第一輪分簇完成。

3）分配給同簇節(jié)點共享密鑰，不同簇之間密鑰不同。分配給簇首以簇首通信密鑰。

4）進行t時間的加密數(shù)據(jù)通信。任何一次數(shù)據(jù)通信或者消息交換都需要進行密鑰認證。同簇之間可以自由通信，但是簇間通信只能由簇首來完成，簇首均有能力直接向基站發(fā)送數(shù)據(jù)包。

5）隨機在網(wǎng)絡中選中1個或者2個（隨機）的節(jié)點，賦予它們惡意節(jié)點的行為特征：節(jié)點向異簇節(jié)點發(fā)出通信請求。正常節(jié)點運行時候，若不是簇首不會向異簇節(jié)點發(fā)起會話請求，即便是簇首節(jié)點也只能向其他簇首節(jié)點發(fā)送請求。而惡意節(jié)點的特征是無論自己或者對方是否同簇或者是否為簇首，均向其發(fā)起數(shù)據(jù)請求。這種行為在模型中被認為是非法的。

6）節(jié)點加密通信的過程中，若某節(jié)點A檢測到密鑰不對的非法通信請求，即將該請求節(jié)點ID記錄加入黑名單devil中。

7）該節(jié)點A立即向簇首（若A是普通節(jié)點）或者基站（若A是簇首）發(fā)布黑名單中的惡意節(jié)點ID，告示其它節(jié)點對這個ID的消息實施封鎖。

8）周期t時間到。開始新的一輪簇首選取。如步驟1）。

9）各節(jié)點計算自己與各簇首之間的距離，請求加入較近的簇首所在簇。這時簇首節(jié)點對請求節(jié)點發(fā)起安全認證。如果在黑名單devil中有記錄，則拒絕其加入本簇。并廣告給其它簇首節(jié)點，拒絕將其加入新簇。基站將這類孤立的惡意節(jié)點剔除出網(wǎng)絡。將剩余能量為0或者小于0的節(jié)點清理出網(wǎng)絡。于是，新簇形成。

10）重復步驟3）、4）、5）、6）、7）、8）、9）。

11）所有節(jié)點均被剔除（惡意的節(jié)點，死亡的節(jié)點），網(wǎng)絡停止，結(jié)束。

在MATLAB[6]平臺上編寫仿真程序，并運行，運行結(jié)果如圖所示。

圖1 基站和節(jié)點分布圖Fig.1Distribution of the base station and nodes

圖2 惡意節(jié)點Fig.2Malicious nodes

其中圖1為初始狀態(tài)隨機產(chǎn)生的節(jié)點位置以及基站位置分布。圖3為剩余節(jié)點數(shù)與循環(huán)輪數(shù)、概論簇頭數(shù)與循環(huán)輪數(shù)的關系。由圖3可以觀察到：使用密鑰預分配方案后，系統(tǒng)的壽命（以Liv為標準）大約為320輪左右。惡意節(jié)點的分布圖如圖2所示。圖4為沒有將惡意節(jié)點識別并剔除的網(wǎng)絡剩余可用節(jié)點與循環(huán)輪數(shù)的關系。由圖3和圖4可以明顯看出，惡意節(jié)點的識別和剔除對于網(wǎng)絡的生存性能非常重要。并且基于LEACH算法的密鑰分配方案對于惡意節(jié)點的識別和剔除效果較好。

圖3 剩余節(jié)點數(shù)與循環(huán)輪數(shù)、該輪簇頭數(shù)與循環(huán)輪數(shù)的關系Fig.3Relationship of the remaining nodes and recycling rounds、The number of cluster heads and recycling rounds

圖4 沒有剔除惡意節(jié)點的網(wǎng)絡剩余節(jié)點數(shù)與循環(huán)輪數(shù)、該輪簇頭數(shù)與循環(huán)輪數(shù)的關系Fig.4Relationship of the remaining nodes and recycling rounds、The number of cluster heads and recycling rounds without moving malicious nodes out

5 模型分析

在無線傳感器網(wǎng)絡中，安全的成簇算法是減少能量消耗的一種關鍵技術，它能夠增強網(wǎng)絡的擴展性，延長網(wǎng)絡的生存時間。與已有探索性研究成果相比，本模型將安全技術前移至成簇階段進行，并基于密鑰預分配方案來識別惡意節(jié)點，從開始就阻截攻擊行為，有助于從根本上保障所采集信息的真實性和可靠性。借鑒LEACH成簇算法，將能效目標、成簇效率結(jié)合起來，有助于最大限度提高網(wǎng)絡的存活性和魯棒性。

模型基于層次通信網(wǎng)絡模型，建模簡單，思路清晰，重點在于成簇階段惡意節(jié)點的識別和剔除。模型采用密鑰預分配的方案實行安全成簇算法，較之“虛假數(shù)據(jù)”、“錯誤數(shù)據(jù)”等普通判斷方法，提高了惡意節(jié)點的識別率，有助于整個網(wǎng)絡的網(wǎng)絡壽命的提高和網(wǎng)絡性能的維護。此外，模型采用等效存活時間的判斷標準，合理簡潔。可以很好地反映網(wǎng)絡的存活指標。方法通俗，可推廣性能高。

當然，無線傳感器網(wǎng)絡的實際通信過程是一個很復雜的過程，遠不止模型中假設的層次通信那么簡單。所以模型具有一定的實際局限性，與實際現(xiàn)實情況有一定差距。此外，惡意節(jié)點的特征描述稍顯簡單，可以適當加入多個判斷標準同時加以判斷。從而確保不漏判不錯判，進一步提高系統(tǒng)的性能和效率。

6 模型改進

由于本次仿真的主要是基于惡意節(jié)點的識別與剔除，所以在建立模型的時候弱化了自組織網(wǎng)絡的通信特性。目前，無線傳感器網(wǎng)絡存在的攻擊模型主要有：蟲洞攻擊（Wormhole攻擊）、黑洞攻擊（Sinkhole攻擊）、女巫攻擊（Sybil攻擊）、虛假路由信息攻擊、選擇性轉(zhuǎn)發(fā)攻擊、HELLO泛洪攻擊以及欺騙性確認攻擊。其中Wormhole攻擊、黑洞攻擊、女巫攻擊是3種比較典型的攻擊方式，也是基本的攻擊手段，其他的攻擊方式常結(jié)合這3種攻擊方式進行。

基于以上實際無線傳感器網(wǎng)絡的特性，模型改進方向可以設置為：自組織鄰居通信，針對典型攻擊明確惡意節(jié)點的行為和其他特征。從而更加真實地仿真網(wǎng)絡系統(tǒng)的通信過程，在多特征識別的優(yōu)勢下，更加準確的識別和剔除對網(wǎng)絡性能破壞的惡意節(jié)點。進一步，更加準確、實用地在成簇階段處理惡意節(jié)點來提高網(wǎng)絡的整體性能和網(wǎng)絡工作壽命。

[1]孫利民.無線傳感器網(wǎng)絡[M].北京:清華大學出版社，2005.

[2]YU YY，CHONG PHJ．A Survey of Clustering Schemes for Mobile Ad Hoc Networks[J]．IEEE Communications Surveys and Tutorials，F(xiàn)irst Quarter，2005，7（1）：32－48．

[3]Heinzelman WR，Chandraka SAN A，Balakrishnan H．Energyefficient communication protocol for wireless microsensor networks[C]//Proceeding33rdAnnualHawaiiInternationalConference on System Sciences（HICSS00），2000:3005－3014．

[4]佘靜濤，胡同森，鐘明霞.無線傳感器網(wǎng)絡路由協(xié)議LEACH的研究與改進[J].計算機系統(tǒng)應用，2009（2）：30－34.SHE Jing-tao，HU Tong-sen，ZHONG Ming-xia.LEACH routing protocol for wireless sensor networks Research and Improvement[J].Applied Computer Systems，2009（2）:30－34

[5]胡向東，蔡東強.無線傳感器網(wǎng)絡安全加密成簇算法的設計及研究[J].重慶郵電大學學報：自然科學版，2009，21（3）：421－424.HU Xiang-dong，CAI Dong-qiang.Wireless sensor network security encryption algorithm design and research clusters[J].Chongqing University of Posts and Telecommunications：Natural Science，2009，21（3）：421－424.

[6]張志涌，楊祖櫻.MATLAB教程[M].北京:北京航空航天大學出版社，2010.