唐 輝，紀 萍

(河海大學文天學院 電氣信息學院，安徽 馬鞍山 243031)

隨著具有感知、計算和通信能力的微型傳感器的出現(xiàn)，由傳感器節(jié)點組成的網(wǎng)絡(luò)(Wireless Sensor Network，WSN)。已被列為對人類未來生活產(chǎn)生影響的10 大新興技術(shù)之一［1］。由于節(jié)點的位置均是隨機的，節(jié)點所采集到的數(shù)據(jù)若是無位置信息幾乎是毫無應(yīng)用價值的。所以，節(jié)點定位也就成為關(guān)鍵問題?？紤]到WSN 網(wǎng)絡(luò)特殊的要求，定位算法應(yīng)簡單、準確、能量有效等。DV－HOP(Distance Vector－Hop)是一種實用有效的算法，但該算法在定位精度上通過存在不足。本文首先討論DV－HOP 算法，并提出一種改進的節(jié)點定位算法WDV－HOP，進行仿真實驗，驗證了定位效果。

1 DV－HOP 原理及AHS 轉(zhuǎn)發(fā)機制與節(jié)點定位

基于非測距的定位算法中通常廣播3 種定位消息:DV－HOP、Dv－Distance 和Euclidean。在DVHOP 算法中錨節(jié)點獲取到距其周圍所有錨節(jié)點的坐標信息和跳數(shù)信息后，便可計算出AHS(Average of Hop)。然后該錨節(jié)點就向其周圍的普通節(jié)點廣播該AHS 值。當普通節(jié)點接收到錨節(jié)點發(fā)送的AHS 值以及距離錨節(jié)點的最小跳數(shù)后，便可計算出到錨節(jié)點的距離。當一個普通節(jié)點得到距離3 個或3 個以上錨節(jié)點的距離后，就能依據(jù)三邊法則計算出其自身的坐標［2］。

每一個錨節(jié)點均存儲一張“錨節(jié)點表”該表記錄有鄰居錨節(jié)點的ID 號、坐標信息、以及其鄰居錨節(jié)點的最小跳數(shù)等信息。定位開始階段每個錨節(jié)點對外廣播包含自身的ID、坐標信息、以及初始計數(shù)器值為零的消息?？煞Q該消息為“跳數(shù)獲取消息”，當其他錨節(jié)點收到該消息后便開始檢查自己的錨節(jié)點表，若表中還沒有該錨節(jié)ID 的記錄，則在自己的錨節(jié)點表中加入一條記錄，同時將消息中的計數(shù)器值加1 后向周圍節(jié)點轉(zhuǎn)發(fā)。若錨節(jié)點表中已存在該錨節(jié)點ID 的記錄，則比較記錄中的跳數(shù)值是否大于收到消息中的跳數(shù)值，若大于則更新為較小的值，同時也將消息中的計數(shù)器值加1 轉(zhuǎn)發(fā)。若消息中的跳數(shù)值大于或等于錨節(jié)點表中的值，則直接丟棄該消息不再轉(zhuǎn)發(fā)。

DV－HOP 位算法中一個重要的消息是錨節(jié)點發(fā)送含有AHS 值的消息。定位開始后錨節(jié)點啟動定時器，當更新AHS 值定時器到達后，錨節(jié)點便開始計算AHS 值，若“錨節(jié)點表”被更新也將促發(fā)新一輪AHS值的計算。AHS 在網(wǎng)絡(luò)中按一定的規(guī)則轉(zhuǎn)發(fā)，普通節(jié)點只接受相同ID 錨節(jié)點的AHS 值，第一個AHS 值的獲取采用先到先得的方式，對于隨后轉(zhuǎn)發(fā)的不同ID 錨節(jié)點的AHS 值則采取丟棄原則。當所有錨節(jié)點的AHS 值均被計算出后整個AHS 求解過程結(jié)束［3－5］。而當普通節(jié)點獲取到AHS 值與到3 個或3 個以上錨節(jié)點的最小跳數(shù)后，可利用三邊算法計算出其物理坐標。由于整個定位過程均為迭代進行，因此稱該定位算法為迭代法［2］。

2 改進的算法WDV－HOP

在DV－HOP 算法中信標節(jié)點的主要任務(wù)是計算出AHS 值。AHS 值的計算公式為

其中，R 是物理坐標已知的信標節(jié)點兩兩之間的距離值矩陣

其中，H 是定位初始階段獲得的信標節(jié)點之間的最小跳數(shù)值矩陣

信標節(jié)點是預(yù)先布設(shè)好或地理位置是可通過類似GPS 等方法精確獲取的。所以，矩陣R 是已知的。因此，矩陣AHS 值完全取決于跳數(shù)值矩陣H，同時定位誤差也主要來源于H 值。若能找到更合理的H，則能計算出更加真實反應(yīng)網(wǎng)絡(luò)情況的AHS 值。從普通節(jié)點一側(cè)分析:dij=AHSj×hij，其中dij是普通節(jié)點i 到錨節(jié)點j 的距離，hij是普通節(jié)點i 到錨節(jié)點j 的最小跳數(shù)值。dij的大小與AHSj和hij值均有關(guān)［3－4］。綜上分析，可分別從信標節(jié)點和普通節(jié)點兩側(cè)著手提出改進的測距算法。

(1)在信標節(jié)點側(cè)提出以下改進措施:每個信標節(jié)點維護一張鄰居信標節(jié)點的信息表，信息表中維護著自身到各個信標節(jié)點的路徑字段NBHopMsg，規(guī)定到每個鄰居信標節(jié)點i 至少記錄5 條路徑信息，5 條路徑分別記錄著該信標節(jié)點到達鄰居信標節(jié)點的不同路徑所需的跳路徑與跳數(shù)，而對于少于3 條路徑的情況則需重新啟用路徑獲取過程以保證計算的精確度。這樣，信標節(jié)點j 在計算AHSj值時，對于記錄中的每一個跳數(shù)值分別計算其對應(yīng)的AHS 值:AHSj1=rji/hopji1，AHAj2=rji/hopji2，…，AHSj5=rji/hopji5…，最后再用信標節(jié)點間的跳數(shù)值做權(quán)值并對所得AHS 值求加權(quán)平均即

最終計算得到信標節(jié)點j 到信標節(jié)點i 的加權(quán)AHSJ值;到其他信標節(jié)點也依據(jù)同理獲得其對應(yīng)的AHS 值，最終將信標節(jié)點j 的所有AHS 值用信標節(jié)點間的距離做加權(quán)求得最終值，距離越遠權(quán)值越大。通過上述加權(quán)方法得到改進的AHS 值能更加真實地反映該信標節(jié)點附近的網(wǎng)絡(luò)情況，使最終的定位結(jié)果更精確

(2)標準DV－HOP 算法中，普通節(jié)點只接收從最近的信標節(jié)點發(fā)送的AHS 值，一旦某個普通節(jié)點獲取到AHS 值后則會拒絕接受其他信標節(jié)點的發(fā)送數(shù)據(jù)。但事實情況是由于各種原因通常無法保證普通節(jié)點所接收的AHS 值是最近信標節(jié)點發(fā)送的，這樣勢必會給后面的定位造成誤差。另一方面通過實際觀察發(fā)現(xiàn)當存在較多信標節(jié)點時，AHS 消息值會存在嚴重浪費，所以可考慮充分利用這些AHS 值。實際中考慮到越靠近普通節(jié)點的錨節(jié)點AHS 值有著越發(fā)重要的作用，因此可給每個接收到的AHS 值做加權(quán)，權(quán)就取為普通節(jié)點到信標節(jié)點跳數(shù)的倒數(shù)。但為防止采用過多AHS 的值會產(chǎn)生負面影響，本改進算采用仿真經(jīng)驗值，將普通節(jié)點用于計算AHS 值的信標節(jié)點的個數(shù)定為≤3［5］。

(3)由于算法中是將節(jié)點間最短路徑作為節(jié)點間距離的估計，因此節(jié)點的定位結(jié)果必然存在誤差。本改進算法是基于分簇算法的，即簇內(nèi)大于最大定位半徑R 的非鄰居節(jié)點的距離是通過WDV－HOP 測距法來計算，這些節(jié)點的定位精度將直接影響整個簇內(nèi)節(jié)點的定位精度。因此，要提高整個節(jié)點的定位精度就需要對上述改進節(jié)點的定位結(jié)果做進一步修正。由于事先已知信標節(jié)點的物理坐標，因此可考慮充分利用信標節(jié)點的這些已知屬性來提高定位精度［6－7］。下面給出一種利用信標節(jié)點信息進行修正因子的方法。設(shè)信標節(jié)點i 的鄰居信標節(jié)點信息表中的記錄NBi(IDk，hopn)的路徑集合為

信標節(jié)點間的實際距離為Dij=(di1，…，dik，…)，，將SPi和Dij中的記錄值做線形回歸運算，該運算要求滿足以下條件

式中，Pij為信標節(jié)點路徑的條數(shù)。設(shè)普通節(jié)點l 距離信標節(jié)點u 擁有最短路徑，則該節(jié)點在做距離計算時對距離值做出修正

其他節(jié)點用類似l 節(jié)點的方法做出修正。

3 仿真實驗

仿真實驗的節(jié)點分布如圖1 所示，矩形區(qū)域內(nèi)隨機分布200 個節(jié)點，其中信標節(jié)點數(shù)為6 個(圖中圓圈)，平局網(wǎng)絡(luò)連通度為12，節(jié)點無線測距誤差為10%，節(jié)點最大通信半徑r 為15 m。

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

圖2 連通度為12 的矩形區(qū)域

圖3 顯示的是WDV－HOP 算法應(yīng)用于多維定標技術(shù)的定位結(jié)果，圓圈為信標節(jié)點。星形代表未知節(jié)點的實際位置，圓點則代表算法定位出的節(jié)點位置，二者之間的黑色連線長度代表定位誤差的大小。圖4 顯示的是應(yīng)用了WDV－HOP 算法和未使用WDV－HOP定位算法的定位結(jié)果誤差對比。連線代表標準算法的定位誤差大小和改進后算法的定位誤差大小。從圖4誤差線段長度可看出，改進后算法普遍誤差線段較短，即應(yīng)用了WDV－HOP 算法的多維定標技術(shù)較之標準算法在定位精度方面有所提高。

圖3 矩形區(qū)域改進算法定位結(jié)果圖

圖4 矩形區(qū)域改進算法和標準算法定位結(jié)果比較

下面通過整理部分實驗數(shù)據(jù)，定量分析改進后算法在定位精度上獲得的提高。表1 列出了矩形區(qū)域中不同外設(shè)條件下得到的部分定位誤差數(shù)據(jù)。表1 分為兩部分，第一部分顯示的數(shù)據(jù)是網(wǎng)絡(luò)連通度為12 的情況下，兩種算法的節(jié)點定位誤差隨節(jié)點測距誤差的關(guān)系數(shù)據(jù)。第二部分則列出了定位誤差為0.1 的情況下，兩種算法的節(jié)點定位誤差隨連通度變化的關(guān)系數(shù)據(jù)。

表1 矩形區(qū)域定位誤差關(guān)系抽樣表

從表1 第一部分可發(fā)現(xiàn)在節(jié)點測距誤差＜0.1 的情況下，改進算法的精度略高于標準算法，而當測距誤差＞0.1 時，改進算法的定位誤差明顯小于標準算法。從表格第二部分可看出在固定了測距誤差的情況下，改變網(wǎng)絡(luò)平均連通度值，改進算法的定位誤差也小于標準算法。

4 結(jié)束語

本文描述了DV－HOP 算法的工作原理，然后借鑒DV－HOP 算法思想提出非鄰居節(jié)點的測距算法WDV－HOP。改進的算法應(yīng)用于多維定標技術(shù)中簇內(nèi)非鄰居節(jié)點間的距離計算。仿真結(jié)果表明，在相同的實驗條件下改進的定位算法定位精度明顯優(yōu)于未改進的定位算法。同時在本次仿真實驗中，節(jié)點定位精度約有3%的提升。

［1］ 周耀偉，邱衛(wèi)東，溫蜜.一種帶認證的LU 密鑰預(yù)分配方案［J］.計算機應(yīng)用，2009，29(1):161－164.

［2］ CHONGG C Y，KUMAR S P.Sensor networks.evolution，opportunities，and challenges［J］.Distributcd Wireless Sensor Networks，2003，91(16):124－125.

［3］ 唐輝，張英杰，阮承治.基于DV－HOP 的改進算法及仿真［J］.電子科技，2010，23(7):69－71，76.

［4］ SAVARESE C，RABAEY J，LANGENDOEN K.Robust positioning algorithms for distributed ad－h(huán)oc wireless sensor networks［C］.Monterey:Proceeding of USENIX Technical Annual Conference，2002.

［5］ HUANG Qiqian，SELVAKENNEDYR S.A range－free localization algorithm for wirelesssensor networks［J］.Computer Aided Designed，2008，13(5):349－352.

［6］ 劉毓，馬曉輝，曹津銘.基于WSN 特點對DV－HOP 算法改進的研究［J］.西安郵電學院學報，2012(6):24－26，55.

［7］ 何艷麗.無線傳感器網(wǎng)絡(luò)質(zhì)心定位算法研究［J］.計算機仿真，2011，28(5):163－166，219.