徐光憲， 丁瑞峰

(遼寧工程技術(shù)大學(xué) 電子與信息工程學(xué)院，遼寧 葫蘆島 125105)

0 引 言

隨著5G通信技術(shù)和人工智能的快速發(fā)展，進(jìn)而推動(dòng)了移動(dòng)通信技術(shù)和移動(dòng)設(shè)備的更新?lián)Q代，這使得無(wú)線傳感器網(wǎng)絡(luò)(wireless sensor networks，WSNs)的應(yīng)用越來(lái)越廣泛[1]，在航空、環(huán)境 、農(nóng)業(yè)、醫(yī)療等領(lǐng)域取得顯著的成果。在WSNs中首要解決的問題就是覆蓋質(zhì)量，而傳統(tǒng)的隨機(jī)節(jié)點(diǎn)部署會(huì)造成節(jié)點(diǎn)密度大和覆蓋率低等問題，進(jìn)而影響網(wǎng)絡(luò)通信性能。因此，如何高效地部署傳感器節(jié)點(diǎn)成為一個(gè)重要的研究話題[2]。

近年來(lái)，群智能優(yōu)化算法在解決WSNs的覆蓋質(zhì)量問題上取得了顯著成果。文獻(xiàn)[3]提出使用螢火蟲算法的WSNs覆蓋最大化方法；于文杰等人[4]提出基于外推人工蜂群算法的節(jié)點(diǎn)部署優(yōu)化方法；胡小平等人[5]提出改進(jìn)灰狼優(yōu)化算法(improved gray wolf optimization algorithm,IGWOA)在WSNs節(jié)點(diǎn)部署中的應(yīng)用；張亮等人[6]提出基于模糊粒子群優(yōu)化算法的WSNs的節(jié)點(diǎn)部署優(yōu)化方法；宋婷婷等人[7]提出基于改進(jìn)鯨魚優(yōu)化算法(improved whale optimization algorithm,IWOA)的WSNs覆蓋優(yōu)化方法。上述各類研究方法中，雖然對(duì)WSNs節(jié)點(diǎn)部署取得了一定成果，但在實(shí)際應(yīng)用過程中，在要求高覆蓋率、高收斂性、高精度等方面仍有待提高。

本文為了使節(jié)點(diǎn)部署達(dá)到較高的覆蓋質(zhì)量，在麻雀搜索算法(sparrow search algorithm,SSA)[8]的基礎(chǔ)上，提出一種混合策略改進(jìn)的SSA(mixed-strategy SSA,MSSA)的覆蓋優(yōu)化方法。首先，利用反向?qū)W習(xí)策略，解決種群初始化問題；其次，利用鯨魚算法的隨機(jī)搜索策略改進(jìn)麻雀發(fā)現(xiàn)者的位置更新方式，提高種群的全局搜索能力，最后，利用螢火蟲算法對(duì)麻雀?jìng)€(gè)體進(jìn)行擾動(dòng)更新，使其具有跳出局部最優(yōu)的能力。

1 WSNs的覆蓋模型

假設(shè)WSNs監(jiān)測(cè)的目標(biāo)區(qū)域是經(jīng)過離散化的面積為L(zhǎng)×M的二維平面，在此二維平面部署具有一樣感知半徑R和通信半徑Rc的N個(gè)同構(gòu)傳感器,Z={z1,z2,…,zN}為所有傳感器節(jié)點(diǎn)的集合。WSNs中節(jié)點(diǎn)感知模型使用布爾模型[9]，假設(shè)某個(gè)傳感器節(jié)點(diǎn)zi的位置坐標(biāo)為(xi,yi)，被監(jiān)測(cè)點(diǎn)Tj的位置坐標(biāo)為(xj,yj)，則傳感器節(jié)點(diǎn)與被監(jiān)測(cè)點(diǎn)的歐氏距離為

(1)

用p(zi,Tj)表示傳感器節(jié)點(diǎn)zi對(duì)Tj是否感知，當(dāng)Tj的位置在以傳感器節(jié)點(diǎn)zi為圓心的圓內(nèi)時(shí)，則表示被感知記為1；否則記為0，數(shù)學(xué)表達(dá)式為

(2)

假設(shè)多只傳感器對(duì)同一個(gè)目標(biāo)點(diǎn)協(xié)同探測(cè)時(shí)，WSNs對(duì)目標(biāo)點(diǎn)的感知質(zhì)量為

(3)

群智能算法對(duì)求最小值問題有顯著的效果，因此,將求高覆蓋率問題轉(zhuǎn)換為求最小值問題，目標(biāo)函數(shù)表示為

(4)

2 SSA

SSA過程主要包括發(fā)現(xiàn)者模型和追隨者模型，同時(shí)還設(shè)置了一定比例的個(gè)體作為預(yù)警機(jī)制，其中,發(fā)現(xiàn)者和警戒者的比例各占整個(gè)種群的10 %～20 %。發(fā)現(xiàn)者在種群中起引領(lǐng)作用，為整個(gè)種群尋找覓食區(qū)域和提供飛行方向，而追隨者則是通過追隨發(fā)現(xiàn)者來(lái)獲取食物，警戒者負(fù)責(zé)食物區(qū)域周圍的警戒。在覓食過程中，三者位置會(huì)不斷更新，進(jìn)而獲取最優(yōu)食源，最優(yōu)食物的位置即為尋得的最優(yōu)解。

2.1 發(fā)現(xiàn)者的位置更新方式

(5)

2.2 追隨者的位置更新方式

(6)

式中Xp和Xworst分別為當(dāng)前發(fā)現(xiàn)者最優(yōu)和全局最差位置。A為每個(gè)元素隨機(jī)賦值為1或-1的矩陣,并且A+=AT(AAT)-1。n為種群個(gè)數(shù)，當(dāng)i>n/2時(shí)，這表明第i個(gè)追隨者適應(yīng)度函數(shù)值較低，即沒有獲得足夠的食物，此時(shí)追隨者變?yōu)榘l(fā)現(xiàn)者需要去其他區(qū)域?qū)ふ沂澄?。否則，向當(dāng)前發(fā)現(xiàn)者最優(yōu)位置Xp移動(dòng)。

2.3 警戒者的位置更新方式

(7)

式中Xbest為當(dāng)前全局最優(yōu)位置。β為隨機(jī)正態(tài)分布的步長(zhǎng)因子。K為種群的步長(zhǎng)控制系數(shù)，其中,K的區(qū)間為[1,1]。fi為麻雀的適應(yīng)度值，fg和fw分別為當(dāng)前全局最佳和最差適應(yīng)度值。ε為防止分母取零的最小常數(shù)。當(dāng)fi>fg時(shí)，表示作為警戒者的i只麻雀不在全局最優(yōu)位置，意識(shí)到危險(xiǎn)逃到Xbest的附近。當(dāng)fi=fg時(shí)，表示作為警戒者的i只麻雀在全局最優(yōu)位置，意識(shí)到危險(xiǎn)逃到自身附近。

3 MSSA

3.1 反向?qū)W習(xí)策略初始化種群

在種群初始化時(shí)，大部分智能優(yōu)化算法都是在搜索空間內(nèi)隨機(jī)生成初始種群,這種隨機(jī)生成初始種群個(gè)體的位置多樣性不足，影響最終的全局最優(yōu)值的輸出。因此,本文利用反向?qū)W習(xí)策略[10]初始化種群彌補(bǔ)不足，其策略如下:

圖1 反向?qū)W習(xí)策略前后種群位置

3.2 發(fā)現(xiàn)者位置更新策略的改進(jìn)

圖2 函數(shù)y和麻雀位置更新的變化趨勢(shì)

為了解決上述問題，利用鯨魚算法[11]中的隨機(jī)搜索策略進(jìn)行改進(jìn)，公式如下

(8)

式中Xrand為一個(gè)隨機(jī)的鯨魚位置，A=2ar1-a,C=2r2,a=2-2t/Tmax。其中,r1和r2為[0,1]均勻分布隨機(jī)數(shù)；a為從2到0線性遞減的收斂因子。A作為步長(zhǎng)系數(shù)是鯨魚算法尋優(yōu)過程的重要參數(shù)，主要取決于收斂因子a。

圖3 步長(zhǎng)A的更新方式

如圖3可知，改進(jìn)后麻雀?jìng)€(gè)體搜索方式可以從自身的正反兩個(gè)方向進(jìn)行位置更新，大大提高了前期麻雀算法的搜索空間，同時(shí)提高了后期種群的收斂速度，能夠使麻雀種群更快的收斂。所以,發(fā)現(xiàn)者的位置更新改進(jìn)為

(9)

3.3 追隨者位置更新策略的改進(jìn)

(10)

改進(jìn)后的模型在最優(yōu)解位置周圍隨機(jī)移動(dòng)，使得其局部搜索能力提高，最終會(huì)收斂于最優(yōu)解的位置。

3.4 螢火蟲擾動(dòng)策略

為了避免算法陷入局部最優(yōu)的問題，在麻雀每代個(gè)體位置更新后用螢火蟲算法[12]對(duì)麻雀?jìng)€(gè)體進(jìn)行位置擾動(dòng)更新，使其具有跳出局部最優(yōu)的能力。擾動(dòng)后的麻雀?jìng)€(gè)體與擾動(dòng)前的麻雀?jìng)€(gè)體進(jìn)行適應(yīng)度函數(shù)的對(duì)比，如果更優(yōu)則更新麻雀位置。螢火蟲擾動(dòng)位置更新模型為

(11)

式中xi為最優(yōu)麻雀的位置，xj為剩余所有麻雀的位置，β0為最大吸引度，γ為一般取1的光強(qiáng)吸收系數(shù)，ri,j為麻雀位置xi與xj之間的空間距離，α∈[0,1]為步長(zhǎng)因子，rand為[0,1]區(qū)間服從均勻分布的隨機(jī)數(shù)。原步長(zhǎng)因子是個(gè)常數(shù)變量，不能滿足算法前期廣泛搜索，后期精細(xì)搜索的要求，因此,將擾動(dòng)步長(zhǎng)因子α改進(jìn)，改進(jìn)后公式為α=2/πarccos(t/Tmax)，且如圖4所示。

圖4 非線性步長(zhǎng)因子

3.5 基于MSSA的覆蓋優(yōu)化過程

將麻雀覓食過程運(yùn)用到覆蓋優(yōu)化問題中節(jié)點(diǎn)位置尋優(yōu)過程中，麻雀位置的每代更新為節(jié)點(diǎn)的位置更新，利用目標(biāo)函數(shù)值的好壞激勵(lì)麻雀位置更新，使其取得最優(yōu)解。

Step1 輸入監(jiān)測(cè)區(qū)域、WSNs和MSSA的相關(guān)參數(shù)。

Step2 利用反向?qū)W習(xí)策略初始化種群。

Step3 根據(jù)式(4)計(jì)算種群適應(yīng)度值，對(duì)適應(yīng)度值進(jìn)行排序，找出位置最優(yōu)和最差的個(gè)體。

Step4 麻雀發(fā)現(xiàn)者、追隨者、警戒者分別根據(jù)式(9)、式(10)、式(7)進(jìn)行位置更新。

Step5 將所有麻雀與最優(yōu)位置麻雀利用螢火蟲擾動(dòng)公式(11)進(jìn)行位置更新。

Step6 重復(fù)Step3，判斷迭代循環(huán)次數(shù)是否滿足結(jié)束條件，若達(dá)到，算法執(zhí)行結(jié)束，輸出結(jié)果。否則，跳轉(zhuǎn)到步驟4繼續(xù)進(jìn)行。

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

4.1 實(shí)驗(yàn)環(huán)境

為了驗(yàn)證MSSA在WSNs覆蓋優(yōu)化問題中節(jié)點(diǎn)部署的實(shí)際情況，利用MATLAB環(huán)境進(jìn)行了仿真，將MSSA,SSA和文獻(xiàn)[5]中的IGWOA和文獻(xiàn)[7]中的IWOA的節(jié)點(diǎn)部署情況進(jìn)行對(duì)比。

4.2 實(shí)驗(yàn)結(jié)果

4.2.1 監(jiān)測(cè)區(qū)域?yàn)?0 m×20 m覆蓋優(yōu)化對(duì)比

實(shí)驗(yàn)參數(shù)設(shè)置為監(jiān)測(cè)區(qū)域?yàn)榈?0 m×20 m二維平面，種群個(gè)數(shù)為40，傳感器節(jié)點(diǎn)數(shù)為24，感知半徑為Rs=2.5 m，通信半徑為Rc=5 m，迭代次數(shù)為1 000次。表1為各算法平均覆蓋率優(yōu)化結(jié)果對(duì)比。圖5為覆蓋優(yōu)化迭代收斂曲線，圖6為各算法優(yōu)化后的WSNs的節(jié)點(diǎn)部署。

表1 平均覆蓋率優(yōu)化結(jié)果對(duì)比

由表1可知，MSSA與SSA、IGWOA和IWOA的優(yōu)化結(jié)果相比，覆蓋率分別提升了16.30 %、6.55 %和4.28 %。從圖5中可知，MSSA在迭代319次陷入局部最優(yōu)，經(jīng)過螢火蟲算法擾動(dòng)后，跳出局部最優(yōu)，在迭代493次達(dá)到全局最優(yōu)解，且所求覆蓋率優(yōu)于其他算法。從圖6中各算法優(yōu)化后的節(jié)點(diǎn)部署可知，SSA優(yōu)化后的節(jié)點(diǎn)部署中覆蓋盲區(qū)較大，IGWOA和IWOA優(yōu)化后的盲區(qū)相對(duì)較小，而MSSA優(yōu)化后的結(jié)果使傳感器節(jié)點(diǎn)分布更均勻。

圖5 覆蓋優(yōu)化迭代收斂曲線

圖6 各算法優(yōu)化后的節(jié)點(diǎn)部署

4.2.2 監(jiān)測(cè)區(qū)域?yàn)?00 m×100 m覆蓋優(yōu)化對(duì)比

實(shí)驗(yàn)參數(shù)設(shè)置為監(jiān)測(cè)區(qū)域100 m×100 m的二維平面，種群個(gè)數(shù)為40，傳器節(jié)點(diǎn)數(shù)為40，感知半徑Rs=10 m，通信半徑Rc=20 m，迭代次數(shù)為1 000次。表2為各算法平均覆蓋率優(yōu)化結(jié)果對(duì)比。圖7為覆蓋優(yōu)化迭代收斂曲線，圖8為各算法優(yōu)化后的WSNs節(jié)點(diǎn)部署。

圖7 覆蓋優(yōu)化迭代收斂曲線

圖8 各算法優(yōu)化后的節(jié)點(diǎn)部署

由表2可知，MSSA與SSA、IGWOA和IWOA的優(yōu)化結(jié)果相比，覆蓋率分別提升了7.44 %、2.62 %和3.93 %。由圖7可知，MSSA在收斂速度上不斷向最優(yōu)值靠近，在362代陷入局部最優(yōu)，通過螢火蟲擾動(dòng)跳出局部最優(yōu)后，在556代達(dá)到全局最優(yōu)。通過圖7和圖8可知，MSSA在求最優(yōu)解和節(jié)點(diǎn)部署的效果方面都要優(yōu)于其他算法。

表2 平均覆蓋率優(yōu)化結(jié)果對(duì)比

從上述在兩種不同監(jiān)測(cè)區(qū)域的實(shí)驗(yàn)結(jié)果表明，MSSA在優(yōu)化WSNs覆蓋問題上，能夠很好地解決節(jié)點(diǎn)冗余、覆蓋率低等問題，相比于其他算法具有一定的優(yōu)勢(shì)。

5 結(jié) 論

本文對(duì)于WSNs中隨機(jī)節(jié)點(diǎn)部署時(shí)容易造成WSNs覆蓋質(zhì)量率低的問題,在SSA的基礎(chǔ)上提出MSSA，對(duì)該問題進(jìn)行優(yōu)化。首先,利用反向?qū)W習(xí)策略初始化種群，增加種群的多樣性和遍歷性；其次,借鑒WOA中隨機(jī)搜索策略對(duì)SSA中發(fā)現(xiàn)者位置更新進(jìn)行改進(jìn)，提高算法的全局搜索能力;同時(shí),對(duì)追隨者位置更新中的收斂于零點(diǎn)的部分進(jìn)行優(yōu)化，提高算法局部搜索能力；最后，利用螢火蟲擾動(dòng)策略對(duì)最優(yōu)麻雀?jìng)€(gè)體進(jìn)行擾動(dòng)更新，使算法具有跳出局部最優(yōu)的能力。實(shí)驗(yàn)結(jié)果表明:MSSA相比于其他算法具有適應(yīng)性強(qiáng)和收斂性較為穩(wěn)定的特點(diǎn)，同時(shí)也使得區(qū)域覆蓋面積有了顯著的提高，減少了節(jié)點(diǎn)冗余度。