基于三維坐標修正的改進型3DDV-Hop定位算法 *

羅施章，張 晶,2,3,4，王健敏

(1.昆明理工大學信息工程與自動化學院，云南 昆明 650500；2.昆明理工大學云南省人工智能重點實驗室，云南 昆明 650500；3.云南梟潤科技服務有限公司，云南 昆明 650500；4.昆明理工大學云南省計算機技術應用重點實驗室，云南 昆明 650500；5.云南省農村科技服務中心，云南 昆明 650021)

1 引言

隨著人類社會智能信息化時代的到來，無線傳感器網絡[1]在各個領域中的應用價值越來越突出，尤其是在工農業、環境保護、軍事安全、社會安全等領域中的應用更為廣泛。例如在對特定湖泊區域水下數據的監測過程中，結合無線傳感器網絡隨機布置一定數量傳感器節點在特定水下三維空間區域中，并對各節點處溫度、濕度、壓強、污染物密度等數據進行實時采集，對所采集數據進行后臺實時分析遴選出數據異常節點，及時對三維空間區域中各異常節點位置處采取相應環境整治措施，以達到對生態環境進行保護的目的，而采取整治措施的前提是獲取異常節點位置，若需獲取各監測節點處坐標則需結合節點的定位算法[2]求解其坐標。

隨著應用場景空間維度的提升，為降低算法計算復雜度以及對未知節點定位成本，目前將無需測距的傳統3DDV-Hop (3D Distance Vector Hop)定位算法作為各應用場景中對節點定位的主流算法，而該算法由于對各節點間跳數、跳距計算不準確，從而影響了未知節點與各錨節點間距離計算，導致未知節點定位誤差較大；為降低跳數、跳距計算誤差，各類基于節點間跳數、跳距計算進行改進的定位算法被陸續提出。但是，這些改進定位算法對節點間跳數、跳距的計算方法有待優化，且未對所求得未知節點在三維空間中坐標位置進行修正以進一步降低未知節點定位誤差[3]。

為解決上述問題，本文提出一種基于三維坐標修正的改進型3DDV-Hop定位算法。該算法首先通過為各錨節點設定3種不同的通信半徑[4]進行數據信息廣播,各節點根據不同通信距離記錄最小跳數，從而降低各節點間最小跳數計算誤差；然后結合該最小跳數分別構建各錨節點間跳數權值Wij(其中，i和j分別為第i個錨節點和第j個錨節點，i≤i,j≤S×V，S為節點總數，V為錨節點比例)、各未知節點與各錨節點間跳數權值Wki(其中，k和i分別為第k個未知節點和第i個錨節點，i≤k≤N，N為未知節點總數)，根據各錨節點間跳數權值進行加權計算求得錨節點平均跳距值AVEHop;再根據該AVEHopi以及Wki加權計算出各未知節點AVEHopk值，通過該AVEHopk值以及未知節點與各錨節點間最小跳數MINHopki可計算得出未知節點與各錨節點間空間直線距離，并采用最大似然估計法求解得出各未知節點在三維空間中的估計坐標；最后對鄰居錨節點數大于或等于2(鄰居節點數決定了構建的空間正方體數量，當空間正方體數量大于或等于2時才可形成交叉區域)的未知節點依據各未知節點與各相鄰錨節點間距離構建正方體交叉區域[5]，并對未處于該交叉區域中的未知節點進行坐標修正，以進一步降低定位誤差。

2 傳統3DDV-Hop算法及改進算法

2.1 傳統3DDV-Hop定位算法

2.1.1 算法原理

隨著無線傳感器網絡的應用空間維度由二維平面拓展至三維空間，節點坐標計算復雜度及定位成本隨之增加，傳統DV-Hop算法需在原有基礎上改進為傳統3DDV-Hop定位算法，以適應空間維度提升的定位場景。傳統3DDV-Hop算法定位步驟可簡述如下：

首先由傳感器網絡中各節點向位于半徑為R的球體范圍內各相鄰節點廣播數據信息包(包含節點ID、節點跳數等信息)，直至各節點間最小跳數均記錄在路由向量信息表中(相鄰節點間最小跳數為1)；其次第i個錨節點可根據自身三維坐標(xi,yi,zi)以及與第j個節點間最小跳數MINHopij計算出自身平均跳距AVEHopi，如式(1)所示：

AVEHopi=

(1)

然后根據上述求得的AVEHopi和MINHopij可計算得知第k個未知節點與第i個錨節點間直線距離，如式(2)所示：

Dki=AVEHopi×MINHopki

(2)

2.1.2 問題描述

(1)如圖1所示，由于傳統3DDV-Hop定位算法在計算節點A1與A4、A1與A5間最小跳數MINHopA1A4和MINHopA1A5時，是由各相鄰節點間最小跳數累加而得，而各相鄰節點間最小跳數均以1計，故通過計算可知，節點A1與A4、A1與A5間MINHopA1A4和MINHopA1A5值分別為2和1，但各相鄰節點間實際直線距離差異較大，從而造成各節點間最小跳數計算誤差較大。

Figure 1 Schematic diagram of calculation error of minimum hop count圖1 最小跳數計算誤差示意圖

(2)如圖2所示，三維空間中a3與a1、a2、a4、a5間距離[6]相等，均為l，通過式(1)計算可知AVEHopa3為2l/3，結合該值與式(2)計算可知a3與a1、a2、a4、a5間直線距離Da3a1,Da3a2,Da3a4,Da3a5分別為4l/3,2l/3,2l/3,4l/3，從而造成通過傳統3DDV-Hop定位算法所得各節點直線距離與實際距離差異較大。

Figure 2 Schematic diagram of calculation error of average jump distance圖2 平均跳距計算誤差示意圖

2.2 各類改進定位算法

2.2.1 算法原理

針對傳統3DDV-Hop定位算法在計算未知節點坐標位置過程中存在的上述問題，文獻[7]提出一種基于加權的3DDV-Hop定位算法[7]，該算法通過構建跳數權值對錨節點平均跳距進行加權計算求解，從而降低未知節點定位誤差；文獻[8]提出一種基于跳數加權與跳距優化的3DDV-Hop定位算法[8]，該算法通過對相鄰節點間AVEHopij進行加權修正以及對AVEHopi結合最小均方誤差進行優化計算，以此降低未知節點的定位誤差。

2.2.2 問題分析

(1)傳統3DDV-Hop定位算法雖然可求得未知節點在三維空間中坐標位置且計算簡單，但是由于相鄰節點最小跳數以及各錨節點平均跳距計算誤差導致未知節點定位誤差較大，實用價值不大。

(2)基于加權的3DDV-Hop定位算法雖通過構建跳數權值對各錨節點平均跳距進行了優化處理以降低未知節點定位誤差，但是平均跳距計算過程中涉及各相鄰節點間最小跳數，而最小跳數計算并未進行任何修正，各節點間最小跳數是直接通過對相鄰節點間最小跳數進行累加所得，從而導致各錨節點平均跳距計算過程中所涉及的節點間最小跳數存在較大誤差，以至于后續的平均跳距計算以及未知節點坐標計算存在較大誤差。

(3)基于跳數加權與跳距優化的3DDV-Hop定位算法雖通過相鄰節點間接收信號強度指示RSSI(Received Signal Strength Indication)值構建的跳數權值[9]以及最小均方誤差降低了節點間最小跳數和各錨節點平均跳距的計算誤差，但是在計算各相鄰節點間最小跳數時只考慮通過外部優化方法對路由信息向量表中已記錄各節點間最小跳數進行修正計算，并未從錨節點自身通信距離出發對MINHopij進行精確記錄；且在AVEHopi計算過程中只針對AVEHopi進行優化計算并以此進行各未知節點與各錨節點間空間直線距離的計算，而并未同時結合未知節點平均跳距值進行優化計算，以進一步降低平均跳距計算誤差。

上述各類改進算法最后均通過最大似然估計法[10]計算得出各未知節點估計坐標，并將該估計坐標值作為各未知節點最終坐標值，并未結合任何修正方法對其進行進一步求精。

針對上述問題，本文提出一種基于三維坐標修正的改進型3DDV-Hop定位算法。

3 本文所提改進型3DDV-Hop定位算法

3.1 設定不同通信半徑記錄最小跳數

首先為無線傳感器網絡中各錨節點設置3類通信半徑，分別為R/3,2R/3,R；其次錨節點分別以3類通信半徑向鄰居節點廣播數據信息包，當鄰居節點處于2R/3通信半徑球體范圍內時，只需將相鄰節點間MINHopij記錄在路由信息向量表中即可，無需繼續轉發數據信息包；當鄰居節點處于2R/3與R之間的環形球體范圍內時，需將MINHopij記錄在路由信息向量表的同時結合泛洪法[11]繼續向自身鄰居節點轉發數據信息包。其中MINHopij具體記錄法則如式(3)所示：

(3)

其中,DIS為相鄰節點間空間直線距離，其值結合相鄰節點間RSSI計算得出。RSSI具體計算如式(4)所示：

(4)

其中,Pr(d)、Pr(d0)分別為與參考節點相距d、d0處節點的RSSI值，可直接測得;而d0為標準參考距離，通常取d0=1 m;1≤η≤3為路徑損耗指數;Xσ為高斯噪聲。

如圖3所示，當處于2R/3與R之間的環形球體范圍內的鄰居節點F接收到來自錨節點A的數據信息包時，將相鄰節點間MINHopFA值記錄在自身路由信息向量表中；并以同樣方式(三通信半徑)繼續向位于通信半徑范圍外的鄰居節點G轉發數據信息包，節點G分別將MINHopAF、MINHopFG記錄在路由信息向量表[12]中，并根據MINHopFG與三通信半徑相對大小關系判定其是否繼續轉發數據信息包。

Figure 3 Schematic diagram of calculating the minimum hop count of three communication radii圖3 三通信半徑最小跳數計算示意圖

各錨節點均根據上述通信方式進行泛洪廣播，直至所有節點間MINHopij記錄完畢。

3.2 加權計算平均跳距及未知節點坐標計算

通過上述三通信半徑計算方法可知所有錨節點間最小跳數MINHopij，結合各錨節點在三維空間已知坐標(xi,yi,zi)、(xj,yj,zj)，可計算出所有錨節點間平均跳距值AVEHopij，如式(5)所示：

AVEHopij=

(5)

與此同時構建所有錨節點間跳數權值Wij，根據該權值以及所有錨節點間AVEHopij通過加權計算得出所有錨節點AVEHopi，如式(6)所示：

AVEHopi=∑i≠jMINHopij×Wij

(6)

其中，

(7)

同理，通過第k個未知節點與所有錨節點間MINHopki構建權值Wki，如式(8)所示：

(8)

結合式(6)中AVEHopi以及式(8)中權值Wki，通過加權計算可求解出第k個未知節點平均跳距[13]AVEHopk，如式(9)所示：

AVEHopk=∑k≠iAVEHopi×Wki

(9)

(10)

對式(10)中各方程式間作差值運算，從而求解出未知節點估計坐標：X=(ATA)-1ATb，其中：

3.3 構建正方體交叉區域修正坐標

當未知節點鄰居節點數大于或等于2時，通過RSSI[14]計算出未知節點與其相鄰節點間距離，各鄰居節點分別以自身為中心，以該距離值的2倍長度為邊長構建空間正方體，若干正方體之間相互交錯形成正方體交叉區域；若第k個節點未處在該正方體交叉空間中，則需結合如下規則對其三維坐標進行修正，如圖4所示。

Figure 4 Schematic diagram of cube intersection area construction圖4 正方體交叉區域構建示意圖

設定圖4中，第i個錨節點標為(xi,yi,zi)，第k個節點(未知節點)與其距離為d，當未知節點未處于交叉區域中時，需對其坐標進行修正，具體修正規則如式(11)所示：

(11)

4 仿真實驗及數據分析

4.1 評價指標及仿真環境

為充分對比各類算法對未知節點定位精確度，實驗過程中將各類算法對所有未知節點(共N個)的平均定位誤差值(ErrEvg)作為評價算法優劣的標準。結合節點在三維空間中實際坐標(xk,yk,zk),1≤k≤N，ErrEvg具體計算方法如式(12)所示：

ErrEvg=

(12)

算法采用Matlab 2016a版仿真軟件，構建邊長為100 m的湖泊水下三維空間區域仿真場景，如圖5所示，設定節點總數(S)、錨節點比例(V)、節點通信半徑(R)變化范圍分別為300～1 000,15%～45%,30 m～100 m，各類實驗條件下未知節點ErrEvg均由定位算法循環運行100次取平均值所得。

Figure 5 Distribution diagram of nodes in underwater three-dimensional space圖5 水下三維空間節點分布圖

4.2 實驗結果對比分析

根據節點在三維空間的分布特點以及節點通信距離與空間范圍的相對關系，首先在初始條件(R=60 m,S=1000)下，統計并對比分析傳統3DDV-Hop定位算法(以下簡稱3DDV-Hop)、基于加權的3DDV-Hop定位算法(以下簡稱3DDV-Hop-WH)、基于跳數加權與跳距優化的3DDV-Hop定位算法(以下簡稱3DDV-Hop-HWHD)、基于三維坐標修正的改進型3DDV-Hop定位算法(以下簡稱3DDV-Hop-CDCR)共計4種算法的ErrEvg隨錨節點比例(V)變化的情況，如圖6所示。

Figure 6 Broken line statistical diagram of ErrEvgchanging with anchor node proportion V圖6 ErrEvg隨錨節點比例V變化折線統計圖

由圖6統計結果分析可知，上述4種算法的ErrEvg隨錨節點比例(V)的增加呈下降趨勢，本文所提3DDV-Hop-CDCR算法相較前3種算法該值下降[0.0066，0.2737](區間下限由前3種算法的ErrEvg最小值與3DDV-Hop-CDCR算法ErrEvg最大值相減所得，區間上限由前3種算法的ErrEvg最大值與3DDV-Hop-CDCR算法ErrEvg最小值相減所得，后續ErrEvg下降區間求解方法相同)。

其次在初始條件(R=60 m,V=25%)下，統計并對比分析4種算法ErrEvg隨節點總數(S)變化的情況，如圖7所示。

Figure 7 Broken line statistical diagram of ErrEvg changing with the total number of nodes S圖7 ErrEvg隨節點總數S變化折線統計圖

根據圖7統計結果分析可知，上述4種算法的ErrEvg隨著節點總數(S)的增加，無明顯變化趨勢，且3DDV-Hop-CDCR定位算法相較前3種定位算法，其ErrEvg下降[0.0596，0.2350]。

最后在初始條件(S=1000,V=25%)下，統計并對比分析4種算法ErrEvg隨節點通信半徑(R)變化的情況，如圖8所示。

Figure 8 Broken line statistical diagram of ErrEvg changing with node communication radius R圖8 ErrEvg隨節點通信半徑R變化折線統計圖

根據圖8實驗統計結果可知，4種定位算法的ErrEvg隨著節點通信半徑(R)的增加呈現明顯下降趨勢，且本文3DDV-Hop-CDCR定位算法相較前3種定位算法，其ErrEvg下降[0.0093，0.2919]。

4.3 計算復雜度對比分析

本文所提3DDV-Hop-CDCR定位算法所涉及的問題規模大小與節點總數相關，而算法仿真過程中基本語句迭代次數由未知節點數N決定，故可令頻度函數T(S)為：T(S)=(1-V)S，再將頻度函數T(S)中所有未知變量全部換成未知因子ε，即T(ε)=ε-ε2，當ε趨近于無窮大時，存在函數f(ε)使得：

其中c為常數，從而得出f(ε)為T(ε)的同量級函數，故算法計算復雜度為O(ε2)。

而前述3種算法計算過程中，基本語句迭代次數也是由未知節點總數N決定，且本文所提算法相較前3種算法所投入錨節點比例并未有所下降，故4種算法未知節點總數相同，算法復雜度也相同，均為O(ε2)。

4.4 節點通信及部署代價對比分析

3DDV-Hop算法、3DDV-Hop-WH算法和本文3DDV-Hop-CDCR算法在定位過程中只涉及通過各錨節點間相互通信獲取各錨節點間最小跳數，以計算各錨節點平均跳距，通信輪數為1。而3DDV-Hop-WH算法在定位過程需要各相鄰節點間相互通信獲取RSSI，以修正各相鄰節點間最小跳數，以及各錨節點間相互通信獲取節點間最小跳數，以求得各錨節點平均跳距，通信輪數為2，相較而言3DDV-Hop-WH算法節點通信代價較高。

由于4種算法所投入的錨節點比例相同，且錨節點數與所投放的GPS定位裝置數對應，故4種算法的節點部署代價相同。

5 結束語

本文通過設定3類節點通信半徑計算節點間最小跳數，以及通過加權運算降低各未知節點平均跳距，從而降低未知節點平均定位誤差，并結合未知節點與鄰居節點間直線距離構建正方體交叉區域，以修正未知節點坐標，進一步降低定位誤差。實驗結果表明,本文所提出的基于三維坐標修正的改進型3DDV-Hop定位算法，相較傳統3DDV-Hop定位算法和各類改進的3DDV-Hop定位算法，其ErrEvg下降[0.0066，0.2919]，顯著降低，算法計算復雜度、節點通信和部署代價均未增加。