基于量子粒子群優(yōu)化的DV-Hop算法研究

張中芳，張玲華

(1.南京郵電大學(xué) 通信與信息工程學(xué)院，江蘇 南京 210003； 2.江蘇省通信與網(wǎng)絡(luò)技術(shù)工程研究中心，江蘇 南京 210003)

0 引 言

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

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

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

在經(jīng)典的DV-Hop節(jié)點(diǎn)定位算法中，對(duì)未知節(jié)點(diǎn)位置估計(jì)的誤差主要包括兩個(gè)方面：一方面是平均跳距的估計(jì)形成的，采用的做法是直接利用錨節(jié)點(diǎn)之間的實(shí)際距離除以錨節(jié)點(diǎn)之間總的跳數(shù)所得；另一方面是用基本位置估計(jì)方法計(jì)算未知節(jié)點(diǎn)位置時(shí)產(chǎn)生的誤差。文中研究的思路是使未知節(jié)點(diǎn)的估計(jì)坐標(biāo)誤差更小，對(duì)估計(jì)坐標(biāo)進(jìn)行優(yōu)化和校正。

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

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

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

2.1 標(biāo)準(zhǔn)粒子群算法

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

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

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

(1)

(2)

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

2.2 量子行為的粒子群算法

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

粒子群算法在搜索過程中，有粒子的速度的概念，當(dāng)算法早熟收斂到一個(gè)極值點(diǎn)時(shí)，所有的粒子容易聚集在一個(gè)固定的區(qū)域，它們的速度會(huì)變?yōu)榱?，這樣一來粒子群就不再繼續(xù)迭代搜索最優(yōu)值，因此得到的解可能是局部最優(yōu)值。為此，根據(jù)量子的概念，文中將量子行為融合到粒子群算法中。量子算法[11]在處理計(jì)算機(jī)問題時(shí)具有高效的計(jì)算能力，表明該算法在處理最優(yōu)化問題方面有很好的優(yōu)化搜索能力。

量子粒子群算法[12]是將量子計(jì)算的一些概念引入到粒子群算法中，使該算法更好地應(yīng)用在優(yōu)化搜索中[13]。但與經(jīng)典的粒子群算法相比，兩者有以下幾點(diǎn)區(qū)別：

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

(2)取消了粒子群算法中的速度參數(shù)。粒子群系統(tǒng)是在量子系統(tǒng)模型下的，當(dāng)然不需要存在經(jīng)典力學(xué)中的速度概念。量子粒子群算法中的粒子不再受限于速度來更新迭代位置，而是在整個(gè)空間里進(jìn)行全面優(yōu)化搜索到最優(yōu)解。

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

(3)

(4)

(5)

采用一種非線性策略來調(diào)整該系數(shù)w，從而改進(jìn)量子粒子群算法。

(6)

其中，wmax和wmin分別為收縮-擴(kuò)張系數(shù)的初始值和迭代結(jié)束值；kmax為最大迭代次數(shù)；k為當(dāng)前迭代次數(shù)。

最后，當(dāng)最優(yōu)位置的適應(yīng)度值符合最小適應(yīng)闕值或者迭代次數(shù)等于最大值時(shí)，該QPSO算法結(jié)束。

2.3 QPSO算法的性能比較

為了驗(yàn)證改進(jìn)算法的性能，利用2個(gè)經(jīng)典函數(shù)(見表1)對(duì)標(biāo)準(zhǔn)PSO算法和改進(jìn)的QPSO算法進(jìn)行對(duì)比實(shí)驗(yàn)，根據(jù)實(shí)驗(yàn)結(jié)果分析改進(jìn)算法的優(yōu)越性和可行性。

表1 測(cè)試函數(shù)

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

圖1 測(cè)試函數(shù)f1(x)

圖2 測(cè)試函數(shù)f2(x)

通過對(duì)比發(fā)現(xiàn)，QPSO算法不僅提高了精度，而且加快了尋優(yōu)的求解速度和收斂速度。同時(shí)，QPSO算法的迭代次數(shù)明顯少于PSO算法，適應(yīng)值在更早的時(shí)候趨于穩(wěn)定狀態(tài)，減少了不必要的迭代。仿真結(jié)果表明，改進(jìn)的QPSO算法在優(yōu)化DV-Hop算法時(shí)，能在很大程度上減少計(jì)算量。

2.4 QPSO算法對(duì)DV-Hop算法優(yōu)化的步驟

通過量子粒子群算法對(duì)DV-Hop算法進(jìn)行優(yōu)化，尋找未知節(jié)點(diǎn)到信標(biāo)節(jié)點(diǎn)的實(shí)際距離與估計(jì)距離之間的最小誤差，從而達(dá)到對(duì)未知節(jié)點(diǎn)位置的估計(jì)。文中算法流程如下：

Step1:在一定范圍內(nèi)隨機(jī)產(chǎn)生若干傳感器節(jié)點(diǎn)，通過DV-Hop算法的前兩步，根據(jù)得到的跳數(shù)和平均跳距得到未知節(jié)點(diǎn)到信標(biāo)節(jié)點(diǎn)的估計(jì)距離,然后用極大似然估計(jì)法計(jì)算出未知節(jié)點(diǎn)的坐標(biāo)。

Step2：初始化網(wǎng)絡(luò)。根據(jù)每個(gè)未知節(jié)點(diǎn)的估計(jì)結(jié)果在限定的范圍內(nèi)初始化種群，設(shè)定粒子個(gè)數(shù)及每個(gè)粒子大小并隨機(jī)初始化各個(gè)粒子的位置，設(shè)置收縮擴(kuò)張系數(shù)的初始值和結(jié)束值，最大迭代次數(shù)。

Step3：粒子空間位置的優(yōu)劣只能由適應(yīng)度函數(shù)衡量，函數(shù)決定著整個(gè)算法的優(yōu)化效果。根據(jù)實(shí)際問題的要求，將跳數(shù)的倒數(shù)設(shè)計(jì)在函數(shù)中，采用的適應(yīng)度函數(shù)為：

fitness(x,y)=

(7)

其中，fitness(x,y)為粒子i的適應(yīng)度值；(xi,yi)為信標(biāo)節(jié)點(diǎn)i的坐標(biāo)值；(x,y)為粒子i的坐標(biāo)值；di為未知節(jié)點(diǎn)到信標(biāo)節(jié)點(diǎn)i的實(shí)際距離；θi與未知節(jié)點(diǎn)到信標(biāo)節(jié)點(diǎn)i的跳數(shù)成反比。

Step4：評(píng)價(jià)種群中所有的粒子。根據(jù)設(shè)計(jì)的適應(yīng)值函數(shù)，算法開始時(shí)計(jì)算每個(gè)粒子的適應(yīng)值，然后把這些適應(yīng)值分別設(shè)置為其粒子的最優(yōu)值。通過比較每個(gè)粒子的最優(yōu)值，得到一個(gè)全局的最優(yōu)值，并記錄該全局最優(yōu)值所對(duì)應(yīng)的粒子位置為全局最優(yōu)位置。

Step5：通過式3～5更新粒子的位置狀態(tài)，根據(jù)式6更新收縮擴(kuò)張系數(shù)。

Step6：如果重新計(jì)算更新后粒子的適應(yīng)度值優(yōu)于以前位置的適應(yīng)度值，則新位置取代以前位置成為下次迭代的起點(diǎn)，否則下一次迭代的起點(diǎn)不變。

Step7：若全局極值滿足小于設(shè)定的闕值或者迭代次數(shù)達(dá)到最大的條件，則改進(jìn)QPSO算法結(jié)束。否則，轉(zhuǎn)至Step3，繼續(xù)進(jìn)行迭代運(yùn)算。

Step8：將迭代結(jié)束得到的全局最優(yōu)位置作為未知節(jié)點(diǎn)的估計(jì)位置。

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

3.1 仿真環(huán)境與參數(shù)

為了驗(yàn)證量子粒子群算法的迭代優(yōu)化性能，在MatlabR2010a平臺(tái)上進(jìn)行仿真實(shí)驗(yàn)。仿真過程中，傳感器節(jié)點(diǎn)被隨機(jī)分布在100 m×100 m的正方形目標(biāo)區(qū)域內(nèi)。算法的主要參數(shù)設(shè)置為：未知節(jié)點(diǎn)的個(gè)數(shù)為100，種群規(guī)模為20，最大迭代次數(shù)為100。為了減少實(shí)驗(yàn)中人為因素的干擾，節(jié)點(diǎn)定位誤差取30次實(shí)驗(yàn)的平均值。采用標(biāo)準(zhǔn)化節(jié)點(diǎn)定位誤差來評(píng)價(jià)算法性能，標(biāo)準(zhǔn)化節(jié)點(diǎn)定位誤差為:

AverageError=

(8)

其中，(x,y)為未知節(jié)點(diǎn)的實(shí)際坐標(biāo)；(xki,yki)為第K次估計(jì)未知節(jié)點(diǎn)i的坐標(biāo)；R為節(jié)點(diǎn)的通信半徑；N為未知節(jié)點(diǎn)的個(gè)數(shù)；K為實(shí)驗(yàn)次數(shù)。

3.2 不同節(jié)點(diǎn)數(shù)目的定位誤差分析

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

圖3 節(jié)點(diǎn)數(shù)量-平均定位誤差

3.3 不同錨節(jié)點(diǎn)密度的節(jié)點(diǎn)定位分析

通過調(diào)節(jié)錨節(jié)點(diǎn)密度，對(duì)比DV-Hop、PSO-DVHop和文中改進(jìn)算法的定位性能。圖4是錨節(jié)點(diǎn)密度從0.04變化到0.22的過程中各個(gè)算法的定位誤差變化曲線。從中可見，當(dāng)錨節(jié)點(diǎn)密度逐漸增大時(shí)，算法的平均定位誤差在逐漸減小，但變化幅度在減緩。在相同的錨節(jié)點(diǎn)密度下，文中算法的定位精度更高。

圖4 錨節(jié)點(diǎn)比例-平均定位誤差

3.4 不同通信半徑對(duì)節(jié)點(diǎn)定位誤差的影響

在保持節(jié)點(diǎn)總數(shù)和錨節(jié)點(diǎn)密度不變的情況下，通過調(diào)節(jié)節(jié)點(diǎn)的通信半徑大小，對(duì)比DV-Hop、PSO-DVHop和文中改進(jìn)算法的定位性能。圖5是通信半徑從5變化到50的過程中各個(gè)算法的平均定位誤差變化曲線。從中可見，當(dāng)節(jié)點(diǎn)的通信半徑在逐漸增加時(shí)，網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)中的跳數(shù)會(huì)發(fā)生改變，節(jié)點(diǎn)之間的跳數(shù)相應(yīng)減小，從而定位誤差將會(huì)減小。文中改進(jìn)算法能很好地降低定位誤差。

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

4 結(jié)束語

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

參考文獻(xiàn):

[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] 王小平,羅 軍,沈昌祥.三邊測(cè)量法的結(jié)果穩(wěn)定性研究[J].計(jì)算機(jī)工程與科學(xué),2012,34(6):12-17.

[4] 徐原博,鐘麗鴻,崔 洋,等.基于無線傳感器網(wǎng)絡(luò)的極大似然定位法的分析[J].傳感器與微系統(tǒng),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] 吳意樂,何 慶.基于改進(jìn)遺傳模擬退火算法的WSN路徑優(yōu)化算法[J].計(jì)算機(jī)應(yīng)用研究,2016,33(10):2959-2962.

[7] 陳星舟，廖明宏，林建華.基于粒子群優(yōu)化的無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位改進(jìn)[J].計(jì)算機(jī)應(yīng)用,2010,30(7):1736-1738.

[8] 李凌燕,杜永貴.改進(jìn)型粒子群優(yōu)化在WSNs節(jié)點(diǎn)定位中的應(yīng)用[J].計(jì)算機(jī)應(yīng)用與軟件,2014,31(4):69-72．

[9] 劉 逸.粒子群優(yōu)化算法的改進(jìn)及應(yīng)用研究[D].西安：西安電子科技大學(xué),2013.

[10] 林偉民,周寧寧.線性遞減的粒子群優(yōu)化算法[J].計(jì)算機(jī)技術(shù)與發(fā)展,2014,24(10):67-70.

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

[12] 潘大志,劉志斌.量子粒子群算法的改進(jìn)實(shí)現(xiàn)[J].計(jì)算機(jī)工程與應(yīng)用,2013,49(10):25-27.

[13] 王艷萍,張惠敏,劉新貴.基于量子粒子群優(yōu)化算法的無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)優(yōu)化[J].傳感器與微系統(tǒng),2010,29(2):32-34.

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

[15] 丁 穎,李 飛.自適應(yīng)收擴(kuò)系數(shù)的雙中心協(xié)作QPSO算法[J].計(jì)算機(jī)工程,2014,40(3):232-237.