基于模糊密度峰聚類和PSO的WSN能量均衡算法

張 勇,呂黎明

(江蘇海洋大學(xué)計(jì)算機(jī)工程學(xué)院,江蘇連云港 222000)

1 引言

在能源有限的無線傳感器網(wǎng)絡(luò)中,如何設(shè)計(jì)一種高效節(jié)能的路由算法,延長網(wǎng)絡(luò)的生存周期,是WSN研究的關(guān)鍵[1]。針對(duì)這一問題,研究者提出了不同類型的路由算法延長WSN的生命周期。其中常用且有效的一種方式是聚類路由優(yōu)化算法。通過將傳感器節(jié)點(diǎn)聚類能夠?qū)崿F(xiàn)提高能源效率和網(wǎng)絡(luò)的使用壽命,達(dá)到無線傳感器網(wǎng)絡(luò)高效節(jié)能的目的[2]。

WSN分簇路由協(xié)議中,最典型的是LEACH(Low Energy Adaptive Clustering Hierarchy)協(xié)議[3]。該算法引入輪的概念,每輪分為簇的建立和數(shù)據(jù)傳輸階段,通過概率機(jī)制周期性選取簇頭[4]。該算法研究的主要目的是通過減少能源消耗來提高WSN的壽命,雖然該協(xié)議有優(yōu)點(diǎn),但它的簇頭選取策略無法保證簇頭均勻分布在整個(gè)網(wǎng)絡(luò)。SU L[5]對(duì)LEACH協(xié)議進(jìn)行了優(yōu)化,提出了一種基于LEACH-GAF算法的分簇路由協(xié)議。通過GAF算法在每輪開始時(shí)將所有節(jié)點(diǎn)劃分成不同區(qū)域,然后應(yīng)用LEACH算法的概率機(jī)制在每個(gè)區(qū)域內(nèi)選擇簇頭。該算法雖然可以保證簇頭分布的均勻,但無法保證選取最優(yōu)簇頭。崔小勇等人[6]提出基于遺傳模擬退火算法,優(yōu)化簇頭到基站的傳輸路徑,均衡節(jié)點(diǎn)的剩余能量,延長網(wǎng)絡(luò)生存周期。

聚類協(xié)議被證明是實(shí)現(xiàn)WSN節(jié)約能量的有效方法,如何選擇最優(yōu)CH成為聚類算法的關(guān)鍵部分[7]。現(xiàn)有的聚類協(xié)議存在關(guān)于聚類結(jié)構(gòu)的問題,這會(huì)對(duì)協(xié)議的聚類性能產(chǎn)生不利影響[8]。同時(shí),由于傳感器節(jié)點(diǎn)是隨機(jī)部署在一定區(qū)域,節(jié)點(diǎn)的分配存在模糊性和不確定性。為了解決上述問題,本文提出了一種基于FDPC和PSO優(yōu)化的無線傳感器網(wǎng)絡(luò)能量均衡路由算法(FDPC-PSO)。本研究的貢獻(xiàn)總結(jié)如下:

1)采用的FDPC算法具有模糊分區(qū)的優(yōu)勢(shì),可以提高聚類性能的靈活性,在處理集群的模糊性和不確定性方面提供了額外的潛力。

2)將數(shù)據(jù)傳輸路徑的選擇規(guī)劃為NP完全問題,并采用PSO算法優(yōu)化傳輸路徑,提高能量利用率。

2 系統(tǒng)模型

在本節(jié)中,將介紹系統(tǒng)模型,包括網(wǎng)絡(luò)模型和能量消耗模型。

2.1 網(wǎng)絡(luò)模型和假設(shè)

本文研究的是由一個(gè)基站(BS)和200個(gè)傳感器節(jié)點(diǎn)隨機(jī)分布在100*100 m2區(qū)域內(nèi)的靜態(tài)傳感器網(wǎng)絡(luò)。傳感器節(jié)點(diǎn)用S={s1,s2,…,sn}表示,傳感器節(jié)點(diǎn)的位置信息表示為(xi,yi),1≤i≤n。引入無向圖G(V,E)的概念,將簇頭節(jié)點(diǎn)存入V中,簇頭節(jié)點(diǎn)之間的鏈路由E存儲(chǔ)。每個(gè)簇都由不同數(shù)量的成員節(jié)點(diǎn)和一個(gè)簇頭構(gòu)成,成員節(jié)點(diǎn)與簇頭之間可以進(jìn)行信息交流。每個(gè)簇頭節(jié)點(diǎn)與基站的最短路徑,將簇頭節(jié)點(diǎn)通過粒子群算法構(gòu)建成鏈,相互之間以多跳網(wǎng)絡(luò)的形式進(jìn)行數(shù)據(jù)傳輸。網(wǎng)絡(luò)模型如圖1所示。

圖1 網(wǎng)絡(luò)模型

對(duì)系統(tǒng)模型有如下假設(shè):

·所有的傳感器節(jié)點(diǎn)都是同質(zhì)的。

·所有的傳感器節(jié)點(diǎn)具有相同的初始能量且能量受限制。

·基站能量不受限制。

·基站記錄傳感器節(jié)點(diǎn)的位置信息。

·所有節(jié)點(diǎn)都隨機(jī)部署在目標(biāo)區(qū)域內(nèi),可以與基站建立連接。

2.2 能量消耗模型

在WSN中,傳感器節(jié)點(diǎn)的能量消耗主要集中在信息的感知、處理以及節(jié)點(diǎn)之間的通信(接收和轉(zhuǎn)發(fā)數(shù)據(jù))等方面,其中節(jié)點(diǎn)之間進(jìn)行數(shù)據(jù)的傳輸是最耗費(fèi)能量的過程,由于信息的感知和處理過程與路由無關(guān),因此文中只考慮通信過程產(chǎn)生的能量消耗。

文中采用Heinzelman等[9]提出的能耗模型。根據(jù)發(fā)送節(jié)點(diǎn)與接收節(jié)點(diǎn)之間的距離,分別使用自由空間(Efs)模型和多路徑衰落信道(Emp)模型對(duì)信道進(jìn)行建模。如果發(fā)送節(jié)點(diǎn)與接收節(jié)點(diǎn)之間的距離小于閾值d0,則根據(jù)自由空間模型(d2功率能耗),計(jì)算能量消耗;否則,使用多路徑衰落模型(d4功率損耗),計(jì)算能量消耗。由于在不同的信道模型中,傳輸相同大小的數(shù)據(jù)所消耗的能量不同,因此能量消耗取決于發(fā)送節(jié)點(diǎn)與接收節(jié)點(diǎn)之間的距離。傳輸kbits的數(shù)據(jù)所消耗的能量為式(1)所示

(1)

傳感器節(jié)點(diǎn)接收kbits數(shù)據(jù)所消耗的能量為

ERx=Eelec×k

(2)

因此,傳感器節(jié)點(diǎn)進(jìn)行數(shù)據(jù)通信所需要消耗的總能量為

ETR=ETx+ERx

(3)

此外,還需要對(duì)簇頭節(jié)點(diǎn)能耗進(jìn)行計(jì)算。簇頭節(jié)點(diǎn)的能耗來源于三部分:接收簇中成員節(jié)點(diǎn)的數(shù)據(jù)所消耗的能量ER＿ch,融合數(shù)據(jù)所消耗的能量EF＿ch以及將融合后的數(shù)據(jù)傳輸?shù)交舅柘牡哪芰縀T＿ch。

簇頭節(jié)點(diǎn)接受來自簇中成員節(jié)點(diǎn)的數(shù)據(jù)所需要消耗的能量為

ER＿ch=m×k×Eelec

(4)

其中m表示該輪進(jìn)行數(shù)據(jù)傳輸?shù)某蓡T節(jié)點(diǎn)數(shù)量。

簇頭節(jié)點(diǎn)需要融合的數(shù)據(jù)來源于兩部分:一部分是成員節(jié)點(diǎn)傳來的數(shù)據(jù),另一部分是簇頭節(jié)點(diǎn)本身收集到的數(shù)據(jù),共有m+1個(gè)節(jié)點(diǎn)的數(shù)據(jù)需要融合。因此簇頭節(jié)點(diǎn)融合數(shù)據(jù)所需要消耗的能量為

EF＿ch=(m+1)×k×EDA

(5)

其中EDA為融合1bit數(shù)據(jù)所需要消耗的能量。

簇頭節(jié)點(diǎn)將融合后的數(shù)據(jù)傳輸?shù)交舅柘牡哪芰繛?/p>

(6)

所以,可以得到簇頭節(jié)點(diǎn)進(jìn)行數(shù)據(jù)通信的總能耗為

Ech=ER＿ch+EF＿ch+ET＿ch

=k×(2m+1)×(Eelex+EDA)

(7)

3 基于FDPC-PSO的分簇路由算法

為了提高能源效率,延長WSN的使用壽命,本文提出了一種高效的FDPC-PSO路由算法。該算法與Leach算法具有相同的框架結(jié)構(gòu),分輪數(shù)進(jìn)行,每輪分為三個(gè)階段:基于FDPC聚類階段,簇頭選擇階段以及數(shù)據(jù)傳輸階段。第一階段通過FDPC算法優(yōu)化網(wǎng)絡(luò)部署,將傳感器節(jié)點(diǎn)分為不同的簇,在網(wǎng)絡(luò)中以集群的形式部署傳感器節(jié)點(diǎn)。第二階段為簇頭選取階段。從第二輪開始,每輪運(yùn)行前BS更新每個(gè)簇中節(jié)點(diǎn)的剩余能量并將其發(fā)送給簇頭節(jié)點(diǎn)。簇頭節(jié)點(diǎn)計(jì)算本簇中剩余能量均值Eavg,并將此值設(shè)置為選取候選節(jié)點(diǎn)的能量閾值。然后,計(jì)算候選節(jié)點(diǎn)當(dāng)選簇頭所需的能量消耗,能量消耗最少者,當(dāng)選此輪的簇頭。第三階段為穩(wěn)態(tài)階段。采用PSO算法優(yōu)化傳輸路徑,將所有CH連接到一個(gè)鏈中,建立到BS最短通信路徑。該方法縮短了總傳輸距離,有效地減少了能量消耗。

3.1 基于FDPC聚類

FDPC聚類方法是由Wang[10]對(duì)DPC算法的改進(jìn)。在DPC框架的基礎(chǔ)上,采用模糊算子和正S型函數(shù)計(jì)算密度峰值。模糊密度峰值的使用改進(jìn)了DPC在劃分集群的模糊性和不確定性等方面的不足。FDPC算法進(jìn)行聚類的關(guān)鍵是求出最優(yōu)的聚類中心。聚類中心應(yīng)該同時(shí)具備兩個(gè)特點(diǎn):在某一區(qū)域內(nèi)該節(jié)點(diǎn)密度最大和與其它密度大的節(jié)點(diǎn)之間的距離相對(duì)更遠(yuǎn)。針對(duì)以上兩個(gè)特點(diǎn),式(8)、(9)定義了模糊密度ρi和距離δi兩個(gè)量。通過FDPC算法聚類的具體步驟如下

輸入:包含n個(gè)節(jié)點(diǎn)的矩陣X,參數(shù)ω,最近鄰的數(shù)量k,高斯核寬σ以及閾值T

步驟1:計(jì)算每個(gè)節(jié)點(diǎn)的模糊密度ρi。模糊密度計(jì)算公式ρi為

ρi=f(?(xi,x1))?f(?(xi,x2))?…?f(?(xi,xk))

(8)

(9)

其中?為模糊算子,f(x)是關(guān)于?(xi,xj)的正雙射隸屬函數(shù),反映節(jié)點(diǎn)xi和xj之間的相似性,表達(dá)式如式(10)所示

ER＿ch=m×k×Eelec

(10)

步驟2:根據(jù)式(11)計(jì)算出節(jié)點(diǎn)與比其密度大的節(jié)點(diǎn)之間的距離δi。

(11)

步驟3:根據(jù)式(12)、(13),選出聚類中心。

γi=ρi·δi

(12)

(γi-γi+1)>T

(13)

T為事先給定的閾值。將γi降序排列,γi的值越大,越適合當(dāng)選簇頭。式(13)確定簇頭的個(gè)數(shù)p,從降序序列中選取前p個(gè)節(jié)點(diǎn)組成簇頭向量C={c1,c2…,cp}。

步驟4:劃分簇。

聚類中心選取后,基于距離因素劃分簇。詳細(xì)過程如下:將ρi(i=1,2,…n)降序排列,得到降序排列下標(biāo)序列qi(i=1,2…n)。在模糊密度大于xi的節(jié)點(diǎn)中,最接近xi的節(jié)點(diǎn)的編號(hào)定義為nqi,用來定義非簇頭節(jié)點(diǎn)的歸類屬性。

(14)

所有節(jié)點(diǎn)標(biāo)簽為li。當(dāng)lqi=-1時(shí),通過lqi=lnqi更新li。每個(gè)節(jié)點(diǎn)會(huì)得到一個(gè)新的標(biāo)簽,此標(biāo)簽值就是非簇頭節(jié)點(diǎn)所在簇的序號(hào)。

(15)

3.2 簇頭選取

完成聚類階段后,得到了首輪運(yùn)行的簇頭節(jié)點(diǎn),在首輪運(yùn)行后,部分節(jié)點(diǎn)的剩余能量發(fā)生變化。為了避免某些節(jié)點(diǎn)的過度使用,造成能量消耗不均,需要在每一輪運(yùn)行前,根據(jù)節(jié)點(diǎn)剩余能量和相對(duì)距離動(dòng)態(tài)更新簇頭?；鞠蛎總€(gè)簇頭發(fā)送簇中所有節(jié)點(diǎn)的剩余能量,簇頭通過式(16)計(jì)算出該簇剩余能量均值Eavg,并將其設(shè)定為該簇閾值,此后每一輪都將進(jìn)行此操作,動(dòng)態(tài)調(diào)整閾值。若節(jié)點(diǎn)的剩余能量高于該閾值,將此節(jié)點(diǎn)設(shè)定為候選簇頭(CCH)。對(duì)候選簇頭采用下列方法進(jìn)行簇頭的選取:該方法主要考慮距離因素對(duì)能耗的影響,該距離包括CCH與簇中成員節(jié)點(diǎn)之間的距離以及與BS之間的距離。通過式(17),基站計(jì)算每個(gè)候選節(jié)點(diǎn)若當(dāng)選簇頭后,進(jìn)行數(shù)據(jù)傳輸所需要消耗的總能量。能量消耗最少者,當(dāng)選此輪運(yùn)行的簇頭。在CH選擇過程結(jié)束后,BS將更新網(wǎng)絡(luò)中的傳感器節(jié)點(diǎn)剩余能量。

(16)

×ERch(xi)+EtoBS(xi→BS)

(17)

其中:Etoch(xj→xi)表示傳感器節(jié)點(diǎn)xj將數(shù)據(jù)包發(fā)送到CCH(xi)所需要消耗的能量。

ERch(xi)表示CCHxi從傳感器節(jié)點(diǎn)xj接收數(shù)據(jù)包所消耗的能量。

EtoBS(xi→BS)表示CCHxi向基站(BS)發(fā)送聚合數(shù)據(jù)包時(shí)所消耗的能量。

3.3 PSO優(yōu)化路徑

針對(duì)數(shù)據(jù)傳輸線路的隨意性,導(dǎo)致能量利用率低這一問題,將簇頭節(jié)點(diǎn)與基站之間的數(shù)據(jù)傳輸規(guī)劃為TSP問題,并采用全局搜索能量強(qiáng)的PSO方法優(yōu)化傳輸路徑。將所有的簇頭節(jié)點(diǎn)連接成鏈,規(guī)劃出所有簇頭節(jié)點(diǎn)與基站進(jìn)行數(shù)據(jù)通信的最短路徑。

1)PSO算法優(yōu)化原理

PSO算法是模擬鳥群的捕食行為而智能建立的群體優(yōu)化算法。PSO算法的優(yōu)化原理可總結(jié)為:在每次迭代過程中,每個(gè)粒子將自身的局部優(yōu)解(pBest)發(fā)送個(gè)群體,群體根據(jù)所有的pBest獲取動(dòng)態(tài)的全局最優(yōu)解(gBest),通過式(18)和(19),每個(gè)粒子根據(jù)gBest和pBest調(diào)整自身的速度v和位置,并更新自身的pBest,循環(huán)此過程,直到滿足終止條件。

vi(t+1)=wvi+c1rand(pBest(t)-xi(t))

+c2rand(gBest(t)-xi(t))

(18)

xi(t+1)=xi(t)+vi(t+1)

(19)

其中,c1和c2為局部和全局加速系數(shù),設(shè)置其值為c1=c2=1.5,rand為[0-1]之間的隨機(jī)數(shù),w為慣性因子,w∈[wmin,wmax],用于表示粒子的尋優(yōu)能力,可由式(20)表示。

(20)

其中,iter為當(dāng)前迭代次數(shù),itermax為最大的迭代次數(shù)。

2)傳輸路徑優(yōu)化

在無向圖G(V,E)中,V=(c1,c2,…,cp)為每輪運(yùn)行前選取的CH,設(shè)置CH為TSP的問題規(guī)模,E={(a,b):a,b∈V}表示所有CH之間鏈路,CH到基站的路徑作為優(yōu)化目標(biāo)。粒子群的規(guī)模設(shè)置為100,最高迭代次數(shù)為200次。CHi和基站之間的最短路徑為piB。當(dāng)所有粒子完成它們的遍歷,達(dá)到收斂條件后,在“Routing[]”中記錄了所有粒子的路徑,計(jì)算所有路徑的長度,然后輸出每個(gè)粒子最短路徑piB。

PSO優(yōu)化的算法流程如下所示:

步驟1:設(shè)置TSP問題的城市規(guī)模,以及PSO算法所需的參數(shù)。

步驟2:初始化粒子的速度和位置。

步驟3:計(jì)算適應(yīng)度函數(shù)值,即CH到基站的距離。

步驟4:根據(jù)粒子的適應(yīng)度函數(shù)值更新pBest和gBest。

步驟5:根據(jù)式(13)、(14),更新粒子的位置和速度。

步驟6:更新迭代次數(shù)并記錄粒子的路徑Routing。

步驟7:判斷是否滿足迭代終止條件,若滿足,則執(zhí)行步驟7,否則,重復(fù)步驟2-步驟4步。

步驟8:輸出最短路徑piB。

4 仿真結(jié)果

在本節(jié)中,對(duì)提出的FDPC-PSO算法進(jìn)行模擬,并通過仿真結(jié)果來評(píng)估所提算法的性能。仿真軟件為python 2019,運(yùn)行設(shè)備為Lenovo 小新Air-14,Intel Core i5 1.00GHz,win10,內(nèi)存為16G。在模擬實(shí)驗(yàn)中,將200個(gè)傳感器節(jié)點(diǎn)隨機(jī)部署在100x100 m2區(qū)域的無線傳感器網(wǎng)絡(luò)中。BS被部署在WSN區(qū)域的中心位置(50,50)處,如圖2。網(wǎng)絡(luò)節(jié)點(diǎn)在初始參數(shù)方面是相同的。實(shí)驗(yàn)所需其它參數(shù)見表1?？紤]五個(gè)參數(shù)對(duì)算法的性能進(jìn)行評(píng)估,包括第一個(gè)死亡節(jié)點(diǎn)、百分之五十節(jié)點(diǎn)死亡、全部節(jié)點(diǎn)死亡、網(wǎng)絡(luò)生存時(shí)間以及網(wǎng)絡(luò)的剩余能量。

表1 無線傳感器網(wǎng)絡(luò)模擬參數(shù)

圖2 節(jié)點(diǎn)部署

4.1 基于網(wǎng)絡(luò)生存周期的比較

FDPC-PSO、EE-LEACH和ACO-K-MEANS三種算法在每輪運(yùn)行后剩余存活的節(jié)點(diǎn)數(shù)量如圖3。從結(jié)果可以觀察到,FDPC-PSO具有最長的生存周期。同時(shí),FPDC-PSO算法的曲線下降是最緩慢的,意味著FDPC-PSO可以更好的分配能量使用,保證能耗平衡,均衡網(wǎng)絡(luò)負(fù)載,保證能源效率的最大化。

圖3 每輪的存活節(jié)點(diǎn)數(shù)

圖4 (a)第一個(gè)節(jié)點(diǎn)死亡(b)百分之五十節(jié)點(diǎn)死亡(c)最后一個(gè)節(jié)點(diǎn)死亡

4.2 基于死亡節(jié)點(diǎn)數(shù)的比較

FDPC-PSO,EE-LEACH以及ACO-K-MEANS三種算法分別在第一個(gè)節(jié)點(diǎn)、百分之五十節(jié)點(diǎn)以及全部節(jié)點(diǎn)死亡所運(yùn)行的輪數(shù)如圖3。 通過圖可以看出,FDPC-PSO在前百分之五十節(jié)點(diǎn)死亡與后百分之五十節(jié)點(diǎn)死亡運(yùn)行時(shí)間大致相同。相比另外兩種算法,死亡節(jié)點(diǎn)比較緩慢,可以達(dá)到均衡使用能量。此外,該算法具有更久的生存周期。EE-LEACH中,最后一個(gè)節(jié)點(diǎn)死亡出現(xiàn)在第4038輪,ACO-K-MEANS出現(xiàn)在第4124輪,而在FDPC-PSO中最后一個(gè)節(jié)點(diǎn)死亡出現(xiàn)在第4781輪。相比EE-LEACH和ACO-K-MEANS,分別提高了18.4%和15.9%。

4.3 基于剩余能量的比較

隨著輪數(shù)的運(yùn)行,網(wǎng)絡(luò)的剩余能量情況如圖5?？梢钥闯?FDPC-PSO算法每輪運(yùn)行的能耗低于其它兩種算法。該算法可以有效的節(jié)省能量,能量性能得到提高,并延長網(wǎng)絡(luò)生存周期。

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

5 結(jié)論

在本文,提出了一種基于FDPC和PSO的無線傳感器網(wǎng)絡(luò)聚類路由算法。該算法首先通過FDPC聚類算法將WSN中的傳感器節(jié)點(diǎn)劃分為簇,并在每輪運(yùn)行前,基于動(dòng)態(tài)能量閾值和最小化能耗兩因素更新簇頭。將數(shù)據(jù)傳輸通路擴(kuò)展到求解TSP問題,并采用PSO算法來確定網(wǎng)絡(luò)中的路由路徑,優(yōu)化傳輸路徑,減少不必要的能量消耗。在實(shí)驗(yàn)過程中,對(duì)第一個(gè)節(jié)點(diǎn)死亡、百分之五十節(jié)點(diǎn)死亡、最后一個(gè)節(jié)點(diǎn)死亡、總剩余能量以及總運(yùn)行輪數(shù)進(jìn)行分析。仿真結(jié)果表明,與EE-LEACH和PSO-K-MEANS相比,所提出的FDPC-PSO算法可以從能源效率、網(wǎng)絡(luò)壽命和能耗等方面提高網(wǎng)絡(luò)性能。