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

叢珊，陳桂芬

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

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

1 DV-Hop定位算法

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

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

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

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

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

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

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

1.1 DV-Hop定位算法的缺點

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

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

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

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

2 改進算法

2.1 加權DV-Hop定位算法

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

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

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

2.2 Min-Max修正算法

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

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

如果未知節(jié)點的估計坐標在重疊區(qū)域內，那么就認為定位不存在誤差，不需要對位置進行修正，如果未知節(jié)點的估計坐標不在重疊區(qū)域內，那么需要對位置進行修正，假設未知節(jié)點原來計坐標為(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）錨節(jié)點以泛洪方式向網絡中廣播信息包，節(jié)點獲得與錨節(jié)點的最小跳數(shù)。

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

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

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

3 算法仿真

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

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

圖1 節(jié)點分布示意圖

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

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

圖2 錨節(jié)點比例與定位誤差的關系

圖3 錨節(jié)點比例與定位誤差的關系

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

圖4 總節(jié)點個數(shù)與定位誤差的關系

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

圖5 錨節(jié)點比例與定位誤差的關系

4 結語

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

參考文獻

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

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

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

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

［5］ 李成岳.基于DV-Hop的無線傳感器網絡節(jié)點定位算法研究［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.