劉鋒

（西安鐵路職業(yè)技術(shù)學(xué)院，陜西 西安 710026）

傳統(tǒng)衛(wèi)星測(cè)繪定位方法的精度較差，當(dāng)?shù)匦谓Y(jié)構(gòu)相對(duì)復(fù)雜時(shí)，其信號(hào)便會(huì)被遮擋，從而導(dǎo)致衛(wèi)星無(wú)法定位。因此，基于衛(wèi)星定位功能部署多個(gè)無(wú)線(xiàn)傳感器網(wǎng)絡(luò)（Wireless Sensor Networks,WSN）[1-3]是改善測(cè)繪衛(wèi)星信號(hào)被遮擋的方式之一。目前無(wú)線(xiàn)傳感器的定位方法可分為兩種，第一種方法需要計(jì)算各無(wú)線(xiàn)傳感器間的實(shí)際距離，該算法較為準(zhǔn)確，但普適性較差，且需要極高的部署成本，故不適合用作大范圍區(qū)域的無(wú)線(xiàn)定位。第二種方法無(wú)需計(jì)算傳感器距離，僅通過(guò)無(wú)線(xiàn)拓?fù)涞男畔鬟f關(guān)系便可對(duì)位置進(jìn)行估算，該方法雖然準(zhǔn)確度略遜于第一種，但成本更低且總體上也能取得良好的效果，其代表性算法為3DDV-Hop[4-5]。

由于傳統(tǒng)3DDV-Hop算法的定位精度較差，因此為了提升其精度，國(guó)內(nèi)諸多學(xué)者均對(duì)該算法進(jìn)行了改進(jìn)。改進(jìn)主要分為兩個(gè)方向：1）對(duì)各個(gè)傳感器節(jié)點(diǎn)的最小跳數(shù)[6]與平均跳距[7]進(jìn)行修訂；2）通過(guò)智能優(yōu)化算法[8]對(duì)節(jié)點(diǎn)的位置進(jìn)行特征學(xué)習(xí)和估算。文獻(xiàn)[9]利用人工蜂群（Artificial Bee Colony,ABC）算法對(duì)搜索空間的距離加以改進(jìn)，并提高了測(cè)距精度。但其迭代步數(shù)較多，故仍有提升空間。文獻(xiàn)[10]則通過(guò)概率統(tǒng)計(jì)值對(duì)節(jié)點(diǎn)的位置進(jìn)行優(yōu)化及預(yù)估，其算法精度雖較高，但計(jì)算量也在增大。

該文分析了3DDV-Hop 存在的問(wèn)題，并從最小跳數(shù)、平均跳距及定位坐標(biāo)的確定方法三方面對(duì)算法進(jìn)行了優(yōu)化，并在實(shí)驗(yàn)部分取得了較優(yōu)的效果。

1 基于改進(jìn)3DDV-Hop 的精確定位算法

1.1 3DDV-Hop定位算法

近年來(lái)無(wú)線(xiàn)傳感網(wǎng)絡(luò)技術(shù)發(fā)展迅速，定位空間的維度已從二維擴(kuò)展至三維。而3DDV-Hop 算法作為立體空間中的目標(biāo)定位方法，受到了廣泛關(guān)注。傳統(tǒng)3DDV-Hop 算法的實(shí)現(xiàn)步驟如下：

1）三維空間中的不同節(jié)點(diǎn)間，以信息傳播的方式確定跳數(shù)值。錨節(jié)點(diǎn)會(huì)發(fā)送包含自身標(biāo)識(shí)、跳數(shù)值與坐標(biāo)值的信息包至三維監(jiān)測(cè)區(qū)域中的相鄰節(jié)點(diǎn)，而該節(jié)點(diǎn)則會(huì)對(duì)信息包中的信息進(jìn)行存儲(chǔ)，此后再繼續(xù)轉(zhuǎn)發(fā)給下一相鄰節(jié)點(diǎn)。以此類(lèi)推，在監(jiān)測(cè)的三維區(qū)域空間中不同節(jié)點(diǎn)間以洪泛的形式進(jìn)行傳播，直至整個(gè)監(jiān)測(cè)區(qū)域內(nèi)的所有節(jié)點(diǎn)均完成信息的傳播與存儲(chǔ)為止。具體的節(jié)點(diǎn)信息傳播圖如圖1 所示。其中白色代表未知節(jié)點(diǎn)，黑色則代表錨節(jié)點(diǎn)。

圖1 三維空間中節(jié)點(diǎn)信息傳播圖

2）以跳數(shù)為依據(jù)求取平均的跳距值與距離信息。通過(guò)步驟1）可知，每個(gè)錨節(jié)點(diǎn)的路由信息表中，均存儲(chǔ)了除去自身以外其他錨節(jié)點(diǎn)的坐標(biāo)值及路由最小跳數(shù)值。以每個(gè)錨節(jié)點(diǎn)記錄的信息為依據(jù)，可計(jì)算整個(gè)監(jiān)測(cè)區(qū)域的平均跳距值為：

式中，HopSizei表示為整個(gè)監(jiān)測(cè)區(qū)域的平均跳距，(xi,yi,zi)和（xj,yj,zj）分別為監(jiān)測(cè)區(qū)域中兩個(gè)不同錨節(jié)點(diǎn)的坐標(biāo)信息值，hij則表示上述兩個(gè)錨節(jié)點(diǎn)間的最小跳數(shù)值。根據(jù)求得的平均跳距值，可計(jì)算區(qū)域中兩個(gè)錨節(jié)點(diǎn)間的估計(jì)距離dij為：

3）區(qū)域內(nèi)未知節(jié)點(diǎn)的坐標(biāo)值計(jì)算。通過(guò)步驟1）-2），可求得任意未知節(jié)點(diǎn)與區(qū)域內(nèi)每個(gè)錨節(jié)點(diǎn)的距離。以此為基礎(chǔ)，并假設(shè)在監(jiān)測(cè)區(qū)域中每個(gè)未知節(jié)點(diǎn)均存在至少4 個(gè)連通的錨節(jié)點(diǎn)，則可采用極大似然估計(jì)法（Maximum Likelihood Estimate,MLE）求得未知節(jié)點(diǎn)的坐標(biāo)信息，具體計(jì)算過(guò)程如下：

其中，(x,y,z)代表的是區(qū)域內(nèi)未知節(jié)點(diǎn)的坐標(biāo)，而(xk,yk,zk)代表的則是區(qū)域內(nèi)與未知節(jié)點(diǎn)連通的第k個(gè)錨節(jié)點(diǎn)坐標(biāo)，且1＜k＜n。將式（3）轉(zhuǎn)換為矩陣形式PX=Q，則有：

上式中，若存在矩陣A和B使得ATA為可逆矩陣時(shí)，則可將區(qū)域內(nèi)未知節(jié)點(diǎn)坐標(biāo)表示為：

1.2 3DDV-Hop定位算法存在的問(wèn)題

由以上分析可知，利用3DDV-Hop 算法定位的重點(diǎn)是跳數(shù)與平均跳距的乘積。通過(guò)該值可獲取傳感器節(jié)點(diǎn)的距離，并在測(cè)出距離后計(jì)算各節(jié)點(diǎn)的位置坐標(biāo)。

計(jì)算跳數(shù)時(shí)，在通信半徑內(nèi)的所有覆蓋節(jié)點(diǎn)均會(huì)記為一跳，由此便會(huì)造成統(tǒng)計(jì)錯(cuò)誤。同時(shí)在多個(gè)通信半徑內(nèi)的節(jié)點(diǎn)通信路徑并非直線(xiàn)，這樣需經(jīng)過(guò)多次跳數(shù)才能完成通信。此外在求解節(jié)點(diǎn)位置時(shí)，通常使用三邊定位法（Trilateral Positioning Method）來(lái)完成。但當(dāng)三個(gè)節(jié)點(diǎn)在一條直線(xiàn)時(shí)，三邊定位法就會(huì)失效。因此，影響3DDV-Hop 精度的主要原因有三個(gè)：跳數(shù)、平均跳距及節(jié)點(diǎn)坐標(biāo)計(jì)算方法。

1.3 算法改進(jìn)

1.3.1 基于雙通信半徑法的最小跳數(shù)修正

傳統(tǒng)的跳數(shù)計(jì)算[11]方式使用單通信半徑法，但該方法的誤差較大。因此為了減小誤差，該文使用雙通信半徑法對(duì)最小跳數(shù)進(jìn)行修正[12]。雙通信半徑算法的示意圖如圖2 所示。

假定節(jié)點(diǎn)數(shù)據(jù)傳輸共有R和0.5R這兩種傳輸半徑，且錨點(diǎn)A分別在傳輸半徑R與0.5R處傳輸信息，由此測(cè)得的數(shù)據(jù)將會(huì)更加精確。從圖中可以看到，節(jié)點(diǎn)1、2 在0.5R半徑內(nèi)，故這兩個(gè)節(jié)點(diǎn)的跳數(shù)均為0.5，而節(jié)點(diǎn)3、4 的跳數(shù)則為1。這使得拓?fù)涓哒鎸?shí)性，也是提高定位精度的前提。

1.3.2 加權(quán)平均跳距改進(jìn)方法

由式（2）可知，使用單一代價(jià)函數(shù)計(jì)算得到的值會(huì)存在一定誤差。因此，該文采用平方代價(jià)函數(shù)對(duì)單一函數(shù)進(jìn)行改進(jìn)。其可表示為：

由偏導(dǎo)數(shù)可求解得到HopSizei的值如下所示：

式（8）-（9）為單個(gè)節(jié)點(diǎn)與其他節(jié)點(diǎn)的平均跳距，且當(dāng)這兩個(gè)數(shù)值間的跳距相差較小時(shí)，就會(huì)引起誤差。因此，可以使用多個(gè)節(jié)點(diǎn)的加權(quán)值對(duì)精度進(jìn)行提升，但節(jié)點(diǎn)過(guò)多會(huì)導(dǎo)致計(jì)算量激增。同時(shí)，若兩個(gè)節(jié)點(diǎn)相距過(guò)遠(yuǎn)，對(duì)最終的結(jié)果影響也較小。所以選擇單個(gè)節(jié)點(diǎn)及與其距離最近三個(gè)節(jié)點(diǎn)的跳距平均值作為加權(quán)值，計(jì)算公式如下：

式中，Ni、Nj、Nk為某錨節(jié)點(diǎn)與其距離最近節(jié)點(diǎn)i、j、k的最小跳數(shù)值。節(jié)點(diǎn)α加權(quán)后的跳距可表示為：

1.3.3 最小最大節(jié)點(diǎn)坐標(biāo)計(jì)算法

在坐標(biāo)求解中，使用最小最大法（Min-Max）[13]對(duì)最終坐標(biāo)進(jìn)行求解。該方法使用求解完成的錨點(diǎn)坐標(biāo)與計(jì)算完畢的跳距值，在空間中構(gòu)建最小與最大區(qū)域限制函數(shù)。再通過(guò)計(jì)算各個(gè)限制函數(shù)所構(gòu)成的限制圓質(zhì)心求得坐標(biāo)值。其在提升精確度的同時(shí)，還可減小了一定的計(jì)算量。Min-Max 算法的構(gòu)造如圖3 所示。

圖3 Min-Max算法構(gòu)造

圖3 中，A、B、C是離位置節(jié)點(diǎn)D最近的三個(gè)錨節(jié)點(diǎn)，且節(jié)點(diǎn)間的距離是已知的。A、B、C的節(jié)點(diǎn)坐標(biāo)為(xp,yp,zp)(p=A,B,C)，則錨點(diǎn)限制區(qū)域如下所示：

式中，下限值的最大與最小值為各區(qū)域的交集，而這些交集所形成的圖形質(zhì)心則為未知錨點(diǎn)的坐標(biāo)值。

1.3.4 改進(jìn)算法流程

該文對(duì)影響3DDV-Hop 定位算法精度的因素進(jìn)行了改進(jìn)[14]，算法的執(zhí)行流程如下：

1）定位節(jié)點(diǎn)初始化。由空間中的定位節(jié)點(diǎn)構(gòu)建定位系統(tǒng)，且初始化的最大通信半徑為R，節(jié)點(diǎn)總數(shù)為P。

2）雙通信半徑傳播。根據(jù)雙通信半徑法設(shè)定R和0.5R的傳播半徑進(jìn)行最小跳數(shù)修正，直至網(wǎng)絡(luò)中錨節(jié)點(diǎn)數(shù)據(jù)傳播完成為止。

3）計(jì)算平均跳距。依據(jù)加權(quán)法（Weighting Method）對(duì)錨點(diǎn)間的平均跳距加以計(jì)算，并選擇與未知節(jié)點(diǎn)距離最近的三個(gè)節(jié)點(diǎn)進(jìn)行加權(quán)。

4）計(jì)算最終坐標(biāo)。使用Min-Max 算法構(gòu)建限制區(qū)域，同時(shí)計(jì)算上下限區(qū)域的質(zhì)心，以得到未知節(jié)點(diǎn)的坐標(biāo)，進(jìn)而完成最終定位。

2 算法測(cè)試

2.1 實(shí)驗(yàn)平臺(tái)

文中使用Matlab[15-16]對(duì)測(cè)繪空間數(shù)據(jù)進(jìn)行生成與仿真。利用部署于測(cè)繪空間內(nèi)部的錨節(jié)點(diǎn)個(gè)數(shù)、通信半徑及未知節(jié)點(diǎn)個(gè)數(shù)三方面進(jìn)行算法性能的對(duì)比。所構(gòu)建的仿真實(shí)驗(yàn)環(huán)境如表1 所示。

表1 實(shí)驗(yàn)環(huán)境

2.2 實(shí)驗(yàn)測(cè)試

文中利用上述三方面的變化值對(duì)算法性能加以測(cè)試。選取了3D-DVHop、3D-WD-DVHop 及IPSODV-Hop 這三種經(jīng)典算法來(lái)與所提方法進(jìn)行對(duì)比。所使用的參數(shù)指標(biāo)則為誤差距離，即測(cè)量值和實(shí)際值之間的歐式距離（Euclidean distance）。默認(rèn)的實(shí)驗(yàn)環(huán)境：200 個(gè)傳感器，20%的錨節(jié)點(diǎn)，80%的未知網(wǎng)絡(luò)節(jié)點(diǎn)，同時(shí)通信半徑為35 m，且做50 次實(shí)驗(yàn)后取平均值[17-18]。

驗(yàn)證通信半徑對(duì)定位精度的影響，取25～60 m之內(nèi)的通信半徑，并測(cè)量定位誤差，所得結(jié)果如圖4所示。

圖4 通信半徑對(duì)定位精度的影響

由圖可知，隨著通信半徑的增大，錨節(jié)點(diǎn)可以覆蓋更多的通信節(jié)點(diǎn)，因此誤差也逐漸降低。此外該算法在對(duì)比算法中具有最低的誤差值，且相較IPSODV-Hop 算法誤差降低了2.1%。

除了通信半徑以外，錨節(jié)點(diǎn)個(gè)數(shù)對(duì)定位誤差也有較大的影響。當(dāng)錨節(jié)點(diǎn)個(gè)數(shù)取10～40 個(gè)時(shí)，各算法的結(jié)果如圖5 所示。

圖5 錨點(diǎn)個(gè)數(shù)對(duì)定位精度的影響

從圖中可看到，在錨節(jié)點(diǎn)數(shù)量較少時(shí)，各算法誤差均較大。而隨著錨節(jié)點(diǎn)數(shù)量的增加，各算法的誤差均有所下降。由于該算法對(duì)跳距與跳數(shù)進(jìn)行了優(yōu)化，因此其定位誤差的平均值比其余三種算法的平均值下降了約6.8%。

此外，未知節(jié)點(diǎn)總數(shù)對(duì)網(wǎng)絡(luò)的連通性也有直接的影響。文中在節(jié)點(diǎn)數(shù)量為125～275 個(gè)之間進(jìn)行了仿真，所得結(jié)果如圖6 所示。

圖6 節(jié)點(diǎn)數(shù)量對(duì)定位精度的影響

由圖6 可知，在節(jié)點(diǎn)數(shù)量較少時(shí)，由于網(wǎng)絡(luò)的連通性較差，所以其定位誤差較高。而隨著節(jié)點(diǎn)個(gè)數(shù)的增加，定位誤差也隨之下降。而該算法通過(guò)增加節(jié)點(diǎn)半徑來(lái)對(duì)節(jié)點(diǎn)數(shù)量的不足加以補(bǔ)償，比其他三種算法的定位誤差平均值降低了約5.4%。

綜上所述，該算法通過(guò)對(duì)最小跳數(shù)、跳距及定位算法進(jìn)行了優(yōu)化，其綜合性能較為理想，定位精度相較對(duì)比算法也有所提升。

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

傳統(tǒng)衛(wèi)星測(cè)繪算法定位精度較差，該文針對(duì)算法存在的三個(gè)缺陷進(jìn)行了改進(jìn)。分別使用雙通信半徑法、加權(quán)平均法和最小最大法對(duì)算法進(jìn)行了優(yōu)化。實(shí)驗(yàn)測(cè)試結(jié)果顯示，所提算法誤差指標(biāo)在對(duì)比算法中均為最優(yōu)，表明該算法可以有效提升衛(wèi)星測(cè)繪的精確度。