張 晶，李 煜

1(昆明理工大學(xué) 信息工程與自動化學(xué)院，昆明 650500)

2(云南梟潤科技服務(wù)有限公司，昆明 650500)

3(昆明理工大學(xué) 云南省人工智能重點實驗室，昆明 650500)

4(昆明理工大學(xué) 云南省計算機(jī)技術(shù)應(yīng)用重點實驗室，昆明 650500)

E-mail：1256058027@qq.com

1 引 言

在萬物互聯(lián)的物聯(lián)網(wǎng)世界中，各種各樣的傳感器在其中扮演著不可或缺的角色，傳感器能夠?qū)κ挛镞M(jìn)行實時的監(jiān)測，通過網(wǎng)絡(luò)通信將有價值的信息再傳遞給人類[1].例如：對森林動物移動位置的監(jiān)測、森林火災(zāi)檢測、戰(zhàn)爭中敵軍的行動位置等等.若無法清楚的了解事件發(fā)生的地點，大多數(shù)時候所獲得的檢測信息也就失去了價值，因此對于傳感器定位位置的研究一直是傳感器的一個研究重點[2].為此，國內(nèi)外許多學(xué)者都花費(fèi)了大量的人力物力在其定位問題的研究上，也均取得了一定的成功.

傳感器是一種對體積、能耗和成本均嚴(yán)格要求的設(shè)備，因此對所有傳感器均加裝GPS定位模塊是不現(xiàn)實的[3]，而且傳感器的位置一般采用飛機(jī)隨機(jī)拋灑的方式，落點不確定，有的落點靠GPS也可能無法實現(xiàn)定位而必須得依靠算法.為此定位算法的研究成為傳感器定位問題的關(guān)鍵.用盡可能低的成本完成位置的確定，也一直是評價算法的很重要指標(biāo).總體而言，定位算法分有兩種[4]，一種是對傳感器添加一些額外設(shè)備完成在實際場景下對距離或角度等信息的測量，故這種算法被稱為測距算法，另一種是無需對傳感器添加任何額外設(shè)備，僅僅依靠網(wǎng)絡(luò)間的連通性即可完成節(jié)點的定位，故這種算法被稱為無需測距的算法，盡管這兩者中測距算法對位置的估計更為精確，但是添加額外設(shè)備也使得節(jié)點成本增加、功耗增加，因此DV-Hop作為無需測距中的典型算法，近年來一直屬于熱門領(lǐng)域[5].

文獻(xiàn)[6]對跳數(shù)設(shè)定閾值，并以此為依據(jù)將跳距劃分為3種類別，對未知節(jié)點進(jìn)行加權(quán)最小二乘求解，并對未知節(jié)點周圍一跳范圍內(nèi)的錨節(jié)點進(jìn)行二次求質(zhì)心，將兩種解取均值作為最終解，對精度有一定提升，但是該算法沒有對一跳錨節(jié)點構(gòu)成的拓?fù)浣Y(jié)構(gòu)進(jìn)行分析，而采用所有錨節(jié)點進(jìn)行求質(zhì)心會增加誤差的積累，文獻(xiàn)[7]對跳距進(jìn)行了優(yōu)化，并對不同錨節(jié)點采用其自身跳距的距離計算方式，隨后使用levy策略的粒子群算法對未知節(jié)點進(jìn)行求解，雖使用仿生優(yōu)化算法，但仍存在較大誤差，為進(jìn)一步對精度進(jìn)行提高從而更有效的定位到事件發(fā)生點，本文提出一種3次修正的DV-Hop定位算法，是基于對DV-Hop算法的改進(jìn)研究，本文對DV-Hop算法的主要改進(jìn)點有：1)跳數(shù)的優(yōu)化：由于每個節(jié)點芯片都具有RSSI測量功能，為此提出基于RSSI測距的跳數(shù)劃分思想，將離散跳數(shù)連續(xù)化，得到更準(zhǔn)確的跳數(shù)值；2)跳距計算的優(yōu)化：由于錨節(jié)點計算跳距時，并沒有考慮到誤差正負(fù)的交替性，因此導(dǎo)致整體誤差不能代表出各項誤差最小化的缺點，為此提出采用平方誤差適應(yīng)度函數(shù)計算跳距的方式，且原始算法未能考慮到錨節(jié)點的跳數(shù)與距離的匹配關(guān)系，而籠統(tǒng)的將所有錨節(jié)點均視為同等重要進(jìn)行最小化適應(yīng)度函數(shù)的求解得到跳距，這會導(dǎo)致誤差的傳播，因此本文在此評定錨節(jié)點的距離與跳數(shù)的關(guān)系并以此作為權(quán)值對適應(yīng)度函數(shù)進(jìn)行最小化，進(jìn)而求解錨節(jié)點跳距；3)錨節(jié)點的反饋：由于DV-Hop是一個依賴網(wǎng)絡(luò)拓?fù)涞乃惴ǎ虼司辔粗?jié)點最近的錨節(jié)點的誤差信息能夠?qū)ξ粗?jié)點的估計坐標(biāo)有進(jìn)行校正的作用，本文采用一種新的錨節(jié)點誤差反饋策略對未知節(jié)點位置進(jìn)行第一次修正；4)采用泰勒展開式對未知節(jié)點進(jìn)行優(yōu)化：將使用錨節(jié)點誤差修正之后的未知節(jié)點位置作為初始值，在其周圍采用泰勒展開式進(jìn)行尋優(yōu)，得到二次修正后的未知節(jié)點位置，最后加入場景性限制條件，將定位的估計位置超出邊界的部分限制在邊界上，將小于零的部分限制為0，第3次修正未知節(jié)點位置，并將其值作為最終坐標(biāo).通過進(jìn)行的大量實驗數(shù)據(jù)表明，各階段的改進(jìn)算法均對未知節(jié)點坐標(biāo)起到了減少誤差的作用，且與文獻(xiàn)[6]、文獻(xiàn)[7]以及各階段算法而言，本文算法表現(xiàn)十分優(yōu)異.

2 原始DV-Hop算法

DV-Hop算法一般由3個主要部分構(gòu)成[8]：

最小跳數(shù)值的獲取[9].在節(jié)點的部署階段，傳感器錨節(jié)點將自身的id編號、位置信息、以及跳數(shù)值(起始跳數(shù)為0)，打包為一個數(shù)據(jù)包進(jìn)行洪泛傳播.當(dāng)節(jié)點第一次接收到各錨節(jié)點的數(shù)據(jù)包時，將接收到的數(shù)據(jù)包中的信息取出，將其跳數(shù)值加1后存入自身的路由表中，隨后未知節(jié)點將該數(shù)據(jù)包洪泛給其它節(jié)點.若節(jié)點不是首次接收到該錨節(jié)點的數(shù)據(jù)包，則對其跳數(shù)加1后比對該跳數(shù)值與路由表中的跳數(shù)值，若小則更新路由表中跳數(shù)值，并將該跳數(shù)加1的數(shù)據(jù)包洪泛給其它節(jié)點，若大則舍棄該數(shù)據(jù)包.自此，所有節(jié)點均能獲得對于各錨節(jié)點而言的最小跳數(shù)值.

錨節(jié)點平均跳距.以錨節(jié)點i為例，錨節(jié)點個數(shù)為N，計算其平均跳距采用無偏估計的方法，適應(yīng)度函數(shù)[10]如下：

f=1N-1∑i≠j(di，j-HopSizei·hopi，j)

(1)

令f=0，則可以求出其平均跳距為：

HopSizei=∑i≠jdi，j∑i≠jhopi，j

(2)

其中，hopi，j為錨節(jié)點i與其他所有錨節(jié)點的跳數(shù)，且均有i≠j，di，j，為錨節(jié)點i距其他各錨節(jié)點的距離.

未知節(jié)點的位置估計[11].各錨節(jié)點對其跳距值進(jìn)行傳播，未知節(jié)點僅接收第1次接收到的跳距值，其余均舍棄，以便獲得最近錨節(jié)點的拓?fù)湟惶?，并以此對自身距各錨節(jié)點距離進(jìn)行計算，以未知節(jié)點p為例，假設(shè)其首次接收到的是錨節(jié)點i的跳距值HopSizei，則如式(3)所示：

dp，j=HopSizei·hopp，j

(3)

其中，hopp，j是p距各錨節(jié)點的跳數(shù)，dp，j為其相對應(yīng)的近似距離.隨后，使用最大似然法列出方程[12]，方程如式(4)所示：

(x-x1)2+(y-y1)2=d21
(x-x2)2+(y-y2)2=d22
?
(x-xm)2+(y-ym)2=d2m

(4)

其中，d1，d2，d3，…，dm為p距各錨節(jié)點的近似距離.

式(4)的矩陣表述為：AX=D，其中：

A=2(x1-xm)(y1-ym)
(x2-xm)(y1-ym)
??
(xm-1-xm)(ym-1-xm)X=x
y

D=x21-x2n+y21-y2n+d2n-d21
x22-x2n+y22-y2n+d2n-d22
?
x2n-1-x2n+y2n-1-y2n+d2n-d2n-1

使用最小二乘[13]可以解得：X=(ATA)-1ATD.

3 改進(jìn)的DV-Hop算法

3.1 基于RSSI測距的跳數(shù)修正

相對于以往的跳數(shù)取值方式，文獻(xiàn)[14]采用的是多通信半徑的思想，但是多通信半徑的思想?yún)s會極大增加節(jié)點能耗，并且跳數(shù)的精確與否直接與預(yù)傳播半徑的劃分程度相關(guān)，文獻(xiàn)[15]采用二通信半徑的思想，不能對跳數(shù)進(jìn)行更精準(zhǔn)的劃分，并且這種劃分隨著通信半徑的增加，跳數(shù)會越來越不準(zhǔn)確.

為此本文采用RSSI測距的思想對跳數(shù)進(jìn)行連續(xù)劃分，使得離散跳數(shù)成為連續(xù)性跳數(shù)，但由于RSSI容易受到環(huán)境、噪聲、多徑傳播等因素的干擾，本文首先對RSSI進(jìn)行加權(quán)正態(tài)濾波優(yōu)化，使用濾波后的距離對跳數(shù)進(jìn)行連續(xù)性劃分.

3.1.1 RSSI測距模型

RSSI是現(xiàn)在的最受歡迎測距算法之一，因為現(xiàn)在大多數(shù)傳感器的芯片都具有測量RSSI強(qiáng)度的功能，無需對傳感器添加任何其它額外的硬件設(shè)備即可完成對距離的估測，但是由于信號在現(xiàn)實傳播過程中，并不是處于真空理想狀態(tài)，自然會受到各種因素的干擾，因此選擇一種合乎實際的模型直接關(guān)系到測距的準(zhǔn)確與否.而實際中常用的模型主要為傳播路徑損耗模型，本文采用此模型進(jìn)行距離的估測.信號傳播模型[16]如下：

RSSIr(d)=RSSIr(d0)-10ηlgdd0+ζ

(5)

其中，RSSIr(d)為距發(fā)射點d處信號強(qiáng)度大小，RSSIr(d0)為距發(fā)射點d0處的信號強(qiáng)度大小，為參考信號強(qiáng)度，一般d0取為1m，且其值已知，ζ為高斯噪聲，η為路徑損耗指數(shù).

3.1.2 加權(quán)正態(tài)濾波

由于信號在傳播時，經(jīng)常會受到環(huán)境、噪聲、多徑效應(yīng)等干擾，因此節(jié)點接收到的信號值往往不是真實值，而是受到干擾的值，為此，本文采用加權(quán)正態(tài)分布對傳感器接收到的信號值進(jìn)行處理.其中正態(tài)分布為：

f(x)=12πσexp(-(x-u)22σ2)

(6)

u=1N∑Ni=1xi

(7)

σ=1N-1∑Ni=1(xi-u)2

(8)

其中，u為信號均值，σ為信號的標(biāo)準(zhǔn)差.

根據(jù)正態(tài)分布的3σ原則，可知信號分布在(u-σ，u+σ)范圍內(nèi)的概率為0.6526，本文取RSSI值處于該區(qū)間內(nèi)的值作為有效值，規(guī)避不正常值對整體值的影響，并對該區(qū)間內(nèi)的一系列有效值進(jìn)行加權(quán)優(yōu)化.

假設(shè)節(jié)點篩選出的一組有效值為(RSSI1，RSSI2，RSSI3，…，RSSIn)，對其進(jìn)行求平均運(yùn)算得：

RSSIAVG=RSSI1+RSSI2+RSSI3+…+RSSInn

(9)

經(jīng)加權(quán)處理之后的最終RSSI值為：

RSSIWeight=∑nk=1wk·RSSIk∑nk=1wk

(10)

wk=11+|RSSIk-RSSIAVG|

(11)

其中wk為各有效RSSI的權(quán)值.

經(jīng)過加權(quán)正態(tài)處理，可以使節(jié)點獲得更為精準(zhǔn)的RSSI值，極大提高了測距的精度，將外界環(huán)境的影響降到最低.

3.1.3 RSSI測距的跳數(shù)修正方法

由于RSSI與距離的對應(yīng)關(guān)系為：

d=10A-RSSIr(d)10η

(12)

其中，A為參考信號強(qiáng)度即RSSIr(1)，為此，節(jié)點根據(jù)其修正的RSSIWeight計算出的距離為：

dweight=10A-RSSIWeight(d)10η

(13)

為此，修正的連續(xù)跳數(shù)為：dWeightR，其中R表示節(jié)點的通信半徑距離.

3.2 跳距適應(yīng)度函數(shù)的修正

原始DV-Hop算法在對跳距進(jìn)行計算時，采取了無偏估計[17]的方式計算跳距，但這種方式未能考慮到誤差是隨機(jī)分布且正負(fù)相間，導(dǎo)致總體誤差最小化并非能使各項誤差最小化，為此本文采用平方誤差函數(shù)作為適應(yīng)度函數(shù)求解跳距，如式(14)所示：

f2=1N-1∑i≠j(di，j-HopSizei·hopij)2

(14)

其中，di，j為錨節(jié)點i距其他所有錨節(jié)點之間的真實距離，N為錨節(jié)點個數(shù)，hopi，j為其相應(yīng)的跳數(shù)最小值，且均有i≠j.

使f2對HopSizei求偏導(dǎo)數(shù)，并令其值為0：

?f2?HopSizei=0

(15)

可以解得，跳距值為：

HopSizei=∑i≠j(hopij·di，j)∑i≠jhop2ij

(16)

盡管如此，在對錨節(jié)點跳距計算時，此適應(yīng)度函數(shù)也并未考慮到錨節(jié)點距離與跳數(shù)之間的匹配關(guān)系，如圖1錨節(jié)點分布.

圖1 錨節(jié)點分布圖Fig.1 Distribution diagram of anchor nodes

錨節(jié)點i與錨節(jié)點a、b、c之間的距離均大約為節(jié)點通信半徑距離R，然而節(jié)點i與節(jié)點a、b、c之間的跳數(shù)約分別為hi，a、hi，a+ha，b和hi，c.若采取同樣眼光看待這種錨節(jié)點關(guān)系，則會對錨節(jié)點的跳距計算產(chǎn)生很大的誤差，本文采用跳數(shù)-距離匹配因子αi，j來對平方誤差適應(yīng)度函數(shù)進(jìn)行修正，其中：

αi，j=di，j/hi，j

(17)

這種跳數(shù)-距離匹配因子可以讓距離與跳數(shù)不匹配的錨節(jié)點在參與計算跳距時所分配的權(quán)重值更小，如圖1中，在計算錨節(jié)點i的跳距時，給錨節(jié)點a、b、c所分配的權(quán)重分別為：

αi，a=di，a/hi，aαi，b=di，b/(hi，a+ha，b)αi，c=di，c/hi，c

因此，跳距的計算方式為如式(18)所示：

f2=1N-1∑i≠jα2i，j(di，j-HopSizei·hopij)2

(18)

同樣的，令?f2/?HopSizei=0，可以解得：

HopSizei=∑i≠jα2i，j·hopij·di，j∑i≠jα2i，j·hop2ij

(19)

3.3 錨節(jié)點誤差反饋策略

DV-Hop是一個依賴拓?fù)浣Y(jié)構(gòu)的算法[18]，且傳感器在分布時，一般采取隨機(jī)拋灑的方式，因此節(jié)點分布一般基本是隨機(jī)均勻分布的.根據(jù)DV-Hop的定位特點，未知節(jié)點跳距采取最近錨節(jié)點傳播的形式[19]，因此越接近待定位節(jié)點的錨節(jié)點，節(jié)點之間的拓?fù)湫问皆较嗨疲猛瑯臃绞?，定位錨節(jié)點和定位未知節(jié)點之間的誤差也越接近.于是本文提出一種錨節(jié)點誤差反饋策略對未知節(jié)點估計位置進(jìn)行修正.

使用改進(jìn)后的跳數(shù)、跳距對錨節(jié)點的位置進(jìn)行估計，假設(shè)錨節(jié)點的估計坐標(biāo)為(，)，真實坐標(biāo)為(x，y)，據(jù)此可以得到錨節(jié)點估計坐標(biāo)與實際坐標(biāo)的偏差值為：

Bx=-x
By=-y

(20)

隨后錨節(jié)點將此偏差值與其錨節(jié)點id打包成數(shù)據(jù)包，進(jìn)行洪泛傳播.

未知節(jié)點對偏差值的接收規(guī)則為：

若未知節(jié)點通信范圍內(nèi)存在大于等于3個的錨節(jié)點，則將所有該范圍錨節(jié)點偏差值的平均作為該未知節(jié)點的校正值.

若未知節(jié)點通信范圍內(nèi)錨節(jié)點數(shù)小于3，則將距該未知節(jié)點最近的3個錨節(jié)點的加權(quán)偏差值作為其校正值.對此未知節(jié)點僅接收3個不同錨節(jié)點id傳來的偏差值，存儲在自身路由表中，并將其繼續(xù)洪泛傳播給其鄰節(jié)點，其余偏差值均舍棄，對接收到的3個與其最近的錨節(jié)點的偏差值進(jìn)行加權(quán)作為自身定位的校正值，因為在實際傳感網(wǎng)絡(luò)中，相距較遠(yuǎn)的錨節(jié)點的定位偏差是毫無意義的，引入較遠(yuǎn)錨節(jié)點的偏差不僅會增加節(jié)點自身的計算量，也會帶入誤差，為此本文僅選擇3個最近錨節(jié)點的加權(quán)偏差值作為未知節(jié)點的校正值.

假設(shè)未知節(jié)點接收到的3個最近錨節(jié)點分別為i，j，k，且其偏差值分別為(Bi，x，Bi，y)，(Bj，x，Bj，y)，(Bk，x，Bk，y)，則該節(jié)點的校正值為：

x=∑kq=i(Wq×Bq，x)
y=∑kq=i(Wq×Bq，y)

(21)

其中，Wq=1/dp，q∑kq=i1dp，q，dp，q為改進(jìn)的距離.

假定未知節(jié)點使用改進(jìn)后的跳數(shù)、跳距值，得到的自身估計位置為(p，p)，則可得到其第1次的修正位置(x，y)為：

x=p-x
y=p-y

(22)

3.4 泰勒中值定理尋優(yōu)與場景限制

在傳統(tǒng)算法中，極大似然估計方程的求解采用的是最小二乘的方式，然而最小二乘無法對未知節(jié)點進(jìn)行更準(zhǔn)確的求解，在矩陣ATA接近奇異時，也包含了很大的誤差，為此，本文提出使用泰勒展開修正未知節(jié)點坐標(biāo)的方法，將使用優(yōu)化跳數(shù)、跳距、錨節(jié)點修正后計算出的未知節(jié)點坐標(biāo)作為展開點對未知節(jié)點位置進(jìn)一步修正，未知節(jié)點方程式(23)如下：

(x-x1)2+(y-y1)2=d21
(x-x2)2+(y-y2)2=d22
?
(x-xm)2+(y-ym)2=d2m

(23)

其中方程左邊部分為：

f(x，y)=(x-xn)2+(y-yn)2

(24)

且n為1，2，3，…，m，m為錨節(jié)點數(shù).

將f(x，y)在修正后的未知節(jié)點附近使用泰勒展開進(jìn)行二次修正，假設(shè)經(jīng)過一次修正后的未知節(jié)點坐標(biāo)為(x0，y0)，則可以得出：

f(x，y)=f(x0，y0)+(x-x0)f′x(x0，y0)+
(y-y0)f′y(x0，y0)+o(n)

(25)

其中令，α=(x-x0)，β=(y-y0)，為避免龐大的計算量，為此省略無窮小項o(n)，則上式變?yōu)椋?/p>

f(x，y)=f(x0，y0)+αf′x(x0，y0)+βf′y(x0，y0)
=(x0-xn)2+(y0-yn)2+2α(x0-xn)+2β(y0-yn)

(26)

將上式代入式(23)左邊項，得出方程組(27)為：

2α(x0-x1)+2β(y0-y1)=d21-(x0-x1)2-(y0-y1)2

2α(x0-x2)+2β(y0-y2)=d22-(x0-x2)2-(y0-y2)2

?

2α(x0-xm)+2β(y0-ym)=d2m-(x0-xm)2-(y0-ym)2

(27)

式(27)方程的矩陣形式表示為：

A=2(x0-x1)2(y0-y1)
2(x0-x2)2(y0-y2)
??
2(x0-xm)2(y0-ym)X=α
β

B=d21-(x0-x1)2-(y0-y1)2
d22-(x0-x2)2-(y0-y2)2
?
d2m-(x0-xm)2-(y0-ym)2

即：AX=B.

使用最小二乘法求解方程組得出X=(ATA)-1ATB，若α2+β2>Q，其中Q為某一較小臨界值，則令：

x0=x0+α/3
y0=y0+β/3

(28)

將(x0，y0)代入式(27)重新計算其α、β，直到α、β滿足α2+β2

最后，對于實際應(yīng)用場景下，節(jié)點一般部署于某一塊區(qū)域內(nèi)，且從理論出發(fā)，節(jié)點的定位坐標(biāo)不應(yīng)超出邊界或小于0值，于是，本文算法對于二次修正的未知節(jié)點定位坐標(biāo)加入場景性限制條件，將未知節(jié)點估計坐標(biāo)大于邊界值的值，限制為邊界值，小于0的坐標(biāo)值，限制為0.自此完成對未知節(jié)點的第3次修正.

3.5 算法實施步驟

本文算法的具體實施過程如下：

Step 1.錨節(jié)點利用洪泛的方式將包含自身id、初始為0的跳數(shù)值、與地理坐標(biāo)信息的數(shù)據(jù)包進(jìn)行傳播.各節(jié)點通過相鄰節(jié)點間接收到的一系列RSSI值，經(jīng)加權(quán)正態(tài)濾波得到其修正的RSSIWeight，根據(jù)計算出的距離得到其修正的連續(xù)跳數(shù)值.洪泛結(jié)束后，各節(jié)點獲得與其它錨節(jié)點的最小跳數(shù)值.

Step 2.各錨節(jié)點利用加權(quán)的適應(yīng)度對跳距進(jìn)行計算，并利用該跳距和連續(xù)跳數(shù)估算與其它錨節(jié)點距離，隨后利用多邊定位的方法進(jìn)行自身坐標(biāo)的估計，并計算出偏差值.

Step 3.錨節(jié)點將自身定位偏差打包成數(shù)據(jù)包進(jìn)行洪泛，未知節(jié)點根據(jù)接收規(guī)則計算自身校正值.

Step 4.未知節(jié)點也使用改進(jìn)的跳數(shù)、跳距計算自身坐標(biāo)，并與校正值相減得到未知節(jié)點第1次修正的坐標(biāo).

Step 5.將第一次修正的未知節(jié)點坐標(biāo)作為泰勒展開式的展開點代入方程組中進(jìn)行第2次修正，當(dāng)達(dá)到循環(huán)退出條件的精度，則退出循環(huán)體，并將其最終坐標(biāo)作為第2次的修正坐標(biāo)，完成對未知節(jié)點的第2次修正.

Step 6.將二次修正后的坐標(biāo)加入場景限制，對不合法的節(jié)點位置進(jìn)行校正，得到其第3次修正后的位置坐標(biāo).自此完成坐標(biāo)的定位.

4 算法分析與實驗設(shè)計

為評估本文算法與傳統(tǒng)DV-Hop算法和各改進(jìn)算法之間性能的差距，所有試驗均設(shè)計在matlab 2016平臺上進(jìn)行仿真驗證，其中改進(jìn)算法1采用本文錨節(jié)點誤差反饋、最小二乘法的第1次修正策略，改進(jìn)算法2采用本文跳數(shù)、跳距優(yōu)化改進(jìn)、錨節(jié)點誤差反饋、最小二乘法的改進(jìn)的第1次修正策略，本文算法采用跳數(shù)、跳距優(yōu)化、錨節(jié)點誤差反饋、泰勒尋優(yōu)、和場景性限制條件的改進(jìn)的3次修正策略，以及文獻(xiàn)[6]和文獻(xiàn)[7]的改進(jìn)算法，進(jìn)行對比實驗，節(jié)點部署于100×100范圍內(nèi)，且各節(jié)點均隨機(jī)分布，算法仿真性能采用未知節(jié)點的平均誤差作為評價算法優(yōu)劣的標(biāo)準(zhǔn)[20]，平均誤差越低代表網(wǎng)絡(luò)中節(jié)點的定位越準(zhǔn)確，如式(29)所示：

Avg_error=∑ni=1(xi-x′i)2+(yi-y′i)2n×R

(29)

圖2 實驗?zāi)M圖Fig.2 Experimental simulation diagram

其中n為測試中未知節(jié)點的數(shù)量，(xi，yi)為其實際位置，(x′i，y′i)為通過算法估計出的位置，實驗?zāi)M圖如圖2所示.

4.1 錨節(jié)點比例與平均定位誤差分析

在邊長均為100×100的矩形內(nèi)，設(shè)置節(jié)點總數(shù)為200，其中的錨節(jié)點比例變化趨勢為0.1、0.15、0.2、0.25、0.3、0.35、0.4、0.45、0.5，節(jié)點通信范圍均設(shè)置為40m，每次實驗結(jié)果對其取100次的均值，觀察6種算法對未知節(jié)點定位的準(zhǔn)確度.

從圖3中可以看出，在同一仿真條件下，在錨節(jié)點比例為0.1時，本文算法相對傳統(tǒng)算法、改進(jìn)算法1、改進(jìn)算法2、文獻(xiàn)[6]與文獻(xiàn)[7]算法的誤差降低了[0.2221，0.1599，0.0561，0.1476，0.1227]，在錨節(jié)點比例為0.3時，本文算法相對傳統(tǒng)算法、改進(jìn)算法1、改進(jìn)算法2、文獻(xiàn)[6]與文獻(xiàn)[7]算法的誤差降低了[0.2407，0.1544，0.0597，0.1364，0.105]，在錨節(jié)點比例為0.5時，本文算法相對傳統(tǒng)算法、改進(jìn)算法1、改進(jìn)算法2、文獻(xiàn)[6]與文獻(xiàn)[7]算法的誤差降低了[0.2442，0.1535，0.0616，0.1216，0.0852].由此可以得出，傳統(tǒng)算法的定位誤差在整個變化過程中幾乎變化不大，始終處于比較高的水平，改進(jìn)算法1、改進(jìn)算法2、文獻(xiàn)[6]、文獻(xiàn)[7]以及本文算法均隨著錨節(jié)點比例的增加，誤差有所降低，且本文算法即使在錨節(jié)點個數(shù)較低時，依然擁有較好的定位精度，對于未知節(jié)點而言，這一特點也使得該算法在一定程度上能夠減少布設(shè)時錨節(jié)點的數(shù)量，從而降低傳感網(wǎng)絡(luò)的造價.

圖3 錨節(jié)點比例與平均誤差的變化趨勢圖Fig.3 Trend chart of anchor nodes ratio and average error

4.2 通信范圍與平均定位誤差分析

在邊長均為100×100的矩形內(nèi)，設(shè)置節(jié)點總數(shù)為200，其中錨節(jié)點比例為0.25，節(jié)點通信范圍的變化趨勢為30、35、40、45、50、55、60、65、70，每次實驗結(jié)果對其取100次的均值，觀察6種算法對未知節(jié)點定位的準(zhǔn)確度.

圖4 通信范圍與平均誤差的變化趨勢圖Fig.4 Trend chart of communication range and average error

從圖4中可以看出，在同一仿真條件下，在節(jié)點通信半徑為30m時，本文算法相對傳統(tǒng)算法、改進(jìn)算法1、改進(jìn)算法2、文獻(xiàn)[6]與文獻(xiàn)[7]算法的誤差降低了[0.2244，0.1571，0.0561，0.1477，0.1198]，在節(jié)點通信半徑為50m時，本文算法相對傳統(tǒng)算法、改進(jìn)算法1、改進(jìn)算法2、文獻(xiàn)[6]與文獻(xiàn)[7]算法的誤差降低了[0.247，0.1503，0.0584，0.1274，0.098]，在節(jié)點通信半徑為70m時，本文算法相對傳統(tǒng)算法、改進(jìn)算法1、改進(jìn)算法2、文獻(xiàn)[6]與文獻(xiàn)[7]算法的誤差降低了[0.2028，0.1249，0.0518，0.1109，0.0799]，由此可以得出，傳統(tǒng)算法、改進(jìn)算法1、改進(jìn)算法2、文獻(xiàn)[6]算法、文獻(xiàn)[7]算法以及本文算法均隨著節(jié)點通信范圍的增加而有所下降，但本文算法對節(jié)點通信范圍容錯性較強(qiáng)，在較短通信范圍的情況下依然可以保持良好的定位準(zhǔn)確度，這也在一定程度上節(jié)省了傳感器的通信能量開銷，在保持良好定位準(zhǔn)確度的同時，本文算法使得網(wǎng)絡(luò)更節(jié)能.

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

在仿真環(huán)境邊長均為100×100的正方形區(qū)域內(nèi)，隨機(jī)投放的節(jié)點總數(shù)變化為100，150，200，250，300，350，400，450，500，其中錨節(jié)點比例為0.3，節(jié)點通信范圍為40m，每次實驗結(jié)果對其取100次的均值，觀察6種算法對未知節(jié)點定位的準(zhǔn)確度.

圖5 節(jié)點總數(shù)與平均誤差的變化趨勢圖Fig.5 Trend chart of the total number of nodes and average error

從圖5中可以看出，在同一仿真條件下，在節(jié)點總數(shù)為100時，本文算法相對傳統(tǒng)算法、改進(jìn)算法1、改進(jìn)算法2、文獻(xiàn)[6]與文獻(xiàn)[7]算法的誤差降低了[0.2057，0.1383，0.048，0.1357，0.0959]，在節(jié)點總數(shù)為300時，本文算法相對傳統(tǒng)算法、改進(jìn)算法1、改進(jìn)算法2、文獻(xiàn)[6]與文獻(xiàn)[7]算法的誤差降低了[0.2502，0.1589，0.0647，0.1332，0.0971]，在節(jié)點總數(shù)為500時，本文算法相對傳統(tǒng)算法、改進(jìn)算法1、改進(jìn)算法2、文獻(xiàn)[6]與文獻(xiàn)[7]算法的誤差降低了[0.2674，0.1657，0.0679，0.1306，0.0903]，由此可以得出，本文算法對節(jié)點數(shù)量適應(yīng)性較強(qiáng)，在較低節(jié)點總數(shù)的情況下，定位精度依然比較高，從而本文算法的實用性更強(qiáng)，更健壯.

4.4 算法計算時長分析

從計算時間分析，在一個1.8GHZ Intel Core i7 CPU和8GB RAM的系統(tǒng)上進(jìn)行測試，節(jié)點總數(shù)分別為100，300，500，其中錨節(jié)點比例為0.3，通信半徑為50m，其中文獻(xiàn)[7]算法的迭代數(shù)MAXG為50次，粒子數(shù)NP為30，每次時間結(jié)果取100次的均值(以秒為單位)，如表1所示.

為此，從計算時長上來看，本文算法的計算量遠(yuǎn)遠(yuǎn)小于使用改進(jìn)仿生算法的文獻(xiàn)[7]，與傳統(tǒng)算法相比，本文算法計算量也僅有小量增加，從精度上來看，本文算法的誤差最低，具有較好的實際應(yīng)用前景.

表1 不同條件下算法的平均運(yùn)行時間對比Table 1 Comparison of the average running time of the algorithm under different conditions

5 結(jié)束語

本文算法針對原始算法的跳數(shù)、跳距不準(zhǔn)確性進(jìn)行了相應(yīng)分析與改進(jìn)，并提出了對坐標(biāo)三次修正的方法，針對原始算法離散跳數(shù)不準(zhǔn)確的特點，提出基于RSSI測距的連續(xù)跳數(shù)劃分概念，其次原始算法采用無偏估計的方式計算跳距，在總體誤差最小化時，未能使得各項誤差最小化，因此本文采用平方誤差函數(shù)作為適應(yīng)度函數(shù)對跳距進(jìn)行求解，且原始算法未考慮到在錨節(jié)點計算跳距過程中的跳數(shù)與距離的匹配關(guān)系，跳距引入了更多的誤差，為此提出跳數(shù)-距離匹配因子對各錨節(jié)點在適應(yīng)度中進(jìn)行加權(quán)，從而得到更精準(zhǔn)的跳距.且由于DV-Hop算法是一種依賴網(wǎng)絡(luò)拓?fù)涞乃惴?，其依靠連通性即可完成對未知節(jié)點的定位，根據(jù)此特性，提出使用新的錨節(jié)點誤差反饋策略的拓?fù)涠ㄎ徽`差傳遞的思想，對使用了優(yōu)化跳數(shù)、跳距計算出的估計坐標(biāo)進(jìn)行第1次修正，其次本文對修正后的坐標(biāo)進(jìn)行泰勒展開尋優(yōu)，并將展開式代入未知節(jié)點方程組中，進(jìn)一步對未知節(jié)點估計坐標(biāo)進(jìn)行修正，最后加入場景性限制條件，第3次修正未知節(jié)點坐標(biāo).實驗也表明，每一步均對未知節(jié)點的估計坐標(biāo)起到了精化作用，該算法的使用使得未知節(jié)點定位更準(zhǔn)確，且具有實用價值.在以后的工作中，將著重于對加入構(gòu)建的動態(tài)錨節(jié)點對誤差傳遞并修正的效果影響以及拓展至三維條件.