一種基于LEAP安全架構的分布式分簇算法

余穩(wěn)定，梁剛

（四川大學計算機學院，成都 610065）

一種基于LEAP安全架構的分布式分簇算法

余穩(wěn)定，梁剛

（四川大學計算機學院，成都 610065）

由于無線傳感器網(wǎng)絡本身的脆弱性，使其很容易遭受各種攻擊，包括節(jié)點偽裝攻擊、簇首占據(jù)攻擊、簇成員惡意征募攻擊、多重簇成員身份攻擊等。針對現(xiàn)有分簇協(xié)議所面臨的安全威脅，基于LEAP安全框架和基站認證簇首成員列表技術提出一種安全分布式分簇協(xié)議，并解決DSCP協(xié)議中個別簇首節(jié)點過早死亡問題和節(jié)點單一入簇問題。實驗表明，該算法能有效抵擋現(xiàn)有的WSN攻擊，同時又能有效控制能耗問題。

分簇協(xié)議；廣播認證；SPINS協(xié)議；LEAP協(xié)議；安全

0 引言

近年來，隨著微電系統(tǒng)和無線通信技術的發(fā)展，無線傳感器網(wǎng)絡被大規(guī)模部署，應用在環(huán)境監(jiān)測、軍事安全、交通管制、社區(qū)安防、森林防火等方面。由于傳感節(jié)點大多被部署在無人照看或者敵方區(qū)域，傳感器網(wǎng)絡安全問題尤為突出。事實上，缺乏有效的安全機制已經(jīng)成為無線傳感器網(wǎng)絡應用的主要障礙[1～4]。

由于無線傳感器網(wǎng)絡是由大量存儲空間小、運算能力弱、電池供電的傳感器節(jié)點組成，為了節(jié)省能量、提高網(wǎng)絡通信效率和大規(guī)模網(wǎng)絡下的可擴展性，無線傳感器網(wǎng)絡一般組織以成簇的拓撲結(jié)構方式工作。分簇使得拓撲結(jié)構有利于分布式算法的應用，適合大規(guī)模部署的網(wǎng)絡。由于大部分節(jié)點僅與簇首通信，且在簇首控制下切換睡眠與通信調(diào)度，所以可以顯著地節(jié)省能量，延長了整個網(wǎng)絡的生存時間。然而這種能量有效的簇拓撲控制方式，亦不可避免遭受外部攻擊和內(nèi)部攻擊，包括節(jié)點偽裝攻擊、簇首占據(jù)攻擊、簇成員惡意征募攻擊、多重簇成員身份攻擊等，使得基于簇拓撲結(jié)構的網(wǎng)絡應用無法正常工作，因此保障簇拓撲結(jié)構的安全性至關重要。本文針對現(xiàn)有分簇協(xié)議的安全問題，基于LEAP[10]安全框架，提出了一種安全的分布式分簇協(xié)議。在網(wǎng)絡初始化階段，使用LEAP安全框架生成鄰居共享密鑰對和安全鄰居列表。在簇首選擇階段，簇首的有效性須被驗證，并引入隨機變量，使得在每輪協(xié)議執(zhí)行之前，簇首節(jié)點不可預知，即阻止了簇首偽裝攻擊和簇首占據(jù)攻擊。而且，簇首選擇時考慮了節(jié)點的剩余能量，剩余能量高的節(jié)點優(yōu)先成為簇首，極大地延長了整個網(wǎng)絡的生存時間。在成員節(jié)點入簇階段，利用基站認證簇首成員列表技術，解決了節(jié)點單一入簇問題，阻止了多重簇成員身份攻擊。

1 相關工作

研究人員針對簇拓撲結(jié)構組織下的無線傳感器網(wǎng)絡的通信能耗、負載均衡等性能優(yōu)化問題，提出了多種有效的分簇算法，如LEACH[5]、HEED[6]、EECS[7]等協(xié)議，但是這些分簇協(xié)議在設計時并沒有考慮傳感器網(wǎng)絡面臨的安全問題。而安全性在無線傳感器網(wǎng)絡的實際應用中至關重要，這是因為網(wǎng)絡部署環(huán)境開放性和節(jié)點資源有限性使得傳感器網(wǎng)絡面臨著各種嚴重的攻擊威脅[1～2]。

鑒于已有分簇協(xié)議的安全性問題，研究人員開始注重安全分簇協(xié)議的研究。Ferreira等人擴展了LEACH協(xié)議[5]，提出抵御外部攻擊的安全分簇機制[14]，但是沒有解決成員節(jié)點加入簇首的注冊消息認證問題[11]。O1iveria等人引入隨機密鑰分布機制，使成員節(jié)點與簇首節(jié)點以一定概率共享密鑰來完成簇首的認證，與簇首沒有共享密鑰的節(jié)點成為孤立節(jié)點或者直接與基站通信。然而，這里存在與文獻[14]同樣的問題[11]。余磊等人在文獻[11]中提出了一種分布式安全分簇協(xié)議（本文以下均稱之為DSCP協(xié)議），通過網(wǎng)絡安全初始化、可信基站的隨機數(shù)廣播和單向密鑰鏈技術可以有效地抵御節(jié)點偽裝和簇首占據(jù)攻擊、簇成員惡意征募攻擊和多重簇成員身份攻擊。但是在簇首選擇階段并沒有考慮到節(jié)點剩余能量問題，導致部分節(jié)點可能過早死亡，而且成員節(jié)點向簇首注冊認證時采用的鄰居節(jié)點一次轉(zhuǎn)發(fā)技術不能解決節(jié)點本身處于兩個簇首一跳鄰居范圍的注冊認證問題。

2 安全分簇算法

本文算法流程見圖1，共分為三個階段：網(wǎng)絡初始化階段、簇首選舉階段和成員節(jié)點入簇階段?？紤]到負載均衡，分簇協(xié)議按輪周期性執(zhí)行，即定期重新建簇并選擇新的簇首。

2.1 網(wǎng)絡初始化

網(wǎng)絡安全初始化是安全成簇的基礎，也是構成整個安全網(wǎng)絡的前提，網(wǎng)絡初始化過程用于建立安全分簇所需的基本安全信息，包括鄰居節(jié)點發(fā)現(xiàn)、與鄰居共享的成對密鑰建立和初始單向認證密鑰鏈生成。

在節(jié)點部署之前，每個節(jié)點i預載入初始密鑰kI和與基站共享的成對密鑰ki。在網(wǎng)絡初始化階段啟動后，每個節(jié)點利用文獻[10]的LEAP密鑰生成算法，計算與每個鄰居節(jié)點的成對密鑰ki，j，用于簇生成階段和數(shù)據(jù)收集階段安全通信；鄰居發(fā)現(xiàn)過程完成之后，節(jié)點刪除初始密鑰kI，防止網(wǎng)絡初始化后惡意節(jié)點的加入，即阻止簇成員惡意征募攻擊。

另外，每個節(jié)點i使用單向散列函數(shù)H，計算長度為L+1的單向密鑰鏈CHAIN_0，用于節(jié)點入簇階段普通節(jié)點對簇首通知報文有效性的認證，阻止簇首占據(jù)攻擊。

2.2 簇首選舉過程

圖1 安全分簇算法流程圖

其中，R為一隨機數(shù)，是在每輪分簇協(xié)議開始執(zhí)行之前，基站用μTESLA廣播認證機制向全網(wǎng)廣播的隨機數(shù)，協(xié)助簇頭的隨機選舉；f是一值域為[0，1]偽隨機函數(shù)；Cprob為預先決定的簇頭比例，0＜Cprob＜1。

當不等式（2）成立時，節(jié)點選擇自己作為本輪的候選簇首，否則，在本輪分簇協(xié)議執(zhí)行過程中，自己作為普通成員節(jié)點，并置is_CH為FALSE。

對于候選簇首，繼續(xù)執(zhí)行以下操作：

①節(jié)點i使用C1uster Key[8]cki廣播簇首競爭報文，HEAD_COMPETE_MSGi={HEAD_COMPETE，i，remained _en，MAC（cki，HEAD_COMPETE|i|remained_en）}。

②設置簇頭競爭定時器Timerc，接收鄰居節(jié)點j的簇頭競爭報文。

HEAD_COMPETE_MSGj，0≤j≤Nnbri

③如果參與簇頭競爭的鄰居節(jié)點的剩余能量大于自己的剩余能量，則節(jié)點自己放棄簇頭競爭，置is_CH=FALSE，否則，一直等待接收競爭報文，直到定時器Timerc時間耗完。

④Timerc時間后，如果is_CH=TRUE，則表明節(jié)點此次競爭簇頭成功，節(jié)點成為簇首，并開始廣播簇首通知報文。

如果is_CH=FALSE，則表明節(jié)點此次競爭簇頭失敗，節(jié)點成為普通節(jié)點，等待接受簇首節(jié)點的簇首通知報文。

2.3 節(jié)點入簇階段

在簇首通知報文廣播過程中，攻擊者可以偽造簇首通知報文以假冒簇首節(jié)點。因此在廣播過程中，收到簇首通知報文的節(jié)點必須對報文的合法性進行驗證。

本文認證方案采用余磊等人[11]提出的單向密鑰鏈簇首身份認證技術，具體實現(xiàn)如下：

節(jié)點從收到的多個合法簇首報文中，利用文獻[7]的節(jié)點入簇權重函數(shù)，計算出權重最大的節(jié)點作為自己的簇首，并廣播成員注冊報文。MEMBER_JOIN_MSGi={MBR_JOIN，j，MAC（ki，j，MBR_JOIN|j）}，其中ki，j為節(jié)點i和簇首j的成對密鑰。

在成簇階段，非簇首的惡意節(jié)點可以發(fā)動多重簇成員身份攻擊，污染多個簇內(nèi)數(shù)據(jù)，使收集的聚合數(shù)據(jù)偏離正確數(shù)據(jù)最大化，所以必須保證一個節(jié)點只能加入一個簇。

考慮到文獻[12]的鄰居節(jié)點一次轉(zhuǎn)發(fā)技術和文獻[11]中的鄰居節(jié)點一次承諾技術不能解決節(jié)點本身處于兩個簇首一跳鄰居范圍的注冊認證問題，本文采用基站認證簇首成員列表技術來解決節(jié)點單一入簇問題。即，節(jié)點入簇階段完成以后，簇首節(jié)點采用μTESLA廣播認證機制把自己的成員節(jié)點序列發(fā)送給基站，由基站判斷有沒有節(jié)點同時加入多個簇范圍，如果有，則基站通知相應節(jié)點并作出處理。

3 協(xié)議執(zhí)行與分析

本文實驗使用文獻[13]中介紹的射頻能耗模型。發(fā)送1比特數(shù)據(jù)到距離d，其射頻能量消耗如下所示：

接收l比特數(shù)據(jù)，能量消耗為:

實驗參數(shù)取值如下：

表1 參數(shù)取值

文獻[9，10]表明RC5加密算法能夠很好地應用在無線傳感器網(wǎng)絡中，所以本文采用RC5算法作為加密算法。為減少對存儲空間的需求，本文中的偽隨機函數(shù)f、單向哈希函數(shù)H、消息認證碼MAC函數(shù)均采用RC5算法的RC5-MAC加密算法。

通過OMNeT++平臺仿真，表明本文算法在保證了節(jié)點信息安全性的同時，能耗亦能得到有效控制。如圖2，反映了隨著時間（迭代次數(shù)）的推移整個網(wǎng)絡死亡節(jié)點數(shù)平穩(wěn)上升，且相對DSCP協(xié)議第一個死亡節(jié)點出現(xiàn)的時間明顯推遲，說明本文對DSCP算法的改進有明顯效果。

3.1 安全性分析

在傳感器節(jié)點被部署后，每個節(jié)點根據(jù)內(nèi)置的初始密鑰kI、偽隨機函數(shù)f和節(jié)點ID計算出自己的主密鑰kim?；谥髅荑€kim，在鄰居發(fā)現(xiàn)過程中，節(jié)點生成與鄰居節(jié)點通信的共享密鑰對ki，j。因為在節(jié)點被部署后的Tmin時間內(nèi)整個網(wǎng)絡是安全的[10]，即此時還沒有攻擊者向網(wǎng)絡添加惡意節(jié)點，而鄰居發(fā)現(xiàn)過程所需時間Test小于Tmin，所以節(jié)點生成的鄰居列表中無惡意節(jié)點。當節(jié)點刪除初始密鑰kI后，致使鄰居發(fā)現(xiàn)過程不可重現(xiàn)，即無法再在網(wǎng)絡中添加新的節(jié)點。雖然這樣犧牲了整個網(wǎng)絡的動態(tài)擴展性，但保證了在整個網(wǎng)絡生命周期內(nèi)，每個節(jié)點的鄰居列表的安全性，防止了在網(wǎng)絡初始化后惡意節(jié)點的動態(tài)加入。

圖2 隨著時間推移網(wǎng)絡中死亡的節(jié)點數(shù)

3.2 存儲與通信開銷分析

在這里，本文以DSCP協(xié)議為基準，詳細分析本文算法的存儲開銷與通信開銷。

由于安全認證機制是本文算法存儲空間的主要開銷，而本文算法采用DSCP協(xié)議的密鑰鏈認證，所以本文的存儲開銷與其存儲開銷保持一致。即在網(wǎng)絡初始化后，每個節(jié)點需要存儲鄰居列表和與鄰居共享的成對密鑰。在協(xié)議運行期間，每個節(jié)點存儲一個長度為L+1密鑰鏈和所有鄰居節(jié)點的密鑰鏈承諾。而適當?shù)剡x擇鄰居發(fā)現(xiàn)通信功率和密鑰鏈長度，可以有效地控制用于存儲鄰居節(jié)點相關信息和認證密鑰鏈地空間。至于鄰居發(fā)現(xiàn)功率和密鑰鏈長度的實際取值，要取決于整個無線傳感器網(wǎng)絡的大小和傳感節(jié)點存儲空間等因素。

至于通信開銷，本文算法與DSCP協(xié)議有所不同，因為本文算法的簇頭選擇和節(jié)點入簇機制不同于DSCP協(xié)議，DSCP協(xié)議的簇頭選擇機制沒有考慮節(jié)點能量問題，個別節(jié)點可能會頻繁擔當簇頭，從而導致這些節(jié)點過早死亡，本文算法解決了這個問題（見圖2），但是通信開銷有所增加。

假設傳感器節(jié)點總數(shù)為n，則編碼整個網(wǎng)絡傳感器節(jié)點只需1og2n比特位，即節(jié)點ID長度為「1og2n/8?字節(jié)。另外，假設量化節(jié)點能量表示需要Len字節(jié)，安全協(xié)議的密鑰長度為Lkey字節(jié)，消息認證碼長度為Lmac字節(jié)，認證密鑰鏈號長度和當前密鑰序號長度分別為Lchain和Lserial字節(jié)。在不考慮報文類型開銷（實際通信中，可嵌入到節(jié)點ID的高位中，減少通信報文長度）情況下，本文算法具體通信開銷如下：

（1）網(wǎng)絡初始化

初始化階段主要完成鄰居節(jié)點發(fā)現(xiàn)和與鄰居共享的成對密鑰建立，本文網(wǎng)絡初始化階段與DSCP協(xié)議保持一致，見文獻[11]。

（2）簇首選舉過程

簇首選舉過程能量消耗在于發(fā)送簇首競爭報文和簇首通知報文，所以：

（3）節(jié)點入簇階段

不考慮多重身份攻擊情況下，普通節(jié)點該階段只需向簇首發(fā)送成員節(jié)點注冊報文注冊自己。

綜上所述，本文與DSCP通信開銷之差：

而ΔEmemJoin表示兩者算法節(jié)點在入簇階段能量消耗之差區(qū)別在于文獻[11]的節(jié)點入簇采用的是向鄰居節(jié)點注冊認證，而本文采用的是基站認證方式，即通信功率的有所不同，但是前者需要鄰居節(jié)點繼續(xù)轉(zhuǎn)發(fā)報文，又加大了這部分通信開銷，而本文不需要轉(zhuǎn)發(fā)報文，所以入簇通信開銷之差可以不考慮。

4 結(jié)語

本文借鑒LEACH[5]、HEED[6]和EECS[7]等傳統(tǒng)分布式分簇協(xié)議的分簇思想和文獻[9～12]等的節(jié)點安全認證思想，提出了一種安全的、能量消耗在控制范圍的成簇算法。并基于已有的能量消耗模型，利用OMNeT++平臺仿真了本文算法的執(zhí)行，結(jié)果表明本文算法對DSCP協(xié)議能耗問題有明顯改進（如圖1，第一個死亡節(jié)點時間明顯推遲）。但本文算法仍有很多不足，在未來的研究中，將考慮解決成員節(jié)點入簇階段的合伙攻擊，并進一步優(yōu)化本文算法，使算法能耗更低。

[1] Perrig A，et a1.Security in Wire1ess Sensor Networks[J].Communications of the ACM，2004，47（6）:53～57

[2] Fei H，Neeraj K.Security Considerations in Ad Hoc Sensor Networks[J].Ad Hoc Networks，2005，1（3）:69～89

[3] Xu-xun Liu.A Survey on C1ustering Routing Protoco1s in Wire1ess Sensor Networks，Sensors 2012（12），11113～11153

[4] Kema1 Akkaya.A Survey on Routing Protoco1s for Wire1ess Sensor Networks.Ad Hoc Networks 3，2005：325～349

[5] Heinze1man，W.，Chandrakasan，A.and Ba1akrishnan，H.Energy-Efficient Communication Protoco1 for Wire1ess Microsensor Networks. Proceedings of the 33rd Internationa1 Conference on System Sciences（HICSS'00）

[6] Younis，O.and Fahmy，S.HEED:A Hybrid，Energy-Efficient.Distributed C1ustering Approach for Ad Hoc Sensor Networks.IEEE Transactions on Mobi1e Computing，2004，3（4）：660～669

[7] Ye，M.，Li，C.，Chen，G.，Wu，J.EECS:An Energy Efficient C1ustering Scheme in Wire1ess Sensor Networks.In Proceedings of the 24th IEEE Internationa1 Performance，Computing，and Communications Conference（IPCCC），Phoenix，AZ，USA，7～9 Apri1 2005：535～540

[8] 裴慶祺.無線傳感器網(wǎng)絡安全技術綜述.Journa1 on Communications，2007，28（8）：113～121

[9] PERRIG A，et a1.SPINS:Security Protoco1s for Sensor Networks[J].Wire1ess Networks Journa1（WINE），2002，8（5）:521～534

[10] Zhu S，Setia S，Jajodia S.LEAP:Efficient Security Mechanisms for Large-Sca1e Distributed Sensor Networks.In:Proc.of the 10th ACM Conf.on Computer and Communications Security.Washington:ACM Press，2003：62～72

[11] 余磊.一種無線傳感器網(wǎng)絡分布式安全成簇協(xié)議.Journa1 of Software，2009，20（10）：2705～2720

[12] Kar1of C，Wagner D.Secure Routing in Wire1ess Sensor Networks:Attacks and Countermeasures.Ad Hoc Networks，2003，1（1）: 293～315

[13] Heinze1man，W.，Chandrakasan，A.，Ba1akrishnan，H.An App1ication-Specific Protoco1 Architecture for Wire1ess Microsensor Networks.IEEE Transactions on Wire1ess Communications，2002，1（4）：660～669

[14] Ferreira AC，Vi1aca MA，O1iveira LB，Habib E，Wong HC，Loureiro AA.On the Security of C1uster-Based Communication Protoco1s for Wire1ess Sensor Networks.In:Proc.of the 4th IEEE Int'1 Conf.on Networking.LNCS 3420，Reunion Is1and:Springer-Ver-1ag，2005：449～458

[15] O1iveria L，Wong H，Bern M，Dahab R，Lourerio F.SecLEACH-A Random Key Distribution So1ution for Securing C1ustered Sensor Networks.In:Proc.of the 5th IEEE Int'1 Symp.on Network Computing and App1ications.Cambridge:IEEE Computer Society，2006：145～154

A Distributed Clustering Algorithm Based on LEAP Security Architecture

YU Wen-ding，LIANG Gang
（Co11ege of Computer Science，Sichuan University，Chengdu 610065）

Due to the fragi1ity of the wire1ess sensor network itse1f,it is very vu1nerab1e to various attacks,inc1uding node feinting,occupy the attack of c1uster head,c1uster member of ma1icious attacks,mu1tip1e c1uster membership recruitment attack,etc.In view of the existing c1ustering protoco1 security threats,and based on LEAP security framework and base station authentication 1ist techno1ogy,proposes a secure distributed c1ustering protoco1,and so1ves the prob1em of the premature death of individua1 c1uster head nodes and sing1e node in one c1uster in the DSCP protoco1.Experiments show that the proposed a1gorithm can effective1y resist the existing WSN attack,and can effective1y contro1 the energy consumption prob1em at the same time.

C1ustering Protoco1s;Broadcast Authentication;SPINS Agreement;LEAP Agreement;Security

1007-1423（2015）05-0010-06

10.3969/j.issn.1007-1423.2015.05.002

余穩(wěn)定（1989-），男，安徽六安人，碩士，研究方向為網(wǎng)絡安全

梁剛（1976-），男，四川人，博士，講師，研究方向為網(wǎng)絡安全

2014-12-18

2015-01-20