摘 要：為解決無線傳感器網(wǎng)絡(luò)（WSN）隨機(jī)部署時(shí)存在分布不均而導(dǎo)致覆蓋率低的問題，提出一種基于Halton序列且結(jié)合鯨魚優(yōu)化算法與灰狼優(yōu)化算法（WOA-GWO）的WSN覆蓋優(yōu)化方法。首先，將WOA算法與GWO算法融合，WOA算法在迭代前期有著更快的收斂速度，可在前期使WSN部署快速趨于成熟，而GWO算法能夠?qū)崿F(xiàn)局部尋優(yōu)與全局尋優(yōu)的平衡，將其用于算法迭代的中后期可保證WSN覆蓋優(yōu)化的整體性能；其次，使用融合隨機(jī)因子的Halton序列方法對(duì)種群進(jìn)行初始化，使傳感器節(jié)點(diǎn)在初始化時(shí)的分布更加均勻，提升初始化種群質(zhì)量；最后，將基于WOA的WSN覆蓋優(yōu)化、GWO的WSN覆蓋優(yōu)化、基于Halton序列WOA-GWO的WSN覆蓋優(yōu)化效果進(jìn)行對(duì)比，驗(yàn)證本文所提方法的有效性。

關(guān)鍵詞：無線傳感器網(wǎng)絡(luò)；覆蓋優(yōu)化；鯨魚算法；灰狼算法；Halton序列；全局尋優(yōu)

中圖分類號(hào)：TP393.0 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：2095-1302（2024）02-00-05

0 引 言

無線傳感器網(wǎng)絡(luò)（Wireless Sensor Network， WSN）是一種由大量微型傳感器節(jié)點(diǎn)組成的網(wǎng)絡(luò)系統(tǒng)，能夠?qū)崿F(xiàn)對(duì)環(huán)境中各種參數(shù)的實(shí)時(shí)監(jiān)測(cè)和數(shù)據(jù)采集。WSN在環(huán)境監(jiān)測(cè)、農(nóng)業(yè)、醫(yī)療、交通等領(lǐng)域具有廣闊的應(yīng)用前景。然而，在WSN中，傳感器節(jié)點(diǎn)分布不均勻會(huì)導(dǎo)致監(jiān)測(cè)區(qū)域未被充分覆蓋，從而影響監(jiān)測(cè)數(shù)據(jù)的準(zhǔn)確性和可靠性。因此，WSN能否充分覆蓋成為WSN研究中的一個(gè)重要問題。WSN覆蓋優(yōu)化是指在保證所有監(jiān)測(cè)區(qū)域被覆蓋的情況下，盡可能減少傳感器節(jié)點(diǎn)的數(shù)量。目前，常用的解決WSN覆蓋問題的方法是優(yōu)化算法，如粒子群算法[1]、蝴蝶優(yōu)化算法[2]、麻雀搜索算法[3]等。然而，這些算法在優(yōu)化效率、解決復(fù)雜問題等方面存在不足。一些研究表明，將新型的優(yōu)化算法、改進(jìn)的智能優(yōu)化算法用于節(jié)點(diǎn)部署具有一定的價(jià)值及意義[4]。

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

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

1 節(jié)點(diǎn)覆蓋模型

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

（1）

監(jiān)測(cè)節(jié)點(diǎn)mj能被感知的概率為：

（2）

所有傳感器對(duì)mj的聯(lián)合覆蓋率為：

（3）

式中：sall是測(cè)量范圍內(nèi)的所有傳感器節(jié)點(diǎn)。傳感器節(jié)點(diǎn)對(duì)整個(gè)區(qū)域的監(jiān)測(cè)范圍就是WSN的覆蓋程度，可計(jì)算出所有監(jiān)測(cè)點(diǎn)的監(jiān)測(cè)覆蓋率：

（4）

2 基本算法介紹

2.1 鯨魚優(yōu)化算法

WOA是對(duì)座頭鯨的特殊搜索方法和圍捕機(jī)制進(jìn)行模擬的算法，其中主要包括圍捕獵物、氣泡網(wǎng)捕食、搜索獵物三個(gè)重要階段。

（1）圍捕獵物

首先，在當(dāng)前種群中選取最佳種群當(dāng)做目前最優(yōu)解，其他個(gè)體根據(jù)最優(yōu)解的位置來更新自身位置，其位置更新公式如下：

（5）

（6）

式中：t表示當(dāng)前迭代次數(shù)；X（t+1）表示更新后的位置；X*（t）是目前最優(yōu)解的位置向量；A和C為系數(shù)向量，計(jì)算方式

如下：

（7）

（8）

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

（2）氣泡網(wǎng)捕食

捕食機(jī)制分別是包圍捕食和氣泡網(wǎng)捕食。采用氣泡網(wǎng)捕食時(shí)，位置更新用對(duì)數(shù)螺旋方程表達(dá)：

（9）

（10）

式中：D*表示當(dāng)前搜索個(gè)體與當(dāng)前最優(yōu)解的距離；b為螺旋形狀參數(shù)；l為[-1，1]間的隨機(jī)數(shù)。為了模擬鯨魚收縮包圍和螺旋更新機(jī)制，用如下公式表達(dá)：

（11）

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

（3）搜索獵物

隨機(jī)尋找獵物是除氣泡網(wǎng)捕食法之外的方法，當(dāng)|A|≥1時(shí)，鯨魚會(huì)隨機(jī)搜索，其公式為：

（12）

（13）

式中：D為當(dāng)前搜索個(gè)體與隨機(jī)個(gè)體的距離；Xrand（t）為當(dāng)前隨機(jī)個(gè)體位置。

2.2 WOA算法流程

標(biāo)準(zhǔn)WOA算法流程如圖1所示。其計(jì)算流程具體如下：

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

（2）計(jì)算當(dāng)前種群適應(yīng)度，并保留最優(yōu)位置種群。

（3）計(jì)算參數(shù)a、p和系數(shù)向量A和C。判斷p是否小于0.5，是則轉(zhuǎn)入步驟（4），否則采用式（9）方式進(jìn)行氣泡網(wǎng)捕食。

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

（5）位置更新結(jié)束，與先前種群個(gè)體適應(yīng)度進(jìn)行比較，保留較優(yōu)解。

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

2.3 灰狼優(yōu)化算法

GWO是通過模擬自然界中灰狼的領(lǐng)導(dǎo)等級(jí)和狩獵機(jī)制來實(shí)現(xiàn)尋優(yōu)的算法，其中主要包括搜索獵物、包圍獵物、攻擊獵物三個(gè)重要階段。

（1）包圍獵物

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

（14）

（15）

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

式（15）；A和C是兩個(gè)協(xié)同系數(shù)向量，計(jì)算方式如下：

（16）

（17）

式中：和是[0，1]內(nèi)取值的隨機(jī)向量；a為收斂因子。

（2）追捕獵物

在狩獵過程中，獵物位置Xp是未知的，因此在GWO中，認(rèn)為α為最優(yōu)灰狼，β為次優(yōu)灰狼，δ為第三優(yōu)灰狼，其余灰狼為ω。根據(jù)α、β、δ來指導(dǎo)ω的移動(dòng)，從而實(shí)現(xiàn)全局最優(yōu)，利用α、β、δ的位置、、來更新所有灰狼位置，公式如下：

（18）

（19）

（20）

（3）攻擊獵物

灰狼攻擊獵物行為被抽象成數(shù)學(xué)模型，如下式所示：

（21）

式中：a為收斂因子，它決定了A的變化，a值偏大時(shí)進(jìn)行全局搜索，偏小時(shí)進(jìn)行局部搜索；t為當(dāng)前迭代次數(shù)；T為最大迭代次數(shù)。

2.4 GWO算法流程

標(biāo)準(zhǔn)GWO算法流程如圖2所示。

計(jì)算流程如下：

（1）初始化參數(shù)灰狼種群，并計(jì)算a、A、C等參數(shù)。

（2）計(jì)算當(dāng)前種群灰狼適應(yīng)度，保留適應(yīng)度最好的前三匹狼α、β、δ。

（3）根據(jù)最優(yōu)的三匹狼，更新其余ω狼的位置。

（4）更新參數(shù)a、A、C。

（5）計(jì)算全部灰狼的適應(yīng)度，并更新α、β、δ狼的位置及適應(yīng)度。

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

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

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

3.1 WOA-GWO算法

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

通過多組實(shí)驗(yàn)進(jìn)行對(duì)比，發(fā)現(xiàn)將整體迭代次數(shù)的前10%作為WOA尋優(yōu)階段，其余90%作為GWO尋優(yōu)階段能夠使尋優(yōu)效果達(dá)到最佳。因此，分別將兩種算法應(yīng)用于WOA-GWO整體迭代過程的前10%與后90%兩個(gè)階段。

3.2 Halton序列

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

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

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

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

3.3 算法流程

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

計(jì)算流程具體如下：

（1）初始化種群數(shù)量N、最大迭代次數(shù)T等參數(shù)，并設(shè)置當(dāng)前迭代次數(shù)t=1。

（2）使用隨機(jī)Halton序列對(duì)種群位置進(jìn)行初始化。

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

（4）更新最優(yōu)種群的位置。

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

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

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

本文在MATLABR2022a平臺(tái)上對(duì)所提方法進(jìn)行仿真，對(duì)其性能等進(jìn)行測(cè)試。將基于Halton序列WOA-GWO的WSN覆蓋效果與基于WOA的WSN覆蓋和基于GWO的WSN覆蓋效果進(jìn)行對(duì)比。為保證算法的公平性，在實(shí)驗(yàn)過程中對(duì)算法設(shè)置相同參數(shù)，監(jiān)測(cè)區(qū)域面積為50 m×50 m，節(jié)點(diǎn)數(shù)量為40個(gè)，種群規(guī)模為100個(gè)，感知半徑為5 m，迭代次數(shù)設(shè)置為500。

4.2 仿真結(jié)果與分析

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

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

從圖12可以對(duì)比出三種算法在WSN覆蓋優(yōu)化過程的覆蓋率變化曲線?；赪OA的WSN覆蓋優(yōu)化在前30次迭代中，收斂速度明顯優(yōu)于GWO算法，然后收斂速度趨于平緩，偶爾會(huì)提高覆蓋率，最終覆蓋率達(dá)到86.44%；基于GWO算法的WSN覆蓋優(yōu)化在整個(gè)迭代過程中覆蓋率不斷提升，并且最終覆蓋率較高，達(dá)到了96.68%；基于Halton序列的WOA-GWO覆蓋優(yōu)化綜合了兩種算法的優(yōu)點(diǎn)，并且基于Halton序列對(duì)種群進(jìn)行初始化，使其在迭代最初便處于較高的覆蓋率，而且既能夠保持前期快速收斂，也能夠保證算法迭代全程中不斷尋優(yōu)，最終覆蓋率達(dá)到97.88%。相對(duì)于前兩種WSN覆蓋優(yōu)化算法，該算法能夠?qū)崿F(xiàn)更高的覆蓋率。

5 結(jié) 語

本文針對(duì)無線傳感器網(wǎng)絡(luò)覆蓋優(yōu)化問題，融合鯨魚優(yōu)化算法和灰狼優(yōu)化算法，并引入Halton序列對(duì)種群進(jìn)行初始化，提出一種基于Halton序列的WOA-GWO算法，然后將其應(yīng)用于無線傳感器網(wǎng)絡(luò)覆蓋優(yōu)化中。通過仿真實(shí)驗(yàn)將本文所提算法與基于WOA的WSN覆蓋優(yōu)化、基于GWO的WSN覆蓋優(yōu)化進(jìn)行對(duì)比分析。仿真結(jié)果表明，本文所提算法在WSN覆蓋優(yōu)化問題上具有更強(qiáng)的覆蓋優(yōu)化性能，優(yōu)化后WSN的覆蓋率更高。

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

參考文獻(xiàn)

[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節(jié)點(diǎn)部署研究[J].計(jì)算機(jī)工程與科學(xué)，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]劉紫娟，田文艷.鯨魚算法的優(yōu)化[J].物聯(lián)網(wǎng)技術(shù)，2021，11（1）：42-46.

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

[10]高敏，劉海榮，朱燕飛.基于改進(jìn)灰狼優(yōu)化算法的WSN覆蓋優(yōu)化[J].上海師范大學(xué)學(xué)報(bào)（自然科學(xué)版），2023，66（2）：256-263.