多策略增強樽海鞘算法下的WSN覆蓋優(yōu)化＊

李 斐，朱曉磊

(1.山東建筑大學(xué)信息與電氣工程學(xué)院，山東 濟南 250101；2.山東省智能建筑技術(shù)重點實驗室；3.積成電子股份有限公司)

0 引言

無線傳感器網(wǎng)絡(luò)WSN 是一種節(jié)點密集的分布式網(wǎng)絡(luò)，其節(jié)點是具有一定計算、處理和通信能力的傳感器。WSN 通過對信息的傳輸、處理、存儲、顯示和控制來實現(xiàn)智能感知，因具有強大的信息探測能力和功耗低、成本低、自組織的特點，在智慧城市、智慧醫(yī)療、智慧環(huán)保、智慧農(nóng)業(yè)等諸多領(lǐng)域有著廣泛應(yīng)用[1]。

如何部署傳感器節(jié)點實現(xiàn)對目標(biāo)區(qū)域的網(wǎng)絡(luò)覆蓋范圍最大，是構(gòu)建無線傳感器網(wǎng)絡(luò)的基本優(yōu)化問題。對于一片二維區(qū)域，為保證覆蓋范圍，經(jīng)常采用隨機拋灑傳感器的部署方法，大規(guī)模的隨機部署可能會產(chǎn)生覆蓋盲區(qū)或高密度重疊覆蓋區(qū)，盲區(qū)不能滿足覆蓋要求，而重疊區(qū)不僅浪費大量資源，并且過多的冗余數(shù)據(jù)會產(chǎn)生干擾或堵塞信道。采用確定性部署方式則可以避免以上問題。

近年來，得益于智能優(yōu)化算法的迅速發(fā)展，WSN覆蓋優(yōu)化問題出現(xiàn)了許多良好的解決方案。宋等人[2]提出了基于改進鯨魚優(yōu)化算法，采用量子位Bloch 球面坐標(biāo)編碼初始化種群，采用萊維飛行策略跳出局部極值，算法收斂較快，覆蓋方案可有效降低節(jié)點的冗余。胡等人[3]提出了改進灰狼優(yōu)化算法，在覆蓋優(yōu)化、覆蓋率和收斂速度等方面對于原始灰狼算法均有提升。

樽海鞘算法（salp swarm algorithm，SSA）是一種受深海微生物——樽海鞘的捕食行為啟發(fā)的優(yōu)化算法[4]。該算法實現(xiàn)簡單，收斂速度較快，在解決單目標(biāo)的約束優(yōu)化問題上有較好的魯棒性和收斂精度，已經(jīng)成功應(yīng)用于參數(shù)優(yōu)化、工程調(diào)度等問題上。為實現(xiàn)高覆蓋率的無線傳感器網(wǎng)絡(luò)的節(jié)點部署，本文提出一種多策略增強的樽海鞘算法（ESSA）。使用Halton 序列代替隨機序列，生成個體的初始化位置，避免隨機點之間有間隙過大和重疊。采用新的非線性收斂因子，平衡算法全局尋優(yōu)和局部探索能力，加速收斂。引入柯西變異，通過擾動增加個體的多樣性，促使個體快速跳出局部最優(yōu)點。實驗表明，ESSA 可以實現(xiàn)WSN快速的高覆蓋率的節(jié)點部署。

1 多策略改進SSA下的WSN覆蓋優(yōu)化

1.1 樽海鞘算法

樽海鞘是一種類似水母的群居海洋生物，以樽海鞘鏈的運動形式進行覓食。樽海鞘算法便是模擬它們在海洋中游動和覓食過程提出的優(yōu)化方法。為了建立樽海鞘群運動覓食的軌跡模型,將種群分為領(lǐng)導(dǎo)者和追隨者兩類。領(lǐng)導(dǎo)者是在樽海鞘鏈頂端的個體，朝著食物移動，并且指導(dǎo)著緊隨其后的個體。其他樽海鞘為追隨者，按照嚴格的等級制度移動，只受前一個樽海鞘影響。這樣的運動模式使樽海鞘鏈有很強的全局探索和局部開發(fā)能力。

建立優(yōu)化算法的數(shù)學(xué)模型。假設(shè)可行域內(nèi)種群規(guī)模為N，解空間的維度為D，領(lǐng)導(dǎo)者的位置更新表示為：

其中，l是當(dāng)前迭代次數(shù)，L是迭代次數(shù)上限。由式⑵可知收斂因子是一個從2 到0 的遞減函數(shù)。其他追隨者的更新公式如下：

1.2 Halton序列初始化

種群初始化的位置影響種群的多樣性，隨機初始化位置往往是分布不均勻的偽隨機序列，導(dǎo)致初始的傳感器節(jié)點之間有間隙過大和重疊的可能。雖然迭代初期最優(yōu)解未知，但若搜索的起始位置更加均勻的分布在整個解空間，則會加快尋優(yōu)的進程，為此，本文采用Halton序列初始化樽海鞘群體的位置。Halton序列是一種隨機序列[5]，被用來生成均勻分布的隨機數(shù)，原理是選取一個質(zhì)數(shù)作為基數(shù)，然后在[0,1]內(nèi)不斷地切分，從而形成一些不重復(fù)并且均勻的點，本文采用Halton 序列生成傳感器節(jié)點的初始坐標(biāo)，需乘以區(qū)域邊長以將其拉伸到可行域中。

1.3 新的非線性收斂因子

原始SSA 算法的非線性收斂因子如公式⑶所示，為了進一步提供算法收斂性，本文提出一種新的非線性收斂因子，如公式⑷。

對比二者的變換曲線，如圖1所示。

圖1 新舊非線性收斂因子幅值對比

由圖1可知，新的收斂因子取值范圍更窄，向橫軸靠攏的速度更快，這會加快前期算法的收斂速度，迭代后期兩條曲線幾乎重合，此時算法的收斂性相當(dāng)。新非線性收斂因子的對性能的提升見實驗3.1。

1.4 柯西變異

按照一定概率對個體的某位置進行變異，從而產(chǎn)生新個體，可有效增加種群的多樣性，避免迭代陷入局部極值，因此在SSA 迭代中引入個體的柯西變異機制。標(biāo)準(zhǔn)柯西分布比標(biāo)準(zhǔn)高斯分布更加矮寬，具有更大的拖尾[6]，領(lǐng)導(dǎo)者按照柯西分布隨機產(chǎn)生較大擾動，變異公式如公式⑸。

其中，cl是第l次迭代產(chǎn)生的柯西變異個體，F(xiàn)為當(dāng)前最優(yōu)解，Cauchy表示與個體位置向量維度相同的標(biāo)準(zhǔn)柯西分布產(chǎn)生的點。在本文中，優(yōu)化對象是二維空間中的坐標(biāo)，因此，每個個體的維度是2，Cauchy可以由以下公式獲得：

其中，rand是一個1× 2大小的[0,1]上的隨機數(shù)。

比較變異個體與當(dāng)前最優(yōu)解的適應(yīng)度函數(shù)值，更新最優(yōu)解。

1.5 算法流程

本文采用布爾感知模型[7]，即傳感器節(jié)點對位于距離R 范圍內(nèi)檢測區(qū)域節(jié)點的感知能力相同，因而傳感器節(jié)點的感知范圍是以傳感器節(jié)點為圓心、以R 為半徑的圓盤。若給定傳感器數(shù)目，節(jié)點部署的目標(biāo)函數(shù)為給定區(qū)域內(nèi)的覆蓋面積之和，優(yōu)化各個傳感器的坐標(biāo)，使覆蓋面積盡可能地大。ESSA 算法下的WSN覆蓋優(yōu)化流程如圖2所示。

圖2 ESSA算法下的WSN覆蓋優(yōu)化流程圖

2 實驗結(jié)果

2.1 改進策略的有效性

針對WSN 網(wǎng)絡(luò)節(jié)點部署的覆蓋問題，首先考查SSA的改進策略的有效性，進行消融實驗，即分別考查三種改進策略單獨使用時的迭代曲線。設(shè)目標(biāo)區(qū)域的大小為100×100，傳感器節(jié)點數(shù)為40，每個節(jié)點的通信半徑為10。優(yōu)化算法的種群大小為20，最大迭代次數(shù)為500。SSA 算法在各個改進策略下的迭代曲線如圖3所示。

圖3 SSA在不同改進策略下的迭代曲線對比

觀察圖3 可見，三種改進方式均可以提升原始SSA 算法的收斂性或精度。其中，新的非線性收斂因子可以明顯提高迭代中前期的收斂性和精度；Halton序列初始化會在迭代前期表現(xiàn)出非常明顯的精度優(yōu)勢，但卻趨于平坦，陷入局部極值的時間較長；Cauchy變異雖在迭代最初曲線較低，但勝在收斂性好，幾次迭代后曲線快速提高，并且迭代結(jié)束后達到最高的精度。表現(xiàn)最好的為本文提出的多策略ESSA，可以將三種改進策略優(yōu)勢互補，獲得起點高、收斂快、精度高的特點。

2.2 WSN覆蓋優(yōu)化

考查ESSA 在WSN 覆蓋優(yōu)化問題上的性能，采用SSA、灰狼算法（gray wolf optimization algorithm,GWO）、鯨魚算法（whale optimization algorithm,WOA）群智能方法進行對比。實驗設(shè)置同3.1 節(jié)。覆蓋率關(guān)于迭代次數(shù)的分布曲線如圖4所示。

圖4 四種群智能方法的迭代曲線對比圖

從迭代曲線可以看出GWO 算法的收斂性差，因此迭代結(jié)束時精度不高，覆蓋率僅為91.33%；WOA 迭代初始起點低，但是收斂速度快，然而算法陷入局部極值無法跳出，產(chǎn)生早熟，在100次迭代后曲線趨于平坦，導(dǎo)致最終覆蓋率最低，為87.66%。ESSA 收斂迅速，精度高，最終取得最高的覆蓋率95.64%。

考查ESSA 的節(jié)點部署結(jié)果，采用隨機拋灑和SSA、GWO、WOA 群智能方法進行對比，部署結(jié)果如圖5所示。

圖5 五種算法的WSN的節(jié)點部署結(jié)果

圖5 中每個星號表示傳感器的部署位置，以此為圓心的圓圈表示該傳感器的感知范圍，全部圓圈的覆蓋面積之并集即為總覆蓋面積，覆蓋率為總覆蓋面積除以方形區(qū)域面積。部署結(jié)果與迭代曲線所反映的趨勢一致。隨機拋灑部署方法的空白區(qū)最多，重疊也最為嚴重，為了保證覆蓋率，需要更多的傳感器，這帶來資源浪費和信號干擾問題。其他優(yōu)化方法也有一定的覆蓋重疊區(qū)域，導(dǎo)致覆蓋率降低。ESSA 方法的節(jié)點分布最為均勻，覆蓋面積最大，這一優(yōu)勢是由改進策略帶來的。

3 結(jié)束語

本文提出一種多策略增強的樽海鞘優(yōu)化算法，進行無線傳感器網(wǎng)絡(luò)的節(jié)點覆蓋優(yōu)化。在Halton序列初始化、新非線性收斂因子及柯西變異策略下，優(yōu)化算法的性能得以提高。與其他群智能方法的對比實驗看出，ESSA 是一種優(yōu)化過程起點高、收斂迅速、精度高、覆蓋率高的WSN節(jié)點部署方法。