基于鄰居節點相似度的改進DV-Hop節點定位算法

廖惜春，楊志高，任敬哲

(五邑大學信息與通信工程學院，廣東江門529020)

近年來，隨著射頻通信技術、物聯網技術、嵌入式技術的迅速發展，無線傳感器網絡(Wireless Sensor Network，WSN)在國防軍事、交通管理、環境監測等領域得到廣泛應用和深入研究。其中，在目標跟蹤、環境監測等應用領域中，節點的位置信息至關重要。只有確定節點的確切位置，才能詳細地表征“在什么地點發生了什么事件”。若缺少節點的位置信息，則感知到的數據可能失去應用價值。因此傳感器節點在隨機播撒后，通過定位技術確定節點位置是十分必要的。

定位技術是WSN的核心技術之一。WSN的定位算法，可以根據實際應用中所需定位機制的不同，分成基于測距算法(Range-based)和無需測距算法(Range-free)兩大類。其中，基于測距的定位機制需要利用未知節點至信標點之間的距離或角度信息，采用三角測量法、三邊測量法或最大似然估計法，計算未知節點位置。而無需測距的定位機制則不需要預先知道未知節點至信標點之間的距離和角度信息，只需要通過網絡中節點間鄰近關系或節點的連通性等信息實現節點定位。如質心、APIT(Approximate Point-in-triangulation Test)定位、DV-Hop(Distance Vector-Hop)定位、Amorphous和MSD-MAP。由于無線傳感器網絡硬件設備的限制，無需測距的定位算法得到廣大學者的關注。

DV-Hop算法的“無需測距定位法”是研究人員關注較多的算法之一。學者們針對其定位精度較低的缺點，提出了許多改進方法，但尚未達到理想效果。文獻［1］采用的算法，雖然具有較高的定位精度，但通信開銷和計算量都較大。如果將RSSI引入DV-Hop算法，雖然可以提高定位精度，但增加了節點的硬件開銷。文獻［2］采用遺傳算法和模擬退火算法對DV-Hop算法進行改進，雖然降低了定位誤差，但是算法復雜，能源消耗多。文獻［3］提出采用粒子群優化的方法，但是該改進算法需要測量信號的方向，從而需要添加相應硬件設備，增加了節點的硬件成本。文獻［4］先獲得網絡中信標節點之間的平均跳距，再計算每個信標節點的平均跳距，進而獲得這兩個平均跳距之間的誤差，從而修正全網的平均跳距。文獻［5］針對DV-Hop定位算法在不規則網絡中的定位精度進行改進，考慮了未知節點與信標節點之間的路徑可能與信標節點間的路徑重合這一特性，對平均跳距進行修正，在一定程度上提高了定位精度，但是由于考慮的因素較少，所以定位精度提高的不是太明顯。

本文在對DV-Hop定位算法進行研究分析的基礎上，通過總結大量改進算法的優缺點之后，提出了基于鄰居節點相似度的DV-Hop改進算法。通過仿真分析，結果表明:算法可在無需增加節點硬件以及通信開銷的基礎上，提高節點的定位精度。

1 DV-Hop定位算法

1.1 DV-Hop 算法描述

DV-Hop算法的核心思想為將未知節點與信標節點之間的距離用信標節點間平均跳距和未知節點與信標節點之間的最小跳數的乘積來表示。然后通過三邊測量法或者最大似然估計法求出未知節點的坐標。定位的過程主要分為以下3個階段［6］:

1)測量未知節點與信標節點之間的最少跳數。采用經典的距離交換協議，使監測區域中所有未知節點獲取與信標節點間的跳數信息。

2)計算未知節點到信標節點的估計距離。每個信標節點獲得自身到其他信標節點的跳數以及其他信標節點的坐標后，計算信標節點i平均每跳的距離，稱為平均跳距di，計算公式為

式中:xi，yi為信標節點i的坐標;hij為信標節點i和j之間的最少跳數。

然后，信標節點將計算獲得的平均跳距di以廣播的形式通知網絡中的其他節點。

3)估計未知節點位置。未知節點利用到各個信標節點之間的最少跳數和平均跳距，求自身的估計坐標。假設(x，y)是未知節點N的坐標，(xi，yi)是第i個信標節點的坐標。未知節點N與信標節點i之間的估計距離為di，并且將未知節點N和網絡中所有信標節點的估計距離表達式整合成方程組，則有

將上述n個二元二次方程，轉化為AX=b的形式。其中

方程AX=b用標準最小二乘法求解得位置節點坐標為

1.2 DV-Hop 算法的不足

1)DV-Hop算法中，平均跳距是通過信標節點之間的最小跳數和信標節點之間的距離獲得。實際中，信標節點之間的距離為直線距離，最小跳數的每跳不一定在同一直線上，且每跳的跳距是不同的。如圖1所示。DV-Hop算法將信標節點之間的距離和最小跳數之商作為平均跳距。這一平均跳距會由于網絡中的節點稀疏程度和連通度的不同而出現不同程度的誤差。

圖1 節點多跳通信鏈路圖

2)用信標節點間的平均跳距與未知節點和信標節點之間的最小跳數的乘積，代替未知節點與信標節點之間的實際距離。其中未知節點和信標節點之間的最小跳數的通信路徑并非呈直線分布，且節點間跳距不同。所以通過此步驟獲得距離也會引入誤差。

2 DV-Hop改進定位算法

2.1 相關定義

1)鄰居節點:在無線傳感器網絡中，節點都有一定的通信半徑，處于此范圍之內的節點稱為該節點的鄰居節點。

2)鄰居節點相似度:無線傳感器網絡中的節點可以通過信息交換，獲取自身的鄰居節點ID號列表，并且和其他節點的鄰居節點列表作比較，節點間的鄰居節點列表中的節點ID號相同的數目越大，鄰居節點的相似度越大，其值為式中:δ可以改變節點間鄰居列表中ID號相同的節點數目對鄰居節點相似度的影響;Numcom指的是節點間鄰居列表中ID號相同的節點數目;Numi和Numj分別指未知節點i和j的鄰居節點數目。

2.2 改進算法要點

2.2.1 單跳節點處理

無線傳感器網絡中可以通過單跳直接和信標節點通信的未知節點。在DV-Hop中全部采用網絡中鄰近信標節點的平均跳距作為距離，實際中，網絡中較多的未知節點可以和信標節點直接通信，如圖2所示。未知節點和信標節點的距離也不盡相同。使用平均跳距作為這些節點與信標節點的距離，從而導致信標節點的鄰居節點區分度單一，而引入較大的誤差。所以，本論文在此處引入修正方法。

圖2 信標節點的鄰居節點

本文提出鄰居節點相似度的概念，通過網絡信息交換獲取節點的鄰居節點列表后，根據式(7)可以求出節點i與節點j的鄰居節點相似度εij。

對單跳節點進行修正后的距離為

2.2.2 多跳節點處理

余弦定理:已知三角形兩邊之長及其夾角，可以求得第三邊的長度。

根據余弦定理，在節點ABC組成的三角形中，如圖3所示。本文假設知道AB和BC的長度，以及∠ABC的度數θ。就可以根據余弦定理，求出AC的長度，這樣就將節點A到節點C之間的折線通信路徑轉化為求直線AC的長，表達式為

圖3 節點通信等效模型

未知節點間單跳跳距的修正方法，采用單跳節點處理方式，根據未知節點ABC的鄰居節點列表和式(7)、式(8)求出節點A到節點B和節點B到節點C的距離。

節點間的距離越近則鄰居節點的相似度越高，而節點距離越遠，鄰居節點的相似度越低。所以，本文將通過節點間鄰居節點的相似度來調整夾角θ的度數。如圖4所示，節點i和節點j恰好處于彼此的通信半徑之外時，節點k通過多跳模式傳遞信息，當節點k距離節點i和節點j距離最遠時，此時∠ikj的度數最小，且近似等于。

圖4 節點通信夾角最小情況

如圖5所示，節點i，j恰好位于各自通信半徑邊緣處，且節點k位于此交集處。此時，節點i，k，j組成一條直線，通信夾角最大，近似為π。節點i，j的距離最遠。

圖5 節點通信夾角最大情況

式中:εij通過式(7)獲得;γ為鄰居節點相似度所占權重值，改變其大小可以改變γ在通信夾角中的影響程度，γ值大小根據具體網絡連通情況和節點的疏密程度而定。

無線傳感器網絡中的任意三個通信節點ABC，如圖3所示。通過式(8)獲得AB和BC的長度，再通過式(10)獲取AB和BC的夾角。根據余弦定理，帶入式(9)，方可將實際中的折線通信距離轉化為求直線距離，減少了由于折線通信帶來的誤差。

2.3 改進算法實現

1)計算全網節點間的最小跳數

信標節點向鄰居節點以廣播的形式發送一個信標，包括位置信息字段和鄰居節點列表字段。其中位置信息字段包括自身坐標、ID號和跳數值，跳數值初始化為0。鄰居節點列表字段包括通信半徑內的所有節點的ID和鄰居節點的數目，初始化為NULL。

節點收到其他節點發來的信息后，位置信息字段更新坐標和ID號，同時跳數值加1;鄰居節點列表字段將接收到的位置信息中的ID號取出，存入鄰居節點列表中，鄰居節點數目加1，并繼續向其他鄰居節點廣播，通過這種泛洪方式向整個網絡傳播數據。若節點收到來自同一個節點的多個信息，則比較其跳數值，只保留最小跳數值的信息，這樣就保證了所得到的跳數值是到網絡中所有節點的最短路徑。

經過此階段，網絡中的所有節點都獲得各個信標節點的坐標，以及鄰近節點的ID號和個數。以及它到各節點的最小跳數。

2)計算未知節點和信標節點的實際跳距

每個信標節點根據第一步中獲取的到其他信標節點的位置信息和跳數，利用式(1)估計平均跳距di。

信標節點的鄰居節點中的未知節點根據式(7)求出未知節點和信標節點的相似度εi。并且將εi帶入到式(8)中修正di為d'i。

通過多跳間接和信標節點通信未知節點，距離修正處理如下:

對于和信標節點通信的節點采用兩跳通信的未知節點。首先，采用式(7)和式(8)修正未知節點i與信標節點的前驅節點j之間的單跳距離d'ij，然后結合信標節點的前驅節點j和信標節點B(即信標節點的鄰居節點)之間的修正距離d'jB。再根據式(10)求出未知節點i和信標節點B通過節點j通信的夾角θiB，帶入到式(9)中得到兩跳通信修正距離d'iB。表達式為

對于通過三跳或三跳以上和信標節點通信的節點采用和兩跳距離修正同樣的方法，先求出兩跳路徑后，再相互結合，直到獲取源節點到信標節點距離。通過此修正方法，使全網中的未知節點獲得到各個信標節點的修正距離。

3)計算未知節點坐標

將2)獲取的未知節點到各信標節點的修正距離，代入到式(2)中，使用最小二乘法，求得未知節點的坐標。

3 仿真結果極其分析

檢測區的范圍是100 m×100 m的正方形區域，隨機播撒100個節點。網絡中節點的通信半徑為R。δ和γ根據監測區域節點分布的疏密程度和連通度分別設置為0.9和1。未知節點坐標與實際坐標之間的相對定位誤差表示為

式中:erri代表每個未知節點的誤差;UN代表未知節點的個數。

通過對DV-Hop、參考文獻［5］算法、參考文獻［7］算法、本文算法進行仿真，并對實驗結果進行比較。從而證明了本文算法的有效性與可行性，圖6～圖9給出了網絡中的節點通信半徑不同時，隨著網絡中信標節點比例變化，三種算法的定位誤差比較結果。

圖6 R=30 m時定位誤差隨參考節點比例變化的情況

圖7 R=25 m時定位誤差隨參考節點比例變化的情況

圖8 R=20 m時定位誤差隨參考節點比例變化的情況

從圖中可以看出在相同的通信半徑下，本文改進算法和文獻［5］、文獻［7］的算法的定位誤差距均低于DV-Hop定位算法。通信半徑為30 m時，本文的改進算法比DV-Hop定位算法在相對定位誤差上降低了33.34% ～35.35%。比文獻［5］、文獻［7］定位算法降低了10.06% ～21.41%。且各個算法的定位誤差隨著信標節點比例的增加，定位誤差都不斷減小，且趨于平穩。當網絡中的信標節點數目一定時，隨著節點的通信半徑減小，節點的定位誤差也隨之減小。如當信標節點的比例為10%，節點的通信半徑分別為30 m時，DV-Hop定位算法獲得的未知節點的相對定位誤差為92.22%［5］，文獻［5］定位算法獲得結果為76.26%，文獻［7］定位算法獲得結果為78.14%，本文改進定位算法結果為58.48%;在不同的通信半經中，信標節點比例小于10%時，改進算法較DV-Hop定位算法的定位誤差降低了約32% ～35%，且與文獻［5］和文獻［7］的定位算法獲得的定位誤差降低了約18% ～20%。

圖9 R=15 m時定位誤差隨參考節點比例變化的情況

算法復雜度分析:文獻［1］將RSSI引入DV-Hop算法，在復雜度上增加了節點關于RSSI強度值計算的相關部分，并且算法需要額外的硬件成本。而文獻［2］和文獻［3］雖然采用了經典的遺傳算法、模擬退火算法和粒子群優化的方法對DV-Hop算法進行改進，這樣極大地增加了算法的復雜度，同時能源消耗多。同時文獻［3］還需要添加硬件設備，增加了硬件成本。文獻［5］主要針對未知節點與信標節點之間的路徑可能與信標節點間的路徑重合這一點進行修正，一定程度上提高定位精度，算法復雜度較低，但是由于考慮的因素較少，所以定位精度提高的不是太明顯。本文算法通過鄰居節點列表的比較，獲取鄰居節點相似度，并在此基礎上對節點的跳距進行修正，在此處略加大算法復雜度。但是節點定位精度卻得到較大的提高。

綜上所述，本文的改進定位算法，無論是相當于傳統的DV-Hop定位算法還是文獻［5］的定位算法，均在節點的相對定位誤差上都有了較大幅度的降低。

4 結論

本文針對DV-Hop定位算法在單跳通信中，處理信標節點的鄰居節點距離沒有區分度，統一采用平均跳數與單跳之積的形式表示，以及多跳通信中該算法沒有考慮折線通信，依然采用同樣的方式處理，從而導致該算法的定位精度較低的情況。同時，這一點也是文獻［5］沒有考慮到的。本文提出了鄰居節點相似度的概念，并應用此概念分別對單跳節點(鄰居節點)的距離進行修正，克服了DV-Hop定位算法在處理單跳節點時，采用同樣的距離表示距離信標節點的距離;在多跳通信中，結合余弦定理將DV-Hop和文獻［5］中的折線距離代替實際中的直線距離，轉化為求直線距離的運算，同時修正了多跳通信中每一跳的距離。使得本算法在定位過程中增加了節點跳距區分度，克服了DV-Hop定位算法和文獻［5］定位算法較單一的計算。由于本算法中的鄰居節點相似度綜合考慮了網絡的連通度和節點的疏密程度等因素，且可根據實際情況作出相應的調整。所以本算法的實際應用價值較高且具有較好的魯棒性。

但是，改進后的算法在提高定位精度的同時增加了算法復雜度，并且網絡中節點的鄰居節點列表的存取上需要占用節點額外的內存空間。這些不完善之處還需要后續進一步改進和深入研究。

［1］劉艷文，王福豹，段渭軍，等.基于DV-Hop定位算法和RSSI測距技術的定位系統［J］.計算機應用，2007，27(3):516-527.

［2］趙仕俊，孫美玲，唐懿芳.基于遺傳模擬退火算法的無線傳感器網絡定位算法［J］.計算機應用與軟件，2009，26(10):189-192.

［3］王馭鳳，王巖.基于矢量和粒子群優化的傳感器網絡節點定位［J］.計算機應用，2009，29(1):309-311.

［4］林金朝，劉海波，李國軍，等.無線傳感器網絡中DV-Hop節點定位改進算法研究［J］.計算機應用研究，2009，26(4):1272-1275.

［5］沈明玉，張寅.基于改進的平均跳距和估計距離的DV-Hop定位算法［J］.計算機應用研究，2011，28(2):648-650.

［6］章浩，李萍萍，張西良.無線傳感器網絡節點定位機制研究［J］.電視技術，2006，30(2):70-72.

［7］林金朝，劉海波，李國軍，等.無線傳感器網絡中DV-Hop節點定位改進算法研究［J］.計算機應用研究，2009，26(4):1272-1275.