基于混合灰狼算法的三維無線傳感網絡覆蓋優化

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

關鍵詞：WSN；混沌映射；三維覆蓋優化；灰狼搜索算法；物聯網；網絡覆蓋率

中圖分類號：TP332.3 文獻標識碼：A 文章編號：2095-1302（2024）07-00-03

0 引 言

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

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

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

1 三維無線傳感器網絡覆蓋率

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

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

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

目標區域中k個探測節點P1， P2， ...， Pk的覆蓋率分別為pcov（s1， P1）， pcov（s2， P2）， ...， pcov（sn， Pk），可得該三維無線傳感網絡的覆蓋率為：

無線傳感器網絡的覆蓋優化問題就是尋找最優的節點位置，使得區域總覆蓋率最大。

2 灰狼優化算法

灰狼優化算法（Grey Wolf Optimization， GWO）是一種基于群體的元啟發式算法，模擬自然界中狼群的領導階層和狩獵機制[6]，具有收斂性能較強、參數少以及易于實現等優點。灰狼優化算法的原理是將最優解視為獵物，將灰狼分為α、β、δ、ω四種類型，分別表示領導者、副領導者、跟隨者和普通灰狼。灰狼種群通過搜索、包圍、最終攻擊獵物這三個步驟來完成一次捕獵。灰狼優化算法的公式如下。

（1）搜索獵物

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

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

（2）包圍獵物

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

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

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

（3）攻擊獵物

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

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

3 改進的混合灰狼優化算法

3.1 Tent混沌映射

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

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

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

3.2 融入鯨魚優化算法的灰狼搜索算法

3.2.1 增強型位置更新策略

在原本的灰狼搜索算法的基礎上進行位置更新公式的改進和優化，采用慣性權重對當前個體的位置更新產生影響，涉及的具體表達式為：

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

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

3.2.2 螺旋泡網狩獵機制的位置更新策略

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

（1）包圍獵物

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

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

（2）發泡網攻擊

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

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

（3）搜索捕食

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

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

4 仿真實驗與分析

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

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

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

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

5 結 語

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

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

參考文獻

[1]段冰冰，馬云鵬，劉津平，等.基于混沌映射與反向學習機制的非線性灰狼優化算法[J].軟件工程，2023，26（5）：36-40.

[2]周利民，楊科華，周攀.基于魚群算法的無線傳感網絡覆蓋優化策略[J].計算機應用研究，2010，27（6）：2276-2279.

[3]董文欣. 改進蟻群算法在函數優化及無線傳感器網絡中的應用[D].西安：西安電子科技大學，2017.

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

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

[6] SADEGHI A，BANI E A，FALLAHI 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算法的三維無線傳感網絡覆蓋優化[J].電子測量技術，2023，46（4）：25-34.

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

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

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