摘要：在無(wú)線(xiàn)傳感器網(wǎng)絡(luò)中，節(jié)點(diǎn)定位占有極其重要的一席之地。無(wú)需測(cè)距方案中的DV-Hop算法因其計(jì)算簡(jiǎn)單易于實(shí)現(xiàn)得到廣泛應(yīng)用。傳統(tǒng)DV-Hop算法不能夠提供相對(duì)好的定位精度，為了保證定位的準(zhǔn)確性，文章對(duì)DV-Hop算法進(jìn)行了優(yōu)化。在優(yōu)化算法中，采用加權(quán)誤差修正錨節(jié)點(diǎn)的估計(jì)平均跳距使其更加接近實(shí)際值，之后采用二維雙曲線(xiàn)算法代替三邊法或最小二乘算法確定接近實(shí)際位置的待測(cè)節(jié)點(diǎn)坐標(biāo)。仿真結(jié)果驗(yàn)證了文章提出算法在無(wú)線(xiàn)傳感器網(wǎng)絡(luò)中定位的準(zhǔn)確性。

關(guān)鍵詞：無(wú)線(xiàn)傳感器網(wǎng)絡(luò)；節(jié)點(diǎn)定位；DV-Hop算法；加權(quán)誤差；平均跳距

中圖分類(lèi)號(hào)：TN929.5" 文獻(xiàn)標(biāo)志碼： A

作者簡(jiǎn)介：董晶（1993— ），女，助教，碩士；研究方向：物聯(lián)網(wǎng)。

*通信作者：陳智（1983— ），男，副教授，碩士；研究方向：電子信息科學(xué)與技術(shù)。

0" 引言

無(wú)線(xiàn)傳感器網(wǎng)絡(luò)（Wireless Sensor Networks，WSN）是一種具備自組織和通信能力的分布式傳感網(wǎng)絡(luò)系統(tǒng)，由分布在監(jiān)測(cè)區(qū)域內(nèi)具備低能耗收發(fā)器及有限處理數(shù)據(jù)能力的小型感知節(jié)點(diǎn)組合而成［1］。無(wú)線(xiàn)傳感器網(wǎng)絡(luò)能夠?qū)ΡO(jiān)測(cè)范圍內(nèi)的監(jiān)測(cè)物體進(jìn)行實(shí)時(shí)監(jiān)測(cè)、感知及數(shù)據(jù)采集，并將收集到的數(shù)據(jù)信息處理后發(fā)送給觀察者。傳感器、探測(cè)目標(biāo)以及觀測(cè)者是構(gòu)成WSN的重要組成元素［2］。WSN能夠通過(guò)相互協(xié)作的方式來(lái)探測(cè)、管理以及發(fā)送網(wǎng)絡(luò)覆蓋范圍內(nèi)監(jiān)測(cè)目標(biāo)的數(shù)據(jù)信息，并且將所監(jiān)測(cè)到的有用數(shù)據(jù)報(bào)告給監(jiān)測(cè)者。WSN主要承擔(dān)數(shù)據(jù)信息的收集、管理以及發(fā)送任務(wù)。WSN是采用無(wú)線(xiàn)網(wǎng)絡(luò)的途徑在傳感器和用戶(hù)之間進(jìn)行通信的，利用創(chuàng)建的通信鏈路通過(guò)節(jié)點(diǎn)間的相互配合來(lái)探測(cè)、管理以及發(fā)送網(wǎng)絡(luò)覆蓋范圍內(nèi)監(jiān)測(cè)目標(biāo)的數(shù)據(jù)信息。

節(jié)點(diǎn)定位技術(shù)是WSN的關(guān)鍵技術(shù)之一，根據(jù)是否需要測(cè)量節(jié)點(diǎn)間的距離，定位技術(shù)可分為基于測(cè)距（Range-based）算法和無(wú)需測(cè)距（Range-free）算法［3-5］。在無(wú)需測(cè)距的算法中，DV-Hop算法因其過(guò)程簡(jiǎn)單、便于計(jì)算、易于實(shí)現(xiàn)等優(yōu)點(diǎn)得到了廣泛應(yīng)用，但它不能滿(mǎn)足高精度定位的要求。早在2001年，Niculescu和Nath提出這個(gè)算法之后，很多領(lǐng)域的研究人員對(duì)此算法做了改進(jìn)，例如對(duì)平均跳距和最小跳數(shù)的修正以及算法的迭代優(yōu)化［6］等。劉鋒等［7］將待測(cè)目標(biāo)節(jié)點(diǎn)收到的錨節(jié)點(diǎn)單跳大小值按照距離遠(yuǎn)近程度賦予權(quán)重值，最終得到所有平均單跳距離的加權(quán)和，使估計(jì)出的單跳距離值更符合實(shí)際值，減小出現(xiàn)的定位誤差，確保了定位的精確度。趙曉青等［8］通過(guò)節(jié)點(diǎn)間距離差值和跳數(shù)取權(quán)值的方法對(duì)單跳距離值進(jìn)行修正，然后通過(guò)錨節(jié)點(diǎn)與待測(cè)目標(biāo)節(jié)點(diǎn)遠(yuǎn)離程度的不同，對(duì)兩者間估算的距離值進(jìn)行修正。祝宇鴻等［9］根據(jù)不同錨節(jié)點(diǎn)之間的距離估算出平均單跳距離值，通過(guò)最大值與最小值求均值來(lái)修正網(wǎng)絡(luò)中的平均單跳距離，得到更精準(zhǔn)的定位。秦鵬程等［10］將監(jiān)測(cè)區(qū)域進(jìn)行劃分，針對(duì)節(jié)點(diǎn)部署不均勻的情況，通過(guò)引進(jìn)可移動(dòng)的錨節(jié)點(diǎn)對(duì)監(jiān)測(cè)區(qū)域內(nèi)的錨節(jié)點(diǎn)進(jìn)行二次部署，避免由錨節(jié)點(diǎn)部署過(guò)于集中而引起的定位不準(zhǔn)確。本文在原DV-Hop算法的基礎(chǔ)上，通過(guò)對(duì)平均誤差取權(quán)值來(lái)修正網(wǎng)絡(luò)的單跳距離值，然后用二維雙曲線(xiàn)算法代替最小二乘算法，對(duì)算法進(jìn)行優(yōu)化，對(duì)待測(cè)目標(biāo)節(jié)點(diǎn)進(jìn)行更精準(zhǔn)的定位。

1" DV-Hop算法

DV-Hop算法是以距離矢量路由和GPS定位為核心思想的一種分布式定位方法，主要分為3步。

1.1" 第1階段 數(shù)據(jù)信息交換

這一階段，網(wǎng)絡(luò)中的每個(gè)錨節(jié)點(diǎn)將帶有自身位置信息分組的數(shù)據(jù)包通過(guò)泛洪的方式進(jìn)行廣播，其中數(shù)據(jù)包包含錨節(jié)點(diǎn)自己的位置信息、節(jié)點(diǎn)ID號(hào)以及自身到接收節(jié)點(diǎn)之間的跳數(shù)值（初值設(shè)為0），若接收節(jié)點(diǎn)接收到的信息包含至錨節(jié)點(diǎn)的最小跳數(shù)，則將跳數(shù)遞加1后的新跳數(shù)值傳遞到網(wǎng)絡(luò)中，并繼續(xù)轉(zhuǎn)發(fā)到下一個(gè)相鄰節(jié)點(diǎn)。此階段結(jié)束后，記錄所有節(jié)點(diǎn)相隔錨節(jié)點(diǎn)的最小跳數(shù)值。

1.2" 第2階段 距離計(jì)算

這一步，每個(gè)錨節(jié)點(diǎn)根據(jù)其他錨節(jié)點(diǎn)的位置信息及相隔最小跳數(shù)值，利用公式（1）估算平均單跳距離值。

HopSizei=∑i≠j（xi-xj）2+（yi-yj）2∑i≠jhij（1）

式中：（xi，yi）（xj，yj）是錨節(jié)點(diǎn)i、j的坐標(biāo)，hij是錨節(jié)點(diǎn)i和j（i≠j）之間的最小跳數(shù)。

得到出錨節(jié)點(diǎn)的平均單跳值之后，將該值作為一個(gè)校正值在網(wǎng)絡(luò)中進(jìn)行二次泛洪廣播。當(dāng)接收到校正值后，待測(cè)目標(biāo)節(jié)點(diǎn)僅僅只記錄收到的第一個(gè)單跳距離值，并將其作自己的平均跳距，由此確保很大一部分節(jié)點(diǎn)獲得的跳距值是從最靠近自己的錨節(jié)點(diǎn)得到的。由式（2）計(jì)算估計(jì)距離：

duv=HopSizei×hopuv（2）

式中，HopSizei是待測(cè)目標(biāo)節(jié)點(diǎn)u從最靠近自己的錨節(jié)點(diǎn)i獲得的跳距值，hopuv是未知節(jié)點(diǎn)u和錨節(jié)點(diǎn)v之間的最小跳距。

1.3" 第3階段 位置估計(jì)

當(dāng)待測(cè)每目標(biāo)節(jié)點(diǎn)獲得3個(gè)或更多至錨節(jié)點(diǎn)的估計(jì)距離值時(shí)，采用最小二乘算法求出待測(cè)目標(biāo)節(jié)點(diǎn)估計(jì)坐標(biāo)值。

未知節(jié)點(diǎn)p（x，y）到所有錨節(jié)點(diǎn)距離如下：

（x1-x）2+（y1-y）2=d21

（xn-x）2+（yn-y）2=d2n（3）

x21-x2n+2（x1-xn）x+y21-y2n-2（y1-yn）y=d21-d2n

（4）

x2n-1-x2n+2（xn-1-xn）x+y2n-1-y2n-2（yn-1-yn）y=d2n-1-d2n

式（4）可寫(xiě)為：

AX=B（5）

這里，

A=2（x1-xn）2（y1-yn）

2（xn-1-xn）2（yn-1-yn）

B=x21-x2n+y21-y2n+d21-d2n

x2n-1-x2n+y2n-1-y2n+d2n-1-d2n（6）

X=xy

根據(jù)最小二乘算法，通過(guò)公式（7）可求出待測(cè)目標(biāo)節(jié)點(diǎn)P的估計(jì)坐標(biāo)值。

P=（ATA）-1ATB（7）

DV-Hop算法主要發(fā)生了2次泛洪機(jī)制，第一次產(chǎn)生泛洪是節(jié)點(diǎn)記錄錨節(jié)點(diǎn)坐標(biāo)信息以及確定到錨節(jié)點(diǎn)的最小跳數(shù)值，第二次泛洪是把節(jié)點(diǎn)跳數(shù)轉(zhuǎn)化為距離值方便進(jìn)行定位。網(wǎng)絡(luò)中的錨節(jié)點(diǎn)利用第一次泛洪獲得的最小跳數(shù)值和節(jié)點(diǎn)距離得到節(jié)點(diǎn)平均跳距。在錨節(jié)點(diǎn)計(jì)算出平均單跳值之后，通過(guò)具有生存周期字段的消息分組再次泛洪廣播到網(wǎng)絡(luò)中，待定位節(jié)點(diǎn)只收錄首次收到的校正數(shù)據(jù)，忽略隨后收到的數(shù)據(jù)以確保節(jié)點(diǎn)的數(shù)據(jù)是從距自己最近的錨節(jié)點(diǎn)發(fā)出的。當(dāng)廣播結(jié)束后，待定位節(jié)點(diǎn)把收到距自己最近的錨節(jié)點(diǎn)平均單跳距離值當(dāng)做自身校正信息，然后與得到的跳數(shù)值進(jìn)行求積運(yùn)算得出距錨節(jié)點(diǎn)間的物理距離值。

2" 改進(jìn)的DV-Hop算法

在DV-Hop算法中，待測(cè)目標(biāo)節(jié)點(diǎn)將首次收到錨節(jié)點(diǎn)的單跳距離值作為自身跳距值，且假設(shè)節(jié)點(diǎn)間的通信路徑是一條直線(xiàn)，但是在實(shí)際情況中，由于網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的不同，節(jié)點(diǎn)之間的距離可能不在同一條直線(xiàn)上，這就導(dǎo)致計(jì)算出來(lái)的平均跳距與實(shí)際跳距有偏差，進(jìn)而未知節(jié)點(diǎn)的位置坐標(biāo)估計(jì)不準(zhǔn)確。針對(duì)以上問(wèn)題，本文主要從錨節(jié)點(diǎn)的平均單跳距離值及待測(cè)目標(biāo)節(jié)點(diǎn)位置估計(jì)方法2個(gè)方面對(duì)DV-Hop算法進(jìn)行優(yōu)化，使優(yōu)化之后的方法比原算法具有更優(yōu)越的性能。

2.1" 加權(quán)誤差修正平均跳距

DV-Hop算法在計(jì)算待測(cè)目標(biāo)節(jié)點(diǎn)與錨節(jié)點(diǎn)間距離時(shí)，采用首次收到的錨節(jié)點(diǎn)的跳段距離值進(jìn)行距離估計(jì)運(yùn)算，但在一般情況下，2個(gè)通信節(jié)點(diǎn)之間的路徑是非直線(xiàn)的，采用平均跳距值乘以最小跳數(shù)值來(lái)估算待測(cè)目標(biāo)節(jié)點(diǎn)坐標(biāo)就會(huì)出現(xiàn)很的大誤差，這里用錨節(jié)點(diǎn)到不同錨節(jié)點(diǎn)的單跳距離取均值［5］：

HopSizeavg=∑HopSizein（8）

這里n為網(wǎng)絡(luò)中錨節(jié)點(diǎn)個(gè)數(shù)。

定義Errori為平均每跳誤差，即：

Errori=HopSizeavg-HopSizei（9）

定義誤差權(quán)重為：

Weightedi=1Ni∑nj=11Nj（10）

這里Ni是錨節(jié)點(diǎn)之間的跳數(shù)。

定義加權(quán)誤差W_errori為：

W_errori=∑（Errori×Weightedi）（11）

重新計(jì)算跳距：

HopSizenewi=HopSizei+W_errori（12）

由此得到待測(cè)目標(biāo)節(jié)點(diǎn)到錨節(jié)點(diǎn)之間的近似距離值：

di=HopSizenewi×hopi（13）

2.2" 二維雙曲線(xiàn)算法

在估算坐標(biāo)位置方法中，本文將其中的二維雙曲線(xiàn)法替代最小二乘算法，對(duì)待測(cè)目標(biāo)節(jié)點(diǎn)的位置進(jìn)行估計(jì)運(yùn)算。

假設(shè)待測(cè)目標(biāo)節(jié)點(diǎn)位置坐標(biāo)為（x，y），錨節(jié)點(diǎn)位置坐標(biāo)為（xi，yi），di為待測(cè)目標(biāo)節(jié)點(diǎn)與錨節(jié)點(diǎn)之間的距離，顯然di的計(jì)算公式為：

di=（xi-x）2+（yi-y）2（14）

對(duì)（14）式兩邊求平方，得到下面方程式：

x2i+y2i-2xix-2yiy+x2+y2=d2i（15）

d2i-Ei=-2xix-2yiy+K（16）

其中Ei=x2i+y2i，K=x2+y2。

令Zc=［x，y，K］T，Gc=-2x1-2y11-2x2-2y21-2xi-2yi1，

Hc=d21-E1

d22-E2

d2i-Ei，

根據(jù)最小二乘算法，有：

Zc=（GTcGc）-1GTcHc（17）

待定位節(jié)點(diǎn)坐標(biāo)為：

x=Zc（1）

y=Zc（2）（18）

3" 實(shí)驗(yàn)仿真與結(jié)果分析

本文采用MATLAB仿真平臺(tái)對(duì)所提算法進(jìn)行性能評(píng)估，用MATLAB2016a作為模擬器來(lái)模擬實(shí)現(xiàn)網(wǎng)絡(luò)場(chǎng)景，選取邊長(zhǎng)為100 m的正方形作為仿真區(qū)域，節(jié)點(diǎn)分布如圖1所示，且每個(gè)實(shí)驗(yàn)在參數(shù)不變的情況下模擬實(shí)驗(yàn)進(jìn)行100次，求其平均值并繪制出對(duì)應(yīng)的誤差曲線(xiàn)圖，通過(guò)定位誤差分析該算法的性能，計(jì)算公式如下：

LocalizationError=∑ni=1（xesti-xtri）2+（yesti-ytri）2n×R（19）

其中，（xesti，yesti）是待測(cè)目標(biāo)節(jié)點(diǎn)估計(jì)坐標(biāo)值，（xtri，ytri）是待測(cè)目標(biāo)節(jié)點(diǎn)真實(shí)坐標(biāo)值，R為通信半徑，n為待測(cè)目標(biāo)節(jié)點(diǎn)總數(shù)。

將DV-Hop算法、Hadir等［11］算法、二維雙曲線(xiàn)算法及WEDV-Hop算法分別在算法參數(shù)改變的情況下進(jìn)行仿真對(duì)比與結(jié)果分析。

3.1" 通信半徑改變

由圖2可知，錨節(jié)點(diǎn)總數(shù)固定不變，隨著通信半徑逐的漸增大，DV-Hop算法、Hadir等［11］算法、二維雙曲線(xiàn)算法及WEDV-Hop算法的定位誤差波動(dòng)較明顯。這是因?yàn)楫?dāng)通信半徑增大，網(wǎng)絡(luò)的聯(lián)通性逐漸增強(qiáng)，定位精度明顯提高，當(dāng)通信半徑達(dá)到一定數(shù)值后，最終定位誤差趨于平穩(wěn)。通過(guò)比較，改進(jìn)后算法性能有所提升，平均誤差值有所下降，比原DV- Hop算法降低7%～15%，比Hadir等［11］算法降低5%～12%，比二維雙曲線(xiàn)算法降低3%～8%。

3.2" 錨節(jié)點(diǎn)數(shù)改變

在通信半徑相同情況下，錨節(jié)點(diǎn)數(shù)N分別為8、10、12、14、16、18、20時(shí)，4種算法的平均定位誤差波動(dòng)比較平緩，都趨于穩(wěn)定減小狀態(tài)。仿真結(jié)果如圖3所示，當(dāng)通信半徑為R=30 m時(shí)，WEDV-Hop算法比原DV-Hop算法有8%～10%的誤差降低趨勢(shì)。隨著錨節(jié)點(diǎn)數(shù)量的增加，誤差趨于穩(wěn)定狀態(tài)。

3.3" 節(jié)點(diǎn)總數(shù)改變

如圖4所示，通信半徑為30 m，錨節(jié)點(diǎn)總數(shù)不變的情況下，隨著網(wǎng)絡(luò)節(jié)點(diǎn)總數(shù)的增加，原DV-Hop算法、Hadir等［11］算法與雙曲線(xiàn)算法的定位誤差均有穩(wěn)定遞增趨勢(shì)。這由于網(wǎng)絡(luò)節(jié)點(diǎn)總數(shù)增加，待定位目標(biāo)節(jié)點(diǎn)數(shù)增多，網(wǎng)絡(luò)的聯(lián)通性變差，導(dǎo)致網(wǎng)絡(luò)中孤立節(jié)點(diǎn)增加，使整體定位準(zhǔn)確性下降。相較于其他3種算法，WEDV-Hop算法定位誤差略有增加。

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

本文提出的WEDV- Hop算法優(yōu)化了傳統(tǒng)的DV-Hop算法，考慮到多個(gè)錨節(jié)點(diǎn)平均跳距對(duì)定位誤差的影響，利用加權(quán)誤差來(lái)校正網(wǎng)絡(luò)平均跳離，通過(guò)" 二維雙曲線(xiàn)算法估計(jì)待定位目標(biāo)節(jié)點(diǎn)位置。仿真結(jié)果表明，在無(wú)須額外增加硬件設(shè)施的條件下，該算法有效地提高了節(jié)點(diǎn)定位的準(zhǔn)確性。

參考文獻(xiàn)

［1］OZDEMIR O，NIU R.Channel aware target localization with quantized data in wireless sensor networks signal processing［J］.IEEE Transactions，2009（3）：1190-1202.

［2］KUMAR S，LOBIYAL K．An advanced DV-Hop ocalization algorithm for wireless sensor networks［J］.Wireless Personal Communications，2013，71： 1365-1385.

［3］孫立明，李建中，陳瑜，等.無(wú)線(xiàn)傳感器網(wǎng)絡(luò)［M］.北京：清華大學(xué)出版社，2005.

［4］GAYAN S，DIAS D.Improved DV-HOP algorithm through anchor position re-estimation［C］//IEEE Asia Pacific Conference on Wireless and Mobile，August：28-30，2014.Piscataway，New Jersey，C2014：126-131.

［5］趙芝璞，吳棟，王艷，等.基于平均跳距和位置優(yōu)化的改進(jìn)DV-Hop定位算法［J］.系統(tǒng)仿真學(xué)報(bào)，2016（6）：1273-1280.

［6］許毅，陳立家，甘浪雄，等.無(wú)線(xiàn)傳感器網(wǎng)絡(luò)技術(shù)原理及應(yīng)用［M］.北京：清華大學(xué)出版社，2015.

［7］劉鋒，張翰，楊驥.一種基于加權(quán)處理的無(wú)線(xiàn)傳感器網(wǎng)絡(luò)平均跳距離估計(jì)算法［J］.電子與信息學(xué)報(bào)，2008（5）：1222-1225.

［8］趙曉青，毛永毅．基于誤差加權(quán)和距離修正的改進(jìn)DV-Hop算法［J］．計(jì)算機(jī)工程與應(yīng)用，2016（18）：117-121.

［9］祝宇鴻，歷彥愷，胡俊，等.基于跳數(shù)閾值和節(jié)點(diǎn)分類(lèi)的DV-Hop改進(jìn)算法［J］.吉林大學(xué)學(xué)報(bào)（信息科學(xué)版），2014（4）：407-412.

［10］秦鵬程，顏文，解培中.基于區(qū)域劃分錨節(jié)點(diǎn)移動(dòng)的DV-Hop定位算法：CN105848283A［P］.2016-08-10.

［11］HADIR A，ZINE-DINE K，BAKHOUYA M，et al.An improved DV-Hop localization algorithm for wireless sensor networks［C］.International Conference on Next Generation Networks and Services（NGNS），May 28-30，2014.Casablanca，2014.

（編輯" 王雪芬）

Improvement of DV-Hop positioning algorithm in wireless sensor networks

DONG" Jing， CHEN" Zhi*

（School of Computing and Artificial Intelligence，Lanzhou University of Information Science and Technology， Lanzhou 730300，China）

Abstract：" Node localization plays an signicant importance role in wireless sensor network. DV-Hop algorithm is a range free algorithm that is widely used of its simple calculation and easy implementation. Traditional DV-Hop algorithm cannot provide relatively better localization accuracy. To ensure the accuracy of localization， an improved DV-Hop localization algorithm is proposed. Under this localization algorithm， using a novel weighted error corrected the average jump distance of the anchor node， and then adopt two-dimensional hyperbolic function instead of the classic trilateration＼＼least square method to determine the locations of unknown nodes， which are very close to their actual locations. Simulations are conducted to validate the accuracy of our proposed localization algorithm in wireless sensor networks.

Key words： wireless sensor network; node location; DV-Hop algorithm; weighted error; average hop distance