馮 穎，高文華，康 琳

(太原科技大學(xué) 電子信息工程學(xué)院，太原 030024)

無線傳感器網(wǎng)絡(luò)( Wireless Sensor Networks， WSN)是各種具有相同功能或者不同功能的傳感器聚集在一起協(xié)同工作，傳感器通過自己的方式自組建立連接，而且維護(hù)在一個被測區(qū)域框架內(nèi)[1]。用于傳感和存儲從動態(tài)環(huán)境收集到的數(shù)據(jù)信息。這些節(jié)點(diǎn)可以部署在任何所需要的領(lǐng)域，用于檢測或監(jiān)視某些特殊事件等[2]。

為了減少規(guī)模成本，有效的收集數(shù)據(jù)。WSN能否對所監(jiān)測的區(qū)域進(jìn)行嚴(yán)格有效的監(jiān)控，以及WSN能否收集和轉(zhuǎn)發(fā)所需的信息，是WSN中需要解決的最基本的問題[3]。用有限的傳感器節(jié)點(diǎn)盡可能大范圍的去覆蓋特定區(qū)域的問題就轉(zhuǎn)化成如何能求得覆蓋率的最大值問題。因此，覆蓋率是評估WSN網(wǎng)絡(luò)質(zhì)量的關(guān)鍵參數(shù)，也是其應(yīng)用在場景中的重要需求。

關(guān)于通過各種不同的智能算法，把WSN覆蓋作為優(yōu)化目標(biāo)的研究有許多。文獻(xiàn)[4]是對PSO中保持原來速度權(quán)重系數(shù)和認(rèn)識因子進(jìn)行了調(diào)整。文獻(xiàn)[5]Lu等人利用具有吸引和排斥的動物覓食策略，提出了一種吸引和排斥相結(jié)合的PSO(CAR-PSO).有效的克服了過早收斂的問題。文獻(xiàn)[6]Kundu等人通過引入一種新的微擾策略來提高PSO算法的性能。文獻(xiàn)[7]是將粒子群的進(jìn)化和聚合程度引入到慣性權(quán)重ω中，產(chǎn)生了隨著粒子聚合程度不斷變化的動態(tài)慣性權(quán)重。以區(qū)域覆蓋率最大做為目標(biāo)函數(shù)，更新節(jié)點(diǎn)的位置從而達(dá)到最大區(qū)域覆蓋率。相比基本PSO覆蓋率稍有提高，但仍然存在節(jié)點(diǎn)分布不均勻等；文獻(xiàn)[8]將權(quán)重系數(shù)的和認(rèn)識因子分別調(diào)整為線性遞減和遞增形式以及利用正弦函數(shù)來使慣性權(quán)重變化；文獻(xiàn)[9]和文獻(xiàn)[10]分別是應(yīng)用改進(jìn)的離散果蠅算法和在人工魚群算法來找出最優(yōu)的覆蓋方案，與之前幾種PSO算法相比，它的覆蓋率稍有提高，節(jié)點(diǎn)分布比較均勻，但是仍然有節(jié)點(diǎn)越界或者由于重疊而覆蓋不到的問題。文獻(xiàn)[10]針對分布時節(jié)點(diǎn)越過邊界區(qū)域和粒子多樣性減弱，提出尋優(yōu)能力增強(qiáng)型越界免疫的PSO，達(dá)到了尋優(yōu)速度快，降低了停止在局部最優(yōu)的可能。該算法的有效覆蓋率能達(dá)到96%以上，而且魯棒性也較好。文獻(xiàn)[11]采用人工魚群算法與PSO結(jié)合的算法運(yùn)用到WSN的覆蓋中，使達(dá)到覆蓋最大化且節(jié)點(diǎn)均勻分布。文獻(xiàn)[12]和[13]將混沌理論與與粒子群算法相結(jié)合提高了WSN的有效覆蓋率。文獻(xiàn)[14]和[15]進(jìn)行了灰狼算法和PSO相結(jié)合，彌補(bǔ)了兩種算法的缺陷對網(wǎng)絡(luò)覆蓋質(zhì)量有了一定的提高。文獻(xiàn)[16]提出了一種尋優(yōu)能力增強(qiáng)型越界免疫粒子群算法(OAEBI-PSO)通過對越界的粒子進(jìn)行處理是覆蓋率得到了提高。通過學(xué)習(xí)研究，相對于其他算法，PSO的流程不繁瑣復(fù)雜，需要調(diào)節(jié)的參數(shù)少，而且易于與其他算法并行實(shí)現(xiàn)。

之前的研究都有效的提高WSN覆蓋率，但是在尋優(yōu)過程中仍然存在粒子越界、重疊、運(yùn)動速度下降或出現(xiàn)停止不動等，失去多樣性的問題，這就造成了探求最優(yōu)粒子的性能的大大減退。

所以針對上述問題，本文通過在算法尋優(yōu)過程中加入粒子間距離調(diào)整，對粒子間的距離超出所限定的最大閾值，進(jìn)行間距調(diào)整。其次，在算法中將粒子探索軌跡進(jìn)行細(xì)化來增添單個體粒子的多樣性，探索性能從而得到增強(qiáng)。 進(jìn)行MATLAB仿真實(shí)驗(yàn)，得出APS-PSO部署的覆蓋率較高，同時求解的節(jié)點(diǎn)均勻度也較小。APS-PSO算法能夠更好結(jié)合WSN覆蓋數(shù)學(xué)模型，達(dá)到較好的優(yōu)化效果。進(jìn)行50次Mote-Carlo實(shí)驗(yàn)后可以得出算法有較好的穩(wěn)定性。

1 WSN覆蓋數(shù)學(xué)模型

1.1 傳感節(jié)點(diǎn)的物理模型

本文用到的是二元感知模型。其定義為：假設(shè)在區(qū)域A上獲取信息，s為區(qū)域上的某個傳感器節(jié)點(diǎn)，只要在以s為圓心，Rs為半徑的圓內(nèi)的數(shù)據(jù)均能被s所感知到。Z為任意被監(jiān)測目標(biāo)點(diǎn)，當(dāng)Z到節(jié)點(diǎn)S的間隔d小于半徑Rs，則S一定能感知到目標(biāo)Z，概率為1；反之，概率為0[17].

實(shí)際上，區(qū)域塊中的信息是通過多個傳感器同時合作來監(jiān)測的。所以就需要求出這些節(jié)點(diǎn)能夠監(jiān)測到目標(biāo)的聯(lián)合概率。那么，某個目標(biāo)z被全部傳感器同時感知到的概率是[18]：

(1)

其中n為區(qū)域范圍中要布置的節(jié)點(diǎn)數(shù)量，psi是目標(biāo)Z被第i個節(jié)點(diǎn)感知到的概率。

1.2 適應(yīng)度函數(shù)

(2)

2 基于粒子間距調(diào)整改進(jìn)的PSO算法

2.1 PSO算法

粒子群優(yōu)化算法(PSO)是鳥群中每一只鳥通過自身所得到的信息和其他鳥群得到的信息來更新速度和位置，每只鳥都代表的一個解，通過不停地位置更新和比較來找出那個最優(yōu)的解。

速度更新公式：

v(i+1)=ω·v(i)+ζ·c1·(p(i)-x(i))+

η·c2·(g(i)-x(i))

(3)

位置更新公式：

x(i+1)=x(i)+v(i+1)

(4)

2.1 PSO算法的改進(jìn)

2.1.1 慣性權(quán)重系數(shù)ω

PSO中的慣性權(quán)重系數(shù)ω的意義是調(diào)節(jié)PSO的收斂速度和均衡個體的搜尋精度，較大的ω有較好的全局搜索，而較小的ω則更有助于更精確的搜索，因此對ω進(jìn)行了改進(jìn)：

(5)

t為當(dāng)前迭代次數(shù)，itermax為最大迭代次數(shù)，r∈rand(0，1)；在迭代初始時，ω是趨于ωmax，收斂變快，后期ω趨于ωmin，縮小搜索范圍，收斂速度隨之也變慢性權(quán)重調(diào)整PSO(W-PSO)相比基本PSO有較好的收斂性。

2.1.2 粒子間距調(diào)整

在粒子尋優(yōu)的過程中，粒子總會出現(xiàn)越過區(qū)域邊界或者粒子相撞等情況，這樣粒子的多樣性會減少，從而搜索能力也會減弱[10]。之前的論文提出過處理粒子越界問題，在粒子超出區(qū)域界線時，取此維度的邊界值；第一種解決方法是粒子在當(dāng)前維度的速度大小不改變，方向取相反方向；第二種解決辦法是將這些超出邊界的粒子淘汰，這些粒子既沒有代入到適應(yīng)度函數(shù)中計算，也不參與比較和更新[11]。這三種方法隨著迭代增加，會造成多樣性丟失。

本文引入調(diào)整兩兩粒子間距來增添多樣性。粒子更新過程中可能會出現(xiàn)越過界或疊加，所以需要采取以下措施將疊化粒子分離開。設(shè)定粒子之間最小距離為Δd，當(dāng)粒子之間距離小于Δd，同一維數(shù)對應(yīng)的兩個粒子過于靠近。進(jìn)行粒子間距調(diào)整。即：

(6)

2.1.3 增強(qiáng)粒子探尋能力

在迭代后期，由于速度變慢或者趨近于零，所以算法的求解能力會減弱。此時，粒子速度接近于零，只能在最優(yōu)的那個粒子周圍移動，其余的粒子也會匯聚在局部最優(yōu)的周圍。而且在整個聚集過程中，不會出現(xiàn)其他更優(yōu)的點(diǎn)。存在無法跳出局部最優(yōu)的可能。在更新粒子時，每個粒子會預(yù)先有p(1，2，…，m)個虛擬的前進(jìn)方向，即粒子向m個方向前進(jìn)后記錄適應(yīng)值，然后再回到原來的位置。對這m個位置進(jìn)行求解[16]。求得的解與此時的最佳值對比，如果優(yōu)于當(dāng)下的最優(yōu)解，則這個解作為一個待選值。粒子的更新方程如下：

(7)

其中p代表第p個試探的方向，step為步長，step∈(0，1).

(8)

(9)

其中，rand0，rand1，rand2∈(0，1)，M為步長，L為監(jiān)測范圍的長度，G是網(wǎng)格粒度。i為當(dāng)下的迭代值，分子為i+1可以使M的取值更小，搜尋的區(qū)域能夠更加精細(xì)；而且rand1是考慮了粒子在搜索過程中的隨機(jī)性。M取值隨著i的變化而改變，呈線性的關(guān)系。從而提高了算法收斂速度；也抑制算法過早地陷入局部收斂，在后期縮短步長M來加強(qiáng)局部搜索能力，有利于精細(xì)搜索，尋找更優(yōu)解。提出的方法不僅改善了方向的集中指向性，而且也優(yōu)化了步長的選取策略，避免了不必要的搜索，從而提高了節(jié)點(diǎn)利用率。

2.2 基于粒子間距調(diào)整改進(jìn)PSO算法步驟

基于粒子間距調(diào)整改進(jìn)PSO算法的過程如下：

(1)初始化種群參數(shù)；

(2)適應(yīng)度值檢測；

(3)全局最優(yōu)和局部最優(yōu)更新；

(4)如果達(dá)到itermax，則結(jié)束，否則進(jìn)行下一步；

(5)粒子速度和位置更新；

(6)判斷兩兩粒子間距，若小于Δd，調(diào)整粒子位置；

(7)將粒子當(dāng)前位置代入到式(8)中可產(chǎn)生m個位置，將m個位置代入到目標(biāo)函數(shù)，比較這m個值和當(dāng)下的最優(yōu)解，篩選出更優(yōu)的解；

(8)轉(zhuǎn)入步驟3，繼續(xù)運(yùn)行。

APS-PSO算法是在粒子間距調(diào)整和粒子搜索能力兩個方向上做出改進(jìn)，在調(diào)整粒子間距的基礎(chǔ)上，又通過從不同方向添加虛構(gòu)粒子來增加粒子特性，從而提高算法性能。

3 仿真分析

對PSO、W-PSO、尋優(yōu)能力增強(qiáng)型越界免疫PSO(OAEBI-PSO)和APS—PSO進(jìn)行了Matlab仿真，對比了算法的分布情況、覆蓋率、均勻度，APS-PSO的覆蓋率、均勻度和穩(wěn)定性都比PSO和W-PSO算法更優(yōu)。參數(shù)設(shè)置如表1.

表1 仿真參數(shù)表

圖1為30個傳感器通過基本PSO算法部署在100 m*100 m的目標(biāo)域內(nèi)。圖2為進(jìn)行W-PSO算法后節(jié)點(diǎn)的分布情況，因?yàn)閷T性權(quán)重做出來了改進(jìn)，所以經(jīng)過W-PSO算法后的分布情況比基本PSO算法的節(jié)點(diǎn)分布稍有所提高，但是不明顯。傳感器節(jié)點(diǎn)的聚集情況仍然較高，空洞也很明顯。圖3為通過OAEBI-PSO算法優(yōu)化后的節(jié)點(diǎn)分布情況，顯然覆蓋效果得到了提升，但是仍然存在覆蓋空洞、不均勻等問題。圖4為進(jìn)行APS-PSO算法后的節(jié)點(diǎn)分布圖。顯然節(jié)點(diǎn)疊加情況有所減少，提高了節(jié)點(diǎn)利用率，節(jié)點(diǎn)分布比基本PSO算法和W-PSO算法后的分布較均勻，更好覆蓋了目標(biāo)區(qū)域避免了能量的浪費(fèi)。

圖1 PSO節(jié)點(diǎn)位置分布Fig.1 PSO node position distribution

圖2 W-PSO節(jié)點(diǎn)位置分布Fig.2 W-PSO node position distribution

圖3 OAEBI-PSO節(jié)點(diǎn)位置分布Fig.3 W-PSO node position distribution

圖4 APS-PSO節(jié)點(diǎn)位置分布Fig.4 APS-PSO node position distribution

計算節(jié)點(diǎn)間標(biāo)準(zhǔn)差越小，均勻度越好，證明覆蓋的質(zhì)量就好。圖5明顯可以觀察到，APS-PSO的標(biāo)準(zhǔn)差是最低的，即節(jié)點(diǎn)分布最均勻，降低了節(jié)點(diǎn)冗余，從而提高了節(jié)點(diǎn)在監(jiān)測區(qū)域的覆蓋。

圖5 節(jié)點(diǎn)分布均勻性Fig.5 Uniformity of node distribution

圖6是基本PSO、W-PSO、OAEBI-PSO和APS-PSO四種算法隨迭代次數(shù)改變覆蓋率曲線的變化。W-PSO覆蓋率相比PSO提升并不明顯，只升高了0.68%.40次迭代后算法趨于收斂。與PSO算法相比，W-PSO加快了收斂。OAEBI-PSO算法覆蓋值與前兩種算法對比OAEBI-PSO的尋優(yōu)能力增強(qiáng)。從圖3可以看出節(jié)點(diǎn)仍然分布不均勻。APS-PSO比OAEBI-PSO、基本PSO和W-PSO具有較高的區(qū)域覆蓋率，APS-PSO可達(dá)到99%以上，有效的增強(qiáng)個體多樣性，可以跳脫出局部最優(yōu)。APS-PSO的最大覆蓋率PSO提高了4.27%，比W-PSO提高了3.59%.比OAEBI-PSO提高了1.57%.

圖6 隨迭代次數(shù)覆蓋率的改變Fig.6 The coverage varies with the number iterations

表2給出了各個算法隨著迭代次數(shù)增加相應(yīng)的覆蓋率的變動，表2和圖6可以觀察出，PSO和W-PSO在求解后期覆蓋率幾乎不變。在后期，PSO和W-PSO可能出現(xiàn)了局部收斂，W-PSO在ω上做出了改進(jìn)，雖然加快的算法收斂但仍然沒有避免粒子早熟。OAEBI-PSO算法尋優(yōu)能力有了顯著提高，但收斂慢，覆蓋率還有待進(jìn)一步提高。本文的APS-PSO算法收斂快，尋求解的能力有所提升，也沒用過早的陷入局部最優(yōu)。

表2 覆蓋率被迭代次數(shù)所影響結(jié)果

為了進(jìn)一步分析基本PSO、W-PSO、OAEBI-PSO和APS-PSO四種算法的有效性和穩(wěn)定性，圖7給出了四種算法通過50次蒙特卡羅實(shí)驗(yàn)后的得出的覆蓋率曲線。觀察到APS-PSO的穩(wěn)定性較好。通過APS-PSO所能獲得的覆蓋率也大多分布在95%以上。相比另外三種算法有較好的有效性和穩(wěn)定性。

4 結(jié)論

WSN中覆蓋優(yōu)化的改善能夠提高網(wǎng)絡(luò)的覆蓋率，使傳感器得到充分的利用，使耗能更加均衡，從而有效的監(jiān)測到或傳遞目標(biāo)區(qū)域內(nèi)的各項(xiàng)數(shù)據(jù)。論文采用覆蓋率和節(jié)點(diǎn)使用率作為目標(biāo)函數(shù)，在基本PSO算法基礎(chǔ)上，通過調(diào)整粒子間距和增強(qiáng)粒子搜索能力對算法做出了改進(jìn)，在添加自身個體和種群多樣性同時，改善節(jié)點(diǎn)疊化情況，抑制陷入局部最優(yōu)，從而來提高算法解的質(zhì)量。也有效縮減了成本，節(jié)約資源，提升了WSN的覆蓋質(zhì)量。在實(shí)際工作中可以更好的去跳出局部最優(yōu)，使節(jié)點(diǎn)覆蓋更加均勻，從而用更少的節(jié)點(diǎn)來覆蓋監(jiān)測區(qū)域。