基于模糊邏輯推理的WSNs非均勻分簇算法

楊健冬,王文娟

(鄭州工業(yè)應(yīng)用技術(shù)學(xué)院,河南 新鄭 451150)

?

基于模糊邏輯推理的WSNs非均勻分簇算法

楊健冬*,王文娟

(鄭州工業(yè)應(yīng)用技術(shù)學(xué)院,河南 新鄭 451150)

為了進(jìn)一步降低無線傳感網(wǎng)絡(luò)WSNs(Wireless Sensor Networks)能耗,拓延網(wǎng)絡(luò)壽命,提出了基于模糊邏輯推理的WSNs非均勻分簇算法,記為DUCF。DUCF算法充分考慮了節(jié)點剩余能量、節(jié)點度以及離基站距離。根據(jù)經(jīng)驗制定模糊規(guī)則,通過模糊推理系統(tǒng)得到節(jié)點當(dāng)選為簇頭的幾率和簇尺寸。DUCF算法形成非均勻簇,進(jìn)而平衡簇頭間的能量消耗。仿真結(jié)果表明,DUCF算法在網(wǎng)絡(luò)壽命、能量消耗方面的性能優(yōu)于LEACH、CHEF和EAUCF算法。

無線傳感網(wǎng);分簇;模糊邏輯推理;非均勻;剩余能量

隨著現(xiàn)代電子技術(shù)的發(fā)展,無線傳感網(wǎng)絡(luò)廣泛使用于各類應(yīng)用,如康復(fù)醫(yī)療、戰(zhàn)場、野外環(huán)境監(jiān)測等[-3]。由于無線傳感網(wǎng)絡(luò)常部署于野外惡劣環(huán)境,更換節(jié)點的電池是不現(xiàn)實的。因此,能耗成為無線傳感網(wǎng)絡(luò)的研究熱點。而相比于感測、處理數(shù)據(jù)階段,通信階段的數(shù)據(jù)傳輸消耗了更多的節(jié)點能量[4-5]。因此,通過提高數(shù)據(jù)匯聚、傳輸效率,可有效地節(jié)省節(jié)點能量。保存節(jié)點能量是非常重要的。一旦節(jié)點能量消耗殆盡,該節(jié)點將無法工作,此類節(jié)點也稱為失效節(jié)點。此類節(jié)點影響了網(wǎng)絡(luò)壽命。

為了存儲節(jié)點能量,常采用簇結(jié)構(gòu),即將鄰近節(jié)點或具有相同特性的節(jié)點匯聚成一個簇[6-7]。每個簇內(nèi)選擇一個節(jié)點作為簇頭,并由簇頭收集簇內(nèi)節(jié)點的感測數(shù)據(jù),經(jīng)融合后,再傳輸至基站。通過簇結(jié)構(gòu),降低網(wǎng)絡(luò)能耗。目前,研究人員提出不同的簇算法。這些算法在簇頭選擇或簇形成階段存在異同。LEACH[8]就是經(jīng)典的分布式簇算法。LEACH算法先計算閾值,然后產(chǎn)生一個隨機(jī)數(shù)。如果該數(shù)大于閾值,就稱為簇頭。這種簇頭產(chǎn)生策略存在隨機(jī)性,并沒有兼顧到節(jié)點個體特性。同時,LEACH算法也存在均勻簇的共性問題。

所謂均勻簇就是指所有簇內(nèi)的節(jié)點數(shù)都相等,反之,若簇內(nèi)節(jié)點數(shù)不相等,有大有小,稱為非均勻簇[9]。而文獻(xiàn)[10]提出非均勻簇算法EECS。EECS算法總是選擇節(jié)點能量最高的節(jié)點作為簇頭。盡管能量是無線傳感網(wǎng)絡(luò)的重要指標(biāo),但是若單一地考慮能量因素,而不兼顧其他特性,是不合理的。

此外,文獻(xiàn)[11]提出了基于模糊邏輯的分布式簇算法CHEF。CHEF算法利用剩余能量和局部距離作為模糊邏輯的輸入,其中局部距離是指節(jié)點離其所有鄰居節(jié)點的距離之和。而模糊邏輯系統(tǒng)的輸出表征節(jié)點成為簇頭幾率。最終,幾率最高的節(jié)點成為簇頭。文獻(xiàn)[12-13]也提出了基于模糊邏輯的分布式簇算法EAUCF。這些算法充分利用了模糊邏輯算法的特性,但是并沒有對簇尺寸進(jìn)行控制,也忽略了簇內(nèi)通信的能量消耗。同時,在選擇簇頭時,沒有考慮到節(jié)點的鄰居節(jié)點數(shù)信息。

為此,本文結(jié)合模糊邏輯系統(tǒng)的優(yōu)勢,提出基于分布式模糊邏輯推理的非均勻簇路由DUCF。利用模糊邏輯算法在處理不確定系統(tǒng)的優(yōu)勢,將節(jié)點離基站的距離、節(jié)點剩余能量以及節(jié)點度作為模糊邏輯系統(tǒng)的輸入,進(jìn)而產(chǎn)生節(jié)點被選為簇頭的幾率以及簇尺寸。通過模糊邏輯系統(tǒng),產(chǎn)生更優(yōu)的簇頭。同時,依據(jù)局部信息,控制簇內(nèi)節(jié)點數(shù)(簇尺寸)。仿真結(jié)果表明,提出的DUCF算法能夠有效地降低能量消耗,擴(kuò)延網(wǎng)絡(luò)壽命。

1 預(yù)備知識

1.1 網(wǎng)絡(luò)模型及約束條件

考慮如圖1所示的網(wǎng)絡(luò)模型,將網(wǎng)內(nèi)傳感節(jié)點劃分不同的簇,每個簇內(nèi)產(chǎn)生一個簇頭。簇頭融合本簇內(nèi)成員節(jié)點的數(shù)據(jù),然后再以直接或間接多跳方式傳輸至基站。

考慮同構(gòu)無線傳感網(wǎng)絡(luò),所有傳感節(jié)點具有相同初始能量Einit。一旦在監(jiān)測區(qū)域內(nèi)部署了傳感節(jié)點,傳感節(jié)點就不再移動,即靜態(tài)無線傳感網(wǎng)絡(luò)。每個傳感節(jié)點具有相同的處理數(shù)據(jù)容量,且節(jié)點的傳輸半徑為R。此外,基站不受能量限制,并且具有全局網(wǎng)絡(luò)知識。

圖1 網(wǎng)絡(luò)模型

1.2 能量模型

無線電能量消耗主要有兩部分組成:運(yùn)行電子元器件、功率放大器所消耗的能量和接收器所消耗的能量[14]。如圖2所示,在相距為d的兩節(jié)點間傳輸q比特的數(shù)據(jù)信息,消耗的能量:

(1)

式中:Eelec運(yùn)行發(fā)射器或接收器固定的能量消耗,Efrris、Etworay分別表示發(fā)射器在自空間、雙徑傳播模型(two ray ground model)的單位功率放大器的能量消耗[14-15]。而dco的定義如式2所示:

(2)

式中:λ為波長、l為系統(tǒng)損耗。ht、hr分別表示發(fā)射天線和接收天線的增益系數(shù)。相應(yīng)地,對于接收q比特的數(shù)據(jù)包所消耗的能量:

ERX(q)=qEelec

(3)

圖2 無線電能量消耗模型

2 DUCF 算法

提出的DUCF算法將時間劃分等間隔輪r(round),如圖3所示。每輪由簇化階段和數(shù)據(jù)匯聚階段。前者又可進(jìn)一步分為簇頭選擇和簇形成兩個子階段。將數(shù)據(jù)匯聚階段劃分等間隔的幀,每一幀內(nèi)有固定的時隙,用于簇內(nèi)成員節(jié)點向簇頭傳輸數(shù)據(jù)。

圖3 DUCF算法的時間模型

圖4 DUCF算法模塊圖

2.1 簇頭選擇階段

本小節(jié)詳盡表述簇頭選擇階段。DUCF算法利用模糊邏輯系統(tǒng)選擇簇頭。首先計算節(jié)點離基站的距離d、節(jié)點的剩余能量Eres以及節(jié)點度ρ,并將這3個變量作為模糊邏輯系統(tǒng)的輸入,系統(tǒng)的輸出變量ζ表征了節(jié)點成為簇頭的幾率,如圖4所示。

圖5 3個輸入變量的隸屬函數(shù)

距離對網(wǎng)絡(luò)性能也存在影響。若離基站過近,節(jié)點將消耗過多的能量向基站轉(zhuǎn)發(fā)數(shù)據(jù)。反之,若離基站過遠(yuǎn),節(jié)點將需要經(jīng)多次轉(zhuǎn)發(fā)才能將數(shù)據(jù)傳輸至基站。因此,在選擇簇頭,應(yīng)充分考慮簇頭離基站的距離信息。距離變量用“鄰近(Nearby)”、“可達(dá)(Reachable)”、“遙遠(yuǎn)(Distant)”表征距離語言變量,如圖5(b)所示,其中“可達(dá)(Reachable)”服從梯形函數(shù)。

最后將節(jié)點度作為模糊邏輯系統(tǒng)的輸入。節(jié)點度指節(jié)點一跳鄰居節(jié)點。節(jié)點度越高,成為簇頭的概率越高。節(jié)點度的隸屬函數(shù)如圖5(c)所示,用“低(Nearby)”、“中等(Average)”、“高(Huge)”表征節(jié)點度語言變量。

依據(jù)圖4可知,模糊邏輯系統(tǒng)有表征成為簇頭的幾率ζ、簇尺寸s的兩個輸出變量,分別如式(4)、式(5)所示。

ζ= {very high,high,rather high,high medium,medium

low medium,rather low,low,very low}

(4)

s= {very small,small,rather small, medium,rather big

big,very big,very small,very big}

(5)

兩個輸出變量的幾率ζ、簇尺寸s的隸屬函數(shù)如圖6所示。

圖6 輸出變量的隸屬函數(shù)

知識規(guī)則庫如表1所示,共有27條規(guī)則。系統(tǒng)輸出的兩個變量為模糊值,僅為語言輸出變量,需要將其轉(zhuǎn)換精確的數(shù)值,即去模糊化。利用文獻(xiàn)[16]的Mamdani模糊控制的重心法,可實現(xiàn)去模糊化。

依據(jù)模糊邏輯系統(tǒng)的輸出,傳感節(jié)點便獲取了自己的幾率值ζ。然后,所有節(jié)點就在一跳傳輸范圍內(nèi)廣播CH_candidate消息,其包含節(jié)點ID和幾率ζ值。每個節(jié)點依據(jù)幾率ζ值設(shè)置定時器,定時時間與ζ值成反比。具體而言,假定節(jié)點i,它的定時時間為Ti:

Ti=|1/ζi|×T

(6)

式中:ζi為節(jié)點i的幾率值、T為定時器的基準(zhǔn)時間。

表1 DUCF算法的規(guī)則庫

從式(6)可知,幾率越小,節(jié)點的定時等待時間越短,成為簇頭的概率就越大。如果節(jié)點在自己定時時間內(nèi),沒有收到其他節(jié)點發(fā)送的CH_won消息,節(jié)點就待定時時間完畢后,立即向一跳鄰居節(jié)點廣播CH_won消息,宣稱自己成為簇頭。如果在定時時間內(nèi),收到CH_won消息,表明一跳鄰居內(nèi)已有更短的定時時間,其已宣稱自己為簇頭。

2.2 簇頭形成階段

沒有成為簇頭的節(jié)點需要選擇離其最近一個簇加入。具體過程如下:簇頭廣播CH_won消息后,鄰居節(jié)點可能收到一條或多條CH_won消息。如果只收到一條,節(jié)點就向該簇頭發(fā)送CM_join消息。若收到多條CH_won消息,節(jié)點就選擇離自己最近的簇頭回復(fù)CM_join消息。一旦發(fā)送了CM_join消息,節(jié)點就等待、并接收簇頭回復(fù)CM_acceptance消息。

為了控制簇尺寸,簇頭接收了CM_join消息后,需要決定是否允許該節(jié)點加入簇。如果簇內(nèi)節(jié)點的節(jié)點數(shù)并沒有超過簇尺寸s,簇頭就向該節(jié)點發(fā)送CM_acceptance消息,表示允許該節(jié)點加入簇。否則,就發(fā)送拒絕CM_rejection消息。

節(jié)點一旦接收了CM_acceptance消息,就加入該簇。若收到CM_rejection消息,節(jié)點再向其他的簇頭發(fā)送CM_join消息,重復(fù)上述過程,直到收到簇頭的CM_acceptance消息。不過,更為糟糕的是,節(jié)點可能無法收到CM_join消息。在這種情況下,該節(jié)點就自己成為簇頭。

2.3 數(shù)據(jù)匯聚階段

簇形成后,每個簇頭為簇內(nèi)成員節(jié)點安排TDMA時隙。簇內(nèi)成員在TDMA時隙內(nèi)向簇頭傳輸感測數(shù)據(jù)。為了節(jié)省節(jié)點能量,節(jié)點僅在數(shù)據(jù)傳輸時隙內(nèi)保持活動狀態(tài),其余時隙保持睡眠狀態(tài)。當(dāng)然,簇頭一直保持非睡眠狀態(tài),使它能夠及時匯聚簇內(nèi)成員節(jié)點的數(shù)據(jù)。由于簇內(nèi)節(jié)點感測的數(shù)據(jù)相似,簇頭需對這些數(shù)據(jù)進(jìn)行融合、匯聚,然后再向基站傳輸。

3 性能仿真

3.1 仿真參數(shù)及性能指標(biāo)

本節(jié)評估DUCF算法的性能,利用MATLAB建立仿真平臺,并與LEACH、EAUCF、CHEF進(jìn)行比較。選擇這3個算法作為參考原因在于:LEACH是經(jīng)典的簇算法,而EAUCF和CHEF算法也采用模糊邏輯,與DUCF算法具有可比性。在仿真過程中,LEACH算法在簇頭百分比設(shè)為0.1,而EAUCF和CHEF算法的簇頭比例為0.3。

100個節(jié)點隨機(jī)分布于200 m×200 m監(jiān)測區(qū)域內(nèi)。為了能更好地分析DUCF算法性能,分別考慮3個場景:基站位于監(jiān)測區(qū)域中心;基站位于監(jiān)測區(qū)域角落;基站位于監(jiān)測區(qū)域外。此外,節(jié)點傳輸半徑R=40 m,其他仿真參數(shù)如表2所示。

表2 仿真參數(shù)

從每輪的能量消耗、傳輸?shù)南?shù)和網(wǎng)絡(luò)壽命三方面分析DUCF算法,其中,傳輸?shù)南?shù)表示在網(wǎng)絡(luò)內(nèi)有一半節(jié)點失效HND(Half Node Die)時,基站所接收到消息數(shù)。而網(wǎng)絡(luò)壽命表示從兩個方面進(jìn)行分析:在第1個節(jié)點失效FND(First Node Die)前,所執(zhí)行的輪數(shù),以及一半節(jié)點失效HND前,所執(zhí)行的輪數(shù)。

3.2 每輪的能量消耗

3個場景下的能量消耗情況如圖7所示。從圖7可知,LEACH算法消耗的能量最多。原因在于LEACH算法中簇頭與基站通信采用直接方式,這加大了能量消耗。相比之下,與LEACH算法相比,CHEF算法的能量消耗有所下降,但是離EAUCF和DUCF算法仍存在較大的差距。與LEACH和CHEF算法相比,EAUCF算法的能量消耗得到有效了的下降。

圖7 每輪的能量消耗

然而,EAUCF算法在選擇簇頭時,僅考慮節(jié)點的剩余能量,并沒有考慮節(jié)點度等其他因素。與LEACH、CHEF和EAUCF算法相比,DUCF算法的能量消耗的最少。這主要因為DUCF算法在選擇簇頭時,充分考慮了節(jié)點的剩余能量、距離以及節(jié)點度的信息,進(jìn)而選擇了更優(yōu)的節(jié)點作為簇頭,這縮減了簇內(nèi)通信的距離。同時簇頭與基站通信采用多跳方式,這些措施有利于節(jié)點能量的保存。

3.3 網(wǎng)絡(luò)壽命

本文分別利用FND和HND時各算法所完成的通信輪數(shù)表征網(wǎng)絡(luò)壽命,實驗數(shù)據(jù)如圖8、圖9所示。

圖8 網(wǎng)絡(luò)壽命(FND)

從圖8可知,提出的DUCF算法能夠有效地提高網(wǎng)絡(luò)壽命。在場景一中,DUCF算法比LEACH、CHEF和EAUCF算法的網(wǎng)絡(luò)壽命分別提高了71.87%、31.91%、16.07%。而在場景二中,DUCF算法在網(wǎng)絡(luò)壽命方面的性能優(yōu)勢更為明顯,比LEACH、CHEF和EAUCF分別提高了127.14%、116.72%、14.95%。當(dāng)基站不在監(jiān)測區(qū)域時,DUCF算法的網(wǎng)絡(luò)壽命得到更大的提升。在場景三,DUCF算法的網(wǎng)絡(luò)壽命比LEACH、CHEF和EAUCF算法分別提高了133.47%、150.0%、5.01%。

圖9 網(wǎng)絡(luò)壽命(HND)

圖9分析了在HND時各算法的網(wǎng)絡(luò)壽命。圖10的實驗數(shù)據(jù)進(jìn)一步表明DUCF算法能夠有效地提高網(wǎng)絡(luò)壽命。在場景一中,DUCF算法比LEACH、CHEF和EAUCF算法分別提高了14.30%、31.78%、16.74%;在場景二中,提高了54.10%、51.74%、2.35%。而當(dāng)基站遠(yuǎn)離監(jiān)測區(qū)域時,DUCF算法在網(wǎng)絡(luò)壽命方面的性能優(yōu)勢更為突出。在場景三中,DUCF算法比LEACH、CHEF和EAUCF算法的網(wǎng)絡(luò)壽命分別提高了95.38%、91.84%、6.72%。

4 總結(jié)

本文提出了基于模糊邏輯推理的WSNs非均勻分簇算法DUCF,旨于降低能耗,提高網(wǎng)絡(luò)壽命。具體而言,利用模糊邏輯推理輸出變量“簇尺寸”,控制簇內(nèi)成員節(jié)點的個數(shù),進(jìn)而平衡節(jié)點能量消耗。DUCF算法充分利用節(jié)點離基站的距離、節(jié)點度以及剩余能量因素計算簇尺寸和成為簇頭的幾率。仿真結(jié)果表明,DUCF算法能夠有效地提高網(wǎng)絡(luò)壽命。特別是在基站位于監(jiān)測區(qū)域場景,DUCF算法在網(wǎng)絡(luò)壽命方面的優(yōu)勢比LEACH、CHEF、 EAUCF算法更為顯著。

提出DUCF算法目的在于降低能量消耗,延長網(wǎng)絡(luò)壽命。這也是該算法的優(yōu)勢。當(dāng)然,利用引入模糊系統(tǒng),提升一定的算法復(fù)雜性,這也是后期工作的重點:在延長網(wǎng)絡(luò)壽命的同時,降低算法復(fù)雜性。

[1] Muruganathan S D,Ma D C,Bhasin R I. A Centralized Energy-Efficient Routing Protocol for Wireless Sensor Networks[J]. IEEE Radio Communications,2011,43(3):8-13.

[2] 歸奕紅. 無線傳感器網(wǎng)絡(luò)HEDSA數(shù)據(jù)聚合研究[J]. 計算機(jī)工程,2011,37(7):160-164.

[3] 沈艷霞,薛小松. 無線傳感網(wǎng)絡(luò)移動信標(biāo)節(jié)點路徑優(yōu)化策略[J]. 傳感器與微系統(tǒng),2012,31(12):42-46.

[4] Zhao F,Liu J. Collaborative Signal and Information Processing:An Information Directed Approach[J]. Processing IEEE,2013,91(8):1199-1209.

[5] 周凱,孟利民,華驚宇. 基于Grover路由策略的無線傳感網(wǎng)絡(luò)剩余容量構(gòu)造與研究[J]. 傳感技術(shù)學(xué)報,2015,28(2):249-253.

[6] Abbasi A,Younis M F. A Survey on Clustering Algorithms for Wireless Sensor Networks[J]. Computing Communication,2012,30(15):2826-2841.

[7] Bajabder F,Awan I. Adaptive Decentralized Re-Clustering Protocol for Wireless Sensor Networks[J]. Journal Computing System,2011,77(2):282-292.

[8] Heizelman W,Chandrakasan A,Balakrishnan H. An Application-Specificprotocol Architecture for Wireless Microsensor Networks[J]. IEEE Transation Wireless Communications,2002,1(4):660-670.

[9] Mehdi M,Tayarani H. Clustering in Sensor Networks:A Literature Survy[J]. Journal Network Complication Application,2014(46):198-226.

[10] Ye M,Chen G H. EECS:An Energy Efficient Clustering Scheme in Wireless Sensor Networks[C]//24th IEEE International Performance,Computing and Communication Conference,2015:535-540.

[11] Kim J,Park S,Han Y. CHEF:Cluster Head Election Mechanism Using Fuzzy Logic in Wireless Sensor Networks[C]//10th International Conference on Advanced Communication Technology,2013:654-659.

[12] Bagci H,Yazici A. An Energy Aware Fuzzy Approach to Unequal Clustering in Wireless Sensor Networks[J]. Application Soft Computing,2013,13(4):1741-1749.

[13] Bagci H,Yazici A. An Energy Aware Fuzzy Unequal Clustering Algorithm for Wireless Sensor Networks[C]//Proceedings of the IEEE International Conference on Fuzzy Systems,2010:1631-1639.

[14] Xinhua W,Sheng W. Performance Comparison of LEACH and LEACH-C Protocols by ns2[C]//Ninth International Symposium on Distributed Computing and Applications to Business,Engineering and Science,2010:23-32.

[15] Liao Y,Qi H,Li W. Load-Balanced Clustering Algorithm with Distributed Self-Organization for Wireless Sensor Networks[J]. IEEE Sens,2013,13(5):1498-1506.

[16] Elbhiri B,Saadane R,El-Fkihi S,et al. Developed Distributed Energy-Efficient Clustering(DDEEC)for Heterogeneous Wireless Sensor Networks[C]//5th International Symposium on I/V Communications and Mobile Network. 2010:32-42.

Fuzzy Logic-Based Unequal Clustering Algorithm for Wireless Sensor Networks

YANG Jiandong*,WANG Wenjian

(Zhengzhou University of Industrial Technology,Xinzheng He’nan 451150,China)

In order to reduce the energy consumption and prolong the network lifetime of Wireless Sensor Networks(WSNs),distributed fuzzy logic inference-based unequal clustering routing is proposed in this paper,which is marked as DUCF. DUCF protocol fully consider the residual energy of the node,distance to base station,and the degree of node. It makes some fuzzy rules,and calculates probability of cluster head and size of cluster through the fuzzy inference system. DUCF forms unequal clusters to balance the energy consumption among the cluster headers. Simulation results show that the proposed DUCF performs better in term of network lifetime and energy consumption as compared to LEACH,CHEF and EAUCF protocols.

wireless sensor network;clustering;fuzzy logic inference;unequal;residual energy

楊健冬(1981-),男,漢族,河南鄭州人,碩士,講師,主要研究領(lǐng)域為計算機(jī)網(wǎng)絡(luò)與通信,互聯(lián)網(wǎng)技術(shù),信息安全;

王文娟(1983-),女,河南鄭州人,碩士研究生,主要研究領(lǐng)域為計算機(jī)網(wǎng)絡(luò)與通訊,電子設(shè)計自動化,信息安全。

項目來源:國家自然科學(xué)基金項目(31630034);河南省基礎(chǔ)與前沿技術(shù)研究計劃項目(142300410283)

2016-10-04 修改日期:2017-02-21

TPT393

A

1004-1699(2017)06-0929-06

C:7230

10.3969/j.issn.1004-1699.2017.06.021