基于量子行為算法的WSN覆蓋優化

摘 要：針對無線傳感器網絡節點因隨機部署而導致覆蓋率低的問題，提出一種基于量子行為的蜣螂算法。首先，采用改進Logistic混沌映射初始化種群，增強種群多樣性和全局搜索能力。其次，在蜣螂算法跳舞行為中引入麻雀算法警戒機制，增強全局搜索能力，加快收斂速度。最后，在蜣螂算法覓食行為中引入量子行為，平衡全局搜索和局部搜索。仿真實驗結果表明，相較于其他傳統算法，改進蜣螂算法能夠有效提高無線傳感網絡節點覆蓋率，且節點利用率更高。

關鍵詞：無線傳感器網絡；覆蓋優化；蜣螂優化算法；節點調度；量子行為；混沌映射

中圖分類號：TP393 文獻標識碼：A 文章編號：2095-1302（2025）03-00-05

0 引 言

無線傳感器網絡是一個由眾多自供能的傳感器節點所組成的網絡系統，這些節點能夠感知環境、采集數據，并通過無線的方式實現數據的交換，從而實現對指定區域的監測、數據處理和通信功能。WSN技術已廣泛應用于工業自動化、農業監測、建筑物智能化、能源管理、城市基礎設施管理以及野生動物監控等多個領域[1]。由于地形、環境影響以及成本等因素，WSN一般采用隨機部署的方法。然而，隨機部署可能會造成節點冗余以及監測區域覆蓋不完全的問題，進而降低網絡的整體可靠性和網絡壽命。因此，需要對傳感器節點的部署策略進行改進，以實現節點的均勻分布，并提高網絡的整體覆蓋率及連通度，以傳遞更多的信息[2-3]。

群智能優化算法在處理WSN覆蓋優化問題上應用廣泛。文獻[4]提出鯨魚算法和灰狼算法相結合的WSN覆蓋優化策略，有效提高了覆蓋率，但該方式增加了算法的復雜性和計算成本。文獻[5]提出改進蛇優化算法的覆蓋優化策略，有效提高了覆蓋率和網絡生存時間，但是存在節點冗余的問題。文獻[6]提出了一種自適應粒子群算法的覆蓋優化策略，提高了覆蓋率，降低了節點移動距離，但是存在覆蓋空洞區域。上述算法都有效地提高了覆蓋率，但是都存在一些問題，仍存在優化空間。

本文應用蜣螂算法（Dung Beetle Optimizer， DBO）[7]來研究WSN覆蓋優化問題，并提出一種改進的蜣螂算法（SQBDBO）。在種群初始化階段引入改進Logistic混沌映射初始化種群；在蜣螂跳舞行為中引入麻雀算法警戒機制，提高算法的全局搜索能力和加快收斂速度；在覓食行為中引入量子行為，增加種群多樣性以及平衡全局搜索和局部搜索的能力。將SQBDBO算法應用于WSN中節點覆蓋優化問題上。在相同實驗條件下與其他優化算法進行仿真對比，驗證本文的改進算法在WSN節點覆蓋優化問題上的有效性。

1 WSN覆蓋模型和目標函數

在面積為M×L的二維平面監測區域內，隨機部署n個傳感器節點，傳感器節點集合為S={S1， S2， ...， Si， ...， Sn}，其中Si表示第i個節點，傳感器Si的坐標位置為（xi， yi），每個節點都具有相同的感知半徑Rp和通信半徑Rc，并且Rp≤2Rc。將二維平面區域離散化成M×L個網格，每個網格面積為1，每個目標子區域的中心節點就是目標節點，目標節點Kj的坐標位置為（xj， yj），則目標節點Kj與傳感器節點Si之間的歐氏距離為：

（1）

若d（Si， Kj）≤Rp，則表明目標節點Kj可以被傳感器節點Si感知并覆蓋。目標節點Kj可以被傳感器節點Si感知的概率p（Si， Kj）為：

（2）

通常情況下某個目標節點可以被多個節點同時感知到，為了提高節點對目標節點的感知概率，將目標節點被所有節點聯合感知的概率定義為：

P（Si， Kj）=1-" [1- p（Si， Kj）] （3）

則監測區域的整體覆蓋率COV為所有傳感器節點覆蓋的目標節點數與目標區域內所有目標節點數的比值，覆蓋率COV定義為：

（4）

2 標準蜣螂算法

將蜣螂分為4類具有特定功能的子種群，分別為滾球蜣螂、繁育蜣螂、小蜣螂及竊賊蜣螂。每個子群體根據各自的行為特點，扮演著不同的角色，并執行相應的位置更新策略。

2.1 滾球蜣螂

蜣螂以其獨特的習性而著稱，它們會將糞便滾成超過自身體積的球體，并將這些球體推向隱蔽的地點以儲存食物資源。在執行這一任務時，蜣螂能夠借助天文線索，如太陽光和偏振光，進行導航，確保糞球能夠沿直線前進。在模擬這一行為的過程中，蜣螂需要在搜索區域內按照既定的路徑移動，并適時調整自己的位置。位置更新的表達式定義為：

xit+1=xit+α·k·xit-1+b×Δx， Δx=|xit- xtworst| （5）

式中：t表示當前迭代的次數；xit表示第i只蜣螂在第t次迭代時的位置信息；k為偏轉系數，取值范圍為k∈（0， 0.2]；b表示（0， 1）之間的常量；α為自然系數，賦值為1或者-1；xtworst表示全局最差位置；Δx表示光照強度的變化。

當滾球蜣螂遭遇障礙物，無法沿當前方向繼續前進時，它會通過一種特殊的舞蹈行為來重新確定方向。在找到新的路徑后，它會繼續推動糞便球沿著新方向行進。位置更新的表達式定義為：

xit+1=xit+ tanθ |xit- xit-1|∣ （6）

式中：θ表示偏轉角度，取值范圍為[0， π]。當θ≠0， π/2， π時用式（6）更新位置；當θ=0， π/2， π時，不用更新滾球蜣螂的位置。

2.2 繁育蜣螂

在自然環境中，雌性蜣螂會將糞球滾至安全地點并隱藏起來，這些糞球既是食物來源，也可能成為孕育后代的場所。因此，選擇一個適宜的產卵區域對雌性蜣螂來說非常關鍵。模擬雌性蜣螂選擇產卵區域的過程，可以通過邊界選擇策略來實現，這種策略可以描述為：

（7）

式中：Lb*和Ub*分別表示產卵區域的下界和上界；xto表示當前局部的最優位置；R=1- t/Tmax，Tmax表示最大迭代次數；Lb和Ub分別表示優化問題的下界與上界。

在確定的產卵范圍內，雌蜣螂將進行產卵活動。DBO算法規定，在每輪迭代過程中，每只雌蜣螂僅產下一枚卵子。由式（7）可知，產卵區域的邊界范圍是動態變化的，因此，在迭代過程中，用于產卵的糞球位置也會隨之動態調整。繁育蜣螂的位置更新的表達式定義為：

xit+1=xot+b1·（xit-Lb*）+b2·（xit-Ub*） （8）

式中：xit為第i個產卵糞球在第t次迭代時的位置信息；b1和b2為兩個相互獨立的大小為1×d維的隨機向量；d表示優化問題的維數。

2.3 小蜣螂

成熟的蜣螂幼蟲會從糞球中爬出，開始尋找食物，這些幼蟲被稱為小蜣螂。小蜣螂的覓食范圍被限制在最優覓食區域內。最優覓食區域可以定義為：

（9）

式中：Lbbfa和Ubbfa分別為最佳覓食區域的下界和上界；xlt表示全局最優位置。因此，小蜣螂在最佳覓食區域內的位置更新表達式定義為：

xit+1=xit+C1·（xit-Lbbfa）+C2·（xit-Ubbfa） （10）

式中：xit表示第i只蜣螂在第t次迭代時的位置信息；C1為服從正態分布的隨機數；C2是（0， 1）之間的隨機向量。

2.4 竊賊蜣螂

一些蜣螂會從其他蜣螂那里奪取糞球，這些蜣螂被稱為竊賊蜣螂。竊賊蜣螂會在最優食物位置xlt附近進行掠奪。在迭代過程中，竊賊蜣螂的位置更新表達式可以定義為：

xit+1=xlt + S × g × （ |xit- xot| + |xit- xlt| ） （11）

式中：S是一個常數；g表示大小為1×d并且服從正態分布的隨機向量。

3 改進蜣螂算法

DBO算法在求解優化問題上優于許多智能優化算法，但是在一些具體的優化問題上還存在不足。因此，本文提出四個改進措施，以提高DBO算法的全局搜索能力、種群多樣性、收斂速度，保證算法在迭代后期有良好的局部搜索能力。

3.1 改進Logistic混沌映射初始化種群

蜣螂算法在求解優化問題時通常是隨機初始化種群，隨機初始化會導致種群多樣性降低，收斂速度緩慢，容易陷入局部最優。混沌映射具有隨機性的特點，可以增加種群多樣性，所以本文引入Logistic混沌映射初始化蜣螂算法種群。Logistic混沌映射中間取值比較均勻，兩邊極端值取值概率比較大，這不利于尋找最優值。而Tent混沌映射具有較好的均勻性和更快的收斂速度。結合兩個混沌映射的特點，本文提出Logistic-Tent混沌映射初始化種群，從而提高蜣螂算法的收斂速度、求解精度和種群多樣性，具體公式如下：

（12）

式中：r和α為控制因子，在本文中設置α=0.5，r=0.2，以達到最優取值效果。改進Logistic混沌映射初始化的頻數分布如圖1所示。

3.2 融合麻雀警戒機制的跳舞行為

當滾球蜣螂遇到障礙物時，會通過跳舞來確定新的前進方向，能有效地在當前解的鄰域內進行搜索，有助于細化和優化解，但是滾球蜣螂主要聚焦于當前解附近，缺乏全局視野，容易陷入局部最優；而麻雀算法警戒機制能夠引導麻雀遠離當前位置，探索新的區域，有助于全局搜索和跳出局部最優，并且能夠根據當前的環境變化（如發現捕食者）動態地調整搜索策略。麻雀警戒機制定義如下：

（13）

式中：xlt為全局最優位置；β為服從標準正態分布的隨機數；K為[0， 1]區間的隨機數；fi為當前適應度值；fg為全局最優適應度值；fw為全局最差適應度值；ε為一個非常小的正數，避免分母為0。

基于此，本文將麻雀算法警戒機制引入蜣螂算法跳舞行為，具體定義如下：

（14）

通過結合蜣螂算法的跳舞行為和麻雀算法的警戒機制改進策略，旨在充分利用兩種算法的優勢，提高全局搜索能力和良好的局部搜索能力，增強算法的靈活性和自適應性，更好地平衡探索新區域和深入挖掘當前區域的需要。結合兩種機制允許算法根據當前搜索狀態自適應地調整搜索策略。在遇到搜索障礙或是搜索進展緩慢時，算法能夠通過警戒機制進行較大范圍的探索；而在找到有前景的區域時，通過跳舞行為進行局部精細搜索。

3.3 引入量子行為的覓食行為

小蜣螂在最佳覓食區域內覓食，覓食區域前期比較大，可以在較大區域內進行全局搜索，隨著迭代的進行，覓食區域逐漸變小，小蜣螂開始局部搜索，這可能導致陷入局部最優和收斂效率低下。基于此，本文引入量子行為提高解的多樣性和并行性，通過量子概率分布實現同時考慮多個潛在解，從而提高全局搜索的效率，降低算法陷入局部最優的風險，加快收斂速度。具體公式如下：

xit+1=xit+Δxit （15）

Δxit=sin（θ（t））（x tbest - xit）+cos（θ（t））（x trand- x it） （16）

θ（t）=θmax·exp（-α） （17）

加入量子行為后，算法在迭代前期主要側重于全局搜索，通過較大的量子角度θ來探索更廣闊的解空間，提高解的多樣性和避免局部最優。隨著迭代進展到后期，覓食區域逐漸減小，算法逐漸增加對局部的搜索，通過減小θ值，加強對當前最優解附近區域的細致探索。這樣的策略使得算法在不同階段能夠自適應地調整搜索行為，有效地平衡了探索與利用，提高了算法的性能。

4 SQBDBO算法求解WSN覆蓋優化問題

在目標區域內部署若干個傳感器節點，求解最大覆蓋率。SQBDBO算法求解WSN節點覆蓋優化問題的步驟如下：

（1）參數初始化，包括目標區域范圍M×L、傳感器節點數量n、節點感知半徑Rp，以及SQBDBO算法的相關參數：種群規模為N、維度為d、最大迭代次數為Tmax。

（2）改進Logistic混沌映射初始化種群，生成蜣螂個體初始位置信息（xi， yi），開始迭代，設置迭代次數t=1。

（3）根據式（4）計算覆蓋率，進而計算適應度值fit。

（4）根據式（5）更新滾球蜣螂位置，根據式（13）與

式（14）更新跳舞蜣螂位置。

（5）" "根據式（8）更新繁育蜣螂位置，根據式（15）、式（16）和式（17）更新覓食蜣螂位置。

（6）根據式（11）更新竊賊蜣螂位置。

（7）重新計算種群適應度值fit1，若fit＜fit1，則輸出全局最優解和最優位置。更新迭代次數t=t+1。

（8）判斷迭代終止條件t≤Tmax，若滿足，則返回步驟（3），否則進行下一步。

（9）輸出WSN節點覆蓋最優方案及最優適應度值。

5 實驗仿真與結果分析

本文所有實驗都是采用以下仿真環境：Windows 10操作系統、16 GB內存、CPU為Intel? CoreTM i5-10500H @4.5 GHz、顯卡為NVIDIA GeForce RTX 1050 Laptop GPU，實驗環境為MATLAB 2020b。將本文算法應用到WSN覆蓋優化問題上，對比其他常用的算法，驗證本文改進算法的有效性。為了驗證SQBDBO算法在WSN覆蓋優化問題上的優化效果，選擇DBO算法、SSA算法[8]、IPSO算法[9]、IWOA算法[10]作為對比算法。仿真實驗具體參數見表1。

將40個節點隨機拋灑在目標區域內，通過算法優化節點部署。圖2～圖7分別為隨機部署、SSA算法、DBO算法、IPSO算法、IWOA算法和SQBDBO算法優化得到的最終部署情況。觀察圖2可知，隨機部署覆蓋率只有71.6%，存在很多的空洞區域，并且左上角、右下角存在大量節點重疊，節點利用率低；SSA算法和DBO算法的平均覆蓋率分別為86.8%和85.1%，相比初始部署，覆蓋率顯著提升，但是還有空洞區域和節點冗余；IPSO算法和IWOA算法的平均覆蓋率分別為89.2%和91.6%，覆蓋率提升幅度相比于前兩者并不大，但是空洞區域顯著減少了；而SQBDBO算法在目標區域內覆蓋率最大達到98.9%，如圖7所示，基本沒有空洞區域和節點重合的情況，節點利用率較高。

通過實驗，成功驗證了本文算法在WSN覆蓋優化問題上的有效性，不同算法的覆蓋率情況具體見表2。圖8為覆蓋率的迭代曲線，觀察圖像可知，SQBDBO算法的收斂速度和求解精度都要優于對比算法，驗證了本文改進算法的有效性。

為了驗證節點數量對覆蓋率的影響，修改節點數分別為50、60。實驗結果如圖9所示，隨著節點數增加覆蓋率也在上升，在最少的節點下達到最高的覆蓋率是檢測算法改進有效性的重要標準。SQBDBO算法在相同節點下覆蓋率最高，且只需要40個節點就能達到其他算法60個節點才能達到的覆蓋率，這證明了本文改進算法的尋優能力和求解精度較高。

6 結 語

本文提出了一種改進蜣螂算法，在原始蜣螂算法的基礎上，使用改進Logistic混沌映射初始化種群，增強了種群多樣性和全局搜索能力；在跳舞行為中引入麻雀算法警戒機制，通過警戒策略動態選擇更新策略，增強全局搜索能力的同時具有良好的局部搜索能力；在蜣螂算法覓食行為中引入量子行為，前期較大的量子角度能夠促進全局搜索，后期隨著量子角度的減小，逐步圍繞最優個體進行局部搜索，有效地平衡了全局搜索和局部搜索。將改進蜣螂算法應用到WSN覆蓋問題上，以覆蓋率為優化目標。實驗結果表明，本文的改進算法有較快的收斂速度和較高的求解精度，有效地提高了節點覆蓋率。不足的是：本文的研究主要聚焦于覆蓋率這一單一指標，并沒有考慮節點剩余能量以及節點移動距離等因素，如何在保持覆蓋率的同時提升WSN的生存時間將是下一步研究的目標。

參考文獻

[1] CHEN H， WANG X， GE B， et al. A multi-strategy improved sparrow search algorithm for coverage optimization in a WSN [J]. Sensors， 2023， 23（8）： 4124.

[2] YANG D D， MEI M， ZHU Y J， et al. Coverage optimization of WSN based on enhanced multi-objective salp swarm algorithm [J]. Applied sciences， 2023， 13（20）： 11252.

[3] SRIVASTAVA A， PAULUS R. Coverage hole aware optimal cluster based routing for wireless sensor network assisted IoT using hybrid deep recurrent neural network [J]. Concurrency and computation： Practice and experience， 2023， 35（6）： 1.

[4]李振，馮鋒.基于Halton序列WOA-GWO算法的WSN覆蓋研究[J].物聯網技術，2024，14（2）：43-47.

[5]楊樂，張達敏，何慶，等.改進獵人獵物優化算法在WSN覆蓋中的應用[J].計算機應用，2024，44（8）：2506-2513.

[6]齊薇，虞慧群，范貴生，等.基于自適應粒子群的WSN覆蓋優化[J].計算機科學，2020，47（7）：243-249.

[7] XUE J， SHEN B. Dung beetle optimizer： A new meta-heuristic algorithm for global optimization [J]. The journal of supercomputing， 2023， 79（7）： 7305-7336.

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

[9]羅鑫.基于改進粒子群算法的紅外WSN覆蓋研究[J].激光與紅外，2023，53（2）：289-295.

[10]宋婷婷，張達敏，王依柔，等.基于改進鯨魚優化算法的WSN覆蓋優化[J].傳感技術學報，2020，33（3）：415-422.