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

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

?

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

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

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

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

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

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

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

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

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

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

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

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

MLFC算法對無線傳感器網(wǎng)絡做出如下假設:①節(jié)點被隨機地分布在檢測區(qū)域內,所有節(jié)點的初始能量都相同。②節(jié)點可根據(jù)需要調整自身的發(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ù)通信距離與能量的關系將網(wǎng)絡劃分為多個層。節(jié)點根據(jù)與基站的距離確定自己所在的層。每層的簇頭數(shù)量由該層的節(jié)點數(shù)和與基站的距離決定。離基站遠的層簇頭少,離基站近的層簇頭多,這樣做的目的,是減少離基站近的傳感器節(jié)點的數(shù)據(jù)轉發(fā)任務,以均衡網(wǎng)絡負載。②各層基于節(jié)點能量、密度和中心度等3個變量采用模糊算法選出多個簇頭。通過模糊算法綜合考慮節(jié)點的能量和位置信息,使簇頭不會因為能量低而過早死亡,同時會減少簇內的通信能量消耗。③其他沒有被選舉為簇頭的節(jié)點加入距離最近的簇頭所形成的簇。④簇內節(jié)點采用單跳方式與簇頭通信,簇頭逐層通過多跳傳遞融合數(shù)據(jù),建立起與基站之間的多跳路由,由此可以避免信號的遠距離傳輸。⑤根據(jù)簇頭剩余能量和每輪的時間重新選擇簇頭,建立起新的路由,進行路由的維護。

2.1 網(wǎng)絡分層

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

dmax=MAX(d(SNj,BS))

(3)

(4)

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

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

(5)

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

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

(6)

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

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

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

傳感器網(wǎng)絡經(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通信范圍內的鄰居節(jié)點個數(shù)Di來表示。節(jié)點密度越高,則與鄰居節(jié)點數(shù)據(jù)傳遞時消耗的能量越低。節(jié)點相對密度PD的大小為節(jié)點SNi的密度Di與節(jié)點SNi所在簇的簇內節(jié)點最大密度Dmax之比。

(8)

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

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

(9)

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

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

(10)

2.2.2 變量的模糊化

模糊化是將每一個輸入值映射到相應的模糊集合,并給每個模糊集合賦予隸屬函數(shù)。設定節(jié)點相對能量PEi=e*,相對密度PDi=d*和相對中心度PCi=c*。相應的模糊輸入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ù)對應的模糊子集和模糊隸屬度函數(shù)時,主要是參考自然經(jīng)驗,確定的參數(shù)和對應的特征集如表1所示。

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

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

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

2.2.3 模糊規(guī)則

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

表2 模糊規(guī)則

2.2.4 解模糊化

解模糊化是把由模糊規(guī)則生成的輸出量轉變成能實際使用的變量。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é)點的通信代價最小。在周期內,簇內節(jié)點將信息發(fā)送給簇頭節(jié)點,簇頭節(jié)點將收集到的數(shù)據(jù)融合處理后打包發(fā)送給基站,其中數(shù)據(jù)融合消耗的能量為EDA。

2.4 路由的建立

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

圖3 路由建立示意

2.5 路由的維護

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

3 仿真結果

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

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

表3 仿真參數(shù)

3.1 模糊算法模型

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

圖4 MLFC算法模糊推理模型仿真結果

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é)點的能耗和地理位置信息,降低了簇頭給簇內節(jié)點發(fā)送控制信息的能耗,并且進一步減少了簇內通信的能量消耗。因此,MLFC算法具有更好的均衡能耗的效果。

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

3.3 網(wǎng)絡能耗

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

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

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

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

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

4 結論

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

[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)絡分簇路由協(xié)議[J].傳感技術學報,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)絡簇頭半徑自適應調節(jié)路由算法[J].儀器儀表學報,2012,3(8):1779-1785.

[5]劉鐵流,巫詠群.基于能量優(yōu)化的無線傳感器網(wǎng)絡分簇路由算法研究[J].傳感技術學報,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)絡非均勻分簇路由協(xié)議[J].軟件學報,2012,23(5):1222-1232.

[9]孫彥清,彭艦,劉唐,等.基于動態(tài)分區(qū)的無線傳感器網(wǎng)絡非均勻成簇路由協(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)絡技術,Julyforever899@163.com;

萬江文(1963-),男,北京航空航天大學教授,博士生導師,主要研究方向為傳感系統(tǒng)與儀器、傳感網(wǎng)絡與信息融合、定位與跟蹤技術,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