馬 超,汪 偉,安斯光

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1.2 能耗模型

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

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

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

(1)

其中d0用式(2)表示:

(2)

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

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

(3)

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

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

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

E=ETx+ERx+n×Ed

(4)

1.3 評價指標(biāo)

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

1) 目標(biāo)函數(shù)

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

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

(5)

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

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

(6)

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

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

(7)

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

2) 充電時間

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

(8)

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

3) 充電效用

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

(9)

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

2 分簇算法

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

2.1 K-means算法

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

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

2.2 簇首選舉機(jī)制

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

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

(10)

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

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

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

步驟1 取隨機(jī)k個位置當(dāng)選最開始的聚類中心。

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

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

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

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

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

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

3.1 改進(jìn)的蟻群算法

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

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

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

(11)

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

(12)

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

2) 信息素更新

在所有螞蟻完成一次路徑搜索之后,節(jié)點(diǎn)之間螞蟻?zhàn)哌^的路徑進(jìn)行信息素更新,如式(13):

(13)

3) 算法終止條件

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

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

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

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

步驟3k=k+1。

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

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

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

步驟7 若k

步驟8 進(jìn)行信息素更新,比較所有螞蟻?zhàn)疃搪窂讲⒂涗洝?/p>

步驟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)化算法進(jìn)行仿真,并對實(shí)驗結(jié)果進(jìn)行分析。實(shí)驗參數(shù)設(shè)置如表1。

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

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

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

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

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

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

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

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

表2 分簇算法對比

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

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

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

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

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

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

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

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

表4 算法收斂速度對比

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

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

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

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

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

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

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

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

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

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

5 結(jié) 語

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