吳建鋒，徐振宇，蔣 震

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

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

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

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

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

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

1.1 DV-Hop算法

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

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

第2步 估計每個錨節(jié)點的平均一跳距離:

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

第3步 評估未知節(jié)點和錨節(jié)點之間的距離。

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

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

1.2.1 曲折路徑

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

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

1.2.2 未知節(jié)點坐標計算方法不合理

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

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

式中:

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

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

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

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

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

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

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

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

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

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

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

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

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

2.2 改進粒子群算法

PSO算法由Eberhart和Kennedy博士提出，其數(shù)學(xué)模型為:假設(shè)粒子種群數(shù)為N，每個粒子i包括一個D維坐標和速度向量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)上均勻分布的隨機數(shù)，w為慣性權(quán)重。

2.2.1 禁忌搜索

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

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

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

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

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

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

2.2.2 權(quán)重改進

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

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

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

將未知節(jié)點到錨節(jié)點的實際距離與估計距離的誤差作為目標函數(shù):

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

2.3 CPDV-Hop算法過程

①在目標區(qū)域隨機部署傳感器節(jié)點，并通過式(2)得到估計距離。

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

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

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

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

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

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

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

3 算法性能分析

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

為了驗證改進算法的定位性能，在不同的實驗條件下對各算法性能進行了對比論證。

采用MATLAB R2016a對算法進行仿真，在二維200 m×200 m區(qū)域部署了200個傳感器節(jié)點，假設(shè)所有傳感器節(jié)點都具有相同的半徑R。其半徑內(nèi)的每個傳感器節(jié)點都能夠直接與其所有相鄰節(jié)點通信。不規(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é)點定位

采用歸一化定位誤差作為定位誤差的評價指標:

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

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

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

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

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

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

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

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

從圖5中可以看出，d“O”型網(wǎng)絡(luò)下，由于存在較少的曲折路徑，總體的估計距離誤差不大，進而定位誤差也不大。隨著節(jié)點總數(shù)的增加，節(jié)點間的距離減小，當達到200個節(jié)點總數(shù)時，定位誤差減小幅度趨于平緩。錨節(jié)點數(shù)增加到15%時，未知節(jié)點得到的有效信息達到飽和，定位誤差減小趨于平緩。在不同節(jié)點總數(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é)點數(shù)量和錨定比對定位性能影響的比較

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

4 結(jié)束語

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