基于改進(jìn)天牛須搜索算法的傳感器網(wǎng)絡(luò)覆蓋優(yōu)化策略*

宋大鵬 楊曉飛 王 俊 葉 輝

（江蘇科技大學(xué)電子信息學(xué)院 鎮(zhèn)江 212100）

1 引言

移動(dòng)傳感器網(wǎng)絡(luò)（Mobile Sensor Networks，MSNs）由很多具有特定功能的傳感器節(jié)點(diǎn)通過移動(dòng)自組織方式形成的網(wǎng)絡(luò)系統(tǒng)［1］，可用于國防監(jiān)控，環(huán)境監(jiān)測和交通等許多領(lǐng)域。區(qū)域覆蓋率［2］是衡量移動(dòng)傳感器網(wǎng)絡(luò)質(zhì)量（Quality of Service，QoS）的一個(gè)重要指標(biāo)。實(shí)際部署時(shí)，為了保證系統(tǒng)的魯棒性，往往增加節(jié)點(diǎn)的部署密度，但冗余節(jié)點(diǎn)存在感知區(qū)域重疊導(dǎo)致網(wǎng)絡(luò)功耗增加，降低了網(wǎng)絡(luò)整體性能［3］。因此，需要獲取最佳的網(wǎng)絡(luò)覆蓋，讓一些節(jié)點(diǎn)暫時(shí)休眠以備不時(shí)之需。

在移動(dòng)傳感器網(wǎng)絡(luò)覆蓋優(yōu)化領(lǐng)域，許多學(xué)者采用了一些智能算法來處理，如粒子群優(yōu)化（PSO）算法［4］、人工蜂群（ABC）算法［5］、蟻獅（ALO）算法［6］、遺傳（GA）算法［7］、蟻群優(yōu)化（ACO）算法［8］等，來獲得全局搜索結(jié)果。隨著問題研究的深入，提出了許多改進(jìn)算法。在文獻(xiàn)［9］中，為了提高粒子群算法的全局搜索能力，在基本粒子群算法中引入了混沌邏輯。文獻(xiàn)［10］在混沌邏輯的基礎(chǔ)上，提出了種群進(jìn)化度和相對聚集度來控制慣性權(quán)重。在文獻(xiàn)［11］中，提出了一種自適應(yīng)優(yōu)化算法來優(yōu)化每個(gè)粒子的位置信息，以增強(qiáng)局部搜索能力。文獻(xiàn)［12］在算法的迭代過程中引入了碰撞反彈策略，以保證粒子群優(yōu)化算法的多樣性，克服了粒子群優(yōu)化算法在優(yōu)化階段陷入局部最優(yōu)的弱點(diǎn)。文獻(xiàn)［13］中引入了一種動(dòng)態(tài)加速因子策略來搜索局部極值位置，引導(dǎo)其跳出局部最優(yōu)，但復(fù)雜度較高。文獻(xiàn)［14］采用混合節(jié)點(diǎn)，引入Voronoi多邊形的特征來尋找覆蓋孔，其大小可以通過輪盤賭來確定。最后采用蜂群算法求解最優(yōu)覆蓋率，對覆蓋空洞進(jìn)行定位和補(bǔ)償，但收斂速度較慢。文獻(xiàn)［15］提出了一種基于混合策略的改進(jìn)蟻獅算法。利用收縮因子提高了算法的搜索遍歷性，加快了算法的收斂速度。

雖然上述學(xué)者提出了多種改進(jìn)算法，但存在種群規(guī)模較為龐大，且易陷入局部最優(yōu)難以跳出等問題，為了實(shí)現(xiàn)移動(dòng)傳感器網(wǎng)絡(luò)的覆蓋率最大化，同時(shí)使得覆蓋更加均勻，本文提出了一種改進(jìn)型的天牛須搜索算法（IBAS）。通過選用較少的種群規(guī)模，利用改進(jìn)步長和隨機(jī)方向等函數(shù)來平衡全局搜索和局部開發(fā)，從而擺脫“早熟”現(xiàn)象，以及基于當(dāng)前最優(yōu)值的偵查策略，提高了算法的收斂速度。

2 相關(guān)問題描述

移動(dòng)傳感器網(wǎng)絡(luò)利用移動(dòng)節(jié)點(diǎn)的傳感器感知周圍信息，需要通過優(yōu)化算法來設(shè)置節(jié)點(diǎn)的最佳移動(dòng)位置來使得傳感器網(wǎng)絡(luò)的整體感知覆蓋率最大化。為了解決移動(dòng)傳感器網(wǎng)絡(luò)的覆蓋優(yōu)化問題，文中建立了各種數(shù)學(xué)模型。

2.1 模型分析

假設(shè)MSNs 是同構(gòu)的，每個(gè)傳感器都有相同的通信半徑Rc和感知半徑Rs，且Rc=2Rs［16］。在面積為L×H 的監(jiān)測區(qū)域內(nèi)，隨機(jī)部署N 個(gè)傳感器節(jié)點(diǎn)S={s1,s2,s3,…,sN}，傳感器節(jié)點(diǎn)si的坐標(biāo)為(xi,yi)，監(jiān)測區(qū)域中任意一點(diǎn)tj的坐標(biāo)為(xj,yj)，i,j∈(1,2,…,N)，則節(jié)點(diǎn)si到點(diǎn)tj的歐氏距離為

在不失一般性的前提下，建立概率感知模型［17～18］，假定目標(biāo)點(diǎn)被傳感器節(jié)點(diǎn)監(jiān)測到的概率是確定的，即監(jiān)測到為1，否則為0，這是一種離散化的理想狀態(tài)模型，一定程度上符合MSNs 的真實(shí)覆蓋情況。則節(jié)點(diǎn)si對目標(biāo)點(diǎn)tj的監(jiān)測概率為因此，可得所有節(jié)點(diǎn)對點(diǎn)tj的聯(lián)合感知半徑為

2.2 覆蓋率

文中所提覆蓋率是指所有工作節(jié)點(diǎn)覆蓋的面積與監(jiān)測區(qū)域總面積的比值，是評價(jià)傳感器網(wǎng)絡(luò)QoS 的一項(xiàng)重要性能指標(biāo)。移動(dòng)節(jié)點(diǎn)的部署位置將很大程度上決定網(wǎng)絡(luò)覆蓋率。為了便于計(jì)算感知面積大小，文中將監(jiān)測區(qū)域分為L×H個(gè)網(wǎng)格，因此，可以將MSNs 覆蓋率定義為被感知到的網(wǎng)格個(gè)數(shù)與網(wǎng)格總個(gè)數(shù)的比值［19～20］：

從而，MSNs 的最佳網(wǎng)絡(luò)覆蓋問題可以轉(zhuǎn)化為以式（4）為目標(biāo)函數(shù)的覆蓋率parea的優(yōu)化求解問題。

3 算法設(shè)計(jì)

針對當(dāng)前部分智能算法在求解移動(dòng)傳感器網(wǎng)絡(luò)覆蓋問題上存在的收斂速度慢、易陷入局部極值和算法復(fù)雜度高的問題，本文提出了基于改進(jìn)型天牛須搜索方法的網(wǎng)絡(luò)覆蓋優(yōu)化求解算法。

3.1 天牛須搜索算法

經(jīng)典天牛須搜索算法（BAS）是2017年Jiang等［21］受到天牛覓食原理的啟發(fā)，提出的一種優(yōu)化算法。天牛利用兩只長觸角，如果左觸角獲得的氣味強(qiáng)度高于右觸角，則往左搜索，反之往右搜索。該算法不需要知道函數(shù)的具體形式和梯度信息，就可以實(shí)現(xiàn)高效的全局尋優(yōu)。相比于粒子群和人工蜂群等算法，該算法的優(yōu)勢在于只需要一個(gè)個(gè)體，可以使運(yùn)算量大大降低。

3.2 算法改進(jìn)過程

1）天牛的覓食行為可轉(zhuǎn)化為n 維移動(dòng)傳感器區(qū)域內(nèi)對目標(biāo)函數(shù)的全局尋優(yōu)。設(shè)置天牛質(zhì)心在網(wǎng)絡(luò)中的位置為X，其左右兩須分別位于質(zhì)心兩側(cè)，分別為XL和XR，(X、XL、XR)∈Rn。

2）為了提高算法的局部搜索能力，天牛每次前進(jìn)的方向是隨機(jī)的，因而從天牛右須指向左須的向量也是隨機(jī)的，這樣可以避免陷入局部最優(yōu)而停滯。

建立n維單位隨機(jī)向量并做歸一化處理：

式（5）中rands(n,1)表示生成n維隨機(jī)向量左須、右須的位置分別為

式中為第k迭代次數(shù)；Xk表示天牛在第k次迭代時(shí)的質(zhì)心坐標(biāo)；XLk和XRk分別表示天牛左須和右須在第k次迭代時(shí)的區(qū)域坐標(biāo)，D為兩須間距。

3）本文將式（4）作為算法的目標(biāo)函數(shù)fun(X)，確定左右觸角氣味的強(qiáng)度，即適應(yīng)度值大小。分別將左、右須的坐標(biāo)代入式（4）中，計(jì)算出對應(yīng)的適應(yīng)度函數(shù)值f(XL)和f(XR)：

4）根據(jù)左、右須的適應(yīng)度值的大小關(guān)系確定下一步的前進(jìn)方向：

其中δk表示天牛前進(jìn)時(shí)的步長，Xk+1表示第k次迭代計(jì)算后更新的質(zhì)心坐標(biāo)位置，sign(.)表示符號(hào)函數(shù)，當(dāng)f(XL)≥f(XR)時(shí)，sign(.)為負(fù)，反之為正。

5）為了提高全局搜索能力，天牛前進(jìn)時(shí)的步長大小需要進(jìn)行改進(jìn)，初期階段步長要足夠的大，并且隨著時(shí)間的推移，步長逐漸減?。?/p>

其中，μ是步長的衰減系數(shù)，μ∈[0,1]，δk+1是第k次迭代更新后的步長。

根據(jù)上式（5）～（9）迭代循環(huán)，直到滿足終止條件，所得到的天牛質(zhì)心位置X，即為目標(biāo)函數(shù)的最優(yōu)解，即最優(yōu)覆蓋率時(shí)的節(jié)點(diǎn)坐標(biāo)位置，所設(shè)計(jì)的改進(jìn)天牛須搜索算法（IBAS）的流程圖如圖1所示。

圖1 天牛須搜索算法流程圖

3.3 算法性能分析

本文采用蒙特卡洛［15］模擬方法驗(yàn)證IBAS 算法的收斂性，為了減輕算法隨機(jī)性造成的影響，設(shè)置50 個(gè)節(jié)點(diǎn)，感知半徑Rs為12，最大迭代次數(shù)為1000，進(jìn)行30次獨(dú)立實(shí)驗(yàn)，實(shí)驗(yàn)數(shù)據(jù)表如下。

由表1 可以看出，本文IBAS 最終可以滿足覆蓋的要求，實(shí)驗(yàn)中的最好覆蓋率為98.29%，最差覆蓋率為92.36%，而平均覆蓋率達(dá)到了95.71%。且實(shí)驗(yàn)中樣本的方差僅僅只有0.00024，表明其波動(dòng)很小，優(yōu)化算法的結(jié)果很穩(wěn)定。

表1 隨機(jī)實(shí)驗(yàn)覆蓋率統(tǒng)計(jì)結(jié)果分析

同時(shí)，為了保證算法的絕對收斂，防止算法在最優(yōu)附近“徘徊”，本文設(shè)置最大迭代次數(shù)，當(dāng)算法達(dá)到最優(yōu)且不再變化時(shí)或算法滿足最大迭代次數(shù)時(shí)，停止該算法。

4 仿真實(shí)驗(yàn)分析

為了驗(yàn)證算法的性能，假設(shè)移動(dòng)傳感器網(wǎng)絡(luò)監(jiān)測區(qū)域?yàn)?00×100m 的正方形區(qū)域，將其離散化為100×100個(gè)網(wǎng)格，在這個(gè)區(qū)域內(nèi)隨機(jī)放置45個(gè)傳感器節(jié)點(diǎn)，每個(gè)傳感器節(jié)點(diǎn)的感知半徑Rs為10m，通信半徑Rc為20m。IBAS 算法的參數(shù)為：步長δ=2*Rs，μ=0.95，最大迭代次數(shù)為500次。

4.1 算法均勻度分析

均勻度［20］是衡量網(wǎng)絡(luò)QoS 的一項(xiàng)重要指標(biāo)。覆蓋均勻度可以保證節(jié)點(diǎn)的分布均勻，這樣可以使網(wǎng)絡(luò)能量消耗相對均衡。均勻度一般用相鄰節(jié)點(diǎn)間距離的標(biāo)準(zhǔn)差來表示。如式（11），標(biāo)準(zhǔn)差越小則覆蓋的均勻性就越好。U是整個(gè)網(wǎng)絡(luò)的均勻度。U越小，網(wǎng)絡(luò)覆蓋的均勻性越好。

其中：n 為節(jié)點(diǎn)總數(shù)；m 為節(jié)點(diǎn)i 的鄰近節(jié)點(diǎn)總數(shù)；mi為節(jié)點(diǎn)i 的鄰近節(jié)點(diǎn)；Di,j為節(jié)點(diǎn)i 和鄰近節(jié)點(diǎn)j之間的距離；Mi為節(jié)點(diǎn)i與其所有鄰近節(jié)點(diǎn)之間距離的平均值；Ui為節(jié)點(diǎn)i的鄰近節(jié)點(diǎn)均勻度。

如圖2和圖3分別所示是初始部署節(jié)點(diǎn)時(shí)和經(jīng)IBAS 算法優(yōu)化后的網(wǎng)絡(luò)覆蓋率圖像。如果節(jié)點(diǎn)間的距離小于或等于通信半徑，則互為鄰近節(jié)點(diǎn)。

圖2 初始部署節(jié)點(diǎn)

圖3 IBAS算法優(yōu)化

對比圖2 和圖3，可以直觀地觀察到網(wǎng)絡(luò)的覆蓋均勻度特征，這兩個(gè)圖說明了我們的IBAS 算法優(yōu)化的初始分布和后分布的節(jié)點(diǎn)分布情況。與圖2相比，可以直觀地看出，圖3中的網(wǎng)絡(luò)覆蓋更加均勻。由于在初始分布時(shí)，有許多覆蓋和未覆蓋的冗余區(qū)域。根據(jù)式（10）和（11），網(wǎng)絡(luò)均勻度可計(jì)算得出為3.531。而經(jīng)過IBAS 算法優(yōu)化后的節(jié)點(diǎn)分布更加均勻，其值為2.714，比初始分布低0.817，這與我們從圖2和圖3中觀察到的結(jié)果一致。

但由于均勻度反映的是節(jié)點(diǎn)的分布程度，即節(jié)點(diǎn)間距離的標(biāo)準(zhǔn)差，當(dāng)節(jié)點(diǎn)全部聚集在一起，彼此間的距離沒有較大波動(dòng)，或節(jié)點(diǎn)彼此間沒有聯(lián)系時(shí)，均勻度就達(dá)不到反映均勻程度的理想效果，所以引入均勻率V，即區(qū)域覆蓋率與均勻度的比值。

Parea為整體網(wǎng)絡(luò)的覆蓋率，V為整體網(wǎng)絡(luò)的均勻率。當(dāng)V越大時(shí)，則網(wǎng)絡(luò)整體覆蓋越均勻。

根據(jù)式（4）可以計(jì)算得出圖2 和圖3 的覆蓋率分別為70.80%和91.21%，根據(jù)式（12）可以得出其均勻率分別為20.05%和33.61%，相較于初始布點(diǎn)時(shí)的均勻率提高了13.56%，由此可以看出經(jīng)IBAS算法優(yōu)化后節(jié)點(diǎn)覆蓋更均勻。

4.2 與其它算法性能對比實(shí)驗(yàn)

為了進(jìn)一步驗(yàn)證IBAS 覆蓋優(yōu)化策略的性能，將本文算法與文獻(xiàn)［4］中提出的粒子群PSO算法和文獻(xiàn)［13］基于動(dòng)態(tài)加速因子的改進(jìn)粒子群PSO-DAC 算法，以及文獻(xiàn)［21］中提出的標(biāo)準(zhǔn)BAS算法進(jìn)行實(shí)驗(yàn)數(shù)據(jù)對比。

從表2 展示的結(jié)果可以看出，采用IBAS 算法的移動(dòng)傳感器網(wǎng)絡(luò)覆蓋率達(dá)到了91.21%，與標(biāo)準(zhǔn)PSO 算法相比提高了11.18%，與改進(jìn)PSO_DAC 算法相比提高了8.71%，與標(biāo)準(zhǔn)BAS 算法相比提高了4.34%，網(wǎng)絡(luò)覆蓋率得到了明顯的改善。而IBAS算法的均勻率為33.61%，相較于PSO 算法、PSO_DAC算法和標(biāo)準(zhǔn)BAS 算法分別提高了9.59%、6.51%和5.01%，由此可見整體網(wǎng)絡(luò)覆蓋更均勻。

表2 相同節(jié)點(diǎn)數(shù)量的優(yōu)化覆蓋率

為了更加直觀地觀察覆蓋效果，將上述實(shí)驗(yàn)結(jié)果輸出，分別得到45 個(gè)初始節(jié)點(diǎn)時(shí)，PSO 算法、PSO_DAC 算法和標(biāo)準(zhǔn)BAS 算法的直觀覆蓋效果，如圖4～圖6所示。

圖4 標(biāo)準(zhǔn)PSO算法優(yōu)化

圖5 PSO_DAC算法優(yōu)化

圖6 BAS算法優(yōu)化

從上面幾種算法對應(yīng)的優(yōu)化覆蓋圖可以看出，利用智能算法進(jìn)行優(yōu)化后，空白區(qū)域逐漸消失，節(jié)點(diǎn)分布趨于平均，其中本文提出IBAS 算法的優(yōu)化效果最佳。

由圖7 可以看出：IBSA 算法能夠穩(wěn)定收斂，達(dá)到算法的最大覆蓋率，最終區(qū)域內(nèi)的覆蓋率穩(wěn)定在91.21%，均勻率為33.61%；標(biāo)準(zhǔn)BAS 算法的最終覆蓋率可以達(dá)到86.87%，均勻率為28.60%；PSO 算法很容易陷入了局部最優(yōu)，結(jié)果導(dǎo)致最終的覆蓋率并未超過85%，僅達(dá)到了80.03%，均勻率為24.09%；而PSO_DAC 算法，在基礎(chǔ)的粒子群算法上使用動(dòng)態(tài)加速因子的方法來改進(jìn)局部搜索的能力，雖然覆蓋率有所提高，但實(shí)驗(yàn)結(jié)果表明其最終結(jié)果仍不理想，僅為83.50%，均勻率為27.46%。

圖7 不同算法迭代收斂對比

4.3 不同網(wǎng)絡(luò)規(guī)模下的對比實(shí)驗(yàn)

為進(jìn)一步驗(yàn)證IBAS 算法在移動(dòng)傳感器網(wǎng)絡(luò)覆蓋中的優(yōu)化效果，與標(biāo)準(zhǔn)PSO、改進(jìn)PSO_DAC 算法，以及標(biāo)準(zhǔn)BAS算法在不同網(wǎng)絡(luò)規(guī)模下進(jìn)行了對比實(shí)驗(yàn)，配置參數(shù)不變，得到的結(jié)果如表3 所示。其中U為均勻度，V為均勻率。

表3 不同節(jié)點(diǎn)數(shù)量的優(yōu)化覆蓋率

從表3 和圖8 中可以看出，在相同配置、不同節(jié)點(diǎn)數(shù)的條件下，IBAS 算法的覆蓋率和均勻率均高于 PSO 算法、PSO_DAC 算法和標(biāo)準(zhǔn)BAS 算法。IBAS 算法不管是在節(jié)點(diǎn)數(shù)量較多時(shí)，還是在節(jié)點(diǎn)數(shù)較少時(shí)均比其他幾種算法能更加有效地提高移動(dòng)傳感器網(wǎng)絡(luò)覆蓋率，由此可以說明IBAS 算法的局部搜索能力更強(qiáng)，更容易克服“早熟”，網(wǎng)絡(luò)覆蓋效果更好，覆蓋更均勻。

圖8 不同節(jié)點(diǎn)數(shù)的覆蓋率對比圖

5 結(jié)語

針對移動(dòng)傳感器網(wǎng)絡(luò)覆蓋率問題，本文提出一種改進(jìn)天牛須搜索（IBAS）算法來解決傳感器節(jié)點(diǎn)的覆蓋優(yōu)化問題。通過引入步長改進(jìn)，隨機(jī)方向函數(shù)，以及利用當(dāng)前最優(yōu)值的偵查策略來對經(jīng)典BAS算法進(jìn)行改進(jìn)。通過對IBAS算法進(jìn)行性能討論和與其它算法進(jìn)行比對，結(jié)果表明：該算法結(jié)構(gòu)簡單，不僅提高了搜索空間的遍歷性，避免了易陷入局部極值的缺點(diǎn)，而且提升了網(wǎng)絡(luò)的穩(wěn)定性和覆蓋率，具有較好的實(shí)用效果。