基于量子粒子群優化的DV-Hop算法研究

張中芳，張玲華

(1.南京郵電大學 通信與信息工程學院，江蘇 南京 210003； 2.江蘇省通信與網絡技術工程研究中心，江蘇 南京 210003)

0 引 言

隨著計算機技術的發展，智能算法在最優化問題中的應用越發普遍，研究者們借助計算機的智能算法來有效地解決問題。通過采用一些新的搜索模型，并根據自然界的進化演變規律進行算法研究。研究者從基本的啟發式算法出發，提出了群體智能算法。它是一種模擬自然過程的優化算法，如蟻群算法、粒子群算法等，因此在智能控制、電力系統和工程設計等方面應用廣泛。無線傳感器網絡(wireless sensor network,WSN)[1]由大量的傳感器節點組成，具有獲取數據、處理信息和無線通信的能力，從而用來采集、處理和傳輸監測對象的信息。節點定位技術是無線傳感器研究領域的關鍵技術，廣泛應用于目標檢測、目標識別和目標跟蹤中。文中提出了一種改進量子粒子群算法與DV-Hop[2]算法的融合算法，有效改善了DV-Hop算法的節點定位誤差，提高了定位精度。

1 DV-Hop定位算法的誤差分析

DV-Hop算法是通過泛洪通信方法來記錄節點之間的跳數和基于距離矢量路由協議的APS定位算法。DV-Hop定位算法一般分為三步，第一步計算各個節點之間的跳數，第二步根據跳數和信標節點之間的距離計算出平均跳距，第三步未知節點可以根據跳數和平均跳距計算出與信標節點之間的距離。通過這些有用的信息，利用三邊測量法[3]或極大似然估計法[4]估計求得未知節點的位置坐標。

在經典的DV-Hop節點定位算法中，對未知節點位置估計的誤差主要包括兩個方面：一方面是平均跳距的估計形成的，采用的做法是直接利用錨節點之間的實際距離除以錨節點之間總的跳數所得；另一方面是用基本位置估計方法計算未知節點位置時產生的誤差。文中研究的思路是使未知節點的估計坐標誤差更小，對估計坐標進行優化和校正。

在利用數學方法計算未知節點的位置坐標時，當選擇的三個點在一條直線上時，就會導致形成的三個圓不能相交于一點，因此采用三邊測量法就得不到正確的解。同時，三邊測量法對測量出的估計誤差非常敏感，而DV-Hop算法在估計平均跳距時會形成誤差的累積，更加降低了節點的定位精度。而采用極大似然估計法可以將誤差平均化，根據矩陣可以得到一個估計的解，但在估計平均每跳距離時會產生誤差。從矩陣方程式AX=b來看，在方程式中引入了很多具有誤差的已知量，因此極大似然估計法求解的節點誤差還是很大的。那么，如果通過選擇合適的適應值函數，利用量子粒子群算法對估算出的未知節點坐標進行優化，節點的定位誤差一定會縮小，從而提高定位精度。

2 基于量子粒子群算法的DV-Hop定位算法

DV-Hop算法是基于非測距定位算法中最受關注的一個，但在利用跳數和平均跳距計算未知節點的未知坐標時存在一定的誤差。為了減少節點定位過程中的誤差，提高定位的精準度，有學者分別利用遺傳算法[5]、模擬退火算法[6]、粒子群算法[7]對DV-Hop進行了優化。標準的粒子群算法在處理優化問題時要求的種群規模數量更多，在粒子迭代的后期搜索速度變慢，收斂的值容易陷入局部最優。因此，為了解決這些缺陷，文中采用量子粒子群算法對DV-Hop算法進行優化，對估計的節點坐標加以校正。量子粒子群算法能夠以更小的種群規模進行搜索，在更短的時間內迭代得到最佳值，易實現且計算量小。

2.1 標準粒子群算法

粒子群算法[8]是模擬鳥群覓食行為，根據粒子的運動軌跡來進行全局搜索優化，具有易實現、搜索速度快、參數少和不需要梯度信息等優點，在科學研究和軍事方面應用廣泛。每個粒子都有一個相對應的適度值和速度矢量，分別表示距離及運動方向。在迭代算法中，通過比較每個粒子的全局極值Gbest和個體極值Pbest，然后對其位置和速度進行迭代更新[9]。

假設粒子種群數量為N，搜索空間的維度為D，則第i個粒子在D維空間中的位置表示為Xi=(xi1,xi2,…,xiD),i=1,2,…,N，該粒子的速度記為Vi=(vi1,vi2,…,viD),i=1,2,…,N。

通過每一次的迭代來尋找Pbest和Gbest，找到這個極值后再根據如下公式更新粒子的位置和速度：

(1)

(2)

其中，pid和pgd(i=1,2,…,N，d=1,2,…,D)分別為粒子個體極值和全局極值的位置；k為迭代次數；c1，c2為學習因子；rand()為0到1之間的隨機數；w為慣性權值[10]，通過合適的調節方法可以在局部尋優與全局尋優之間找到平衡。慣性權值越小，則局部尋優能力增強，全局尋優能力減弱；慣性權值越大，則全局尋優速度加快，局部尋優能力減弱。

2.2 量子行為的粒子群算法

粒子群算法在靜態尋優方面具有良好的性能，但算法容易出現局部最優值和提前收斂的現象，其他外部因素也會影響算法的智能搜索能力。當前，研究者們主要是通過加入其他智能算法或使粒子發生變異以增加種群多樣性等方式來處理這些缺陷。

粒子群算法在搜索過程中，有粒子的速度的概念，當算法早熟收斂到一個極值點時，所有的粒子容易聚集在一個固定的區域，它們的速度會變為零，這樣一來粒子群就不再繼續迭代搜索最優值，因此得到的解可能是局部最優值。為此，根據量子的概念，文中將量子行為融合到粒子群算法中。量子算法[11]在處理計算機問題時具有高效的計算能力，表明該算法在處理最優化問題方面有很好的優化搜索能力。

量子粒子群算法[12]是將量子計算的一些概念引入到粒子群算法中，使該算法更好地應用在優化搜索中[13]。但與經典的粒子群算法相比，兩者有以下幾點區別：

(1)描述粒子狀態的信息不同。在量子空間中描述粒子狀態的是一個波函數，而波函數是一個概率密度函數[14]，因此迭代變化中的粒子有不確定性的特點，該函數非常適合用來描述算法中尋優的粒子。

(2)取消了粒子群算法中的速度參數。粒子群系統是在量子系統模型下的，當然不需要存在經典力學中的速度概念。量子粒子群算法中的粒子不再受限于速度來更新迭代位置，而是在整個空間里進行全面優化搜索到最優解。

(3)沒有“速度”參數，粒子更新迭代的方式也有所不同。經過前人的研究總結，假設粒子種群數量為N，搜索空間的維度為D，則第i個粒子在D維空間中粒子的進化方程為：

(3)

(4)

(5)

采用一種非線性策略來調整該系數w，從而改進量子粒子群算法。

(6)

其中，wmax和wmin分別為收縮-擴張系數的初始值和迭代結束值；kmax為最大迭代次數；k為當前迭代次數。

最后，當最優位置的適應度值符合最小適應闕值或者迭代次數等于最大值時，該QPSO算法結束。

2.3 QPSO算法的性能比較

為了驗證改進算法的性能，利用2個經典函數(見表1)對標準PSO算法和改進的QPSO算法進行對比實驗，根據實驗結果分析改進算法的優越性和可行性。

表1 測試函數

圖1和圖2分別是QPSO和PSO算法的收斂曲線。

圖1 測試函數f1(x)

圖2 測試函數f2(x)

通過對比發現，QPSO算法不僅提高了精度，而且加快了尋優的求解速度和收斂速度。同時，QPSO算法的迭代次數明顯少于PSO算法，適應值在更早的時候趨于穩定狀態，減少了不必要的迭代。仿真結果表明，改進的QPSO算法在優化DV-Hop算法時，能在很大程度上減少計算量。

2.4 QPSO算法對DV-Hop算法優化的步驟

通過量子粒子群算法對DV-Hop算法進行優化，尋找未知節點到信標節點的實際距離與估計距離之間的最小誤差，從而達到對未知節點位置的估計。文中算法流程如下：

Step1:在一定范圍內隨機產生若干傳感器節點，通過DV-Hop算法的前兩步，根據得到的跳數和平均跳距得到未知節點到信標節點的估計距離,然后用極大似然估計法計算出未知節點的坐標。

Step2：初始化網絡。根據每個未知節點的估計結果在限定的范圍內初始化種群，設定粒子個數及每個粒子大小并隨機初始化各個粒子的位置，設置收縮擴張系數的初始值和結束值，最大迭代次數。

Step3：粒子空間位置的優劣只能由適應度函數衡量，函數決定著整個算法的優化效果。根據實際問題的要求，將跳數的倒數設計在函數中，采用的適應度函數為：

fitness(x,y)=

(7)

其中，fitness(x,y)為粒子i的適應度值；(xi,yi)為信標節點i的坐標值；(x,y)為粒子i的坐標值；di為未知節點到信標節點i的實際距離；θi與未知節點到信標節點i的跳數成反比。

Step4：評價種群中所有的粒子。根據設計的適應值函數，算法開始時計算每個粒子的適應值，然后把這些適應值分別設置為其粒子的最優值。通過比較每個粒子的最優值，得到一個全局的最優值，并記錄該全局最優值所對應的粒子位置為全局最優位置。

Step5：通過式3～5更新粒子的位置狀態，根據式6更新收縮擴張系數。

Step6：如果重新計算更新后粒子的適應度值優于以前位置的適應度值，則新位置取代以前位置成為下次迭代的起點，否則下一次迭代的起點不變。

Step7：若全局極值滿足小于設定的闕值或者迭代次數達到最大的條件，則改進QPSO算法結束。否則，轉至Step3，繼續進行迭代運算。

Step8：將迭代結束得到的全局最優位置作為未知節點的估計位置。

3 仿真實驗與分析

3.1 仿真環境與參數

為了驗證量子粒子群算法的迭代優化性能，在MatlabR2010a平臺上進行仿真實驗。仿真過程中，傳感器節點被隨機分布在100 m×100 m的正方形目標區域內。算法的主要參數設置為：未知節點的個數為100，種群規模為20，最大迭代次數為100。為了減少實驗中人為因素的干擾，節點定位誤差取30次實驗的平均值。采用標準化節點定位誤差來評價算法性能，標準化節點定位誤差為:

AverageError=

(8)

其中，(x,y)為未知節點的實際坐標；(xki,yki)為第K次估計未知節點i的坐標；R為節點的通信半徑；N為未知節點的個數；K為實驗次數。

3.2 不同節點數目的定位誤差分析

通過調節節點總數，在保持錨節點密度不變的條件下，對比DV-Hop、PSO-DVHop和文中改進算法的定位性能。圖3是節點從100增加到550的過程中各個算法的平均定位誤差變化曲線。從圖中可見，當節點總數逐漸增加時，三種算法的定位誤差都有不同程度的下降，但改進算法誤差下降幅度明顯。三種算法的曲線都有一定的波動，這是由于每次仿真實驗時，網絡部署的節點都是隨機生成的，因而誤差上下有所浮動。

圖3 節點數量-平均定位誤差

3.3 不同錨節點密度的節點定位分析

通過調節錨節點密度，對比DV-Hop、PSO-DVHop和文中改進算法的定位性能。圖4是錨節點密度從0.04變化到0.22的過程中各個算法的定位誤差變化曲線。從中可見，當錨節點密度逐漸增大時，算法的平均定位誤差在逐漸減小，但變化幅度在減緩。在相同的錨節點密度下，文中算法的定位精度更高。

圖4 錨節點比例-平均定位誤差

3.4 不同通信半徑對節點定位誤差的影響

在保持節點總數和錨節點密度不變的情況下，通過調節節點的通信半徑大小，對比DV-Hop、PSO-DVHop和文中改進算法的定位性能。圖5是通信半徑從5變化到50的過程中各個算法的平均定位誤差變化曲線。從中可見，當節點的通信半徑在逐漸增加時，網絡拓撲結構中的跳數會發生改變，節點之間的跳數相應減小，從而定位誤差將會減小。文中改進算法能很好地降低定位誤差。

圖5 通信半徑-平均定位誤差

4 結束語

為了提高傳統DV-Hop定位算法的性能，提出用改進的量子粒子群算法來代替粒子群算法來優化節點定位。在保持節點定位硬件成本不變和一定的通信量范圍內，定位節點的精確度更好，一定程度上解決了運用PSO來優化DV-Hop時的定位缺陷問題，體現了該算法的優越性。仿真結果表明，該算法雖然增加了一些計算量，但是節點的平均定位誤差減少10%～15%左右，定位精度得到明顯的提高。

參考文獻:

[1] AKYILDIZ I F,SU W,SANKARASUBRAMANIAM Y,et al.Wireless sensor networks:a survey[J].Computer Networks,2002,38:393-422.

[2] NICULESCU D, NATH B. DV based positioning in Ad Hoc networks[J].Telecommunication Systems,2003,22(1-4):267-280．

[3] 王小平,羅 軍,沈昌祥.三邊測量法的結果穩定性研究[J].計算機工程與科學,2012,34(6):12-17.

[4] 徐原博,鐘麗鴻,崔 洋,等.基于無線傳感器網絡的極大似然定位法的分析[J].傳感器與微系統,2011,30(10):37-40.

[5] LI Wenwen,ZHOU Wunen.Genetic algorithm-base localization algorithm for wireless sensor networks[C]//2011 seventh international conference on natural computation.[s.l.]:[s.n.],2011:2096-2099.

[6] 吳意樂,何 慶.基于改進遺傳模擬退火算法的WSN路徑優化算法[J].計算機應用研究,2016,33(10):2959-2962.

[7] 陳星舟，廖明宏，林建華.基于粒子群優化的無線傳感器網絡節點定位改進[J].計算機應用,2010,30(7):1736-1738.

[8] 李凌燕,杜永貴.改進型粒子群優化在WSNs節點定位中的應用[J].計算機應用與軟件,2014,31(4):69-72．

[9] 劉 逸.粒子群優化算法的改進及應用研究[D].西安：西安電子科技大學,2013.

[10] 林偉民,周寧寧.線性遞減的粒子群優化算法[J].計算機技術與發展,2014,24(10):67-70.

[11] 張 毅,盧 凱,高穎慧.量子算法與量子衍生算法[J].計算機學報,2013,36(9):1835-1842.

[12] 潘大志,劉志斌.量子粒子群算法的改進實現[J].計算機工程與應用,2013,49(10):25-27.

[13] 王艷萍,張惠敏,劉新貴.基于量子粒子群優化算法的無線傳感器網絡節點優化[J].傳感器與微系統,2010,29(2):32-34.

[14] 孫 俊,方 偉,吳小俊,等.量子行為粒子群優化:原理及其應用[M].北京:清華大學出版社,2011:30-39.

[15] 丁 穎,李 飛.自適應收擴系數的雙中心協作QPSO算法[J].計算機工程,2014,40(3):232-237.