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

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

1 引言

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

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

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

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

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

2.1.1 算法原理

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

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

AVEHopi=

(1)

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

Dki=AVEHopi×MINHopki

(2)

2.1.2 問(wèn)題描述

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

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

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

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

2.2 各類(lèi)改進(jìn)定位算法

2.2.1 算法原理

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

2.2.2 問(wèn)題分析

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

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

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

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

針對(duì)上述問(wèn)題，本文提出一種基于三維坐標(biāo)修正的改進(jìn)型3DDV-Hop定位算法。

3 本文所提改進(jìn)型3DDV-Hop定位算法

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

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

(3)

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

(4)

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

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

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

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

3.2 加權(quán)計(jì)算平均跳距及未知節(jié)點(diǎn)坐標(biāo)計(jì)算

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

AVEHopij=

(5)

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

AVEHopi=∑i≠jMINHopij×Wij

(6)

其中，

(7)

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

(8)

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

AVEHopk=∑k≠iAVEHopi×Wki

(9)

(10)

對(duì)式(10)中各方程式間作差值運(yùn)算，從而求解出未知節(jié)點(diǎn)估計(jì)坐標(biāo)：X=(ATA)-1ATb，其中：

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

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

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

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

(11)

4 仿真實(shí)驗(yàn)及數(shù)據(jù)分析

4.1 評(píng)價(jià)指標(biāo)及仿真環(huán)境

為充分對(duì)比各類(lèi)算法對(duì)未知節(jié)點(diǎn)定位精確度，實(shí)驗(yàn)過(guò)程中將各類(lèi)算法對(duì)所有未知節(jié)點(diǎn)(共N個(gè))的平均定位誤差值(ErrEvg)作為評(píng)價(jià)算法優(yōu)劣的標(biāo)準(zhǔn)。結(jié)合節(jié)點(diǎn)在三維空間中實(shí)際坐標(biāo)(xk,yk,zk),1≤k≤N，ErrEvg具體計(jì)算方法如式(12)所示：

ErrEvg=

(12)

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

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

4.2 實(shí)驗(yàn)結(jié)果對(duì)比分析

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

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

由圖6統(tǒng)計(jì)結(jié)果分析可知，上述4種算法的ErrEvg隨錨節(jié)點(diǎn)比例(V)的增加呈下降趨勢(shì)，本文所提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)計(jì)并對(duì)比分析4種算法ErrEvg隨節(jié)點(diǎn)總數(shù)(S)變化的情況，如圖7所示。

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

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

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

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

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

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

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

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

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

4.4 節(jié)點(diǎn)通信及部署代價(jià)對(duì)比分析

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

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

5 結(jié)束語(yǔ)

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