周楊，秦嘉杭，李萬雷

（1.南京財(cái)經(jīng)大學(xué) 信息工程學(xué)院，南京 210046；2.南京郵電大學(xué)）

引 言

無線傳感器網(wǎng)絡(luò)是由大量隨機(jī)分布的傳感器節(jié)點(diǎn)組成，是一種分布式的、自組織的網(wǎng)絡(luò)。其關(guān)鍵技術(shù)包括：網(wǎng)絡(luò)拓?fù)淇刂?、?jié)點(diǎn)定位、時(shí)鐘同步、數(shù)據(jù)融合、路由協(xié)議等[1]。而節(jié)點(diǎn)定位問題則是無線傳感器網(wǎng)絡(luò)中的一個(gè)最為基本和重要的問題[2]。目前，無線傳感器網(wǎng)絡(luò)定位算法可以分為基于測距和基于非測距的定位算法[3]?；跍y距定位常用的測量方法有 TOA[4]、TDOA[5]、AOA[6]、RSSI[7]，盡管這些技術(shù)相對(duì)精度高，但是對(duì)硬件要求很高?；诜菧y距定位常用的測量方法有：DV－Hop[8]、質(zhì)心[9]、APIT[9－10]、MDS－MAP[11]。

DV－Hop為典型的基于非測距定位，其對(duì)硬件要求低，實(shí)現(xiàn)簡單。它的不足之處在于計(jì)算平均跳距及定位坐標(biāo)時(shí)會(huì)產(chǎn)生誤差。因此針對(duì)DV－Hop算法的缺陷，提出了一系列的改進(jìn)算法，參考文獻(xiàn)[12]對(duì)原始算法中的平均跳距進(jìn)行改進(jìn)，使用多個(gè)錨節(jié)點(diǎn)估算平均距離并且采用歸一化加權(quán)的平均跳距。參考文獻(xiàn)[13]提出了基于幾何學(xué)的定位算法，利用幾何學(xué)中的斜率方法來判斷錨節(jié)點(diǎn)間的位置關(guān)系，從中選取最優(yōu)的錨節(jié)點(diǎn)序列，從而更精確地確定未知節(jié)點(diǎn)。參考文獻(xiàn)[14]引入共線度的概念，利用共線度參數(shù)，動(dòng)態(tài)地調(diào)節(jié)未知節(jié)點(diǎn)可以收集的鄰居錨節(jié)點(diǎn)的距離閾值，挑選網(wǎng)絡(luò)中好的錨節(jié)點(diǎn)組進(jìn)行位置估計(jì)，最后再用加權(quán)估計(jì)機(jī)制來得到最終的節(jié)點(diǎn)位置估計(jì)。這些方法都在一定程度上提高了定位精度。

本文針對(duì)DV－Hop算法中計(jì)算平均跳距和三邊定位兩方面存在的定位誤差，提出了改進(jìn)的算法。首先利用全網(wǎng)平均跳距來糾正單個(gè)錨節(jié)點(diǎn)的平均跳距，然后在最后計(jì)算三邊定位時(shí)，利用節(jié)點(diǎn)間連通度的不同，選擇最優(yōu)組合的3個(gè)錨節(jié)點(diǎn)來參與定位，進(jìn)一步提高定位精度。

1 DV-Hop算法介紹

美國路特葛斯大學(xué)的Dragos Niculescu等人利用距離矢量路由和GPS定位原理提出一系列分布式定位算法，合稱APS，DV－Hop算法就是其中的一種。

DV－Hop分為3個(gè)步驟實(shí)現(xiàn)：

① 錨節(jié)點(diǎn)i廣播自身的位置信息IDi。初始跳數(shù)0，每發(fā)送一個(gè)節(jié)點(diǎn)信息，跳數(shù)就加1，然后轉(zhuǎn)發(fā)，直到網(wǎng)絡(luò)中所有的節(jié)點(diǎn)都收到錨節(jié)點(diǎn)的信息包。如果節(jié)點(diǎn)收到同一個(gè)錨節(jié)點(diǎn)不同的跳數(shù)信息，只取最小的跳數(shù)信息。

② 當(dāng)錨節(jié)點(diǎn)i接收到其他錨節(jié)點(diǎn)的位置和最小跳數(shù)信息后，就可以計(jì)算出平均每跳距離（Average Hop Distance，AHD）的計(jì)算公式：

其中，（xi，yi）、（xj，yj）分別為錨節(jié)點(diǎn)i、j的坐標(biāo)；hij為兩個(gè)錨節(jié)點(diǎn)之間的跳數(shù)。未知節(jié)點(diǎn)只接收離它最近的錨節(jié)點(diǎn)的AHDi，hopi為未知節(jié)點(diǎn)離最近錨節(jié)點(diǎn)的跳數(shù)，再根據(jù)跳數(shù)信息，即可算得未知節(jié)點(diǎn)與錨節(jié)點(diǎn)的距離P：

③當(dāng)未知節(jié)點(diǎn)獲得3個(gè)或者更多的錨節(jié)點(diǎn)信息時(shí)，可以利用三邊定位或者最大似然相似求出未知節(jié)點(diǎn)的位置。（x，y）為未知節(jié)點(diǎn)的坐標(biāo)，（xi，yi）為已知錨節(jié)點(diǎn)的坐標(biāo)。根據(jù)式（2）即可算出未知節(jié)點(diǎn)的坐標(biāo)：

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

本文主要對(duì)DV－Hop算法里的第2步和第3步進(jìn)行改進(jìn)，第1步與原算法相同。原算法中，在第2步計(jì)算平均跳距的時(shí)候，未知節(jié)點(diǎn)接收來自最近的錨節(jié)點(diǎn)的平均跳距。但是由于網(wǎng)絡(luò)節(jié)點(diǎn)分布的不均勻性，導(dǎo)致單個(gè)錨節(jié)點(diǎn)計(jì)算的平均跳距存在著一定的誤差，因此本文引入全網(wǎng)平均跳距與單個(gè)錨節(jié)點(diǎn)平均跳距的均值來修正原算法中的平均跳距。在第3步中，錨節(jié)點(diǎn)的位置信息對(duì)定位精度影響很大，本文利用節(jié)點(diǎn)間連通度的不同，選取最優(yōu)的3個(gè)錨節(jié)點(diǎn)，以減小定位誤差。

2.1 平均跳距的改進(jìn)

將全網(wǎng)平均跳距與單個(gè)錨節(jié)點(diǎn)估算出來的AHDi取平均來代替經(jīng)典算法中的平均跳距，這樣未知節(jié)點(diǎn)既有全網(wǎng)的估算信息，也具有離它最近的錨節(jié)點(diǎn)的估算平均跳距AHDi的局部信息。全網(wǎng)平均跳距公式為：

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

修正后的平均跳距AHD公式為：

2.2 基于選擇性的3個(gè)錨節(jié)點(diǎn)

基于選擇性的錨節(jié)點(diǎn)的定位算法[15]利用連通度的不同，在三邊節(jié)點(diǎn)定位時(shí)，選擇最優(yōu)的3個(gè)錨節(jié)點(diǎn)定位，使其定位誤差最小。節(jié)點(diǎn)分布圖如圖1所示。未知節(jié)點(diǎn)N1利用三邊定位時(shí)可以用不同的3個(gè)錨節(jié)點(diǎn)組（P，P，P）、（P1，P2，P4）、（P2，P3，P4）、（P1，P3，P4）來定位。而用最大似然估計(jì)計(jì)算時(shí)，則選用（P1，P2，P3，P4）來定位，這樣不同的錨節(jié)點(diǎn)組肯定會(huì)產(chǎn)生不同的定位位置。

圖1 節(jié)點(diǎn)分布圖

2.2.1 基本規(guī)則

用未知節(jié)點(diǎn)與每個(gè)錨節(jié)點(diǎn)的最小跳數(shù)來定義連通度，用數(shù)組來表示。比如N1到所有錨節(jié)點(diǎn)的連通度為[1，1，2，5]。這樣圖1中的所有的未知節(jié)點(diǎn)的連通度可以用數(shù)組表示，如表1所列。

表1 未知節(jié)點(diǎn)的連通度

用未知節(jié)點(diǎn)之間連通度差的絕對(duì)值的和來定義連通度的不同，比如N1與N2之間連通度的不同為∣1－2∣＋∣1－1∣＋∣2－1∣＋∣5－4∣＝3。這樣可以計(jì)算N1到其他所有未知節(jié)點(diǎn)的連通度的不同，如表2所列。

表2 N1到未知節(jié)點(diǎn)連通度的不同

由表2可以得出，N2、N3到N1連通度不同為3、4，而N4、N5到 N1連通度不同為9、11。說明 N1離 N2、N3更近。這一點(diǎn)也可以從圖1中看出。

2.2.2 確定最優(yōu)的3個(gè)錨節(jié)點(diǎn)

選擇性錨節(jié)點(diǎn)的節(jié)點(diǎn)分布圖如圖2所示。未知節(jié)點(diǎn)Nx代表未知節(jié)點(diǎn)的實(shí)際位置，N（i，j，k）為根據(jù)3個(gè)錨節(jié)點(diǎn)組合所估算的位置，R為節(jié)點(diǎn)的通信半徑，An是離N（i，j，k）最 近 的 錨 節(jié) 點(diǎn) ，Am為 通 信范圍R之外的任意錨節(jié)點(diǎn)。

An的位置情況有3種：在0.5R的通信范圍內(nèi)；在0.5R～R的通信范圍內(nèi)；在R通信范圍之外。這樣計(jì)算 AHD（i，j，k），m就有3種可能：

圖2 選擇性錨節(jié)點(diǎn)的節(jié)點(diǎn)分布圖

其中，AHD（i，j，k），m為根據(jù)3個(gè)錨節(jié)點(diǎn)組合所估算的位置節(jié)點(diǎn)與錨節(jié)點(diǎn)Am之間的平均跳距，AHDn，m為錨節(jié)點(diǎn)An與錨節(jié)點(diǎn)Am之間的平均跳距，AHDm為錨節(jié)點(diǎn)Am的平均跳距。

N（i，j，k）與 錨 節(jié) 點(diǎn) Am之 間 的 距 離 P（i，j，k），m可 以 計(jì) 算 出來，那 么 就 可 以 算 出 N（i，j，k）與 錨 節(jié) 點(diǎn) Am之 間 的 跳 數(shù)hop（i，j，k），m，公式為：

假設(shè)一共有n個(gè)錨節(jié)點(diǎn)，這樣 N（i，j，k）與 Nx計(jì)算出來的連通度的不同可以表示為

Nx選出最小的連通度不同的節(jié)點(diǎn)是最為靠近Nx的節(jié)點(diǎn)（即定位的誤差最小）。

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

為了驗(yàn)證算法理論的可行性，在100m×100m的區(qū)域中，對(duì)提出的改進(jìn)的DV－Hop算法用Matlab7.0進(jìn)行實(shí)驗(yàn)仿真，將實(shí)驗(yàn)結(jié)果與原DV－Hop算法和參考文獻(xiàn)[12]的算法進(jìn)行對(duì)比分析。仿真數(shù)據(jù)隨機(jī)運(yùn)行50次，最后取平均值。

3.1 測距誤差

測距誤差是指節(jié)點(diǎn)間的估算距離與實(shí)際距離的差值。在100m×100m的區(qū)域中，隨機(jī)分布100個(gè)節(jié)點(diǎn)進(jìn)行仿真實(shí)驗(yàn)，其中有一部分部署的是錨節(jié)點(diǎn)，是能夠獲知自身位置信息的節(jié)點(diǎn)，且錨節(jié)點(diǎn)和未知節(jié)點(diǎn)具有相同的通信半徑。通過設(shè)置不同的錨節(jié)點(diǎn)比例和節(jié)點(diǎn)通信半徑，比較改進(jìn)的算法與原DV－Hop算法對(duì)測距誤差的影響。圖3為通信半徑為10m時(shí)的測距誤差，圖4為通信半徑為20m時(shí)的測距誤差。

在同等條件下，改進(jìn)的測距誤差始終是低于原DVHop算法的，且不同的通信半徑對(duì)測距誤差也會(huì)產(chǎn)生不同的結(jié)果。圖3中，通信半徑為10m，改進(jìn)后的算法平均測距誤差比原算法降低1.45m；圖4中，通信半徑為20 m，改進(jìn)后的算法平均測距誤差比原算法降低1.67m。這是因?yàn)殡S著通信半徑的變化，會(huì)對(duì)節(jié)點(diǎn)間的跳數(shù)和平均跳距產(chǎn)生影響。由于本文改進(jìn)后的算法是用全網(wǎng)的平均跳距代替單個(gè)節(jié)點(diǎn)的平均跳距，這樣使得對(duì)平均跳距的估計(jì)更為準(zhǔn)確，估算距離也就越準(zhǔn)確，越接近實(shí)際的距離。

3.2 定位誤差

圖3 通信半徑為10m時(shí)的測距誤差

圖4 通信半徑為20m時(shí)的測距誤差

定位誤差（Localization Error，LE）是指通過定位算法測量估計(jì)的坐標(biāo)與實(shí)際坐標(biāo)之間的差值。用這種差值除以節(jié)點(diǎn)的通信半徑，就是定位誤差率。計(jì)算方法如下：

其中，（x，y）為未知節(jié)點(diǎn)的實(shí)際坐標(biāo)，（xi，yi）為定位算法所估計(jì)出來的坐標(biāo)；R為節(jié)點(diǎn)的通信半徑。

圖5和圖6是節(jié)點(diǎn)總數(shù)分別為100和300、節(jié)點(diǎn)通信半徑為10m時(shí)，本文改進(jìn)算法、DV－Hop算法和參考文獻(xiàn)[12]中的算法三者在錨節(jié)點(diǎn)比例不同時(shí)的定位誤差比較結(jié)果。從兩幅圖中可以看出，在相同的半徑和錨節(jié)點(diǎn)的環(huán)境下，改進(jìn)算法的定位誤差率要低于DV－Hop算法和參考文獻(xiàn)[12]中的算法。但是在錨節(jié)點(diǎn)比例較低的情況下，節(jié)點(diǎn)的定位誤差較大。這是因?yàn)殄^節(jié)點(diǎn)較少時(shí)，未知節(jié)點(diǎn)與錨節(jié)點(diǎn)之間的距離變遠(yuǎn)，導(dǎo)致計(jì)算平均距離時(shí)會(huì)產(chǎn)生很大的誤差。因此隨著錨節(jié)點(diǎn)比例的增加，能夠有效地減小定位誤差。

圖5中，當(dāng)錨節(jié)點(diǎn)的比例為30%時(shí)，DV－Hop的定位誤差率為43.25%，參考文獻(xiàn)[12]算法的定位誤差率為33.37%，而本文改進(jìn)算法的定位誤差率為28.34%。圖6中，當(dāng)錨節(jié)點(diǎn)的比例為30%時(shí)，DV－Hop的定位誤差率為26.89%，參考文獻(xiàn)[12]算法的定位誤差率為14.95%，而本文改進(jìn)算法的定位誤差率為10.21%。由此說明，本文的改進(jìn)算法要優(yōu)于其他兩種算法。這是因?yàn)樵趨⒖嘉墨I(xiàn)[12]中，只考慮了平均跳距一個(gè)因素對(duì)定位誤差的影響，而本文改進(jìn)算法則是從平均跳距的改進(jìn)和利用連通度的不同選取錨節(jié)點(diǎn)兩個(gè)方面考慮，使其定位誤差進(jìn)一步地減小。

圖5 節(jié)點(diǎn)總數(shù)為100時(shí)的定位精度

圖6 節(jié)點(diǎn)總數(shù)為300時(shí)的定位精度

結(jié) 語

本文首先介紹了DV－Hop算法的基本思想，針對(duì)經(jīng)典的DV－Hop算法中存在的定位精度不高的缺陷，提出了兩點(diǎn)改進(jìn)：

單個(gè)錨節(jié)點(diǎn)所估計(jì)的平均跳距來代替全網(wǎng)的平均跳距，會(huì)產(chǎn)生很大的誤差，因此平均跳距利用全網(wǎng)平均跳距與單個(gè)錨節(jié)點(diǎn)估計(jì)的平均跳距的均值來修正；

根據(jù)連通度的不同選擇最優(yōu)的三個(gè)錨節(jié)點(diǎn)進(jìn)行三邊定位計(jì)算，以提高定位精度。

仿真實(shí)驗(yàn)數(shù)據(jù)表明，改進(jìn)后的算法降低了測距誤差，與參考文獻(xiàn)[12]等提出的算法比較，定位誤差率進(jìn)一步降低，從而提高定位精度。且在改進(jìn)的過程中，沒有添加硬件成本。

[1] 李曉維，徐勇軍，任豐原.無線傳感器網(wǎng)絡(luò)技術(shù)[M].北京：北京理工大學(xué)出版社，2007：10－11.

[2] 黃布毅，何超前，李冬富，等.基于無線傳感器網(wǎng)絡(luò)的家庭報(bào)警系統(tǒng)設(shè)計(jì)[J].電子技術(shù)應(yīng)用，2007，33（1）：74－76.

[3] Guo Qing GAO，Lin Lei.An improved node localization algorithm based on DV－Hop in WSN[C]／／IEEE Conference on Advanced Computer Control（ICACC），Shenyang，2010：321－324.

[4] Harter A，Hopper A，Steggles Pete.The anatomy of a context aware application[J].Wireless Networks，2002，8（2－3）：187－197.

[5] Girod L，Estrin D.Robust range estimation using acoustic and multimodal sensing[C]／／IEEE International Conference on Intelligent Robusts and Systems，Maui，HI，2001：1312－1320.

[6] Niculescu D，Nath B.Ad hoc positioning system（APS）using AOA[C]／／INFOCOM 2003.Twenty－Second Annual Joint Conference of the IEEE Computer and Cormnunications San Francisco，USA，2003，IEEE Societies（3）：1734－1743.

[7] 王珊珊，殷建平，蔡志平，等.基于RSSI的無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)自身定位算法[J].計(jì)算機(jī)研究與發(fā)展，2008，45（S1）：385－388.

[8] Niculescu D，Nath B.DV Based Positioning In Ad－Hoc Networks[J].Journal of Telecommunications Systems，2003，22（1／4）：267－280.

[9] Bulusu N，Heidemann J，Estrin D.GPS－less low cost outdoor localization for very small devices[J].IEEE Personal Communications Magazine，2000，7（5）：28－34.

[10] 周四清，陳銳標(biāo).無線傳感器網(wǎng)絡(luò)APIT定位算法及其改進(jìn)[J].計(jì)算機(jī)工程，2009，35（7）：87－89.

[11] Hu Junfeng，Cao Jun，Zhao Yafeng，et al.A MDS－Based Localization Algorithm for Large－Scale Wireless Sensor Network[C]／／2010International Conference On Computer Design And Applications（ICCDA 2010），China，2010：566－570.

[12] 王新生，趙衍靜，李海濤.基于DV－Hop定位算法的改進(jìn)研究[J].計(jì)算機(jī)科學(xué)，2011，38（2）：76－78.

[13] 劉影，錢志鴻，劉丹，等.基于幾何學(xué)的無線傳感器網(wǎng)絡(luò)定位算法[J].光電子·激光，2010，21（10）：1436－1438.

[14] 吳凌飛，孟慶虎，梁華為.一種基于共線度的無線傳感器網(wǎng)絡(luò)定位算法[J].傳感技術(shù)學(xué)報(bào)，2009，22（5）：723－727.

[15] Linqing Gui，Thierry VAL，Anne WEI.Improving Localication Accuracy Using Selective 3Anchor DV－h(huán)op Algorithm[C]／／IEEE VTC Fall，San Francisco，CA ，2011：1－5.