一種適用于礦下人員定位的改進DV-Hop算法

張 琪，周勝梅，黃廷磊

（桂林電子科技大學，廣西 桂林541004）

隨著網絡技術的飛速發展，通信技術及無線定位技術也迅速發展起來。伴隨信息時代的到來，無線定位技術被廣泛應用于人員定位、救援等領域。我國礦難頻繁發生，這為國家和人民帶來了巨大的損失，所以礦下救援成為國家和煤礦企業非常重視的一個問題。礦下救援主要是對礦下人員的救援，其過程主要是確定礦下人員的準確位置。無線定位技術的發展為礦下救援帶來了方便，它能大大加快救援速度。現有的定位技術在實際應用中還有待研究，為了進一步改善其技術，定位算法的選擇至關重要。現有的定位算法有基于距離的算法（RSSI、TOA/TDOA和 AOA）和非基于距離的算法（質心、DV-Hop、APIT、Amorphous、凸規劃）。

DV-Hop節點定位算法由于對信標節點比例要求較少，定位精度較高，從而可大大降低網絡的布置成本。以往對DV-Hop算法的改進有：結合ZigBee技術來組建無線通信網絡；與加權質心相結合；與RSSI算法結合等。文本在分析DV-Hop算法的誤差成因后，在保留其算法簡單、不依賴于測距誤差優點的基礎上對其進行了改進。本文根據礦上地理位置進行劃分范圍，以縮小查找未知節點的單位來提高定位精度。

1 DV-Hop定位算法

1.1 DV-Hop算法的基本思想

DV-Hop算法由Niculescu等人提出，其基本思想是將未知節點和錨節點之間的距離用兩者之間的跳數和最近錨節點的平均跳距的乘積表示,當未知節點獲得與3個或更多錨節點的距離時進行三邊測量定位。其具體過程分為以下三步：

(1)通過節點之間的信息交換，使網絡中的每個未知節點獲取到信標節點的最小跳數。

(2)在已知信標節點的位置和它們到未知節點的最小跳數后，利用式（1）計算出網絡中平均每跳的距離，然后計算未知節點到每個信標節點的跳段距離。

其中，(xi，yi)、(xj，yj)為信標節點 i、j的坐標，hj為信標節點 i與 j(i≠j)之間的跳段數。

(3)未知節點在獲得3個或3個以上到信標節點的跳段距離時，利用三邊測量公式法(如式(2)所示)或極大似然估計值法計算出未知節點的坐標。

1.2 DV-Hop算法的舉例基本思想

如圖 1所示，如果 A、B、C為信標節點,第(1)步泛洪后可得到跳數，根據它們的坐標和跳數計算出相互間的距離，進一步計算出平均每跳的距離：A為(20+40)/(3+5)=7.5；B 為(20+30)/(3+3)=8.33；C 為(30+40)/(3+5)=8.75。它們向其鄰居節點發送該平均距離，最后未知節點P得到的平均距離是最小跳數對應的信標節點B的平均每跳距離，即8.33，則 P到各個節點的距離為：P到A 為 8.33×2=16.66；P到 B 為 8.33×1=8.33；P到 C 為8.33×3=24.99，然后P根據這些距離和信標節點的坐標通過三邊測量法來計算自身坐標[1]。

1.3 現有改進的DV-Hop算法

[2]中，王新生等人提出了使用多個錨節點估算的平均跳距并且采用加權平均跳距代替傳統算法中的平均跳距的改進算法。參考文獻[3]中，沈明玉等提出了一種基于平均跳距和估計距離的改進的DV-Hop算法。該算法考慮了未知節點到參考節點的路徑與參考節點間的路徑可能存在重合或部分重合這一特性,對平均跳距進行修改,并利用誤差對距離進行修正。參考文獻[4]～[5]中，周小波、呂振等提出了基于RSSI的改進型DV-Hop算法。

2 改進DV-Hop算法

對提高定位精度的一個有效方法就是縮小查找范圍，從而減小定位誤差。以往的算法應用于整個區域，而本文是將所有的節點進行分類，將查找的區域分成多塊，再在未知節點所在的那塊區域應用DV-Hop算法來確定未知節點的位置。具體步驟如下：

(1)將礦下整個區域看成是一個長方形，那么未知節點就在這個長方形范圍內。把信標節點均勻分布在這個長方形區域內，使其整個區域都能被信號覆蓋(此區域內的每個節點至少能接收到1個信標節點廣播的信號)。

(2)導致DV-Hop算法定位精度不高的一個主要原因就是對平均跳距的計算存在很大的誤差，本文利用RSSI測距技術來計算平均跳距。

未知節點收集鄰節點信息，選出RSSI最小值并確定此值所屬的信標節點。如果這個信標節點在邊界上，則另外選出與這個信標節點最相鄰的3個信標節點構成一個新的區域；如果這個信標節點在其內部，則選出與這個信標節點最相鄰的4個信標節點構成一個新的四邊形區域。

(3)以9個信標節點為例，位置分別在長方形的頂點、中心和四邊的中點處,如圖2所示。如果測出RSSI最小值信標節點是 1，則選擇 1、2、8、9 或 1、7、8、9 四個信標節點構成四邊形區域(一般礦下是非常窄的通道，選 1、7、8、9 比較合理)；如果是 2，則選取 1、3、9 三個信標節點構成三角形區域；如果是 9，則選取 2、4、6、8這樣的信標節點構成四邊形區域。

(4)對已知坐標的節點進行歸類。歸類方法：判定已知節點是否在新構成的多邊形區域內，若在，則保留這個節點作為新的信標節點；否則放棄。如圖2所示，可以把已知節點歸類到A、B、C、D四個區域中。

(5)在未知節點所在的區域中，把已知信息的未知節點當做信標節點，采用基本DV-Hop算法來確定未知節點的位置。

3 實驗及仿真結果

為了驗證本文算法的可行性，使用Matlab7.0作為仿真工具進行仿真，并對仿真結果進行分析。仿真環境是在100 m×100 m的正方形范圍內[6]，隨機產生 191個未知傳感器網絡節點和9個確定的信標節點，節點的通信距離為15 m。仿真結果數據取自20次仿真的平均值。初始節點分布圖如圖3所示。

縮小范圍后，節點分布圖如圖4所示。

節點分類后，保留4個固定的信標節點，其余54個未知節點隨機分布。其中，也可將在其范圍內的已知節點當做新的信標節點，這樣可大大提高對未知節點的定位精度。

當把隨機給出的未知節點分類后，得出54個未知節點，在其范圍內隨機定義5個已知的鄰節點和4個固定的信標節點作為新的信標節點。圖5所示為在縮小的范圍內當有9個信標節點、54個未知節點時，每個未知節點的誤差。

圖6是在通信距離為50 m時的平均定位誤差圖，從圖中可以看出隨著信標節點的增加，未知節點的定位誤差會相對減少。與原始的DV-Hop算法相比，改進后的算法定位誤差減少了近20%。改進后將4個固定節點當做是信標節點，然后隨著隨機增加信標節點來確定定位誤差。以信標節點占全部節點的比例作為圖中的橫坐標，以未知節點的平均誤差作為縱坐標。

介于礦下的特殊環境，本文介紹了一種基于DVHop的改進后的節點定位算法，在保留傳統DV-Hop算法計算簡單、通信開銷小的優點的基礎上，用縮小定位范圍的方法來提高定位精度。本文先對未知節點進行模糊定位，確定未知節點在哪塊區域內，再把已知坐標的節點當成信標節點進行分類，最后在縮小定位范圍內使用DV-Hop算法對未知節點進行定位。實驗結果證明，此方法大大提高了定位精度，很適合于煤礦快速查找人員所在的位置。

參考文獻

[1]倪海燕，應祥岳，簡家文，等.無線傳感器網絡的自身定位算法研究[J].寧波大學學報，2009，22(1)：7-11.

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

[3]沈明玉，張寅.基于改進的平均跳距和估計距離的DVHop 定位算法[J].計算機應用研究，2011，28(2)：648-650.

[4]周小波，喬鋼柱，曾建潮.無線傳感器網絡中基于RSSI的加權DV-HOP定位方法[J].計算機工程與應用，2011，18(4)：93-96.

[5]呂振，李亞杰，孫延飛，等.基于 DV-Hop的修正和改進定位算法[J].傳感器與微系統，2008，29(8)：31-33.

[6]楊小瑩，張萬禮，房愛東.一種改進的 DV-Hop定位算法[J].宿州學院學報，2011，18(4)：23-25.