基于模糊規(guī)則的WSNs分簇路由算法

趙夢龍,鄭宇超

(1.貴州職業(yè)技術(shù)學(xué)院信息工程學(xué)院,貴陽 550003;2.華東交通大學(xué)軟件學(xué)院,南昌 330013)

無線傳感器網(wǎng)絡(luò)WSNs(Wireless Sensor Networks)通過在監(jiān)控區(qū)域內(nèi)部署海量廉價(jià)、微型傳感節(jié)點(diǎn)實(shí)現(xiàn)對環(huán)境監(jiān)測的目的。傳感節(jié)點(diǎn)自行構(gòu)建網(wǎng)絡(luò),并通過網(wǎng)絡(luò)將感測數(shù)據(jù)傳輸至控制中心[1]。而節(jié)點(diǎn)的數(shù)據(jù)傳輸效率與節(jié)點(diǎn)能量緊切相關(guān)。若節(jié)點(diǎn)能量消耗殆盡,節(jié)點(diǎn)將無法感測數(shù)據(jù),更難以完成數(shù)據(jù)的傳輸。

然而,WSNs內(nèi)的節(jié)點(diǎn)一般通過電池供電。由于WSNs常采用隨機(jī)方式部署傳感節(jié)點(diǎn),即使電池耗盡,也不便更換電池[3]。因此,降低節(jié)點(diǎn)能耗是WSNs的一個(gè)研究熱點(diǎn)[4]。

傳輸數(shù)據(jù)所消耗的能量占據(jù)了節(jié)點(diǎn)能耗的大部分。為此,研究人員采用層次型路由實(shí)現(xiàn)數(shù)據(jù)傳輸,進(jìn)而降低能耗。作為最經(jīng)典的分簇路由,低功耗自適應(yīng)層次路由 LEACH(Low Energy Adaptive Clustering Hierarchy)[5]將WSNs劃分多個(gè)簇。每個(gè)簇由一個(gè)簇頭和簇成員構(gòu)成。簇頭收集本簇成員的數(shù)據(jù),并進(jìn)行一定的處理,再傳輸至控制中心。LEACH路由引用“輪”的方式均衡網(wǎng)絡(luò)內(nèi)節(jié)點(diǎn)的能耗,進(jìn)而延長WSNs壽命。然而,LEACH路由產(chǎn)生簇頭的策略存在不足。它是以隨機(jī)方式產(chǎn)生簇頭,并沒有考慮到節(jié)點(diǎn)的剩余能量信息。為此,研究人員提出不同的LEACH路由的優(yōu)化算法。

董發(fā)志等[6]采用遺傳算法優(yōu)化簇頭的選擇。在選擇簇頭過程中考慮了距離、節(jié)點(diǎn)能量信息。張雅瓊利用K-Means算法進(jìn)行分簇(KMCR)[7]。但是該算法在選擇簇頭時(shí)并沒有考慮節(jié)點(diǎn)間的距離關(guān)系。而張靜靜引用粗糙C-均值聚類對LEACH路由進(jìn)行改進(jìn)[8],提高簇頭節(jié)點(diǎn)分布的均勻性。

此外,文獻(xiàn)[9]引用網(wǎng)格概念,將每個(gè)網(wǎng)格內(nèi)能量最高的節(jié)點(diǎn)作為簇頭。而文獻(xiàn)[10]通過智能算法構(gòu)建最小生成樹,并依據(jù)最小生成樹傳輸數(shù)據(jù),進(jìn)而降低能耗。而文獻(xiàn)[11]先利用概率模型產(chǎn)生多個(gè)分簇集合,然后選擇能量最高的節(jié)點(diǎn)作為簇頭。

為此,提出基于模糊規(guī)則算法的分簇-能效-路由算法FLECR(Fuzzy Logic-based Energy-efficient Clustering Routing)。FLECR路由仍采用輪方式構(gòu)建簇。但與LEACH路由不同,FLECR路由并非在每一輪都重新分簇,而是采用按需方式。并通過模糊規(guī)則決策該簇是否需要重新分簇。只有需要重新分簇的簇就進(jìn)行構(gòu)建簇,而那些無需分簇的簇就保存簇頭不變,減少了頻繁構(gòu)建簇和執(zhí)行簇頭選擇所消耗的能量。仿真結(jié)果表明,提出的FLECR路由有效地降低了能耗,并提高網(wǎng)絡(luò)吞吐量。

1 預(yù)備知識

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

FLECR路由采用按需方式重新分簇概念。最初先建立若干簇。然后,再依據(jù)各簇的信息,決策是否下一輪進(jìn)行重新分簇。所謂重新分簇就是重新進(jìn)行簇頭選舉以及簇形成。通過該策略,降低頻繁地構(gòu)建簇,減少能耗。如圖1所示,在第i輪進(jìn)行簇頭選舉,但是在第i+1輪未進(jìn)行簇選舉和簇形成階段。即FLECR路由并非采用固定方式進(jìn)行簇頭選舉,而是采用按需方式進(jìn)行簇頭選舉。

圖1 FLECR路由輪次

圖2 無線電能量消耗模型

1.2 能量消耗模型

考慮自由空間和多徑兩類衰減情況[12],如圖2所示。假定發(fā)送端與接收端間距離為d。發(fā)送端將k比特?cái)?shù)據(jù)傳輸至接收端所消耗的能量Etx(k,d):

(1)

接收端接收k比特?cái)?shù)據(jù)所消耗的能量Erx(k):

Erx(k)=kEelec

(2)

2 FLECR路由

2.1 初始分簇

(3)

在定時(shí)時(shí)間Ti內(nèi),節(jié)點(diǎn)si監(jiān)聽是否收到其他節(jié)點(diǎn)發(fā)送的通告消息M_Ch_adv。值得一提的是:FLECR路由規(guī)定,當(dāng)節(jié)點(diǎn)選舉成簇頭時(shí),節(jié)點(diǎn)就向鄰居節(jié)點(diǎn)廣播簇頭通告消息M_Ch_adv。

圖3 簇頭選舉和簇形成的流程

當(dāng)收到M_Ch_adv消息,表明已有節(jié)點(diǎn)被選舉成為簇頭。節(jié)點(diǎn)就將該簇頭加入自己的鄰居簇頭集Ψ。假定節(jié)點(diǎn)sj廣播M_Ch_adv(sj)消息,節(jié)點(diǎn)si收到M_Ch_adv(sj)。在這種情況下,節(jié)點(diǎn)si就將節(jié)點(diǎn)sj加入鄰居簇頭集Ψi,如式(4)所示:

Ψi←Ψi∪{sj}

(4)

若定時(shí)時(shí)間Ti內(nèi),未收到其他節(jié)點(diǎn)發(fā)送的 M_Ch_adv 消息,節(jié)點(diǎn)si就在定時(shí)時(shí)間結(jié)束后,立即 廣播通告消息M_Ch_adv(si),即宣稱自己為簇頭。

節(jié)點(diǎn)si的鄰居簇頭集Ψi不空時(shí),表明節(jié)點(diǎn)si收到多個(gè)節(jié)點(diǎn)廣播的通告消息。在這種情況下,節(jié)點(diǎn)就從Ψi選擇剩余能量大的作為自己的簇頭。同時(shí),向該簇頭發(fā)送加入消息M_join。整個(gè)流程如圖3所示。

2.2 基于模糊規(guī)則的簇重構(gòu)

FLECR路由先通過2.1節(jié)進(jìn)行初步分簇,并產(chǎn)生簇頭[13]。接下來,簇頭依據(jù)剩余能量、相對距離以及本簇內(nèi)活動節(jié)點(diǎn)中心度三項(xiàng)信息,并結(jié)合邏輯規(guī)則決策是否在下一輪進(jìn)行重新選舉簇頭,如圖4所示。

圖4 模糊規(guī)則系統(tǒng)

將相對剩余能量、距離和相對中心度作為模糊規(guī)則系統(tǒng)的輸入,再通過推理系統(tǒng)產(chǎn)生輸出變量Out。再將輸出變量Out判斷是否在下一輪進(jìn)行重新分簇。

2.2.1模糊變量

①簇頭離信宿距離

(5)

式中:d(Chi,Sink)表示簇頭Chi離信宿的直接距離。而dmax、dmin分別表示網(wǎng)絡(luò)內(nèi)簇頭離信宿的最遠(yuǎn)距離、離信宿的最近距離。

②相對剩余能量

(6)

③相對中心度

引用文獻(xiàn)[14]節(jié)點(diǎn)中心度,計(jì)算簇頭的中心度。

(7)

式中:(xi,yi)表示簇頭Chi的位置坐標(biāo)。

2.2.2 模糊變量模糊化

將簇頭的剩余能量、相對距離和中心度三個(gè)變量作為模糊輸入值,按需參數(shù)作為輸出變量。三個(gè)模糊變量的隸屬度函數(shù)如表1所示。

表1 隸屬度函數(shù)

依據(jù)三個(gè)輸入變量制定模糊規(guī)則,如表2所示。共27條規(guī)則。

表2 規(guī)則庫

接下來,通過控制輪長度限定重新分簇次數(shù)。令Li表示簇頭Chi是否在下一輪進(jìn)行重新分簇的標(biāo)志值。若Li=1,則表示在下一輪進(jìn)行重新分簇。若Li=2,則表示間隔一輪就進(jìn)行重新分簇;若Li=3,則表示間隔兩輪才進(jìn)行重新分簇。據(jù)此,對Li進(jìn)行定義,如式(8)所示:

Li=max(Out,1)

(8)

式中:Out表示模糊規(guī)則的輸出。

3 性能分析

為了更好地分析FLECR路由性能,通過MATLAB R2012b建立仿真平臺[15]。在邊長100 m的正方形區(qū)域內(nèi)隨機(jī)部署100個(gè)節(jié)點(diǎn),且基站位于區(qū)域中心,且基站位置為(50 m,50 m)。具體仿真參數(shù)如表3所示。

表3 仿真參數(shù)

同時(shí),選用LEACH路由和KMCR路由作為參照,并對比分析FLECR路由與LEACH、KMCR路由的性能,包括死亡節(jié)點(diǎn)數(shù)、生命周期、網(wǎng)絡(luò)能耗和吞吐量。

3.1 實(shí)驗(yàn)一

首先分析FLECR、LEACH和KMCR路由的死亡節(jié)點(diǎn)數(shù),如表4所示。從表4可知,FLECR路由的死亡節(jié)點(diǎn)數(shù)出現(xiàn)的最晚,其在2238輪出現(xiàn)第一個(gè)死亡節(jié)點(diǎn),比LEACH和KMCR路由進(jìn)行大幅度推遲。而FLECR、LEACH和KMCR路由分別在2 441輪、1 261輪和2 243輪時(shí)有50%節(jié)點(diǎn)死亡。

表4 3個(gè)路由的死亡節(jié)點(diǎn)數(shù)出現(xiàn)的輪數(shù)

圖5顯示三個(gè)路由的活動節(jié)點(diǎn)數(shù)。用活動節(jié)點(diǎn)數(shù)表征網(wǎng)絡(luò)的生命周期。從圖5可知,在同一輪數(shù),FLECR路由活動節(jié)點(diǎn)數(shù)遠(yuǎn)高于LEACH路由、KMCR路由。原因在于:FLECR路由減少重新構(gòu)建簇的頻率,降低能耗。

圖5 活動節(jié)點(diǎn)數(shù)

3.2 實(shí)驗(yàn)二

本次實(shí)驗(yàn)分析三個(gè)路由的網(wǎng)絡(luò)能耗,如圖6所示。從圖6可知,在執(zhí)行同等的輪數(shù)時(shí),FLECR路由的剩余能量最高,高于LEACH路由和KMCR路由。這主要是因?yàn)?FLECR路由采用按需方式?jīng)Q策是否重新分簇,減少了構(gòu)建簇的頻率。同時(shí),依據(jù)節(jié)點(diǎn)能量選擇簇頭,延長簇頭壽命。

圖6 網(wǎng)絡(luò)剩余能量

3.3 實(shí)驗(yàn)三

部署傳感網(wǎng)絡(luò)的根本目的在于收集監(jiān)測區(qū)域內(nèi)的環(huán)境數(shù)據(jù)。據(jù)此,吞吐量是評價(jià)網(wǎng)絡(luò)性能的重要指標(biāo)。

圖7顯示了基站在不同輪數(shù)所收的數(shù)據(jù)量。從圖7可知,隨著輪數(shù)的增加,基站所收的數(shù)據(jù)量線性增加。但當(dāng)輪數(shù)增加至一定輪數(shù)后,數(shù)據(jù)量不再增加。

圖7 網(wǎng)絡(luò)吞吐量

此外,相比于LEACH路由和KMCR路由,提出的FLECR路由有效地提升基站所接收的數(shù)據(jù)量,增加了吞吐量。原因在于:FLECR網(wǎng)絡(luò)生命周期更長,傳感節(jié)點(diǎn)能夠監(jiān)測更多數(shù)據(jù)。

4 總結(jié)

分簇路由是降低WSNs能耗的有效方式。為此,提出基于模糊規(guī)則分簇-能效-路由FLECR。FLECR路由采用不固定時(shí)間進(jìn)行分簇,依據(jù)按需方式進(jìn)行簇重構(gòu)。同時(shí),引用模糊規(guī)則產(chǎn)生簇頭。依據(jù)簇頭的剩余能量、距離以及中心度決策重構(gòu)簇的時(shí)間間隔,避免了頻繁地重構(gòu)簇,降低了能耗。仿真數(shù)據(jù)證實(shí),提出的FLECR路由有效地提升了能效,延長了網(wǎng)絡(luò)壽命,并增加了網(wǎng)絡(luò)吞吐量。