一種基于誤差距離加權與跳段算法選擇的遺傳優化DV-Hop定位算法

程 超 錢志鴻 付彩欣 劉曉慧

?

一種基于誤差距離加權與跳段算法選擇的遺傳優化DV-Hop定位算法

程 超 錢志鴻*付彩欣 劉曉慧

(吉林大學通信工程學院 長春 130012)

針對DV-Hop (Distance Vector-Hop) 定位算法存在較大定位誤差的問題，該文提出了一種基于誤差距離加權與跳段算法選擇的遺傳優化DV-Hop定位算法，即WSGDV-Hop定位算法。改進算法用基于誤差與距離的權值處理錨節點的平均每跳距離；根據判斷的位置關系選擇適合的跳段距離計算方法；用改進的遺傳算法優化未知節點坐標。仿真結果表明，WSGDV-Hop定位算法的性能明顯優于DV-Hop定位算法，減小了節點定位誤差、提高了算法定位精度。

無線傳感器網絡；遺傳算法；歸一化加權；DV-Hop(Distance Vector-Hop) 定位算法；判斷選擇

1 引言

隨著無線通信技術的不斷發展與壯大，作為物聯網(Internet of Things, IoT)底層重要技術之一的無線傳感器網絡(Wireless Sensor Network, WSN)已經成為了研究熱點[1]。WSN可以使IoT在任意時間、地點獲取任何想要得到的監測信息。而在WSN中監測信息的采集節點的位置是至關重要的，沒有位置信息的監測信息毫無意義，只有已知位置的監測信息才有理論研究意義和實際應用價值，因此在WSN中能夠確定監測信息采集位置的定位技術成為了WSN研究的關鍵問題之一，也是目前國內外的研究重點。

根據實際計算傳感器節點間的距離或角度，把無線傳感器網絡定位算法分為基于距離(range- based)的和距離無關(range-free)的兩種定位算法。其中，基于距離定位算法是在定位過程中通過使用外界設備來計算節點間距離或角度，再利用計算得到的距離角度信息進行未知節點位置定位的一種定位算法，包括：基于RSSI(Received Signal Strength Indicator)的定位[2]，基于TOA(Time Of Arrival)的定位[3]，基于AOA(Angle Of Arrival)的定位[4]和基于TDOA(Time Difference Of Arrival)的定位[5]。距離無關定位算法是在定位過程中無需使用外界設備計算節點間距離或角度，只需要根據網絡拓撲關系和錨節點的位置就可以進行未知節點位置定位的一種定位算法，包括：APIT (Approximate Point-In- triangulation Test)算法、DV-Hop(Distance Vector- Hop)定位算法[6,7]、質心算法[8]以及Amorphous算法[9,10]等。基于距離定位算法需要使用外界設備才能對未知節點的位置進行定位，網絡能耗大、成本高，但是該算法的定位精度高；而距離無關定位算法無需使用外界設備就可以對未知節點的位置進行定位，網絡能耗小、成本低，但是該算法的定位精度低，雖然低但該低定位精度依然可以滿足實際應用，所以距離無關定位算法成為了WSN定位算法中的重點研究算法。

在WSN的眾多距離無關定位算法中，性能較優的DV-Hop定位算法由于具備了距離無關定位算法的全部優點而得到了國內外研究者的關注，但仍存在節點定位誤差大、算法定位精度低的缺點。而文獻[15]先利用DV-Hop定位算法計算出未知節點的坐標，然后利用一個能夠判斷節點之間關系的優化模型來刪除定位誤差較大的坐標，進而提高改進算法的定位精度；文獻[16]中未知節點的平均每跳距離值是通過平均網絡中所有錨節點的平均每跳距離值而得到的，使用此策略提高了DV-Hop定位算法的定位精度；文獻[17]中錨節點使用兩種通信半徑廣播數據分組來計算自己與未知節點的最小跳數與距離，在經典DV-Hop定位算法的基礎上降低了節點的定位誤差；文獻[18]將網絡中的未知節點模擬成錨節點來進行DV-Hop定位，該方法雖然增加了累積誤差但相比于定位誤差的增加定位精度的提高更明顯。以提高算法的定位精度為目的，出現了以上等參考文獻對經典DV-Hop定位算法的改進，但仍然存在很多不足。本文將從經典DV-Hop定位算法存在較大定位誤差的問題出發，結合多種方法對DV-Hop定位算法進行改進并仿真證明降低了節點的定位誤差、提高了算法的定位精度。

2 DV-Hop定位算法

首先，確定最小跳數。所有錨節點向網絡中廣播帶有跳數字段和錨節點位置信息的數據分組，通過該過程網絡中每個傳感器節點都知道了自己到每個錨節點之間的最小跳數和每個錨節點的位置信息。

其次，確定跳段距離。網絡中錨節點的平均每跳距離計算公式為

然后，所有錨節點向網絡中廣播自己的平均每跳距離信息，未知節點就把最先接收到的那個錨節點的平均每跳距離當做自己的平均每跳距離。未知節點用自己到某一個錨節點的最小跳數乘以自己的平均每跳距離作為自己到該錨節點的跳段距離。

最后，確定未知節點坐標。根據未知節點與每個錨節點的跳段距離以及錨節點的位置信息，利用極大似然估計法或三邊測量法計算未知節點的坐標。

3 WSGDV-Hop定位算法

隨著WSN定位算法研究的不斷發展[19,20]，算法簡單且網絡能耗小、成本低的DV-Hop定位算法更是學者們的研究熱點[21]。本文從經典DV-Hop定位算法存在誤差的幾個方面出發進行算法改進，提出了一種基于誤差距離加權與跳段算法選擇的遺傳優化DV-Hop定位算法(WSGDV-Hop)。

3.1 未知節點平均每跳距離的確定

在經典DV-Hop定位算法中未知節點將最先接收到的錨節點的平均每跳距離作為自己的平均每跳距離，然而該方法存在一定的問題，如：一旦唯一接收的錨節點平均每跳距離存在很大的誤差，就會使未知節點的平均每跳距離存在很大的誤差，則之后一切基于未知節點平均每跳距離的計算都是誤差的不斷累積，導致定位誤差越來越大；而未知節點的平均每跳距離是用于計算與周邊網絡內節點的跳段距離的，因此只有一個距離未知節點最近的錨節點的平均每跳距離無法代表未知節點周邊網絡的情況，且距離未知節點越近的錨節點越能代表未知節點周邊網絡的情況。綜上，考慮以上兩點因素后以減小定位誤差為目的，在改進算法中未知節點需要考慮多個錨節點的平均每跳距離，且以錨節點平均每跳距離誤差越小距離未知節點越近越能代表未知節點平均每跳距離為原則。WSGDV-Hop改進算法中未知節點的平均每跳距離具體計算過程如下：

首先，所有錨節點向網絡中廣播帶有跳數字段和錨節點坐標的數據分組，廣播結束后網絡中任意兩節點間的最小跳數以及錨節點的坐標已知，因此可以計算出錨節點的平均每跳距離：

得知了網絡中所有錨節點的平均每跳距離后，開始計算每個錨節點的平均每跳距離誤差。首先計算錨節點與之間的跳段距離即計算距離：

然后計算錨節點與之間的實際距離：

最后計算錨節點的平均每跳距離誤差：

錨節點以廣播的形式將計算得到的自身平均每跳距離和平均每跳距離誤差向網絡進行廣播。未知節點以錨節點距離自己越近平均每跳距離誤差越小越重要為原則，對接收到的個錨節點的平均每跳距離誤差和距離未知節點的跳數距離進行處理計算每個錨節點的權值：

由于未知節點以距離自己越近越重要為原則，所以未知節點接收距離自己最近的個錨節點的信息，其中的取值不宜過大否則接收的過多網絡能耗會增加，其次距離未知節點遠的錨節點就不能很好地反映未知節點周圍的網絡了，所以根據仿真試驗可以確定的最佳取值為3。

最后，未知節點對接收到的最近的3個錨節點的平均每跳距離做基于權值w的歸一化加權處理來計算自己的平均每跳距離：

3.2 未知節點與錨節點間跳段距離的確定

在經典DV-Hop定位算法中未知節點用自己的平均每跳距離乘以距離錨節點的最小跳數來計算彼此間的跳段距離，該方法用跳段距離估計彼此間的直線距離本身就是一個估計值存在誤差，然而除此估計誤差外該方法還有一定的問題：在計算未知節點與錨節點間跳段距離時應該考慮該錨節點的信息，且網絡中有距離未知節點越近的錨節點越能很好地反映它周邊網絡的原則，所以在計算未知節點與距離自己較近的錨節點間跳段距離時可以根據經典算法計算，因為此時的未知節點平均每跳距離中既涵有該錨節點的信息又有距離未知節點最近的錨節點的信息；當計算與距離自己較遠的錨節點間跳段距離時，由于經典算法中未知節點的平均每跳距離中不涵有該錨節點的信息只有距離未知節點最近的錨節點的信息而不適用，應該考慮該錨節點的信息。綜上，在改進算法中可以把未知節點周邊的錨節點簡單的分為距離自己最近的錨節點和非最近的錨節點，然后根據節點位置關系的不同選擇不同的跳段距離計算方法來確定彼此間的跳段距離，計算中都要既考慮最近的錨節點的信息又考慮該錨節點的信息。WSGDV-Hop改進算法中未知節點與錨節點間跳段距離的具體計算過程如下：

首先，在圖1中，判斷節點間的位置關系將需要定位的未知節點周邊的錨節點分為距離自己最近的錨節點和非最近的錨節點，其中最近的錨節點只有一個，其它均為非最近的錨節點。

圖1 WSGDV-Hop跳段距離計算中錨節點位置判斷

其次，針對距離未知節點最近的錨節點，二者間的跳段距離計算公式為

最后，針對距離未知節點非最近的錨節點，二者間的跳段距離計算公式為

3.3 未知節點坐標的確定

在經典DV-Hop定位算法中，得知未知節點與錨節點間的跳段距離后，采用三邊測量法或極大似然估計法計算未知節點坐標，然而使用以上兩種坐標計算方法計算得到的未知節點坐標都存在無可避免的誤差。因此，在改進算法中引入優化的概念，挑選一個適合的優化模型對以上兩種方法計算得出的帶有誤差的未知節點坐標進行優化，減小未知節點的定位誤差。WSGDV-Hop改進算法中未知節點坐標的確定過程如下：首先，根據上文計算得出的未知節點與網絡中所有錨節點間的跳段距離，采用極大似然估計法計算未知節點坐標(,)。然后，用改進的遺傳算法對未知節點坐標(,)進行優化處理，最后得出未知節點坐標的最優解。

3.3.1 WSGDV-Hop定位算法中遺傳算法的改進

為了有效地把遺傳算法結合到WSGDV-Hop定位算法中，在經典遺傳算法基礎上做了些許改進以適應改進算法并更好地優化未知節點坐標，改進遺傳算法基本要素及關鍵參數設置如下：

(1)染色體與初始種群的確定： 把所有未知節點坐標組成的問題空間內的每一個未知節點坐標(,)轉換成遺傳算法所能處理的染色體，未知節點坐標(,)中的,轉化成染色體中的1,2，具體為

(2)適應度函數的確定： 在WSGDV-Hop定位算法中問題空間的目標函數即未知節點坐標定位誤差為

改進遺傳算法把問題空間的目標函數作為自己的適應度函數，其值越小，染色體適應力越強，被遺傳下去的可能性越高，而不是適應度函數值越大適應能力越強，適應度函數為

(3)交叉算子： 改進遺傳算法的交叉算子為

(4)變異算子： 針對遺傳算法中變異算子的設計，改進遺傳算法與經典遺傳算法一致，其計算式為

(5)選擇算子： 改進遺傳算法中選擇操作作用于種群中的每一個染色體即每一個號位的染色體，比較染色體和經過交叉、變異后生成的染色體的適應度函數值大小，并選擇適應度函數值大的染色體保留到該染色體號位上，完成一代遺傳操作過程，而不是在種群中橫向比較并選擇若干適應度函數值大的染色體遺傳下去，改進遺傳算法一定要保留每一個號位上的染色體。

4 算法仿真結果

4.1 仿真場景

使用MATLAB仿真比較經典DV-Hop定位算法與WSGDV-Hop定位算法的性能指標，表1為算法對比仿真參數。

表1仿真參數

參數名稱取值 網絡區域(m2)100100 節點總數100 錨節點數量5, 10, 15, 20, 25, 30, 35, 40 通信半徑(m)25, 30, 35, 40, 45 仿真次數總計300 初始種群P0X 交叉概率Pc0.9 變異概率Pm0.07 終止代數T100

4.2 性能評價指標

在WSN中衡量一個定位算法性能好壞的基本指標主要包括：算法的定位精度和節點的平均定位誤差，具體計算公式如下：

算法的定位精度：

節點的平均定位誤差：

4.3 仿真與分析

圖2為WSN網絡的拓撲結構圖，圖中100個傳感器節點隨機地部署在100 m×100 m的監測區域內，其中的70個黑色圓點是網絡中的未知節點，30個五角星是網絡中的錨節點。在仿真實驗中網絡中傳感器節點的總數始終為100，而錨節點與未知節點的個數是可以隨著實驗而確定的。

圖2 網絡拓撲結構圖　　　　　　　圖3 通信半徑R=30 m時WSGDV-Hop與DV-Hop定位算法對比

圖4 通信半徑R=35 m時WSGDV-Hop與DV-Hop定位算法對比　?????　圖5 通信半徑R=40 m時WSGDV-Hop FDV-Hop與DV-Hop算法的定位精度對比

5 結束語

針對DV-Hop定位算法存在較大定位誤差的問題，以減小DV-Hop定位算法的節點定位誤差，提高算法的定位精度為目的，本文從經典DV-Hop定位算法存在誤差的幾個方面出發進行算法改進，提出了一種基于誤差距離加權與跳段算法選擇的遺傳優化DV-Hop定位算法，即WSGDV-Hop定位算法。改進算法包括3個改進點：用基于誤差與距離的權值處理錨節點的平均每跳距離來確定未知節點的平均每跳距離；根據判斷的位置關系選擇適合的跳段距離計算方法來確定未知節點與錨節點間的跳段距離；用改進的遺傳算法優化未知節點坐標來確定未知節點坐標的最優解。仿真結果表明，WSGDV-Hop定位算法的性能明顯優于DV-Hop定位算法，達到了減小節點定位誤差、提高算法定位精度的目的。

[1] 錢志鴻, 王義君. 面向物聯網的無線傳感器網絡綜述[J]. 電子與信息學報, 2013, 35(1): 215-227.

Qian Zhi-hong and Wang Yi-jun. Internet of things-oriented wireless sensor networks review[J].&, 2013, 35(1): 215-227.

[2] Cheng X, Thaeler A, Xue G,.. TPS:A time-based positioning scheme for outdoor wireless sensor networks[C]. Proceedings-IEEE INFOCOM, Hong Kong, 2004: 2685-2696.

[3] Niculescu D and Nath B. Ad hoc positioning system(APS) using AOA[C]. IEEE INFOCOM 2003: The Conference on Computer Communications, San Francisco, 2003: 1734-1743.

[4] Naeimi Soroush, Chow Chee-onn, and Ishii Hiroshi. Directional multi-hop clustering routing protocol for wireless sensor networks[J]., 2013, 14(2): 123-134.

[5] Girod L and Estrin D. Robust range estimation using acoustic and multimodal sensing[C]. IEEE International Conference on Intelligent Robots and Systems, Hawaii, 2001: 1312-1320.

[6] Radhika Nagpal, Howard Shrobe, and Jonathan Bachrach. Organizing a global coordinate system from local information on an Ad hoc sensor network[C]. 2nd International Workshop on Information Processing in Sensor Networks (IPSN '03), Palo Alto, 2003: 1-16.

[7] Niculescu D and Nath B. DV based positioning in Ad hoc networks[J]., 2003, 22(1~4): 267-280.

[8] Bahl Paramvir and Padmanabhan Venkata N. RADAR: an in-building RF-based user location and tracking system[C]. Proceedings-IEEE International Conference on Computer Communications, Tel Aviv, 2000: 775-784.

[9] Bulusu N, Heidemann J, and Estrin D. GPS-less low cost outdoor localization for very small devices[J]., 2000, 7(5): 28-34.

[10] Nagpal R. Organizing a global coordinate system from local information on an amorphous computer[R]. Artificial Intelligence Memo 1666, MIT Artificial Intelligence Laboratory,Massachusetts, 1999.

[11] Kumar Shrawan and Lobiyal D K. An advanced DV-Hop localization algorithm for wireless sensor networks[J]., 2013, 71(2): 1365-1385.

[12] Hu Yu and Li Xue-mei. An improvement of DV-Hop localization algorithm for wireless sensor networks[J]., 2013, 53(1): 13-18.

[13] Safa Haidar. A novel localization algorithm for large scale wireless sensor networks[J]., 2014, 45(7): 32-46.

[14] Jia Song-hao and Yang Cai. Sub-regional DV-Hop localization algorithm for dynamic anchor nodes[J]., 2013, 51(22): 162-170.

[15] 劉影, 錢志鴻, 王雪. 基于到達時間差的無線傳感器網絡質心定位算法[J]. 吉林大學學報(工學版), 2010, 40(1): 245-249.

Liu Ying, Qian Zhi-hong, and Wang Xue. Wireless sensor network centroid localization algorithm based on time difference of arrival[J].(),2010, 40(1): 245-249.

[16] Chen Hongyang, Karo Sezaki, Deng Ping,. An improved DV-hop localization algorithm for wireless sensor networks[C]. IEEE Conference on Industrial Electronics and Applications (ICIEA2008), Singapore, 2008: 1557-1561.

[17] 李娟, 劉禹, 錢志鴻. 基于雙通信半徑的傳感器網絡DV-Hop定位算法[J]. 吉林大學學報(工學版), 2013, 44(2): 502-507.

Li Juan, Liu Yu, and Qian Zhi-hong. Improved DV-Hop localization algorithm based on two communication ranges for wireless sensor network[J].(),2013, 44(2): 502-507.

[18] Liu Peng-xi, Zhang Xin-ming, Tian Shuang,. A novel virtual anchor node-based localization algorithm for wireless sensor networks[C]. Sixth International Conference on Networking (ICN’07), Martinique, 2007: 9.

[19] Rashid Haroon and Turuk Ashok Kumar. Localization of wireless sensor networks using a single anchor node[J]., 2013, 72(2): 975-986.

[20] Lazaro A, Girbau D, and Moravek P. A study on localization in wireless sensor networks using frequency diversity for mitigating multipath effects[J]., 2013, 19(3): 82-87.

[21] 嵇瑋瑋, 劉中. DV-Hop定位算法在隨機傳感器網絡中的應用研究[J]. 電子與信息學報, 2008, 30(4): 970-974.

Ji Wei-wei and Liu Zhong. Study on the application of DV-hop localization algorithms to random sensor networks[J].&, 2008, 30(4): 970-974.

[22] 劉影. 無線傳感器網絡節點定位算法研究[D]. [博士論文], 吉林大學, 2011.

Liu Ying. Study on node localization algorithms in wireless sensor network[D]. [Ph.D. dissertation], Jilin University, 2011.

Genetic Optimization DV-Hop Localization Algorithm Based on Error Distance Weighted and Hop Algorithm Selection

Cheng Chao Qian Zhi-hong Fu Cai-xin Liu Xiao-hui

(,,130012,)

For the problem of larger location error in Distance Vector-Hop (DV-Hop) localization algorithm, a genetic optimization DV-Hop localization algorithm based on error distance weighted and hop algorithm selection is proposed, namely WSGDV-Hop localization algorithm. The average every hop distance of anchor nodes is weighted by the error and the distance, the hop distance calculation method between unknown nodes to anchor nodes is selected by position judgment, and the calculated unknown nodes coordinates are optimized by improved genetic algorithm. The simulation results show that WSGDV-Hop localization algorithm achieves better performance than DV-Hop localization algorithm, the node location error is reduced, and the location accuracy is increased.

Wireless Sensor Network (WSN); Genetic algorithm; Normalized weighted; Distance Vector-Hop (DV-Hop) localization algorithm; Judgment selection

TP393

A

1009-5896(2015)10-2418-06

10.11999/JEIT141205

2014-09-15；改回日期：2015-06-24；

2015-07-17

錢志鴻 dr.qzh@163.com

國家自然科學基金(61401175, 61371092)

The National Natural Science Foundation of China (61401175, 61371092)

程 超： 男，1984年生，博士生，研究方向為短距離無線通信路由及定位技術.

錢志鴻： 男，1957年生，教授，博士生導師，研究方向為無線網絡通信理論及技術.

付彩欣： 女，1988年生，碩士生，研究方向為無線傳感器定位技術.