宋大鵬 楊曉飛 王 俊 葉 輝

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

1 引言

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

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

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

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

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

2.1 模型分析

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

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

2.2 覆蓋率

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

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

3 算法設(shè)計

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

3.1 天牛須搜索算法

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

3.2 算法改進過程

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

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

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

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

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

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

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

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

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

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

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

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

3.3 算法性能分析

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

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

表1 隨機實驗覆蓋率統(tǒng)計結(jié)果分析

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

4 仿真實驗分析

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

4.1 算法均勻度分析

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

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

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

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

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

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

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

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

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

4.2 與其它算法性能對比實驗

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

從表2 展示的結(jié)果可以看出，采用IBAS 算法的移動傳感器網(wǎng)絡(luò)覆蓋率達到了91.21%，與標(biāo)準(zhǔn)PSO 算法相比提高了11.18%，與改進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é)點數(shù)量的優(yōu)化覆蓋率

為了更加直觀地觀察覆蓋效果，將上述實驗結(jié)果輸出，分別得到45 個初始節(jié)點時，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)化覆蓋圖可以看出，利用智能算法進行優(yōu)化后，空白區(qū)域逐漸消失，節(jié)點分布趨于平均，其中本文提出IBAS 算法的優(yōu)化效果最佳。

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

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

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

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

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

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

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

5 結(jié)語

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