基于跳數與跳距優(yōu)化的三維DV-Hop 定位算法研究*

時雨農，劉海隆

(電子科技大學資源與環(huán)境學院，四川 成都 611731)

近年來，隨著無線傳感器技術的不斷發(fā)展，無線傳感器網絡(Wireless Sensor Network，WSN)在生態(tài)環(huán)境監(jiān)測中也得到了大量應用[1]。 其中野外生態(tài)環(huán)境要素的位置信息是重要的參數之一，因經典的二維WSN 定位方法無法反映地形、植株高度等空間上的差異，會產生較大的誤差，因此針對WSN 的三維定位算法也就成為重要的研究方向[2-4]。

WSN 三維定位算法可以分為測距(rangebased)的和非測距(range-free)兩種[5]。 測距定位算法包括基于信號強度(RSS， Received Signal Strength)來進行距離測量的RSSI 定位算法[6]、利用信號傳輸時延測距的TOA(Time of Arrival)定位算法[7]、基于到達時間差的TDOA(Time Difference of Arrival)定位算法[8]和綜合信號發(fā)射和接收角度與時延的AOA(Angle of Arrival)定位算法[9]等。 測距定位算法在精確度上有一定優(yōu)勢，但是因為對設備有所要求，定位成本相對較高，且測量結果易受到WSN 節(jié)點所處環(huán)境的影響[10]，因此適用于室內或者環(huán)境均勻分布的室外WSN 三維定位。 非測距定位算法包括基于三角形內點測試法的APIT 算法[11]、基于網絡連通性的質心定位算法[12]和基于距離矢量路由和GPS 定位思想的DV-Hop 定位算法[13]等。 非測距定位算法功耗較小，受環(huán)境影響不大，但是精度相對較低，適合用于低功耗、低成本的室外無線傳感器網絡定位[14]。

DV-Hop 定位算法是由Dragos Niculescu 等人提出的一種非測距定位算法[15]，其工作過程簡單、易實現(xiàn)、并且不需要測距設備，但精度相對較差，有不少學者對其進行了改進[16-20]。 本文針對環(huán)境監(jiān)測中對于戶外復雜地形WSN 三維定位的需要，分析了傳統(tǒng)DV-Hop 算法誤差產生的原因，并在此基礎上以優(yōu)化跳數和跳距為核心改進了傳統(tǒng)算法，得到了一種更精確的DV-Hop 改進三維定位算法。

1 三維DV-Hop 算法原理

傳統(tǒng)三維DV-Hop 定位算法主要分為以下三個步驟[21-28]:

①計算信標節(jié)點與未知節(jié)點間的最小跳數

首先網絡中的信標節(jié)點(錨節(jié)點)廣播自身信息，節(jié)點每接收到一個信息就更新它到該節(jié)點的最小跳數并處理后轉發(fā)；若該信息來自自身，則忽略，以確保所有節(jié)點都能保存自身與其他任一信標節(jié)點間的最小跳數。

②估算未知節(jié)點的平均每跳距離

每個信標節(jié)點確定自身位置之后，位于(xi，yi，zi)的信標節(jié)點i就可根據以下公式確定自身的平均每跳距離:

式中:(xj，yj，zj)為錨節(jié)點j的位置，hopi，j為i、j兩個信標節(jié)點之間的最短跳數。 得到平均每跳距離后，信標節(jié)點將其廣播出去，而每個未知節(jié)點會記錄自己所接受的第一個數值，并將其作為自己的平均跳距。

③計算未知節(jié)點的位置

設未知節(jié)點U的位置為(x，y，z)，平均跳距為Hopsize，與其能直接通信的信標節(jié)點位置和跳數分別為(x1，y1，z1)、(x2，y2，z2)、(x3，y3，z3)、…、(xn，yn，zn)，hop1、hop2、hop3、…、hopn。 則此點到相應的信標節(jié)點的預測距離分別為d1、d2、d3、…、dn，其中

根據四邊定位計算法則，可列出以下方程組:

誤差e為

根據最小二乘估計的優(yōu)化規(guī)則min(B-AX)T(B-AX)，對X求偏導，并令其值為0，則可以得到X的估計值:

2 三維DV-Hop 算法定位誤差成因分析

2.1 仿真參數設計

利用MATLAB R2020a 軟件根據以上步驟對經典三維DV-Hop 算法進行仿真，仿真具體數據如表1所示。 仿真結果如圖1(a)所示，圖中點號“·”代表未知節(jié)點，星號“*”代表信標節(jié)點。

表1 經典三維DV-Hop 算法仿真參數設置

根據經典DV-Hop 定位算法，可計算出未知節(jié)點的具體位置，稱為測算位置。 圖1(b)表示的是經過經典DV-Hop 算法計算后各未知節(jié)點的預測位置，圖中加號“+”節(jié)點表示預測的未知節(jié)點位置，圖中將各未知節(jié)點與其對應的預測位置連接起來以表示對應關系。

圖1 節(jié)點分布與定位結果圖

2.2 通信距離與信標節(jié)點占比對定位誤差的影響

本文通過改變信標節(jié)點占比和最大通信半徑的方法來測算誤差大小并尋找誤差規(guī)律。 由于無線傳感器網絡節(jié)點分布具有隨機性，為保證實驗結果的代表性，每次實驗結果均為1 000 次重復仿真結果的平均值。 圖2(a)是在保持信標節(jié)點占比(60%)不變的情況下，改變通信半徑，得到的節(jié)點定位平均相對誤差；圖2(b)是保持最大通信半徑(40 m)不變，改變信標節(jié)點占比，得到的節(jié)點定位平均相對誤差。

圖2 通信距離與信標節(jié)點占比對定位誤差的影響

分析圖3 可知，在達到一定的信標節(jié)點占比和通信半徑后，經典DV-Hop 算法可以進行較為精確的定位。 在信標節(jié)點占比不變的情況下，最大通信半徑越大，定位的相對誤差越小，最低接近20%；同樣的，在最大通信半徑不變的情況下，信標節(jié)點占比越大，相對定位誤差越小，最低接近34%。

2.3 跳數對定位誤差的影響

圖3 為未知節(jié)點與信標節(jié)點之間測算距離與實際距離的誤差值仿真結果。 實驗中將信標節(jié)點占比設為40%，通信距離設為30 m，并重復1 000 次求得平均值。 由圖可得，相隔跳數較少的節(jié)點距離估算誤差較小。

圖3 相隔跳數對測距誤差的影響

2.4 誤差成因總結

結合仿真結果與理論分析，可以得出傳統(tǒng)DVHop 定位算法的主要誤差來源:

①最小跳數計算

在經典DV-Hop 算法中，如果兩個節(jié)點互在對方的最大通信范圍內，就將這兩個節(jié)點間跳數記為1跳。 但是由于通信距離是一個較大的區(qū)間，節(jié)點間的實際距離卻可以有相當大的差別。 如圖4 所示。

圖4 節(jié)點A 周邊節(jié)點示意圖

對于節(jié)點A 來說，最外圈的圓表示最大通信半徑，而其他三個節(jié)點B、C、D 都處于這一半徑之內，在跳數統(tǒng)計上這三點與節(jié)點A 的跳數都是1 跳，但是這三者與A 的距離卻有著不同差別，代入計算后會造成誤差。

②平均跳距計算

經典DV-Hop 算法中，未知節(jié)點選擇與自己跳數最少的信標節(jié)點的平均跳距作為自身的平均跳距。 而在實際網絡中，不同節(jié)點在不同區(qū)域內的分布并不是完全均勻的，節(jié)點分布密集的區(qū)域平均跳距較小，反之則平均跳距較大，若以單一跳距作為所有節(jié)點的計算要素，就不能正確反映整體網絡分布狀況。

③計算方法

由于DV-Hop 算法中最后的距離估算采用的是直接相乘方法，這在相關節(jié)點共線的情況下誤差較小。 但是實際情況中節(jié)點的布設較為隨機，不同節(jié)點間的網絡拓撲圖并不是直線，直接相乘會造成較大誤差。

3 三維DV-Hop 定位算法的改進與精度驗證

3.1 算法改進

針對上述對DV-Hop 算法誤差的分析，本文提出了以下幾點優(yōu)化方案:

①細化跳數

針對跳數計算的問題，本文提出細化跳數的方法。 由于1 跳的代表范圍較大，可將一跳細分為更小的區(qū)間。 對節(jié)點來說，設其周圍某鄰居節(jié)點與其的距離為d，最大通信半徑為R，跳數hop 則為:

細分跳數后，跳數和距離之間的比值更接近正比關系。 進而在之后的運算中更加精確地計算節(jié)點與其鄰居節(jié)點間的距離。 顯然，m的取值越大，跳數細分程度越高，計算結果就會更加精確。 但是，實際使用中，更細分的跳數會帶來兩個問題:第一，更細分的跳數意味著節(jié)點需要更多次地按照不同通信半徑洪泛廣播信號，導致無線傳感器節(jié)點耗能過多，這與無線傳感器需要長期存活的要求相違背；第二，實際應用中，較高的細分系數需要無線傳感器對信號強度有極高的靈敏度，在實地試驗中由于電磁環(huán)境復雜，多種無線信號混雜干擾，無線傳感器難以分辨更細的跳數，因此可能會產生新的誤差。 綜合能耗、性能與實際情況，本文將采用m=2 的細分系數。

②信標節(jié)點平均跳距計算修正

DV-Hop 算法中對于信標節(jié)點平均跳距的計算都是基于無偏估計準則。 即通過令式(11)為0 來計算平均跳距Hopsizei:

式中:N為信標節(jié)點的個數。 但在實驗中，根據誤差分布的高斯特性，使用均方誤差比只使用方差要更為合理。 因此本文將式(12)進行等值變換得

根據無偏估計計算法則，對式(12)進行一階求導，并令其為0，可得符合最小均方誤差的平均跳距:

③未知節(jié)點平均跳距選擇

傳統(tǒng)DV-Hop 算法中未知節(jié)點直接采用離自己最為接近的信標節(jié)點的平均跳距作為自身的跳距。根據圖3 仿真結果可以發(fā)現(xiàn)，信標節(jié)點與未知節(jié)點的跳數越大，測算出來的距離誤差就越大；直接取用離自身最近的信標節(jié)點的數據確實可以避免更遠節(jié)點對應跳數所造成的誤差影響，但卻無法完全代表節(jié)點周圍的所有網絡分布狀況。 因此，可將離與未知節(jié)點一定跳數t內的信標節(jié)點的平均跳距納入未知節(jié)點平均跳距計算之中，以權重的形式加入計算。由于距離越遠節(jié)點的距離誤差越大，綜合考慮后設定信標節(jié)點i的權系數wi為:

式中:跳數限制t，根據仿真實驗結果，與環(huán)境大小l與通信半徑R有關，即

最終求得未知節(jié)點的加權平均跳距為:

3.2 仿真精度驗證

3.2.1 實驗環(huán)境設置

實驗采用MATLAB R2020a 軟件進行仿真，詳細數據如表2 所示。

表2 仿真參數設置

3.2.2 仿真結果分析

①信標節(jié)點比例對定位精度的影響

圖5(a)表示了在固定通信半徑為40 m 的情況下，優(yōu)化算法與經典DV-Hop 算法之間的精度差距。由結果可得，在固定通信距離的情況下，信標節(jié)點占比較小時，經典算法和優(yōu)化算法精度比較接近，這是因為信標節(jié)點數量過少，大部分的未知節(jié)點與信標節(jié)點的跳數都較大，測算的距離誤差較大，進而導致最終定位的誤差率較高；但是當信標節(jié)點數量增多后，優(yōu)化效果逐漸得到體現(xiàn)，定位誤差大幅下降，并且下降趨勢逐漸趨緩。 比起傳統(tǒng)定位算法，優(yōu)化后的定位算法定位精度平均提高25%左右。

圖5 經典算法與優(yōu)化算法精度比較

②節(jié)點通信半徑對定位精度的影響

圖5(b)表示了在固定信標節(jié)點比例為60%的情況下，優(yōu)化算法與經典DV-Hop 算法之間的精度差距。 由結果可知，在通信距離較近的情況下，很多節(jié)點無法與信標節(jié)點直接通信，或者相距跳數較大，這種情況下經典DV-Hop 算法和改進后的算法的定位精度都受到較大影響。 相對于經典算法，優(yōu)化后的DV-Hop 算法精度得到大幅提高。 在最大通信半徑較小的情況下，優(yōu)化后的算法與經典算法差距不大；但在最大通信半徑超過一定值后，優(yōu)化算法精度顯著提高，并隨著通信距離的增大逐漸穩(wěn)定，這是由于在較大的通信距離下細化的跳數所能帶來的優(yōu)化效應慢慢降低，并趨向于穩(wěn)定。 相較于傳統(tǒng)DV-Hop算法，改進算法將定位精度平均提高約30%。

4 結束語

本文通過仿真和理論分析的方法研究傳統(tǒng)DVHop 算法的誤差，并基于傳統(tǒng)DV-Hop 算法的缺陷，提出了一種改進后的DV-Hop 算法。 通過多通信半徑的方式來細分節(jié)點跳數，以達到提高節(jié)點間距離估計的精確度；通過調整平均跳距計算公式的方式改進了信標節(jié)點的平均跳距計算；利用傳統(tǒng)DVHop 算法得出的規(guī)律以權重的形式改進了未知節(jié)點平均跳距的選取。 仿真結果說明，本文提出的改進算法相對于傳統(tǒng)算法，在相同WSN 網絡中，具有更高的定位精度。