基于改進布谷鳥搜索算法的WSN覆蓋優化策略

作者簡介：李思陽（1997-），碩士研究生，從事信息物理系統與無線傳感器網絡的研究，772073406@qq.com。

引用本文：李思陽.基于改進布谷鳥搜索算法的WSN覆蓋優化策略［J］.化工自動化及儀表，2024，51（2）：215-221；300.

DOI：10.20030/j.cnki.1000-3932.202402010

摘 要 針對傳感器節點分散不均、覆蓋程度低及匯聚層Sink節點冗余等問題，設計了一種雙層無線傳感器網絡覆蓋優化方法，該方法對傳統布谷鳥搜索算法進行了改進。首先，在種群初始化過程中采用了量子位Bloch球面坐標，可以保持較高的多樣性；其次，針對布谷鳥搜索算法的Levy飛行尋優階段，改進候選解更新方法，隨機生成每個縱向維度的新候選解；最后，基于逐維更新貪婪評價策略進行隨機游動選擇。通過這些改進方式提升了布谷鳥搜索算法的迭代速度和精度，避免相同維度間的干擾。實驗結果表明，該改進算法與傳統布谷鳥搜索算法、外推人工蜂群算法相比，傳感器節點覆蓋率分別提高了1.79％和9.87％，匯聚層Sink節點冗余率降低5.13％和21.28％。

關鍵詞 雙層無線傳感器網絡 改進布谷鳥搜索算法（ICS） 量子位Bloch球面坐標 逐維更新

中圖分類號 TP29?? 文獻標志碼 A?? 文章編號 1000-3932（2024）02-0215-08

無線傳感器網絡（WSN）屬于信息物理系統（Cyber Physical Systems，CPS）［1］科研領域的重要部分，當前已成為電子與信息技術領域中新興的科研熱點，與眾多學科相互交叉，在醫療、軍事、建筑［2］以及采礦等場景中具有較高的應用價值。無線傳感器網絡在結構上劃分為多個部分，包括管理、匯聚和傳感器節點［3］。多個WSN節點在部署后通過無線通信的方式形成一個多跳自組織網絡，WSN節點負責采集和檢測被測對象的信息，并將信息轉發給Sink節點，Sink節點負責將收集到的數據處理、存儲并轉發，用戶通過管理節點獲取數據資源，以上功能實現所需的能量都由電池提供。多層WSN包含傳感器層、匯聚層和管理層。

無線傳感器通常隨機進行拋灑，因此會存在覆蓋盲點或集中覆蓋等問題，此外還存在匯聚層Sink節點大量冗余的問題。如何提高大規模的WSN節點覆蓋率，減少匯聚層Sink節點冗余，是研究大規模無線傳感器網絡急需解決的問題。采用適應度強、精度高的覆蓋優化算法能夠有效地解決這些問題。現有的方法和研究已對上述問題做了很多杰出的工作。文獻［4］針對原始人工蜂群算法存在的陷入局部最優解和收斂速度慢的問題，設計了一種改進的人工蜂群算法，此算法利用一維高斯變異法提升了網絡結構的合理性，改善了網絡壽命。文獻［5］針對原始鯨魚算法進行了研究和改進，引入量子位球面坐標進行初始化，之后加入Levy飛行，防止產生局部最優的情況。文獻［6］在傳統人工魚群算法的基礎上，加入了交叉和再尋優算子來提高搜索的精度，以解決傳統人工魚群在后期尋優處理過程中準確度不高的問題。以上覆蓋方式都可以很合理地增加覆蓋率，但在算法迭代速率、計算準確度等方面尚有待進一步改善。因此筆者引入布谷鳥搜索（Cuckoo Search，CS）算法，將布谷鳥搜索算法進行改進來解決雙層WSN覆蓋優化問題。布谷鳥搜索算法的性能在全局搜索和精確度方面明顯優于遺傳算法［7］、模擬退火算法等，對無線傳感器網絡覆蓋優化的適應程度也具有明顯的優勢。國內外學者對該算法進行了很多有效的改進并加以應用［8］，如許夢楠和陳兵提出一種按照適應度變動程度自適應調整比例因子的布谷鳥搜索算法，并將其用于車間作業調度優化［9］，該算法提高了找到最優車間作業調度方案的成功率。文獻［10］提出一種全新的具有動態發現概率和步長修正因子的布谷鳥搜索算法，優化了磁滯參數辨識模型和磁流變阻尼器的均方根誤差。

筆者針對CS算法存在的收斂過早、迭代慢和精度不高的問題進行了研究，提出了有效的解決策略。首先，在種群初始化時利用量子位Bloch球面坐標［11］，通過這種方式可避免種群過于單一的情況；其次，針對布谷鳥搜索算法的Levy飛行尋優階段，改進候選解更新方法，隨機生成每個縱向維度的新候選解；最后，采用逐維更新貪婪評價策略［12］來提升CS算法的迭代速度和精度，避免相同維度間的干擾。在相同環境下進行雙層無線傳感器網絡覆蓋優化時，傳感器節點覆蓋率明顯提升，在達到相同覆蓋率時，使用該算法優化后的匯聚層Sink節點冗余較少。

1 WSN覆蓋模型

1.1 0/1模型及覆蓋率

依據相關文獻，本研究中的WSN節點模型采用0/1模型［13］。將傳感器節點的目標監測區域設置為二維平面，并且將二維平面離散化為L×M的網格，每個網格大小都是1。在二維平面區域Area上，部署N個完全相同的WSN節點，WSN節點集表示為：

Node={Node，Node，…，Node} （1）

將WSN節點的感知半徑和通信半徑分別設置為R和R，且R≤2R，其中Node定義如下：

Node=（x，y，R）（2）

其中，（x，y）、（x，y）分別代表WSN節點和p點的坐標，二者之間的歐氏距離表示為：

d（Node，p）=（3）

目標節點被WSN節點覆蓋的概率P為：

P（x，y，Node）=1，d（Node，p）≤R0，otherwise（4）

所有WSN節點Node在二維平面區域Area上的覆蓋率定義為WSN節點的覆蓋率與總面積的比R，計算式為：

R（Node）=（5）

筆者以式（5）為區域覆蓋率的適應度函數進行優化。

1.2 匯聚層Sink節點覆蓋

匯聚層Sink節點［14］用于傳感器節點之間的信息管理和信息傳輸。根據匯聚層Sink節點的工作特點，將傳感器節點作為目標節點進行覆蓋，靜態部署N個傳感器節點，形成固定的監控區域。Sink節點占通率R定義為在傳感器數量N不變的環境下，相互連通的Sink節點數目與目標傳感器之間的比例，即：

R=［P（P（d（Node，Node）≤R）＞0）］/N（6）

R值越高表示目標越分散，需要的Sink節點數目越多；反之，表示Sink節點部署合理，使用較少的Sink節點就能達到覆蓋要求。

2 傳統布谷鳥搜索算法

CS算法是根據布谷鳥的寄生和雛育行為而提出的元啟發式算法。布谷鳥的寄生雛育行為與眾不同，它們將蛋放于其他鳥的鳥巢中，通過寄主的蛋來增加自己的蛋孵化成功的概率，小布谷鳥通過發出比其他幼鳥更加響亮的叫聲來獲取更多的食物，從而增加存活的概率。CS算法遵循以下3個規則：

a. 每只布谷鳥只孵化一次卵，隨機挑選一個宿主的鳥巢存放；

b. 隨機地選擇一個鳥巢存放后，最優的宿主鳥巢更新保存；

c. 每次可選的宿主鳥巢數量都一定，一個宿主找到布谷鳥蛋的概率是Pa。

基于上述3個規則，候選解由鳥巢表示，將CS的基本流程劃分為3個部分，如圖1所示。

首先，種群初始化以后每個D維向量都可以表示一個巢，計算出所有種群個體的適應度數值，根據適應度數值選出候選解；基于以上步驟得出候選解后，使用蒙特卡洛方法通過模擬Levy飛行，在隨機游動過程中得到最新候選解；再通過貪婪選擇評價來保存最優解。假設CS在第r次迭代時的第m個候選解為X：

X=（x，x，…，x，…，x），j∈［1，D］（7）

之后，通過隨機游動來產生新的候選解

X：

圖1 布谷鳥搜索算法流程

X=X+（X-X）·（γ？茚L（β））（8）

其中，X是當前的全局最優解；γ是初始搜索步長；L（β）是Levy飛行隨機游動的路徑，具體可以定義為：

L（β）～（9）

其中，u、v為服從標準高斯分布的隨機數；β為常數1.5；？準可表示為：

？準＝（10）

其中，τ（）為伽馬函數。

最后，根據P舍棄部分候選解的同時根據隨機游動產生新的解來補缺，該過程表示為：

X=X+σ·（X-X）（11）

其中，σ是算法控制縮放的系數，σ∈［0，1］；X和X分別是第r次迭代時第k個和第s個隨機候選解。

更新并保留優秀的解進入下一次迭代，直到符合收斂要求，停止算法迭代。

3 算法改進

3.1 引入量子位Bloch球面坐標

傳統算法初始化種群為隨機初始化，為了加快收斂速度，提高解的精度，加入量子位Bloch球面坐標，擴展搜索空間和種群多樣性。在量子統計中，量子位屬于最小的單元，其狀態可以表示為：

|φ＞=cos（θ/2）|0＞+esin（θ/2）|1＞（12）

其中，0≤θ≤π，0≤δ≤2π，這兩者能夠唯一確定球面上一點ρ的坐標，量子位Bloch球面如圖2所示。

圖2 Bloch球面坐標圖

圖2中：

|φ＞=［cos φsin θ ？搖 sin φcos θ？搖? cos θ］（13）

每個量子位坐標式都可以通過式（13）表示，再將量子位坐標進行劃分。

在CS中，對每個布谷鳥個體都使用球面坐標進行編碼，設N為種群中的第i個候選解，則編碼為：

N=cos φsin θsin φsin θ?? cos θ…cos φsin θsin φsin θ?? cos θ（14）

其中，n代表搜索空間維數；φ=2π×rand，θ=π×rand，rand代表隨機數，取值在［0，1］之間；i=1，2，…，m，m代表種群大小。

在量子位Bloch球面內的Bloch坐標有3個，各個坐標包括3個解，因此可以得到各個布谷鳥個體覆蓋優化的解分別對應著x、y、z解，具體如下：

ρ=（cos φsin θ，…，cos φsin θ）ρ=（sin φsin θ，…，sin φsin θ）ρ=（cos θ，cos θ，…，cos θ）（15）

考慮到連續優化的問題，把每個布谷鳥個體中的3個解從單位空間映射到覆蓋優化的解空間中去。布谷鳥個體N上的第j個量子位Bloch球面坐標為［x，y，z］，其解空間表示為：

X=0.5［b（1+x）+a（1-x）］（16）

X=0.5［b（1+y）+a（1-y）］（17）

X=0.5［b（1+z）+a（1-z）］（18）

其中，i=1，2，…，m；j=1，2，…，n；［a，b］是第j個量子位的范圍。

3.2 改進Levy尋優

在Levy尋優過程中，傳統布谷鳥搜索算法根據適應度函數值從X中選出最優解X，再與

X相減。改進后的布谷鳥搜索算法中的X不再根據適應度值選出，而是將X劃分為30個1×80維的矩陣，其中每一個1×80維矩陣中隨機的兩個縱向維度的值相減得到相應數量的1×80維矩陣，再將這些矩陣重新組合得到X。新得到的X有很強的隨機性，這樣就大幅提升了尋優過程的可能性，獲得解的精度也就更高，式（8）可變為：

X=X+（X-X）·（γ？茚L（β））（19）

3.3 采用逐維更新評價策略

在傳統布谷鳥搜索算法中，盡管隨機游動可以提高全局搜索能力和種群的多樣性，但由于在覆蓋優化實驗中維度較高，傳統算法用于高維度優化，對整個候選解群采用更新評價策略會影響收斂速度和解的精度。加入逐維更新評價策略可以解決這些問題，并避免相同維度之間的干擾。

在隨機游動的過程中加入逐維更新評價策略，分別考慮各個維度候選解的更新，當某一個維度的解更新后，將這個解與其他維度的解組合起來得到一個新的解，采用貪婪策略評價這個新的解，只有當這個解被優化達到最優才被保留，否則放棄當前維度的解，進行下一維度的更新。考慮到在隨機游動中的步長，γ更新方法是根據隨機解進行更新的，不利于局部搜索，因為式（11）中控制縮放的系數σ的范圍為［0，1］，限制影響了搜索的方向，將σ的可取值范圍調整為

［-1，1］，使單向搜索變為雙向搜索，則式（11）可變為：

X=X+σ·（X-X）（20）

3.4 總體改進

首先，在種群初始化階段加入量子Bloch球面坐標進行初始化，將每個布谷鳥個體映射為3個候選解坐標，擴展了搜索空間和種群多樣性；之后，在Levy飛行尋優過程中，改變其更新方式，由原來的選取最優候選解變為隨機生成候選解，擴展尋優的可能性；最后，在隨機游動過程中加入逐維更新評價策略，將各個維度的解與其他維度的解組合得出新的解，再使用貪婪評價策略對新解進行評價，如果達到最優就保留當前解，否則進行下一維度的更新，加快了迭代速度，提升了解的精度。改進后的算法流程如圖3所示。

圖3 ICS流程

ICS流程的具體說明如下：

a. 利用量子球面坐標進行初始化，單個個體將生成3個解，例如布谷鳥個體N上第j個量子位Bloch球面坐標為［x，y，z］T，計算每個個體的適應度值。

b. 每個鳥巢產生新的解后，與舊解進行比較，更新當前鳥巢的位置。

c. 在Levy飛行尋優階段，選出新的候選解，選出的新解不再根據適應度值生成，而是根據隨機兩個縱向維度生成一個新的X，再根據X生成新解，根據發現概率P保留或舍棄。

d. 進行逐維更新，貪婪評價；對解的每一個維度進行貪婪選擇，判斷新解是否優于舊解，若優于舊解則更新，反之則舍棄并開始下一維度的比較。

e. 保留最優解，直到滿足收斂條件時返回最優解。

4 實驗設計與分析

4.1 實驗環境

為了驗證筆者提出的改進布谷鳥搜索算法在雙層無線傳感器網絡覆蓋優化中的性能，將ICS、CS和外推人工蜂群算法（EABC）進行對比實驗。實驗在MATLAB平臺進行仿真，實驗環境的詳細參數見表1，實驗在100 m×100 m的平面區域進行。為了滿足R≤2R的條件，設感知半徑R為

10 m，通信半徑R為20 m，考慮到在匯聚層Sink節點覆蓋實驗中Sink節點數量會變化，動態設置匯聚層Sink節點個數為0～100個，迭代次數設為400次。

表1 實驗環境參數

4.2 算法關鍵參數

為了使改進布谷鳥搜索算法、傳統布谷鳥搜索算法和外推人工蜂群算法［15］更好地適用于無線傳感器網絡覆蓋優化，對以上算法設定相對應的適用于覆蓋優化的參數，不同算法的詳細參數見表2。

4.3 傳感器節點覆蓋優化對比與分析

在上述實驗環境下，部署35個傳感器節點，在面積為100 m×100 m的平面區域里對目標節點進行覆蓋優化，進行400次迭代后3種算法的迭代曲線如圖4所示。

圖4 算法覆蓋率對比曲線

分析圖4可知，測試環境相同的情況下，ICS的網絡覆蓋率可以達到87.95％，相較于CS算法與EABC算法，網絡覆蓋率分別提高了1.79％和9.87％，覆蓋率得到了很大程度的提升。在迭代速度上ICS也有明顯的優勢，迭代到網絡覆蓋率為82.74％時，ICS與CS分別迭代了88次和147次，而EABC則更差，在第122次迭代時就陷入了局部最優。由此可以表明，ICS無論是在精度還是迭代速度上相較于其他兩種算法具有明顯的優勢。

為了更直觀地表現傳感器節點的分布情況，采用分布圖進行詳細比較，如圖5～8所示。

由圖5可以直觀地看出，初始部署的傳感器節點分布極為不均勻且重復覆蓋較多，有大面積空白區域沒有被覆蓋到。

圖5 初始部署分布圖

圖6 EABC優化部署分布圖

由圖6可直觀地看出，經過EABC優化后，部署情況有明顯地改變，空白區域變少，重復覆蓋區域也少了許多，優化有一定的效果。

圖7 CS優化部署分布圖

由圖7可直觀地看出，經過CS優化后，部署分布已經十分均勻，空白區域相較EABC優化后更少，重復覆蓋區域也更少，優化效果明顯。

圖8 ICS優化部署分布圖

由圖8可直觀地看出，經過ICS優化后，部署分布更加均勻，幾乎已經完全覆蓋，重復覆蓋區域也更少，優化效果最佳。

4.4 Sink節點覆蓋優化對比與分析

為了測試匯聚層Sink節點覆蓋WSN節點的程度，減少匯聚層Sink節點冗余，靜態部署好

1 000個傳感器節點作為目標節點，形成固定監控區域，再用匯聚層Sink節點去覆蓋傳感器節點，在達到一定要求覆蓋率的情況下，對比3種算法優化后所需要的匯聚層Sink節點數目，3種算法優化覆蓋的對比如圖9所示。

圖9 Sink節點變化曲線

由圖9可知，ICS算法達到90％覆蓋率時只用到了37個匯聚層Sink節點，而CS與EABC算法分別用了39個和47個。結果表明，用ICS算法進行覆蓋優化后很大程度減少了匯聚層Sink節點冗余，降低了部署匯聚層Sink節點的成本。

5 結束語

筆者針對傳感器節點分散不均、覆蓋程度低及匯聚層Sink節點冗余等問題，改進了傳統的布谷鳥搜索算法。通過引入量子位Bloch球面坐標、改進尋優過程以及加入逐維更新策略的方法對算法進行改進，經過改進的算法在迭代速度和精度方面有很大程度的提升。

在無線傳感器網絡相關問題的研究中，覆蓋優化問題僅是關鍵問題之一，要想整體提升網絡生命周期需要考慮多個問題。在接下來的研究中，將能耗優化與覆蓋優化相結合用以提升整個網絡的生命周期可以作為一個研究方向，此外還可以向三維覆蓋方向進一步研究。

參 考 文 獻

［1］ ZHANG J H，ZHU Y，XIAO F X.Modelling and analysis of real-time and reliability for WSN-based CPS［J］.International Journal of Internet Protocol Technology，2019，12（2）：76-84.

［2］?? BENALIA N E-H，MOHAND I S H，FERHATTALEB S，et al.MoEA-DeployWSN-SB：Three variants of multi-objective evolutionary algorithms for the deployment optimization strategy of a WSN in a smart building［J］.International Journal of Information Technology，2022，14（1）：333-344.

［3］?? HAO P，CAN L，DANDAN Z，et al.Security Evaluation under Different Exchange Strategies Based on Heterogeneous CPS Model in Interdependent Sensor Networks［J］.Sensors，2020，20（21）：6123.

［4］?? 陳蘭，王聯國.極值個體引導的人工蜂群算法［J］.計算機科學與探索，2021，16（11）：2628-2641.

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

［6］?? 李志武.人工魚群算法的改進及在無線傳感器網絡覆蓋優化的應用［D］.長沙：湖南大學，2012.

［7］?? 金合麗，劉半藤，陳唯，等.基于遺傳算法的水下傳感器網絡節點部署算法研究［J］.傳感技術學報，2019，

32（7）：1083-1087.

［8］?? LIU P，ZHANG S J.A Novel Cuckoo Search Algorithm and Its Application［J］.Scientific Journal of Intelligent Systems Research，2021，11（9）：1071-1081.

［9］?? 許夢楠，陳兵.改進布谷鳥搜索算法的車間作業調度優化研究［J］.小型微型計算機系統，2021，42（9）：1826-1829.

［10］?? ROSLI R，ZAMRI M.Optimization of modified Bouc-Wen model for magnetorheological damper using modified cuckoo search algorithm［J］.Journal of Vibration and Control，2021，27（17-18）：1956-1967.

［11］?? 李勝，張培林，李兵，等.漸近式Bloch球面搜索的量子遺傳算法及其應用［J］.系統工程理論與實踐，2016，36（4）：1042-1046.

［12］?? 張津源，張軍，季偉東，等.具備自糾正和逐維學習能力的粒子群算法［J］.小型微型計算機系統，2021，

42（5）：919-926.

［13］?? 張微微，楊海寧.改進人工魚群算法的無線傳感器網絡節點覆蓋優化［J］.電子技術與軟件工程，2020（12）：24-25.

［14］? ASHOK A K， PATIL B M.Systematic analysis and review of path optimization techniques in WSN with mobile sink［J］.Computer Science Review，2021，41.DOI：10.1016/J.COSREV.2021.100412.

［15］?? 杜振鑫，劉廣鐘，韓德志，等.基于全局無偏搜索策略的精英人工蜂群算法［J］.電子學報，2018，46（2）：

308-314.

（收稿日期：2023-04-03，修回日期：2024-02-01）

Optimization of Double-layer Wireless Sensor Networks Coverage

Based on Improved Cuckoo Search

LI Si-yang

（Faculty of Information Engineering and Automation， Kunming University of Science and Technology）

Abstract?? Aiming at the? uneven coverage of sensor nodes and redundancy of Sink nodes in the aggregation layer，? the optimization method for two-tier wireless sensor networks coverage? based on improved cuckoo search（ICS）was proposed. Firstly， having quantum-bits Bloch spherical coordinates adopted in population? initialization to expand? search space and population diversity； secondly， in the Levy flight optimization stage of cuckoo search， having the method of updating candidate solutions improved to randomly generate new candidate solutions in each longitudinal dimension； finally， having strategy of updating the greedy evaluation dimension by dimension based? to select? random walk? so as to avoid interference? of? the same dimension， speed up iteration speed and improve? accuracy. Experimental results show that， compared with the original cuckoo algorithm and extrapolated artificial bee colony（EABC）， the sensor node coverage can be improved by 1.79% and 9.87%， and Sink node redundancy in the aggregation layer is reduced by 5.13% and 21.28%.

Key words?? double-layer wireless sensor networks， ICS algorithm， quantum-bits Bloch spherical coordinates， updating dimension by dimension