基于Halton序列WOA-GWO算法的WSN覆蓋研究

摘 要：為解決無線傳感器網絡（WSN）隨機部署時存在分布不均而導致覆蓋率低的問題，提出一種基于Halton序列且結合鯨魚優化算法與灰狼優化算法（WOA-GWO）的WSN覆蓋優化方法。首先，將WOA算法與GWO算法融合，WOA算法在迭代前期有著更快的收斂速度，可在前期使WSN部署快速趨于成熟，而GWO算法能夠實現局部尋優與全局尋優的平衡，將其用于算法迭代的中后期可保證WSN覆蓋優化的整體性能；其次，使用融合隨機因子的Halton序列方法對種群進行初始化，使傳感器節點在初始化時的分布更加均勻，提升初始化種群質量；最后，將基于WOA的WSN覆蓋優化、GWO的WSN覆蓋優化、基于Halton序列WOA-GWO的WSN覆蓋優化效果進行對比，驗證本文所提方法的有效性。

關鍵詞：無線傳感器網絡；覆蓋優化；鯨魚算法；灰狼算法；Halton序列；全局尋優

中圖分類號：TP393.0 文獻標識碼：A 文章編號：2095-1302（2024）02-00-05

0 引 言

無線傳感器網絡（Wireless Sensor Network， WSN）是一種由大量微型傳感器節點組成的網絡系統，能夠實現對環境中各種參數的實時監測和數據采集。WSN在環境監測、農業、醫療、交通等領域具有廣闊的應用前景。然而，在WSN中，傳感器節點分布不均勻會導致監測區域未被充分覆蓋，從而影響監測數據的準確性和可靠性。因此，WSN能否充分覆蓋成為WSN研究中的一個重要問題。WSN覆蓋優化是指在保證所有監測區域被覆蓋的情況下，盡可能減少傳感器節點的數量。目前，常用的解決WSN覆蓋問題的方法是優化算法，如粒子群算法[1]、蝴蝶優化算法[2]、麻雀搜索算法[3]等。然而，這些算法在優化效率、解決復雜問題等方面存在不足。一些研究表明，將新型的優化算法、改進的智能優化算法用于節點部署具有一定的價值及意義[4]。

鯨魚優化算法（Whale Optimization Algorithm， WOA）是由Mirjalili等人于2016年提出的元啟發式算法[5]，通過模擬隨機或最佳個體捕食獵物的狩獵行為進行尋優。灰狼優化算法（Grey Wolf Optimizer， GWO）是Mirjalili等人于2014年提出的元啟發式算法[6]，它通過模擬灰狼群體捕食行為，基于狼群群體協作機制來達到優化的目的。將兩種算法單獨用于WSN覆蓋優化問題上，可以起到一定的優化效果，但覆蓋率仍然較低。因此，在了解兩種算法在解決WSN覆蓋問題方面所呈現的優點與不足后，本文將兩種算法結合起來，然后將結合后的WOA-GWO算法應用于WSN覆蓋優化問題中，能夠有效提高WSN覆蓋率。

在本文所提出的算法中，首先將WOA與GWO算法結合；然后引入融合隨機因子的Halton序列方法對種群進行初始化。將該算法應用于WSN覆蓋優化問題中，實驗結果表明，與基于WOA的WSN覆蓋優化、GWO的WSN覆蓋優化相比，基于Halton序列WOA-GWO的WSN覆蓋優化效果更優，并且能用更少的迭代次數實現更高的覆蓋率。

1 節點覆蓋模型

假設無線傳感器監測區域長為L，寬為W，將其劃分成L×W個網格，網格中心點為監測點，監測節點的集合為M={m1， m2， m3， ...， mn}，節點mj的坐標為（xj， yj）；無線傳感器節點集合定義為S={s1， s2， s3， ...， sn}，集合中任意一個傳感器節點二維坐標表示為（xi， yi），N為傳感器個數，R為傳感器的感知半徑。在監測過程中，若是監測節點與任意一個傳感器節點距離不大于R，則認為該點被覆蓋。無線傳感器節點與監測節點之間的距離為：

（1）

監測節點mj能被感知的概率為：

（2）

所有傳感器對mj的聯合覆蓋率為：

（3）

式中：sall是測量范圍內的所有傳感器節點。傳感器節點對整個區域的監測范圍就是WSN的覆蓋程度，可計算出所有監測點的監測覆蓋率：

（4）

2 基本算法介紹

2.1 鯨魚優化算法

WOA是對座頭鯨的特殊搜索方法和圍捕機制進行模擬的算法，其中主要包括圍捕獵物、氣泡網捕食、搜索獵物三個重要階段。

（1）圍捕獵物

首先，在當前種群中選取最佳種群當做目前最優解，其他個體根據最優解的位置來更新自身位置，其位置更新公式如下：

（5）

（6）

式中：t表示當前迭代次數；X（t+1）表示更新后的位置；X*（t）是目前最優解的位置向量；A和C為系數向量，計算方式

如下：

（7）

（8）

式中：a在整個迭代過程中由2線性降到0；r1和r2是[0，1]中的隨機向量。

（2）氣泡網捕食

捕食機制分別是包圍捕食和氣泡網捕食。采用氣泡網捕食時，位置更新用對數螺旋方程表達：

（9）

（10）

式中：D*表示當前搜索個體與當前最優解的距離；b為螺旋形狀參數；l為[-1，1]間的隨機數。為了模擬鯨魚收縮包圍和螺旋更新機制，用如下公式表達：

（11）

式中：p為捕食機制概率，為[0，1]間的隨機數；參數A和收斂因子a隨著迭代次數增加逐漸減少，若|A|lt;1，則鯨魚包圍當前最優解。

（3）搜索獵物

隨機尋找獵物是除氣泡網捕食法之外的方法，當|A|≥1時，鯨魚會隨機搜索，其公式為：

（12）

（13）

式中：D為當前搜索個體與隨機個體的距離；Xrand（t）為當前隨機個體位置。

2.2 WOA算法流程

標準WOA算法流程如圖1所示。其計算流程具體如下：

（1）設置種群數量N、最大迭代次數T，初始化位置信息。

（2）計算當前種群適應度，并保留最優位置種群。

（3）計算參數a、p和系數向量A和C。判斷p是否小于0.5，是則轉入步驟（4），否則采用式（9）方式進行氣泡網捕食。

（4）判斷|A|是否小于1，是則按照式（6）包圍獵物，否則按照式（12）全局搜索獵物。

（5）位置更新結束，與先前種群個體適應度進行比較，保留較優解。

（6）判斷是否滿足終止條件，若滿足則終止算法，否則進入下一次迭代，返回步驟（3）。

2.3 灰狼優化算法

GWO是通過模擬自然界中灰狼的領導等級和狩獵機制來實現尋優的算法，其中主要包括搜索獵物、包圍獵物、攻擊獵物三個重要階段。

（1）包圍獵物

灰狼在狩獵過程中，利用以下公式來更新對獵物包圍的位置：

（14）

（15）

式中：X表示灰狼所處位置；t表示當前迭代次數；Xp表示獵物所在位置；D表示灰狼與獵物間的距離，計算方法為

式（15）；A和C是兩個協同系數向量，計算方式如下：

（16）

（17）

式中：和是[0，1]內取值的隨機向量；a為收斂因子。

（2）追捕獵物

在狩獵過程中，獵物位置Xp是未知的，因此在GWO中，認為α為最優灰狼，β為次優灰狼，δ為第三優灰狼，其余灰狼為ω。根據α、β、δ來指導ω的移動，從而實現全局最優，利用α、β、δ的位置、、來更新所有灰狼位置，公式如下：

（18）

（19）

（20）

（3）攻擊獵物

灰狼攻擊獵物行為被抽象成數學模型，如下式所示：

（21）

式中：a為收斂因子，它決定了A的變化，a值偏大時進行全局搜索，偏小時進行局部搜索；t為當前迭代次數；T為最大迭代次數。

2.4 GWO算法流程

標準GWO算法流程如圖2所示。

計算流程如下：

（1）初始化參數灰狼種群，并計算a、A、C等參數。

（2）計算當前種群灰狼適應度，保留適應度最好的前三匹狼α、β、δ。

（3）根據最優的三匹狼，更新其余ω狼的位置。

（4）更新參數a、A、C。

（5）計算全部灰狼的適應度，并更新α、β、δ狼的位置及適應度。

（6）判斷是否達到最大迭代次數，若達到則終止算法，否則返回步驟（3）。

3 基于Halton序列的WOA-GWO算法

本文提出的基于Halton序列的WOA-GWO算法主要由兩部分組成，首先將WOA與GWO算法融合，其次將Halton序列引入種群初始化中，下文將詳細介紹其具體內容。

3.1 WOA-GWO算法

將WOA應用于整體算法的迭代前期，可使尋找最優解的收斂速度更快，在短迭代周期內便達到了較為成熟的適應度值。將GWO應用在整體算法中后期迭代階段，既可保證GWO算法階段內前期的全局搜索，又能夠保證后期的局部尋優。

通過多組實驗進行對比，發現將整體迭代次數的前10%作為WOA尋優階段，其余90%作為GWO尋優階段能夠使尋優效果達到最佳。因此，分別將兩種算法應用于WOA-GWO整體迭代過程的前10%與后90%兩個階段。

3.2 Halton序列

Halton序列是由德國數學家John Halton提出的一種低差異序列[7]，即使在較高維度的數據中，也可生成均勻分布的點。對于WSN部署問題，使用Halton序列對傳感器節點進行初始化，能夠使數量較少的傳感器節點均勻分布在固定的空間范圍內，從而使其比隨機分布生成的覆蓋率更大，有效提升初始種群質量。圖3與圖4分別為二維空間內100個點的隨機分布與基于Halton序列分布圖像，通過比較可以發現，基于Halton序列點的分布在平面內更加均勻。因此，將Halton序列用于WSN節點位置的初始化能夠具有較好的分布效果。

由于Halton序列只能保證節點以單一的方式均勻分布，而不能保證對每個個體初始化且其具有差異性，因此，為使個體具有多樣性，引入小范圍的隨機因子對傳感器節點的初始位置進行處理。隨機因子r被定義為：

r=rand-0.5" " " " " " " " " " " " " " " " " " （22）

式中：rand為[0，1]間隨機數，-0.5是為了使r的值有正有負，便于計算。使用隨機因子r對基于Halton序列初始化的WSN節點位置進行隨機擾動，豐富了種群的多樣性。圖5為隨機擾動后的Halton序列生成的節點分布，可以看出圖中各點與圖4中各點具有明顯差異，但其分布仍比較均勻。

3.3 算法流程

基于Halton序列的WOA-GWO算法流程如圖6所示。

計算流程具體如下：

（1）初始化種群數量N、最大迭代次數T等參數，并設置當前迭代次數t=1。

（2）使用隨機Halton序列對種群位置進行初始化。

（3）判斷當前迭代次數是否小于總迭代次數的0.1倍，若小于則使用WOA算法更新種群位置，否則使用GWO算法更新種群位置。

（4）更新最優種群的位置。

（5）判斷是否達到最大迭代次數，若達到則終止算法，否則返回步驟（3）。

4 實驗仿真與分析

4.1 實驗環境設置

本文在MATLABR2022a平臺上對所提方法進行仿真，對其性能等進行測試。將基于Halton序列WOA-GWO的WSN覆蓋效果與基于WOA的WSN覆蓋和基于GWO的WSN覆蓋效果進行對比。為保證算法的公平性，在實驗過程中對算法設置相同參數，監測區域面積為50 m×50 m，節點數量為40個，種群規模為100個，感知半徑為5 m，迭代次數設置為500。

4.2 仿真結果與分析

按照上述參數進行仿真實驗，圖7～圖12為仿真結果。圖7為傳感器節點隨機初始化的覆蓋圖，圖8為基于隨機Halton序列的節點初始化覆蓋圖，圖9為基于WOA的WSN仿真覆蓋圖，圖10為基于GWO的WSN仿真覆蓋圖，圖11為基于Halton序列的WOA-GWO仿真覆蓋圖，圖12為三種算法在各迭代次數中最高覆蓋率的變化曲線。

從圖7和圖8的對比可以看出，相對于傳感器節點隨機部署，基于隨機Halton序列可使節點在初始化時使得傳感器節點分布更加均勻，具有更高的覆蓋率。通過圖9～圖11的對比可以看出，基于WOA的WSN覆蓋優化與基于GWO的WSN覆蓋優化都使傳感器節點的覆蓋率得到了一定提升，但仍存在一些覆蓋盲區，而基于Halton序列的WOA-GWO覆蓋優化后，傳感器節點分布更加均勻，覆蓋率也高于前兩種方法。

從圖12可以對比出三種算法在WSN覆蓋優化過程的覆蓋率變化曲線。基于WOA的WSN覆蓋優化在前30次迭代中，收斂速度明顯優于GWO算法，然后收斂速度趨于平緩，偶爾會提高覆蓋率，最終覆蓋率達到86.44%；基于GWO算法的WSN覆蓋優化在整個迭代過程中覆蓋率不斷提升，并且最終覆蓋率較高，達到了96.68%；基于Halton序列的WOA-GWO覆蓋優化綜合了兩種算法的優點，并且基于Halton序列對種群進行初始化，使其在迭代最初便處于較高的覆蓋率，而且既能夠保持前期快速收斂，也能夠保證算法迭代全程中不斷尋優，最終覆蓋率達到97.88%。相對于前兩種WSN覆蓋優化算法，該算法能夠實現更高的覆蓋率。

5 結 語

本文針對無線傳感器網絡覆蓋優化問題，融合鯨魚優化算法和灰狼優化算法，并引入Halton序列對種群進行初始化，提出一種基于Halton序列的WOA-GWO算法，然后將其應用于無線傳感器網絡覆蓋優化中。通過仿真實驗將本文所提算法與基于WOA的WSN覆蓋優化、基于GWO的WSN覆蓋優化進行對比分析。仿真結果表明，本文所提算法在WSN覆蓋優化問題上具有更強的覆蓋優化性能，優化后WSN的覆蓋率更高。

注：本文通訊作者為馮鋒。

參考文獻

[1] KENNEDY J，RUSSELL E. Particle swarm optimization [C]// Proceedings of ICNN'95-international conference on neural networks. IEEE，1995.

[2] ARORA S，SINGH S. Butterfly optimization algorithm：a novel approach for global optimization [J]. Soft computing，2019，23：715-734.

[3] XUE J，SHEN B. A novel swarm intelligence optimization approach：sparrow search algorithm [J]. Systems science amp; control engineering，2020，8（1）：22-34.

[4]張孟健，汪敏，王霄，等.混合粒子群-蝴蝶算法的WSN節點部署研究[J].計算機工程與科學，2022，44（6）：1013-1022.

[5] MIRJALILI S，LEWIS A. The whale optimization algorithm [J]. Advances in engineering software，2016，95：51-67.

[6] MIRJALILI S，MIRJALILI S M，LEWIS A. Grey wolf optimizer [J]. Advances in engineering software，2014，69：46-61.

[7] HALTON J H. On the efficiency of certain quasi-random sequences of points in evaluating multi-dimensional integrals [J]. Numerische mathematik，1960，2：84-90.

[8]劉紫娟，田文艷.鯨魚算法的優化[J].物聯網技術，2021，11（1）：42-46.

[9]黃冬民，潘泉，梁新華.基于隨機化Halton序列的粒子濾波算法研究[J].計算機應用研究，2011，28（1）：91-94.

[10]高敏，劉海榮，朱燕飛.基于改進灰狼優化算法的WSN覆蓋優化[J].上海師范大學學報（自然科學版），2023，66（2）：256-263.