黃俊杰，劉士興，干小宇，尹 坤

(合肥工業(yè)大學 電子科學與應用物理學院，安徽 合肥 230009)

無線傳感器網(wǎng)絡是由部署在一定區(qū)域內(nèi)的許多具有采集數(shù)據(jù)、處理數(shù)據(jù)和傳輸數(shù)據(jù)功能的傳感器節(jié)點組成，節(jié)點之間通過無線通信的方式構(gòu)成一個多跳的自組織網(wǎng)絡。無線傳感器網(wǎng)絡中有很多特定的應用需要獲取節(jié)點的地理位置信息，且較多網(wǎng)絡的運行與管理需節(jié)點位置信息的輔助。因此，對無線傳感器網(wǎng)絡中節(jié)點定位機制以及定位算法的研究有著重要意義［1］。

根據(jù)定位機制，將現(xiàn)有的定位算法分為兩種，即基于測距的定位算法(Range－based)和與距離無關(guān)(Range－free)的定位算法［2］。前者需額外增加硬件來測量相鄰節(jié)點間的絕對距離或者方位，并利用節(jié)點間的實際距離來計算未知節(jié)點的位置;后者無需額外硬件測量節(jié)點間的絕對距離或方位，而是利用節(jié)點間的估計距離計算未知節(jié)點的位置。常用的與距離相關(guān)的定位技術(shù)有RSSI、TOA、TDOA 和AOA。這類算法定位精度相對較高，但是成本與能耗開銷也較大。與距離無關(guān)的定位算法利用網(wǎng)絡的連通性進行定位，常用的有質(zhì)心算法、DV－Hop［3］、Amorphous［4］、APIT［5］等，這類算法成本和功耗較低，應用更加廣泛。

DV－Hop 算法是目前應用最為廣泛的定位算法之一，針對DV－Hop 算法改進研究，本文提出了提高節(jié)點定位精度的加權(quán)DV－Hop 算法和降低功耗的基于節(jié)點密度的定位算法。

1 DV－HOP 算法

DV－Hop 定位算法是由Niculescud 等人提出的一種基于距離矢量計算跳數(shù)的算法。其基本思想是將未知節(jié)點到信標節(jié)點之間的距離用平均跳距和兩者之間跳數(shù)的乘積表示，具體步驟如下［6］:

(1)信標節(jié)點信息泛洪廣播和所有節(jié)點獲取距離信標節(jié)點的最小跳數(shù)。信標節(jié)點采用泛洪廣播方式將其位置信息采用分組形式傳遞給其鄰居節(jié)點，廣播的信息包格式為:{Idi，xi，yi，Hopsi}，其中包含了該節(jié)點的標識Idi、位置坐標(xi，yi)以及跳數(shù)信息Hopsi，初始Hopsi的值為0。接收到此數(shù)據(jù)的每個節(jié)點將此信息記錄下來，然后繼續(xù)向其鄰居節(jié)點廣播，每廣播一次就將Hopsi加1，并將分組信息以{Idi，xi，yi，Hopsi}的格式存儲到自身的數(shù)據(jù)表中。當節(jié)點接收到有相同Id的數(shù)據(jù)包時，對兩個數(shù)據(jù)包中的Hopsi進行比較，如果新的跳數(shù)小于原表中保存的跳數(shù)，則用新跳數(shù)替換節(jié)點中的信息，這就意味著找到了一條更短的到達該信標節(jié)點的路徑。如果新的跳數(shù)大于節(jié)點中的跳數(shù)，則丟棄該數(shù)據(jù)包，也不再進行轉(zhuǎn)發(fā)。

(2)計算未知節(jié)點與信標節(jié)點的估計距離。經(jīng)第一步后，每個信標節(jié)點獲得了其他信標節(jié)點的位置和最小跳數(shù)。此時通過式(1)計算網(wǎng)絡中平均每跳的距離

式(1)中，(xi，yi)，(xj，yj)為信標節(jié)點i，j 的坐標;hi為信標節(jié)點i 與j(i ≠j)之間的跳段數(shù);HopSize 為求出的平均跳距。

(3)信標節(jié)點將平均跳距廣播到網(wǎng)絡，通過式(2)計算未知節(jié)點到信標節(jié)點的估計距離du，i

當未知節(jié)點得到3 個或更多節(jié)點之間的距離后，再通過3 邊測量法［7］或極大似然估計等數(shù)學方法計算未知節(jié)點的坐標。

2 加權(quán)DV－Hop 算法

在實際使用中，DV－Hop 算法的定位精度受到節(jié)點密度及其分布情況影響。網(wǎng)絡中信標節(jié)點的密度越大，分布越合理，則定位精度越高，反之則定位誤差大。

2.1 DV－Hop 算法誤差分析

在實際使用中，部署信標節(jié)點的成本較高，因而信號節(jié)點的總數(shù)不會很多。另外，節(jié)點通常是隨機放置在探測環(huán)境中，難以保證信標節(jié)點分布的合理性［8－9］。綜上，實際使用中，DV－Hop 定位算法會有較大的定位誤差。

DV－Hop 定位算法使用跳段數(shù)與平均每跳距離的乘積來得到未知節(jié)點與信標節(jié)點的估計距離。該種估算方法時會有較大誤差，如圖1 所示對應的網(wǎng)絡拓撲結(jié)構(gòu)。

圖1 DV－Hop 誤差分析

其中A1，A2和A3為信標節(jié)點，U1，U2，U3，U4，U5和A為未知節(jié)點。對于未知節(jié)點A，由于A2離其最近，所以A 應從A2獲取HopSize 值。由式(1)得HopSize=(40+25)/(2+5) =10.7，那么3 個信標節(jié)點與A 之間的距離分別為A1:10.7×3，A2:10.7×2，A3:10.7×3。但A 與3 個信標節(jié)點的真實距離分別為:50 m，40 m，50 m，這使得定位誤差較大。在該網(wǎng)絡中，A2與A3真實距離很小，僅略大于通信半徑，用A2與A3來估算每跳距離，所得的誤差就較大。

2.2 加權(quán)DV－Hop 算法

針對上文所提關(guān)于DV－Hop 定位算法中使用相同的平均跳距來計算未知節(jié)點到信標節(jié)點間距離的定位誤差問題，有學者提出了加權(quán)DV－Hop 定位算法［10－11］。該算法的基本思想是在DV－Hop 定位算法中，通過加權(quán)系數(shù)的大小體現(xiàn)不同信標節(jié)點對未知節(jié)點位置坐標運算中的影響力大小，然后通過加權(quán)平均跳距估算未知節(jié)點的位置。實際使用中，不同信標節(jié)點的加權(quán)系數(shù)Wi通過式(3)確定

其中，ni表示信標節(jié)點i 與未知節(jié)點之間的跳數(shù)。

根據(jù)式(4)，得未知節(jié)點的加權(quán)平均跳距為

使用加權(quán)后的平均跳距，代入DV－Hop 定位算法的第三步，計算出未知節(jié)點到信標節(jié)點之間的距離，再通過3 邊測量法或者極大似然估計等數(shù)學方法計算出未知節(jié)點的坐標。

3 基于節(jié)點密度的定位算法

加權(quán)DV－Hop 定位算法改進了DV－Hop 定位算法中對平均跳距的計算，但在該算法的執(zhí)行過程中仍然需進行兩次泛洪廣播，需要較大的通信開銷，也增加了節(jié)點的能耗。Amorphous 定位算法使用節(jié)點通信半徑代替DV－Hop 定位算法中的平均跳距，該方法只需一次泛洪廣播，但定位誤差較大。為此，本文提出了基于節(jié)點密度的定位算法。

假設二維平面中節(jié)點信息的傳播是以節(jié)點為中心，節(jié)點通信半徑為半徑的圓形區(qū)域，且節(jié)點之間的信息傳播是相互的。若一個面積為S 的仿真區(qū)域中有n個節(jié)點，則此仿真區(qū)域的節(jié)點密度為

仿真區(qū)域內(nèi)某一個節(jié)點的鄰居節(jié)點數(shù)為N，計算方法如下

由Kleinrock－Silvester 式［12－13］可知節(jié)點的每跳距離與節(jié)點的通信半徑和節(jié)點的鄰居節(jié)點數(shù)存在一定的關(guān)系

式中，dhop為計算出的跳距;R 為節(jié)點通信半徑;N 為鄰居節(jié)點數(shù)目。當N 已知時，dhop便可用R 表示，如圖2所示。

圖2 鄰居節(jié)點數(shù)與每跳平均距離關(guān)系

若直接使用該跳距乘以最小跳距計算未知節(jié)點到信標節(jié)點之間的距離，將會出現(xiàn)較大誤差，因而參考加權(quán)DV－Hop 定位算法的思想，在信標節(jié)點和未知節(jié)點之間的計算進行加權(quán)處理，得出加權(quán)跳距

通過式(8)，計算出的加權(quán)平均跳距乘以跳數(shù)，就可得到未知節(jié)點到信標節(jié)點i 的距離。當獲得3 個或以上距離信標節(jié)點的距離后，就可用3 邊測量法或者極大似然估計等數(shù)學方法計算出未知節(jié)點的坐標。

4 算法仿真驗證

采用Matlab 對上述算法進行仿真，并對仿真數(shù)據(jù)進行分析。仿真環(huán)境為100 m×100 m 的正方形區(qū)域，未知節(jié)點和錨節(jié)點隨機分布。下面對DV－Hop算法和改進算法的定位誤差和通信開銷在不同錨節(jié)點數(shù)目下進行評估。針對固定的錨節(jié)點數(shù)目，重復做50 次仿真，取平均值。假設未知節(jié)點的估算位置為(xc，yc)，節(jié)點的實際位置為(xi，yi)，則未知節(jié)點的定位誤差為

式中，R 為節(jié)點的通信半徑;N 為未知節(jié)點的個數(shù)。

仿真得到的定位誤差如圖3 和圖4 所示，采用加權(quán)DV－Hop 定位算法得到的定位誤差最小，基于節(jié)點密度的定位算法次之，兩種改進型算法的定位精度都優(yōu)于DV－Hop 定位算法。以圖3 為例，在通信半徑為20 m，信標節(jié)點個數(shù)為12 的條件下，DV－Hop 定位算法的誤差為45.47%，基于節(jié)點密度定位算法的誤差為43.09%，而加權(quán)DV－Hop 算法的定位誤差為42.16%。

圖3 節(jié)點個數(shù)與定位誤差的關(guān)系(R=20 m)

圖4 節(jié)點個數(shù)與定位誤差的關(guān)系(R=25 m)

通信開銷是節(jié)點在定位過程中主要的能耗，為評估不同算法的通信開銷，假設節(jié)點的通信半徑為20 m，分別對包含不同節(jié)點數(shù)目的區(qū)域進行算法仿真，最后收集定位過程中的數(shù)據(jù)包數(shù)來體現(xiàn)節(jié)點的能耗，仿真過程中不考慮信息包之間的沖突與丟失。仿真結(jié)果如圖5 所示，基于節(jié)點密度的定位算法比DV－Hop 定位算法和加權(quán)DV－Hop 算法功耗低。

圖5 算法通信開銷

5 結(jié)束語

介紹了現(xiàn)有DV－Hop 定位算法，分析了該算法存在定位精度低和通信開銷大的缺陷。加權(quán)DV－Hop定位算法有效提高了定位精度，但不能降低通信開銷。通過Matlab 仿真結(jié)果表明，基于節(jié)點密度的改進型定位算法，在節(jié)點定位誤差與節(jié)點的通信開銷上均有明顯的改善，適合于對節(jié)點能耗要求嚴格的場合。

本文討論的算法均是在理想狀態(tài)下進行的仿真，但現(xiàn)實環(huán)境中通常會因溫度、濕度以及大氣壓強等因素對節(jié)點定位造成影響。如何在考慮這些影響因素的前提下來提高節(jié)點的定位精度還有待進一步研究。

［1］ Bulusu N，Heidemann J，Estrin D.GPS－less low cost outdoor localization for very small devices［J］.IEEE Personal Communication，2000，7(5):28－34.

［2］ 孫利民，李建中，陳渝.無線傳感器網(wǎng)絡［M］.北京:清華大學出版社，2005.

［3］ Lin Jinchao，Chen Xiaobing，Liu Haibo.Iterative algorithm for locating nodes in WSN based on modifying average hopping distances［J］.Journal on Communications，2009，30(10):107－113.

［4］ Nagpal R.Organizing a global coordinate system from local information on an amorphous computer［D］.MA USA:MIT AI Laboratory，1999.

［5］ He Tian，Huang Chengdu，Blum B M，et al.Range－free localization schemes in large scale sensor networks［C］.San Diego，USA:Proceedings of the 9th Annual International Conference on Mobile Computing and Networking，MOBICOM'2003，2003:81－95.

［6］ 李曉維，徐勇軍，任豐原.無線傳感器網(wǎng)絡技術(shù)［M］.北京:北京理工大學出版社，2007.

［7］ Cao Yu，Chen Xiupeng，Yu Yang，et al.Range－free distance estimate methods using neighbor information in wireless sensor networks［C］.Proc IEEE 70th Vehicular Technology conference Fall，2009:1－5.

［8］ Tian Shuang，Zhang Xinming，Wang Xinguo，et al.A selective anchor node localization algorithm for wireless sensor networks［C］.International Conference on Convergence Information Technology(ICCIT)，2007:358－362.

［9］ Liu Shaoqiang，Pang Xinmiao，F(xiàn)an Xiaoping.Improved DVHop algorithm for higher positioning accuracy［J］.Chinese Journal of Sensors and Actuators，2010，23:1179－1183.

［10］馮江，朱強，吳春春.改進的DV－Hop 定位算法研究［J］.計算機工程，2012，38(19):74－77.

［11］Chen Hongyang，Sezaki K，Deng Ping，et al.An improved DV－HOP localization algorithm for wireless sensor networks［C］.Industrial Electronics and Applications，ICIEA 3rd IEEE Conference，2008:1557－1561.

［12］Nagpal R，Shrobe H，Bachrach J.Organizing a global coordinate system from local information on an Ad Hoc sensor network［C］.Palo Alto，CA，USA:Second International Workshop，IPSN 2003，2003.

［13］Erchin Serpe Din，Qasim M Chaudhari.Synchronization in wireless sensor networks ［M］.CA USA: Science Press，2011.