面向無線異構傳感器網絡的三維覆蓋研究

黃德昌 蔡芳龍 黃招娣 吳章

收稿日期：2023-09-21

基金項目：江西省自然科學基金項目（20232BAA10012）；江西省教育廳科學技術研究項目（GJJ210610）

文章編號：1005-0523（2024）03-0082-08

摘要：【目的】為達到增強無線異構傳感器網絡（HWSN）三維覆蓋能力的目的，提出了一種基于改進蜜獾優化算法（IHBA）的無線異構傳感器網絡三維部署方法?！痉椒ā渴紫?，結合自適應果蠅優化算法，增強算法的隨機搜索性，便于算法得到全局最優解，然后引入替換最差個體策略，避免適應度過低的個體占據種群位置，提高算法收斂速度，同時引入新個體提高種群多樣性，避免算法個體早熟?！窘Y果】將該算法應用于無線異構傳感器網絡的覆蓋優化，相比標準蜜獾算法，其網絡覆蓋率提升18.1%?！窘Y論】仿真結果表明，該算法收斂速度更快，可以有效提高無線異構傳感器的網絡覆蓋能力，整個網絡的節點分布也更加均勻。

關鍵詞：無線異構傳感器網絡；蜜獾算法；自適應果蠅優化算法；替換最差個體策略

中圖分類號：TP212.9；U495 文獻標志碼：A

本文引用格式：黃德昌，蔡芳龍，黃招娣，等. 面向無線異構傳感器網絡的三維覆蓋研究[J]. 華東交通大學學報，2024，41（3）：82-89.

Research on Three-Dimensional Coverage for Wireless Heterogeneous Sensor Networks

Huang Dechang， Cai Fanglong， Huang Zhaodi， Wu Zhang

（School of Information Engineering， East China Jiaotong University， Nanchang 330013， China）

Abstract： 【Objective】In order to enhance the 3D coverage capability of wireless heterogeneous sensor networks （HWSN）， a 3D deployment method based on improved honey badger optimization algorithm （IHBA） is proposed. 【Method】Firstly， combined with the adaptive fruit fly optimization algorithm， the random search ability of the algorithm is enhanced， which is convenient for the algorithm to obtain the global optimal solution. Then， the strategy of replacing the worst individual is introduced to avoid the low adapting individual to occupy the population position and improve algorithm convergence speed. In the meantime， new individuals are introduced to improve the population diversity and avoid the individual prematurity of the algorithm. 【Result】This algorithm is applied to the coverage optimization of HWSN， and the network coverage is improved by 18.1% compared with the standard Honey Badger algorithm. 【Conclusion】The simulation results show that the algorithm converges faster， can effectively improve the network coverage capability of wireless heterogeneous sensors， and the node distribution of the whole network is more uniform.

Key words： wireless heterogeneous sensor networks （HWSN）; honey badger algorithm; adaptive fruit fly optimization algorithm; the worst individual strategy replacement

Citation format： HUANG D C， CAI F L， HUANG Z D， et al. Research on three-dimensional coverage for wireless heterogeneous sensor networks[J]. Journal of East China Jiaotong University， 2024， 41（3）： 82-89.

【研究意義】隨著無線通信技術的不斷發展，無線異構傳感器網絡（heterogeneous wireless sensor networks，HWSN）已逐漸成為全球社會生產和生活不可或缺的重要技術手段[1] 。無線異構傳感器網絡可應用于諸多領域，如農業生產、車輛檢測、環境監測、工 業自動化、交通信號控制等領域[2-4]，是實現智慧交通、智慧城市的關鍵技術之一。在無線異構傳感器網絡應用中，如何高效地進行網絡覆蓋是亟須解決的問題[5-6]。

【研究進展】近年來，為提高復雜三維地形的異構傳感器網絡覆蓋，無線異構傳感器網絡的三維覆蓋得到了廣泛且深入的研究[7-8]。馮秀芳等[9]提出了基于虛擬力的異構節點網絡覆蓋增強算法，在傳感器節點之間引入虛擬力來最大化網絡覆蓋率。劉鵬等[10]提出了一種基于自適應果蠅優化算法的分層異構無線傳感器網絡三維優化部署，模擬果蠅較強的隨機搜索性，加快算法的搜索速度。吳儀等[11]針對異構傳感器網絡部署時引發的隨機空洞與冗余均衡問題，提出一種空洞弧段引導下異構傳感網的覆蓋優化策略，實現了本地化的空洞識別和低耗適配的空洞修補。李明等[12]針對給定部署區域在不同的子區域有不同的重要性，部署的移動傳感器節點具有不同可靠性、壽命、能量和移動能力的復雜條件下節點部署優化問題，提出了一種改進的微分進化算法，增強了算法的局部搜索能力，有效提高了算法覆蓋性能。茍平章等[13]針對異構無線傳感器網絡中初始節點隨機部署或節點失效產生覆蓋盲區的問題，提出一種節點穩定匹配的覆蓋空洞修復優化算法，利用Voronoi多邊形劃分確定節點覆蓋盲區，使得算法收斂速度加快，匹配次數和節點移動距離減少，覆蓋率提高。

【創新特色】綜合現有研究，本文從算法搜索性能、跳出局部最優能力的角度進行研究，首先引入自適應果蠅算法增強算法搜索的隨機性，從而提高算法前期的搜索能力；其次在算法迭代過程中進行替換最差個體操作，減少迭代種群中適應度過低的個體，從而加快了算法的收斂速度，同時引入新個體，避免算法陷入局部最優。

【關鍵問題】為了有效提高異構傳感器網絡覆蓋范圍，減少不必要的資源浪費，結合上述改進策略，本文提出了一種基于改進型蜜獾優化算法的無線異構傳感器網絡覆蓋方法。該方法首先將區域覆蓋率映射為適應度函數，傳感器節點坐標映射為蜜獾個體的位置，并引入蜜獾算法，結合自適應果蠅優化算法、替換最差個體策略形成改進型蜜獾算法，進而優化傳感器節點坐標，以提高區域網絡覆蓋率。

1 傳感器網絡模型

1.1 覆蓋模型

在HWSN中，節點感知模型可分為兩類：0/1感知模型和概率感知模型。其中，0/1感知模型旨在模擬一個以傳感器節點為中心，r為感知半徑的球形空間，當監測點位于該感知半徑內時，就可以認定其已被覆蓋。在三維空間中，傳感器節點[si（xi，yi，zi）]與監測節點[mj（xj，yj，zi）]之間的歐氏距離為

[d（si，mj）=（xi-xj）2+（yi-yj）2+（zi-zj）2] （1）

傳感器節點對監測節點的感知概率定義如下

[Pcov（si，mj）=1，0， d（si， mj）≤r? d（si， mj）>r] （2）

將所有傳感器節點[sall]在目標檢測環境中的區域覆蓋率[Rp（sall，mj）]定義為傳感器節點的覆蓋體積與監測區域的空間體積[Vol]之比，如下

[Rp（sall，mj）=PcovVol] （3）

為使得覆蓋率最大，所求問題可描述為

[f=max（Rp）] （4）

1.2 有效覆蓋模型

討論節點對監測區域的覆蓋情況，采用一種有效覆蓋率作為可靠性指標之一，網絡的有效覆蓋率越高，說明節點覆蓋利用率越高。有效覆蓋率用[Rt]表示

[Rt=RpRm] （5）

式中：[Rm]為所有傳感器節點能覆蓋的最大體積。

2 蜜獾算法

蜜獾算法的基礎是蜜獾的智能搜索行為，蜜獾通過嗅覺發現食物的位置，并在接近食物的地方進行挖掘，以獲取食物。此外，蜜獾還可以跟隨導蜜鳥的指引，找到蜂巢，獲得蜂蜜。Hashim等基于蜜獾尋找食物源的行為建立了標準蜜獾算法模型[14]。

2.1 種群初始化階段

在目標區域內，對蜜獾的種群規模和個體位置隨機初始化

[xi=lbi+r1×（ubi-lbi）] （6）

式中：[xi]為種群中第[i]個蜜獾的位置；[r1]為0～1的隨機數；[lbi，ubi]分別為目標區域的下界和上界。

2.2 定義強度I

蜜獾的嗅覺強度取決于它們對獵物的注意力和距離。氣味強度和運動速度成正比。獵物的氣味強度用[Ii]表示為

[Ii=r2×S4πd2iS=（xi-xi+1）2di=xprey-xi] （7）

式中：[r2]為0～1的隨機數；[S]為獵物集中強度；[di]為當前蜜獾與獵物的距離。

2.3 更新密度因子

密度因子[α]受迭代次數控制，當更新隨著迭代次數減少，密度因子[α]也會減少隨機化，來確?？碧诫A段能平穩過渡到開發階段，從而減少蜜獾覓食過程中的不確定性。計算式為

[α=C×exp-ttmax] （8）

式中：[C≥1]（一般默認為2）；[tmax]為最大迭代次數。

2.4 挖掘階段

在挖掘階段，蜜獾的運動軌跡類似于心臟線，其運動軌跡公式如下

[xnew=xprey+F×β×I×xprey+? ????????F×r3×α×di×cos（2πr4）×1-cos（2πr5）] （9）

式中：[xprey]為蜜獾的全局最優位置；[r3，r4，r5]為3個0～1的不同隨機數；[β]為蜜獾獲取食物的能力，取值大于等于1，一般默認為6；[F]為搜索方向的變向標記，其公式如下

[F=1，-1， r6<0.5r6≥0.5] （10）

式中：[r6]為0～1的隨機數，在蜜獾挖掘階段中，蜜獾比較依賴氣味強度，同時挖掘期間會受到干擾，從而導致蜜獾無法尋找到更好的位置。

2.5 采蜜階段

蜜獾在導蜜鳥的指引下，成功地發現蜂巢的過程可用公式表達為

[xnew=xprey+F×r7×α×di] （11）

式中：[r7]為0～1的隨機數；[xnew]為蜜獾個體更新后的位置；[xprey]為食物源的位置。由上式可知，蜜獾在獵物附近進行搜索。

3 改進型蜜獾算法

針對蜜獾算法在解決優化問題時存在的問題，結合果蠅優化算法、替換最差個體策略提出一種改進型蜜獾算法，替換最差蜜獾個體，保留優良蜜獾個體，同時增加蜜獾隨機搜索能力，從而增強算法尋優過程的穩定性以及算法的跳出局部最優能力[15]。

3.1 結合果蠅優化算法

果蠅優化算法（fruit fly optimization algorithm，FOA）是一種較新的優化算法，它仿照果蠅覓食的行為，來優化復雜問題。FOA遵循果蠅群體智能的自組織行為；思想簡單，參數少，易于實現；既利用全局隨機搜索，也融入局部聚集搜索；FOA的缺點則是容易陷入局部最優，收斂速度相對較慢。

參考劉鵬等[10]提出的一種基于自適應果蠅優化算法的分層異構無線傳感器網絡三維優化部署方法；將其引入標準蜜獾算法的采蜜階段當中，對于蜜獾進行更新，更新的計算公式如下

[xnew=xprey+2×sl×rand-sl] （12）

式中：[rand]為0～1之間的隨機數；[sl]為果蠅飛行的自適應步長，其計算公式為[sl=0.3×α]；引入自適應步長果蠅優化算法，參數少，易于實現；步長隨著迭代次數的增加而減小，滿足前期全局搜索最優，后期局部聚集搜索最優的特性。

3.2 替換最差個體策略

替換最差個體是一種選擇操作，它會替換種群中最差適應度的個體，以維持種群的進化質量。替換最差個體能避免適應度過低的個體占據種群位置，提高算法收斂速度，同時引入新個體提高種群多樣性。替換最差個體主要思想為：找到種群中的最優適應度[max_n]以及最差適應度[min_n]，根據最優適應個體以及最差適應個體設定一個評估閾值[lim]，評估閾值計算公式如下

[lim=（max_n-min_n）×0.2+min_n] （13）

若種群中的個體適應度小于評估閾值，則判定為需要被替換的個體，替換方式則是用最優個體的位置替換該個體的位置，用最優個體的適應度值替換該個體的適應度值。

3.3 IHBA實現流程

IHBA算法實現流程如下。

Step 1 設置種群數N，蜜獾個體數目[n]，最大迭代次數[tmax]，目標區域上下界[ub]和[lb]，蜜獾獲取食物能力[β]等參數，并初始化蜜獾種群；

Step 2 計算蜜獾個體的適應度 ，確定食物源；

Step 3 開始迭代，隨機生成一個概率r，概率大于0.5進入Step 4，否則跳轉到Step 5；

Step 4 進入蜜獾挖掘階段，用式（9）更新蜜獾個體位置；

Step 5 采用自適應果蠅優化算法的搜索方式，用式（12）更新蜜獾個體位置；

Step 6 對種群所有個體的適應度進行評估，選出最優個體適應度以及最差個體適應度，根據最優適應度以及最差適應度設定評估閾值：若蜜獾個體的適應度低于評估閾值，則判定為需要被替換個體，用最優個體的位置以及適應度值替換該個體的位置以及適應度值；

Step 7 計算蜜獾個體適應度，更新食物源位置及其適應度；

Step 8 判斷是否達到最大迭代次數，若滿足條件則輸出最優解，程序結束，反之跳轉到Step 3。

3.4 IHBA流程圖

圖1所示為IHBA實現的流程圖，其實現流程與3.3節中的步驟一致，概括了IHBA算法從種群初始化到輸出最優解的過程。

4 仿真及對比分析

為了驗證IHBA對無線異構傳感器網絡覆蓋的有效性，將無線異構傳感器節點位置映射為蜜獾個體位置，無線異構傳感器網絡節點覆蓋率映射為適應度；并選擇與基本的HBA算法和粒子群算法在MATLAB R2019a的環境中進行無線異構傳感器網絡優化對比，通用實驗參數一致。參與對比的算法有HBA、PSO（粒子群優化算法）。實驗評價指標為無線傳感器覆蓋率、有效覆蓋率以及算法運行時間。

4.1 仿真實驗

4.1.1 目標區域為20×20×20覆蓋優化對比

本組實驗采用兩種不同感知半徑的傳感器進行仿真，感知半徑分別為3，5 m，其數量分別選取30，10，在不考慮間隙誤差情況以及覆蓋模型形狀的情況下，本組參數的異構傳感器恰好能夠完全監測空間，具體實驗參數如表1所示。圖2，圖3，圖4分別為HBA、PSO與IHBA的節點分布對比，圖5所示為IHBA與HBA、PSO的覆蓋率收斂情況對比。表2展示了不同算法的覆蓋率優化結果，其中包括HBA、IHBA、PSO。

圖中紅色球體表示半徑為5 m的傳感器節點覆蓋空間，藍色表示半徑為3 m的傳感器節點覆蓋空間；通過觀察，IHBA優化后，節點位置分布更均勻、排列更整齊；HBA以及PSO優化后的節點覆蓋盲點較多，冗余性更高。

從圖5可以看出，PSO較早地獲得了局部最優解，并沒有獲得全局最優解；HBA前期更新迭代慢，搜索速度較慢，并且沒有獲取到全局最優解；相比前兩種方法，IHBA的效果更好，自適應果蠅算法的引入增強了算法搜索的隨機性，從而增強了算法前期搜索能力。在算法迭代中替換最差個體，減少迭代種群中適應度過低的個體，從而提高了算法的收斂速度；同時引入新個體，避免了算法陷入局部最優，算法中后期覆蓋率緩慢增長，也說明IHBA能夠跳出局部最優，找到更優的全局解。

由表2可知，IHBA進行500次迭代優化后，相比基本HBA，PSO覆蓋率分別提高18.1%，15.1%；有效覆蓋率與覆蓋率相差較小，說明優化后的節點利用率較高，節點冗余較少；在引入改進策略后，IHBA與HBA的算法運行時間相近，可見引入改進策略后并未明顯拖慢算法效率。

4.1.2 目標區域為50×50×50覆蓋優化對比

本組實驗采用感知半徑分別為5，8 m的傳感器進行仿真，其數量分別選取55，45，在不考慮間隙誤差情況以及覆蓋模型形狀的情況下，該組參數的異構傳感器恰好能夠完全監測空間，具體實驗參數如表3所示。

圖6，圖7，圖8分別為HBA優化節點分布圖，PSO優化節點分布圖以及IHBA優化節點分布圖，圖中紅色球體表示半徑為8 m的傳感器節點覆蓋空間，其余均表示半徑為5 m的傳感器節點覆蓋空間。通過仿真效果圖可知，IHBA優化后，節點位置分布更均勻，覆蓋盲點少；HBA以及PSO優化后的節點分布散亂，覆蓋冗余性較高。

從圖9可以看出，在將目標空間增大、節點數量規模增加后，PSO，HBA均出現前期更新迭代慢，搜索速度較慢，并且沒有獲取到全局最優解的情況；相比之下，IHBA依舊能夠進行較快地搜索，這表明結合的自適應果蠅算法在規模增大的情況下依舊具備較強的搜索隨機性，從而增強了算法的搜索能力。在算法迭代中替換最差個體，避免迭代種群中適應度過低的個體占據過多的位置，加快了算法的收斂速度，同時引入新個體，增強了算法跳出局部最優能力，算法中后期覆蓋率緩慢增長，也說明IHBA具備跳出局部最優的能力，繼而尋找到全局最優解。

由表4可知，IHBA進行500次迭代優化后，覆蓋率相比基本HBA、PSO分別提高了17.5%、16.6%；覆蓋率與有效覆蓋率接近，表明節點利用率較高，覆蓋重疊區域較少；IHBA與HBA的算法運行時間相近，說明引入改進策略后并未明顯拖慢算法效率。可見IHBA在無線異構傳感器網絡覆蓋應用中具備有效性和可行性。

4.2 仿真結果分析

從以上仿真實驗可以得出，改進型蜜獾算法具有良好的收斂速度、較強的探索性和跳出局部最優的能力，自適應果蠅算法的引入增強了算法搜索的隨機性，從而增強了算法前期搜索能力；在算法迭代中進行替換最差個體操作，減少迭代種群中適應度過低的個體，從而提高了算法的收斂速度，同時引入新個體，避免了算法陷入局部最優。將該算法應用到HWSN的覆蓋優化問題中，能夠有效提高異構網絡覆蓋范圍，減少不必要的節點部署，從而節省覆蓋所需的資源和成本。

5 結論

針對無線異構傳感器網絡覆蓋優化問題，本文提出了一種改進型蜜獾算法優化異構傳感器節點網絡的覆蓋。通過結合自適應果蠅優化算法，以及引入替換最差個體策略，對標準蜜獾算法進行改進，通過仿真分析，得出以下結論。

1） 引入改進策略后，有效地增強了算法的搜索性能和收斂速度。

2） 將其應用在無線異構傳感器網絡中，異構網絡覆蓋率得到較好地提升。

3） 未來工作可以考慮無線異構網絡節點連通度、通信質量以及節點能耗等。

參考文獻：

[1]?? YAKUBU A W， ALHASSAN A B， SALIFU A M. An enhanced clustering method for extending sensing lifetime of wireless sensor network[J]. Earthline Journal of Mathematical Sciences， 2021， 8（1）： 67-82.

[2]?? WANG J， GUO H Y. Virtual force field coverage algorithms for wireless sensor networks in water environments[J]. International Journal of Sensor Networks， 2020， 32（3）： 174-181.

[3]?? SAADI N， BOUNCEUR A，?EULER R， et al. Maximum lifetime target coverage in wireless sensor networks[J]. Wireless Personal Communications， 2020， 111（3）： 1525-1543.

[4]?? MOHAMMAD M， OZDEMIR S. Towards coverage-aware fuzzy logic-based faulty node detection in heterogeneous wireless sensor networks[J]. Wireless Personal Communications， 2020， 111（1）： 581-610.

[5]?? GOU P， GUO B， GUO M， et al. VKECE-3D： Energy-efficient coverage enhancement in three-dimensional heterogeneous wireless sensor networks based on 3D-voronoi and K-means algorithm[J]. Sensors， 2023， 23（2）： 573.

[6]?? ZENG C， QIN T， TAN W， et al. Coverage optimization of heterogeneous wireless sensor network based on improved wild horse optimizer[J]. Biomimetics， 2023， 8（1）： 70.

[7]?? DAO T K， CHU S C， NGUYEN T T， et al. An optimal WSN node coverage based on enhanced archimedes optimization algorithm[J]. Entropy， 2022， 24（8）： 1018.

[8]?? TOLOUEIASHTIAN M， GOLSORKHTABARAMIRI M， RAD S Y B. An improved whale optimization algorithm solving the point coverage problem in wireless sensor networks[J]. Telecommunication Systems， 2022， 79（3）： 417-436.

[9]?? 馮秀芳， 關志艷， 全欣娜. 基于虛擬力的異構節點網絡覆蓋增強算法[J]. 計算機工程， 2009， 35（5）： 103-105.

FENG X F， GUAN Z， QUAN X N. Coverage-enhancing algorithm for non-isomorphic node network based on virtual force[J]. Computer Engineering， 2009， 35（5）： 103-105.

[10] 劉鵬， 孟欣， 唐蘇瓊， 等. 基于自適應果蠅優化算法的分層異構無線異構傳感器網絡三維優化部署[J]. 傳感技術學報， 2020， 33（7）： 1033-1040.

LIU P， MENG X， TANG S， et al. Optimization on 3D deployment of hierarchical heterogeneous wireless sensor networks： An adaptive FOA approach[J]. Chinese Journal of Sensors and Actuators， 2020， 33（7）： 1033-1040.

[11] 吳儀， 秦寧寧. 空洞弧段引導下異構傳感網的覆蓋優化策略[J]. 傳感技術學報， 2021， 34 （4）： 531-538.

WU Y， QIN N N. Coverage optimization strategy of heterogeneous sensor network guided by hollow arc[J]. Chinese Journal of Sensors and Actuators， 2021， 34 （4）： 531-538.

[12] 李明， 胡江平. 復雜條件下移動異構無線傳感器網絡覆蓋算法[J]. 傳感器與微系統， 2019， 38 （12）： 124-127.

LI M， HU J P， et al. Coverage algorithm for mobile heterogeneous WSNs under complex conditions[J]. Transducer and Microsystem Technologies ， 2019， 38 （12）： 124-127.

[13] 茍平章， 毛剛， 李鳳珍， 等. 異構WSNs中節點穩定匹配的覆蓋空洞修復優化算法[J]. 傳感技術學報， 2019， 32 （6）： 908-914.

GOU P Z， MAO G， LI F Z， et al. Optimized algorithm for recovering coverage holes in heterogeneous wireless sensor networks with node stable matching[J]. Chinese Journal of Sensors and Actuators， 2019， 32 （6）： 908-914.

[14] HASHIM F A， HOUSSEIN E H， HUSSAIN K， et al. Honey badger algorithm： New metaheuristic algorithm for solving optimization problems[J]. Mathematics and Computers in Simulation， 2022（192）： 84-110.

[15] DAO T K， NGUYEN T D， NGUYEN V T. An improved honey badger algorithm for coverage optimization in wireless sensor network[J]. Journal of Internet Technology， 2023， 24（2）： 363-377.

通信作者：黃德昌（1983—），男，碩士，高級實驗師，研究方向為物聯網、機器學習。E-mail： 2777@ecjtu.edu.cn。