無(wú)線傳感器網(wǎng)絡(luò)中改進(jìn)粒子群優(yōu)化DV-Hop算法的研究*

吳建鋒，徐振宇，蔣 震

(1.浙江樹人大學(xué)信息科技學(xué)院，浙江 杭州 310015.2.杭州電子科技大學(xué)電子信息學(xué)院，浙江 杭州 310018)

過(guò)去幾年中，位置信息在各種無(wú)線傳感器網(wǎng)絡(luò)應(yīng)用中發(fā)揮了重要作用。對(duì)許多研究者來(lái)說(shuō)，設(shè)計(jì)高效的定位算法是一項(xiàng)具有挑戰(zhàn)性的任務(wù)。

大多數(shù)以前的算法[3]假設(shè)節(jié)點(diǎn)部署在規(guī)則區(qū)域下，以獲得針對(duì)大多數(shù)應(yīng)用的滿意結(jié)果，但在現(xiàn)實(shí)世界場(chǎng)景中，往往區(qū)域是不規(guī)則的，帶有空洞和障礙物，因此一對(duì)傳感器節(jié)點(diǎn)之間的幾何距離并不總是與它們的跳數(shù)距離成正比，這破壞了許多現(xiàn)有的無(wú)測(cè)距定位算法的假設(shè)。

文獻(xiàn)[5]在DV-Hop算法中利用信號(hào)功率衰減修正跳數(shù)，但該方法易受到地形限制。文獻(xiàn)[5]提出了Rendered Path算法，利用網(wǎng)絡(luò)的幾何特征，以糾正曲折路徑的最短距離，但該算法并未考慮節(jié)點(diǎn)的分布密度。文獻(xiàn)[7]提出了Partiton weighting算法，該算法對(duì)錨節(jié)點(diǎn)隨機(jī)分配等級(jí)區(qū)域，以此區(qū)域加權(quán)修正距離，但該法在錨節(jié)點(diǎn)數(shù)量較少時(shí)效果并不理想。文獻(xiàn)[8]提出的DV-maxHop算法在計(jì)算中移除了一些離未知節(jié)點(diǎn)較遠(yuǎn)的錨節(jié)點(diǎn)，并沒有很好地利用錨節(jié)點(diǎn)的有效信息。

為了提高在不規(guī)則區(qū)域下的定位精度，本文在DV-Hop算法的基礎(chǔ)上進(jìn)一步研究，提出一種無(wú)線傳感器網(wǎng)絡(luò)中改進(jìn)粒子群優(yōu)化DV-Hop算法。

1 DV-Hop算法及不規(guī)則區(qū)域下誤差分析

1.1 DV-Hop算法

DV-Hop算法的實(shí)現(xiàn)主要有三個(gè)步驟:

第1步 估計(jì)傳感器節(jié)點(diǎn)和錨節(jié)點(diǎn)之間的最小跳數(shù)，所有錨節(jié)點(diǎn)將向網(wǎng)絡(luò)中的所有其他節(jié)點(diǎn)廣播包含跳數(shù)和坐標(biāo)的消息。跳數(shù)的值初始化為零，并在每一跳增加1。

第2步 估計(jì)每個(gè)錨節(jié)點(diǎn)的平均一跳距離:

式中:(xa，ya)，(xb，yb)分別是錨節(jié)點(diǎn)a和b的坐標(biāo)，hopab是a和b之間的跳數(shù)。

第3步 評(píng)估未知節(jié)點(diǎn)和錨節(jié)點(diǎn)之間的距離。

式中:dau是節(jié)點(diǎn)a和u之間的估計(jì)距離，HopSizea是未知節(jié)點(diǎn)u最近錨節(jié)點(diǎn)a的平均一跳，hopau是在第一步中獲得的節(jié)點(diǎn)a和u之間的跳數(shù)。

1.2 在不規(guī)則區(qū)域下的誤差分析

1.2.1 曲折路徑

由于障礙物和空洞的存在，會(huì)使得節(jié)點(diǎn)間通信的路徑發(fā)生曲折，這樣以簡(jiǎn)單的跳數(shù)乘以平均跳距估計(jì)的距離會(huì)被嚴(yán)重誤估，導(dǎo)致精度大幅度下降。如圖1(a)不規(guī)則區(qū)域所示:錨節(jié)點(diǎn)A1和未知節(jié)點(diǎn)U3之間由于障礙物的影響造成了嚴(yán)重的曲折路徑，跳數(shù)明顯增加，共有6跳，而兩個(gè)節(jié)點(diǎn)之間的實(shí)際距離并不大。在圖1(b)規(guī)則區(qū)域中U3到A1只需要3跳，不規(guī)則區(qū)域和規(guī)則區(qū)域下跳數(shù)相差3跳，這樣根據(jù)式(2)得到的估計(jì)距離誤差較大。

圖1 區(qū)域節(jié)點(diǎn)分布圖

1.2.2 未知節(jié)點(diǎn)坐標(biāo)計(jì)算方法不合理

使用最小二乘法計(jì)算每個(gè)未知節(jié)點(diǎn)的位置。假設(shè)區(qū)域內(nèi)有n個(gè)錨節(jié)點(diǎn)，未知節(jié)點(diǎn)的坐標(biāo)為(xu，yu)，根據(jù)錨節(jié)點(diǎn)和未知節(jié)點(diǎn)的位置關(guān)系可得:

將式(3)寫為線性方程組AX＝b的形式，并利用最小二乘法求解:

式中:

將式(2)得到的估計(jì)距離dau代入到式(4)中，由于dau在估計(jì)時(shí)就存在不同程度的誤差，故用該法求解坐標(biāo)時(shí)容易造成誤差累積。而在不規(guī)則區(qū)域中，類似這樣的曲折路徑有許多，即使定位算法精度再高也難以得到準(zhǔn)確的坐標(biāo)值，矩陣b的變化必然會(huì)引起解的波動(dòng)。其次，在求解X＝(ATA)-1ATb時(shí)，矩陣ATA可能存在不可逆的情況，導(dǎo)致最終無(wú)法獲得坐標(biāo)。此外，當(dāng)網(wǎng)絡(luò)中錨節(jié)點(diǎn)數(shù)量較少或錨節(jié)點(diǎn)分布不均勻時(shí)，也會(huì)對(duì)定位精度造成影響。

2 改進(jìn)粒子群優(yōu)化DV-Hop算法

在上述誤差分析的基礎(chǔ)上，本文提出了基于臨界值的改進(jìn)粒子群DV-Hop算法(Critical value and improved particle swarm algorithm of DV-Hop，CPDVHop)來(lái)提升不規(guī)則區(qū)域下的定位精度，在DV-Hop算法的跳數(shù)上設(shè)置了臨界值，對(duì)每跳距離進(jìn)行修正，并用改進(jìn)PSO代替最小二乘法優(yōu)化定位。

2.1 曲折路徑的跳數(shù)與跳距修正

由于不規(guī)則區(qū)域的影響，錨節(jié)點(diǎn)的不均勻分布，無(wú)線傳感器網(wǎng)絡(luò)中的跳數(shù)與平均跳距各不相同。往往有些未知節(jié)點(diǎn)到某一錨節(jié)點(diǎn)的跳數(shù)遠(yuǎn)大于正常跳數(shù)，為了合理地利用該錨節(jié)點(diǎn)的信息，本文設(shè)置了跳數(shù)臨界值限制最大跳數(shù)，并對(duì)這些超過(guò)臨界值的跳數(shù)相對(duì)應(yīng)的跳距進(jìn)行了修正，而對(duì)于那些小于跳數(shù)臨界值的信息則不做處理。以此使得未知節(jié)點(diǎn)與錨節(jié)點(diǎn)之間的估計(jì)距離更接近真實(shí)值，具體實(shí)現(xiàn)方法如下:

步驟1 計(jì)算未知節(jié)點(diǎn)與其最遠(yuǎn)錨節(jié)點(diǎn)z之間的最大跳數(shù)MaxHopu。

式中:N a是網(wǎng)絡(luò)中所有錨節(jié)點(diǎn)的集合，z是離未知節(jié)點(diǎn)u最遠(yuǎn)的錨節(jié)點(diǎn)。

步驟2 計(jì)算跳數(shù)臨界值T。當(dāng)未知節(jié)點(diǎn)u的最大跳數(shù)超過(guò)了臨界值T時(shí)，代表了最遠(yuǎn)錨節(jié)點(diǎn)z與未知節(jié)點(diǎn)u存在曲折路徑，需要修正，臨界值可以通過(guò)文獻(xiàn)[9]中的臨界值計(jì)算公式計(jì)算。

式中:R是節(jié)點(diǎn)的通信半徑，L是網(wǎng)絡(luò)區(qū)域邊長(zhǎng)，N為節(jié)點(diǎn)總數(shù)，ρ為錨定比，M是定位未知節(jié)點(diǎn)所需的最小錨節(jié)點(diǎn)數(shù)量。根據(jù)式(9)，T一般為3；

步驟3 計(jì)算跳距校正值Cau。錨節(jié)點(diǎn)通信半徑R與平均一跳距離的差值稱為最大跳躍距離誤差DistErrorMaxHop，由式(10)得到。

不同錨節(jié)點(diǎn)相對(duì)未知節(jié)點(diǎn)的位置不同，最大跳躍距離誤差也不同，這里引入加權(quán)思想，對(duì)最大跳躍距離誤差賦以權(quán)值，權(quán)值λau由式(11)求得。將最大跳躍距離誤差乘以最大跳數(shù)權(quán)值誤差得到校正值Cau，如等式(12)所示。

錨節(jié)點(diǎn)a和未知節(jié)點(diǎn)u之間的每條鏈路修改后的平均一跳為:

故不規(guī)則區(qū)域下的估計(jì)距離如式(14)所示:

2.2 改進(jìn)粒子群算法

PSO算法由Eberhart和Kennedy博士提出，其數(shù)學(xué)模型為:假設(shè)粒子種群數(shù)為N，每個(gè)粒子i包括一個(gè)D維坐標(biāo)和速度向量x i＝(xi1，xi2，…xiD)，v i＝(vi1，vi2，…viD)，粒子i的歷史最優(yōu)位置pb＝(pbi1，pbi2，…，pbiD)，全局最優(yōu)位置gb＝(gb1，gb2，…，gbD).粒子i的速度和位置更新公式為:

式中:iter表示迭代次數(shù)，c1、c2為學(xué)習(xí)因子，r1，r2為(0，1)上均勻分布的隨機(jī)數(shù)，w為慣性權(quán)重。

2.2.1 禁忌搜索

為了解決標(biāo)準(zhǔn)粒子群算法后期局部搜索能力差，收斂速度慢的問(wèn)題，提出一種改進(jìn)粒子群算法。首先由粒子群算法實(shí)現(xiàn)全局搜索，當(dāng)算法收斂速度明顯降低時(shí)停止粒子群算法的搜索，并將當(dāng)前解作為初始解進(jìn)行鄰域搜索。在鄰域搜索法中引入禁忌思想[10]，設(shè)置動(dòng)態(tài)禁忌表來(lái)禁忌短期內(nèi)找到的最優(yōu)解，避免迭代陷入局部最優(yōu)。當(dāng)在搜索過(guò)程中尋得的解在禁忌表中，則重新生成解。迭代過(guò)程中，只有不在禁忌表中的優(yōu)質(zhì)解才能作為下一次迭代的初始解。

利用禁忌搜索算法對(duì)當(dāng)前解的鄰域做進(jìn)一步搜索，當(dāng)搜索次數(shù)達(dá)到一定次數(shù)，而最優(yōu)解仍未改變時(shí)，擴(kuò)大鄰域搜索半徑，并增加鄰域解數(shù)目。當(dāng)鄰域半徑擴(kuò)大數(shù)次后，仍未找到比當(dāng)前最優(yōu)解更優(yōu)質(zhì)的解，則表明該解為當(dāng)前區(qū)域的最優(yōu)解。

鄰域解從當(dāng)前解的鄰域范圍rd內(nèi)隨機(jī)生成，對(duì)于鄰域解各維度值均滿足:

式中:x′d為鄰域解的第d維值，xd為當(dāng)前解的第d維值。

禁忌對(duì)象以目標(biāo)函數(shù)周圍區(qū)域εi作為禁忌對(duì)象，如式(18)所示:

式中:f(x)、f(x′)為當(dāng)前解、鄰域解的目標(biāo)函數(shù)值。

2.2.2 權(quán)重改進(jìn)

ω為控制粒子群算法全局索搜能力和局部尋優(yōu)能力的主要因素，目前研究采用較多的為線性遞減慣性權(quán)重策略[11]，通過(guò)調(diào)整慣性權(quán)值來(lái)避免陷入局部搜索，本文設(shè)置的慣性權(quán)重值如式(19)表示:

式中:wmax和wmin分別表示最大和最小慣性權(quán)值，并且通常設(shè)為0.9和0.4。itermax為最大允許迭代次數(shù)，iter表示當(dāng)前迭代次數(shù)，α為(0，1)之間的隨機(jī)數(shù)。

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

將未知節(jié)點(diǎn)到錨節(jié)點(diǎn)的實(shí)際距離與估計(jì)距離的誤差作為目標(biāo)函數(shù):

式中:n為錨節(jié)點(diǎn)數(shù)量，(xns，yns)為最優(yōu)解的坐標(biāo)，(xa，ya)為第a個(gè)已知錨節(jié)點(diǎn)的坐標(biāo)，dau為兩者之間的距離。fitness值越小，則表示該位置越接近真實(shí)位置。

2.3 CPDV-Hop算法過(guò)程

①在目標(biāo)區(qū)域隨機(jī)部署傳感器節(jié)點(diǎn)，并通過(guò)式(2)得到估計(jì)距離。

②根據(jù)式(7)~(8)得到最遠(yuǎn)錨節(jié)點(diǎn)的跳數(shù)與臨界值T比較，判斷是否存在曲折路徑并由式(14)得到修正后的估計(jì)距離。

③設(shè)置改進(jìn)粒子群算法相關(guān)參數(shù)學(xué)習(xí)因子c1、c2，權(quán)重最大、最小值wmax和wmin，種群數(shù)N，最大迭代次數(shù)itermax，鄰域范圍ri，禁忌區(qū)域εi。

④初始化粒子群。隨機(jī)產(chǎn)生粒子的速度v i和位置xi，并設(shè)置當(dāng)前最優(yōu)位置pb和歷史最優(yōu)位置gb，迭代次數(shù)iter＝0。

⑤令iter＝iter+1，并根據(jù)式(15)和(16)更新粒子速度和位置。

⑥判斷是否滿足改進(jìn)PSO算法的終止條件(即達(dá)到最大迭代次數(shù)itermax)，如果滿足終止條件則停止迭代，返回最優(yōu)解，否則進(jìn)行⑤。

⑦利用⑥中得到的最優(yōu)解進(jìn)行禁忌搜索，如果禁忌搜索得到的最優(yōu)值優(yōu)于當(dāng)前最優(yōu)值且不在禁忌表中，則更新最優(yōu)值；若持續(xù)找不到最優(yōu)解，則擴(kuò)大鄰域半徑，同時(shí)增加鄰域解的個(gè)數(shù)繼續(xù)搜索。

⑧判斷當(dāng)前解是否滿足禁忌搜索迭代結(jié)束條件(達(dá)到最大迭代次數(shù))，若不滿足則返回⑦。反之，輸出最優(yōu)解。

3 算法性能分析

3.1 仿真參數(shù)與實(shí)驗(yàn)環(huán)境

為了驗(yàn)證改進(jìn)算法的定位性能，在不同的實(shí)驗(yàn)條件下對(duì)各算法性能進(jìn)行了對(duì)比論證。

采用MATLAB R2016a對(duì)算法進(jìn)行仿真，在二維200 m×200 m區(qū)域部署了200個(gè)傳感器節(jié)點(diǎn)，假設(shè)所有傳感器節(jié)點(diǎn)都具有相同的半徑R。其半徑內(nèi)的每個(gè)傳感器節(jié)點(diǎn)都能夠直接與其所有相鄰節(jié)點(diǎn)通信。不規(guī)則區(qū)域布置為“C”、“O”、“S”型，如圖2所示。本文算法的參數(shù)設(shè)置為:學(xué)習(xí)因子c1＝c2＝2，粒子種群N＝50，最大迭代次數(shù)itermax為50。wmax＝0.9，wmin＝0.4，鄰域范圍ri＝0.01，禁忌區(qū)域εi＝0.1。

圖2 3種不規(guī)則區(qū)域下的傳感器節(jié)點(diǎn)定位

采用歸一化定位誤差作為定位誤差的評(píng)價(jià)指標(biāo):

式中:(xi，yi)為未知節(jié)點(diǎn)的實(shí)際位置，為未知節(jié)點(diǎn)的估計(jì)位置，N為節(jié)點(diǎn)總數(shù)，R為通信半徑。

3.2 仿真結(jié)果及分析

圖3是不同定位區(qū)域下，節(jié)點(diǎn)通信半徑對(duì)定位性能的影響。設(shè)置總節(jié)點(diǎn)數(shù)為200，錨定比為7.5%。從圖中可以看出，經(jīng)典DV-Hop算法在“C”型網(wǎng)絡(luò)、“O”型網(wǎng)絡(luò)、“S”型網(wǎng)絡(luò)下，定位誤差較大，尤其是在“S”型網(wǎng)絡(luò)下，由于多個(gè)曲折路徑的存在，定位誤差始終高于“C”型、“O”型網(wǎng)絡(luò)，而“O”型網(wǎng)絡(luò)接近規(guī)則區(qū)域，相較于其他網(wǎng)絡(luò)，受到曲折路徑的影響較小，定位精度相對(duì)較高。在通信半徑為25時(shí)，由于未知節(jié)點(diǎn)附近可通信得節(jié)點(diǎn)數(shù)量少，且離未知節(jié)點(diǎn)很遠(yuǎn)的錨節(jié)點(diǎn)，跳數(shù)值遠(yuǎn)高于正常值，估計(jì)距離過(guò)大，故歸一化定位精度不高，三種網(wǎng)絡(luò)模型下歸一化定位誤差都大于1.5。而在通信半徑R＞40時(shí)有較好的表現(xiàn)，因?yàn)殡S著通信半徑的增大，通信范圍內(nèi)的節(jié)點(diǎn)增多，跳數(shù)值趨于正常范圍。而本文提出的CPDV-Hop算法意在削弱由于曲折半徑的存在而導(dǎo)致的估計(jì)距離增大，從圖中明顯可見，本文改進(jìn)算法，在不規(guī)則區(qū)域下有較好的適用性。

圖3 3種不規(guī)則區(qū)域下節(jié)點(diǎn)通信半徑對(duì)定位性能的影響

圖4~圖6分別是“C”型、“O”型、“S”型網(wǎng)絡(luò)下，不同錨定比，不同節(jié)點(diǎn)總數(shù)量對(duì)定位性能的影響，其中默認(rèn)通信半徑為35 m，節(jié)點(diǎn)數(shù)量為200，錨定比為7.5%。并與經(jīng)典DV-Hop，文獻(xiàn)[8]的DVmaxHop算法，文獻(xiàn)[9]的RDV-Hop算法定位性能進(jìn)行對(duì)比。

圖4 “C“型網(wǎng)絡(luò)下節(jié)點(diǎn)數(shù)量和錨定比對(duì)定位性能能影響的比較

圖6 “S”型網(wǎng)絡(luò)下節(jié)點(diǎn)數(shù)量和錨定比對(duì)定位性能能影響的比較

從圖4中可以看出，在“C”型網(wǎng)絡(luò)下，由于未知節(jié)點(diǎn)與錨節(jié)點(diǎn)之間存在曲折路徑，估計(jì)距離誤差增大，現(xiàn)有算法的定位精度不高。但當(dāng)錨節(jié)點(diǎn)數(shù)和節(jié)點(diǎn)數(shù)量增加時(shí)，四種算法的定位誤差均減小，主要是由于錨節(jié)點(diǎn)的增多使得未知節(jié)點(diǎn)能得到更多有效的跳距信息，而節(jié)點(diǎn)總數(shù)的增多會(huì)減少最小跳數(shù)。本文提出的CPDV-Hop算法相較于經(jīng)典DV-Hop算法、DV-maxHop算法、RDV-Hop算法，在不同節(jié)點(diǎn)總數(shù)下，定位誤差平均減小了53.9%、29.6%和19.7%。在不同錨定比下，定位誤差平均減小了48.7%、7.9%和24.4%。

從圖5中可以看出，d“O”型網(wǎng)絡(luò)下，由于存在較少的曲折路徑，總體的估計(jì)距離誤差不大，進(jìn)而定位誤差也不大。隨著節(jié)點(diǎn)總數(shù)的增加，節(jié)點(diǎn)間的距離減小，當(dāng)達(dá)到200個(gè)節(jié)點(diǎn)總數(shù)時(shí)，定位誤差減小幅度趨于平緩。錨節(jié)點(diǎn)數(shù)增加到15%時(shí)，未知節(jié)點(diǎn)得到的有效信息達(dá)到飽和，定位誤差減小趨于平緩。在不同節(jié)點(diǎn)總數(shù)時(shí)，CPDV-Hop算法相較于DV-Hop算法、DV-maxHop算法、RDV-Hop算法，定位誤差平均減小了74.1%、36.4%和18.2%。在不同錨定比情況下，定位誤差平均減少了57.8%、18.3%和30.5%。

圖5 “O“型網(wǎng)絡(luò)下節(jié)點(diǎn)數(shù)量和錨定比對(duì)定位性能影響的比較

從圖6中可以看出，在“S”型網(wǎng)絡(luò)下，整體定位精度不佳，且在改變節(jié)點(diǎn)總數(shù)和錨定比時(shí)，定位誤差減小緩慢，這是由于在該網(wǎng)絡(luò)下存在較多曲折路徑，使得未知節(jié)點(diǎn)與最遠(yuǎn)錨節(jié)點(diǎn)之間的跳數(shù)明顯增加，從而導(dǎo)致估計(jì)距離與實(shí)際距離的偏差較大，最終導(dǎo)致整體定位效果不佳。本文提出的CPDV-Hop算法在跳數(shù)階段設(shè)置了臨界值并對(duì)跳數(shù)進(jìn)行了修正，定位精度優(yōu)于DV-Hop算法、DV-maxHop算法、RDVHop算法，在不同節(jié)點(diǎn)總數(shù)時(shí)，定位誤差分別減少了51.9%、31.0%和38.5%。在不同錨定比情況下，定位誤差分別減少了45.5%、14.6%和24.6%。

4 結(jié)束語(yǔ)

本文對(duì)DV-Hop算法在不規(guī)則區(qū)域下的定位誤差進(jìn)行了分析，并提出了改進(jìn)粒子群DV-Hop算法以優(yōu)化無(wú)線傳感器網(wǎng)絡(luò)定位精度，算法主要做了以下幾個(gè)方面的改進(jìn):①根據(jù)不規(guī)則區(qū)域設(shè)定跳數(shù)臨界值，并判斷是否有曲折路徑。②利用最大跳數(shù)MaxHop修正距離，使得估計(jì)距離更加接近真實(shí)情況。③引入改進(jìn)粒子群算法代替最小二乘法對(duì)定位結(jié)果進(jìn)行優(yōu)化。仿真表明，在不規(guī)則區(qū)域下，CPDVHop比DV-Hop算法、DV-maxHop算法和RDV-Hop算法定位精度更高。