基于模糊邏輯的多跳WSNs分簇算法

章思青,陶 洋,代建建,楊 柳(重慶郵電大學通信與信息工程學院,重慶 400065)

近來,隨著無線通信以及低功耗射頻RF(Radio Frequency)技術的發展,無線傳感器網絡在環境監測、交通、災難救援和國土安全等領域已經得到了廣泛的應用[1-2]。無線傳感器網絡由許多傳感器節點組成,并且都有數據收集和轉發的能力。分簇路由算法是一種有效處理網絡能耗和拓撲控制問題的方法。在分簇結中,每個簇都包含簇首節點和由某種選舉機制創建的成員節點。簇中的成員節點通過多跳通信向簇首節點轉發信息,通過利用AODV[3]機制選擇中繼節點進行路由發現,將數據轉發到基站,實現數據上傳[4]。當為無線傳感器網絡設計分布式分簇算法時,需要考慮多種因素,如節點剩余能量,鄰居節點個數等;因此,如何在多種條件下選擇合適的簇首對整個網絡的穩定性影響很大。

LEACH(Low Energy Adaptive Clustering Hierarchy)協議[5]是WSNs中最經典的分簇算法,它通過選舉簇首,將整個網絡的能量負載到每個傳感器節點,提高動態網絡的可拓展性和魯棒性。文獻[6]是一種將模糊邏輯[7]引入無線傳感器網絡以優化網絡能耗的分簇算法CHEF(Cluster Head Election mechanism using Fuzzy logic in Wireless Sensor Networks)。CHEF算法選擇節點剩余能量和節點與基站之間的距離作為輸入值,計算每個節點的概率選擇簇首,盡管該算法在分布式簇首選舉算法中為無線傳感器網絡提供了一個很好的決策方案,但是忽略了節點鄰居個數對網絡的影響。文獻[8]提出了一種分布式分簇多跳能量感知路由協議EAMMH(Energy Aware Multi-Hop Multi-Path Hierarchical Routing Protocol for Wireless Sensor Networks),主要是根據剩余能量選舉簇首,簇內采用多跳傳輸完成數據的采集,同時簇內也是采用多跳數據傳輸,在一定程度上延長了網絡的生存時間,但是簇間和簇內都采用多跳傳輸,容易出現熱區問題[9]。文獻[10]中也提出了一種分布式分簇算法DFLC(a Distributed Fuzzy Logic-based root selection algorithm for wireless sensor networks),DFLC算法采用模糊邏輯的方法選舉簇首。簇內采用多跳傳輸數據,在節點向簇首傳輸數據時,該算法減少了中繼節點不必要轉發和接受的數據,在選舉簇首之前增加一個過濾機制來改進候選節點的質量。該算法選擇節點剩余能量、到基站的距離和節點密度作為簇頭選舉的依據。但是,DFLC算法忽略了多跳通信中的熱區問題。文獻[11]中提出一種基于模糊邏輯推理的WSNs非均勻分簇算法,該算法充分考慮了剩余節點能量、節點鄰居個數以及節點到基站的距離,選舉簇頭。通過模糊系統輸出簇頭的概率和簇半徑,從而均衡了簇頭間的能量消耗。

為了改善簇內多跳的熱區問題,采用模糊邏輯選擇簇頭,考慮節點剩余能量和節點鄰居節點個數,額外引入鄰居節點的平均剩余能量作為模糊系統輸入。對于簇間多跳之間的熱區問題,提出一種基于斐波那契序列的多跳能量均衡傳輸方法。通過仿真驗證了本文提出的算法的有效性。

圖1 實際場景圖

1 系統模型和分析

1.1 網絡模型

假設監測區域中有N0的傳感器節點,如圖1所示,將網絡中的節點分成不同的簇,每一個簇中產生一個簇頭。簇內節點以多跳或單跳方式發送數據給簇頭,簇頭間以多跳或者直接發送數據給基站。

1.2 能量消耗模型

為了計算出傳感器節點消耗的能量,需要建立設備之間的無線信道傳輸模型,根據文獻[12]得,傳感器節點間的信道模型有兩種:自由空間模型和多徑衰減傳播模型。設發送kbit數據消耗的能量為:

(1)

式中:d為接收端到發送端之間的距離;Eelec為接收電路或者發送電路接收或者發送1 bit數據消耗的能量;εfs與εamp分別為自由空間傳播模型和多徑衰減傳播模型對應的放大特性常數;d0是兩種信道的距離閾值,計算如下:

(2)

在接收端,接收kbit數據消耗的能量計算如下:

ERx(k)=kEelec+k(1/a-1)EDA

(3)

式中:(1/a-1)EDA表示融合1 bits數據消耗的能量,a為融合系數,取值范圍為(0,1];當a=1時,表示數據沒有進行融合。

2 FLCMN算法

2.1 簇頭選擇階段

本節將詳細描述簇頭選擇階段。FLCMN算法采用模糊邏輯推理的方式選擇簇頭。首先,傳感器節點計算自身的剩余能量,鄰居節點的個數,鄰居節點的平均剩余能量,并將這3個變量輸入到模糊系統中,模糊系統輸出簇頭選舉滿意度(Pfitness),表征了該節點成為簇頭的可能性。如圖2所示。

圖2 FLCMN算法模塊圖

設節點剩余能量為Eres。用少(Low)、中(Medium)、高(Hight)3個語言變量表述節點的剩余能量,其隸屬度函數如圖3(c)所示,“少”、“中”和“多”服從三角函數。設鄰居節點的平均剩余能量為Ea,用弱(Weak)、正常(Normal)、強(Strong)3個語言變量表述鄰居節點的平均剩余能量,其隸屬度函數如圖3(b)所示,“正常”、“強”和“弱”符合三角函數。最后將節點鄰居節點個數,記為ω,作為模糊系統的輸入。其隸屬度函數如圖3(a)所示,用“少(Less)”、“平均(Everage)”、“多(Enormous)”表征鄰居節點個數語言變量,“少”和“多”服從梯形函數,“中”服從三角函數。

圖3 輸入變量的隸屬度函數

依圖3可知,模糊系統有表征成為簇頭的滿意度(Pfitness)一個輸出變量,其輸出規則如表1所示,隸屬度函數如圖4所示,12VH和12VL服從梯形函數,其他25個符合三角形函數。

圖4 輸出變量的隸屬度函數

知識庫如表1所示,模糊系統利用文獻[13]的模糊控制重心法,可得到精確輸出值。

表1 FLCMN算法規則庫

計算公式如下:

(4)

Z*是解模糊的輸出,Ui(Z)是融合隸屬度函數,Z是輸出變量。

依據模糊系統的輸出,傳感器節點獲取自己競爭簇頭的滿意度。在形成簇頭之前,每個節點將會計算一個延時值Tdelay-time,計算如下:

(5)

Pfitness是節點當選簇頭的滿意度,取值范圍在[0,100]之間,Tmax是形成簇的最大時間。

2.2 簇頭形成階段

首先,節點在通信范圍內廣播Node_Msg(node_id,node_Eres),每個節點接收到了鄰居節點的信息以后,便計算出鄰居的個數和鄰居節點的平均剩余能量;節點將自身的剩余能量、鄰居節點的個數和鄰居節點的平均剩余能量輸入到模糊系統中求得節點成為簇頭的滿意度(Pfitness),在延時Tdelay-time后,節點向鄰居節點廣播Pre_CH_Msg(node_id,Pfitness)。然后,在時間Tmax結束后,節點和鄰居節點比較成為簇頭的滿意度,如果節點的滿意度大于所有鄰居節點,則節點在通信范圍內廣播Fin_CH_Msg(node_id,Pfitness),否則等待接收Fin_CH_Msg。

最后,節點根據接收到的Fin_CH_Msg,選擇簇頭并發送Node_Join(node_id,Pfitness);如果節點接收多個Fin_CH_Msg,則根據發送信號強度,選擇距離最近的簇頭發送Node_Join,對應簇頭接收到Node_Join后,然后向對應節點回復CH-Accept。如果節點在其通信范圍內,沒有可以加入的簇,則該節點獨立成簇。具體過程如算法1所示。

Algorithm1TheProposedClusteringAlgorithmforFLCMN

2.3 基于斐波那契序列的多跳數據傳輸

首先引入中繼代價函數Cost(CHj),計算如下:

(6)

式中:∑Pfitness(CHi)表示簇頭(CHi)的所有鄰居簇頭滿意度的總和,CHj.Pfitnes表示簇頭(CHj)節點的滿意度,ρ是權重因子,取值范圍為0到1之間。

簇頭節點(CHi)獲取所有鄰居簇頭代價,會選擇到基站距離小于簇頭節點(CHi)到基站的距離的鄰居簇頭,這樣會確保鏈路不會出現回路。表示如下:

CHRelay={CHj|CHj.ND2S

(7)

式中:CHj.ND2S表示簇頭(CHj)到基站的距離,CHi.ND2S表示簇頭(CHi)到基站的距離。根據文獻[14]得斐波那契序列遵循很好的黃金比例,故采用斐波那契序列可以很好均衡簇頭間負載和能量消耗。簇頭節點(CHi)將其鄰居簇頭的中繼代價進行升序排列,根據斐波那契序列給鄰居簇頭分配負載。如圖5所示。

圖5 數據傳輸路徑

假如節點A要發送7個數據包到S,A不會直接發送數據到S,而是通過B、C、D中繼傳輸。假設B、C、D中繼代價函數滿足如下關系:

Cost(B)>Cost(D)>Cost(C)

(8)

根據斐波那契序列:

f(0)=0,f(1)=1,f(n)=f(n-2)+f(n-1),n≥2

(9)

第1輪,節點B傳輸1個數據包,節點D傳輸1個數據包,節點C傳輸2個數據包;第2輪,節點C傳輸2個數據包,節點D傳輸1個數據包,依次類推。同理,簇頭間的傳輸也采用這種負載方式,避免了簇頭承擔過多的中繼數據包,降低熱區問題出現的可能性。

簇形成以后,首先,簇頭就廣播獲取鄰居簇頭的信息,計算出鄰居簇頭的中繼代價。然后,簇頭為簇內成員分配數據傳輸的時隙,簇內成員成員采用多跳方式向簇頭發送數據,非簇頭節點只有在傳輸數據時,才處于活動狀態。簇頭則一直保持非睡眠狀態,簇間采用基于斐波那契序列的多跳數據傳輸。

3 仿真分析

3.1 仿真參數

本節評估FLCMN算法的的性能,利用MATLAB建立仿真平臺,分別從網絡生存時間和網絡能量的消耗兩個方面進行驗證;并與LEACH、EAMMH、DFLC進行比較。在仿真過程中,100個節點隨機分布在200 m×200 m監測區域內。為了在保證網絡性能同時延長網絡的生存時間,故以死亡一半節點時的輪數來表征網絡的生存時間,此處設置最大輪數為600輪,是FLCMN算法運行時節點死亡一半時運行的最大輪數。相關參數設置如表2。

表2 參數表

3.2 仿真結果分析

從能量消耗和網絡壽命兩個方面分析FLCMN算法,其中,網絡壽命從兩個方面進行分析:在第1個節點失效FND(First Node Die)前,所執行的輪數;以及一半節點失效HND(Half Node Die)時,所執行的輪數;而能量的消耗,則從節點平均剩余能量分析。

圖6 網絡的壽命

圖6所示是100次仿真平均的結果,從圖6可以看出,LEACH算法出現FND是在32輪數,因為 LEACH協議只考慮剩余能量選擇簇頭。EAMMH算法出現FND是在44輪數,因為EAMMH算法采簇間采用多跳數據傳輸,選舉簇頭時額外考慮鄰居節點的個數。DFLC算法出現FND是在56輪數,優于以上兩種算法,這是由于DFLC算法采用模糊邏輯選擇簇頭,考慮節點的剩余能量、節點到基站的距離和節點的密度作為模糊系統的輸入。但是,忽略了簇內多跳通信中的熱區問題。與DFLC算法相比,FLCMN算法出現FND是在91輪數,因為FLCMN算法采用模糊邏輯選擇簇頭,考慮了節點剩余能量、節點鄰居個數和鄰居節點的平均剩余能量作為模糊系統的輸入,在簇內多跳傳輸數據時,考慮了鄰居節點的平均剩余能量,將數據轉發任務均勻分配每個節點,保證了簇內中繼節點負載平衡,避免了熱區問題。

圖7是節點死亡的總個數,從圖7可以看出,當運行的輪數超600輪時,4種算法中都死亡了大部分節點,但是FLCMN算法中死亡節點個數還是小于其他算法;可知FLCMN算法的性能優于其他算法,同時驗證了以上的分析。

圖7 節點死亡的個數

圖8是每輪節點平均剩余,表明網絡能量的消耗情況。從圖中看出,LEACH、EAMMH能量消耗的曲線都是迅速下降,DFLC和FLCMN算法能量消耗的曲線都是緩慢下降,這是由于利用了模糊邏輯選擇簇頭,綜合考慮了多種因素,增加簇頭選擇的合理性。FLCMN算法能量消耗的能量優于DFLC主要由于兩個方面,第一、考慮鄰居節點的剩余能量作為選擇簇頭的因素,減少了簇內中繼節點的熱區問題,同時,第二、簇間采用了基于斐波那契序列的多跳數據傳輸,減少了采用一個簇頭中繼消耗的能量,將負載均勻分配到多個簇頭。

圖8 每輪節點平均剩余能量

4 結論

本文提出了基于模糊邏的多跳WSNs分簇算法,旨在降低整個網絡的能量消耗,提高網絡的壽命。具體來說,利用模糊邏輯輸出選舉簇頭的滿意度,根據簇頭滿意度的大小選舉簇頭。FLCMN算法不僅考慮了節點的剩余能量和節點鄰居個數,而且還考慮了鄰居節點平均剩余能量水平,避免了熱區問題的出現,同時均衡了簇內節點的消耗;此外提出一種基于斐波那契序列的簇間多跳傳輸方法,避免一個簇頭承載過多的數據傳輸量,進一步延長網絡的生存時間。仿真結果表明,FLCMN算法能夠有效地提高網絡的壽命,FLCMN算法在網絡壽命和能量消耗方面的性能優于LEACH、EAMMH、DCFL算法。