無線傳感器網絡DV-Hop定位算法

叢珊，陳桂芬

（長春理工大學 電子信息工程學院，長春 130022）

無線傳感器網絡是目前國際上備受關注的研究領域，微機電系統、無線通信和嵌入式技術的進步推動了無線傳感器網絡的發展，無線傳感器具有十分廣闊的應用前景［1］。無線傳感器網絡是由大量傳感器節點以自組織和多跳的方式構成的無線網絡［2］，其目的是將感知、采集和處理的數據和信息傳送給監控中心或終端用戶，實現“人與物”之間、“物與物”之間的通信。在軍事領域，無線傳感器網絡在戰場監視、國土安全、戰場偵察、目標定位、目標跟蹤等方面起到很重要的作用。近年來，已經由最初的軍事應用發展到民用領域，例如環境監測、工業控制、醫療健康、智能家居、科學探索和公共安全等方面，使人們可以即時地得到有效的消息，從而提高了人民的生活質量。其中，定位技術是無線傳感器網絡許多應用中的基礎技術。節點定位是根據少數位置已知的節點通過定位算法確定位置未知的節點信息，在無線傳感器網絡中建立起節點之間相互關聯的定位機制［3］。目前，最有名在無線傳感器網絡中應用得比較廣泛的是GPS（全球定位系統），雖然它能夠獲得很高的位置精度，但是不適合使用在大規模的傳感器節點中。首先，一個GPS接收器至少需要三個衛星確定目標位置，這在很多情況下是不可能的，例如室內和地下。第二，在計算環境中，小型的傳感器節點對于大型昂貴的GPS接收機是不適合的。最后，傳感器節點一般會部署在環境比較惡劣，或者人類無法到達的地區，電池無法更換，GPS接收機消耗了太多了的能量，大量的用在傳感器節點上能耗太大。所以，GPS不符合無線傳感器網絡的要求，如果傳感器帶有GPS，價格昂貴，會導致資源浪費。所以，利用傳感器節點進行定位在很多實際應用中是很重要的，提出一種花費少，能耗低同時定位精度高的定位算法是很有實際意義的。定位技術有很多中不同的分類方法，目前，應用較多的分類方法是基于測距（range-based）與無需測距（range-free）的定位算法［4］，其中，基于測距的定位技術需要測量節點之間的距離［5］，雖然定位精度高，但是其對硬件的依賴性大，功耗大?？紤]到能耗和花費的原因，人們對無需測距定位算法的關注度更高。因為無需測距定位算法主要依靠網絡的連通性進行定位［6］，花費低，易實現，而且可以滿足大多數應用對精度的要求。在無需測距的定位算法中，DV-Hop算法應用得比較廣泛。

1 DV-Hop定位算法

美國學者Dragos Niculescu和Bsdri Nath等人基于距離矢量路由和GPS原理設計了一系列分布式定位算法，統稱為APS［7］，其中包括DV-distance算法、DV-Bearing算法、DV-Radial算法、DV-Hop算法、Euclidean算法和DV-coordinate算法。在這六種算法里面，DV-Hop定位算法應用的比較廣泛，其原理與距離矢量路由算法比較相似。DV-Hop算法的主要思想是用未知節點到錨節點的最小跳數乘以距離未知節點最近的錨節點的平均每跳距離，之后計算未知節點與錨節點的距離，進而計算未知節點的位置，主要分為以下三個階段：

第一階段：節點獲得與錨節點的最小跳數［8］。錨節點以泛洪方式向網絡中廣播數據包，信息包括錨節點的ID、位置信息和一個初始值為0的跳數值，格式如。錨節點的信息包數據會被接收節點接收并且記錄，之后把跳數加1再傳遞給下一個節點，在信息傳遞的整個過程里，節點或許會多次接收到同一個錨節點的數據包，節點對同一個錨節點數據信息的跳數信息進行比較，具有最小跳數的值的信息包被篩選并記錄下來，然后丟掉具有較大跳數值的信息包。

第二階段：計算錨節點與未知節點的距離［9］。當每個錨節點都知道與網絡中除該節點之外的其余錨節點的最小跳數信息后，用式（1）計算其平均每跳距離：

式中，HopSizei表示錨節點i的平均跳距，坐標(xi,yi)，(xj,yj)分別表示錨節點i與錨節點j的坐標，hij為節點i與節點j之間的最小跳數。

每個錨節點的平均每跳距離被計算出來之后，錨節點把自己的平均每跳距離向整個網絡傳播，未知節點接收錨節點的平均每跳距離，并且保留距離它最近的錨節點的平均每跳距離，用該平均每跳距離乘以未知節點與錨節點的最小跳數，就是未知節點與錨節點間的距離，如式（2）所示：

式中，dij表示未知節點j與錨節點i的距離，HopSizei表示距離未知節點j最近的錨節點i的平均每跳距離，hij是未知節點j和錨節點i間的最小跳數。

第三階段：計算未知節點的位置。當用上述方法計算出未知節點到三個或者三個以上錨節點的距離時，用三邊定位法或者極大似然估計法計算未知節點的估計位置。

1.1 DV-Hop定位算法的缺點

（1）傳統的DV-Hop定位算法是把距離未知節點最近的錨節點平均每跳距離作為未知節點的平均每跳距離。該平均每跳距離與未知節點到錨節點的最小跳數相乘可以得到兩個節點之間的距離。但是在實際應用中，傳感器節點是隨機分布的，所以網絡節點平均每跳距離與實際的距離是有偏差的。

（2）傳感器節點的密度也會影響定位的精度。在傳感器節點密度大的區域，節點間實際的距離較小，在節點密度小的區域，實際的距離較大，如果仍然用平均每跳距離計算節點間的距離會與實際的距離有很大的偏差。

（3）在最后的定位階段，三邊定位法雖然計算簡單，但是對誤差比較敏感。而極大似然估計法在一定程度上減小了誤差，但是其計算起來較為復雜，得出的定位結果還是存在較大誤差。

針對DV-Hop定位算法在定位過程中的缺陷，文獻［10-13］對其進行改進：文獻［10］針對第三步中使用多邊定位法估計未知節點坐標存在較大誤差，提出來多邊定位法和泰勒級數展開法相結合的改進算法，首先用多邊定位法初步估計節點位置，然后利用估計位置作為初始值，對坐標進行迭代運算；文獻［11］對節點設定了優先級，直接由三個或者三個以上錨節點定位的節點級數最高，為一級節點，在二級節點的定位中把一級節點看成錨節點進行定位，以此類推，可逐級得到位置節點較低的節點的坐標；文獻［12］首先用整個網絡所有錨節點的平均每跳距離相加，除以錨節點個數得到整個網絡的平均每跳距離，然后求得整個網絡的平均定位誤差，最后用平均定位誤差修正未知節點的坐標。文獻［13］針對傳統定位算法中，兩個節點之間距離小于網絡通信半徑就記為一跳，當兩個節點之間距離很小時，誤差比較大的情況下，提出了多通信半徑的改進算法。

2 改進算法

2.1 加權DV-Hop定位算法

傳統的定位算法利用距離未知節點跳數最少的錨節點的平均每跳距離作為未知節點的平均每跳距離，而加權的DV-Hop定位算法則是綜合考慮所有錨節點的平均每跳距離，根據錨節點和未知節點之間的跳數作為不同平均每跳距離的權值的衡量值，權數的大小可以反映錨節點對未知節點平均每跳距離的影響，能夠有效減小由于使用單個錨節點的平均每跳距離造成的估計位置誤差。一個未知節點所有的權值相加等于1，假設未知節點一共接收到N個錨節點的平均每跳距離，到錨節點i的距離為Ni，那么該錨節點的權值可以用下式表示：

從上式能夠看出，未知節點與錨節點間的最小跳數可以反映權值的大小，兩者是反比的關系，未知節點與錨節點的最小跳數越大，那么對應的權值越小，未知節點與錨節點的最小跳數越小，那么對應的權值越大。假設錨節點i的平均每跳距離是di，其對應的權值是Wi，那么未知節點的平均每跳距離可用式（4）表示：

改進算法考慮了網絡中所有錨節點的平均每跳距離，與傳統的算法相比可以減小定位誤差，提高定位精度。

2.2 Min-Max修正算法

用上述方法對DV-Hop算法進行改進之后，還是會存在個別節點定位不精確的問題，所以接下來需要對第三步進行改進，在未知節點用三邊定位法或者極大似然估計法計算坐標后，用Min-Max修正算法對未知節點的位置進行修正，修正算法的基本原理為：取距離未知節點最近的三個錨節點，以錨節點到未知節點的距離的2倍為邊長做出正方形，三個正方形會有重疊區域，如果未知節點位于重疊區域中，則不修改坐標，若未知節點不在重疊區域中，則需要修改坐標。

如果三個錨節點的坐標分別(x1,y1)、(x2,y2)、(x3,y3)，到錨節點的距離分別為d1、d2、d3，那么重疊部分可以表示為：

如果未知節點的估計坐標在重疊區域內，那么就認為定位不存在誤差，不需要對位置進行修正，如果未知節點的估計坐標不在重疊區域內，那么需要對位置進行修正，假設未知節點原來計坐標為(x,y)，修正后的坐標為(X,Y)，用如下公式進行修正：

當x＜max(xi-di)時，X=max(xi-di)；

當x＞max(xi-di)時，X=max(xi+di)；

當y＜max(yi-di)時，Y=max(yi+di)；

當y＞min(yi-di)時，Y=min(yi+di)。

從上述算法改進原理可以看出，在Min-Max修正算法中，幾乎都是一些加減算法，存在較少的乘法，總體來說沒有復雜的運算。在實際的應用中，定位的延遲時間與能量的消耗都不高，非常適合用于成本不高、能量有限和對實時性要求較高的無線傳感器網絡中，所以Min-Max修正算法是非常具有實際運用價值的。

改進后算法步驟如下：

（1）錨節點以泛洪方式向網絡中廣播信息包，節點獲得與錨節點的最小跳數。

（2）計算整個網絡中所有錨節點的平均每跳距離，用加權改進算法計算每個未知節點新的平均每跳距離。未知節點新的平均每跳距離乘以未知節點與錨節點之間的最小跳數，求得未知節點到錨節點的距離。

（3）當未知節點獲得到三個或者三個以上錨節點距離時，用三邊測量法或者極大似然估計法計算未知節點坐標［14］。

（4）用Min-Max修正算法修正未知節點坐標，若節點估計坐標在正方形相互重疊區域內，則不需要對節點坐標進行修改，若節點的估計坐標不在正方形的相互重疊區域內，則需要對未知節點坐標進行修正。

3 算法仿真

為了更加充分了解改進算法的定位精度，用Matlab 2016a對算法進行仿真。在100m×100m的感知區域內，隨機的分布著傳感器節點，通信半徑為20米，其中有未知節點，有一部分是攜帶GPS的位置已知的錨節點，下面分別討論錨節點比例、總節點數對傳統定位算法與改進算法的定位精確度的影響，每種仿真都進行100次，然后取這100次結果的算術平均值作為最后的結果，其中節點定位誤差可用式（6）表示，E為節點定位誤差，(x,y)是節點的實際坐標，(X,Y)是節點的估計坐標，R是節點的通信半徑。已被定位的未知節點的定位誤差相加總和除以其個數等于節點的平均定位誤差。

圖1表示傳感器節點的分布圖，在100m×100m的正方形區域內隨機生成100個傳感器節點，其中錨節點的個數是8個，未知節點的個數是92個。

圖1 節點分布示意圖

圖2為錨節點的比例分別為5%、10%、15%、20%、25%、30%時，對傳統算法與加權DV-Hop定位算法定位精度進行比較。從圖中能夠看出，錨節點比例為5%時，加權定位算法與傳統定位算法的誤差幾乎一樣，隨著錨節點比例增加，誤差逐漸拉開，錨節點比例為20%時，加權算法對比傳統算法的精度提高的最多，達到3.5%，之后，加權定位算法精度提高的比例有所減少?？傮w來說，改進的加權定位算法提高了定位精度，減小了定位誤差。

圖3為錨節點的比例分別為5%、10%、15%、20%、25%、30%時，傳統算法與Min-Max修正算法的定位誤差比較。從圖中可以看出用Min-Max修正算法對節點位置進行修正后定位誤差明顯比傳統定位算法小，在錨節點比例為20%時，高了5.3%，雖然在錨節點比例大于25%時，定位誤差降低的比例有所減少，但是定位精度仍然比傳統定位精度高。

圖2 錨節點比例與定位誤差的關系

圖3 錨節點比例與定位誤差的關系

圖4為錨節點個數一定，總節點數分別為100，120，140，160，180，200，220時，Min-Max修正算法與傳統算法的誤差比較。從圖中可以看出當節點總數較少時，Min-Max修正算法的定位效果明顯比傳統的定位算法要好，隨著節點總數的增加，當節點總數大于130時Min-Max修正算法與傳統算法定位誤差越來相近，所以Min-Max修正算法不適用于節點總數較大的情況，但是在實際應用中增加總節點數勢必會增加花費，所以Min-Max修正算法還是有一定的實用性的。

圖4 總節點個數與定位誤差的關系

圖5為先使用加權DV-Hop算法后再進行位置修正（加權-MinDV-Hop）與傳統算法的在錨節點比例分別為5%、10%、15%、20%、25%、30%時定位誤差比較?？梢钥闯龈倪M定位算法的定位精度比傳統的定位精度高，在錨節點比例為15%和25%時最為明顯。通過比較圖2、圖3可知：對平均每跳距離進行加權計算后再對未知節點的位置坐標進行修正，比單用加權算法和Min-Max修正算法的定位精度更高。

圖5 錨節點比例與定位誤差的關系

4 結語

介紹了一種無需測距定位算法，DV-Hop定位算法。并分析了該算法在定位過程中的缺點。針對傳統的DV-Hop定位算法在第二步和第三步存在的不足之處，提出了改進算法。每個未知節點的平均每跳距離不再僅僅由距離它最近的錨節點的平均每跳距離決定，而是把網絡中所有錨節點的平均每跳距離都考慮進來。根據錨節點與未知節點的距離，計算出錨節點平均跳距對應的權值，進而計算出所有未知節點加權后的平均每跳距離，最后對未知節點坐標用Min-Max算法修正。仿真結果表明，對傳統的定位方法僅用加權改進算法或者Min-Max改進算法，在一定的程度上提高了定位精度，但是先用加權算法對平均每跳距離進行改進再用Min-Max算法修正未知節點坐標，定位精度會更高，由于改進方法計算起來方便，不需要增加額外的硬件，所以具有很強的應用性。

參考文獻

［1］ 姚先連，胡貞，呂曉玲.無線傳感器網絡中卡爾曼濾波在移動目標跟蹤中的研究［J］.長春理工大學學報：自然科學版，2011，34（3）：88-92.

［2］ 李雪梅.基于DV-HOP算法的無線傳感器網絡節點定位技術研究［D］.太原：太原理工大學，2012.

［3］ 梁紅燕.無線傳感器網絡DV-HOP節點定位算法的研究［D］.沈陽：東北大學，2013.

［4］ 尚小航.基于DV-HOP的無線傳感器網絡定位算法研究［D］.長春：吉林大學，2012.

［5］ 李成岳.基于DV-Hop的無線傳感器網絡節點定位算法研究［D］.吉林大學，2011.

［6］ Abdelali Hadir，Khalid Zine-Dine，Mohamed Bakhouya，et al.An optimized DV-Hop location algorithm usingaveragehopweightedmeaninWSNs［C］.2014 5th Workshop on Codes，Cryptography and Communication Systems（WCCCS）.2014.

［7］ 許毅，陳立家，甘浪雄，等.無線傳感器網絡技術原理及應用［M］.北京：清華大學出版社，2015.

［8］ Qihong Tao，Linghua Zhang.Enhancement of DV-Hop by weighted hop distance［C］.2016 IEEE AdvancedInformationManagement，Communicates，Electronic and Automation Control Conference（IMCEC）.2016.

［9］ Songlin Liu，Chungang Liu，Wenbin Zhang，et al.Hybrid localization algorithm based on APIT and DV-HOP in WirelessSensor Networks［C］.2015 IEEE/CIC International Conference on Communications in China-Workshops（CIC/ICCC），2015.

［10］ 林金朝，李小玲，劉海波.無線傳感器網絡DV-Hop算法改進與性能［J］.重慶大學學報，2010，33（2）：127-132.

［11］ 姜曉榮.無線傳感器網絡DV-Hop定位算法［D］.太原：太原理工大學，2010.

［12］ Mohaddeseh Peyvandi，Ali A.Pouyan.An improved DV-Hop localization algorithm in wireless sensor networks［C］.2015SignalProcessing andIntelligent Systems Conference（SPIS），2015.

［13］ 邴曉瑛.無線傳感器中DV-Hop定位算法的改進研究［D］.江南大學，2016.

［14］ Wei Gao，Yue Sun，Wenjun Li，et al.An improved DV-Hop algorithm based on hop distance and estimated coordinates［C］.2017 29thChinese Control And Decision Conference（CCDC）.2017.