基于粒子間距調整改進PSO算法

馮 穎，高文華，康 琳

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

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

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

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

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

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

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

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

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

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

(1)

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

1.2 適應度函數(shù)

(2)

2 基于粒子間距調整改進的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算法的改進

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

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

(5)

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

2.1.2 粒子間距調整

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

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

(6)

2.1.3 增強粒子探尋能力

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

(7)

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

(8)

(9)

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

2.2 基于粒子間距調整改進PSO算法步驟

基于粒子間距調整改進PSO算法的過程如下：

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

(2)適應度值檢測；

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

(4)如果達到itermax，則結束，否則進行下一步；

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

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

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

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

APS-PSO算法是在粒子間距調整和粒子搜索能力兩個方向上做出改進，在調整粒子間距的基礎上，又通過從不同方向添加虛構粒子來增加粒子特性，從而提高算法性能。

3 仿真分析

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

表1 仿真參數(shù)表

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

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

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

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

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

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

圖5 節(jié)點分布均勻性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)能力增強。從圖3可以看出節(jié)點仍然分布不均勻。APS-PSO比OAEBI-PSO、基本PSO和W-PSO具有較高的區(qū)域覆蓋率，APS-PSO可達到99%以上，有效的增強個體多樣性，可以跳脫出局部最優(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ù)增加相應的覆蓋率的變動，表2和圖6可以觀察出，PSO和W-PSO在求解后期覆蓋率幾乎不變。在后期，PSO和W-PSO可能出現(xiàn)了局部收斂，W-PSO在ω上做出了改進，雖然加快的算法收斂但仍然沒有避免粒子早熟。OAEBI-PSO算法尋優(yōu)能力有了顯著提高，但收斂慢，覆蓋率還有待進一步提高。本文的APS-PSO算法收斂快，尋求解的能力有所提升，也沒用過早的陷入局部最優(yōu)。

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

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

4 結論

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