基于跳數(shù)修正的DV－Hop改進(jìn)算法

韓 震，肖鐵軍

(江蘇大學(xué)計(jì)算機(jī)科學(xué)與通信工程學(xué)院，江蘇鎮(zhèn)江 212013)

無線傳感器網(wǎng)絡(luò)［1］由大量廉價(jià)微型傳感器節(jié)點(diǎn)組成，通過無線通信方式形成一個(gè)多跳的自組織網(wǎng)絡(luò)系統(tǒng)，用于感知、采集和處理網(wǎng)絡(luò)中感知對象的信息，現(xiàn)已廣泛應(yīng)用于環(huán)境、醫(yī)療、軍事等領(lǐng)域。

定位技術(shù)作為無線傳感器網(wǎng)絡(luò)的核心技術(shù)之一，可分為基于測距(Range－Based)和與距離無關(guān)(Range－Free)的定位算法［2］。基于測距的定位算法需要獲取節(jié)點(diǎn)間距離或角度信息，定位精度較高，但對節(jié)點(diǎn)硬件要求也較高;與距離無關(guān)的定位算法依賴網(wǎng)絡(luò)連通度來計(jì)算未知節(jié)點(diǎn)與信標(biāo)節(jié)點(diǎn)間距離實(shí)現(xiàn)定位，定位精度不如基于測距的定位算法，但其無需額外硬件，適用于對定位精度要求不高且成本敏感的場合。與距離無關(guān)的定位算法應(yīng)用廣泛，DV－Hop(Distance Vector－Hop)算法就是其中的一種典型算法。

針對DV－Hop算法定位精度不高的問題，相關(guān)研究已取得了一些成果。文獻(xiàn)［3］采用最小二乘法修正信標(biāo)節(jié)點(diǎn)間的平均跳距，算法的計(jì)算量較大;文獻(xiàn)［4］將平均每跳距離取平均作為未知節(jié)點(diǎn)平均每跳距離，但不能解決節(jié)點(diǎn)間分布不均帶來的估算誤差;文獻(xiàn)［5～6］使用RSSI(Received Signal Strength Indicator)加權(quán)修正跳數(shù)，但對于RSSI值依賴較大，產(chǎn)生誤差;文獻(xiàn)［7］采用跨境返回測距機(jī)制，通過判斷兩節(jié)點(diǎn)的位置關(guān)系將節(jié)點(diǎn)歸類以減少定位誤差，定位精度提升不明顯;文獻(xiàn)［8］對跳距細(xì)化并使用RSSI比值對跳數(shù)加權(quán)修正，但使用RSSI測距模型需要較大的計(jì)算量;文獻(xiàn)［9］引入RSSI比值修正跳數(shù)，定位精度需進(jìn)一步提高;以上算法對定位精度有一定提高，但有的計(jì)算量較大，有的未能考慮節(jié)點(diǎn)分布的可能情況。本文針對跳數(shù)進(jìn)行水平及垂直修正，使跳數(shù)信息盡可能地反應(yīng)節(jié)點(diǎn)真實(shí)距離關(guān)系，同時(shí)分析兩節(jié)點(diǎn)之間的距離導(dǎo)致下一節(jié)點(diǎn)分布的可能性情況，采用修正角度優(yōu)化節(jié)點(diǎn)間跳數(shù)，提高定位精度的同時(shí)降低計(jì)算量，最后仿真驗(yàn)證改進(jìn)算法性能。

1 DV－Hop算法

DV－Hop算法［10］分為以下3個(gè)階段:

(1)計(jì)算信標(biāo)節(jié)點(diǎn)到其他節(jié)點(diǎn)的最小跳數(shù):每個(gè)信標(biāo)節(jié)點(diǎn)向鄰居節(jié)點(diǎn)廣播自身位置信息的分組。接收節(jié)點(diǎn)記錄到每個(gè)信標(biāo)節(jié)點(diǎn)的最小跳數(shù)，忽略來自同一信標(biāo)節(jié)點(diǎn)的較大跳數(shù)分組，此時(shí)跳數(shù)加1，并轉(zhuǎn)發(fā)分組信息。通過這個(gè)方法，網(wǎng)絡(luò)中的節(jié)點(diǎn)獲取到每個(gè)信標(biāo)節(jié)點(diǎn)的最小跳數(shù)。

(2)計(jì)算未知節(jié)點(diǎn)到信標(biāo)節(jié)點(diǎn)的實(shí)際跳段距離:信標(biāo)節(jié)點(diǎn)根據(jù)式(1)計(jì)算平均每跳距離

式(1)中，(xi，yi)，(xj，yj)分別是信標(biāo)節(jié)點(diǎn) i，j的真實(shí)坐標(biāo);hij是信標(biāo)節(jié)點(diǎn)i，j的最小跳數(shù);HopSizei是信標(biāo)節(jié)點(diǎn)i的平均每跳距離。

未知節(jié)點(diǎn)i收到最近的平均每跳距離校正值后，計(jì)算到信標(biāo)節(jié)點(diǎn)j的跳段距離dij如下

(3)利用三邊測量法或極大似然估計(jì)法計(jì)算位置:未知節(jié)點(diǎn)獲取3個(gè)跳段距離，使用三邊測量法，3個(gè)以上跳段距離使用極大似然估計(jì)法得出自身位置信息。

2 DV－Hop算法改進(jìn)

傳統(tǒng)DV－Hop算法第一階段獲取節(jié)點(diǎn)間的最小跳數(shù)，然后依靠最小跳數(shù)計(jì)算出信標(biāo)節(jié)點(diǎn)平均每條距離，最后未知節(jié)點(diǎn)使用最小跳數(shù)計(jì)算到信標(biāo)節(jié)點(diǎn)的跳段距離?？梢?，跳數(shù)信息在DV－Hop算法中占據(jù)重要的位置，跳數(shù)信息的準(zhǔn)確性直接影響到未知節(jié)點(diǎn)定位精度，但傳統(tǒng)算法中，節(jié)點(diǎn)通信范圍內(nèi)的所有節(jié)點(diǎn)間跳數(shù)都是1跳，不能較好地反應(yīng)出相鄰節(jié)點(diǎn)實(shí)際距離關(guān)系，由此獲取的最小跳數(shù)信息對實(shí)際平均每跳距離產(chǎn)生誤差，最終影響未知節(jié)點(diǎn)的定位精度值。如圖1所示。

圖1 節(jié)點(diǎn)分布示意圖

圖1中，節(jié)點(diǎn)1、2、3水平分布，跳數(shù) h12和 h13分別是1跳和2跳，但由于水平分布節(jié)點(diǎn)密度不均勻，實(shí)際距離d13并不一定是d12的2倍關(guān)系;節(jié)點(diǎn)3、4、5可以是水平與垂直分布的結(jié)果，跳數(shù)h35是跳數(shù)h34與h45之和，實(shí)際距離d35并非d34與d45之和，兩者存在一定的誤差。

針對圖1所示情況，本文引入RSSI量化跳數(shù)，進(jìn)行水平修正，在水平修正的情況下，引入修正角度，進(jìn)行垂直修正。

2.1 水平修正

2.1.1 RSSI測距模型

無線傳感器網(wǎng)絡(luò)中應(yīng)用最廣泛的信號傳播損耗模型是 Shadowing 模型［11］，表達(dá)式如下

式(3)中，d0為參考距離;d為接收端到發(fā)送端的距離;Pr(d)為距離為d時(shí)接收端的平均接收功率;β為實(shí)際環(huán)境路徑損耗因子，通常取值范圍在2～6之間;Xσ為遮蔽因子，均值為0，均方差為 σ的正態(tài)隨機(jī)變量。

Shadowing模型描述了接收功率和信號傳播距離的關(guān)系，通常接收端距離發(fā)射端越遠(yuǎn)，接收到的功率越小。一般情況下，接收端可直接讀取相應(yīng)的RSSI值，無需額外的硬件。

2.1.2 跳數(shù)水平修正

節(jié)點(diǎn)通信半徑R范圍內(nèi)的節(jié)點(diǎn)跳數(shù)都是1跳，該跳數(shù)并不能較好地反應(yīng)出節(jié)點(diǎn)間實(shí)際距離大小關(guān)系，由此產(chǎn)生較大的測距誤差。本文根據(jù)接收到的鄰居節(jié)點(diǎn)RSSI值對每一跳進(jìn)行分段細(xì)化，有助于提高節(jié)點(diǎn)定位精度。

假設(shè)節(jié)點(diǎn)通信半徑為R，將水平修正跳數(shù)h按照相鄰節(jié)點(diǎn)間實(shí)際距離L劃分成n段，其中n的取值為2k，i為實(shí)際距離L所對應(yīng)的分段區(qū)間數(shù)。水平修正方式如下

式(4)中相鄰節(jié)點(diǎn)間實(shí)際距離L可以通過RSSI測距模型計(jì)算。然而，計(jì)算距離L會產(chǎn)生較大的計(jì)算量，節(jié)點(diǎn)的RSSI值可直接讀取，將分段距離轉(zhuǎn)換成相應(yīng)的RSSI值可大幅降低計(jì)算量，可得式(5)和式(6)如下

式(5)中，參考距離設(shè)置為節(jié)點(diǎn)通信半徑R，可獲取距離發(fā)射端L的接收功率P(l)dB;式(6)中，將各個(gè)分段距離代入式(5)獲取各個(gè)分段的接收功率，比較接收節(jié)點(diǎn)獲取的RSSI(L)值，可獲取對應(yīng)的分段區(qū)間數(shù)i，代入式(4)便可獲取水平修正跳數(shù)h。可制成分段區(qū)間對照表1，未知節(jié)點(diǎn)直接獲取RSSI值后，從區(qū)間1開始依次查找比對表1中接收功率，獲取對應(yīng)的水平修正跳數(shù)，可減少修正過程中的計(jì)算量。

表1 分段區(qū)間對照表

水平修正后的跳數(shù)信息允許原DV－Hop算法1跳數(shù)量變成小數(shù)，并不一定是整數(shù)，可提高跳數(shù)信息的準(zhǔn)確性，為垂直修正提供基礎(chǔ)。

2.2 垂直修正

水平修正跳數(shù)后，只是修正了兩節(jié)點(diǎn)間跳數(shù)，未能考慮到整個(gè)網(wǎng)絡(luò)中節(jié)點(diǎn)分布相關(guān)聯(lián)的可能情況，需進(jìn)一步用來修正非相鄰節(jié)點(diǎn)之間的跳數(shù)信息，如圖2所示。

圖2 節(jié)點(diǎn)垂直修正分布示意圖

圖2中，節(jié)點(diǎn)1和2之間的水平修正跳數(shù)為a，節(jié)點(diǎn)2和3之間的水平修正跳數(shù)為b，節(jié)點(diǎn)1和3之間的跳數(shù)c與a、b之和存在一定誤差，引入a、b之間的修正夾角θ，經(jīng)過垂直修正后，節(jié)點(diǎn)1和3之間的跳數(shù)c如下所示

修正夾角θ的取值按照節(jié)點(diǎn)分布的概率取值，如圖3所示，節(jié)點(diǎn)A和B是兩圓圓心，兩圓相距r，節(jié)點(diǎn)通信半徑相同，均為R，即兩圓半徑，假設(shè)節(jié)點(diǎn)A通過節(jié)點(diǎn)B連通的節(jié)點(diǎn)為節(jié)點(diǎn)C，這節(jié)點(diǎn)C必定在圖3陰影部分，同時(shí)，陰影部分上下兩半是對稱的，只需考慮上半部分即可?？紤]到節(jié)點(diǎn)分布是隨機(jī)的，所以，修正角度θ應(yīng)該可以平分上半部分陰影區(qū)域面積。

圖3 修正夾角示意圖

修正角度θ的計(jì)算方法如式(8)所示。式(8)中，S1/2為圖3中陰影上半部分面積，可通過定積分求取，(π－θ)R2表示圓心角為(π－θ)的扇形BFG面積的2倍，(R－r)2tan(π－θ)為三角形BDE面積的2倍，此處計(jì)算取近似值，其中線段BF平分陰影區(qū)域面積，點(diǎn)F、G在圓上，線段ED為以A為圓心的圓切線，交BC與點(diǎn)E。

表2 修正角度對照表

r取值為iR/n，其中i為分段區(qū)間數(shù)，R為節(jié)點(diǎn)通信半徑，n為分段數(shù)量。r/R的比值為i/n，取值對應(yīng)水平修正跳數(shù)的分段區(qū)間。表2為r/R取值與修正角度θ的關(guān)系，其中分段數(shù)量n為8，修正角度單位rad。

接收節(jié)點(diǎn)根據(jù)發(fā)送節(jié)點(diǎn)的RSSI值，計(jì)算相應(yīng)分段區(qū)間，獲取距離比值r/R，通過查找表2，得到對應(yīng)修正角度。

2.3 改進(jìn)算法具體步驟

改進(jìn)算法具體步驟如下:

(1)計(jì)算信標(biāo)節(jié)點(diǎn)到其他節(jié)點(diǎn)的修正跳數(shù)。信標(biāo)節(jié)點(diǎn)向鄰居節(jié)點(diǎn)廣播信息分組，每個(gè)節(jié)點(diǎn)維護(hù)一組信息表{Xi，Yi，Hi，hi}，其中(Xi，Yi)為信標(biāo)節(jié)點(diǎn) i的位置信息，Hi為原DV－Hop算法中的最小跳數(shù)，hi為修正跳數(shù)，Hi、hi初始值均為0。接收節(jié)點(diǎn)記錄到每個(gè)信標(biāo)節(jié)點(diǎn)的最小跳數(shù)Hi，忽略來自同一信標(biāo)節(jié)點(diǎn)的較大跳數(shù)分組，此時(shí)跳數(shù)Hi加1，并對來自發(fā)送端的跳數(shù)進(jìn)行水平及垂直修正，當(dāng)然，對于Hi=1，即只有1跳的情況，只需進(jìn)行水平修正，于此同時(shí)轉(zhuǎn)發(fā)分組信息。通過這種方法，每個(gè)節(jié)點(diǎn)獲得原DV－Hop算法中最小跳數(shù)的同時(shí)，也獲得了最小跳數(shù)的修正值。

(2)計(jì)算未知節(jié)點(diǎn)到信標(biāo)節(jié)點(diǎn)的實(shí)際跳段距離。每個(gè)信標(biāo)節(jié)點(diǎn)需要獲取平均每跳距離，按照式(1)計(jì)算即可，其中，hij不再是原算法中信標(biāo)節(jié)點(diǎn)i，j的最小跳數(shù)，而是最小跳數(shù)的修正值;信標(biāo)節(jié)點(diǎn)j廣播平均每跳距離HopSizej，未知節(jié)點(diǎn)i收到該信息后，計(jì)算到信標(biāo)節(jié)點(diǎn)j的實(shí)際跳段距離dij，如式(9)所示

其中，HopSizej是對應(yīng)信標(biāo)節(jié)點(diǎn)的平均每跳距離，不再是原算法中距離未知節(jié)點(diǎn)最近的平均每跳距離，這有助于在跳數(shù)修正的基礎(chǔ)上提高定位精度;hj為未知節(jié)點(diǎn)到信標(biāo)節(jié)點(diǎn)j最小跳數(shù)的修正值。

(3)利用三邊測量法或極大似然估計(jì)法計(jì)算自身位置信息。未知節(jié)點(diǎn)獲取至少3個(gè)到各個(gè)信標(biāo)節(jié)點(diǎn)的跳段距離后，使用三邊測量法或者極大似然估計(jì)法計(jì)算出自身的位置信息，其中獲取3個(gè)跳段距離的使用三邊測量法，3個(gè)以上使用極大似然估計(jì)法。

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

為驗(yàn)證基于跳數(shù)修正的改進(jìn)算法的性能，采用Matlab 7.11.0進(jìn)行仿真實(shí)驗(yàn)，對比改進(jìn)算法與原算法的定位精度，并對仿真結(jié)果進(jìn)行分析。

無線傳感器網(wǎng)絡(luò)的仿真環(huán)境如下:節(jié)點(diǎn)共100個(gè);所有節(jié)點(diǎn)隨機(jī)分布在100 m×100 m的正方形區(qū)域;正方形區(qū)域左下角為坐標(biāo)原點(diǎn)(0，0)，右上角坐標(biāo)為(100，100);信標(biāo)節(jié)點(diǎn)與未知節(jié)點(diǎn)的通信半徑相同且可調(diào)。為消除定位過程中節(jié)點(diǎn)隨機(jī)分布產(chǎn)生的誤差，仿真數(shù)據(jù)均為相同條件下運(yùn)行100次的平均值。

無線傳感器網(wǎng)絡(luò)中定位精度是定位算法的一個(gè)重要指標(biāo)，定位誤差Error為

式(10)中，n為未知節(jié)點(diǎn)個(gè)數(shù);R為節(jié)點(diǎn)通信半徑;(xrel，yrel)為未知節(jié)點(diǎn)實(shí)際坐標(biāo);(xest，yest)為未知節(jié)點(diǎn)估計(jì)坐標(biāo)。

在不改變節(jié)點(diǎn)總數(shù)的情況下，分3種網(wǎng)絡(luò)情況進(jìn)行仿真，與原算法進(jìn)行比較:(1)信標(biāo)節(jié)點(diǎn)比例不變，調(diào)整通信半徑。(2)通信半徑不變，調(diào)整信標(biāo)節(jié)點(diǎn)比例。(3)固定信標(biāo)節(jié)點(diǎn)比例，調(diào)整節(jié)點(diǎn)總數(shù)。

3.1 調(diào)整通信半徑

在100 m×100 m正方形區(qū)域內(nèi)，隨機(jī)分布100個(gè)節(jié)點(diǎn)，信標(biāo)節(jié)點(diǎn)比例為0.3，在其他條件不變的情況下，調(diào)整節(jié)點(diǎn)通信半徑，對應(yīng)通信半徑與定位精度關(guān)系圖，如圖4所示，其中通信半徑為R，n表示改進(jìn)算法中水平修正分段數(shù)量。

如圖4所示，隨著通信半徑的增加，DV－Hop算法、改進(jìn)算法以及文獻(xiàn)［9］算法的定位誤差都呈下降趨勢，改進(jìn)算法的定位誤差比原算法明顯降低，尤其是改進(jìn)算法中分段數(shù)量較大的情況下。通信半徑為20 m時(shí)，通過仿真可發(fā)現(xiàn)，節(jié)點(diǎn)間最小跳數(shù)在3～8跳的比例為在70%左右，其中最小跳數(shù)最多的為6跳，由于節(jié)點(diǎn)隨機(jī)分布造成情況復(fù)雜，造成改進(jìn)算法、原算法、文獻(xiàn)［9］算法的定位精度都不高;通信半徑為25 m時(shí)，圖4所示算法定位精度明顯提高;通信半徑達(dá)到30 m時(shí)，改進(jìn)算法和原算法定位誤差趨于穩(wěn)定，改進(jìn)算法(n=8)定位精度比原算法提高了約10%，相比文獻(xiàn)［9］算法定位提高3%左右，改進(jìn)算法(n=4)此時(shí)與文獻(xiàn)［9］算法的定位誤差還沒有明顯的區(qū)別，在隨后半徑增大的過程中才出現(xiàn)一定的差距。在趨于穩(wěn)定的情況下，改進(jìn)算法(n=8)的定位精度比改進(jìn)算法(n=4)的定位精度高出約2%，表明增大分段數(shù)量有助于提高定位精度。可以看出，在其他條件不變的情況下，調(diào)整通信半徑，改進(jìn)算法(n=8)與原算法和文獻(xiàn)［9］算法有明顯的優(yōu)勢。

圖4 通信半徑與定位精度關(guān)系圖

圖5是改進(jìn)算法(n=8)在調(diào)整通信半徑過程中，將通信半徑設(shè)為30 m時(shí)的定位誤差圖，節(jié)點(diǎn)位置隨機(jī)分布，星號表示信標(biāo)節(jié)點(diǎn)，空心圓表示未知節(jié)點(diǎn)位置估計(jì)值，直線表示未知節(jié)點(diǎn)位置估計(jì)值與真實(shí)位置的誤差。如圖5所示，未知節(jié)點(diǎn)在中心位置的估計(jì)誤差比邊緣位置小。

圖5 改進(jìn)算法(n=8，R=30 m)定位誤差圖

3.2 調(diào)整信標(biāo)節(jié)點(diǎn)比例

同樣在在100 m×100 m正方形區(qū)域內(nèi)，隨機(jī)分布100個(gè)節(jié)點(diǎn)，選取節(jié)點(diǎn)通信半徑30 m，在其他條件不變的情況下，調(diào)整信標(biāo)節(jié)點(diǎn)的比例Ratio，對應(yīng)信標(biāo)節(jié)點(diǎn)比例與定位精度的關(guān)系，如圖6所示。

圖6 信標(biāo)節(jié)點(diǎn)比例與定位精度關(guān)系圖

如圖6所示，隨著信標(biāo)節(jié)點(diǎn)比例的增加，DV－Hop算法和改進(jìn)算法的定位誤差都呈下降的趨勢，改進(jìn)算法的定位誤差比原算法明顯低。信標(biāo)節(jié)點(diǎn)比例達(dá)到0.2之前，改進(jìn)算法、原算法以及文獻(xiàn)［9］算法定位精度都不高，但隨著信標(biāo)節(jié)點(diǎn)比例的增加，定位精度明顯。信標(biāo)節(jié)點(diǎn)比例達(dá)到0.25時(shí)，改進(jìn)算法、原算法以及文獻(xiàn)［9］算法的定位誤差趨于穩(wěn)定，此時(shí)，改進(jìn)算法(n=4)的定位精度比原算法提高了約5%，與文獻(xiàn)［9］算法定位精度相當(dāng)，改進(jìn)算法(n=8)的定位精度比原算法提高約8%。改進(jìn)算法中分段數(shù)量由4增加到8時(shí)，定位精度同樣提高3%左右，分段數(shù)量的增加在此情況下也有助于提高算法的定位精度。所以，在只調(diào)整信標(biāo)節(jié)點(diǎn)比例的情況下，改進(jìn)算法(n=8)與其他算法相比，也有較大的優(yōu)勢。

圖7是改進(jìn)算法(n=8)在調(diào)整信標(biāo)節(jié)點(diǎn)比例過程中，將信標(biāo)節(jié)點(diǎn)比例設(shè)為0.25時(shí)的定位誤差圖，星號表示信標(biāo)節(jié)點(diǎn)，空心圓表示未知節(jié)點(diǎn)位置估計(jì)值，直線表示未知節(jié)點(diǎn)位置估計(jì)值與真實(shí)位置的誤差。由圖7可看出，處于中心位置的未知節(jié)點(diǎn)估計(jì)誤差較小。

圖7 改進(jìn)算法(n=8，Ratio=0.25)定位誤差圖

3.3 調(diào)整節(jié)點(diǎn)總數(shù)

同樣在100 m×100 m正方形區(qū)域內(nèi)，隨機(jī)分布N個(gè)節(jié)點(diǎn)，信標(biāo)節(jié)點(diǎn)比例設(shè)為20%，選取節(jié)點(diǎn)通信半徑30 m，在其他條件不變的情況下，調(diào)整節(jié)點(diǎn)總數(shù)N，對應(yīng)節(jié)點(diǎn)總數(shù)與定位精度圖，如圖8所示。

圖8 節(jié)點(diǎn)總數(shù)與定位精度關(guān)系圖

如圖8所示，隨著節(jié)點(diǎn)總數(shù)的增加，DV－Hop算法和改進(jìn)算法的定位誤差都不斷減小。節(jié)點(diǎn)總數(shù)較小時(shí)，改進(jìn)算法、原算法以及文獻(xiàn)［9］算法定位精度都不高，但是隨著節(jié)點(diǎn)總數(shù)的增加，定位精度提升明顯。節(jié)點(diǎn)總數(shù)在80個(gè)以上時(shí)，改進(jìn)算法、原算法以及文獻(xiàn)［9］算法的定位誤差趨于穩(wěn)定，此時(shí)，改進(jìn)算法(n=4)的定位精度比原算法提高了約4%，與文獻(xiàn)［9］算法定位精度相當(dāng)，改進(jìn)算法(n=8)的定位精度比原算法提高約7%。改進(jìn)算法對于原算法有明顯優(yōu)勢，同時(shí)，改進(jìn)算法(n=8)相比文獻(xiàn)［9］算法有較大優(yōu)勢。

圖9是改進(jìn)算法(n=8)在調(diào)整節(jié)點(diǎn)總數(shù)過程中，將節(jié)點(diǎn)總數(shù)設(shè)為80時(shí)的定位誤差圖，星號表示信標(biāo)節(jié)點(diǎn)，空心圓表示未知節(jié)點(diǎn)位置估計(jì)值，直線表示未知節(jié)點(diǎn)位置估計(jì)值與真實(shí)位置的誤差。從圖9也可得出圖5和圖7中的結(jié)論，中心處的未知節(jié)點(diǎn)估計(jì)誤差較小。

圖9 改進(jìn)算法(n=8，N=80)定位誤差圖

3.4 改進(jìn)算法分析

通過上述3種網(wǎng)絡(luò)情況的分析可看出，改進(jìn)算法的定位精度與原算法相比有明顯提高。改進(jìn)算法在水平修正過程中的分段數(shù)量也影響著定位精度的提高，一般情況下，分段數(shù)量越多，跳數(shù)信息所反映的節(jié)點(diǎn)間距離關(guān)系越準(zhǔn)確，定位精度越高。

同時(shí)，改進(jìn)算法對跳數(shù)進(jìn)行水平及垂直修正，修正的過程中引入查找表，大幅減少了修正過程中的計(jì)算量，與原算法相比，計(jì)算量增加不明顯。改進(jìn)算法的通信量與原算法相當(dāng)，并未給原算法增加額外通信開銷。

4 結(jié)束語

針對傳統(tǒng)DV－Hop算法中跳數(shù)信息不能反應(yīng)節(jié)點(diǎn)間實(shí)際距離關(guān)系而導(dǎo)致較大定位誤差的問題，提出一種水平及垂直修正跳數(shù)的改進(jìn)算法。改進(jìn)算法首先將相鄰節(jié)點(diǎn)跳數(shù)細(xì)化，并在分析兩節(jié)點(diǎn)距離和可能分布情況的基礎(chǔ)上，對不相鄰節(jié)點(diǎn)引入修正角度，兩者結(jié)合，使修正跳數(shù)盡可能反應(yīng)節(jié)點(diǎn)間實(shí)際距離關(guān)系。改進(jìn)算法在定位過程中引入查找表，較好地降低了改進(jìn)算法的計(jì)算量，而且改進(jìn)算法也并未增加通信開銷。仿真結(jié)果表明，改進(jìn)算法較好地提高了傳統(tǒng)DV－Hop算法的定位精度。下一步需要研究邊緣位置的未知節(jié)點(diǎn)定位情況，提高邊緣位置的定位精度。

［1］Akyildiz I F，Su W，Sankara Subramaniam Y，et al.Wireless sensor networks:a survey［J］.Computer Networks，2002，38(4):393－422.

［2］He T，Huang C，Blum B M，et al.Range － free localization schemes for large scale sensor networks［C］.Proceedings of the 9th Annual International Conference on Mobile Computing and Networking，ACM，2003:81 －95.

［3］林金朝，陳曉冰，劉海波.基于平均跳距修正的無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)迭代定位算法［J］.通信學(xué)報(bào)，2009(10):107－113.

［4］Wu H，Gao R.An improved method of DV －h(huán)op localization algori－ thm［J］.Journal of Computational Information Systems，2011，7(7):2293 －2298.

［5］周小波，喬鋼柱，曾建潮.無線傳感器網(wǎng)絡(luò)中基于 RSSI的加權(quán) DV－HOP定位方法［J］.計(jì)算機(jī)工程與應(yīng)用，2011，47(14):109－111.

［6］楊祥，潘瑋.基于RSSI比值修正的無線傳感器網(wǎng)絡(luò)DVHop定位算法［J］.傳感器與微系統(tǒng)，2013，32(7):126－128.

［7］Deng Yin Z，Guo Dong C.A union node localization algorithm based on RSSI and DV － Hop for WSNs［C］.International Conference on Instrumentation，Measurement，Computer，Communication and Control(IMCCC)，IEEE，2012:1094 －1098.

［8］溫江濤，范學(xué)敏，吳希軍.基于 RSSI跳數(shù)修正的 DVHop改進(jìn)算法［J］.傳感技術(shù)學(xué)報(bào)，2014(1):113－117.

［9］方海濤，雷菁，胡昆明，等.基于 RSSI修正的改進(jìn) DVHop測距算法［J］.通信技術(shù)，2012，45(2):16 －18.

［10］Du W，Deng J，Han Y S，et al.A pairwise key predistributionscheme for wireless sensor networks［J］.ACM Transactions on Information and System Security(TISSEC)，2005，8(2):228－258.

［11］He T，Huang C，Blum B M，et al.Range － free localization schemes for large scale sensor networks［C］.Proceedings of the 9th Annual International Conference on Mobile Computing and Networking，ACM，2003:81－95.