多策略增強樽海鞘算法下的WSN覆蓋優化＊

李 斐，朱曉磊

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

0 引言

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

如何部署傳感器節點實現對目標區域的網絡覆蓋范圍最大，是構建無線傳感器網絡的基本優化問題。對于一片二維區域，為保證覆蓋范圍，經常采用隨機拋灑傳感器的部署方法，大規模的隨機部署可能會產生覆蓋盲區或高密度重疊覆蓋區，盲區不能滿足覆蓋要求，而重疊區不僅浪費大量資源，并且過多的冗余數據會產生干擾或堵塞信道。采用確定性部署方式則可以避免以上問題。

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

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

1 多策略改進SSA下的WSN覆蓋優化

1.1 樽海鞘算法

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

建立優化算法的數學模型。假設可行域內種群規模為N，解空間的維度為D，領導者的位置更新表示為：

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

1.2 Halton序列初始化

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

1.3 新的非線性收斂因子

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

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

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

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

1.4 柯西變異

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

其中，cl是第l次迭代產生的柯西變異個體，F為當前最優解，Cauchy表示與個體位置向量維度相同的標準柯西分布產生的點。在本文中，優化對象是二維空間中的坐標，因此，每個個體的維度是2，Cauchy可以由以下公式獲得：

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

比較變異個體與當前最優解的適應度函數值，更新最優解。

1.5 算法流程

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

圖2 ESSA算法下的WSN覆蓋優化流程圖

2 實驗結果

2.1 改進策略的有效性

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

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

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

2.2 WSN覆蓋優化

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

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

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

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

圖5 五種算法的WSN的節點部署結果

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

3 結束語

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