一種基于跳數修正的DV-Hop定位算法

肖麗萍，劉曉紅

(燕山大學信息科學與工程學院，河北秦皇島 066004)

無線傳感器網絡WSN(Wireless Sensor Networks)是由部署在監測區域內的大量廉價微型傳感器節點通過無線通信方式形成的一個多跳的自組織的網絡系統［1］，其中節點定位技術是其關鍵技術之一。節點定位是根據本網絡內少數位置已知的節點(稱為錨節點)，按照某種定位機制來確定其它未知節點位置的過程。根據定位機制可將現有的無線傳感器網絡定位算法大致分為基于測距(Range-Based)的定位算法和無需測距(Range-Free)的定位算法［2］。前者定位精度相對較高，但需要測量相鄰節點之間的絕對距離或方位，且對網絡的硬件設施要求也比較高，后者僅根據網絡連通性等信息即可實現定位，因此無需測距的定位技術以其低功耗，低成本的優勢受到了越來越多的關注。

典型的無需測距的定位算法包括質心算法［3］、DV-Hop 算法［4－5］、APIT 算法［6］和 MDS-MAP［7］算法等，其中DV-hop算法巧妙地將網絡的連通信息和距離矢量信息轉化為近似的距離測量，是目前研究最廣泛的算法之一。文獻［8－12］都對該算法進行了不同程度的改進，但是仍然存在較大的定位誤差，因此本文提出了一種基于跳數修正的定位算法。

1 DV-Hop算法描述及存在的問題

DV-Hop算法是一種基于距離矢量的分布式定位算法，該算法的實現大致分為3個階段:

第1階段 網絡中的各錨節點通過典型的距離矢量交換協議向鄰居節點廣播自身位置信息分組，使得網絡中的所有節點獲得距錨節點的最小跳數信息。

第2階段 每個錨節點在獲得其它錨節點的位置和相隔的最小跳數信息后，根據下式計算錨節點i自身的平均每跳距離Ci:

式中，(xi，yi)、(xj，yj)為錨節點i與j的實際坐標，dij為錨節點i到其他錨節點的直線距離，且

hopsij為錨節點i與j之間的最小跳數(i≠j)。每個錨節點將計算得到的平均每跳距離以洪泛的方式廣播到網絡中，未知節點僅記錄接收到的第1個平均每跳距離(之后收到的丟棄)，并對該平均每跳距離立即轉發，再結合第1階段記錄的最小跳數可近似計算得到與各錨節點的距離。

第3階段 未知節點得到3個或3個以上錨節點的距離后，再利用三邊測量法或極大似然估計算法計算出自身的位置坐標，從而完成定位。

圖1 DV-Hop定位算法示意圖

假設p為待定位節點，p到錨節點i、j、k的最小跳數分別為hopspi、hopspj和hopspk，其中p與錨節點i之間的距離最短，因此p從錨節點i處獲得平均每跳距離值，即Cp=Ci，再結合第1階段記錄的最小跳數便可得到未知節點p到各錨節點的估計距離分別為:Cphopspi、Cphopspj、Cphopspk。然后運用三邊測量法計算節點p的位置坐標。

傳統的DV-Hop算法不需要直接測量節點之間的距離或角度信息，而是依賴于節點間的跳數。對于各向同性的密集網絡，各節點可以得到合理的平均每跳距離，從而達到較高的定位精度，但對于拓撲不規則的網絡，定位精度會明顯下降。這主要是因為實際應用中WSN的節點一般是隨機分布的，錨節點和未知節點之間往往不是直線路徑，且節點間實際每跳長度也不盡相同，因此運用相同的平均跳距去估計節點間的距離必定會產生較大的誤差。針對上述問題，學者們對其進行了不同的改進，如文獻［8］采用最小均方誤差法對平均跳距進行修正，并進行了迭代求精；文獻［9］引入多維平均跳距的概念來修正平均跳距；文獻［10］中對最小二乘法進行了加權；文獻［11］利用夾角對平均每跳距離修正；文獻［12］用所有錨節點的平均跳距對每個跳距進行修正，同時對不良節點進行了簡單處理，這些改進算法在一定程度上都起到了提高定位精度的作用，但仍有不足，本文重點對節點間的跳數進行修正。

2 DV-Hop定位算法的改進

傳統DV-Hop定位算法在計算節點間跳數時，在通信范圍內無論其相距多遠，都將其跳數估計為一跳，而每跳的距離不同，利用公式Cphopspi計算時，必然偏離實際距離，造成節點定位出現較大的誤差。如圖2中的錨節點L1與錨節點L2之間的最短路徑，其中每跳的長度都不同，只有最后一跳的長度接近于實際值，即節點的通信半徑，但用傳統DVHop定位算法計算錨節點間的最小跳數時仍然記為4跳，這必定會給最后的定位引入較大的誤差。

圖2 兩錨節點間的最短路徑

針對以上問題，本文提出了一種新的計算跳數的方法來降低由跳數引入的誤差。為了說明本文的改進算法，首先定義幾個參數。

定義1兩錨節點i與j之間的實際距離與所有節點的通信半徑R之比定義為理想跳數，用Hij表示，即:

定義2節點間實際跳數與理想跳數的相對誤差定義為偏離因子，用αij表示，即:

其中，hopsij為錨節點i與j之間的實際跳數值。偏離因子反映了節點間平均每一跳偏離理想跳數的程度，αij越大，表明實際跳數偏離理想跳數的程度越大，用此實際跳數代替理想跳數時引入的誤差就越大。

定義3假設錨節點i與j之間的實際跳數為hopsij，偏離因子為αij，定義跳數修正系數wij為:

其中n取正整數，當n=2時，定位效果最佳，下面給出本文的跳數修正算法。

2.1 錨節點間跳數

為了盡可能使實際跳數接近理想值，按下式對錨節點間跳數進行修正:

其中，hops'ij為錨節點間修正后的跳數，hopsij為錨節點間的實際跳數。

改進后的跳數與理想跳數的偏差為:

2.2 未知節點到錨節點間跳數的改進

傳統DV-Hop定位算法中未知節點計算距離錨節點的距離時采用距離矢量交換協議得到的是整數跳數，實際的跳數并非都是整數，因此由整數跳數計算未知節點到各錨節點的距離的必然存在誤差。針對這一不足本文對未知節點與錨節點間的跳數進行了修正。

①未知節點計算距其最近錨節點的跳數

假設未知節點p與錨節點i之間的實際跳數為hopspi，錨節點數為n，本文利用如式(7)進行修正，修正后的跳數為:

②未知節點計算距其它錨節點的跳數

未知節點p計算距其它錨節點的跳數時運用如式(8)進行修正:

式中wij由式(5)得到，hopspj為未知節點與其它錨節點間的實際跳數。在實際網絡中大多數未知節點到任兩錨節點的路徑會有部分重疊［13］，因此用兩錨節點間的偏離因子更能體現未知節點距離其它錨節點跳數偏離程度。

3 改進后的算法步驟

改進后的DV-Hop算法如下:

第1階段:與傳統算法相同，所有節點獲得到各錨節點的距離和跳數信息。

第2階段:各錨節點首先運用式(6)修正錨節點間的跳數，然后用修正后的跳數根據式(1)計算每個錨節點的平均每跳距離。

第3階段:未知節點分別運用式(7)、式(8)修正距其最近錨節點和其它錨節點的跳數，然后結合與其最近錨節點的平均每跳距離計算距離個錨節點的距離。最后對計算出的距離采用二維雙曲線定位算法［14］得到未知節點的位置估計坐標。

4 實驗仿真及結果分析

為了對改進算法進行驗證，本文首先對提出的跳數修正系數中的n取不同正整數值時的性能進行了仿真，并對傳統的DV-Hop算法、文獻［9］和本文的改進算法進行了仿真對比。仿真的網絡環境如下:傳感器節點隨機分布在100 m×100 m的正方形區域內(假設所有節點的通信半徑R都相同)，分別研究在不同的錨節點比例、不同節點個數和不同的通信半徑的條件下傳統算法和改進算法的定位誤差。

在無線傳感器網絡中，定義平均定位誤差error為所有未知節點的估計值與實際值的差值的平均值:

式中(x'i，y'i)和(xi，yi)分別為未知節點的估計位置和實際位置，K為仿真次數，un為未知節點總數。為了消除由于節點隨機分布造成的誤差的不穩定性，在相同的網絡環境下分別進行500次仿真實驗，然后取平均值。

定義歸一化平均定位誤差為平均定位誤差error與通信半徑R(單位:m)的比值:

圖3給出了改進算法在取不同跳數修正系數的情況下，定位誤差隨錨節點比例的變化曲線。從圖中可以看出，當跳數修正因子中n=2時，定位精度最優，所以本文算法中n都取2。

圖3 不同修正系數下的定位誤差

圖4給出了總節點數為100，通信半徑為20 m的情況下節點歸一化平均定位誤差與錨節點比例的關系曲線，由仿真結果可以看出，3種定位算法的歸一化平均定位誤差都隨錨節點比例的增加而減小，并逐漸趨于穩定，但本文改進算法的歸一化平均定位誤差較傳統DV-Hop算法降低了約10% ～15%，較文獻［9］降低了約4% ～8%。

圖4 節點歸一化平均定位誤差與錨節點比例的關系

圖5給出了錨節點比例為10%，節點通信半徑為20 m的情況下節點歸一化平均定位誤差與總節點個數的關系曲線，由仿真結果可以看出，3種算法的歸一化平均定位誤差都隨總節點數量的增加減小，并逐漸趨于穩定。這是因為節點所在區域不變的情況下，節點總數的增加將會使網絡中節點密度增大，從而提高了定位精度。同樣，本文算法的誤差小于傳統DV-Hop算法和文獻［9］的算法，而且這種優勢在總節點數較少的時候更加突出。

圖5 節點歸一化平均定位誤差與總節點個數的關系

圖6給出了錨節點比例為10%時節點平均定位誤差與通信半徑的關系曲線，由仿真結果可以看出，3種定位算法的平均定位誤差都隨節點通信半徑的增加而增大，這是因為通信半徑的增大導致了節點間跳數的誤差增大，從而使節點平均跳距誤差增大，而傳統算法和改進算法都是通過跳數和平均跳距來估計未知節點位置的，所以節點的平均定位誤差隨著節點通信半徑的增大而增大。但在相同的通信半徑情況下，本文算法的平均定位誤差低于傳統DV-hop方法和文獻［9］的定位誤差。

圖6 節點平均定位誤差與通信半徑的關系

5 結束語

本文針對傳統DV-Hop定位算法在隨機分布網絡環境中的局限性進行了改進。首先對錨節點間的最短跳數進行了修正，之后對未知節點與錨節點間的跳數進行了修正，仿真表明，該改進算法的定位誤差明顯優于傳統算法。該算法并沒有改變傳統DVHop算法的基本定位過程，且無需額外的硬件支持，具有較好的實用價值。

［1］孫利明，李建中，陳瑜，等.無線傳感器網絡［M］.北京:清華大學出版社，2005:149－151.

［2］王福豹，史龍，任豐原.無線傳感器網絡中的自身定位系統和算法［J］.軟件學報，2005，5(16):857－868.

［3］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.

［4］Niculescu D，Nath B.DV Based Positioning in Ad Hoc Networks［J］.Telecommunication Systems，2003，22(1－4):267－280.

［5］Niculescu D，Nath B.Ad-Hoc Positioning System(AP-S)［C］//Proc of the 2001 IEEE Global Telecommunications Conf.San Antonio:IEEE Communications Society，2001，2926－2931.

［6］He T，Huang C D，Blum B M，et al.Range-Free Localization Schemes for Large Scale Sensor Networks［C］//Proc of the 9th Annual Int’1 Conf on Mobile Computingand Networking.San Diego:ACM Press，2003，81－95.

［7］Shang Y，Ruml W，Zhang Y，et al.Localization from Mere Connectivity［C］//Proc of the 4th ACM Int’1 Symp on Mobile Ad Hoc Networking＆ Computing.Annapolis:ACM Press，2003，201－212.

［8］林金朝，陳曉冰，劉海波.基于平均跳距修正的無線傳感器網絡節點迭代定位算法［J］.通信學報，2009，30(10):107－113.

［9］胡蜂松，孟湘琴.多維平均跳距值的DV-Hop定位算法研究［J］.計算機工程與應用，2011，47(28):42－44，68.

［10］朱敏，劉昊霖，張志宏，等.一種基于DV-Hop改進的無線傳感器網絡定位算法［J］.四川大學學報(工程科學版)，2012，44(1):93－98.

［11］王新生，趙衍靜，李海濤.基于DV-Hop定位算法的改進研究［J］.計算機科學，2011，38(2):76－78，90.

［12］李輝，熊盛武，劉毅，等.無線傳感器網絡DV-HOP定位算法的改進［J］.傳感技術學報，2011，24(1):1782－1785.

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

［14］石為人，賈傳江，梁煥煥.一種改進的無線傳感器網絡DV-Hop定位算法［J］.傳感技術學報，2011，24(1):83－87.