張 永,韓 睿,徐華榮,王文浩,王肖叢,孫田弋,孫御驥

(1.國(guó)網(wǎng)浙江省電力有限公司,浙江杭州 310000;2.國(guó)網(wǎng)浙江省電力有限公司電力科學(xué)研究院,浙江杭州 310000;3.南京南瑞信息通信科技有限公司,江蘇南京 210000;4.山東大學(xué)微電子學(xué)院,山東濟(jì)南 250000)

0 引言

無(wú)線傳感器網(wǎng)絡(luò)具備成本低、低功耗、部署靈活的優(yōu)勢(shì),在智能控制、自動(dòng)化工程、網(wǎng)絡(luò)自動(dòng)化等諸多領(lǐng)域得到了廣泛應(yīng)用[1]。傳感器節(jié)點(diǎn)部署及網(wǎng)絡(luò)覆蓋是決定網(wǎng)絡(luò)感知和通信質(zhì)量的關(guān)鍵,直接影響網(wǎng)絡(luò)生存時(shí)間和網(wǎng)絡(luò)管理效率[2-3]。為了滿足覆蓋需求,將大量WSN節(jié)點(diǎn)隨機(jī)拋灑于監(jiān)測(cè)區(qū)域,會(huì)導(dǎo)致覆蓋盲區(qū)、節(jié)點(diǎn)密度過高和冗余節(jié)點(diǎn)多等問題,覆蓋盲區(qū)會(huì)降低區(qū)域監(jiān)測(cè)質(zhì)量,節(jié)點(diǎn)密度過高和冗余節(jié)點(diǎn)多則會(huì)導(dǎo)致過多數(shù)據(jù)轉(zhuǎn)發(fā)的能耗浪費(fèi)、通信擁塞、冗余數(shù)據(jù)多等問題,這些問題會(huì)降低網(wǎng)絡(luò)可靠性和增加節(jié)點(diǎn)能耗。因此,優(yōu)化WSN節(jié)點(diǎn)部署,提高監(jiān)測(cè)區(qū)域覆蓋率具有重要意義。

將WSN節(jié)點(diǎn)部署與智能優(yōu)化算法結(jié)合,可以利用智能優(yōu)化算法強(qiáng)大的隨機(jī)啟發(fā)式搜索機(jī)制加快節(jié)點(diǎn)覆蓋尋優(yōu)過程。文獻(xiàn)[4]利用混合遺傳與差分進(jìn)化對(duì)WSN節(jié)點(diǎn)覆蓋優(yōu)化問題求解,最大化節(jié)點(diǎn)覆蓋率。文獻(xiàn)[5]利用虛擬力粒子群算法優(yōu)化WSN覆蓋后將覆蓋率提升了5個(gè)百分點(diǎn)。文獻(xiàn)[6]利用改進(jìn)人工蜂群算法優(yōu)化WSN節(jié)點(diǎn)部署,網(wǎng)絡(luò)覆蓋率得到了改善,但依然有較多覆蓋盲區(qū)。文獻(xiàn)[7]利用改進(jìn)灰狼優(yōu)化算法將WSN節(jié)點(diǎn)覆蓋率提升了4個(gè)百分點(diǎn),但仍存在分布不均勻。文獻(xiàn)[8]利用自適應(yīng)動(dòng)態(tài)混沌量子粒子群算法將覆蓋率優(yōu)化至90%。鯨魚優(yōu)化算法[9]、果蠅算法[10]等也均應(yīng)用在了WSN節(jié)點(diǎn)覆蓋優(yōu)化問題中。然而,智能算法本身也存在尋優(yōu)精度上的不足,尤其容易造成搜索與精細(xì)開采過程失衡和帶來(lái)局部最優(yōu)的缺陷。同時(shí),以上研究考慮的場(chǎng)景均是無(wú)障礙物簡(jiǎn)單環(huán)境的節(jié)點(diǎn)覆蓋優(yōu)化,未討論監(jiān)測(cè)區(qū)域內(nèi)存在復(fù)雜障礙物的節(jié)點(diǎn)覆蓋優(yōu)化問題,實(shí)用性有限。

樽海鞘群算法SSA是一種新型智能優(yōu)化算法[11],其結(jié)構(gòu)簡(jiǎn)單、參數(shù)少,能夠有效提升尋優(yōu)精度,在圖像分割[12]、特征選擇[13]、作業(yè)調(diào)度[14]等問題上得到廣泛應(yīng)用。但標(biāo)準(zhǔn)SSA算法還存在著早熟收斂和求解精度低的不足。為了更好地解決障礙物環(huán)境中的WSN節(jié)點(diǎn)覆蓋優(yōu)化問題,本文將設(shè)計(jì)一種多策略融合改進(jìn)樽海鞘群算法MSISSA。為了提高SSA的尋優(yōu)性能,設(shè)計(jì)模糊邏輯種群角色調(diào)整機(jī)制,對(duì)領(lǐng)導(dǎo)者種群規(guī)模動(dòng)態(tài)調(diào)整;設(shè)計(jì)多項(xiàng)式變異擾動(dòng)機(jī)制對(duì)跟隨者變異,增強(qiáng)跟隨者局部隨機(jī)搜索能力;設(shè)計(jì)拓?fù)鋵?duì)立學(xué)習(xí)機(jī)制生成領(lǐng)導(dǎo)者拓?fù)鋵?duì)立解,充分挖掘區(qū)域內(nèi)的精英位置信息。在復(fù)雜障礙物環(huán)境下以WSN節(jié)點(diǎn)覆蓋率最大為目標(biāo),利用改進(jìn)算法優(yōu)化WSN節(jié)點(diǎn)覆蓋問題,求解節(jié)點(diǎn)最優(yōu)部署位置。并開展實(shí)驗(yàn)驗(yàn)證改進(jìn)算法的性能。

1 樽海鞘群算法SSA

樽海鞘群算法種群由領(lǐng)導(dǎo)者和跟隨者組成,并組成鏈?zhǔn)浇Y(jié)構(gòu)。鏈?zhǔn)讉€(gè)體為領(lǐng)導(dǎo)者個(gè)體,其他個(gè)體均為跟隨者個(gè)體。跟隨者在領(lǐng)導(dǎo)者的牽引下搜索食物源。令N為種群規(guī)模,D為搜索空間維度,SSA中樽海鞘個(gè)體的位置信息存儲(chǔ)于N×D的二維矩陣內(nèi),個(gè)體i可表示為Xi={xi,1,xi,2,…,xi,D},xi,j表示個(gè)體i在j維度上的位置,j=1,2,…,D。令種群的搜索目標(biāo)為F,領(lǐng)導(dǎo)者的位置更新方式為

(1)

式中:[lbj,ubj]為個(gè)體在j維度上的搜索邊界值;Fj為搜索目標(biāo)的j維度值;x1,j(t+1)為鏈?zhǔn)最I(lǐng)導(dǎo)者的j維更新位置;t為當(dāng)前迭代次數(shù);c2、c3為均勻分布隨機(jī)數(shù),c2、c3∈[0,1];c2控制移動(dòng)步長(zhǎng),c1用于搜索算法的全局搜索與局部開發(fā)轉(zhuǎn)換。

c1的定義為

(2)

式中:t為當(dāng)前迭代次數(shù);Tmax為最大迭代次數(shù)。

跟隨者的位置更新方式為

(3)

式中:xi,j(t)、xi,j(t+1)分別為個(gè)體i(i≥2)在j維度上的原位置和更新位置;xi-1,j(t)為相鄰個(gè)體的j維位置。

2 多策略融合改進(jìn)樽海鞘群算法MSISSA

2.1 基于模糊邏輯的種群角色調(diào)整

SSA算法中,領(lǐng)導(dǎo)者代表著種群的優(yōu)勢(shì)群體,但算法迭代搜索過程中,領(lǐng)導(dǎo)者的樽海鞘種群規(guī)模是維持不變的。然而,算法迭代早期,較大規(guī)模領(lǐng)導(dǎo)者有利于SSA算法進(jìn)行更充分的全局搜索,加快算法的收斂速度;而到了算法迭代后期,應(yīng)更側(cè)重于局部開發(fā),此時(shí)領(lǐng)導(dǎo)者規(guī)模應(yīng)該隨之減少,以便于SSA算法進(jìn)行精細(xì)開發(fā),提高算法的收斂精度。

為了對(duì)領(lǐng)導(dǎo)者種群規(guī)模進(jìn)行動(dòng)態(tài)的自適應(yīng)調(diào)整,MSISSA算法引入一種基于模糊推理系統(tǒng)的領(lǐng)導(dǎo)者個(gè)體數(shù)量占比非線性更新機(jī)制。模糊推理系統(tǒng)是以模糊邏輯為理論基礎(chǔ),實(shí)現(xiàn)多輸入變量與單輸出變量間復(fù)雜非線性映射關(guān)系的方法,其結(jié)構(gòu)如圖1所示。定義領(lǐng)導(dǎo)者占比因子的模糊推理系統(tǒng)的2個(gè)輸入變量為種群多樣性φ和算法迭代階段κ。其中,種群多樣性φ表示每個(gè)樽海鞘個(gè)體與當(dāng)前最優(yōu)解個(gè)體間的歐氏距離,定義為

圖1 模糊推理系統(tǒng)

(4)

式中:N為種群規(guī)模;D為搜索維度;xi,j(t)為迭代t時(shí)個(gè)體i在維度j上的位置;xbest,j(t)為當(dāng)前迭代最優(yōu)解的j維度位置。

由此可見,種群多樣性φ能夠描述種群個(gè)體在搜索空間內(nèi)分布的分散程度。個(gè)體間距離越大,則個(gè)體位置相對(duì)越分散,其種群多樣性也越好;反之,個(gè)體間距離越小,種群越趨于集中,種群多樣性也越差。

迭代階段κ表示算法當(dāng)前迭代次數(shù)與最大迭代次數(shù)之比,定義為

κ=t/Tmax

(5)

式中Tmax為算法的最大迭代次數(shù)。

輸入變量種群多樣性φ和迭代階段κ在模糊推理系統(tǒng)中的隸屬度函數(shù)設(shè)計(jì)如圖2所示。

(a)輸入變量為迭代階段

種群多樣性φ以3個(gè)隸屬度函數(shù)分為L(zhǎng)ow、Medium和High 3種狀態(tài),迭代階段κ以3個(gè)隸屬度函數(shù)分為Early、Medium和Late 3種狀態(tài)。為了對(duì)領(lǐng)導(dǎo)者占比因子進(jìn)行精確輸出,如圖2(c)所示,將其以5個(gè)隸屬度函數(shù)分為Very_Small、Small、Medium、Big和Very_Big 5個(gè)階段。

為了實(shí)現(xiàn)模糊推理系統(tǒng)中對(duì)領(lǐng)導(dǎo)者占比因子的精確輸出,還需要設(shè)計(jì)合理的模糊規(guī)則。SSA算法迭代前期,領(lǐng)導(dǎo)者規(guī)?？梢云?以求更充分的全局搜索;而隨著迭代進(jìn)行,領(lǐng)導(dǎo)者規(guī)模應(yīng)逐步減小,使算法側(cè)重于精細(xì)開發(fā)。同時(shí),還應(yīng)考慮種群多樣性對(duì)領(lǐng)導(dǎo)者占比因子的影響。當(dāng)種群多樣性較差時(shí),表明此時(shí)個(gè)體趨向聚集,此時(shí)應(yīng)增加領(lǐng)導(dǎo)者占比提高算法的全局搜索能力;當(dāng)種群多樣性較好時(shí),則可適當(dāng)減小領(lǐng)導(dǎo)者占比。綜上,設(shè)計(jì)表1所示模糊推理系統(tǒng)的模糊規(guī)則。

表1 模糊規(guī)則

結(jié)合表1所示的模糊規(guī)則,經(jīng)過去模糊化即可得到模糊推理系統(tǒng)實(shí)現(xiàn)的輸出領(lǐng)導(dǎo)者占比因子,如圖2(d)所示?？梢?在不同種群多樣性和算法迭代階段狀態(tài)下,領(lǐng)導(dǎo)者占比因子會(huì)進(jìn)行自適應(yīng)動(dòng)態(tài)調(diào)整,使得算法在迭代前后期以不同能力的搜索和開發(fā)性能進(jìn)行目標(biāo)搜索。

2.2 多項(xiàng)式變異擾動(dòng)

SSA算法的迭代后期,種群個(gè)體會(huì)逐步趨近于當(dāng)前迭代中搜索到的最優(yōu)解。若該最優(yōu)解為局部最優(yōu)解,勢(shì)必導(dǎo)致算法得到局部最優(yōu)。為此,MSISSA算法引入一種多項(xiàng)式變異算子作用于跟隨者種群,使SSA算法具備一定的局部隨機(jī)搜索能力,在迭代后期加速算法向最優(yōu)解收斂的同時(shí),使種群維持一定多樣性,避免生成局部最優(yōu)解。多項(xiàng)式變異表達(dá)式為:

xk+1=xk+δ·(uk-lk)

(6)

(7)

式中:lk、uk分別為搜索區(qū)間的下限值和上限值;xk、xk+1分別為原個(gè)體位置和變異后個(gè)體位置;δ為多項(xiàng)式變異算子;μ為隨機(jī)量μ∈[0,1];ηm為分布指數(shù);且:

(8)

結(jié)合多項(xiàng)式變異的擾動(dòng)方式具體為:算法迭代開始后,從算法第11次迭代開始,若種群連續(xù)10代搜索的最優(yōu)解適應(yīng)度均未發(fā)生更新,此時(shí)可視為算法得到局部最優(yōu)解而無(wú)法跳離,需要利用多項(xiàng)式變異算子對(duì)跟隨者種群個(gè)體進(jìn)行擾動(dòng),增加種群多樣性,拓展種群的搜索范圍,從而增加算法跳離局部最優(yōu)解的概率。個(gè)體變異公式為

xi,j(t+1)=xi,j(t)+δ·(xub-x1b)

(9)

式中:xi,j(t)、xi,j(t+1)分別原位置和更新位置;xlb、xub分別為搜索區(qū)間的下限值和上限值。

2.3 拓?fù)鋵?duì)立學(xué)習(xí)策略

拓?fù)鋵?duì)立學(xué)習(xí)TOBL[15]是一種基于對(duì)立學(xué)習(xí)OBL的增強(qiáng)優(yōu)化策略,能夠顯著提升算法的搜索能力。對(duì)立學(xué)習(xí)僅生成一個(gè)與原始個(gè)體完全反向的對(duì)立個(gè)體,而拓?fù)鋵?duì)立學(xué)習(xí)可生成2D個(gè)備選個(gè)體。

令在D維空間內(nèi)一個(gè)點(diǎn)xi=(xi,1,xi,2,...,xi,j,…,xi,D),其拓?fù)鋵?duì)立點(diǎn)Ti=(Ti,1,Ti,2,…,Ti,j,…,Ti,D),定義為

(10)

式中:xbest,j為當(dāng)前迭代最優(yōu)解的j維度位置;oi,j為對(duì)立點(diǎn)i的j維度位置,定義為

oi,j=lbj+ubj-xi,j,j=1,2,…,D

(11)

式中l(wèi)bj、ubj分別為搜索空間的下限值和上限值。

為了提高SSA算法的尋優(yōu)能力,MSISSA算法引入拓?fù)鋵?duì)立學(xué)習(xí)機(jī)制,在樽海鞘種群更新位置之后,先利用式(11)生成每個(gè)個(gè)體的對(duì)立點(diǎn),再比較最優(yōu)解與該對(duì)立點(diǎn)以及原個(gè)體間的曼哈頓距離。若對(duì)立點(diǎn)位置與最優(yōu)解距離最小,則表明該對(duì)立點(diǎn)為個(gè)體的拓?fù)鋵?duì)立點(diǎn)。如圖3所示為三維空間內(nèi)一個(gè)種群個(gè)體潛在的拓?fù)鋵?duì)立點(diǎn)位置。

圖3 三維空間拓?fù)鋵?duì)立點(diǎn)分布

計(jì)算個(gè)體的拓?fù)鋵?duì)立點(diǎn)是為了得到適應(yīng)度最優(yōu)的個(gè)體,以使得種群對(duì)搜索空間進(jìn)行更充分的全局搜索,進(jìn)而提高算法的尋優(yōu)效率。計(jì)算個(gè)體的拓?fù)鋵?duì)立點(diǎn)后,對(duì)其適應(yīng)度進(jìn)行評(píng)估,若其適應(yīng)度優(yōu)于原個(gè)體位置,則進(jìn)行交換。擇優(yōu)交換方式為

(12)

式中:f(xi(t))、f(Ti(t))分別為原個(gè)體及其拓?fù)鋵?duì)立點(diǎn)的適應(yīng)度值;xi′(t+1)為擇優(yōu)交換后的解。

圖4為MSISSA算法的執(zhí)行流程。

圖4 MSISSA算法流程

3 基于障礙物環(huán)境的WSN節(jié)點(diǎn)覆蓋優(yōu)化

3.1 WSN節(jié)點(diǎn)覆蓋模型描述

在二維平面區(qū)域S=L×W內(nèi)部署若干WSN節(jié)點(diǎn),區(qū)域內(nèi)存在若干個(gè)障礙物,且整個(gè)待監(jiān)測(cè)區(qū)域被離散化為L(zhǎng)×W個(gè)像素點(diǎn)。令WSN節(jié)點(diǎn)集合N={n1,n2,…,nk},k為WSN節(jié)點(diǎn)數(shù)量,障礙物集合O={o1,i,o2,i,…,oj,i},j為障礙物數(shù)量,i為障礙物類型。令(xk,yk)為WSN節(jié)點(diǎn)nk的坐標(biāo),其感知半徑為r,通信半徑為R,且R=2r。選用概率感知模型決定區(qū)域內(nèi)某個(gè)像素點(diǎn)是否能被WSN節(jié)點(diǎn)所覆蓋。令待檢測(cè)點(diǎn)g的坐標(biāo)為(xg,yg),則WSN節(jié)點(diǎn)nk對(duì)g點(diǎn)的感知概率為

(13)

式中:d(nk,g)為WSN節(jié)點(diǎn)nk與目標(biāo)點(diǎn)g間的歐氏距離;re為WSN節(jié)點(diǎn)在障礙物環(huán)境下感知能力的不確定性度量值,0

圖5為WSN節(jié)點(diǎn)的感知模型,區(qū)域g1內(nèi)的目標(biāo)點(diǎn)被WSN節(jié)點(diǎn)nk感知的概率為100%,區(qū)域g3以外目標(biāo)點(diǎn)確定無(wú)法被nk所感知,區(qū)域g2內(nèi)的目標(biāo)點(diǎn)的感知概率則由感知因子λ、β決定,感知概率為0～100%。

圖5 感知模型

d(nk,g)以歐氏距離方式定義為

(14)

由于一個(gè)目標(biāo)點(diǎn)可以同時(shí)被多個(gè)WSN節(jié)點(diǎn)所覆蓋,可將整個(gè)WSN的聯(lián)合感知概率定義為

(15)

式中p(nk,g)為傳感節(jié)點(diǎn)nk對(duì)點(diǎn)g的感知概率。

則整個(gè)區(qū)域的覆蓋率為

(16)

式中L、W表示待監(jiān)測(cè)區(qū)域的長(zhǎng)度和寬度。

3.2 避障設(shè)計(jì)

復(fù)雜環(huán)境中一般在待監(jiān)測(cè)區(qū)域內(nèi)存在障礙物的限制,若WSN節(jié)點(diǎn)部署位置落入障礙物區(qū)域,則需要對(duì)節(jié)點(diǎn)進(jìn)行移動(dòng)重部署。WSN節(jié)點(diǎn)部署過程中需要針對(duì)目標(biāo)函數(shù)設(shè)計(jì)避開障礙物的覆蓋優(yōu)化策略。為了避免選擇不合適的約束條件而導(dǎo)致WSN節(jié)點(diǎn)部署中出現(xiàn)聚集性,從而導(dǎo)致區(qū)域覆蓋率降低,本文設(shè)計(jì)一種基于人工勢(shì)場(chǎng)虛擬斥力場(chǎng)策略對(duì)WSN節(jié)點(diǎn)位置進(jìn)行重新部署。建立如圖6所示W(wǎng)SN節(jié)點(diǎn)部署的障礙物模型,實(shí)際障礙物包含于圓形中,障礙物大小決定圓半徑ro的大小,且圓的范圍也是斥力場(chǎng)存在的區(qū)域。WSN節(jié)點(diǎn)與障礙物間的距離簡(jiǎn)化為與圓心oi的距離,若節(jié)點(diǎn)落入圓內(nèi),便受到障礙物的斥力作用,并沿著斥力方向移動(dòng)相應(yīng)斥力大小的距離,從而達(dá)到讓W(xué)SN節(jié)點(diǎn)避開障礙物的目的。來(lái)自障礙物的斥力大小定義為

圖6 障礙物內(nèi)WSN節(jié)點(diǎn)的移動(dòng)方向

(17)

式中:Fno為WSN節(jié)點(diǎn)與障礙物間的斥力大小,斥力用于控制WSN節(jié)點(diǎn)避障的移動(dòng)距離;d(ni,oicenter)為WSN節(jié)點(diǎn)與障礙物的間距;ro為障礙物斥力的有效作用范圍,即圓半徑。

圖6(b)中,當(dāng)障礙物周圍存在部署區(qū)域邊界A時(shí),為了避免WSN節(jié)點(diǎn)移動(dòng)超過邊界,向邊界方向移動(dòng)的節(jié)點(diǎn)會(huì)按斥力反方向移動(dòng),斥力大小定義為

Fno′=2ro-Fno

(18)

3.3 基于MSISSA算法的WSN節(jié)點(diǎn)覆蓋優(yōu)化

MSISSA算法的優(yōu)化目標(biāo)是在特定的障礙物環(huán)境下待監(jiān)測(cè)平面區(qū)域S=L×W內(nèi),求解WSN節(jié)點(diǎn)的最優(yōu)部署坐標(biāo),使式(16)的區(qū)域覆蓋率Rcov達(dá)到最大。將WSN節(jié)點(diǎn)覆蓋優(yōu)化問題定義為區(qū)域覆蓋率Rcov為目標(biāo)函數(shù)的高維矢量尋優(yōu)問題,將WSN節(jié)點(diǎn)位置的尋優(yōu)過程抽象為MSISSA算法中樽海鞘群的搜索行為,算法最優(yōu)解即為WSN節(jié)點(diǎn)的部署坐標(biāo)。將MSISSA算法中樽海鞘個(gè)體位置表示為WSN節(jié)點(diǎn)的一個(gè)覆蓋分布,個(gè)體位置維度為WSN節(jié)點(diǎn)數(shù)的2倍?；贛SISSA算法的WSN節(jié)點(diǎn)覆蓋優(yōu)化具體步驟為:

輸入:監(jiān)測(cè)區(qū)域大小S=L×M、WSN節(jié)點(diǎn)數(shù)k、節(jié)點(diǎn)感知半徑r、通信半徑R、障礙物數(shù)量與類型,MSISSA算法參數(shù):種群規(guī)模N、迭代最大次數(shù)Tmax、個(gè)體搜索區(qū)間[lb,ub](對(duì)應(yīng)監(jiān)測(cè)區(qū)域大小);

輸出:WSN節(jié)點(diǎn)部署位置及最優(yōu)覆蓋率Rcov。

步驟1:設(shè)置監(jiān)測(cè)區(qū)域S及障礙物數(shù)量、類型及位置,初始化MSISSA算法的參數(shù);

步驟2:根據(jù)式(16)計(jì)算種群個(gè)體適應(yīng)度,確定最優(yōu)解;

步驟3:初始化算法迭代次數(shù)t=1;

步驟4:利用式(4)、式(5)分別計(jì)算模糊系統(tǒng)的2個(gè)輸入變量:種群多樣性diversity和迭代階段iter,調(diào)用模糊邏輯計(jì)算樽海鞘領(lǐng)導(dǎo)者種群的占比因子;

步驟5:利用式(1)更新領(lǐng)導(dǎo)者位置;

步驟6:利用式(3)更新跟隨者位置,并利用式(9)進(jìn)行跟隨者個(gè)體變異;

步驟7:利用式(10)、式(11)計(jì)算領(lǐng)導(dǎo)者的拓?fù)鋵?duì)立學(xué)習(xí)位置,再根據(jù)式(12)擇優(yōu)交換;

步驟8:更新種群全局最優(yōu)解;

步驟9:更新算法迭代次數(shù)t=t+1;

步驟10:判斷算法是否迭代終止。若未終止,返回步驟4執(zhí)行;否則,算法終止,輸出全局最優(yōu)解,得到WSN節(jié)點(diǎn)部署坐標(biāo)并計(jì)算最優(yōu)覆蓋率Rcov。

4 實(shí)驗(yàn)分析

設(shè)置WSN節(jié)點(diǎn)的部署區(qū)域大小為S=100 m×100 m,待部署WSN節(jié)點(diǎn)數(shù)為28個(gè),節(jié)點(diǎn)感知半徑為12 m,分布障礙物為5個(gè),障礙物類型設(shè)置為菱形和三角形,包括4個(gè)三角形障礙物和1個(gè)菱形障礙物,三角形障礙物分布于矩形區(qū)域邊角處,菱形障礙物處于區(qū)域中央,其具體分布如圖7。設(shè)置MSISSA算法的種群規(guī)模為20,最大迭代次數(shù)為500。引入標(biāo)準(zhǔn)樽海鞘群算法SSA、改進(jìn)灰狼優(yōu)化算法IGWO[7]以及改進(jìn)鯨魚優(yōu)化算法IWOA[9]進(jìn)行性能的對(duì)比分析。

圖7 障礙物分布區(qū)域

圖8為4種算法在障礙物環(huán)境下的WSN節(jié)點(diǎn)部署結(jié)果。圓內(nèi)實(shí)心點(diǎn)為WSN節(jié)點(diǎn)部署的坐標(biāo)位置,圓形區(qū)域?yàn)橄鄳?yīng)WSN節(jié)點(diǎn)的覆蓋區(qū)域。可以看到,SSA算法的節(jié)點(diǎn)覆蓋存在明顯的覆蓋盲區(qū)和覆蓋冗余,WSN節(jié)點(diǎn)部署均勻性較差,算法搜索精度不足。IGWO和IWOA算法經(jīng)過搜索機(jī)制的優(yōu)化后,比SSA算法的節(jié)點(diǎn)覆蓋更加均勻,但依然存在較多的覆蓋盲區(qū)。MSISSA算法相比3種對(duì)比算法,WSN節(jié)點(diǎn)位置分布更加均勻,覆蓋冗余更少,證明綜合改進(jìn)機(jī)制有效可行。

(a)SSA

圖9為算法覆蓋率收斂曲線?？梢钥闯?SSA較快進(jìn)入收斂狀態(tài),但得到的是局部最優(yōu)解,覆蓋率較低,且至算法迭代結(jié)束也無(wú)法跳離局部最優(yōu)處。IGWO和IWOA迭代前期覆蓋率均上升較快,然后進(jìn)入局部最優(yōu)解處,但在迭代若干次后,在算法迭代中后期均有跳離局部最優(yōu)解的特征,表明針對(duì)算法的改進(jìn)策略能夠一定程度提高尋優(yōu)精度,但覆蓋率還有提升空間。MSISSA得到了最高的覆蓋率,且迭代初期已經(jīng)獲得更好的種群分布,算法通過拓?fù)鋵?duì)立學(xué)習(xí)機(jī)制擇優(yōu)保留優(yōu)質(zhì)個(gè)體,充分挖掘了區(qū)域內(nèi)的精英位置信息,增加了每次迭代搜索得到更高覆蓋率的可能。此外,MSISSA的收斂曲線始終處于更加平衡的狀態(tài),這表明引入模糊邏輯系統(tǒng)對(duì)領(lǐng)導(dǎo)者樽海鞘個(gè)體占比的自適應(yīng)調(diào)整能夠保證優(yōu)勢(shì)群體領(lǐng)導(dǎo)者的搜索與開發(fā)水平的均衡。同時(shí),MSISSA迭代的中后期雖有一段時(shí)間的局部收斂和搜索停滯,但最后還是能夠跳離局部最優(yōu)解,得到更高的覆蓋率,這表明多項(xiàng)式變異機(jī)制下的局部隨機(jī)搜索能力,能夠較好避免生成局部最優(yōu)。

圖9 覆蓋率收斂曲線

圖10是WSN節(jié)點(diǎn)數(shù)變化對(duì)覆蓋率的影響曲線。設(shè)置WSN節(jié)點(diǎn)范圍為[16,32],遞增步長(zhǎng)為4。可以看出,隨著WSN節(jié)點(diǎn)數(shù)的增加,覆蓋率穩(wěn)步上升,這是由于更多的節(jié)點(diǎn)部署可以增加降低覆蓋盲區(qū)的概率。但覆蓋率遞增速率上,MSISSA算法在增加WSN節(jié)點(diǎn)數(shù)后覆蓋率明顯增長(zhǎng)更快。并且在相同WSN節(jié)點(diǎn)下,算法覆蓋率最高,這表明MSISSA算法具有更高的尋優(yōu)精度,能夠在障礙物復(fù)雜環(huán)境中實(shí)現(xiàn)對(duì)WSN節(jié)點(diǎn)的覆蓋優(yōu)化。

圖10 不同節(jié)點(diǎn)數(shù)下的覆蓋率

圖11選擇展示SSA和MSISSA算法的WSN節(jié)點(diǎn)覆蓋下,利用Prim算法得到的節(jié)點(diǎn)組網(wǎng)結(jié)果。傳感器網(wǎng)絡(luò)中需要重點(diǎn)關(guān)注節(jié)點(diǎn)間的通信距離和數(shù)據(jù)匯聚,可以看到,MSISSA算法的組網(wǎng)結(jié)果中,WSN節(jié)點(diǎn)的通信距離分布比較均勻,這有利于節(jié)省WSN節(jié)點(diǎn)的數(shù)據(jù)傳輸能耗。此外,從組網(wǎng)結(jié)果看,承擔(dān)數(shù)據(jù)聚合的匯聚節(jié)點(diǎn)沒有大量集中在區(qū)域的中間位置,而是更多地分布在靠近區(qū)域邊界的區(qū)域,這樣有利于避免數(shù)據(jù)匯聚的長(zhǎng)距離傳送,降低節(jié)點(diǎn)的長(zhǎng)距離傳輸能耗。WSN節(jié)點(diǎn)更均勻的分布可以有效增強(qiáng)通信網(wǎng)絡(luò)的可靠性,降低節(jié)點(diǎn)數(shù)據(jù)傳輸耗能,最終延長(zhǎng)WSN的有效工作時(shí)間。SSA算法中WSN節(jié)點(diǎn)覆蓋的均勻性明顯差于MSISSA算法,導(dǎo)致部分通信距離較長(zhǎng),而部分節(jié)點(diǎn)又過于密集,不利于節(jié)點(diǎn)間數(shù)據(jù)傳輸能耗節(jié)省。

WSN網(wǎng)絡(luò)的目標(biāo)是通過部署的傳感節(jié)點(diǎn)收集數(shù)據(jù),并自組網(wǎng)絡(luò)進(jìn)行信息傳輸。傳感器節(jié)點(diǎn)一般以電池供電,節(jié)點(diǎn)位置則直接影響著數(shù)據(jù)的傳輸距離。結(jié)合傳感器節(jié)點(diǎn)的能耗模型,本部分觀測(cè)4種算法進(jìn)行節(jié)點(diǎn)部署后的網(wǎng)絡(luò)生存時(shí)間。在自組網(wǎng)絡(luò)中運(yùn)行分簇協(xié)議LEACH,圖12是協(xié)議運(yùn)行100輪后傳感器節(jié)點(diǎn)的存活率。出現(xiàn)第一個(gè)節(jié)點(diǎn)能量耗盡的順序是SSA、IGWO、IWOA和MSISSA。依據(jù)傳感器節(jié)點(diǎn)的能耗模型可知,節(jié)點(diǎn)能耗主要集中在數(shù)據(jù)傳輸能耗,因此,當(dāng)節(jié)點(diǎn)覆蓋均勻性差,部分區(qū)域冗余節(jié)點(diǎn)多,會(huì)導(dǎo)致數(shù)據(jù)重復(fù)傳輸多,快速消耗節(jié)點(diǎn)能源。同時(shí),覆蓋空洞區(qū)域則需要多次遠(yuǎn)距離中繼傳輸,同樣會(huì)加速節(jié)點(diǎn)能源消耗。MSISSA的節(jié)點(diǎn)優(yōu)化覆蓋結(jié)果避免了過多的遠(yuǎn)距離傳輸和近距離冗余傳輸,有效節(jié)省了傳感節(jié)點(diǎn)的能耗,延長(zhǎng)WSN網(wǎng)絡(luò)的生存時(shí)間。

圖12 傳感器網(wǎng)絡(luò)生存時(shí)間

5 結(jié)束語(yǔ)

WSN節(jié)點(diǎn)部署容易造成覆蓋冗余和覆蓋空白的不足,本文提出了一種障礙物環(huán)境中基于多策略融合改進(jìn)樽海鞘群算法的WSN節(jié)點(diǎn)覆蓋優(yōu)化策略。為了提高樽海鞘群算法的尋優(yōu)性能,引入模糊邏輯種群角色調(diào)整機(jī)制、多項(xiàng)式變異擾動(dòng)機(jī)制及拓?fù)鋵?duì)立學(xué)習(xí)機(jī)制對(duì)算法全局搜索與局部開發(fā)間的平衡、局部隨機(jī)搜索能力及精英位置信息挖掘進(jìn)行了改進(jìn),然后利用改進(jìn)樽海鞘群算法求解障礙物環(huán)境WSN節(jié)點(diǎn)覆蓋優(yōu)化問題,以網(wǎng)絡(luò)覆蓋率最大為目標(biāo),迭代搜索節(jié)點(diǎn)部署的最優(yōu)位置。實(shí)驗(yàn)結(jié)果表明改進(jìn)算法能夠有效提高節(jié)點(diǎn)覆蓋率,減少覆蓋冗余,優(yōu)化節(jié)點(diǎn)均勻分布。