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

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

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

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

圖1 實際場景圖

1 系統(tǒng)模型和分析

1.1 網(wǎng)絡模型

假設監(jiān)測區(qū)域中有N0的傳感器節(jié)點,如圖1所示,將網(wǎng)絡中的節(jié)點分成不同的簇,每一個簇中產(chǎn)生一個簇頭。簇內節(jié)點以多跳或單跳方式發(fā)送數(shù)據(jù)給簇頭,簇頭間以多跳或者直接發(fā)送數(shù)據(jù)給基站。

1.2 能量消耗模型

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

(1)

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

(2)

在接收端,接收kbit數(shù)據(jù)消耗的能量計算如下:

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

(3)

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

2 FLCMN算法

2.1 簇頭選擇階段

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

圖2 FLCMN算法模塊圖

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

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

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

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

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

表1 FLCMN算法規(guī)則庫

計算公式如下:

(4)

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

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

(5)

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

2.2 簇頭形成階段

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

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

Algorithm1TheProposedClusteringAlgorithmforFLCMN

2.3 基于斐波那契序列的多跳數(shù)據(jù)傳輸

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

(6)

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

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

CHRelay={CHj|CHj.ND2S

(7)

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

圖5 數(shù)據(jù)傳輸路徑

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

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

(8)

根據(jù)斐波那契序列:

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

(9)

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

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

3 仿真分析

3.1 仿真參數(shù)

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

表2 參數(shù)表

3.2 仿真結果分析

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

圖6 網(wǎng)絡的壽命

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

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

圖7 節(jié)點死亡的個數(shù)

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

圖8 每輪節(jié)點平均剩余能量

4 結論

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