基于模糊理論的無線傳感器網(wǎng)絡(luò)多層分簇式路由算法*

陸亞芳,易可夫,馮 緒,萬江文

(北京航空航天大學儀器科學與光電工程學院,北京 100191)

?

基于模糊理論的無線傳感器網(wǎng)絡(luò)多層分簇式路由算法*

陸亞芳,易可夫,馮 緒,萬江文*

(北京航空航天大學儀器科學與光電工程學院,北京 100191)

為了進一步降低無線傳感器網(wǎng)絡(luò)的能量消耗,延長網(wǎng)絡(luò)壽命,提出一種基于模糊理論的多層分簇式路由算法(MLFC)。新算法根據(jù)通信距離與能量的相關(guān)性將網(wǎng)絡(luò)劃分為多層,采用模糊算法根據(jù)節(jié)點的能量、分布密度和中心度在每層中選出多個簇頭,其余節(jié)點分別加入同層中距離最近簇頭形成的簇,簇頭逐層傳遞數(shù)據(jù),建立起自組多跳路由。仿真實驗結(jié)果表明,多層分簇式路由算法可以更好地均衡無線傳感器網(wǎng)絡(luò)各節(jié)點的負載,能明顯提高節(jié)點的生命周期,延長網(wǎng)絡(luò)壽命。

無線傳感器網(wǎng)絡(luò);路由算法;模糊理論;分簇

無線傳感器網(wǎng)絡(luò)WSNs(Wireless Sensor Networks)是由大量具有感知、計算和通信能力的微型傳感器節(jié)點通過自組織方式構(gòu)成的無線網(wǎng)絡(luò)。它已經(jīng)開始在環(huán)境監(jiān)測、智慧城市、精細農(nóng)業(yè)等眾多領(lǐng)域發(fā)揮重要作用。WSNs的傳感器節(jié)點一般是由電量有限的電池供電,降低能量消耗是WSNs的關(guān)鍵問題之一,當前仍然是研究的熱點。

合適的網(wǎng)絡(luò)通信路由是降低WSNs能量消耗的有效途徑之一,目前已經(jīng)有一些旨在降低能耗的分簇式路由算法[1-9]發(fā)表。LEACH算法[1]是最早提出來的分簇式路由協(xié)議,它采用輪循環(huán)方式,各節(jié)點成為簇頭的概率都相同,使得網(wǎng)絡(luò)中的節(jié)點能夠相對均衡地消耗能量。但是,由于LEACH算法中簇頭采用單跳方式與基站BS(Base Station)通信,距離基站遠的節(jié)點會不可避免地過度消耗能量。HEED協(xié)議[6]根據(jù)主次參數(shù)均勻選擇簇頭以均衡節(jié)點的通信負載,采用多跳方式與基站通信,克服了LEACH協(xié)議單跳通信方式帶來的距離基站遠的節(jié)點能量消耗過快的問題。但是,多跳路由會使距離BS近的簇頭因大量轉(zhuǎn)發(fā)遠距離簇頭信息而過快消耗能量。為解決上述問題,EEUC[7]、DEBUC[8]、UCDP[9]等算法采用非均勻分簇方式,減少靠近BS的簇的通信半徑,減輕其數(shù)據(jù)轉(zhuǎn)發(fā)的任務(wù),一定程度上均衡了通信負載。

從節(jié)點分簇,到多跳通信,再到非均勻分簇,通過更合適的路由來降低WSNs能耗的研究在不斷深入。在不明顯增加計算量的前提下,研究更為合理的分簇及簇頭通信方式,很有必要。

如果在選舉簇頭之前,先將網(wǎng)絡(luò)分層,在層中綜合考慮節(jié)點能耗、分布密度和中心度等多種因素選出簇頭,再由簇頭建立層間通信多跳路由,應(yīng)當可以進一步地均衡節(jié)點通信負載、降低網(wǎng)絡(luò)能耗。

模糊算法在不需要復雜的數(shù)學建模的情況下,即可將多個因素綜合評價以得出優(yōu)先級,這一特點可以用于綜合考慮WSNs節(jié)點的多種因素并選出簇頭。由此,提出一種基于模糊理論的無線傳感器網(wǎng)絡(luò)多層分簇式路由算法MLFC(Efficient Multi-Layer Routing Protocol Through Fuzzy Logic Based Clustering Mechanism),首先,根據(jù)與BS的距離將網(wǎng)絡(luò)劃分為多層,各層中簇頭數(shù)量與該層和BS的距離成反比;然后,各層中采用模糊算法綜合考慮節(jié)點剩余能量、分布密度和中心度,合理選擇簇頭;最后,簇頭逐層傳遞數(shù)據(jù),建立起多跳路由。這種算法,復雜度不會有明顯增加,卻能更有效地均衡網(wǎng)絡(luò)負載和降低能耗。

1 網(wǎng)絡(luò)與能量模型

1.1 網(wǎng)絡(luò)模型[10]

MLFC算法對無線傳感器網(wǎng)絡(luò)做出如下假設(shè):①節(jié)點被隨機地分布在檢測區(qū)域內(nèi),所有節(jié)點的初始能量都相同。②節(jié)點可根據(jù)需要調(diào)整自身的發(fā)射功率。③節(jié)點通過RSSI方式可知道與其他節(jié)點的距離。④節(jié)點具有足夠的計算能力來完成算法。

1.2 能量模型[11]

根據(jù)發(fā)送節(jié)點和接收節(jié)點之間的通信距離分別采用自由空間模型和多徑衰減模型。節(jié)點發(fā)送k比特數(shù)據(jù)到距離d的接收器消耗的能量Et和接收器接收k比特數(shù)據(jù)消耗的能量Er分別為

(1)

Er=kEelec

(2)

上述中Eelec代表收發(fā)器的能量消耗,Eamp1和Eamp2分別代表自由空間模型和多徑衰減模型放大電路的能量損耗,d0是兩種模型的通信距離分界值。

2 基于模糊理論的多層分簇式路由算法

MLFC采用輪循環(huán)機制,每一輪中可以分為以下幾個步驟:①根據(jù)通信距離與能量的關(guān)系將網(wǎng)絡(luò)劃分為多個層。節(jié)點根據(jù)與基站的距離確定自己所在的層。每層的簇頭數(shù)量由該層的節(jié)點數(shù)和與基站的距離決定。離基站遠的層簇頭少,離基站近的層簇頭多,這樣做的目的,是減少離基站近的傳感器節(jié)點的數(shù)據(jù)轉(zhuǎn)發(fā)任務(wù),以均衡網(wǎng)絡(luò)負載。②各層基于節(jié)點能量、密度和中心度等3個變量采用模糊算法選出多個簇頭。通過模糊算法綜合考慮節(jié)點的能量和位置信息,使簇頭不會因為能量低而過早死亡,同時會減少簇內(nèi)的通信能量消耗。③其他沒有被選舉為簇頭的節(jié)點加入距離最近的簇頭所形成的簇。④簇內(nèi)節(jié)點采用單跳方式與簇頭通信,簇頭逐層通過多跳傳遞融合數(shù)據(jù),建立起與基站之間的多跳路由,由此可以避免信號的遠距離傳輸。⑤根據(jù)簇頭剩余能量和每輪的時間重新選擇簇頭,建立起新的路由,進行路由的維護。

2.1 網(wǎng)絡(luò)分層

如圖1所示,根據(jù)能量模型式(1)中的d0,網(wǎng)絡(luò)劃分為L層。設(shè)d是節(jié)點到BS的距離。dmax是網(wǎng)絡(luò)中的節(jié)點到BS的最大距離。

dmax=MAX(d(SNj,BS))

(3)

(4)

圖1 網(wǎng)絡(luò)分層示意

節(jié)點SNj所在層的層數(shù)為l

(5)

這樣分層,能夠使簇頭逐層通信時的通信距離小于d0,以減少遠距離通信帶來的能量消耗。

各層的簇頭個數(shù)Cl與層數(shù)l成反比,與第l層中節(jié)點的個數(shù)Nl成正比。這樣可以使距離BS近和節(jié)點密度大的層中的簇頭數(shù)量更多,有利于減小簇內(nèi)通信的能量消耗。Cl的計算如下:

(6)

其中K為系統(tǒng)的預設(shè)參數(shù)。

2.2 基于模糊算法的簇頭選擇方法

模糊算法不需要復雜的數(shù)學建模,具有結(jié)構(gòu)簡單、魯棒性好的特點[12]。

傳感器網(wǎng)絡(luò)經(jīng)過分層后,在每層中根據(jù)模糊變量和模糊規(guī)則,采用模糊算法,計算出節(jié)點的優(yōu)先級,選擇優(yōu)先度級的節(jié)點作為簇頭。

2.2.1 模糊變量

(1)節(jié)點的相對能量

節(jié)點相對能量PE代表節(jié)點SNi的剩余能量Ei與SNi所在簇的剩余能量最大節(jié)點的剩余能量Emax之比。

(7)

(2)節(jié)點的相對密度

節(jié)點密度代表傳感器節(jié)點附近節(jié)點的密集程度,用節(jié)點SNi在d0通信范圍內(nèi)的鄰居節(jié)點個數(shù)Di來表示。節(jié)點密度越高,則與鄰居節(jié)點數(shù)據(jù)傳遞時消耗的能量越低。節(jié)點相對密度PD的大小為節(jié)點SNi的密度Di與節(jié)點SNi所在簇的簇內(nèi)節(jié)點最大密度Dmax之比。

(8)

(3)節(jié)點的相對中心度

節(jié)點中心度Ci代表節(jié)點SNi與鄰居節(jié)點的靠近程度。它的計算公式如下:

(9)

式中xi代表節(jié)點SNi的x坐標,yi代表節(jié)點SNi的y坐標。

簇頭與鄰居節(jié)點越近,通信消耗的能量越少。節(jié)點相對中心度PC的大小為傳感器節(jié)點SNi所在簇的簇內(nèi)節(jié)點的最小中心度Cmin與Ci之比。

(10)

2.2.2 變量的模糊化

模糊化是將每一個輸入值映射到相應(yīng)的模糊集合,并給每個模糊集合賦予隸屬函數(shù)。設(shè)定節(jié)點相對能量PEi=e*,相對密度PDi=d*和相對中心度PCi=c*。相應(yīng)的模糊輸入E*(e),D*(d),C*(c)可以表示為:

(11)

采用三角形和梯形隸屬度函數(shù),因為它們適用于實時系統(tǒng)[13]。MLFC算法中包含3個模糊輸入?yún)?shù):相對能量、相對密度和相對中心度;包含一個輸出參數(shù):節(jié)點優(yōu)先級。節(jié)點優(yōu)先級決定了該節(jié)點能否成為簇頭。

在建立輸入和輸出參數(shù)對應(yīng)的模糊子集和模糊隸屬度函數(shù)時,主要是參考自然經(jīng)驗,確定的參數(shù)和對應(yīng)的特征集如表1所示。

表1 參數(shù)和特征集

圖2 模糊邏輯系統(tǒng)輸入和輸出的隸屬度函數(shù)

圖2(a)表示相對能量的隸屬度函數(shù)及特征值之間的關(guān)系。相對能量按照一定的隸屬度屬于某特征值。當相對能量低于0.2時,相對能量屬于“少”;當相對能量在0.3和0.7之間時,相對能量屬于“中等”;當相對能量大于0.8時,相對能量屬于“多”。當相對能量在0.2和0.3之間時,相對能量有兩個特征值:即“少”和“中等”,它按照隸屬度μ1和μ2分別屬于“少”和“中等”;當相對能量在0.7和0.8之間時,相對能量有兩個特征值:即“中等”和“多”,它按照隸屬度μ3和μ4分別屬于“中等”和“多”。圖2(b)表示相對密度的隸屬度函數(shù)及特征值之間的關(guān)系,圖2(c)表示相對中心度的隸屬度函數(shù)及特征值之間的關(guān)系,圖2(d)表示節(jié)點優(yōu)先級的隸屬度函數(shù)及特征值之間的關(guān)系。節(jié)點相對密度、相對中心度和優(yōu)先級的隸屬度函數(shù)及特征值之間的關(guān)系與相對能量的類似。

2.2.3 模糊規(guī)則

MLFC算法采用模糊IF-THEN分類規(guī)則,例如,相對能量多、相對密度高并且相對中心度高,則節(jié)點的優(yōu)先級非常高。MLFC算法包含3×3×3=27條模糊規(guī)則,如表2所示。

表2 模糊規(guī)則

2.2.4 解模糊化

解模糊化是把由模糊規(guī)則生成的輸出量轉(zhuǎn)變成能實際使用的變量。MLFC采用重心法進行解模糊化。公式如下:

(12)

sup代表節(jié)點的優(yōu)先度,μsup(x)是節(jié)點優(yōu)先級的模糊集成員函數(shù),x表示優(yōu)先級的具體值。

2.2.5 模糊算法計算示例

SNi節(jié)點的優(yōu)先級sup的值為:

2.3 簇的形成

節(jié)點被選為簇頭后,向鄰居節(jié)點廣播信息,鄰居節(jié)點接收到信息后加入距離最近的簇頭形成的簇,并向簇頭發(fā)送加入信息。這樣節(jié)點與簇頭節(jié)點的通信代價最小。在周期內(nèi),簇內(nèi)節(jié)點將信息發(fā)送給簇頭節(jié)點,簇頭節(jié)點將收集到的數(shù)據(jù)融合處理后打包發(fā)送給基站,其中數(shù)據(jù)融合消耗的能量為EDA。

2.4 路由的建立

層間路由如圖3所示。CHli是第l層的簇頭,它把要傳送給BS的數(shù)據(jù)轉(zhuǎn)發(fā)給距離最近的第l-1層的簇頭CH(l-1)j。簇頭CH(l-1)j再把要傳送給BS的數(shù)據(jù)轉(zhuǎn)發(fā)給距離最近的第l-2層的簇頭CH(l-2)k。依次傳遞,直到第1層的簇頭CH1p把數(shù)據(jù)轉(zhuǎn)發(fā)給BS。從而建立起簇頭與BS之間數(shù)據(jù)逐層傳遞的多跳路由。

圖3 路由建立示意

2.5 路由的維護

①當?shù)趌層中某簇頭的能量低于簇內(nèi)各節(jié)點剩余能量的平均值的一半時,在l層內(nèi)部進行新的簇頭選舉和并建立新簇,同時重新建立起l+1層到l層和l層到l-1層的簇頭數(shù)據(jù)轉(zhuǎn)發(fā)路徑;②經(jīng)過T時間,整個網(wǎng)絡(luò)建立起新一輪的路由。

3 仿真結(jié)果

采用MATLAB仿真分析算法的性能,并與LEACH、EECU算法做比較。

算法的仿真參數(shù)如表3所示。

表3 仿真參數(shù)

3.1 模糊算法模型

模糊算法的仿真結(jié)果如圖4所示。當節(jié)點的相對能量為0時,無論相對中心度和相對密度怎么變化,節(jié)點的優(yōu)先級都很小。當節(jié)點的相對能量到達一定數(shù)值時,節(jié)點的優(yōu)先級會隨著相對密度和相對中心度的增加而增加。這說明,節(jié)點相對能量是決定節(jié)點優(yōu)先級的最重要因素,同時,相對密度和中心度也會對優(yōu)先級產(chǎn)生明顯影響。

圖4 MLFC算法模糊推理模型仿真結(jié)果

3.2 簇頭能量消耗

圖5是MLFC算法與LEACH和EEUC算法的簇頭能量消耗的對比曲線。前20 s的簇頭能量消耗數(shù)據(jù)更具有可比性。MLFC和EEUC算法的簇頭能量消耗比LEACH算法平穩(wěn)并且明顯低。LEACH算法是采用輪詢方式以等可能概率隨機選取簇頭,所以簇頭消耗的能量波動較大。MLFC和EEUC算法在進行簇頭選擇時是有條件的并且相對穩(wěn)定,所以簇頭能量消耗相對平穩(wěn)。MLFC和EEUC采用多跳路由,相對LEACH算法節(jié)省了能量。MLFC算法的簇頭能量消耗比EEUC算法更低。因為MLFC算法在選擇簇頭時通過模糊算法綜合考慮了節(jié)點的能耗和地理位置信息,降低了簇頭給簇內(nèi)節(jié)點發(fā)送控制信息的能耗,并且進一步減少了簇內(nèi)通信的能量消耗。因此,MLFC算法具有更好的均衡能耗的效果。

圖5 3種算法的簇頭能量消耗曲線

3.3 網(wǎng)絡(luò)能耗

圖6是MLFC算法與LEACH和EEUC算法網(wǎng)絡(luò)剩余能量的對比曲線。MLFC采用模糊理論綜合考慮節(jié)點剩余能量、中心度和密度等多個因素,合理選擇簇頭,減少了簇內(nèi)節(jié)點通信消耗的能量,并且,簇頭將融合數(shù)據(jù)逐層傳遞給基站,建立多跳路由,減少與基站通信之間的能量消耗。因此,MLFC網(wǎng)絡(luò)能量消耗速度比LEACH和EEUC算法都要低,起到了減少能量消耗的作用。

圖6 3種算法的網(wǎng)絡(luò)剩余能量對比

3.4 網(wǎng)絡(luò)生存周期

圖7是MLFC算法與LEACH和EEUC算法的網(wǎng)絡(luò)存活節(jié)點數(shù)量的對比曲線,圖中MLFC算法的第一個節(jié)點死亡時間明顯晚于EEUC和LEACH算法。MLFC算法將網(wǎng)絡(luò)劃分為多層,距離基站近的層中簇頭多,減少了靠近基站的簇頭的轉(zhuǎn)發(fā)任務(wù),均衡了網(wǎng)絡(luò)中的負載,從而使得網(wǎng)絡(luò)中節(jié)點的存活時間明顯延長。

圖7 3種算法的存活節(jié)點數(shù)量對比

4 結(jié)論

MLFC路由算法的中心思想是根據(jù)通信距離將網(wǎng)絡(luò)劃分為多層,使靠近基站的層有相對更多的簇頭,緩解了多跳路由中靠近基站的節(jié)點過多承擔轉(zhuǎn)發(fā)任務(wù)導致過早死亡的問題;選舉簇頭時綜合考慮節(jié)點剩余能量和位置信息,采用模糊理論合理選擇簇頭,更好地均衡各節(jié)點的能量消耗,同時減少簇內(nèi)通信量;簇頭自組建立層間的多跳路由,減少節(jié)點遠距離發(fā)送數(shù)據(jù)帶來的能量消耗。MLFC采取的模糊算法不需要復雜的數(shù)學計算,能夠有效均衡網(wǎng)絡(luò)負載,顯著減少網(wǎng)絡(luò)能耗和延長網(wǎng)絡(luò)壽命。

[1] Wendi B Heinzelman,Anantha P Chandrakasan,Hari Balakrishnan.An Application-Specific Protocol Architecture for Wireless Micro sensor Networks[J].IEEE Transactions on Wireless Communications,2002,1(4):660-670.

[2]魏春娟,楊俊杰,張志美.一種分布式能量有效的無線傳感器網(wǎng)絡(luò)分簇路由協(xié)議[J].傳感技術(shù)學報,2013,26(7):1014-1018.

[3]Babar Nazir,Halabi Hasbullah.Energy Efficient and QoS Aware Routing Protocol for Clustered Wireless Sensor Network[J].Computers and Electrical Engineering,2013,39(8):2425-2441.

[4]石為人,柏蕩,高鵬,等.無線傳感器網(wǎng)絡(luò)簇頭半徑自適應(yīng)調(diào)節(jié)路由算法[J].儀器儀表學報,2012,3(8):1779-1785.

[5]劉鐵流,巫詠群.基于能量優(yōu)化的無線傳感器網(wǎng)絡(luò)分簇路由算法研究[J].傳感技術(shù)學報,2011,24(5):764-770.

[6]Ossama Younis,Sonia Fahmy.HEED:A Hybrid,Energy-Efficient,Distributed Clustering Approach for Ad Hoc Sensor Networks[J].IEEE Transactions on Mobile Computing,2004,3(4):366-379.

[7]Li Chengfa,Ye Mao,Chen Guihai.An Energy-Efficient Unequal Clustering Mechanism for Wireless Sensor Networks[C]//IEEE International Conference on Mobile Adhoc and Sensor Systems Conference,Washington,DC,USA,2005:597-604.

[8]蔣暢江,石為人,唐賢倫.能量均衡的無線傳感器網(wǎng)絡(luò)非均勻分簇路由協(xié)議[J].軟件學報,2012,23(5):1222-1232.

[9]孫彥清,彭艦,劉唐,等.基于動態(tài)分區(qū)的無線傳感器網(wǎng)絡(luò)非均勻成簇路由協(xié)議[J].通信學報,2014,35(1):198-206.

[10]Sival Ranjani S,Radha Krishnan S,Thangaraj C,et al.Achieving Energy Conservation by Cluster Based Data Aggregation in Wireless Sensor Networks[J].Wireless Personal Communications,2013,73(3):731-751.

[11]Jin Rencheng,Gao Teng,Song Jinyan,et al.Passive Cluster-Based Multipath Routing Protocol for Wireless Sensor Networks[J].Wireless Networks,2013,19(8):1851-1866.

[12]Vilém Novák.Reasoning about Mathematical Fuzzy Logic and Its Future[J].Fuzzy Sets and Systems,2012,192:25-44.

[13]Feng Renjian,Che Shenyun,Wang Xiao.A Credible Cluster-Head Election Algorithm Based on Fuzzy Logic in Wireless Sensor Networks[J].Journal of Computational Information Systems,2012,15(8):6241-6248.

陸亞芳(1990-),女,北京航空航天大學在讀碩士研究生,研究方向為無線傳感器網(wǎng)絡(luò)技術(shù),Julyforever899@163.com;

萬江文(1963-),男,北京航空航天大學教授,博士生導師,主要研究方向為傳感系統(tǒng)與儀器、傳感網(wǎng)絡(luò)與信息融合、定位與跟蹤技術(shù),jwwan@buaa.edu.cn。

EfficientMulti-LayerRoutingProtocolforWirelessSensorNetworksthroughFuzzyLogicBasedClusteringMechanism*

LUYafang,YIKefu,FENGXu,WANJiangwen*

(School of Instrumentation Science and Opto-Electronics Engineering,Beihang University,Beijing 100191,China)

In order to reduce the energy consumption and prolong the network lifetime of wireless sensor networks(WSNs),an efficient multi-layer routing protocol through fuzzy logic based clustering mechanism(MLFC)for WSNs is proposed.The MLFC mainly includes three steps.First,the network is divided into several layers based on the relationship between communication distance and energy.Second,cluster headers are elected among layers through fuzzy logic according to node’s remaining energy,distribution density and concentration.Nodes join the cluster formed by the nearest cluster headers.Third,data packets are transmitted to the base station layer by layer.A multi-hop routing is constructed.Experiment results show that the MLFC is of benefit to balance the nodes energy consumption and achieves an evident improvement of network lifetime.

wireless sensor networks;routing protocol;fuzzy logic;clustering

項目來源:國家自然科學基金項目(61371135)

2014-04-25修改日期:2014-06-09

10.3969/j.issn.1004-1699.2014.07.015

TP393

:A

:1004-1699(2014)07-0933-06