無線傳感網中兼顧多因素的簇頭選擇算法

張冬旭，秦 智

(成都信息工程學院信息安全工程學院，四川成都610225)

0 引言

近年來，無線傳感網絡(Wireless Sensor Network，WSN)技術廣泛應用于軍事、環境觀測及預報、醫療護理、智能家居、建筑狀態檢測等多個物聯網領域[1]。WSN是一種由眾多的低功耗、低成本的傳感器節點組成的大規模動態性自組織網絡，這些傳感器節點體積微小且分布廣泛，同時也存在著一些限制如電源能力有限、計算和存儲能力有限和通信能力有限等。傳感器節點的部署環境復雜，加上這些限制就導致它容易受到攻擊，存在眾多的安全隱患。因此，需要有效的措施來提高無線傳感網絡的安全性。

網絡的拓撲控制具有重要的意義，基于簇結構的拓撲控制有利于分布式算法的應用，分簇結構中選舉出簇頭節點來擔任數據融合的任務，減少了數據通信量。已經有多種算法提出，LEACH算法[2]是一種自適應分簇拓撲算法，以循環的方式選擇簇頭節點，使各節點都可以等概率地擔任簇頭節點，保證網絡能量相對均衡[3];PEGASIS 算法[4]是在 LEACH 算法基礎上的一種改進算法，網絡中所有節點成一個簇，節點只與它最近的節點通信，從而減少能量損耗，延長網絡生命周期[5];GAF算法[1]則是定期地選舉出一個簇頭節點，只有簇頭節點保持活動，其他進入休眠狀態以節省能量。以上這些算法都是基于能量因素提出的算法，同時目前大多的簇頭選擇算法都主要考慮能量損耗問題，而很少考慮到其他因素。文獻[6]提出一種WSN中兼顧安全和剩余能量的簇頭選擇方法，該算法有了很大改進，綜合考慮到節點信任和剩余能量因素，但是沒有考慮到通信、數據等因素。在此基礎上對此算法進行改進，綜合考慮節點信任度、通信、能量以及數據因素，提出一種兼顧多因素的簇頭選擇算法，使之更全面更適應無線傳感網。

1 相關算法及研究

1.1 LEACH算法

LEACH(Low Energy Adaptive Clustering Hierarchy)協議的簇頭選擇算法是分布式的，是一種自適應的分簇拓撲算法，周期性地執行該過程，并且沒有節點可以對簇頭的選擇進行決定或者協調，每個節點獨立自主運行簇頭選舉算法并決定是否成為簇頭。每輪選舉可以分為建立簇階段和數據傳輸階段[7]。在每一輪簇頭選舉成功后，簇頭向周圍的節點公布消息，其他節點開始加入簇，然后開始進入穩定數據傳輸階段[8]。簇頭收到各節點的數據后進行數據融合，并且與匯聚節點通信，簇頭節點會消耗能量很大，因此隔一段時間就要進行新一輪的簇頭選舉來保持網絡能量的均衡[9]。

簇頭選舉時，每個節點都會生成一個在區間[0，1]內的隨機數，設定一個閥值T(n)，如果該隨機數小于T(n)，就發布自己是簇頭的公告。

其中，p為簇頭節點在所有節點中所占的百分比，r為當前簇頭選舉的輪次，G為一個節點集合，其中包含所有在最近的1/p次簇頭選舉中都未曾當選為簇頭的節點。

LEACH協議中簇頭節點的算法可以在一定程度上平衡網絡的負載，從而延長網絡壽命。同時簇頭在處理數據時使用數據融合及壓縮的技術，大大減少數據傳輸量。但是LEACH算法仍然存在一些不足，每個節點都等概率的成為簇頭節點，沒有考慮到節點的剩余能量。若剩余能量不足的節點成為簇頭，則其能量會很快耗盡。因為選擇的隨機性，容易出現簇與簇之間簇頭數目分布不均勻，該選舉方法無論從數量還是分布位置上都不夠穩定。

1.2 簇頭選擇考慮因素

簇頭節點對于分簇拓撲結構網絡來說相當重要，負責調節簇內節點的工作，數據的融合及轉發、與匯聚節點通信等工作，能量消耗較大，因此簇頭的選擇也要考慮多方面的因素才能保證整個無線傳感網絡的正常運行。簇頭選舉需要考慮以下幾個因素。

1.2.1 節點信任度

無線傳感器節點由于體積、內存、計算能力較小、通信范圍有限，無法建立整個無線傳感網的全局信任模型，一般只與其鄰居節點交互，只需對其鄰居節點信任度進行評估，建立局部信任[10]。節點信任值又分為兩部分:一部分是直接信任值，即源節點根據自身與目標節點[11]直接交互的經驗計算所得的信任值;另外一部分是間接信任值，即源節點通過推薦節點對目標節點的監控得到的間接信任值。某一節點的信任值需要將其所有鄰居節點對它的信任值綜合起來得到。信任關系如圖1所示，節點i和j為鄰居節點，節點j與p、q、m、n都互為鄰居節點。

圖1 直接信任與間接信任

1.2.2 通信因素

無線傳感網中，惡意節點極有可能會丟棄或者篡改接收到的數據包，對網絡安全及能量的正常使用造成威脅。而自私節點只在有自身需求時才加入網絡以節省自身能量，平時不理會網絡路由的需要，導致網絡能量消耗量不均衡，從而影響網絡壽命[12]。根據歷史通信的失敗與成功，可以來預測未來通信的成敗，觀察節點間的通信行為可以為惡意節點和自私節點的判斷提供重要參考依據。

1.2.3 能量因素

傳感器節點的能量很有限，而能量又決定了整個無線傳感器網絡的生命周期，因此能量的高效利用是簇頭選擇的一項重要因素。傳感器節點需要進行數據的接收、傳輸和轉發，若能量不足甚至耗盡，將會給網絡正常運行帶來重大影響。

為使數據傳輸過程中整個網絡能量均衡消耗，無線傳感網通常會采用能量多路徑路由機制，這樣就可以延長網絡的生存周期。在多徑傳播方式中能量的消耗與節點之間的距離成指數關系，并且發送與接收數據時消耗能量的計算方法也不同[13]。

發送數據時能量消耗Ec為

其中，發送的數據大小為l，d為兩節點之間的距離，Eelec為發射電路的單位能耗，εamp和famp為發射放大器的單位能耗。為距離閥值，當發送數據的距離小于該閥值時，發射放大器的消耗能量與距離的平方成正比;當距離大于等于該閥值，能耗則與距離的四次方成正比，因此在發送數據過程中，應盡量避免直接向遠距離的節點發送數據來節約能耗[14]。

接收數據時能量消耗Er的計算公式為

其中，Erx為接收數據時的單位能耗，Er與接收數據的大小成正比。

1.2.4 數據因素

考慮到的數據因素包括:數據內容的大小以及數據的一致性。

無線傳感器網絡中需要傳輸大量數據，這就會消耗大量的能量。因此需要進行數據融合，即中間節點在對收到的數據進行轉發前，先對其進行綜合并去掉冗余數據，以節省傳輸能量并提高數據收集效率[1]。可設置一個數據閥值，接收數據與這個閥值相差越大則可信度的波動就會越大，以此來判斷接收到數據的準確性。

同時，數據的一致性也是評估節點可信度的重要因素，通過檢查數據的一致性來計算數據信任值。對數據內容的一致性進行評估，偏差越大則數據信任值越低;反之，偏差越小則數據信任值越高。

通過對數據信任值的評定，可以及時發現自私節點，以采取相關的安全措施來保障無線傳感網絡的數據安全。

2 算法描述

文中提出的兼顧多因素的簇頭選擇算法流程如圖2所示。

圖2 兼顧多因素的簇頭選擇算法流程圖

2.1 節點信任度計算

(i)節點Ni和Nj是鄰居節點，Ni對Nj的直接信任TDij是通過Nj對Ni的數據包轉發率來衡量的 (dr為接收轉發的包的數目，dt是實際轉發的包數)

(ii)節點Ni對Nj的間接信任度通過Nj的鄰居節點Nm的監控得到。定義P為其他推薦節點的集合，P={Nm|Ni的鄰居節點，Tij≥信任推薦值Th}，P中所有節點對Nj的信任值加權平均，得到Ni對Nj的間接信任度

(iii)節點Ni對Nj的信任值為

其中，α表示TDij在信任值計算中所占權重，通過改變α的大小可以改變TDij和Mij二者的比例。

(iv)節點Nj的綜合信任值Tj計算，通過計算Nj的所有鄰居節點對它的信任值的均值得到，即

其中k為節點Nj的鄰居節點的總個數。

2.2 通信信任值

β模型[15]利用節點過去的通信成功和失敗的記錄，通過計算預計未來通信成功的概率。兩相鄰節點Ni和Nj進行多次通信，使用β模型表示這兩個節點間通信成功的概率，該模型概率密度函數為

其中，0＜x＜1，α ＞0，β ＞0。

該信任模型的期望公式為

假設節點Nj和Ni進行n次通信后，統計得到成功通信次數為Sji，失敗次數為fji，由公式(6)可得節點Nj對Ni可信的期望值為

則該模型中，對下次通信的期望就是此次通信的信任值

綜合Nj與其鄰居節點多次通信的信任值，求和取均值，可得到該節點的通信信任值

2.3 能量信任值

節點Nj的現存能量為Ej，初始能量為E0，剩余能量比Hj為

節點在接下來一段通信過程中接收、發送及處理數據所需的能量為en，同時令Te=en/Ej，則有

則節點能量信任值Cj的計算公式為

其中p和q分別為Hj和Ij的所占權重，且p+q=1，由式(15)可以看出節點能量信任值Cj由剩余能量比Hj和Ij共同決定。

2.4 數據信任值

設置的數據信任值由兩個內容決定:數據大小信任值和數據一致性信任值。

傳輸數據過大，則會消耗過多能量，并且容易被利用攻擊，導致網絡危險;而數據過小則有可能是自私節點為了節省自身能量而選擇丟包[13]。為了節省能量，延長網絡壽命的同時保證網絡的安全，設置一個數據傳輸的閥值Ds，以此為數據大小的界限，綜合經節點Nj發送給節點Ni的數據，其數據大小信任值DSji為

算出由節點Nj發送給它的所有鄰居節點的數據的信任值，求出均值，則得到節點Nj的數據大小信任值

節點Nj采集數據一致的次數為Uj，數據采集不一致的次數為Vj，則節點Nj的數據一致性信任值DAj的計算方法為

綜合以上兩種信任值，在數據信任值的計算中，數據大小信任值所占權重為m，數據一致性信任值所占權重為n，且m+n=1，則有Nj的數據信任值

2.5 節點綜合因子

節點Nj的綜合因子需要考慮多種因素，節點信任度、通信、能量及數據因素，將以上幾個方面整合起來就得到傳感器節點的綜合因子

其中，a、b、c和d都為權重因子，計算節點綜合因子時按各個因素的重要程度來選擇其大小，某因素權重因子越大則表示該因素越重要，且有(a+b+c+d)=1。設定一個因子閥值Ws，一旦節點能量耗盡或者綜合因子小于該閥值，則自動被當作死亡節點處理。

2.6 簇頭選擇

綜合因子計算出來后，根據各個節點的綜合因子值進行簇頭選擇。設定綜合因子的閥值Wn，一旦某節點綜合因子低于該閥值，則默認為是惡意節點，同時也被定義為死亡節點。而綜合因子越大的節點越可信，按照簇頭節點在該簇內所占比例p，算出簇頭節點的個數p×n，再選擇綜合因子Wj大的節點擔任簇頭。

3 仿真實驗

仿真實驗通過Java代碼和MATLAB來實現。實驗中，在200 m×200 m空間內隨機選取100個節點，模擬無線傳感網的通信，通過每個輪次的通信，觀察節點的信任度、通信信任值、剩余能量比以及數據信任值。該實驗中選取節點信任度權重a為30%，通信信任值權重b為20%，剩余能量比權重c為30%，數據信任值權重d為20%，最后通過計算算得節點的綜合因子。實驗中其他的參數設定如表1所示。

表1 基本參數設定

實驗1:基于文中的信任模型，分別對網絡中的某一個正常節點和非正常節點的綜合因子的變化情況進行監控。

圖3 正常節點綜合因子變化圖

圖4 非正常節點綜合因子變化圖

選取該網絡中某一正常節點，其綜合因子變化情況如圖3所示。由于能量消耗，該節點正常通信情況下，綜合因子數值呈緩慢下降趨勢。非正常節點的綜合因子的變化如圖4所示，一旦節點產生惡意行為例如傳送數據過大或過小，就會導致節點綜合急速下降。因此該模型可以很好的區別出正常節點和惡意節點。

實驗2:比較兩種算法的網絡生存周期。

如圖5所示，數據1代表的是僅考慮節點信任度和剩余能量比時的網絡生存周期;數據2則代表使用文中兼顧多因素的算法時的網絡生存周期。分別使用兩種算法，進行500輪通信，觀察存活節點的個數變化。通過圖示的對比可以看到，文中所描述的算法使得網絡生存周期延長了近20%。從而證明使用該算法可以延長網絡生存周期。

圖5中，在剛開始的幾輪通信中數據2的圖像迅速下降，說明開始幾輪通信就出現了節點死亡，而死亡的節點就是惡意節點，說明本算法中惡意節點在剛進行一點惡意行為后就被檢測出來，從而增強了網絡的安全性。

實驗證明該算法的實用性以及安全性。

圖5 節點生存周期圖

4 結束語

在借鑒現有的信任模型及簇頭選擇算法的基礎上，提出一種適用于無線傳感網的兼顧節點信任度、通信、剩余能量比以及數據多因素的簇頭選擇算法。與只考慮信任與能量的簇頭選擇算法相比，新的算法有效延長了網絡生存周期，同時可以在開始通信不久就識別出惡意節點，大大增強了網絡的安全性。考慮到多種因素的簇頭選擇算法，為無線傳感網中的信任評價提供一種新的思路，但是該算法在安全性上仍需要進一步的考慮，同時對網絡能量消耗、算法的復雜性和算法計算時消耗能量問題應有更多考慮，這就是下一步要進行的研究工作。

致謝:感謝成都市科技攻關項目(2014-HM01-00108-SF)對本文的資助

[1] 孫利民，李建中，陳渝，等.無線傳感器網絡[M].北京:清華大學出版社，2005:90－100.

[2] 林楠，史葦杭.無線傳感器LEACH算法的優化及仿真[J].計算機仿真，2011，28(1):178－181.

[3] Heinzelman W B，Chandra K A，Bala K H.An Application-specific Protocol Architecture for Wireless Micro-sensor Networks[J].IEEE Transactions on Wireless Communications，2002，1(4):660－670.

[4] 張震，閆連山，潘煒，等.基于 LEACH和 PEGASIS的簇頭成鏈可靠路由協議研究[J].傳感技術學報，2010，23(8):1173－1178.

[5] Lindsey S，Raghavendra C，Sivalingam K M.Data Gathering Algorithms in Sensor Networks Using Energy Metrics[J].IEEE Trans on Parallel and Distributed Systems，2002，13(9):924－935.

[6] 周立朋，卡米力·木衣丁.WSN中兼顧安全和剩余能量的簇頭選擇算法[J].計算機工程與應用，2012，48(3):88－90.

[7] 陳云峰，范興剛，許博.基于LEACH的WSN簇頭優化策略[J].計算機工程，2011，37(22):82－87.

[8] 王偉超，代增全，徐啟建.LEACH協議簇頭選擇算法的改進[J].無線電工程，2010，40(3):1－3.

[9] 張浩，李臘元.基于LEACH協議的能耗均衡路由算法[J]. 計算機工程，2011，37(7):91－93，111.

[10] 孫秋景，曾平凡，曹勇.基于可信推薦節點集合的P2P信譽模型[J].計算機工程，2010，36(20):142－144.

[11] 胡光明，胡華平，龔正虎.簇結構移動自組網絡中基于推薦的局部信任模型[J].計算機工程與應用，2006，29:16－22.

[12] 吳磊.無線傳感器網絡防范惡意節點信譽機制研究[D].重慶:重慶大學，2013.

[13] 張仕斌，陳建鈞，楊駿偉.WSNs中基于簇結構的云信任模型研究[J].四川大學學報:工程科學版，2014，(8):1－6.

[14] 劉艷飛.基于分層信任管理的無線傳感器網絡信任模型[D].太原:太原理工大學，2015.

[15] 馮健昭，肖德琴，楊波.基于β分布的無線傳感器網絡信譽系統[J].計算機應用，2007，27(1):111－113.