祝宇鴻，歷彥愷，胡 俊，姜華庚

(吉林大學通信工程學院，長春130012)

0 引言

隨著信息技術的發(fā)展，無線傳感網(wǎng)絡已經(jīng)廣泛應用在人們的日常生活中，而且由于其具有自組織、部署快捷、高容錯性和強隱蔽性等技術優(yōu)勢，因此非常適用于戰(zhàn)場目標定位、生理數(shù)據(jù)收集、智能交通系統(tǒng)和海洋探測等領域［1］。在這些應用中最重要的信息就是位置信息，因而實現(xiàn)精確的定位顯得特別重要。由于無線傳感節(jié)點受能量、運算能力、部署成本以及應用環(huán)境的限制，無法通過全部加裝GPS(Global Positioning System)模塊的方式實現(xiàn)精確定位，因此研究如何在傳感器網(wǎng)絡中實現(xiàn)高精度定位是一個熱點問題。

目前已有的定位技術按照其是否需要測距可分為基于測距的定位算法和無需測距的定位算法兩類。前者需要測量節(jié)點之間的距離或接收信號的角度，然后利用三邊法或最大似然估計法計算節(jié)點坐標。典型測距定位算法其實現(xiàn)技術手段主要有基于RSSI(Received Signal Strength Indication)［2-6］、基 于 時 間 差 (TDOA:Time Difference of Arrival)［7］和 基 于 角 度 (AOA:Angle of Arrival)等，上述算法能實現(xiàn)較高的定位精度，但往往需要額外硬件支持且計算比較復雜，因此部署成本較高。后者是根據(jù)網(wǎng)絡的連接關系，利用節(jié)點間的估計距離計算坐標位置。代表性算法有DV-Hop算法、APIT(Approximate Point-In-Triangulation Test)算法［8］和 MDS-MAP(Multi-dimensional Scaling Map)［9］算法，其中DV-Hop由于算法簡單、容易實現(xiàn)而得到了廣泛應用。然而算法存在定位精度不高、需要較高的信標節(jié)點比例、要求網(wǎng)絡均勻分布等缺點，對此學者們提出了很多改進措施，包括誤差修正［10］、最小均方估計［11］、質(zhì)心法［12］、最小二乘法［13］和 RSSI修正［14］。通過研究發(fā)現(xiàn)在信標計算跳距階段設置跳數(shù)閾值以及未知節(jié)點跳距計算階段對信標節(jié)點進行分類能很好地提高算法的性能，在此基礎上，筆者提出了基于跳數(shù)閾值和節(jié)點分類的DV-Hop改進算法，最后通過仿真驗證了改進算法的性能。

1 DV-Hop算法原理

1.1 DV-Hop算法描述

DV-Hop算法是由Niculescu等［15］提出的一種距離無關的基于距離矢量的定位算法?；驹硎窃诰W(wǎng)絡中設置一定比例的信標節(jié)點，利用這些節(jié)點的位置和跳數(shù)信息就可以估計節(jié)點間的跳距，未知節(jié)點到信標的距離可用跳距與跳數(shù)的乘積表示，最后利用三邊法或最大似然法計算未知節(jié)點的坐標。具體過程可分為3個階段。

第1階段:通過距離矢量交換協(xié)議所有節(jié)點獲得與其他節(jié)點的最小跳數(shù)值，所有信標節(jié)點獲得其他信標節(jié)點的位置信息。

第2階段:信標節(jié)點利用信標節(jié)點i的平均每跳距離

計算自身的平均每跳距離，并將此結果廣播到網(wǎng)絡中。式(1)中，(xi，yi)和(xj，yj)是信標節(jié)點的位置，hij是信標節(jié)點i到信標節(jié)點j的最小跳數(shù)。

未知節(jié)點接收到信標節(jié)點發(fā)送的跳距信息后，只保留距離其最近信標的信息，然后利用未知節(jié)點i到信標節(jié)點j的距離

計算其與信標節(jié)點的距離。式(2)中，hmin是未知節(jié)點j到信標節(jié)點i的最小跳數(shù)。

第3階段:未知節(jié)點計算出未知節(jié)點到3個或3個以上信標節(jié)點的距離后，可以利用三邊測量法或極大似然估計法計算未知節(jié)點的坐標。

假設未知節(jié)點的坐標為(x，y)，信標節(jié)點i的坐標為(xi，yi)，可得到系統(tǒng)方程

然后前m-1個方程分別減去最后一個方程，可將式(3)轉化為AX=b形式的線性方程組，其中

最后可采用最小二乘法求解，由式X=(ATA)-1ATb可求得未知節(jié)點的坐標值。

1.2 DV-Hop算法誤差分析

實際的傳感器網(wǎng)絡往往是隨機部署的，從而造成節(jié)點密度稀疏不一。在節(jié)點密集、分布均勻的區(qū)域DV-Hop算法能實現(xiàn)較高定位精度，而在節(jié)點稀疏的區(qū)域則不能實現(xiàn)良好的定位，這主要是因為算法中節(jié)點在計算跳距時未充分考慮網(wǎng)絡的分布狀況而引起的。圖1是無線傳感器網(wǎng)絡的局部連接圖，L1～L4是信標節(jié)點，N1～N8是未知節(jié)點。由圖1可知，N1到L2和L4的最小跳數(shù)為2，到L1的最小跳數(shù)為3，到L3的最小跳數(shù)為4。依據(jù)DV-Hop算法定位原理，N1會選擇L2或L4的計算結果作為自身跳距。然而由圖1可知，這4個信標節(jié)點距離N1都不是很遠，如果能充分利用其計算結果，則能獲得更好的定位結果。此外采用原算法信標計算跳距時，跳數(shù)為1的節(jié)點參與計算會引起較大誤差，因為只有經(jīng)過足夠多轉接節(jié)點才能更好地反應網(wǎng)絡的平均分布情況。

圖1 無線傳感器局部網(wǎng)絡Fig.1 Wireless sensors local network

2 算法的改進

針對1.2節(jié)關于DV-Hop算法的誤差分析結果，本節(jié)主要對原算法信標節(jié)點跳距的計算、未知節(jié)點跳距的計算以及未知節(jié)點到信標節(jié)點之間距離的計算進行了改進，主要涉及原算法的第2階段，改進后的算法如下。

2.1 信標節(jié)點跳距的計算

信標在計算每跳平均距離時，為更好地估計網(wǎng)絡的分布情況，盡可能選取那些距離較遠且中間經(jīng)過多個節(jié)點轉接的信標節(jié)點參與計算。信標節(jié)點可通過設定跳數(shù)閾值，只讓那些與其距離大于等于跳數(shù)閾值的節(jié)點參與每跳平均距離的計算，改進后的跳距計算公式如下

其中hi_thresh是信標節(jié)點i與其他信標節(jié)點的跳數(shù)閾值，其可根據(jù)信標節(jié)點之間的跳數(shù)信息

求得。其中hmin為信標i到其他信標節(jié)點的最小跳數(shù)值。

2.2 未知節(jié)點跳距的計算

在隨機部署的網(wǎng)絡中，節(jié)點的密度往往是稀疏不一的，某些未知節(jié)點可能與多個信標節(jié)點的距離最近，而另一些節(jié)點可能與多個信標節(jié)點的距離差不多。圖1中L2和L4是離未知節(jié)點N1最近的信標節(jié)點，而L1和L3離未知節(jié)點N1也不是太遠，DV-Hop算法以信標L2或L4的計算結果作為未知節(jié)點N1的跳距顯然不能取得更好的估計。對此本節(jié)提出了節(jié)點分類計算的方法，未知節(jié)點依據(jù)其與信標節(jié)點間的跳數(shù)信息將信標節(jié)點分為如下兩類:

第1類:算法中采用跳數(shù)信息度量未知節(jié)點與信標節(jié)點之間的距離，由于網(wǎng)絡部署的隨機特性，在未知節(jié)點一跳范圍內(nèi)往往會存在多個信標節(jié)點。對此類信標節(jié)點可以取其均值得到平均跳距其中hmin是未知節(jié)點i到最近的信標節(jié)點的跳數(shù)值，hij是未知節(jié)點i到信標節(jié)點j的最小跳數(shù)，M是網(wǎng)絡中信標節(jié)點的數(shù)目。

第2類:對于那些與未知節(jié)點跳數(shù)大于hmin的信標節(jié)點，以未知節(jié)點與其之間跳數(shù)的倒數(shù)作為權重因子，得到一個加權跳距

考慮到上述兩類跳距信息對定位的精度具有不同的影響，在這里引入影響因子ai，參數(shù)ai的取值范圍在0～1之間，參數(shù)ai的值可由跳數(shù)信息計算得到

最后可以得到未知節(jié)點i的跳距

2.3 未知節(jié)點到信標節(jié)點距離的計算

原始算法中，未知節(jié)點利用相同的跳距值計算其到不同信標節(jié)點的距離。考慮到其經(jīng)過路徑的差異性，顯然每條路徑的跳距是不同的，為了降低估算誤差并體現(xiàn)這種差異性，可利用對應信標節(jié)點的跳距DjHop進行修正，未知節(jié)點i到信標節(jié)點j的距離

3 仿真

為檢驗改進算法的性能，筆者對DV-Hop算法及改進算法進行了仿真。場景設置如下:在一個邊長為100 m×100 m的方形區(qū)域內(nèi)，隨機部署傳感器節(jié)點，部署后的節(jié)點是不可移動。通過仿真分別研究了信標節(jié)點比例、節(jié)點密度以及節(jié)點通信半徑對定位精度的影響，最終結果取1 000次仿真結果的均值。

3.1 仿真參數(shù)的定義

定義ei為節(jié)點測量誤差，假設節(jié)點i算法求得的坐標為(xi，yi)，實際坐標為(xi_true，yi_true)，節(jié)點的通信半徑為R，則

則網(wǎng)絡中所有未知節(jié)點的平均測量誤差eError及誤差的最大值eErrormax分別如下

3.2 仿真結果及分析

圖2是節(jié)點總數(shù)為100且信標節(jié)點比例為20%時，傳感器節(jié)點在100 m×100 m的方形區(qū)域內(nèi)隨機部署的仿真圖。由圖2可知，節(jié)點的分布稀疏不一，而且信標節(jié)點在圖中間部分明顯比其他部分密集。這樣的隨機分布情形會給定位算法的性能帶來諸多挑戰(zhàn)，同時也意味著原始算法性能存在可提升的空間。

圖3是節(jié)點數(shù)量為100個，節(jié)點通信半徑為30 m，信標節(jié)點比例從5%到40%變化時，DV-Hop算法和改進算法的仿真的結果。由圖3可知，隨著信標節(jié)點比例的提高，未知節(jié)點的平均定位誤差和最大定位誤差都相應減小，而且這種趨勢在信標比例從5%到15%變化時最為明顯，改進算法的平均定位誤差比原算法降低了約10%。

圖2 100個節(jié)點的隨機分布圖Fig.2 The random distribution figure of 100 nodes

圖3 信標節(jié)點比例對定位算法性能的影響Fig.3 Impact of beacon node ratio on the performance of location algorithm

圖4是節(jié)點通信半徑為20 m且信標節(jié)點比例為10%，節(jié)點數(shù)目從80～240變化時，對DV-Hop算法和改進算法進行仿真的結果。由圖4可知，隨著網(wǎng)絡中節(jié)點數(shù)目的增多，兩種算法的平均定位誤差和最大定位誤差都隨之降低，而且改進算法比原算法的定位誤差更小，最大降低了約11%。

圖4 節(jié)點密度對定位算法性能的影響Fig.4 Impact of node density on the performance of location algorithm

圖5是節(jié)點數(shù)目為100個，信標節(jié)點所占比例為10%，節(jié)點通信半徑從20～36 m變化時的仿真結果。由圖5可知，隨著節(jié)點通信半徑R的增大，平均定位誤差和最大定位誤差都越來越小，而且R在20～28 m時變化最大，改進算法的平均定位誤差比原算法降低了約10%。

圖5 節(jié)點通信半徑對定位算法性能的影響Fig.5 Impact of communication radius on the performance of location algorithm

4 結語

筆者在分析DV-Hop算法的基礎上，提出了基于跳數(shù)閾值和節(jié)點分類的改進算法。與其他改進算法相比，該算法具有定位精度更高、能更好地適應復雜地形(尤其是在隨機部署的傳感器網(wǎng)絡中性能更佳)、不需要額外的硬件支持等優(yōu)點。最后通過仿真分別檢驗了信標比例、節(jié)點密度和節(jié)點通信半徑對算法定位性能的影響。仿真結果表明，改進的算法的定位性能比原始算法顯著提高。然而由于仿真并不能完全反應實際應用情況，尤其是在地形復雜、環(huán)境惡劣的環(huán)境中，節(jié)點的通信范圍并不是嚴格意義上的圓形區(qū)域，可能會出現(xiàn)諸如單向鏈路、孤立節(jié)點等情況，下一步將深入研究這些現(xiàn)象對定位精度的影響。

［1］錢志鴻，王義君.面向物聯(lián)網(wǎng)的無線傳感器網(wǎng)絡綜述［J］.電子與信息學報，2013，35(1):215-227.QIAN Zhihong，WANG Yijun.Internet of Things-Oriented Wireless Sensor Networks Review ［J］.Journal of Electronics＆Information Technology，2013，35(1):215-227.

［2］SAHU P K，WUEHK，SAHOO J.DuRT:Dual RSSI Trend Based Localization for Wireless Sensor Networks［J］.Sensors Journal，IEEE，2013，13(8):3115-3123.

［3］KAREL HEURTEFEUX，F(xiàn)ABRICE VALOIS.Is RSSI a Good Choice for Localization in Wireless Sensor Network?［C］∥Advanced Information Networking and Applications(AINA)，2012 IEEE 26th International Conference on.［S.l.］:IEEE，2012:732-739.

［4］RAIDA AL ALAWI.RSSI Based Location Estimation in Wireless Sensors Networks［C］∥Works(ICON)，2011 17th IEEE International Conference on.［S.l.］:IEEE，2011:118-122.

［5］顧海軍，王永，崔啟帆，等.簡易WSN定位算法及其實現(xiàn)［J］.吉林大學學報:信息科學版，2013，31(5):443-448.GU Haijun，WANG Yong，CUI Qifan，et al.Simple Positioning Algorithm and Its Implementation Based on WSN ［J］.Journal of Jilin University:Information Science Edition，2013，31(5):443-448.

［6］杜巧玲，錢志鴻，王樹勛.無線傳感器網(wǎng)絡二維協(xié)作式定位方法［J］.吉林大學學報:信息科學版，2009，27(2):167-172.DU Qiaoling，QIAN Zhihong，WANG Shuxun.Cooperative Location Scheme for 2D Wireless Sensor Networks［J］.Journal of Jilin University:Information Science Edition，2009，27(2):167-172.

［7］PARK JANG WOO，PARK DAE HEON，LEE CHANGHOON.Angle and Ranging Based Localization Method for Ad Hoc Network［J］.Journal of Supercomputing，2013，64(2):507-521.

［8］ZENG Fanzhen，YU Min，ZOU Chengwu，et al.An Improved Point in Triangulation Localization Algorithm Based on Cosine Theorem［C］∥Wireless Communications，Networking and Mobile Computing(WiCOM)，2012 8th International Conference on.［S.l.］:IEEE，2012:12.

［9］馬震，劉云，沈波.分布式無線傳感器網(wǎng)絡定位算法MDS-MAP(D)［J］.通信學報，2008，29(6):57-62.MA Zhen，LIU Yun，SHEN Bo.Distributed Locating Algorithm for Wireless Sensor Networks-MDS-MAP(D)［J］.Journal on Communications，2008，29(6):57-62.

［10］SHRAWAN KUMAV，LOBIYAL D K.An Advanced DV-Hop Localization Algorithm for Wireless Sensor Networks［J］.Wireless Personal Communications，2013，71(2):1365-1385.

［11］CHEN Hongyang，KAORU SEZAKI，DENG Ping，et al.An Improved DV-Hop Localization Algorithm for Wireless Sensor Networks［C］∥Industrial Electronics and Applications，2008.ICIEA 2008.3rd IEEE Conference on.Singapore:IEEE，2008:1557-1561.

［12］TOMIC S，MEZEI I.Improved DV-Hop Localization Algorithm for Wireless Sensor Networks［C］∥2012 IEEE 10th Jubilee International Symposium on Intelligent Systems and Informatics.［S.l.］:IEEE，2012:389-394.

［13］朱敏，劉昊霖，張志宏，等.一種基于DV-HOP改進的無線傳感器網(wǎng)絡定位算法［J］.四川大學學報:工程科學版，2012，44(1):93-98.ZHU Min，LIU Haolin，ZHANG Zhihong，et al.An Improved Localization Algorithm Based on DVHOP in WSN［J］.Journal of Sichuan University:Engineering Science Edition，2012，44(1):93-98.

［14］ZHANG Dengyin，GUO Dong.A Union Node Localization Algorithm Based on RSSI and DVHop for WSNS ［C］∥Instrumentation，Measurement，Computer，Communication and Control(IMCCC)，2012 Second International Conference on.Hangzhou:IEEE，2012:1094-1098.

［15］NICULESCU D，NATH B.Ad Hoc Positioning System(APS)［C］∥Global Telecommunications Conference.San Antonio，TX:IEEE，2001:2926-2931.