基于DV－HOP 的改進(jìn)算法WDV－HOP 及仿真

唐 輝，紀(jì) 萍

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

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

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

基于非測(cè)距的定位算法中通常廣播3 種定位消息:DV－HOP、Dv－Distance 和Euclidean。在DVHOP 算法中錨節(jié)點(diǎn)獲取到距其周?chē)绣^節(jié)點(diǎn)的坐標(biāo)信息和跳數(shù)信息后，便可計(jì)算出AHS(Average of Hop)。然后該錨節(jié)點(diǎn)就向其周?chē)钠胀ü?jié)點(diǎn)廣播該AHS 值。當(dāng)普通節(jié)點(diǎn)接收到錨節(jié)點(diǎn)發(fā)送的AHS 值以及距離錨節(jié)點(diǎn)的最小跳數(shù)后，便可計(jì)算出到錨節(jié)點(diǎn)的距離。當(dāng)一個(gè)普通節(jié)點(diǎn)得到距離3 個(gè)或3 個(gè)以上錨節(jié)點(diǎn)的距離后，就能依據(jù)三邊法則計(jì)算出其自身的坐標(biāo)［2］。

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

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

2 改進(jìn)的算法WDV－HOP

在DV－HOP 算法中信標(biāo)節(jié)點(diǎn)的主要任務(wù)是計(jì)算出AHS 值。AHS 值的計(jì)算公式為

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

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

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

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

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

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

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

信標(biāo)節(jié)點(diǎn)間的實(shí)際距離為Dij=(di1，…，dik，…)，，將SPi和Dij中的記錄值做線(xiàn)形回歸運(yùn)算，該運(yùn)算要求滿(mǎn)足以下條件

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

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

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

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

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

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

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

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

圖4 矩形區(qū)域改進(jìn)算法和標(biāo)準(zhǔn)算法定位結(jié)果比較

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

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

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

4 結(jié)束語(yǔ)

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

［1］ 周耀偉，邱衛(wèi)東，溫蜜.一種帶認(rèn)證的LU 密鑰預(yù)分配方案［J］.計(jì)算機(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ìn)算法及仿真［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 特點(diǎn)對(duì)DV－HOP 算法改進(jìn)的研究［J］.西安郵電學(xué)院學(xué)報(bào)，2012(6):24－26，55.

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