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

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

1 引言

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

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

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

2 傳統(tǒng)3DDV-Hop算法及改進算法

2.1 傳統(tǒng)3DDV-Hop定位算法

2.1.1 算法原理

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

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

AVEHopi=

(1)

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

Dki=AVEHopi×MINHopki

(2)

2.1.2 問題描述

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

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

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

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

2.2 各類改進定位算法

2.2.1 算法原理

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

2.2.2 問題分析

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

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

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

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

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

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

3.1 設(shè)定不同通信半徑記錄最小跳數(shù)

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

(3)

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

(4)

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

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

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

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

3.2 加權(quán)計算平均跳距及未知節(jié)點坐標計算

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

AVEHopij=

(5)

與此同時構(gòu)建所有錨節(jié)點間跳數(shù)權(quán)值Wij，根據(jù)該權(quán)值以及所有錨節(jié)點間AVEHopij通過加權(quán)計算得出所有錨節(jié)點AVEHopi，如式(6)所示：

AVEHopi=∑i≠jMINHopij×Wij

(6)

其中，

(7)

同理，通過第k個未知節(jié)點與所有錨節(jié)點間MINHopki構(gòu)建權(quán)值Wki，如式(8)所示：

(8)

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

AVEHopk=∑k≠iAVEHopi×Wki

(9)

(10)

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

3.3 構(gòu)建正方體交叉區(qū)域修正坐標

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

Figure 4 Schematic diagram of cube intersection area construction圖4 正方體交叉區(qū)域構(gòu)建示意圖

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

(11)

4 仿真實驗及數(shù)據(jù)分析

4.1 評價指標及仿真環(huán)境

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

ErrEvg=

(12)

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

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

4.2 實驗結(jié)果對比分析

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

Figure 6 Broken line statistical diagram of ErrEvgchanging with anchor node proportion V圖6 ErrEvg隨錨節(jié)點比例V變化折線統(tǒng)計圖

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

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

Figure 7 Broken line statistical diagram of ErrEvg changing with the total number of nodes S圖7 ErrEvg隨節(jié)點總數(shù)S變化折線統(tǒng)計圖

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

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

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

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

4.3 計算復(fù)雜度對比分析

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

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

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

4.4 節(jié)點通信及部署代價對比分析

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

由于4種算法所投入的錨節(jié)點比例相同，且錨節(jié)點數(shù)與所投放的GPS定位裝置數(shù)對應(yīng)，故4種算法的節(jié)點部署代價相同。

5 結(jié)束語

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