李 斐，朱曉磊

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

0 引言

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

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

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

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

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

1.1 樽海鞘算法

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

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

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

1.2 Halton序列初始化

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

1.3 新的非線性收斂因子

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

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

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

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

1.4 柯西變異

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

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

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

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

1.5 算法流程

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

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

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

2.1 改進(jìn)策略的有效性

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

圖3 SSA在不同改進(jìn)策略下的迭代曲線對比

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

2.2 WSN覆蓋優(yōu)化

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

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

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

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

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

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

3 結(jié)束語

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