基于動(dòng)態(tài)分級(jí)蝴蝶優(yōu)化算法的WSN 節(jié)點(diǎn)覆蓋優(yōu)化*

吳 亮趙晴峰湯顯峰

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

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

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

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

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

1 模型描述

1.1 WSN 覆蓋模型

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

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

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

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

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

1.2 能耗模型

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

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

接收l(shuí)bit 數(shù)據(jù)的能耗為:

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

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

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

1.3 目標(biāo)函數(shù)

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

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

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

2 BOA 算法

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

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

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

蝴蝶個(gè)體全局搜索時(shí)的位置更新方式為:

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

蝴蝶個(gè)體局部開(kāi)發(fā)時(shí)的位置更新方式為:

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

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

式中:r3∈[0，1]，為隨機(jī)量。

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

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

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

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

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

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

3.2 動(dòng)態(tài)分級(jí)策略

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

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

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

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

(1)針對(duì)差質(zhì)種群的黃金正弦變異擾動(dòng)機(jī)制

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

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

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

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

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

(3)針對(duì)優(yōu)勢(shì)種群的精英引導(dǎo)機(jī)制

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

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

DLBOA 算法的流程如圖3。

圖3 DLBOA 算法

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

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

圖4 個(gè)體位置編碼

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

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

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

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

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

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

步驟3 令迭代t=1；

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

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

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

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

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

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

步驟7t=t＋1；

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

5 實(shí)驗(yàn)分析

為了驗(yàn)證方法的有效性，利用兩個(gè)實(shí)驗(yàn)場(chǎng)景進(jìn)行性能分析。 實(shí)驗(yàn)場(chǎng)景1:令布署區(qū)域大小S=60 m×60 m，傳感器節(jié)點(diǎn)總數(shù)V=80，傳感器感知半徑r=5 m，通信半徑R=10 m。 實(shí)驗(yàn)場(chǎng)景2:令布署區(qū)域大小S=100 m×100 m，傳感器節(jié)點(diǎn)總數(shù)V=100，傳感器感知半徑r=8 m，通信半徑R=15 m。 傳感器初始能量Estart=1 J，目標(biāo)函數(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。 實(shí)驗(yàn)環(huán)境為Windows10操作系統(tǒng)，CPU 主頻為3.0 G，內(nèi)存為8 GB，實(shí)驗(yàn)平臺(tái)為MATLAB 2019b。 利用節(jié)點(diǎn)隨機(jī)布署方法 RAND、 混沌優(yōu)化細(xì)菌覓食算法COBFA[6]、自適應(yīng)動(dòng)態(tài)混沌量子粒子群算法DACQPSO[8]和本文的DLBOA 算法進(jìn)行性能比較。

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

圖5 實(shí)驗(yàn)場(chǎng)景1 RAND 算法節(jié)點(diǎn)隨機(jī)布署

圖7 實(shí)驗(yàn)場(chǎng)景1 DACQPSO 算法的節(jié)點(diǎn)覆蓋圖

圖8 實(shí)驗(yàn)場(chǎng)景1 DLBOA 算法的節(jié)點(diǎn)覆蓋圖

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

圖9 實(shí)驗(yàn)場(chǎng)景1 覆蓋率的變化

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

圖10 實(shí)驗(yàn)場(chǎng)景1 傳感器節(jié)點(diǎn)布署數(shù)量對(duì)覆蓋率的影響

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

圖11 實(shí)驗(yàn)場(chǎng)景2 RAND 算法節(jié)點(diǎn)隨機(jī)布署

圖12 實(shí)驗(yàn)場(chǎng)景2 COBFA 算法的節(jié)點(diǎn)覆蓋圖

圖13 實(shí)驗(yàn)場(chǎng)景2 DACQPSO 算法的節(jié)點(diǎn)覆蓋圖

圖14 實(shí)驗(yàn)場(chǎng)景2 DLBOA 算法的節(jié)點(diǎn)覆蓋圖

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

圖15 實(shí)驗(yàn)場(chǎng)景2 覆蓋率的變化

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

圖16 實(shí)驗(yàn)場(chǎng)景2 傳感器節(jié)點(diǎn)布署數(shù)量對(duì)覆蓋率的影響

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

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

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

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

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

圖19 切換概率取值的影響

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

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