作者簡(jiǎn)介：李思陽(yáng)（1997-），碩士研究生，從事信息物理系統(tǒng)與無(wú)線傳感器網(wǎng)絡(luò)的研究，772073406@qq.com。

引用本文：李思陽(yáng).基于改進(jìn)布谷鳥(niǎo)搜索算法的WSN覆蓋優(yōu)化策略［J］.化工自動(dòng)化及儀表，2024，51（2）：215-221；300.

DOI：10.20030/j.cnki.1000-3932.202402010

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

關(guān)鍵詞 雙層無(wú)線傳感器網(wǎng)絡(luò) 改進(jìn)布谷鳥(niǎo)搜索算法（ICS） 量子位Bloch球面坐標(biāo) 逐維更新

中圖分類號(hào) TP29?? 文獻(xiàn)標(biāo)志碼 A?? 文章編號(hào) 1000-3932（2024）02-0215-08

無(wú)線傳感器網(wǎng)絡(luò)（WSN）屬于信息物理系統(tǒng)（Cyber Physical Systems，CPS）［1］科研領(lǐng)域的重要部分，當(dāng)前已成為電子與信息技術(shù)領(lǐng)域中新興的科研熱點(diǎn)，與眾多學(xué)科相互交叉，在醫(yī)療、軍事、建筑［2］以及采礦等場(chǎng)景中具有較高的應(yīng)用價(jià)值。無(wú)線傳感器網(wǎng)絡(luò)在結(jié)構(gòu)上劃分為多個(gè)部分，包括管理、匯聚和傳感器節(jié)點(diǎn)［3］。多個(gè)WSN節(jié)點(diǎn)在部署后通過(guò)無(wú)線通信的方式形成一個(gè)多跳自組織網(wǎng)絡(luò)，WSN節(jié)點(diǎn)負(fù)責(zé)采集和檢測(cè)被測(cè)對(duì)象的信息，并將信息轉(zhuǎn)發(fā)給Sink節(jié)點(diǎn)，Sink節(jié)點(diǎn)負(fù)責(zé)將收集到的數(shù)據(jù)處理、存儲(chǔ)并轉(zhuǎn)發(fā)，用戶通過(guò)管理節(jié)點(diǎn)獲取數(shù)據(jù)資源，以上功能實(shí)現(xiàn)所需的能量都由電池提供。多層WSN包含傳感器層、匯聚層和管理層。

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

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

1 WSN覆蓋模型

1.1 0/1模型及覆蓋率

依據(jù)相關(guān)文獻(xiàn)，本研究中的WSN節(jié)點(diǎn)模型采用0/1模型［13］。將傳感器節(jié)點(diǎn)的目標(biāo)監(jiān)測(cè)區(qū)域設(shè)置為二維平面，并且將二維平面離散化為L(zhǎng)×M的網(wǎng)格，每個(gè)網(wǎng)格大小都是1。在二維平面區(qū)域Area上，部署N個(gè)完全相同的WSN節(jié)點(diǎn)，WSN節(jié)點(diǎn)集表示為：

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

將WSN節(jié)點(diǎn)的感知半徑和通信半徑分別設(shè)置為R和R，且R≤2R，其中Node定義如下：

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

其中，（x，y）、（x，y）分別代表WSN節(jié)點(diǎn)和p點(diǎn)的坐標(biāo)，二者之間的歐氏距離表示為：

d（Node，p）=（3）

目標(biāo)節(jié)點(diǎn)被WSN節(jié)點(diǎn)覆蓋的概率P為：

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

所有WSN節(jié)點(diǎn)Node在二維平面區(qū)域Area上的覆蓋率定義為WSN節(jié)點(diǎn)的覆蓋率與總面積的比R，計(jì)算式為：

R（Node）=（5）

筆者以式（5）為區(qū)域覆蓋率的適應(yīng)度函數(shù)進(jìn)行優(yōu)化。

1.2 匯聚層Sink節(jié)點(diǎn)覆蓋

匯聚層Sink節(jié)點(diǎn)［14］用于傳感器節(jié)點(diǎn)之間的信息管理和信息傳輸。根據(jù)匯聚層Sink節(jié)點(diǎn)的工作特點(diǎn)，將傳感器節(jié)點(diǎn)作為目標(biāo)節(jié)點(diǎn)進(jìn)行覆蓋，靜態(tài)部署N個(gè)傳感器節(jié)點(diǎn)，形成固定的監(jiān)控區(qū)域。Sink節(jié)點(diǎn)占通率R定義為在傳感器數(shù)量N不變的環(huán)境下，相互連通的Sink節(jié)點(diǎn)數(shù)目與目標(biāo)傳感器之間的比例，即：

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

R值越高表示目標(biāo)越分散，需要的Sink節(jié)點(diǎn)數(shù)目越多；反之，表示Sink節(jié)點(diǎn)部署合理，使用較少的Sink節(jié)點(diǎn)就能達(dá)到覆蓋要求。

2 傳統(tǒng)布谷鳥(niǎo)搜索算法

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

a. 每只布谷鳥(niǎo)只孵化一次卵，隨機(jī)挑選一個(gè)宿主的鳥(niǎo)巢存放；

b. 隨機(jī)地選擇一個(gè)鳥(niǎo)巢存放后，最優(yōu)的宿主鳥(niǎo)巢更新保存；

c. 每次可選的宿主鳥(niǎo)巢數(shù)量都一定，一個(gè)宿主找到布谷鳥(niǎo)蛋的概率是Pa。

基于上述3個(gè)規(guī)則，候選解由鳥(niǎo)巢表示，將CS的基本流程劃分為3個(gè)部分，如圖1所示。

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

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

之后，通過(guò)隨機(jī)游動(dòng)來(lái)產(chǎn)生新的候選解

X：

圖1 布谷鳥(niǎo)搜索算法流程

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

其中，X是當(dāng)前的全局最優(yōu)解；γ是初始搜索步長(zhǎng)；L（β）是Levy飛行隨機(jī)游動(dòng)的路徑，具體可以定義為：

L（β）～（9）

其中，u、v為服從標(biāo)準(zhǔn)高斯分布的隨機(jī)數(shù)；β為常數(shù)1.5；？準(zhǔn)可表示為：

？準(zhǔn)＝（10）

其中，τ（）為伽馬函數(shù)。

最后，根據(jù)P舍棄部分候選解的同時(shí)根據(jù)隨機(jī)游動(dòng)產(chǎn)生新的解來(lái)補(bǔ)缺，該過(guò)程表示為：

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

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

更新并保留優(yōu)秀的解進(jìn)入下一次迭代，直到符合收斂要求，停止算法迭代。

3 算法改進(jìn)

3.1 引入量子位Bloch球面坐標(biāo)

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

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

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

圖2 Bloch球面坐標(biāo)圖

圖2中：

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

每個(gè)量子位坐標(biāo)式都可以通過(guò)式（13）表示，再將量子位坐標(biāo)進(jìn)行劃分。

在CS中，對(duì)每個(gè)布谷鳥(niǎo)個(gè)體都使用球面坐標(biāo)進(jìn)行編碼，設(shè)N為種群中的第i個(gè)候選解，則編碼為：

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

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

在量子位Bloch球面內(nèi)的Bloch坐標(biāo)有3個(gè)，各個(gè)坐標(biāo)包括3個(gè)解，因此可以得到各個(gè)布谷鳥(niǎo)個(gè)體覆蓋優(yōu)化的解分別對(duì)應(yīng)著x、y、z解，具體如下：

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

考慮到連續(xù)優(yōu)化的問(wèn)題，把每個(gè)布谷鳥(niǎo)個(gè)體中的3個(gè)解從單位空間映射到覆蓋優(yōu)化的解空間中去。布谷鳥(niǎo)個(gè)體N上的第j個(gè)量子位Bloch球面坐標(biāo)為［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個(gè)量子位的范圍。

3.2 改進(jìn)Levy尋優(yōu)

在Levy尋優(yōu)過(guò)程中，傳統(tǒng)布谷鳥(niǎo)搜索算法根據(jù)適應(yīng)度函數(shù)值從X中選出最優(yōu)解X，再與

X相減。改進(jìn)后的布谷鳥(niǎo)搜索算法中的X不再根據(jù)適應(yīng)度值選出，而是將X劃分為30個(gè)1×80維的矩陣，其中每一個(gè)1×80維矩陣中隨機(jī)的兩個(gè)縱向維度的值相減得到相應(yīng)數(shù)量的1×80維矩陣，再將這些矩陣重新組合得到X。新得到的X有很強(qiáng)的隨機(jī)性，這樣就大幅提升了尋優(yōu)過(guò)程的可能性，獲得解的精度也就更高，式（8）可變?yōu)椋?/p>

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

3.3 采用逐維更新評(píng)價(jià)策略

在傳統(tǒng)布谷鳥(niǎo)搜索算法中，盡管隨機(jī)游動(dòng)可以提高全局搜索能力和種群的多樣性，但由于在覆蓋優(yōu)化實(shí)驗(yàn)中維度較高，傳統(tǒng)算法用于高維度優(yōu)化，對(duì)整個(gè)候選解群采用更新評(píng)價(jià)策略會(huì)影響收斂速度和解的精度。加入逐維更新評(píng)價(jià)策略可以解決這些問(wèn)題，并避免相同維度之間的干擾。

在隨機(jī)游動(dòng)的過(guò)程中加入逐維更新評(píng)價(jià)策略，分別考慮各個(gè)維度候選解的更新，當(dāng)某一個(gè)維度的解更新后，將這個(gè)解與其他維度的解組合起來(lái)得到一個(gè)新的解，采用貪婪策略評(píng)價(jià)這個(gè)新的解，只有當(dāng)這個(gè)解被優(yōu)化達(dá)到最優(yōu)才被保留，否則放棄當(dāng)前維度的解，進(jìn)行下一維度的更新。考慮到在隨機(jī)游動(dòng)中的步長(zhǎng)，γ更新方法是根據(jù)隨機(jī)解進(jìn)行更新的，不利于局部搜索，因?yàn)槭剑?1）中控制縮放的系數(shù)σ的范圍為［0，1］，限制影響了搜索的方向，將σ的可取值范圍調(diào)整為

［-1，1］，使單向搜索變?yōu)殡p向搜索，則式（11）可變?yōu)椋?/p>

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

3.4 總體改進(jìn)

首先，在種群初始化階段加入量子Bloch球面坐標(biāo)進(jìn)行初始化，將每個(gè)布谷鳥(niǎo)個(gè)體映射為3個(gè)候選解坐標(biāo)，擴(kuò)展了搜索空間和種群多樣性；之后，在Levy飛行尋優(yōu)過(guò)程中，改變其更新方式，由原來(lái)的選取最優(yōu)候選解變?yōu)殡S機(jī)生成候選解，擴(kuò)展尋優(yōu)的可能性；最后，在隨機(jī)游動(dòng)過(guò)程中加入逐維更新評(píng)價(jià)策略，將各個(gè)維度的解與其他維度的解組合得出新的解，再使用貪婪評(píng)價(jià)策略對(duì)新解進(jìn)行評(píng)價(jià)，如果達(dá)到最優(yōu)就保留當(dāng)前解，否則進(jìn)行下一維度的更新，加快了迭代速度，提升了解的精度。改進(jìn)后的算法流程如圖3所示。

圖3 ICS流程

ICS流程的具體說(shuō)明如下：

a. 利用量子球面坐標(biāo)進(jìn)行初始化，單個(gè)個(gè)體將生成3個(gè)解，例如布谷鳥(niǎo)個(gè)體N上第j個(gè)量子位Bloch球面坐標(biāo)為［x，y，z］T，計(jì)算每個(gè)個(gè)體的適應(yīng)度值。

b. 每個(gè)鳥(niǎo)巢產(chǎn)生新的解后，與舊解進(jìn)行比較，更新當(dāng)前鳥(niǎo)巢的位置。

c. 在Levy飛行尋優(yōu)階段，選出新的候選解，選出的新解不再根據(jù)適應(yīng)度值生成，而是根據(jù)隨機(jī)兩個(gè)縱向維度生成一個(gè)新的X，再根據(jù)X生成新解，根據(jù)發(fā)現(xiàn)概率P保留或舍棄。

d. 進(jìn)行逐維更新，貪婪評(píng)價(jià)；對(duì)解的每一個(gè)維度進(jìn)行貪婪選擇，判斷新解是否優(yōu)于舊解，若優(yōu)于舊解則更新，反之則舍棄并開(kāi)始下一維度的比較。

e. 保留最優(yōu)解，直到滿足收斂條件時(shí)返回最優(yōu)解。

4 實(shí)驗(yàn)設(shè)計(jì)與分析

4.1 實(shí)驗(yàn)環(huán)境

為了驗(yàn)證筆者提出的改進(jìn)布谷鳥(niǎo)搜索算法在雙層無(wú)線傳感器網(wǎng)絡(luò)覆蓋優(yōu)化中的性能，將ICS、CS和外推人工蜂群算法（EABC）進(jìn)行對(duì)比實(shí)驗(yàn)。實(shí)驗(yàn)在MATLAB平臺(tái)進(jìn)行仿真，實(shí)驗(yàn)環(huán)境的詳細(xì)參數(shù)見(jiàn)表1，實(shí)驗(yàn)在100 m×100 m的平面區(qū)域進(jìn)行。為了滿足R≤2R的條件，設(shè)感知半徑R為

10 m，通信半徑R為20 m，考慮到在匯聚層Sink節(jié)點(diǎn)覆蓋實(shí)驗(yàn)中Sink節(jié)點(diǎn)數(shù)量會(huì)變化，動(dòng)態(tài)設(shè)置匯聚層Sink節(jié)點(diǎn)個(gè)數(shù)為0～100個(gè)，迭代次數(shù)設(shè)為400次。

表1 實(shí)驗(yàn)環(huán)境參數(shù)

4.2 算法關(guān)鍵參數(shù)

為了使改進(jìn)布谷鳥(niǎo)搜索算法、傳統(tǒng)布谷鳥(niǎo)搜索算法和外推人工蜂群算法［15］更好地適用于無(wú)線傳感器網(wǎng)絡(luò)覆蓋優(yōu)化，對(duì)以上算法設(shè)定相對(duì)應(yīng)的適用于覆蓋優(yōu)化的參數(shù)，不同算法的詳細(xì)參數(shù)見(jiàn)表2。

4.3 傳感器節(jié)點(diǎn)覆蓋優(yōu)化對(duì)比與分析

在上述實(shí)驗(yàn)環(huán)境下，部署35個(gè)傳感器節(jié)點(diǎn)，在面積為100 m×100 m的平面區(qū)域里對(duì)目標(biāo)節(jié)點(diǎn)進(jìn)行覆蓋優(yōu)化，進(jìn)行400次迭代后3種算法的迭代曲線如圖4所示。

圖4 算法覆蓋率對(duì)比曲線

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

為了更直觀地表現(xiàn)傳感器節(jié)點(diǎn)的分布情況，采用分布圖進(jìn)行詳細(xì)比較，如圖5～8所示。

由圖5可以直觀地看出，初始部署的傳感器節(jié)點(diǎn)分布極為不均勻且重復(fù)覆蓋較多，有大面積空白區(qū)域沒(méi)有被覆蓋到。

圖5 初始部署分布圖

圖6 EABC優(yōu)化部署分布圖

由圖6可直觀地看出，經(jīng)過(guò)EABC優(yōu)化后，部署情況有明顯地改變，空白區(qū)域變少，重復(fù)覆蓋區(qū)域也少了許多，優(yōu)化有一定的效果。

圖7 CS優(yōu)化部署分布圖

由圖7可直觀地看出，經(jīng)過(guò)CS優(yōu)化后，部署分布已經(jīng)十分均勻，空白區(qū)域相較EABC優(yōu)化后更少，重復(fù)覆蓋區(qū)域也更少，優(yōu)化效果明顯。

圖8 ICS優(yōu)化部署分布圖

由圖8可直觀地看出，經(jīng)過(guò)ICS優(yōu)化后，部署分布更加均勻，幾乎已經(jīng)完全覆蓋，重復(fù)覆蓋區(qū)域也更少，優(yōu)化效果最佳。

4.4 Sink節(jié)點(diǎn)覆蓋優(yōu)化對(duì)比與分析

為了測(cè)試匯聚層Sink節(jié)點(diǎn)覆蓋WSN節(jié)點(diǎn)的程度，減少匯聚層Sink節(jié)點(diǎn)冗余，靜態(tài)部署好

1 000個(gè)傳感器節(jié)點(diǎn)作為目標(biāo)節(jié)點(diǎn)，形成固定監(jiān)控區(qū)域，再用匯聚層Sink節(jié)點(diǎn)去覆蓋傳感器節(jié)點(diǎn)，在達(dá)到一定要求覆蓋率的情況下，對(duì)比3種算法優(yōu)化后所需要的匯聚層Sink節(jié)點(diǎn)數(shù)目，3種算法優(yōu)化覆蓋的對(duì)比如圖9所示。

圖9 Sink節(jié)點(diǎn)變化曲線

由圖9可知，ICS算法達(dá)到90％覆蓋率時(shí)只用到了37個(gè)匯聚層Sink節(jié)點(diǎn)，而CS與EABC算法分別用了39個(gè)和47個(gè)。結(jié)果表明，用ICS算法進(jìn)行覆蓋優(yōu)化后很大程度減少了匯聚層Sink節(jié)點(diǎn)冗余，降低了部署匯聚層Sink節(jié)點(diǎn)的成本。

5 結(jié)束語(yǔ)

筆者針對(duì)傳感器節(jié)點(diǎn)分散不均、覆蓋程度低及匯聚層Sink節(jié)點(diǎn)冗余等問(wèn)題，改進(jìn)了傳統(tǒng)的布谷鳥(niǎo)搜索算法。通過(guò)引入量子位Bloch球面坐標(biāo)、改進(jìn)尋優(yōu)過(guò)程以及加入逐維更新策略的方法對(duì)算法進(jìn)行改進(jìn)，經(jīng)過(guò)改進(jìn)的算法在迭代速度和精度方面有很大程度的提升。

在無(wú)線傳感器網(wǎng)絡(luò)相關(guān)問(wèn)題的研究中，覆蓋優(yōu)化問(wèn)題僅是關(guān)鍵問(wèn)題之一，要想整體提升網(wǎng)絡(luò)生命周期需要考慮多個(gè)問(wèn)題。在接下來(lái)的研究中，將能耗優(yōu)化與覆蓋優(yōu)化相結(jié)合用以提升整個(gè)網(wǎng)絡(luò)的生命周期可以作為一個(gè)研究方向，此外還可以向三維覆蓋方向進(jìn)一步研究。

參 考 文 獻(xiàn)

［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，F(xiàn)ERHATTALEB 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］?? 陳蘭，王聯(lián)國(guó).極值個(gè)體引導(dǎo)的人工蜂群算法［J］.計(jì)算機(jī)科學(xué)與探索，2021，16（11）：2628-2641.

［5］?? 宋婷婷，張達(dá)敏，王依柔，等.基于改進(jìn)鯨魚(yú)優(yōu)化算法的WSN覆蓋優(yōu)化［J］.傳感技術(shù)學(xué)報(bào)，2020，33（3）：415-422.

［6］?? 李志武.人工魚(yú)群算法的改進(jìn)及在無(wú)線傳感器網(wǎng)絡(luò)覆蓋優(yōu)化的應(yīng)用［D］.長(zhǎng)沙：湖南大學(xué)，2012.

［7］?? 金合麗，劉半藤，陳唯，等.基于遺傳算法的水下傳感器網(wǎng)絡(luò)節(jié)點(diǎn)部署算法研究［J］.傳感技術(shù)學(xué)報(bào)，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］?? 許夢(mèng)楠，陳兵.改進(jìn)布谷鳥(niǎo)搜索算法的車間作業(yè)調(diào)度優(yōu)化研究［J］.小型微型計(jì)算機(jī)系統(tǒng)，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球面搜索的量子遺傳算法及其應(yīng)用［J］.系統(tǒng)工程理論與實(shí)踐，2016，36（4）：1042-1046.

［12］?? 張津源，張軍，季偉東，等.具備自糾正和逐維學(xué)習(xí)能力的粒子群算法［J］.小型微型計(jì)算機(jī)系統(tǒng)，2021，

42（5）：919-926.

［13］?? 張微微，楊海寧.改進(jìn)人工魚(yú)群算法的無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)覆蓋優(yōu)化［J］.電子技術(shù)與軟件工程，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］?? 杜振鑫，劉廣鐘，韓德志，等.基于全局無(wú)偏搜索策略的精英人工蜂群算法［J］.電子學(xué)報(bào)，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