改進的無約束優(yōu)化3D-DV-Hop定位算法*

張 晶，李 煜

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

1 引言

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

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

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

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

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

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

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

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

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

HopSizei=

(1)

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

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

dp,j=HopSizei×hpj

(2)

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

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

(3)

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

B=

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

X=(ATA)-1ATB

(4)

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

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

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

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

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

在圖2中，錨節(jié)點i,k與未知節(jié)點a的距離為R，錨節(jié)點j與未知節(jié)點a的距離略小于0.5R，此時傳統(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三維定位算法處理每個錨節(jié)點的平均跳距時，采用的代價函數(shù)如式(5)所示：

(5)

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

3 改進的DV-Hop三維定位算法

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

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

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

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

3.2 平均跳距的改進

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

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

(6)

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

(7)

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

(8)

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

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

(9)

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

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

(10)

3.3 無約束的Lagrangian乘子法

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

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

(11)

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

(12)

(13)

令：

ai=2(xm-xi)

bi=2(ym-yi)

ci=2(zm-zi)

αi=-2di

β=2dm

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

(14)

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

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

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

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

s.t.CY=D

(15)

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

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

mineTQe

s.t.CY=D

(16)

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

(17)

其中，λ為Lagrangia乘子，λ>0且為常數(shù)。

3.3.2 無約束方程的求解

首先令f對矩陣Y求梯度矩陣為：

(18)

f對矩陣Y的Hessian矩陣為：

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

(19)

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

(20)

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

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

(21)

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

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

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

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

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

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

Avg_error=

(22)

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

4.2 仿真結(jié)果分析

本文從錨節(jié)點數(shù)、通信半徑和節(jié)點總數(shù)3個方面來對4種算法進行分析討論。

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

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

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

從圖4中可以看出，4種算法的平均定位誤差均隨著錨節(jié)點比例的增加而下降，且改進算法2的平均定位誤差略低于本文算法的。在整個實驗過程中，傳統(tǒng)算法、改進算法1和改進算法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é)點比例為0.1時，本文算法相對傳統(tǒng)算法、改進算法1和改進算法2的平均定位誤差分別降低了0.203 2,0.080 2,-0.003 5；在錨節(jié)點比例為0.3時，本文算法相對傳統(tǒng)算法、改進算法1和改進算法2的平均定位誤差分別降低了0.197 5,0.091 5,-0.007 8；在錨節(jié)點比例為0.5時，本文算法相對傳統(tǒng)算法、改進算法1和改進算法2的平均定位誤差分別降低了0.200 8,0.095 1,0.000 7。由此可知本文算法不論在何種錨節(jié)點比例情況下，相對于傳統(tǒng)算法均能將平均定位誤差降低0.20左右，相對于改進算法1均能將誤差降低0.09左右，相對于改進算法2而言，本文算法仍具有與其相當(dāng)?shù)木取?/p>

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

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

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

從圖5中可以看出，傳統(tǒng)算法與改進算法1的平均定位誤差均隨著通信半徑的增加而降低，改進算法2與本文算法的平均定位誤差雖隨通信半徑變化不大，但均處于較高精度水平。整個實驗過程中，傳統(tǒng)算法、改進算法1和改進算法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時，本文算法相對傳統(tǒng)算法、改進算法1和改進算法2的平均定位誤差分別降低了0.191 7,0.088 3,-0.007 5；在通信半徑為55 m時，本文算法相對傳統(tǒng)算法、改進算法1和改進算法2的平均定位誤差分別降低了0.200 3,0.066 5,-0.009 3；在通信半徑為70 m時，本文算法相對傳統(tǒng)算法、改進算法1和改進算法2的平均定位誤差分別降低了0.152 7,0.054 3,-0.01 9,其中本文算法與改進算法2在通信半徑為65 m時誤差相差最大僅為0.02，故從本文算法與改進算法2在整個實驗中的平均定位誤差均值與其之間的最大誤差差值來看，這種差值仍是可接受的良性水平。

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

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

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

從圖6中可以看出，在節(jié)點總數(shù)大于250時，改進算法2與本文算法定位精度差距變大。在整個實驗過程中，傳統(tǒng)算法、改進算法1和改進算法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é)點總數(shù)為100時，本文算法相對傳統(tǒng)算法、改進算法1和改進算法2的平均定位誤差分別降低了0.182 9,0.075 2,-0.008 1；在節(jié)點總數(shù)為300時，本文算法相對傳統(tǒng)算法、改進算法1和改進算法2的平均定位誤差分別降低了0.205 4,0.077 3,-0.011 7；在節(jié)點總數(shù)為500時，本文算法相對傳統(tǒng)算法、改進算法1和改進算法2的平均定位誤差分別降低了0.218 3,0.082 4,-0.017 9,其中改進算法2與本文算法在整個實驗過程中的平均定位誤差差值為0.002 4和0.017 9，節(jié)點總數(shù)為200時平均定位誤差差值最小，節(jié)點總數(shù)為500時平均定位誤差差值最大。不論是平均定位誤差還是最大定位誤差差值，本文算法在不進行大量計算的情況下與使用仿生算法的改進算法2之間的誤差差值都是比較小的。

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

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

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

Table 4 Comparison of algorithm average running time under different conditions

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

5 結(jié)束語

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