基于分簇的WSN充電路徑優(yōu)化算法研究

馬 超,汪 偉,安斯光

(中國計量大學 機電工程學院,浙江 杭州 310018)

無線傳感器網(wǎng)絡(Wireless Sensor Network,WSN)由多個傳感器節(jié)點組成,其具有感知、計算、存儲等特點,已經(jīng)廣泛應用于軍事、環(huán)境監(jiān)測、交通管理等方面[1]。受節(jié)點體積的影響,傳感器節(jié)點只能攜帶極小容量的電池,自身儲存電量較少,所以傳感器節(jié)點的電量有限問題已經(jīng)成為WSN持續(xù)運行的瓶頸;這些節(jié)點通常放置于危險、復雜的環(huán)境下,人為進行維護變得困難。

解決上述問題的主要方式有:對網(wǎng)絡進行分簇從而降低WSN數(shù)據(jù)傳輸能耗;通過無線充電的方式,采用移動充電車(Mobile Charging Vehicle,WCV)為傳感器節(jié)點充電。

網(wǎng)絡分簇是WSN減少自身能耗的一種重要方式,尤其是對中大型WSN,分簇能夠減小簇內(nèi)能量消耗。從WSN中選取傳感器節(jié)點當選簇首節(jié)點,簇首節(jié)點承擔主要能量消耗,簇首節(jié)點能夠接收其他節(jié)點發(fā)送的數(shù)據(jù)并進行數(shù)據(jù)融合,減少數(shù)據(jù)發(fā)送量,通過這種方式達到降低網(wǎng)絡平均能量消耗,延長網(wǎng)絡存活時間的目的。文獻[2]提出了WSN的一種經(jīng)典分簇協(xié)議——LEACH協(xié)議。LEACH可以通過隨機選擇簇首與數(shù)據(jù)融合的方式減少網(wǎng)絡通信能耗。在LEACH的基礎上,文獻[3]提出了LEACH-CC改進方案,對節(jié)點列出一個簇首當選次序,每個節(jié)點根據(jù)次序依次當選簇首節(jié)點。文獻[4]基于LEACH提出能量均衡的改進算法,引入節(jié)點電量等因素進行分簇,從而優(yōu)化簇首節(jié)點選擇。文獻[5]提出了多點改進的K-means算法,使用K-means算法依據(jù)傳感器節(jié)點的位置進行劃分,然后在簇內(nèi)進行簇首選擇。文獻[6]提出了一種NSGA-Ⅱ多目標聚類算法,用該算法實現(xiàn)聚類分簇,根據(jù)用戶的需求從中選擇其中任意解。LEACH協(xié)議雖然能減小能耗,但是也有它的不足之處:簇首的選舉是完全隨機的,能量低的節(jié)點也可能當選為簇首,導致節(jié)點電量過早衰竭。

采用移動充電車給傳感器節(jié)點進行充電是延長節(jié)點壽命的有效方式,如何對充電路徑進行優(yōu)化是一個關(guān)鍵問題。WSN中的充電規(guī)劃問題與車輛路徑問題類似,相關(guān)的優(yōu)化算法有蟻群算法(Ant Colony Optimization,ACO)、模擬退火算法、遺傳算法等[7-9]。蟻群算法采用分布式計算方法,具有全局搜索能力強、信息正反饋等特點,被廣泛應用于該類問題[10-11]。文獻[12]還提出了一種基于貪心策略的在線充電算法,每次選擇距離充電車最近的節(jié)點充電。文獻[13]基于K-means算法將網(wǎng)絡劃分為多個集群,提出用兩個充電車相反方向移動進行充電。雖然以上研究能解決一定的充電路徑問題,但是傳感器節(jié)點的充電優(yōu)先程度不同,WCV若不能及時到達需要充電的節(jié)點,節(jié)點可能會面臨能量耗盡的問題。

在一次充電周期中,也需要考慮為不同數(shù)目的節(jié)點進行充電時,是否會影響充電效用,所以考慮設置充電閾值。有些文獻提出為所有節(jié)點進行充電,此時不設閾值。文獻[14]提出了給全部節(jié)點充電的充電方案,無線充電車一個充電行程為網(wǎng)絡里所有節(jié)點充電,避免有傳感器節(jié)點死亡。還有些文獻提出選取一個閾值,為電量在閾值之下的節(jié)點進行充電,對部分節(jié)點進行充電。文獻[15]提出了一種按需充電的充電方案,低于閾值的傳感器節(jié)點提出充電請求,充電設備制定好充電次序之后依次為傳感器充電。可是,設閾值是否能提高充電效用沒有做出比較說明。

針對上述問題。本文將網(wǎng)絡分簇和移動充電路徑規(guī)劃結(jié)合,提出基于分簇的WSN充電優(yōu)化算法。本文主要有以下三點貢獻。

1) 提出head-K-means分簇方法。將簇首選舉機制和K-means算法結(jié)合,將距離相近的節(jié)點分配到同一個簇中,制定簇首輪換規(guī)則,用更加合理的簇首選擇方式替代隨機選舉簇首。

2) 提出改進的蟻群算法(Modified Ant Colony Algorithm,MACO)。將傳感器剩余電量這個影響因子添加到算法的轉(zhuǎn)移規(guī)則中,與啟發(fā)因子、信息素濃度共同決定螞蟻下一節(jié)點的選擇,從而優(yōu)化WCV的充電路線,同時提高算法收斂速度。

3) 充電閾值仿真實驗分析。通過實驗結(jié)果分析不同充電閾值對充電效用的影響,并得出最佳充電閾值。

1 WSN網(wǎng)絡模型

1.1 結(jié)構(gòu)模型

在本文中采用如下所述結(jié)構(gòu)模型:WSN部署在一個二維區(qū)域上,區(qū)域內(nèi)隨機分布n個規(guī)格相同的傳感器節(jié)點,每個節(jié)點的位置是固定和已知的;基站位于WSN的中心位置,基站接收傳感器節(jié)點發(fā)送的數(shù)據(jù)并決定所需充電的傳感器節(jié)點,并將該信息發(fā)送給WCV;WCV從起始點出發(fā),采取一對一的方式為節(jié)點充電,充電完成后再回到起始點。

每個傳感器節(jié)點都配備了相同容量的可無線充電電池,傳感器具有相同的計算和通信級別,電池的最大容量用Emax表示。Ei表示節(jié)點i的當前電量,WCV行駛距離用L表示。需要充電的傳感器設為集合G,G包含m個傳感器,其中0

圖1 網(wǎng)絡結(jié)構(gòu)示意圖Figure 1 WSN structure diagram

1.2 能耗模型

傳感器節(jié)點的能耗主要產(chǎn)生于數(shù)據(jù)的發(fā)送,特別是在數(shù)據(jù)量比較大的情況下,節(jié)點長期工作在數(shù)據(jù)的發(fā)送和收集狀態(tài)。每個傳感器節(jié)點監(jiān)測周圍環(huán)境并生成數(shù)據(jù),并將自身收集到的數(shù)據(jù)發(fā)送給簇首節(jié)點。

在本文的WSN中,假設所有節(jié)點的電池容量完全相同,但是節(jié)點的初始電量不同,節(jié)點能夠監(jiān)測自身電池的剩余電量。由于本文考慮到網(wǎng)絡分簇,簇首節(jié)點和普通節(jié)點的能耗不同,為了便于計算,使用文獻[16]中的能量損耗模型:

在d距離下傳輸abit數(shù)據(jù)所消耗的能量如式(1)。

(1)

其中d0用式(2)表示:

(2)

接收abit所需能耗由式(3)表示:

ERx(a)=ERx_elec(a)=aEelec。

(3)

式(3)中,a為節(jié)點的數(shù)據(jù)監(jiān)測量。Eelec為節(jié)點發(fā)送或接受1 bit所需要的能量消耗;εfs為自由空間時功率放大器的消耗參數(shù);εtrg為多路徑傳輸時功率放大器的消耗參數(shù)。因為接收端不需要進行信號放大,所以接收端沒有放大器的能耗。

由于簇首節(jié)點需要對數(shù)據(jù)進行融合,在進行數(shù)據(jù)融合時也需要消耗一定的能量。假設融合1 bit數(shù)據(jù)所消耗的能量記為Ed。則簇首節(jié)點接收nbit數(shù)據(jù)之后,對nbit數(shù)據(jù)進行融合,然后發(fā)送給基站。

簇首的能耗表達式如式(4):

E=ETx+ERx+n×Ed

(4)

1.3 評價指標

選取充電路徑長度和WCV充電一周所需要的時間以及充電效用作為評價指標。

1) 目標函數(shù)

最終的目標是得到充電路徑,所以優(yōu)化充電路徑就是本文的主要目標。目標函數(shù)用WCV的移動距離來表示,即WCV完成一周充電所移動的距離,如式(5):

L(x)=dist(start,x[1])+

(5)

式(5)中,L(x)為路徑長度,start為充電車的起點,用x代表每個傳感器節(jié)點,x[i]為WCV第i個到達的傳感器節(jié)點,dist表示距離。

為了避免在充電過程中出現(xiàn)節(jié)點死亡,加入一個約束條件,WCV在到達充電節(jié)點之前要保證該節(jié)點的剩余電量大于0,所以節(jié)點i的電量Ei要保證滿足式(6),即WCV到達該節(jié)點之前,傳感器節(jié)點剩余電量能維持正常工作。

(6)

式(6)中,Li是WCV到達節(jié)點i所需要走的路徑長度,τj為WCV給節(jié)點j的充電時間。s為節(jié)點電量平均消耗速度。如果不滿足該約束條件,則添加一個懲罰函數(shù)。

所以,此時的目標函數(shù)如式(7):

(7)

式(7)中,p(x)為懲罰函數(shù),M為懲罰因子,c為常數(shù),懲罰因子設置為遠大于L(x)的數(shù),如果得到的充電路徑中不滿足約束條件(6),則c=1;否則c=0。

2) 充電時間

充電時間用T來表示,充電時間由兩部分構(gòu)成,一個是WCV充電時移動所需要的時間,另一個是為傳感器節(jié)點充電所需要的時間,如式(8):

(8)

式(8)中,τi為WCV在節(jié)點i的充電時間。

3) 充電效用

WCV充電效用其含義是:WCV向節(jié)點補充的能量與其消耗的總能量的比值。如式(9):

(9)

式(9)中,用Ei表示節(jié)點i的剩余電量。Eroute代表WCV充電一周移動消耗的電量。

2 分簇算法

在充電之前首先要對網(wǎng)絡進行分簇。本文提出新簇首選舉機制的head-K-means算法進行分簇。在該算法中,網(wǎng)絡分簇分成三個步驟:1) K-means算法進行區(qū)域劃分;2) 簇首選擇;3) 簇首輪換。

2.1 K-means算法

K-means算法是一種基于距離的聚類算法,因其算法簡潔、方便高效的特點使得它成為使用最廣泛的聚類方法。將距離作為相似度程度的評價標準,即認為節(jié)點之間的距離越近,他們的相似度就越大,相似度的接近程度決定了節(jié)點能否分到相同的簇中。

首先將數(shù)據(jù)預分為k組,然后隨機選取k個對象作為初始的聚類中心;計算每個對象與各個聚類中心之間的距離,然后每個對象分配給距離它最近的聚類中心,聚類中心以及分配給它的對象就組成了一個聚類;每分配一個對象,根據(jù)類中現(xiàn)有的對象對聚類中心重新進行計算;這個過程將不斷重復直到滿足沒有聚類中心再發(fā)生變化。

2.2 簇首選舉機制

在分簇過程中,簇首的選舉是尤其重要的。在有些分簇算法中,簇首的選舉是隨機的,這樣會加大節(jié)點之間電量的不均衡。K-means算法一般只是計算出簇的范圍,將質(zhì)心作為整個簇的中心,這樣雖然簇首節(jié)點到簇內(nèi)子節(jié)點的平均距離是最短的,但是簇首節(jié)點的負擔很重,大大增加了中心節(jié)點的能耗。所以需要設計一種動態(tài)選取簇首的方法。

本文綜合考慮了節(jié)點剩余電量、節(jié)點位置、當選簇首次數(shù)等因素,動態(tài)選擇最優(yōu)的節(jié)點當選簇首,并且在完成一輪數(shù)據(jù)收集之后,輪換簇首節(jié)點。簇首選擇方法如式(10),C最大的節(jié)點成為簇首。

(10)

式(10)中,Ei表示節(jié)點i的剩余電量,Eave(m)表示第m個簇的平均電量。Ai表示節(jié)點當過簇首的次數(shù)。D(i)表示簇首節(jié)點到i節(jié)點的距離,Dmax(m)表示第m個簇內(nèi)子節(jié)點與簇首節(jié)點的最大距離,D(i)to_base表示節(jié)點i到基站的距離。α,β,γ是三個影響因子,在設定的時候遵循一定的原則,當網(wǎng)絡整體電量較低時,α的值設置較大;當更看重網(wǎng)絡節(jié)點間相互距離時,β此時需要占主導地位;當需要考慮節(jié)點當選簇首次數(shù)的時候,γ設置成為較大的值。

2.3 head-K-means算法實現(xiàn)步驟

head-K-means算法的具體步驟如下。

步驟1 取隨機k個位置當選最開始的聚類中心。

步驟2 網(wǎng)絡中所有節(jié)點通過計算與聚類中心的距離,并加入最近的聚類中心所在的簇中,直到所有的節(jié)點找到自己的簇。

步驟3 根據(jù)節(jié)點位置,計算所生成的k個簇的中心坐標,得到簇中心位置。

步驟4 當簇心位置不再變化時,算法結(jié)束,此時得到的分簇結(jié)果就是期望的結(jié)果。否則繼續(xù)迭代,重復執(zhí)行步驟二,直到簇心位置不再變化。

步驟5 根據(jù)公式(10)選舉簇首。

步驟6 若發(fā)送完一輪數(shù)據(jù),重復以上步驟。

3 充電路徑優(yōu)化算法

3.1 改進的蟻群算法

在本文中傳感器節(jié)點的電量健康狀況是十分重要的。傳統(tǒng)的蟻群算法只考慮了信息素濃度和啟發(fā)路徑函數(shù)兩個方面來確定下一節(jié)點的選擇,卻忽視了節(jié)點剩余電量的影響,從而在充電過程中出現(xiàn)節(jié)點死亡的情況。

1) 修改的轉(zhuǎn)移概率

轉(zhuǎn)移概率是蟻群算法的核心,螞蟻會根據(jù)轉(zhuǎn)移概率來選擇下一個要訪問的傳感器節(jié)點,在蟻群算法的轉(zhuǎn)移概率中添加節(jié)點當前電量,如式(11):

(11)

式(11)中,τij表示節(jié)點i與節(jié)點j連接路徑上的信息素濃度;α為信息素重要程度因子,其值越大,表示信息素濃度在選擇下一充電節(jié)點中起的作用越大。β為啟發(fā)信息重要程度因子,其值越大,表示啟發(fā)信息在轉(zhuǎn)移中的作用越大,即螞蟻就會以較大的概率轉(zhuǎn)移到距離較近的節(jié)點。Ej是傳感器節(jié)點j的剩余電量,c為常數(shù),γ為電量因素重要程度因子,當網(wǎng)絡節(jié)點電量處于較低水平時,γ的值要相應增大。allowk表示G中還沒有被充電的傳感器節(jié)點集合。式中啟發(fā)信息ηij如式(12):

(12)

式(12)中,dij表示節(jié)點i到節(jié)點j的距離。由于下一個節(jié)點選擇是一個概率問題,螞蟻依然有可能向距離自身較遠或者信息素濃度較低的路線移動。

2) 信息素更新

在所有螞蟻完成一次路徑搜索之后,節(jié)點之間螞蟻走過的路徑進行信息素更新,如式(13):

(13)

3) 算法終止條件

在蟻群算法中,完成一次迭代的標志是所有螞蟻都完成路徑搜索,所以開始時要確定螞蟻的數(shù)量,還要設置最大迭代次數(shù)。當所有螞蟻都完成一次路徑搜索,迭代次數(shù)加1,直到達到最大迭代次數(shù)條件時,算法結(jié)束,此時得到的收斂路徑即為最佳路徑,輸出該路徑長度,同時把該條路徑保存。

3.2 改進的蟻群算法實現(xiàn)步驟

步驟1 初始化參數(shù):節(jié)點位置、螞蟻個數(shù)m、最大迭代次數(shù)Nmax、螞蟻位置。

步驟2 迭代次數(shù)N=N+1。

步驟3k=k+1。

步驟4 計算節(jié)點的剩余工作時間、螞蟻跟各節(jié)點之間的距離。

步驟5 根據(jù)公式(11)選擇下一充電節(jié)點。

步驟6 更新禁忌表,重復步驟5,直到所有待充電節(jié)點完成充電。

步驟7 若k

步驟8 進行信息素更新,比較所有螞蟻最短路徑并記錄。

步驟9 若N

3.3 基于分簇的充電路徑算法流程圖

基于head-K-means分簇的WSN充電路徑優(yōu)化算法完整的流程圖如圖2。

圖2 算法流程圖Figure 2 Algorithm flow chart

4 仿真及結(jié)果分析

在Matlab環(huán)境下分別對分簇算法以及分簇后MACO優(yōu)化算法進行仿真,并對實驗結(jié)果進行分析。實驗參數(shù)設置如表1。

表1 仿真參數(shù)設置

在后面三小節(jié)里分別對分簇算法、充電優(yōu)化算法以及充電效用進行實驗仿真,并對結(jié)果進行分析。

針對現(xiàn)有文獻中提到的全部節(jié)點充電和部分節(jié)點充電,哪種方式更能夠提高充電效用問題。用本文基于分簇的充電路徑優(yōu)化算法對不同閾值下充電效用進行比較分析,得出充電效用與設置閾值之間是否存在關(guān)系。

4.1 分簇算法仿真及結(jié)果分析

為了驗證本文head-K-means分簇算法的有效性,與LEACH分簇算法進行比較,比較兩種算法在不進行充電情況下,出現(xiàn)節(jié)點死亡的時間、網(wǎng)絡持續(xù)運行時間。圖3為head-K-means算法和LEACH算法兩個方面的對比圖。

圖3(a)為能量耗盡節(jié)點個數(shù)對比圖。橫坐標為網(wǎng)絡運行輪數(shù),縱坐標為能量耗盡節(jié)點個數(shù),從圖中可以看出,head-K-means算法中能量耗盡的節(jié)點出現(xiàn)的輪數(shù)明顯后移。圖3(b)為網(wǎng)絡剩余能量對比圖。在初期兩種算法的能耗接近,但是隨著實驗輪數(shù)不斷增加,使用LEACH算法網(wǎng)絡平均剩余能量下降速度更快。使用LEACH算法時,在大概350輪時網(wǎng)絡的平均剩余能量降為0;而使用本文算法時,在500輪時網(wǎng)絡的平均剩余能量才降為0,所以能得出head-K-means算法的能耗比LEACH算法更小。

圖3 分簇算法對比圖Figure 3 Comparison diagram of clustering algorithm

表2為兩種分簇算法,出現(xiàn)節(jié)點死亡和全部節(jié)點死亡的輪數(shù)。LEACH分簇算法第一個死亡節(jié)點大概出現(xiàn)在150輪,而本文head-K-means算法第一個死亡節(jié)點大概出現(xiàn)在200輪,推遲了33%左右;在大概350輪時網(wǎng)絡全部節(jié)點死亡,而本文算法出現(xiàn)在510輪,推遲了大概46%。

表2 分簇算法對比

綜上所述,與LEACH算法相比,本文提出的head-K-means分簇算法更能夠均衡網(wǎng)絡的能耗,延長網(wǎng)絡工作時間。

4.2 充電路徑優(yōu)化算法仿真及結(jié)果分析

使用head-K-means分簇算法后,采用MACO算法進行充電。從實驗中選取了一個WCV移動路徑圖,如圖4。圖中中心信號塔為基站,五角星為每個簇的簇首節(jié)點,其他不同形狀的符號代表不同簇中的節(jié)點。WCV的起始點為(0,0)點。

為了驗證MACO算法的有效性,與兩種經(jīng)典充電調(diào)度算法進行對比:ACO算法和EDF算法。ACO算法為原始的蟻群算法。EDF算法稱為最早截止優(yōu)先算法,根據(jù)節(jié)點電量所能維持的工作時間動態(tài)分配優(yōu)先級,工作時間越短,優(yōu)先級越高;工作時間越長,優(yōu)先級越低。

用本文的MACO算法與ACO算法以及EDF算法進行比較,從全部節(jié)點中選取電量最低的10～50節(jié)點構(gòu)成需要充電的傳感器集合G。每個實驗分別進行30次并取平均值。

全部實驗數(shù)據(jù)平均值如表3。

表3 三種算法實驗數(shù)據(jù)對比

表4為MACO算法和ACO算法收斂速度對比,從中可以看出兩者都有較快的收斂速度,并且MACO收斂速度更快。

表4 算法收斂速度對比

圖5為WCV充電路徑長度對比圖,從圖中可以看到本文的MACO算法明顯優(yōu)于其他兩種,而且隨著待充電節(jié)點數(shù)目的增加,優(yōu)勢更加明顯。

圖5 路徑長度對比圖Figure 5 Comparison chart of path length

圖6為WCV充電一周所需要的時間對比圖,從中可以看出,當待充電節(jié)點個數(shù)較少時,如G中有10個節(jié)點時,三種方法WCV所用的時間大小比較接近,隨著網(wǎng)絡規(guī)模的增大,MACO算法更優(yōu)于ACO算法,相比于EDF算法優(yōu)勢更加明顯。

圖6 WCV充電一輪時間對比圖Figure 6 Comparison chart of WCV charging round time

圖7為網(wǎng)絡充電效用對比圖,同樣在G中只有10個節(jié)點時,三種算法的差距不大,隨著節(jié)點數(shù)量的增多,MACO算法的優(yōu)勢更加明顯,即MACO算法的WCV充電效用更高。

圖7 充電效用對比圖Figure 7 Comparison chart of charging utility

4.3 不同閾值下充電效用對比

隨著電量閾值增大,需要充電的節(jié)點會增多,充電效用更能反映能量利用率。為了分析不同充電閾值對充電效用影響,本文通過仿真實驗對比不同閾值下充電效用。進行多組仿真實驗,每組進行30次實驗,結(jié)果取平均值,如圖8。

取閾值區(qū)間30%～90%以及不設閾值進行對比,給電量處于閾值之下的節(jié)點進行充電。分析圖8可以得到,當閾值過小或者閾值過大都不能得到最佳的充電效用,最佳充電效用出現(xiàn)在53%～55%,從而可以得出充電閾值的大小能夠影響充電效用。

圖8 不同閾值下充電效用對比圖Figure 8 Comparison chart of charging utility under different thresholds

5 結(jié) 語

本文提出了一種基于分簇的WSN充電路徑優(yōu)化算法,并通過實驗仿真驗證了算法的有效性。首先提出新簇首選擇機制的head-K-means分簇算法,與LEACH算法相比,第一個死亡節(jié)點出現(xiàn)時間推遲了33%左右;全部節(jié)點死亡時間推遲了大概46%。提出改進的蟻群算法對分簇后的WSN進行充電路徑優(yōu)化研究,把節(jié)點剩余電量加入到螞蟻概率轉(zhuǎn)移規(guī)則中,仿真結(jié)果表明,MACO優(yōu)化算法相比于ACO算法和EDF算法在充電車充電移動距離、充電時間以及充電效用方面都有一定的優(yōu)勢。最后對比了不同充電閾值下充電效用,實驗表明充電閾值能夠影響充電效用,在本文實驗環(huán)境下53%～55%左右時充電效用最大。