張 晶，李 煜

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

1 引言

無(wú)線傳感器網(wǎng)絡(luò)WSNs(Wireless Sensor Networks)是由許多具有感知和通信功能的傳感器節(jié)點(diǎn)部署在某個(gè)區(qū)域中組成的感知網(wǎng)絡(luò)[1]，隨著科學(xué)技術(shù)的發(fā)展和人民生活水平的日益提高，傳感器的身影已經(jīng)隨處可見(jiàn)。比如，畜牧業(yè)中羊群的檢測(cè)與跟蹤，森林火災(zāi)的檢測(cè)，甚至戰(zhàn)爭(zhēng)中敵軍的行動(dòng)檢測(cè)等等。傳感器網(wǎng)絡(luò)感知的信息很重要，可是在更多時(shí)候，人們更需要信息的發(fā)生位置[2]。為此，國(guó)內(nèi)外的一批學(xué)者對(duì)無(wú)線傳感器網(wǎng)絡(luò)的定位算法進(jìn)行了深入研究。由于實(shí)際部署的地點(diǎn)往往是三維空間而少有二維平面，因此本文主要研究傳感器網(wǎng)絡(luò)的三維定位問(wèn)題。

目前根據(jù)是否需要實(shí)際測(cè)量節(jié)點(diǎn)之間的距離，無(wú)線傳感器網(wǎng)絡(luò)的定位算法分有2種[3]：一種是需要給傳感器附加額外裝置來(lái)獲取節(jié)點(diǎn)之間的間距(稱為測(cè)距算法)。這種算法更精準(zhǔn)，但是由于需要添加額外的硬件設(shè)備也使得這種算法的部署對(duì)節(jié)點(diǎn)成本的要求較高[4]，不適合大型區(qū)域的監(jiān)測(cè)。另一種是不需要添加任何其他硬件設(shè)備對(duì)節(jié)點(diǎn)間間距進(jìn)行測(cè)量，只需要依靠網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)即可完成定位的非測(cè)距算法。這種算法定位精度低，但由于其相對(duì)測(cè)距算法而言節(jié)點(diǎn)造價(jià)低，適合于大型無(wú)線傳感器網(wǎng)絡(luò)的監(jiān)測(cè)，成為近些年研究的熱點(diǎn)。本文要探討的就是非測(cè)距算法中的典型算法——DV-Hop三維定位算法。

DV-Hop三維定位算法可以從3個(gè)方面進(jìn)行優(yōu)化：跳數(shù)優(yōu)化、平均跳距優(yōu)化以及對(duì)未知節(jié)點(diǎn)的估計(jì)。文獻(xiàn)[5]提出新的平均跳距計(jì)算方法，對(duì)定位精度有一定優(yōu)化，但是計(jì)算時(shí)采用的跳數(shù)未經(jīng)優(yōu)化，本身就會(huì)引入誤差，其次最后采用傳統(tǒng)極大似然估計(jì)法對(duì)節(jié)點(diǎn)進(jìn)行定位，不能將定位誤差最小化。文獻(xiàn)[6]對(duì)平均跳距進(jìn)行優(yōu)化，同時(shí)升級(jí)輔助錨節(jié)點(diǎn)以提高定位覆蓋率，但是使用遺傳算法計(jì)算節(jié)點(diǎn)位置，過(guò)多的迭代次數(shù)增加了節(jié)點(diǎn)計(jì)算開(kāi)銷。文獻(xiàn)[7]的算法在第2階段使用蛙跳算法改進(jìn)跳距誤差，并在第3階段使用混合遺傳-粒子群算法，提高了定位精度，但大量的仿生計(jì)算也極大增加了傳感器節(jié)點(diǎn)的功耗和定位所需的時(shí)長(zhǎng)，對(duì)于節(jié)點(diǎn)能量有限的傳感器來(lái)說(shuō)是不合適的。文獻(xiàn)[8]使用2種灰狼算法對(duì)平均跳距進(jìn)行優(yōu)化，對(duì)精度有一定提升效果，但是未對(duì)跳數(shù)進(jìn)行優(yōu)化，且使用的最小二乘法沒(méi)有考慮到權(quán)值誤差最小化問(wèn)題。

綜上所述，現(xiàn)有大多數(shù)三維定位算法都是采用仿生算法或者機(jī)器學(xué)習(xí)[9]的算法進(jìn)行優(yōu)化，雖然取得了一定的效果，但是對(duì)于能量有限的傳感器而言，計(jì)算任務(wù)過(guò)于繁重。然而最小二乘法[10]的整體誤差最小化思想又無(wú)法對(duì)未知節(jié)點(diǎn)進(jìn)行精確求解。本文針對(duì)傳統(tǒng)DV-Hop三維定位算法定位精度低，且傳感器節(jié)點(diǎn)能量有限不適合進(jìn)行大量計(jì)算和通信的特點(diǎn)，對(duì)DV-Hop算法進(jìn)行改進(jìn)。針對(duì)DV-Hop三維定位算法的定位方式，本文從3個(gè)方面對(duì)其進(jìn)行優(yōu)化：(1)采用二通信半徑(分別為R和0.5R)優(yōu)化跳數(shù)值；(2)采用平方代價(jià)函數(shù)計(jì)算跳距，并對(duì)其進(jìn)行加權(quán)優(yōu)化；(3)使用Lagrangian乘子法求解未知節(jié)點(diǎn)方程組，將最小二乘的整體誤差最小化轉(zhuǎn)換加權(quán)誤差最小化，使用加權(quán)誤差最小化的思想來(lái)對(duì)未知節(jié)點(diǎn)進(jìn)行定位計(jì)算。最后通過(guò)4種算法進(jìn)行實(shí)驗(yàn)，結(jié)果表明，本文算法在不需要進(jìn)行大量計(jì)算的基礎(chǔ)上，能夠大大提高節(jié)點(diǎn)定位精度，降低誤差率。

2 傳統(tǒng)DV-Hop三維定位算法和誤差原因探討

2.1 傳統(tǒng)DV-Hop三維定位算法

傳統(tǒng)DV-Hop三維定位算法包括3個(gè)步驟，分別是：

Step1確定最小跳數(shù)值。在開(kāi)始組網(wǎng)過(guò)程中，每個(gè)錨節(jié)點(diǎn)使用通信半徑R將包含自身編號(hào)id、所處GPS定位信息和跳數(shù)值為0的數(shù)據(jù)包發(fā)送給鄰居節(jié)點(diǎn)，并且每經(jīng)過(guò)一次鄰居節(jié)點(diǎn)的轉(zhuǎn)發(fā)就對(duì)跳數(shù)值增加1。當(dāng)鄰居節(jié)點(diǎn)(可能是未知的節(jié)點(diǎn)或錨節(jié)點(diǎn))接收到該類數(shù)據(jù)包之后，分2種情況處理：若自身已經(jīng)接收到該id編號(hào)的數(shù)據(jù)包，則對(duì)比路由表中具有相同id編號(hào)的數(shù)據(jù)包和接收到的數(shù)據(jù)包的跳數(shù)值大小，如果接收到的數(shù)據(jù)包中的跳數(shù)值比存儲(chǔ)的小，則用接收到的跳數(shù)值替換已存儲(chǔ)的跳數(shù)值；若接收到數(shù)據(jù)包中的跳數(shù)值大于存儲(chǔ)在路由表具有相同id編號(hào)的跳數(shù)值，則舍棄本次接收到的數(shù)據(jù)包。如此重復(fù)，便能得到對(duì)于各錨節(jié)點(diǎn)而言的最小跳數(shù)值。

Step2計(jì)算錨節(jié)點(diǎn)的平均跳距值和未知節(jié)點(diǎn)與各錨節(jié)點(diǎn)的距離。通過(guò)Step 1獲取到與各錨節(jié)點(diǎn)之間的最小跳數(shù)值之后，在傳統(tǒng)算法中，錨節(jié)點(diǎn)的平均跳距值的計(jì)算如式(1)所示：

HopSizei=

(1)

其中,j=1,2,…,m且i≠j，m為錨節(jié)點(diǎn)數(shù)量,(xi,yi,zi)和(xj,yj,zj)是由GPS定位出的錨節(jié)點(diǎn)i和錨節(jié)點(diǎn)j的三維位置信息，hij為錨節(jié)點(diǎn)i距錨節(jié)點(diǎn)j的最小跳數(shù)(由Step 1得出)。

計(jì)算出所有HopSizei后，每個(gè)錨節(jié)點(diǎn)使用通信半徑R對(duì)其計(jì)算出的HopSizei進(jìn)行廣播,未知節(jié)點(diǎn)p只存儲(chǔ)第1次接收到的平均跳距值。當(dāng)未知節(jié)點(diǎn)p接收到錨節(jié)點(diǎn)i傳來(lái)的HopSizei時(shí)，使用式(2)計(jì)算其與各錨節(jié)點(diǎn)的估計(jì)距離：

dp,j=HopSizei×hpj

(2)

其中，dp,j表示未知節(jié)點(diǎn)p與錨節(jié)點(diǎn)j在三維空間中的估計(jì)距離，j=1,2,…,m。

Step3未知節(jié)點(diǎn)坐標(biāo)估計(jì)。本文令未知節(jié)點(diǎn)p的三維位置信息為(x,y,z)，由GPS定位的第i個(gè)錨節(jié)點(diǎn)的三維位置信息為(xi,yi,zi)，其中i=1,2,…,m，根據(jù)Step 2計(jì)算出的p與各錨節(jié)點(diǎn)的估計(jì)距離d1,d2,…,dm，可以利用極大似然估計(jì)法列出如式(3)所示的方程組：

(3)

式(3)的矩陣形式為AX=B,其中，

B=

使用最小二乘法,可以解得：

X=(ATA)-1ATB

(4)

2.2 算法誤差產(chǎn)生原因

在傳統(tǒng)DV-Hop三維定位算法中，對(duì)跳數(shù)的估計(jì)是不精確的，如圖1所示。

Figure 1 Schematic diagram of hop error圖1 跳數(shù)誤差示意圖

從圖1中可以看出，未知節(jié)點(diǎn)a與錨節(jié)點(diǎn)i的距離大約為0.5R，未知節(jié)點(diǎn)b與錨節(jié)點(diǎn)i的距離為R，但是由于未知節(jié)點(diǎn)a和b在傳統(tǒng)DV-Hop算法中的跳數(shù)值均為1，導(dǎo)致節(jié)點(diǎn)a估算的距離與實(shí)際的距離0.5R差別很大，引入了接近一倍的誤差，降低了定位精度。定位誤差產(chǎn)生過(guò)程如圖2所示。

Figure 2 Generation process of positioning error圖2 定位誤差產(chǎn)生過(guò)程

在圖2中，錨節(jié)點(diǎn)i,k與未知節(jié)點(diǎn)a的距離為R，錨節(jié)點(diǎn)j與未知節(jié)點(diǎn)a的距離略小于0.5R，此時(shí)傳統(tǒng)DV-Hop三維定位算法依然將其跳數(shù)值處理為1，其與i、k和j的距離本應(yīng)為1*HopSize,1*HopSize和0.5*HopSize，卻由于跳數(shù)值為1變?yōu)?*HopSize,1*HopSize和1*HopSize,由此造成了定位誤差。

其次，傳統(tǒng)DV-Hop三維定位算法處理每個(gè)錨節(jié)點(diǎn)的平均跳距時(shí)，采用的代價(jià)函數(shù)如式(5)所示：

(5)

最后，傳統(tǒng)DV-Hop三維定位算法采用極大似然估計(jì)[11]的思想列出的方程組并沒(méi)有考慮誤差的權(quán)值，且使用最小二乘法對(duì)方程進(jìn)行求解，然而最小二乘法在矩陣接近奇異時(shí)的求解也十分不理想，因此造成了2方面誤差的產(chǎn)生。

3 改進(jìn)的DV-Hop三維定位算法

由于傳統(tǒng)DV-Hop三維定位算法的一系列缺點(diǎn)[12]，本文結(jié)合無(wú)線傳感器網(wǎng)絡(luò)的特點(diǎn)，從3個(gè)方面分別進(jìn)行改進(jìn)。

3.1 最小跳數(shù)值的修正

傳統(tǒng)DV-Hop三維定位算法在獲取最小跳數(shù)值時(shí)，只采用了一個(gè)通信半徑[13]，這樣做的缺點(diǎn)有：若通信半徑過(guò)大，則會(huì)造成最小跳數(shù)值極不準(zhǔn)確；若通信半徑過(guò)小，則會(huì)造成網(wǎng)絡(luò)連通性很差，甚至出現(xiàn)盲節(jié)點(diǎn)。為此本文提出二通信半徑的思想：

在執(zhí)行Step 1之前，錨節(jié)點(diǎn)使用通信半徑的一半(0.5R)傳播數(shù)據(jù)包，相鄰節(jié)點(diǎn)接收到數(shù)據(jù)包存儲(chǔ)在數(shù)據(jù)表中，考慮到傳感器節(jié)點(diǎn)特點(diǎn)，相鄰節(jié)點(diǎn)并不轉(zhuǎn)發(fā)數(shù)據(jù)包，隨后，錨節(jié)點(diǎn)使用通信半徑R對(duì)數(shù)據(jù)包(同Step1)進(jìn)行洪泛，以此獲得修正的跳數(shù)值，從而使得節(jié)點(diǎn)之間的最小跳數(shù)值更準(zhǔn)確。

3.2 平均跳距的改進(jìn)

3.2.1 采用平方代價(jià)函數(shù)計(jì)算HopSize

在傳統(tǒng)DV-Hop三維定位算法中，采用代價(jià)函數(shù)f1的計(jì)算方式不理想，所以本文采用平方代價(jià)函數(shù)f2計(jì)算平均跳距值，如式(6)所示:

(6)

對(duì)HopSizei求偏導(dǎo)，并令其值為0，即:

(7)

則可以求解出平均跳距值HopSizei如式(8)所示:

(8)

3.2.2 平均跳距的加權(quán)

DV-Hop的定位實(shí)質(zhì)上與節(jié)點(diǎn)的拓?fù)溆兄芮械年P(guān)系，當(dāng)未知節(jié)點(diǎn)與多個(gè)錨節(jié)點(diǎn)之間的距離和跳數(shù)均相差不大時(shí)，單單依靠一個(gè)錨節(jié)點(diǎn)的平均跳距就會(huì)產(chǎn)生相當(dāng)大的誤差，但是若采用全部錨節(jié)點(diǎn)進(jìn)行加權(quán)，則會(huì)增加不必要的計(jì)算量,因此應(yīng)當(dāng)有選擇性地選擇錨節(jié)點(diǎn)的個(gè)數(shù)。為此，本文采用對(duì)距未知節(jié)點(diǎn)最近的3個(gè)錨節(jié)點(diǎn)引入權(quán)值的思想，僅對(duì)距離未知節(jié)點(diǎn)最近的3個(gè)錨節(jié)點(diǎn)引入權(quán)值1，其余錨節(jié)點(diǎn)權(quán)值均為0，即只使用3個(gè)錨節(jié)點(diǎn)的平均跳距信息。由于這3個(gè)錨節(jié)點(diǎn)與未知節(jié)點(diǎn)的距離是有區(qū)別的，越靠近未知節(jié)點(diǎn)的錨節(jié)點(diǎn)越能反映出未知節(jié)點(diǎn)周圍的拓?fù)淝闆r，使用該錨節(jié)點(diǎn)的平均跳距的權(quán)重也應(yīng)當(dāng)越大。本文使用Wi來(lái)表示錨節(jié)點(diǎn)i的平均跳距對(duì)于未知節(jié)點(diǎn)的權(quán)重比例，如式(9)所示：

(9)

其中，i、j和k分別是與未知節(jié)點(diǎn)距離最近的3個(gè)錨節(jié)點(diǎn)，Ni、Nj和Nk分別是未知節(jié)點(diǎn)與錨節(jié)點(diǎn)i、j和k經(jīng)過(guò)最小跳數(shù)修正后得出的跳數(shù)值。

在本文中，未知節(jié)點(diǎn)p平均跳距采用式(10)進(jìn)行計(jì)算：

(10)

3.3 無(wú)約束的Lagrangian乘子法

3.3.1 構(gòu)造無(wú)約束方程組

傳統(tǒng)DV-Hop三維定位算法，幾乎都是使用蛙跳算法、差分進(jìn)化算法和遺傳算法等一類仿生算法來(lái)求解式(3)，不可否認(rèn)這些算法都相當(dāng)優(yōu)秀，但是過(guò)多的迭代次數(shù)和龐大的計(jì)算量加劇了傳感器網(wǎng)絡(luò)的能量消耗。本文使用無(wú)約束的Lagrangian乘子法對(duì)未知節(jié)點(diǎn)進(jìn)行求解。

(11)

用前m-1個(gè)方程依次減去最后一個(gè)方程并展開(kāi)得到式(12)：

(12)

(13)

令：

ai=2(xm-xi)

bi=2(ym-yi)

ci=2(zm-zi)

αi=-2di

β=2dm

則式(13)可以寫(xiě)成如式(14)所示形式：

(14)

式(14)的矩陣形式為CY=D，其中,

Y=[x,y,z,e1,e2,…,em]T

D=[D1,D2,D3,…,Dm-1]T

經(jīng)過(guò)上述一系列步驟，求解問(wèn)題轉(zhuǎn)換為式(15)所示的約束問(wèn)題:

s.t.CY=D

(15)

為體現(xiàn)出誤差的權(quán)值性，本文在此引入權(quán)值矩陣Q對(duì)誤差項(xiàng)進(jìn)行加權(quán)，從而將問(wèn)題轉(zhuǎn)化為權(quán)值誤差最小化問(wèn)題：

于是約束問(wèn)題轉(zhuǎn)換為式(16)所示形式：

mineTQe

s.t.CY=D

(16)

使用Lagrangian乘子法將式(16)的約束問(wèn)題轉(zhuǎn)換成無(wú)約束問(wèn)題，如式(17)所示：

(17)

其中，λ為L(zhǎng)agrangia乘子，λ>0且為常數(shù)。

3.3.2 無(wú)約束方程的求解

首先令f對(duì)矩陣Y求梯度矩陣為：

(18)

f對(duì)矩陣Y的Hessian矩陣為：

H[f]=2(Z+λCTC)

(19)

H[f]=2(Z+λCTC+δI)

(20)

其中，δ為擾動(dòng)因子且δ>0，I為m+3階單位矩陣。

Y=(Z+λCTC)-1λCTD

(21)

由于H[f]為正定矩陣，所以Y=(Z+λCTC+δI)-1λCTD，至此,可以解得未知節(jié)點(diǎn)的坐標(biāo) 。

4 仿真結(jié)果及分析

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

為驗(yàn)證本文算法與傳統(tǒng)算法、改進(jìn)算法1、改進(jìn)算法2的定位精度，在Matlab 2016a中進(jìn)行仿真實(shí)驗(yàn)。其中改進(jìn)算法1采用本文提出的跳數(shù)、跳距優(yōu)化及最小二乘法的策略；改進(jìn)算法2采用本文提出的跳數(shù)、跳距優(yōu)化及粒子群算法的策略。實(shí)驗(yàn)場(chǎng)景為邊長(zhǎng)均為100 m的山區(qū)地形環(huán)境，并于其中隨機(jī)投放未知節(jié)點(diǎn)和錨節(jié)點(diǎn)[14]，如圖3所示。

Figure 3 Node 3D distribution map圖3 節(jié)點(diǎn)三維分布圖

本文使用式(22)所示的未知節(jié)點(diǎn)平均定位誤差作為評(píng)價(jià)算法優(yōu)劣的標(biāo)準(zhǔn)[15]：

Avg_error=

(22)

其中,(xi,yi,zi)為未知節(jié)點(diǎn)的真實(shí)三維坐標(biāo)，(x′i,y′i,z′i)為通過(guò)算法求出的未知節(jié)點(diǎn)的三維坐標(biāo)，n為實(shí)驗(yàn)中未知節(jié)點(diǎn)的個(gè)數(shù)。

4.2 仿真結(jié)果分析

本文從錨節(jié)點(diǎn)數(shù)、通信半徑和節(jié)點(diǎn)總數(shù)3個(gè)方面來(lái)對(duì)4種算法進(jìn)行分析討論。

4.2.1 錨節(jié)點(diǎn)數(shù)與平均定位誤差分析

在邊長(zhǎng)均為100 m的山區(qū)地形環(huán)境隨機(jī)投放200個(gè)節(jié)點(diǎn)，且實(shí)驗(yàn)采用的通信半徑均設(shè)置為40 m,觀察當(dāng)錨節(jié)點(diǎn)比例變化時(shí)，對(duì)4種算法定位誤差的影響，其中錨節(jié)點(diǎn)比例分別取0.1,0.15,0.2,0.25,0.3,0.35,0.4,0.45,0.5。實(shí)驗(yàn)結(jié)果為各類算法運(yùn)行100次的均值，并繪制變化趨勢(shì)圖，如圖4所示。

Figure 4 Trend of anchor node proportion and average positioning error圖4 錨節(jié)點(diǎn)比例與平均定位誤差的關(guān)系變化趨勢(shì)圖

從圖4中可以看出，4種算法的平均定位誤差均隨著錨節(jié)點(diǎn)比例的增加而下降，且改進(jìn)算法2的平均定位誤差略低于本文算法的。在整個(gè)實(shí)驗(yàn)過(guò)程中，傳統(tǒng)算法、改進(jìn)算法1和改進(jìn)算法2的平均定位誤差分別為0.318 1,0.207 6和0.113 0,本文算法的平均定位誤差為0.118 6。具體變化情況如表1所示。

Table 1 Average positioning errors under different anchor node proportion

從表1中可以得出，在錨節(jié)點(diǎn)比例為0.1時(shí)，本文算法相對(duì)傳統(tǒng)算法、改進(jìn)算法1和改進(jìn)算法2的平均定位誤差分別降低了0.203 2,0.080 2,-0.003 5；在錨節(jié)點(diǎn)比例為0.3時(shí)，本文算法相對(duì)傳統(tǒng)算法、改進(jìn)算法1和改進(jìn)算法2的平均定位誤差分別降低了0.197 5,0.091 5,-0.007 8；在錨節(jié)點(diǎn)比例為0.5時(shí)，本文算法相對(duì)傳統(tǒng)算法、改進(jìn)算法1和改進(jìn)算法2的平均定位誤差分別降低了0.200 8,0.095 1,0.000 7。由此可知本文算法不論在何種錨節(jié)點(diǎn)比例情況下，相對(duì)于傳統(tǒng)算法均能將平均定位誤差降低0.20左右，相對(duì)于改進(jìn)算法1均能將誤差降低0.09左右，相對(duì)于改進(jìn)算法2而言，本文算法仍具有與其相當(dāng)?shù)木取?/p>

4.2.2 通信半徑與平均定位誤差分析

在邊長(zhǎng)均為100 m的山區(qū)地形環(huán)境隨機(jī)投放200個(gè)節(jié)點(diǎn)，且實(shí)驗(yàn)采用的錨節(jié)點(diǎn)比例均設(shè)置為0.25，觀察當(dāng)通信半徑變化時(shí)，4種算法的平均定位誤差變化趨勢(shì)，其中，通信半徑分別為40,45,50,55,60,65,70，實(shí)驗(yàn)結(jié)果為各類算法運(yùn)行100次的均值，并繪制變化趨勢(shì)圖，如圖5所示。

Figure 5 Trend of communication radius and average positioning error圖5 通信半徑與平均定位誤差的關(guān)系變化趨勢(shì)圖

從圖5中可以看出，傳統(tǒng)算法與改進(jìn)算法1的平均定位誤差均隨著通信半徑的增加而降低，改進(jìn)算法2與本文算法的平均定位誤差雖隨通信半徑變化不大，但均處于較高精度水平。整個(gè)實(shí)驗(yàn)過(guò)程中，傳統(tǒng)算法、改進(jìn)算法1和改進(jìn)算法2的平均定位誤差分別為0.294 2,0.176 5,0.096 9,本文算法的平均定位誤差為0.108 3。具體變化情況如表2所示。

Table 2 Average positioning error under different transmission radius

從表2中可以得出，在通信半徑為40 m時(shí)，本文算法相對(duì)傳統(tǒng)算法、改進(jìn)算法1和改進(jìn)算法2的平均定位誤差分別降低了0.191 7,0.088 3,-0.007 5；在通信半徑為55 m時(shí)，本文算法相對(duì)傳統(tǒng)算法、改進(jìn)算法1和改進(jìn)算法2的平均定位誤差分別降低了0.200 3,0.066 5,-0.009 3；在通信半徑為70 m時(shí)，本文算法相對(duì)傳統(tǒng)算法、改進(jìn)算法1和改進(jìn)算法2的平均定位誤差分別降低了0.152 7,0.054 3,-0.01 9,其中本文算法與改進(jìn)算法2在通信半徑為65 m時(shí)誤差相差最大僅為0.02，故從本文算法與改進(jìn)算法2在整個(gè)實(shí)驗(yàn)中的平均定位誤差均值與其之間的最大誤差差值來(lái)看，這種差值仍是可接受的良性水平。

4.2.3 節(jié)點(diǎn)總數(shù)與平均定位誤差分析

在邊長(zhǎng)均為100 m的山區(qū)地形環(huán)境內(nèi)，設(shè)置錨節(jié)點(diǎn)比例恒定為0.4，參與實(shí)驗(yàn)節(jié)點(diǎn)通信半徑均設(shè)置成50 m，觀察節(jié)點(diǎn)總數(shù)變化，對(duì)4種算法平均定位定位誤差的影響，其中，節(jié)點(diǎn)總數(shù)分別為100,150,200,250,300,350,400,450,500。實(shí)驗(yàn)結(jié)果為各類算法運(yùn)行100次的均值，并繪制變化趨勢(shì)圖，如圖6所示。

Figure 6 Trend of total number of nodes and average average positioning error圖6 節(jié)點(diǎn)總數(shù)與平均定位誤差的關(guān)系變化趨勢(shì)圖

從圖6中可以看出，在節(jié)點(diǎn)總數(shù)大于250時(shí)，改進(jìn)算法2與本文算法定位精度差距變大。在整個(gè)實(shí)驗(yàn)過(guò)程中，傳統(tǒng)算法、改進(jìn)算法1和改進(jìn)算法2的平均定位誤差分別為0.296 7,0.172 4,0.084 0，本文算法的平均定位誤差為0.095 2。具體變化情況如表3所示。

Table 3 Average positioning errors under different total number of nodes

從表3中可以得出，在節(jié)點(diǎn)總數(shù)為100時(shí)，本文算法相對(duì)傳統(tǒng)算法、改進(jìn)算法1和改進(jìn)算法2的平均定位誤差分別降低了0.182 9,0.075 2,-0.008 1；在節(jié)點(diǎn)總數(shù)為300時(shí)，本文算法相對(duì)傳統(tǒng)算法、改進(jìn)算法1和改進(jìn)算法2的平均定位誤差分別降低了0.205 4,0.077 3,-0.011 7；在節(jié)點(diǎn)總數(shù)為500時(shí)，本文算法相對(duì)傳統(tǒng)算法、改進(jìn)算法1和改進(jìn)算法2的平均定位誤差分別降低了0.218 3,0.082 4,-0.017 9,其中改進(jìn)算法2與本文算法在整個(gè)實(shí)驗(yàn)過(guò)程中的平均定位誤差差值為0.002 4和0.017 9，節(jié)點(diǎn)總數(shù)為200時(shí)平均定位誤差差值最小，節(jié)點(diǎn)總數(shù)為500時(shí)平均定位誤差差值最大。不論是平均定位誤差還是最大定位誤差差值，本文算法在不進(jìn)行大量計(jì)算的情況下與使用仿生算法的改進(jìn)算法2之間的誤差差值都是比較小的。

4.3 算法計(jì)算復(fù)雜度與計(jì)算時(shí)間分析

算法的計(jì)算復(fù)雜度與該區(qū)域未知節(jié)點(diǎn)數(shù)相關(guān)，令頻度函數(shù)為T(η)=(1-δ)η，其中，η為節(jié)點(diǎn)總數(shù),δ為錨節(jié)點(diǎn)比例，令T(η)的各未知項(xiàng)均為υ，可得T(υ)=υ2，故可知傳統(tǒng)算法與改進(jìn)算法1及本文算法的計(jì)算復(fù)雜度均為O(υ2)。改進(jìn)算法2的頻度函數(shù)為T(η)=(1-δ)η·MAXG·NP，其中,MAXG為最大迭代次數(shù)，NP為種群數(shù)量，令T(η)的各未知項(xiàng)均為υ，可得T(υ)=υ4，因此改進(jìn)算法2的計(jì)算復(fù)雜度為O(υ4)，遠(yuǎn)高于本文算法的計(jì)算復(fù)雜度。

在一個(gè)1.8 GHz Intel Core i7 CPU和8 GB RAM的系統(tǒng)上測(cè)試各算法的運(yùn)行時(shí)間，其中錨節(jié)點(diǎn)比例為0.3，通信半徑為50 m，改進(jìn)算法2的MAXG為100，NP為100，時(shí)間結(jié)果取算法運(yùn)行100次的均值，如表4所示。

Table 4 Comparison of algorithm average running time under different conditions

不論從計(jì)算復(fù)雜度還是計(jì)算時(shí)間來(lái)看，改進(jìn)算法2的計(jì)算代價(jià)比本文算法都要高，而本文算法與改進(jìn)算法2之間的最大定位誤差差值卻不到0.02，本文算法在不使用大量迭代運(yùn)算的前提下，對(duì)精度的提升是十分明顯的，也是具有實(shí)際應(yīng)用意義的。

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

本文指出了傳統(tǒng)DV-Hop三維定位算法在跳數(shù)計(jì)算、平均跳距計(jì)算和最小二乘法的不足3個(gè)方面的缺陷，并有針對(duì)性地提出了改進(jìn)方法：采用二通信半徑使得跳數(shù)計(jì)數(shù)更為準(zhǔn)確；采用平方代價(jià)函數(shù)的思想使跳距誤差更小，并針對(duì)未知節(jié)點(diǎn)與多個(gè)錨節(jié)點(diǎn)相鄰的情況，提出加權(quán)跳距的方案；使用無(wú)約束優(yōu)化并對(duì)誤差加權(quán)，使得加權(quán)誤差最小化。最后通過(guò)實(shí)驗(yàn)表明，本文算法在不進(jìn)行大量計(jì)算的前提下能夠大大提升定位精度，具有較好的應(yīng)用前景。