基于混合灰狼算法的三維無線傳感網(wǎng)絡(luò)覆蓋優(yōu)化

摘 要：針對三維無線傳感器網(wǎng)絡(luò)部署中存在的傳感器節(jié)點部署不均勻、覆蓋率偏低、收斂所需的迭代次數(shù)多等問題進(jìn)行優(yōu)化探索。采用Tent混沌映射初始化方法進(jìn)行節(jié)點部署，并將鯨魚優(yōu)化算法與改良灰狼搜索算法混合后進(jìn)行優(yōu)化，以解決部署不均勻等問題，進(jìn)而增強(qiáng)算法的尋優(yōu)收斂能力。實驗結(jié)果表明，所采取的算法相較于目前主流的三維傳感器搜索算法有較大提升。

關(guān)鍵詞：WSN；混沌映射；三維覆蓋優(yōu)化；灰狼搜索算法；物聯(lián)網(wǎng)；網(wǎng)絡(luò)覆蓋率

中圖分類號：TP332.3 文獻(xiàn)標(biāo)識碼：A 文章編號：2095-1302（2024）07-00-03

0 引 言

無線傳感器網(wǎng)絡(luò)（Wireless Sensor Network， WSN）是一種由傳感器組成的分布式多跳自組織網(wǎng)絡(luò)。WSN具有網(wǎng)絡(luò)設(shè)置靈活，設(shè)備位置可以隨時更改，可以與互聯(lián)網(wǎng)進(jìn)行有線或無線連接等優(yōu)點，因此在社會生活的諸多領(lǐng)域被廣泛應(yīng)用[1]。例如，可以用無線傳感器網(wǎng)絡(luò)來監(jiān)測混凝土澆灌溫度、畜牧家禽養(yǎng)殖環(huán)境、工業(yè)環(huán)境等。因此，如何調(diào)整傳感器的部署位置，使無線傳感器網(wǎng)絡(luò)在有限的條件下在目標(biāo)區(qū)域中具有更高的覆蓋率是很多人關(guān)注和研究的問題。

無線傳感器覆蓋問題是WSN應(yīng)用過程中的一個重要問題，它直接影響了網(wǎng)絡(luò)的性能和應(yīng)用效果。根據(jù)不同條件，無線傳感器覆蓋問題可以分為不同的類型。根據(jù)覆蓋區(qū)域的維度，可分為一維、二維和三維覆蓋問題；根據(jù)覆蓋質(zhì)量的要求，可以分為最小覆蓋、最大覆蓋和K-覆蓋問題。無線傳感器覆蓋問題的求解方法主要有兩類：一類是基于幾何方法，利用幾何圖形或拓?fù)浣Y(jié)構(gòu)來描述和分析覆蓋問題；另一類是基于優(yōu)化方法，利用啟發(fā)式算法或元啟發(fā)式算法來尋找最優(yōu)或近似最優(yōu)的解。面對WSN中節(jié)點部署不均勻、覆蓋率差等問題，周利民等[2]利用魚群算法來解決無線傳感器網(wǎng)絡(luò)監(jiān)測區(qū)域面積的覆蓋優(yōu)化問題，利用魚群算法的搜索能力提高了無線傳感器網(wǎng)絡(luò)的覆蓋率。董文欣[3]針對蟻群算法中存在的缺陷加入了混沌搜索策略，顯著改善了算法的全局搜索效果。張希淼等人[4]針對鯨魚優(yōu)化算法（Whale Optimization Algorithm， WOA）尋優(yōu)精度低、尋優(yōu)過程中容易陷入局部最優(yōu)解并且算法的收斂速度不夠快等問題，提出了一種融合混沌映射和二次插值策略的自適應(yīng)鯨魚優(yōu)化算法。在算法中引入混沌映射進(jìn)行初始化種群操作，使初始化種群分布更加均勻，提高了種群多樣性；設(shè)計了一種自適應(yīng)的權(quán)重，提高了算法的尋優(yōu)能力以及收斂速度；利用二次插值策略生成新的鯨魚個體，采用貪婪策略更新局部最優(yōu)解，提高了種群計算的精度。

目前，一維和二維環(huán)境下的無線傳感網(wǎng)絡(luò)覆蓋已經(jīng)基本完善，主流算法覆蓋率已經(jīng)足夠高，但在實際生產(chǎn)生活中，還需要考慮在三維空間中的傳感器覆蓋問題。目前針對WSN的三維覆蓋問題的研究仍不足，主流的優(yōu)化算法大多存在收斂速度慢、算法復(fù)雜度高以及傳感器節(jié)點冗余等問題。本文針對性地提出了基于Tent混沌映射下混合灰狼搜索算法的三維傳感器位置優(yōu)化算法。經(jīng)實驗驗證，改進(jìn)后的算法具有節(jié)點分布較為均勻、算法復(fù)雜度低等優(yōu)點。

1 三維無線傳感器網(wǎng)絡(luò)覆蓋率

無線傳感器三維覆蓋模型是用于描述無線傳感器網(wǎng)絡(luò)在三維空間中對目標(biāo)區(qū)域的監(jiān)測能力的數(shù)學(xué)模型，通常涉及到傳感器節(jié)點的感知模型、覆蓋率的定義和計算、覆蓋優(yōu)化算法等方面。三維空間中的n個傳感器節(jié)點集合表示為Node{s1， s2， ...， sn}，傳感器的感知半徑為R，其中第i個節(jié)點坐標(biāo)表示為（xi， yi， zi）。探測節(jié)點P（x， y， z）到傳感器節(jié)點的距離為：

采用布爾模型作為概率感知模型，則該探測節(jié)點被傳感器節(jié)點所覆蓋的概率為：

上式表明，若節(jié)點到傳感器的歐氏距離小于等于傳感器的感知半徑，則該節(jié)點可以被傳感器覆蓋，反之則不能[5]。對于n個傳感器節(jié)點，它們對探測節(jié)點P的覆蓋率分別為p（s1）， p（s2）， ...， p（sn），可得點P的覆蓋率為：

目標(biāo)區(qū)域中k個探測節(jié)點P1， P2， ...， Pk的覆蓋率分別為pcov（s1， P1）， pcov（s2， P2）， ...， pcov（sn， Pk），可得該三維無線傳感網(wǎng)絡(luò)的覆蓋率為：

無線傳感器網(wǎng)絡(luò)的覆蓋優(yōu)化問題就是尋找最優(yōu)的節(jié)點位置，使得區(qū)域總覆蓋率最大。

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

灰狼優(yōu)化算法（Grey Wolf Optimization， GWO）是一種基于群體的元啟發(fā)式算法，模擬自然界中狼群的領(lǐng)導(dǎo)階層和狩獵機(jī)制[6]，具有收斂性能較強(qiáng)、參數(shù)少以及易于實現(xiàn)等優(yōu)點?；依莾?yōu)化算法的原理是將最優(yōu)解視為獵物，將灰狼分為α、β、δ、ω四種類型，分別表示領(lǐng)導(dǎo)者、副領(lǐng)導(dǎo)者、跟隨者和普通灰狼?；依欠N群通過搜索、包圍、最終攻擊獵物這三個步驟來完成一次捕獵?；依莾?yōu)化算法的公式如下。

（1）搜索獵物

式中：t為當(dāng)前迭代次數(shù)；Xp和X分別表示獵物和當(dāng)前灰狼個體的位置向量；A和C為系數(shù)向量，計算公式如下：

式中：收斂因子a的值在迭代過程中由2線性減小到0[7]；r1和r2是取值在[0，1]范圍內(nèi)的隨機(jī)向量。當(dāng)|A|≥1時算法進(jìn)行全局搜索，|A|＜1時算法進(jìn)行局部搜索。

（2）包圍獵物

通過計算得到最優(yōu)解、優(yōu)解以及次優(yōu)解，分別賦予α、β、δ灰狼類型。

式中：Dα、Dβ和Dδ分別表示α、β和δ狼與其他個體間的距離；Xα、Xβ和Xδ分別代表α、β和δ狼當(dāng)前的位置；C1、C2和

C3的計算方法如式（7）所示。

（3）攻擊獵物

其他狼的位置由三個位置最優(yōu)的狼，即α、β和δ的位置共同決定，在產(chǎn)生新群體后對種群中的個體進(jìn)行邊界控制，最終完成一次迭代。

式中：A1、A2和A3的計算方法如式（6）所示。

3 改進(jìn)的混合灰狼優(yōu)化算法

3.1 Tent混沌映射

灰狼優(yōu)化算法具有受參數(shù)影響小以及易于收斂的優(yōu)點，但在解決復(fù)雜問題時仍存在易過早收斂、易陷入局部最優(yōu)解的問題。為解決這一問題，采取Tent混沌映射對種群初始化，使得初始解可以更加均勻地分布在解空間中，便于尋優(yōu)。基于Tent映射形成混沌序列的過程如下。

式中：k為種群數(shù)；t為當(dāng)前迭代次數(shù)；為保持算法初始化信息的隨機(jī)性，u取值為（0，1）之間的隨機(jī)數(shù)，本實驗取值0.5。結(jié)合混沌序列Ztk生成搜索區(qū)域內(nèi)的灰狼個體初始位置序列Xtk的過程如下[8]：

式中：Xkt， min和Xkt， max分別為Xtk序列的最小值和最大值。

3.2 融入鯨魚優(yōu)化算法的灰狼搜索算法

3.2.1 增強(qiáng)型位置更新策略

在原本的灰狼搜索算法的基礎(chǔ)上進(jìn)行位置更新公式的改進(jìn)和優(yōu)化，采用慣性權(quán)重對當(dāng)前個體的位置更新產(chǎn)生影響，涉及的具體表達(dá)式為：

在原始的灰狼搜索算法中，控制參數(shù)a的值線性均勻減少，但由于GWO算法的搜索過程并非線性的，此參數(shù)控制策略不能真實反映搜索過程且效果較差。因此，在增強(qiáng)型灰狼搜索算法中優(yōu)化了a的參數(shù)控制策略，公式如下：

式中：t表示當(dāng)前迭代次數(shù)；iter表示最大迭代次數(shù)；μ為取值在（0，1）范圍內(nèi)的非線性調(diào)整指數(shù)；ainitional和afinal分別表示控制參數(shù)a的初始值和終止值[9]，即2和0。

3.2.2 螺旋泡網(wǎng)狩獵機(jī)制的位置更新策略

鯨魚優(yōu)化算法是模仿座頭鯨的狩獵行為提出的一種新型啟發(fā)式優(yōu)化算法。在算法中，每只座頭鯨的位置代表一個可行解[10]。以座頭鯨螺旋型逐漸包圍游向獵物的狩獵行為為靈感，鯨魚優(yōu)化算法采用螺旋泡網(wǎng)狩獵機(jī)制，主要包括包圍獵物、發(fā)泡網(wǎng)攻擊以及搜索捕食三個步驟。

（1）包圍獵物

與灰狼優(yōu)化算法不同，鯨魚優(yōu)化算法直接以種群中位置最優(yōu)的個體位置作為包圍的中心點，表達(dá)式如下：

式中：X*（t）為種群中最優(yōu)個體的位置向量。

（2）發(fā)泡網(wǎng)攻擊

座頭鯨在捕獵的過程中，有一半的概率選擇收縮包圍圈，一半的概率選擇以螺旋形態(tài)向獵物游走逼近。當(dāng)選擇收縮包圍時位置更新公式與上一步相同，當(dāng)選擇螺旋逼近時位置更新公式如下：

式中：D表示鯨魚和獵物之間的距離；b是一個常數(shù)，用來定義螺線的形狀；l是取值在（-1，1）之間的隨機(jī)數(shù)。

（3）搜索捕食

為增強(qiáng)鯨魚優(yōu)化算法的全局搜索能力，在搜索捕食過程中鯨魚個體可能選擇一名隨機(jī)鯨魚的位置進(jìn)行靠近而非最佳個體位置。因此，當(dāng)|A|gt;1時進(jìn)行全局搜索。X'為種群中某一隨機(jī)個體的位置向量。

經(jīng)實驗對比可見，鯨魚優(yōu)化算法在迭代后期速度較快且具有良好的局部尋優(yōu)能力，但全局搜索能力較差且種群多樣性不足；而灰狼優(yōu)化算法存在容易早熟收斂的問題。為了彌補(bǔ)灰狼算法的缺點，采取將鯨魚優(yōu)化算法與增強(qiáng)型灰狼搜索算法結(jié)合的方式，在迭代前期采用灰狼優(yōu)化算法對目標(biāo)進(jìn)行逼近，在后期采用鯨魚優(yōu)化算法來避免陷入局部最優(yōu)解的情況。

4 仿真實驗與分析

本次仿真實驗的環(huán)境主要為Intel? CoreTM i7-7700 CPU處理器，內(nèi)存8 GB，編程環(huán)境為MATLAB R2023a。無線傳感器網(wǎng)絡(luò)的部署環(huán)境為60 m×60 m×60 m的三維空間，傳感器節(jié)點數(shù)為70，感知半徑為10 m，迭代次數(shù)為100次，種群規(guī)模為50。在同一實驗環(huán)境下，分別采用鯨魚優(yōu)化算法、灰狼搜索算法和改進(jìn)的灰狼搜索算法進(jìn)行10次測試，分別取平均值并進(jìn)行記錄。

為驗證改進(jìn)灰狼搜索算法在三維WSN覆蓋優(yōu)化研究中的效果，選用國際通用的Benchmark函數(shù)進(jìn)行測試，并選擇鯨魚優(yōu)化算法（WOA）與灰狼搜索算法（GWO）進(jìn)行對比分析。

進(jìn)行算法對比實驗時，設(shè)置相同的參數(shù)和實驗環(huán)境，經(jīng)過實驗可得其三維初始化部署如圖1（a）所示，可以看到節(jié)點分布不夠均勻，覆蓋率較低，僅為0.639 4。經(jīng)過優(yōu)化，初始GWO算法得到的覆蓋率約為0.782 73，WOA算法得到的覆蓋率約為0.810 97，本文提出的算法覆蓋率約為0.843 88，且運(yùn)行時間較短。

從圖1所示的三種算法的覆蓋率優(yōu)化部署圖中可以看出：采用本文的優(yōu)化方法，傳感器節(jié)點分布較為均勻且覆蓋率較高，節(jié)點的利用率較高。各算法下的基準(zhǔn)函數(shù)對比如圖2所示。

5 結(jié) 語

對于三維環(huán)境下采用灰狼優(yōu)化算法時出現(xiàn)的節(jié)點分布不均勻、容易早熟收斂等問題，本文提出了一種在Tent初始化映射后與鯨魚優(yōu)化算法混合的增強(qiáng)型灰狼搜索算法。經(jīng)過實驗證明取得了較為良好的效果，改善了算法的優(yōu)化過程，但還存在算法局限性較大、計算量較大等問題。在以后的工作中將針對這些問題進(jìn)行研究和優(yōu)化。

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

參考文獻(xiàn)

[1]段冰冰，馬云鵬，劉津平，等.基于混沌映射與反向?qū)W習(xí)機(jī)制的非線性灰狼優(yōu)化算法[J].軟件工程，2023，26（5）：36-40.

[2]周利民，楊科華，周攀.基于魚群算法的無線傳感網(wǎng)絡(luò)覆蓋優(yōu)化策略[J].計算機(jī)應(yīng)用研究，2010，27（6）：2276-2279.

[3]董文欣. 改進(jìn)蟻群算法在函數(shù)優(yōu)化及無線傳感器網(wǎng)絡(luò)中的應(yīng)用[D].西安：西安電子科技大學(xué)，2017.

[4]張希淼，馬寧，付偉，等.融合混沌映射和二次插值的自適應(yīng)鯨魚優(yōu)化算法[J].計算機(jī)工程與設(shè)計，2023，44（4）：1088-1096.

[5]馬敬思，史旭華，何婷婷，等.基于免疫算法的無線傳感網(wǎng)絡(luò)覆蓋研究[J].移動通信，2015，39（6）：70-75.

[6] SADEGHI A，BANI E A，F(xiàn)ALLAHI A. Grey wolf optimizer and whale optimization algorithm for stochastic inventory management of reusable products in a two-level supply chain [J]. IEEE access，2023，11：40278-40297.

[7]陳立萬，曾蝶，趙尚飛，等.基于EGWOEO算法的三維無線傳感網(wǎng)絡(luò)覆蓋優(yōu)化[J].電子測量技術(shù)，2023，46（4）：25-34.

[8]劉志強(qiáng)，何麗，袁亮，等.采用改進(jìn)灰狼算法的移動機(jī)器人路徑規(guī)劃[J].西安交通大學(xué)學(xué)報，2022，56（10）：49-60.

[9]覃溪，龍文.基于隨機(jī)差分變異的改進(jìn)鯨魚優(yōu)化算法[J].中國科技論文，2018，13（8）：937-942.

[10]張東洋，楊永輝，儲茂祥，等.基于2維鯨魚優(yōu)化加權(quán)的WGG-Otsu算法的鋼板表面缺陷圖像分割[J].安徽大學(xué)學(xué)報（自然科學(xué)版），2020，44（3）：72-77.