吳 亮趙晴峰湯顯峰

(1.中國科學院大學附屬腫瘤醫(yī)院(浙江省腫瘤醫(yī)院)，浙江 杭州310022；2.中國科學院基礎(chǔ)醫(yī)學與腫瘤研究所，浙江 杭州310022；3.浙江大學信息技術(shù)中心，浙江 杭州310027)

無線傳感器網(wǎng)絡(luò)(Wireless Sensor Network，WSN)具有成本低、覆蓋范圍廣、布署靈活的特點[1]，已經(jīng)被廣泛應(yīng)用于環(huán)境監(jiān)測、智慧交通、健康醫(yī)療等諸多領(lǐng)域[2-4]。 而監(jiān)測區(qū)域內(nèi)傳感器節(jié)點分布是否均勻、是否具有高覆蓋率成為決定影響無線傳感器網(wǎng)絡(luò)監(jiān)測質(zhì)量和網(wǎng)絡(luò)生存時間的關(guān)鍵因素。若將大量傳感器節(jié)點在區(qū)域內(nèi)隨機布署，容易出現(xiàn)節(jié)點聚集、覆蓋盲區(qū)等問題。 若局部區(qū)域節(jié)點密度過高，不僅會產(chǎn)生過多的冗余數(shù)據(jù)傳輸和網(wǎng)絡(luò)擁塞，還會導致過多的能量浪費。 而覆蓋盲區(qū)則會降低區(qū)域的監(jiān)測質(zhì)量，影響網(wǎng)絡(luò)的可靠性。 因此，優(yōu)化傳感器節(jié)點的布署和覆蓋，以均衡的能耗要求，以盡可能少的布署節(jié)點完成高區(qū)域覆蓋率對無線傳感器網(wǎng)絡(luò)的發(fā)展將具有重要的現(xiàn)實意義。

群智能優(yōu)化算法因其強大的啟發(fā)式搜索思維和全局搜索能力，近年來已被廣泛應(yīng)用于傳感器節(jié)點的覆蓋優(yōu)化問題。 文獻[5]針對不均勻問題提出了改進自適應(yīng)粒子群(Improved Particle Swarm Optimization，IPSO)的節(jié)點覆蓋優(yōu)化算法，通過進化因子和聚合因子對慣性權(quán)重的改進，提升了傳統(tǒng)粒子群的尋優(yōu)性能，將網(wǎng)絡(luò)覆蓋率提高了2%～6%。 文獻[6]設(shè)計了一種混沌優(yōu)化細菌覓食算法(Chaos Optimization of Bacterial Foraging Algorithm，COBFA)對節(jié)點布署進行優(yōu)化，構(gòu)造了多目標優(yōu)化模型，提高了覆蓋率和網(wǎng)絡(luò)綜合利用率。 文獻[7]設(shè)計基于虛擬力的改進粒子群優(yōu)化算法(Virtual Force Particle Swarm Optimization，VFPSO)，引入維度選擇策略，將傳感節(jié)點布署后的覆蓋率提升了約5%。 文獻[8]設(shè)計了自適應(yīng)動態(tài)混沌量子粒子群算法(Dynamic self-Adaptive Chaotic Quantum-behaved PSO，DACQPSO)，利用種群分布熵和平均粒距的概念，加速了量子粒子群的進化尋優(yōu)過程，平均覆蓋率提高了約2.7%，但依然存在覆蓋盲區(qū)。 文獻[9]提出了改進灰狼優(yōu)化算法(Improved Grey Wolf Optimization，IGWO)，利用混沌機制、收斂因子非線性調(diào)節(jié)及混合變異對傳統(tǒng)GWO 算法進行改進，網(wǎng)絡(luò)覆蓋率提升了3%，但仍存在部分區(qū)域布署過于集中、分布缺乏均勻性的問題。 文獻[10]針對分布不均勻的低覆蓋率問題，提出了改進鯨魚優(yōu)化(Improved Whale Optimization Algorithm，IWOA)的覆蓋優(yōu)化算法，最后以更少的傳感節(jié)點布署得到更高的覆蓋率，網(wǎng)絡(luò)監(jiān)測質(zhì)量有所提高。 上述算法在優(yōu)化傳感器節(jié)點覆蓋問題上雖然取得了性能提升，但群智能優(yōu)化算法本身所固有的尋優(yōu)精度不高、收斂速度慢、易于早熟收斂等問題還有待進一步解決，這使得在提高網(wǎng)絡(luò)覆蓋率、均衡節(jié)點能量使用等問題上仍然有進一步的優(yōu)化空間。

蝴蝶優(yōu)化算法(Butterfly Optimization Algorithm，BOA)是2019年提出的一種模擬蝴蝶種群覓食行為的智能優(yōu)化算法[11]。 該算法易于實現(xiàn)，依賴參數(shù)少。 在求解高維度函數(shù)優(yōu)化問題時，其性能已經(jīng)優(yōu)于傳統(tǒng)粒子群算法(Particle Swarm Optimization，PSO)、差分進化算法(Differential Evolution，DE)和蜂群優(yōu)化算法(Artificial Bee Colony，ABC)。 因此，已經(jīng)廣泛應(yīng)用于特征選擇[12]、圖像分割[13]和工程設(shè)計優(yōu)化[14]等問題。 然而，標準BOA 算法依然存在尋優(yōu)精度低、收斂速度慢的不足，尤其在解決高維復雜問題時，算法的尋優(yōu)穩(wěn)定性、跳離局部最優(yōu)能力的適應(yīng)性依然還有很大改進空間。

為了更好地進行傳感器節(jié)點的覆蓋優(yōu)化，提升傳感器節(jié)點能量的均衡利用，本文設(shè)計了一種基于動態(tài)分級的改進蝴蝶優(yōu)化算法(Dynamic Leveling Butterfly Optimization Algorithm，DLBOA)。 為了提高傳統(tǒng)蝴蝶優(yōu)化算法的尋優(yōu)性能，通過混沌映射優(yōu)化初始種群結(jié)構(gòu)，提升種群多樣性；設(shè)計動態(tài)分級策略，基于種群個體適應(yīng)度，將種群劃分為差、中、優(yōu)三種等級，并分別利用黃金正弦算法、慣性權(quán)重位置更新和精英引導機制進行優(yōu)化，以提高算法的收斂速度，增強脫離局部最優(yōu)的能力。 將DLBOA 算法應(yīng)用于求解WSN 中傳感器節(jié)點的覆蓋優(yōu)化問題。 結(jié)果表明，改進算法實現(xiàn)了預期效果，在提升區(qū)域覆蓋率和均衡能量利用方面具有明顯效果。

1 模型描述

1.1 WSN 覆蓋模型

將若干同質(zhì)結(jié)構(gòu)的傳感器節(jié)點布署于規(guī)則的二維平面區(qū)域，布署后的傳感節(jié)點不具備移動性。 同時，傳感器節(jié)點可以感知在其感知半徑以內(nèi)的其他節(jié)點。 令無線傳感器網(wǎng)絡(luò)WSN 的節(jié)點布署區(qū)域大小S=L×M，單位:m2，可將其視為L×M的網(wǎng)格，單個網(wǎng)格大小為1，則區(qū)域內(nèi)可監(jiān)測的像素點數(shù)為L×M。令集合Z={Z1，Z2，…，ZV}表示待布署的傳感器節(jié)點集合，節(jié)點總數(shù)為V。 令r為節(jié)點的感知半徑，R為數(shù)據(jù)通信半徑，且r≤2R。

假設(shè)傳感器Zi的坐標位置為(xi，yi)，i=1，2，…，V，(xj，yj)為區(qū)域內(nèi)某像素點gj的坐標，則傳感器Zi與像素點gj的距離為:

若d(Zi，gj)≤r，則表明像素點gj可被傳感器節(jié)點Zi感知并覆蓋。 則可以通過布爾0-1 測量模型定義節(jié)點感知模型，定義點gj被傳感節(jié)點Zi感知的概率為:

通常情況下，一個傳感器節(jié)點可以被多個節(jié)點同時感知。 因此，為了提升無線傳感器布署區(qū)域的感知概率，像素點gj被布署的傳感器節(jié)點聯(lián)合感知的概率可定義為:

則網(wǎng)絡(luò)整體覆蓋率為所有傳感器節(jié)點所覆蓋的目標像素點數(shù)量與布署區(qū)域內(nèi)的總像素點數(shù)量之比[9]，為:

1.2 能耗模型

傳感器節(jié)點能耗主要由節(jié)點進行數(shù)據(jù)收發(fā)時的能耗組成，能耗模型如圖1 所示。 功率放大器根據(jù)收發(fā)雙方間距決定使用Friss 自由空間模型或者多路衰減模型。 令傳感器節(jié)點間距為dis，數(shù)據(jù)發(fā)送量為lbit，則節(jié)點的發(fā)送能耗計算為[6]:

圖1 傳感器節(jié)點的能耗模型

接收lbit 數(shù)據(jù)的能耗為:

式中:Eelec為射頻電路/接收電路單位bit 數(shù)據(jù)的能耗，εfriss、εtwo-ray為自由空間模型和多路衰減模型中功率放大器的能耗，dcross為能耗模型距離閾值。

若令傳感器節(jié)點的初始能量為Estart，則經(jīng)過數(shù)據(jù)發(fā)送與接收后，其剩余能量為:

式中:α、β分別表示傳感器節(jié)點發(fā)送與接收數(shù)據(jù)的次數(shù)。

1.3 目標函數(shù)

無線傳感器網(wǎng)絡(luò)WSN 中的節(jié)點覆蓋優(yōu)化問題，是以更少的傳感器節(jié)點布署數(shù)量，在確保能耗均衡的前提下，盡可能得到更高的區(qū)域覆蓋率。 將目標函數(shù)定義為:

式中:F1=COV(Z)，表示網(wǎng)絡(luò)覆蓋率；F2=(V-V′)/V，表示傳感節(jié)點空閑率；F3為剩余能量均衡函數(shù)，定義為:

式中:Ei為目標節(jié)點所在局部區(qū)域的傳感器剩余能量，E′i為傳感節(jié)點剩余能量之和，W為感知像素點周圍的傳感節(jié)點數(shù)。w1、w2、w3分別表示網(wǎng)絡(luò)覆蓋率權(quán)重、傳感節(jié)點節(jié)省權(quán)重和傳感節(jié)點剩余能量權(quán)重，用于定義對目標的偏好程度，且w1＋w2＋w3=1。

2 BOA 算法

BOA 算法中，每只蝴蝶會散發(fā)一定濃度的香味，經(jīng)過空氣擴散后，其他個體會根據(jù)香味濃度被其吸引。 若嗅到最高濃度的香味，個體會向其靠近，該過程即為全局搜索。 若感知不到任何香味，個體將在空間內(nèi)進行隨機游走式飛行，該過程即為局部開發(fā)。 香味濃度的計算公式為:

式中:I為刺激強度，c為感知形態(tài)，a為冪指數(shù)，理解為不同程度香味的吸收，且a、c∈[0，1]，BOA 算法中，通常a= 0.1，c初值為0.01，其迭代變化公式為:

式中:Tmax為最大迭代次數(shù)。

蝴蝶個體全局搜索時的位置更新方式為:

式中:xi(t)為原始位置，xi＋1(t＋1)為迭代后的新位置，g*為當前最優(yōu)位置(解)，r1∈[0，1]，為隨機量，fi為蝴蝶i的香味濃度。

蝴蝶個體局部開發(fā)時的位置更新方式為:

式中:xj(t)、xk(t)為種群中隨機選擇的兩只蝴蝶的位置，r2∈[0，1]，為隨機量。

種群進行全局搜索或局部開發(fā)由切換概率P決定，P∈[0，1]，具體為:

式中:r3∈[0，1]，為隨機量。

3 動態(tài)分級蝴蝶優(yōu)化算法DLBOA

3.1 基于混沌映射的種群初始化

研究表明，初始種群位置優(yōu)劣直接影響著群智能優(yōu)化算法的收斂速度和解的質(zhì)量。 均勻的初始分布比隨機分布對解空間的覆蓋率更高，更容易生成質(zhì)量更高的初始解。 標準BOA 算法采用隨機方式生成初始種群的位置，具體方法是:

式中:Rand 為[0，1]間的隨機生成量，xi為個體位置，[lbi，ubi]為個體i的搜索范圍。 但這種方式并不能確保覆蓋整個解空間。

混沌序列對比隨機搜索，具有遍歷性、隨機性和規(guī)律性特征，可以更高的概率對解空間進行全局搜索，確保種群多樣性。 根據(jù)以上分析，本文首先在改進算法中利用遍歷均勻性和迭代速度更快的Tent混沌映射生成初始個體位置，盡可能覆蓋整個解空間，具體公式為:

式中:yi(t＋1)為[0，1]間的混沌序列值。 根據(jù)混沌序列值可以逆映射到種群的初始位置，計算方式為:

3.2 動態(tài)分級策略

對于基本BOA 算法而言，隨著迭代更新，種群個體的適應(yīng)度都有所不同。 鄰近最優(yōu)解的個體適應(yīng)度更優(yōu)，遠離最優(yōu)解的個體適應(yīng)度則更差。 而為了同時兼顧種群的全局搜索和局部開發(fā)能力，種群也需要擁有這種多樣性特征。 但所有個體如果采用相同的位置更新方式，勢必會影響算法的尋優(yōu)效率。為此，本文將引入一種動態(tài)分級方法，根據(jù)每次迭代中種群個體適應(yīng)度值的升序排列，將種群動態(tài)地劃分為差質(zhì)種群個體、中等種群個體和優(yōu)質(zhì)種群個體。同時，對于不同的種群劃分，利用不同策略對其個體進行位置更新。 算法結(jié)構(gòu)如圖2 所示。

圖2 動態(tài)分級蝴蝶優(yōu)化算法

令種群個體總數(shù)為n。 若令排序后的差質(zhì)種群個體數(shù)量為p，中等種群個體數(shù)量為q-p，優(yōu)勢種群個體數(shù)量為n-q，則種群的動態(tài)分級模型可表示為:

隨著算法迭代，種群適應(yīng)度會逐步提升，即優(yōu)勢種群規(guī)模會逐步擴大，此時應(yīng)該控制不同分級種群的規(guī)模，擴大優(yōu)勢種群規(guī)模，使算法能夠在精英引導機制下，實現(xiàn)算法的快速收斂。 具體地，將種群分級邊界值動態(tài)地設(shè)置為:

(1)針對差質(zhì)種群的黃金正弦變異擾動機制

差質(zhì)種群個體位置適應(yīng)度較差，說明此時距離最優(yōu)解區(qū)域較遠，因此，為了避免局部最優(yōu)，需要引入變異機制對差質(zhì)個體進行擾動，以提高種群的多樣性。 為此，本文引入一種基于黃金正弦算法(Golden-Sine Algorithm，GSA) 的變異擾動機制。GSA 算法是一種新型元啟發(fā)式算法，受啟發(fā)于正弦函數(shù)遍歷單位圓所有正弦值等同于個體在搜索空間內(nèi)的迭代尋優(yōu)過程，通過構(gòu)造正弦函數(shù)數(shù)學模型求解優(yōu)化問題。 對于適應(yīng)度較差的差質(zhì)種群，引入黃金正弦的位置更新方式對個體進行更新，具體方式為:

式中:g*(t)為當前差質(zhì)種群中的最優(yōu)個體，R1∈[0，2π]，R2∈[0，π]，均為隨機數(shù)，R1決定個體迭代時的移動距離，R2決定個體迭代時的移動方向，θ1、θ2是根據(jù)黃金分割數(shù)τ=(51/2-1)/2 得出的系數(shù)，且θ1=-π＋(1-τ)×2π，θ2=-π＋τ×2π，該系數(shù)縮小了算法的搜索空間，可引導個體向最優(yōu)解逼近。

(2)針對中等種群的慣性權(quán)重位置更新機制

對于中等種群，其適應(yīng)度處于中間部分，離最優(yōu)解距離不是最遠，但進化速度較慢。 為了加速算法收斂，中等種群位置更新在維持原始BOA 算法位置更新方式的基礎(chǔ)上，引入粒子群算法PSO 中的慣性權(quán)重思維[15]，控制蝴蝶個體的社會學習與認知學習能力。 慣性權(quán)重的思想是:迭代早期，以較大慣性權(quán)重提升全局搜索能力；迭代晚期，以較小慣性權(quán)重增強局部開發(fā)能力，加速算法收斂。 此外，算法設(shè)計了一種自適應(yīng)非線性慣性權(quán)重更新方法，具體公式為:

式中:wmax為初始慣性權(quán)重最大值，wmin為迭代結(jié)束時的慣性權(quán)重最小值。 則將中等種群的位置更新方式改進為:

(3)針對優(yōu)勢種群的精英引導機制

對于優(yōu)質(zhì)種群，由于已經(jīng)接近于最優(yōu)解，此時需要加快個體向最優(yōu)解靠近。 為此，引入一種針對優(yōu)質(zhì)種群的精英引導策略，在位置更新中引入個體最優(yōu)，通過精英引導加速算法收斂。 更新參數(shù)r1、r2后，利用控制參數(shù)cpi在精英引導方式和原種群更新方式之間切換，具體方式為:

式中:cp(t)為切換概率，設(shè)為cp(t)= 1/2-t/2Tmax，rand∈[0，1]，為隨機數(shù)。 根據(jù)以上位置更新方式，迭代早期，cp(t)較大，個體傾向于用后兩式更新位置，算法可以沿著最優(yōu)解的方向加速進化；而迭代晚期，cp(t)較小，此時精英引導作用減弱，算法依然采用原始種群更新方式(前兩式)更新種群位置。

DLBOA 算法的流程如圖3。

圖3 DLBOA 算法

4 DLBOA 算法求解WSN 節(jié)點覆蓋

首先解決個體位置的編碼映射問題。 傳感器節(jié)點布署問題需要求解的是所布署的傳感節(jié)點在區(qū)域內(nèi)的橫縱坐標值，可將DLBOA 算法中的蝴蝶個體位置編碼為傳感器節(jié)點的一個覆蓋分布，蝴蝶位置的維度設(shè)置為傳感器節(jié)點的兩倍，即2V，并將維度2d-1 視為傳感器節(jié)點d的橫坐標，維度2d視為d的縱坐標。 如圖4 是蝴蝶個體位置編碼示意圖，傳感器節(jié)點Zi∈Z，i=1，2，…，V，Zi=(xi，yi)，xi∈[0，L]，yi∈[0，M]。

圖4 個體位置編碼

DLBOA 算法的優(yōu)化目標是:將若干數(shù)量的傳感器節(jié)點布署在監(jiān)測區(qū)域S，在均衡能耗的要求下，以盡可能少的布署節(jié)點完成高區(qū)域覆蓋率的目標，并求解相應(yīng)節(jié)點布署的最優(yōu)坐標位置。 此時，節(jié)點布署覆蓋優(yōu)化問題即適應(yīng)度函數(shù)(8)為目標函數(shù)的高維復雜矢量尋優(yōu)問題，節(jié)點布署位置的尋優(yōu)過程可抽象為改進蝴蝶優(yōu)化算法中蝴蝶的覓食尋優(yōu)行為。

覆蓋優(yōu)化的具體求解步驟如下:

輸入:布署區(qū)域大小S=L×M、傳感器節(jié)點總數(shù)V、節(jié)點感知半徑r、通信半徑R；DLBOA 算法參數(shù):種群規(guī)模n、迭代總次數(shù)Tmax、個體搜索區(qū)間[lb，ub](對應(yīng)布署區(qū)域大小)、慣性權(quán)重初值wmax和終值wmin、切換概率P；

輸出:傳感節(jié)點布署的坐標位置及最優(yōu)目標函數(shù)值；

步驟1 輸入網(wǎng)絡(luò)參數(shù)、DLBOA 算法參數(shù)；

步驟2 利用混沌映射進行種群初始化，生成初始傳感節(jié)點布署位置坐標；

步驟3 令迭代t=1；

步驟4 計算種群適應(yīng)度，確定全局最優(yōu)解，并計算蝴蝶個體的香味濃度值；

步驟5 按適應(yīng)度值對種群個體進行降序排列，按式(18)對種群動態(tài)分級，劃分為差質(zhì)種群、中等種群和優(yōu)質(zhì)種群；

步驟5a 對于差質(zhì)種群個體，按式(21)進行位置更新；

步驟5b 對于中等種群個體，先以式(22)更新慣性權(quán)重，再以式(23)更新位置；

步驟5c 對于優(yōu)質(zhì)種群個體，以式(24)更新位置；

步驟6 重新計算種群適應(yīng)度，并更新全局最優(yōu)解；

步驟7t=t＋1；

步驟8 判斷迭代條件t≤Tmax? 若滿足，返回步驟4；否則，算法結(jié)束，輸出傳感節(jié)點布署的坐標位置及最優(yōu)目標函數(shù)值。

5 實驗分析

為了驗證方法的有效性，利用兩個實驗場景進行性能分析。 實驗場景1:令布署區(qū)域大小S=60 m×60 m，傳感器節(jié)點總數(shù)V=80，傳感器感知半徑r=5 m，通信半徑R=10 m。 實驗場景2:令布署區(qū)域大小S=100 m×100 m，傳感器節(jié)點總數(shù)V=100，傳感器感知半徑r=8 m，通信半徑R=15 m。 傳感器初始能量Estart=1 J，目標函數(shù)中的權(quán)重w1=0.6，w2=0.2，w3=0.2。 DLBOA 算法參數(shù)中，種群規(guī)模n=40，迭代總次數(shù)Tmax=400，慣性權(quán)重初值wmax=0.9，終值wmin= 0.4，切換概率P= 0.7。 實驗環(huán)境為Windows10操作系統(tǒng)，CPU 主頻為3.0 G，內(nèi)存為8 GB，實驗平臺為MATLAB 2019b。 利用節(jié)點隨機布署方法 RAND、 混沌優(yōu)化細菌覓食算法COBFA[6]、自適應(yīng)動態(tài)混沌量子粒子群算法DACQPSO[8]和本文的DLBOA 算法進行性能比較。

實驗場景1 結(jié)果分析:圖5～圖8 是分別利用隨機算法RAND、COBFA 算法、DACQPSO 算法和DLBOA算法得到傳感器節(jié)點布署情況，區(qū)域內(nèi)的黑色實心點代表傳感器節(jié)點(位置坐標)，圍繞節(jié)點周圍的圓形為其覆蓋區(qū)域。 由于前文覆蓋模型中已將覆蓋區(qū)域簡化為L×M個像素點，則若總計有K個像素點被傳感器節(jié)點覆蓋，則其覆蓋率為K/(L×M)。觀察RAND 算法得到的節(jié)點布署結(jié)果，其覆蓋盲區(qū)還是比較多，包括左下角、右側(cè)邊界、上邊界以及中間位置區(qū)域均存在有覆蓋盲區(qū)，同時在左側(cè)上下區(qū)域和右上區(qū)域有明顯的傳感器節(jié)點密集分布，節(jié)點冗余度太高，這顯然不能滿足高覆蓋率的傳感器節(jié)點布署需求。 COBFA 算法和DACQPSO 算法得到的節(jié)點布署結(jié)果較明顯地減少了覆蓋盲區(qū)，節(jié)點分布的均勻性有所提升，但依然存在小面積的覆蓋盲區(qū)。 在節(jié)點密度導致的冗余問題上，DACQPSO 算法略優(yōu)于COBFA 算法，前者基本不存在較密集的節(jié)點分布，后者在中間區(qū)域的節(jié)點密度、重復覆蓋位置略高，說明兩種改進算法的位置精度還有提升空間。 而本文的DLBOA 算法可以在區(qū)域內(nèi)得到更均勻的傳感節(jié)點分布，基本沒有覆蓋盲區(qū)，節(jié)點間距更加平均，使得節(jié)點覆蓋冗余更少，這說明算法在求解布署位置上具有更高的精度，更好地滿足了目標函數(shù)的最優(yōu)化。

圖5 實驗場景1 RAND 算法節(jié)點隨機布署

圖7 實驗場景1 DACQPSO 算法的節(jié)點覆蓋圖

圖8 實驗場景1 DLBOA 算法的節(jié)點覆蓋圖

圖9 是網(wǎng)絡(luò)覆蓋率的收斂曲線。 從網(wǎng)絡(luò)覆蓋率上看，本文的DLBOA 算法在進行200 次迭代后，覆蓋率已經(jīng)接近100%，是四種算法中最好的。 其次是DACQPSO 算法和COBFA 算法。 曲線的斜率可以反映算法對前次迭代中傳感器節(jié)點位置的修正情況，三種智能優(yōu)化算法的曲線明顯要更加陡峭，說明節(jié)點位置調(diào)整后對網(wǎng)絡(luò)覆蓋率有了較大提升。 而RAND 算法基本是平緩的直線走勢，調(diào)整幅度有限，覆蓋率也比較低。 DACQPSO 算法和COBFA 算法的網(wǎng)絡(luò)覆蓋率之所以無法進一步提升的原因在于，種群進化已經(jīng)處于局部最優(yōu)解處，算法無法跳離該位置，即無法進一步找到最佳的節(jié)點布署位置。 在網(wǎng)絡(luò)覆蓋率上，DLBOA 比DACQPSO、COBFA 和RAND 算法分別高出4.3%、11.5%和17.8%。 同時，DLBOA 算法可以以更少迭代次數(shù)得到更高的網(wǎng)絡(luò)覆蓋率，說明算法求解精度不僅更高，其演化速度也是更快的。

圖9 實驗場景1 覆蓋率的變化

圖10 是傳感器節(jié)點布署數(shù)量對網(wǎng)絡(luò)覆蓋率的影響。 節(jié)點布署數(shù)量增加，勢必會增加網(wǎng)絡(luò)覆蓋率，但算法表現(xiàn)各有不同。 RAND 算法的增長速度最為緩慢，節(jié)點布署位置并未得到優(yōu)化。 DLBOA 算法增長速度最快，同時也是四種算法中覆蓋率最高的。此外，若布署傳感器節(jié)點較少，無論利用哪種算法，節(jié)點密集和交叉覆蓋的情況會相對較少，所以算法之間在覆蓋率上并沒有較大差距。 但當傳感節(jié)點數(shù)量增長到一定程度時，節(jié)點交叉區(qū)域變多，若不對布署位置精確求解，顯然會出現(xiàn)覆蓋空洞和節(jié)點密集等情況。 可以看到，DLBOA 算法在增加節(jié)點數(shù)量后的覆蓋率增長明顯更快，最后接近于全覆蓋，這更加佐證了改進蝴蝶優(yōu)化算法在求解精度上得到了進一步提高，可以較少的節(jié)點布署數(shù)量維持較高的網(wǎng)絡(luò)覆蓋率。

圖10 實驗場景1 傳感器節(jié)點布署數(shù)量對覆蓋率的影響

實驗場景2 結(jié)果分析:場景2 的布署區(qū)域和節(jié)點覆蓋半徑都有相應(yīng)增加，四種算法的節(jié)點分布情況如圖11～圖14 所示。 RAND 算法的覆蓋盲區(qū)依然很多，部分區(qū)域的傳感器節(jié)點分布也過于密集，冗余度過高。 COBFA 算法和DACQPSO 算法的節(jié)點布署明顯減少了覆蓋盲區(qū)，分布均勻性更好，但依然存在個別位置的空白。 此外，DACQPSO 算法在節(jié)點密集冗余分布上要優(yōu)于COBFA 算法，COBFA 算法還是存在較嚴重的重復覆蓋問題，說明算法的尋優(yōu)性能、位置布署精度有待改善。 DLBOA 算法得到的節(jié)點具有更均勻的分布，覆蓋冗余更少，更加有效地利用了傳感節(jié)點的單點覆蓋面積，節(jié)點間距也更加平均。

圖11 實驗場景2 RAND 算法節(jié)點隨機布署

圖12 實驗場景2 COBFA 算法的節(jié)點覆蓋圖

圖13 實驗場景2 DACQPSO 算法的節(jié)點覆蓋圖

圖14 實驗場景2 DLBOA 算法的節(jié)點覆蓋圖

結(jié)合圖15 給出的網(wǎng)絡(luò)覆蓋率收斂曲線可知，擴大布署區(qū)域后，DLBOA 算法迭代250 次左右后，覆蓋率已接近100%，收斂速度要優(yōu)于另外三種算法。兩種智能算法處于收斂處的網(wǎng)絡(luò)覆蓋率無法接近于100%的原因在于，其算法求解的是局部最優(yōu)解，算法無法有效跳離局部極值點而開拓新的搜索空間得到候選解。 在平均網(wǎng)絡(luò)覆蓋率上，DLBOA 算法比DACQPSO、COBFA 和RAND 算法分別高出8.2%、16.5%和22.6%。

圖15 實驗場景2 覆蓋率的變化

圖16 是該場景下傳感器節(jié)點布署數(shù)量對網(wǎng)絡(luò)覆蓋率的影響。 可見，DLBOA 算法在增加節(jié)點數(shù)量后的覆蓋率增長依然是所有算法中更快的，最后的網(wǎng)絡(luò)覆蓋率也接近于全覆蓋。 經(jīng)過兩個不同規(guī)模布署場景的驗證，證明DLBOA 算法具備穩(wěn)定的性能表現(xiàn)。

圖16 實驗場景2 傳感器節(jié)點布署數(shù)量對覆蓋率的影響

無線傳感器網(wǎng)絡(luò)的最終目標是通過傳感節(jié)點的數(shù)據(jù)收集和自組網(wǎng)絡(luò)將信息傳輸?shù)竭h端的匯聚基站。 由于傳感節(jié)點多由電池供電，能耗有限，節(jié)點布署位置直接影響數(shù)據(jù)傳輸距離。 結(jié)合節(jié)點的能耗模型，本部分進一步觀察不同布署算法下網(wǎng)絡(luò)的生存時間，且該生存時間直接由區(qū)域內(nèi)存活的傳感器節(jié)點數(shù)量決定。 選取經(jīng)典的分簇路由協(xié)議LEACH 對傳感器節(jié)點自組織成網(wǎng)，圖17 是在實驗場景1 下四種算法進行節(jié)點布署后，協(xié)議運行100 輪次過程中，網(wǎng)絡(luò)節(jié)點存活量的變化情況。 根據(jù)實驗結(jié)果，出現(xiàn)第一個死亡節(jié)點的輪次順序是RAND 早于COBFA，COBFA 早于DACQPSO，DLBOA 算法最晚，由于傳感節(jié)點主要能耗集中于數(shù)據(jù)傳輸能耗，因此該結(jié)果的原因可解釋為:若節(jié)點布署不均勻，部分區(qū)域節(jié)點密度高，冗余節(jié)點多，數(shù)據(jù)重復傳輸過多，節(jié)點能耗更快；而未覆蓋的空洞區(qū)域則需要更多次的遠距離數(shù)據(jù)中繼，同樣會使節(jié)點能耗加快。 DLBOA 算法以更少的傳感節(jié)點布署量覆蓋更多區(qū)域，數(shù)據(jù)傳輸距離均等，避免了過多的遠距離傳輸和近距離冗余傳輸，在有限的能量儲備下延長了節(jié)點的工作時間，從而也延長了整個網(wǎng)絡(luò)的工作時間。 表1 是各算法間的系統(tǒng)比較結(jié)果，可以看到，在平均網(wǎng)絡(luò)覆蓋率、布署節(jié)點數(shù)量以及剩余網(wǎng)絡(luò)能量三個方面，DLBOA 算法均要優(yōu)于另外三種算法。

表1 算法系統(tǒng)比較

圖17 傳感器網(wǎng)絡(luò)的生存時間

影響DLBOA 算法性能的主要參數(shù)為慣性權(quán)重初值wmax和終值wmin以及切換概率P。 在前文場景1、場景2 中設(shè)置的參數(shù)wmax=0.9、wmin=0.4 和切換概率P=0.7 是根據(jù)文獻閱讀所取的經(jīng)驗值，也是多數(shù)算法中取值的最優(yōu)組合。 為了算法的嚴謹性，本部分根據(jù)不同的取值組合驗證算法的尋優(yōu)性能。 慣性權(quán)重w和切換概率P均對DLBOA 算法在迭代前后期的全局搜索與局部開發(fā)能力的切換具有重要影響。 分別選取四組參數(shù)組合進行實驗測試，慣性權(quán)重的四組取值組合為(wmin，wmax)=(0.2，0.7)、(0.3，0.8)、(0.4，0.9)和(0.5，0.8)，切換概率P=0.5、0.7、0.8 和0.9。

固定P=0.7，改變慣性權(quán)重取值進行第一組實驗，利用場景1 配置實驗環(huán)境，結(jié)果如圖18 所示，柱狀圖對應(yīng)左縱坐標取值，折線圖對應(yīng)右縱坐標取值。結(jié)合網(wǎng)絡(luò)平均覆蓋率和網(wǎng)絡(luò)剩余能量指標看，慣性權(quán)重取值對DLBOA 算法的尋優(yōu)結(jié)果具有一定影響。 (0.4，0.9)的取值組合下算法可以得到最優(yōu)的覆蓋率，雖然優(yōu)勢并不明顯，但依然是四種取值中最佳的。 固定(wmin，wmax)= (0.4，0.9)，改變切換概率取值進行第二組實驗，結(jié)果如圖19。 概率閾值P直接決定了DLBOA 算法在全局搜索與局部開發(fā)間的切換。P取值越大，越易進入全局搜索階段；反之，越易進入局部開發(fā)階段。 結(jié)果顯示，P=0.7 和0.8時，平均覆蓋率較接近，幾乎相等。 而網(wǎng)絡(luò)剩余能量指標上，P=0.7 時略優(yōu)于0.8。 對于蝴蝶種群進化過程而言，若P值較大，全局搜索比重則更大，會導致算法收斂慢；若P值過小，局部開發(fā)比重則增加，會導致算法種群多樣性缺失，搜索精度下降。 合理的搜索應(yīng)在迭代前期具有更強大的全局搜索能力，迭代后期則應(yīng)加強局部開發(fā)能力，加快尋優(yōu)收斂。 切換概率的常量設(shè)定也具有一定局限性，動態(tài)調(diào)整全局搜索與局部開發(fā)比重，以自適應(yīng)方式設(shè)置切換概率將是下一步優(yōu)化的目標。

圖18 慣性權(quán)重取值的影響

圖19 切換概率取值的影響

6 結(jié)束語

提出一種基于動態(tài)分級蝴蝶優(yōu)化算法的節(jié)點布署策略。 為了提高傳統(tǒng)蝴蝶優(yōu)化算法的尋優(yōu)精度和速度，引入混沌映射進行種群初始化，確保種群多樣性；采用動態(tài)分級策略，根據(jù)種群個體適應(yīng)度，將蝴蝶種群劃分為差質(zhì)、中等和優(yōu)質(zhì)三種等級，并分別利用黃金正弦算法、慣性權(quán)重位置更新和精英引導機制對三類種群進行優(yōu)化，提高算法的收斂速度，增強脫離局部最優(yōu)的能力。 將動態(tài)分級蝴蝶優(yōu)化算法應(yīng)用于求解傳感器節(jié)點的覆蓋優(yōu)化問題，以融合區(qū)域覆蓋率、能量均衡和節(jié)點閑置率的目標函數(shù)作為算法的適應(yīng)度函數(shù)，對傳感器節(jié)點的布署位置進行迭代尋優(yōu)。 結(jié)果表明，改進算法能夠有效優(yōu)化傳感節(jié)點布署，提高網(wǎng)絡(luò)覆蓋率，延遲節(jié)點死亡。 如何構(gòu)建更加復雜的布署模型，如存在非均勻遮擋或衰減分布的實驗場景，將是下一步需要深入研究的問題。