采用虛擬錨節(jié)點的高精度VAD-Hop定位算法*

姜 鈞，程良倫

(廣東工業(yè)大學 自動化學院，廣州 510006)

無線傳感器網(wǎng)絡(luò)(WSN)技術(shù)在軍事、商業(yè)、環(huán)境監(jiān)測、醫(yī)療護理、家庭自動化等領(lǐng)域獲得越來越多的應(yīng)用［1－2］。節(jié)點定位作為其關(guān)鍵技術(shù)之一逐漸成為研究熱點［3－4］。

無線傳感器網(wǎng)絡(luò)定位算法有很多種，一般可以分為基于測距(rang-based)和無需測距(rang-free)兩類［5］。前者需要測量節(jié)點間的角度或距離信息，然后使用三邊或多邊定位得到節(jié)點位置，對時間同步和節(jié)點硬件提出較高的要求;后者不需要測量節(jié)點間角度或距離信息，僅通過節(jié)點間的連通度進行定位。因此，無需測距的定位算法更適合大規(guī)模無線傳感器網(wǎng)絡(luò)節(jié)點定位的實際需求，得到越來越多的關(guān)注。

DV-Hop［6］定位算法是目前運用最廣泛的無需測距的定位算法，針對該算法的優(yōu)化也是不斷出現(xiàn)［7－10］。文獻［7］對未知節(jié)點與錨節(jié)點之間的估計距離作修正，該修正由多跳的校正值和錨節(jié)點的平均每跳距離誤差所組成，同時將總體最小二乘法應(yīng)用于最后的三邊測量法中。文獻［8］在節(jié)點的初始位置上利用彈簧模擬方法對節(jié)點位置迭代求精。文獻［9］根據(jù)不同的節(jié)點分布情況計算出不同的平均跳距，使其更接近于實際平均跳距，定位時用Min-Max方法代替了最小二乘法，另外，對定位初步結(jié)果進行循環(huán)位置修正。文獻［10］通過最小二乘準則校正了平均每跳距離，并且通過加權(quán)修正了跳段距離，最后還通過泰勒展開進行了迭代求精。上述參考文獻中的優(yōu)化都或多或少的增加了通信開銷和計算開銷。本文主要從降低DV-Hop算法對錨節(jié)點密度需求的角度入手引入虛擬錨節(jié)點，并參考文獻［10］，對跳數(shù)和平均跳距進行了限制與修正，通過仿真實驗，驗證了方案的性能。

1 DV-Hop定位算法

DV-Hop算法的基本思想是，將未知節(jié)點到錨節(jié)點間的距離用節(jié)點平均每跳距離和跳數(shù)的乘積來表示，然后再利用三邊測量法或者多邊測量法求得未知節(jié)點的位置。它主要包括3個階段。

第一階段，每個錨節(jié)點以泛洪的形式在整個網(wǎng)絡(luò)廣播信息，信息格式為{idi，xi，yi，hopsi}，其中包含了錨節(jié)點的標識idi，位置信息(xi，yi)以及跳數(shù)信息hopsi。這樣錨節(jié)點i根據(jù)式(1)計算自己的平均每跳距離。

式中j為錨節(jié)點i數(shù)據(jù)表中的其它錨節(jié)點，hopsij為錨節(jié)點i和j之間的跳數(shù)。

第二階段，錨節(jié)點廣播自己計算的平均每跳距離，未知節(jié)點收取每個錨節(jié)點的第一個平均每跳距離，而丟棄后來數(shù)據(jù)。

如圖 1 所示，假設(shè)有錨節(jié)點i，j，k，錨節(jié)點i和j、k之間的距離為dij，dik，則錨節(jié)點i計算的平均每跳距離為

假設(shè)要定位未知節(jié)點m的位置，m先收到三個錨節(jié)點中i的平均每跳距離信息，節(jié)點m便用cm=ci估算出到錨節(jié)點i，j，k的距離分別為cmhopsmi，cmhopsmj，cmhopsmk。

第三階段，未知節(jié)點根據(jù)求出的到各錨節(jié)點的距離，利用三邊或多邊定位法完成定位。

圖1 DV-Hop定位算法示意圖

2 DV-Hop定位算法的特征

由于節(jié)點之間的信息交互不是走的直線距離，再加上節(jié)點間每一跳的距離都是有差別的，所以估算的節(jié)點位置和實際值是有差別的。例如圖1中未知節(jié)點m估算的到錨節(jié)點k的距離為4cm，即使網(wǎng)絡(luò)中每一跳的距離都相等，得到的估計距離也和實際值dmk不相等。節(jié)點隨機分布的網(wǎng)絡(luò)拓撲使得以平均每跳距離來衡量所有距離本身就是有誤差的，如果錨節(jié)點密度偏小，這種誤差將會更大。

3 VAD-Hop定位算法

本文參考DV-Hop算法，提出一種基于虛擬錨節(jié)點的定位算法，簡稱為VAD-Hop定位算法。

3.1 細化跳距

由于節(jié)點不是均勻分布的，所以會出現(xiàn)在錨節(jié)點的通信距離內(nèi)有的未知節(jié)點離錨節(jié)點較近，有的未知節(jié)點離錨節(jié)點較遠，但它們各自從收到的信息來看都認為自己在離錨節(jié)點距離一跳的位置，這樣得到的跳段距離是不準確的。這會間接影響錨節(jié)點得到平均每跳距離的數(shù)值，因此要采取相應(yīng)措施。

實際上，跳數(shù)依照小數(shù)的細分與距離成直線性關(guān)系，而信號強度與距離并不是，所以式(3)并不是一個很準確的式子。而在細化的程度不大的時候，也就是k值不大的時候，該公式的應(yīng)用還是準確的。k值的選取與網(wǎng)絡(luò)的拓撲結(jié)構(gòu)，節(jié)點通信半徑都有關(guān)系，具體選取時需要實際情況實際對待，既要考慮能夠提高定位精度，又要考慮不過多增加存儲量，增加成本。

3.2 利用虛擬錨節(jié)點

在網(wǎng)絡(luò)中，如果錨節(jié)點稀疏，跳距的累計誤差會加大，定位精度會降低，但是由于錨節(jié)點的成本比較高［11］，因此在低錨節(jié)點密度的無線傳感器網(wǎng)絡(luò)中如何用DV-Hop算法來保證定位精度是首要著手點。文獻［12］將未知節(jié)點升級為新錨節(jié)點，最終實現(xiàn)低錨節(jié)點密度網(wǎng)絡(luò)中所有未知節(jié)點的定位，本文將其稱為虛擬錨節(jié)點，即在網(wǎng)絡(luò)布局的時候為未知節(jié)點，在定位的過程中升級成為錨節(jié)點為其它的未知節(jié)點的定位提供幫助。

根據(jù)虛擬錨節(jié)點的得到條件，又可分為四類。這里將依靠三個及三個以上錨節(jié)點定位的虛擬錨節(jié)點稱為準虛擬錨節(jié)點，將依靠少量準錨節(jié)點和大量錨節(jié)點定位的虛擬錨節(jié)點稱為亞虛擬錨節(jié)點，將依靠大量虛擬錨節(jié)點和少量錨節(jié)點定位的虛擬錨節(jié)點稱為次虛擬錨節(jié)點，將依靠全部虛擬錨節(jié)點定位的虛擬錨節(jié)點稱為純虛擬錨節(jié)點。理論上講只要網(wǎng)絡(luò)中存在3個以上的錨節(jié)點，每一個未知節(jié)點都能接收到從每個錨節(jié)點傳來的信息，從而利用三邊或多邊法進行定位，但是有的未知節(jié)點距離錨節(jié)點的跳數(shù)很大，會造成跳距的很大累計誤差，定位誤差很大，本文認為這些從很遠處的錨節(jié)點獲取消息是無效的，不如利用相隔較近的虛擬錨節(jié)點的信息進行定位。雖然虛擬錨節(jié)點本身的位置信息是估算的，不如錨節(jié)點的位置信息準確，但是如果經(jīng)過一定的處理，提高虛擬錨節(jié)點位置信息的準確度，可以使得最后節(jié)點的定位誤差小于依靠較遠位置的錨節(jié)點定位產(chǎn)生的誤差。同時節(jié)點將收到跳數(shù)較多的錨節(jié)點發(fā)出的信息丟棄在一定程度上還能減少網(wǎng)絡(luò)的通信量。這里引入跳數(shù)的有效閾值m，大于m的跳數(shù)被認為節(jié)點間相隔較遠。

由于四類虛擬錨節(jié)點的定位存在依賴關(guān)系，即會造成累計誤差，本文研究和實驗的對象以依靠準虛擬錨節(jié)點和亞虛擬錨節(jié)點實現(xiàn)所有未知節(jié)點定位的低錨節(jié)點密度的無線傳感器網(wǎng)絡(luò)。

假設(shè)得到的準虛擬錨節(jié)點存在誤差e1，亞虛擬錨節(jié)點存在誤差e2，由于e1是由錨節(jié)點得到的，并且沒有依賴距離比較遠的錨節(jié)點，故其值是很小的。而e2主要是由大量錨節(jié)點定位的，這中間也沒有依賴距離比較遠的錨節(jié)點，所以其值也是可以信賴的，雖然在e1的基礎(chǔ)上存在累計誤差，但是有部分亞虛擬錨節(jié)點的e2可能與e1存在方向相反的分量，可以有效消除部分誤差分量。而后面兩種虛擬錨節(jié)點也存在部分的誤差抵消情況，但是本身是依靠位置信息存在誤差的虛擬錨節(jié)點得到的，故本身位置信息的誤差較大，暫時不在本文實驗范圍之內(nèi)。

引入虛擬錨節(jié)點會出現(xiàn)一個問題，就是虛擬錨節(jié)點的id確定的問題。由于定位的過程中，節(jié)點需要識別不同的錨節(jié)點的信息，也就是需要辨別出數(shù)據(jù)包的來源，這里提出特征標識Tb的概念，用于區(qū)分錨節(jié)點與虛擬錨節(jié)點。當錨節(jié)點發(fā)送數(shù)據(jù)包時，Tb=0，當準虛擬錨節(jié)點發(fā)送數(shù)據(jù)包時，Tb=1，當亞虛擬錨節(jié)點發(fā)送數(shù)據(jù)包時Tb=2，后面依次類推。通過引入特征標識可以將錨節(jié)點與虛擬錨節(jié)點區(qū)分開來，但是還是不能很好的區(qū)分同類虛擬錨節(jié)點的id，會出現(xiàn)未知節(jié)點由于收到來源于不同虛擬錨節(jié)點的相同的id而將后來者丟棄的情況。這里定義

為準虛擬錨節(jié)點的id，其中n為到虛擬錨節(jié)點的可用錨節(jié)點的個數(shù)，hopsn為每個錨節(jié)點經(jīng)過細化后的到虛擬錨節(jié)點的總跳數(shù)。使用式(4)用簡單的計算得到小數(shù)形式的數(shù)據(jù)作為準虛擬錨節(jié)點的id，即使兩個未知節(jié)點相隔比較近，但是式中用兩個不相關(guān)的變量基本能將不同虛擬錨節(jié)點相同id的概率降到0。亞虛擬錨節(jié)點將準虛擬錨節(jié)點以錨節(jié)點看待，采用同樣的方法得到自己的id。

3.3 錨節(jié)點修正平均每跳距離

基于無偏估計準則計算錨節(jié)點平均每跳距離應(yīng)用得很多，最小二乘法也可應(yīng)用其中［10］。在 DVHop的第一階段，假設(shè)錨節(jié)點i接收到其它錨節(jié)點的位置信息，則錨節(jié)點i計算的平均每跳距離ci應(yīng)滿足:

式中j為錨節(jié)點i的數(shù)據(jù)表中存儲的其它錨節(jié)點，hopsij為錨節(jié)點i和j之間的跳數(shù)，dij為二者之間的真實距離，eij為用平均每跳距離與跳數(shù)乘積代替實際距離產(chǎn)生的誤差。如果誤差越小，采用的ci最合理，根據(jù)最小二乘法準則，用∑作為總誤差，則

以圖1為例，錨節(jié)點i采用VAD-Hop算法計算的平均每跳距離為

當然這里的hopsij和hopsij并不為2和5，而是采用上面提到的經(jīng)過細化處理后的跳距，具體的數(shù)值要根據(jù)選取的信號強度等級k有關(guān)。

4 VAD-Hop算法的實現(xiàn)

該算法主要在于用虛擬錨節(jié)點參與未知節(jié)點的定位，減少了成本，同時為了提高定位精度采用細化跳距，修正平均每跳距離的做法，對于很多人提到的加權(quán)處理和迭代處理，雖然在一定程度上能夠提高定位精度，但是增加了計算量和通信量，本文沒有考慮。具體的算法步驟如下:①網(wǎng)絡(luò)初始化，設(shè)置k，m;②錨節(jié)點以泛洪形式廣播包含Tb，id，hops信息的數(shù)據(jù)包，其中hops的初始值為0;③接收到數(shù)據(jù)包的未知節(jié)點獲取細化后的跳數(shù)y，然后通過比較特征標識和id將同一來源的跳數(shù)較小的數(shù)據(jù)信息記錄下來，并將跳數(shù)加y，如果此時的跳數(shù)小于m就將數(shù)據(jù)包轉(zhuǎn)發(fā)出去，否則丟棄;④廣播一段時間后，每個錨節(jié)點使用得到的錨節(jié)點的信息計算出自己的平均每跳距離c，然后將包含 Tb，id，hops，c信息的數(shù)據(jù)包以泛洪形式廣播出去;⑤重復③，同時，未知節(jié)點計算自己到錨節(jié)點的估算距離;⑥獲得三個以上錨節(jié)點信息的未知節(jié)點利用三邊法或多邊法進行定位，定位后的節(jié)點計算自己的id，并將自己的Tb改為1;⑦一段時間后，已經(jīng)定位的未知節(jié)點成為虛擬錨節(jié)點，和錨節(jié)點一起通過泛洪形式廣播包含Tb，id，hops信息的數(shù)據(jù)包，其中 hops的初始值為0;⑧重復③、④、⑤;⑨獲得3個以上少量虛擬錨節(jié)點和大量錨節(jié)點的未知節(jié)點利用三邊法或多邊法進行定位，定位后的節(jié)點計算自己的id，并將自己的Tb改為2;⑩一段時間后，亞虛擬錨節(jié)點，準虛擬錨節(jié)點和錨節(jié)點一起重復②、③、④、⑤，未知節(jié)點按照三邊或者多邊測量法計算自己的位置。

5 仿真實驗

為了驗證算法的性能，本文對傳統(tǒng)的DV-Hop定位算法和VAD-Hop算法在MATLAB 7.1平臺上進行了仿真對比。將100個節(jié)點隨機分布于50×50的區(qū)域內(nèi)，錨節(jié)點的個數(shù)分別取 5，8，11，14，17，20，23，節(jié)點通訊距離取15，跳數(shù)閾值m取35，記錄50次節(jié)點隨機分布試驗的定位誤差取平均值。其中k取值2，亞虛擬錨節(jié)點的選取按依靠少于1/3的準虛擬錨節(jié)點和多于2/3的錨節(jié)點定位確定來決定，定位誤差按照文獻［10］中計算，將基于平均跳距修正的無線傳感器網(wǎng)絡(luò)節(jié)點迭代定位算法簡稱為DVHop(跳距修正)，將本文算法與其比較。接著逐步增加節(jié)點總數(shù)，進一步進行比較。

從圖2和圖3可以看出VAD-Hop算法比原DV-Hop和DV-Hop(跳距修正)的定位誤差小，并且隨著節(jié)點總數(shù)的增加，VAD-Hop的優(yōu)越性更加體現(xiàn)出來。通過仿真實驗很好的說明了VAD-Hop算法的效果。

圖2 錨節(jié)點個數(shù)與定位誤差

圖3 節(jié)點總數(shù)與定位誤差

6 結(jié)束語

本文在DV-Hop算法的基礎(chǔ)上，以減少錨節(jié)點完成定位為目標，引入虛擬錨節(jié)點，并對幾種虛擬錨節(jié)點進行了定性分析，提出解決虛擬錨節(jié)點身份識別的方法，在使用準虛擬錨節(jié)點和亞虛擬錨節(jié)點的基礎(chǔ)上，又采用了跳數(shù)閾值限制下的跳數(shù)細分，并且修正了跳距。整個算法可以降低定位對錨節(jié)點的需求，從而可以降低網(wǎng)絡(luò)成本，并且可以提高定位精度。對于類型有區(qū)別的虛擬錨節(jié)點還需要深入的深究，對于如何選擇跳數(shù)閾值以及跳數(shù)細分時采用的信號強度等級也需要進一步作研究，這些問題將在以后的論文中提出。

［1］李瑤怡，赫曉星，劉守印.基于路徑損耗模型參數(shù)實時估計的無線定位方法［J］.傳感技術(shù)學報，2010，23(9):1328－1333.

［2］Wang Lei，Wang Xiaopeng，Du Xiaotong.Some Issues on WSN Localization Based on MLE［C］//Intelligent Control and Automation(WCICA)，2010 8th World Congress on，2010:796－800.

［3］蔡紹濱，李希，田鷹，等.基于圓形選擇技術(shù)的循環(huán)三邊組合測量法的研究［J］.計算機研究與發(fā)展，2010，47(2):238－244.

［4］Shahriari Nia M，Khaxar M，Rashti S M.Discrete Probabilistic DVHop:Reengineering High Accuracy Range-Free WSN Localization［C］//Ultra Modern Telecommunications ＆ Workshops，2009.ICUMT’09.International Conference on，2009:1－6.

［5］Gao Guoqing，Lei Lin.An Improved Node Localization Algorithm Based on DV-HOP in WSN［C］//Advanced Computer Control(ICACC)，2010 2nd International Conference on，2010:321－324.

［6］Nicolescu D，Nath B.Ad-Hoc Positioning Systems(APS)［C］//Proc.of the 2001 IEEE Global Telecommunications Conf.Vol.5，San Antonio:IEEE Communications Society，2001.2926－2931.

［7］張佳，吳延海，石峰，等.基于DV-HOP的無線傳感器網(wǎng)絡(luò)定位算法［J］.計算機應(yīng)用，2010，30(2):323－326.

［8］田金鵬，施惠昌.無線傳感器網(wǎng)絡(luò)節(jié)點定位改進算法［J］.上海大學學報(自然科學版)，2009，15(3):225－229.

［9］趙清華，劉少飛，張朝霞，等.一種無需測距節(jié)點定位算法的分析和改進［J］.傳感技術(shù)學報，2010，23(1):122－127.

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

［11］Zhou Zude，Wang Sheng，Liu Quan.Local Hop-Count Probability Grid:An Improvement Nodes Localization Scheme in WSN［C］//Innovative Computing，Information and Control，2006.ICICIC ＇06.First International Conference on，2006:64－67.

［12］楊石磊，樊曉平，劉少強.一種改進的無線傳感器網(wǎng)絡(luò)DV-Hop定位算法［J］.計算機測量與控制，2008，16(9):1356－1358.