無線傳感網(wǎng)中兼顧多因素的簇頭選擇算法

張冬旭，秦 智

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

0 引言

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

網(wǎng)絡(luò)的拓?fù)淇刂凭哂兄匾囊饬x，基于簇結(jié)構(gòu)的拓?fù)淇刂朴欣诜植际剿惴ǖ膽?yīng)用，分簇結(jié)構(gòu)中選舉出簇頭節(jié)點來擔(dān)任數(shù)據(jù)融合的任務(wù)，減少了數(shù)據(jù)通信量。已經(jīng)有多種算法提出，LEACH算法[2]是一種自適應(yīng)分簇拓?fù)渌惴?，以循環(huán)的方式選擇簇頭節(jié)點，使各節(jié)點都可以等概率地?fù)?dān)任簇頭節(jié)點，保證網(wǎng)絡(luò)能量相對均衡[3];PEGASIS 算法[4]是在 LEACH 算法基礎(chǔ)上的一種改進(jìn)算法，網(wǎng)絡(luò)中所有節(jié)點成一個簇，節(jié)點只與它最近的節(jié)點通信，從而減少能量損耗，延長網(wǎng)絡(luò)生命周期[5];GAF算法[1]則是定期地選舉出一個簇頭節(jié)點，只有簇頭節(jié)點保持活動，其他進(jìn)入休眠狀態(tài)以節(jié)省能量。以上這些算法都是基于能量因素提出的算法，同時目前大多的簇頭選擇算法都主要考慮能量損耗問題，而很少考慮到其他因素。文獻(xiàn)[6]提出一種WSN中兼顧安全和剩余能量的簇頭選擇方法，該算法有了很大改進(jìn)，綜合考慮到節(jié)點信任和剩余能量因素，但是沒有考慮到通信、數(shù)據(jù)等因素。在此基礎(chǔ)上對此算法進(jìn)行改進(jìn)，綜合考慮節(jié)點信任度、通信、能量以及數(shù)據(jù)因素，提出一種兼顧多因素的簇頭選擇算法，使之更全面更適應(yīng)無線傳感網(wǎng)。

1 相關(guān)算法及研究

1.1 LEACH算法

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

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

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

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

1.2 簇頭選擇考慮因素

簇頭節(jié)點對于分簇拓?fù)浣Y(jié)構(gòu)網(wǎng)絡(luò)來說相當(dāng)重要，負(fù)責(zé)調(diào)節(jié)簇內(nèi)節(jié)點的工作，數(shù)據(jù)的融合及轉(zhuǎn)發(fā)、與匯聚節(jié)點通信等工作，能量消耗較大，因此簇頭的選擇也要考慮多方面的因素才能保證整個無線傳感網(wǎng)絡(luò)的正常運行。簇頭選舉需要考慮以下幾個因素。

1.2.1 節(jié)點信任度

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

圖1 直接信任與間接信任

1.2.2 通信因素

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

1.2.3 能量因素

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

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

發(fā)送數(shù)據(jù)時能量消耗Ec為

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

接收數(shù)據(jù)時能量消耗Er的計算公式為

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

1.2.4 數(shù)據(jù)因素

考慮到的數(shù)據(jù)因素包括:數(shù)據(jù)內(nèi)容的大小以及數(shù)據(jù)的一致性。

無線傳感器網(wǎng)絡(luò)中需要傳輸大量數(shù)據(jù)，這就會消耗大量的能量。因此需要進(jìn)行數(shù)據(jù)融合，即中間節(jié)點在對收到的數(shù)據(jù)進(jìn)行轉(zhuǎn)發(fā)前，先對其進(jìn)行綜合并去掉冗余數(shù)據(jù)，以節(jié)省傳輸能量并提高數(shù)據(jù)收集效率[1]?？稍O(shè)置一個數(shù)據(jù)閥值，接收數(shù)據(jù)與這個閥值相差越大則可信度的波動就會越大，以此來判斷接收到數(shù)據(jù)的準(zhǔn)確性。

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

通過對數(shù)據(jù)信任值的評定，可以及時發(fā)現(xiàn)自私節(jié)點，以采取相關(guān)的安全措施來保障無線傳感網(wǎng)絡(luò)的數(shù)據(jù)安全。

2 算法描述

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

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

2.1 節(jié)點信任度計算

(i)節(jié)點Ni和Nj是鄰居節(jié)點，Ni對Nj的直接信任TDij是通過Nj對Ni的數(shù)據(jù)包轉(zhuǎn)發(fā)率來衡量的 (dr為接收轉(zhuǎn)發(fā)的包的數(shù)目，dt是實際轉(zhuǎn)發(fā)的包數(shù))

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

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

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

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

其中k為節(jié)點Nj的鄰居節(jié)點的總個數(shù)。

2.2 通信信任值

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

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

該信任模型的期望公式為

假設(shè)節(jié)點Nj和Ni進(jìn)行n次通信后，統(tǒng)計得到成功通信次數(shù)為Sji，失敗次數(shù)為fji，由公式(6)可得節(jié)點Nj對Ni可信的期望值為

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

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

2.3 能量信任值

節(jié)點Nj的現(xiàn)存能量為Ej，初始能量為E0，剩余能量比Hj為

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

則節(jié)點能量信任值Cj的計算公式為

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

2.4 數(shù)據(jù)信任值

設(shè)置的數(shù)據(jù)信任值由兩個內(nèi)容決定:數(shù)據(jù)大小信任值和數(shù)據(jù)一致性信任值。

傳輸數(shù)據(jù)過大，則會消耗過多能量，并且容易被利用攻擊，導(dǎo)致網(wǎng)絡(luò)危險;而數(shù)據(jù)過小則有可能是自私節(jié)點為了節(jié)省自身能量而選擇丟包[13]。為了節(jié)省能量，延長網(wǎng)絡(luò)壽命的同時保證網(wǎng)絡(luò)的安全，設(shè)置一個數(shù)據(jù)傳輸?shù)拈y值Ds，以此為數(shù)據(jù)大小的界限，綜合經(jīng)節(jié)點Nj發(fā)送給節(jié)點Ni的數(shù)據(jù)，其數(shù)據(jù)大小信任值DSji為

算出由節(jié)點Nj發(fā)送給它的所有鄰居節(jié)點的數(shù)據(jù)的信任值，求出均值，則得到節(jié)點Nj的數(shù)據(jù)大小信任值

節(jié)點Nj采集數(shù)據(jù)一致的次數(shù)為Uj，數(shù)據(jù)采集不一致的次數(shù)為Vj，則節(jié)點Nj的數(shù)據(jù)一致性信任值DAj的計算方法為

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

2.5 節(jié)點綜合因子

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

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

2.6 簇頭選擇

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

3 仿真實驗

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

表1 基本參數(shù)設(shè)定

實驗1:基于文中的信任模型，分別對網(wǎng)絡(luò)中的某一個正常節(jié)點和非正常節(jié)點的綜合因子的變化情況進(jìn)行監(jiān)控。

圖3 正常節(jié)點綜合因子變化圖

圖4 非正常節(jié)點綜合因子變化圖

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

實驗2:比較兩種算法的網(wǎng)絡(luò)生存周期。

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

圖5中，在剛開始的幾輪通信中數(shù)據(jù)2的圖像迅速下降，說明開始幾輪通信就出現(xiàn)了節(jié)點死亡，而死亡的節(jié)點就是惡意節(jié)點，說明本算法中惡意節(jié)點在剛進(jìn)行一點惡意行為后就被檢測出來，從而增強(qiáng)了網(wǎng)絡(luò)的安全性。

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

圖5 節(jié)點生存周期圖

4 結(jié)束語

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

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

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

[2] 林楠，史葦杭.無線傳感器LEACH算法的優(yōu)化及仿真[J].計算機(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的簇頭成鏈可靠路由協(xié)議研究[J].傳感技術(shù)學(xué)報，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].計算機(jī)工程與應(yīng)用，2012，48(3):88－90.

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

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

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

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

[11] 胡光明，胡華平，龔正虎.簇結(jié)構(gòu)移動自組網(wǎng)絡(luò)中基于推薦的局部信任模型[J].計算機(jī)工程與應(yīng)用，2006，29:16－22.

[12] 吳磊.無線傳感器網(wǎng)絡(luò)防范惡意節(jié)點信譽(yù)機(jī)制研究[D].重慶:重慶大學(xué)，2013.

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

[14] 劉艷飛.基于分層信任管理的無線傳感器網(wǎng)絡(luò)信任模型[D].太原:太原理工大學(xué)，2015.

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