基于多維度精確定位的測繪數據處理技術研究

劉鋒

（西安鐵路職業技術學院，陜西 西安 710026）

傳統衛星測繪定位方法的精度較差，當地形結構相對復雜時，其信號便會被遮擋，從而導致衛星無法定位。因此，基于衛星定位功能部署多個無線傳感器網絡（Wireless Sensor Networks,WSN）[1-3]是改善測繪衛星信號被遮擋的方式之一。目前無線傳感器的定位方法可分為兩種，第一種方法需要計算各無線傳感器間的實際距離，該算法較為準確，但普適性較差，且需要極高的部署成本，故不適合用作大范圍區域的無線定位。第二種方法無需計算傳感器距離，僅通過無線拓撲的信息傳遞關系便可對位置進行估算，該方法雖然準確度略遜于第一種，但成本更低且總體上也能取得良好的效果，其代表性算法為3DDV-Hop[4-5]。

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

該文分析了3DDV-Hop 存在的問題，并從最小跳數、平均跳距及定位坐標的確定方法三方面對算法進行了優化，并在實驗部分取得了較優的效果。

1 基于改進3DDV-Hop 的精確定位算法

1.1 3DDV-Hop定位算法

近年來無線傳感網絡技術發展迅速，定位空間的維度已從二維擴展至三維。而3DDV-Hop 算法作為立體空間中的目標定位方法，受到了廣泛關注。傳統3DDV-Hop 算法的實現步驟如下：

1）三維空間中的不同節點間，以信息傳播的方式確定跳數值。錨節點會發送包含自身標識、跳數值與坐標值的信息包至三維監測區域中的相鄰節點，而該節點則會對信息包中的信息進行存儲，此后再繼續轉發給下一相鄰節點。以此類推，在監測的三維區域空間中不同節點間以洪泛的形式進行傳播，直至整個監測區域內的所有節點均完成信息的傳播與存儲為止。具體的節點信息傳播圖如圖1 所示。其中白色代表未知節點，黑色則代表錨節點。

圖1 三維空間中節點信息傳播圖

2）以跳數為依據求取平均的跳距值與距離信息。通過步驟1）可知，每個錨節點的路由信息表中，均存儲了除去自身以外其他錨節點的坐標值及路由最小跳數值。以每個錨節點記錄的信息為依據，可計算整個監測區域的平均跳距值為：

式中，HopSizei表示為整個監測區域的平均跳距，(xi,yi,zi)和（xj,yj,zj）分別為監測區域中兩個不同錨節點的坐標信息值，hij則表示上述兩個錨節點間的最小跳數值。根據求得的平均跳距值，可計算區域中兩個錨節點間的估計距離dij為：

3）區域內未知節點的坐標值計算。通過步驟1）-2），可求得任意未知節點與區域內每個錨節點的距離。以此為基礎，并假設在監測區域中每個未知節點均存在至少4 個連通的錨節點，則可采用極大似然估計法（Maximum Likelihood Estimate,MLE）求得未知節點的坐標信息，具體計算過程如下：

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

上式中，若存在矩陣A和B使得ATA為可逆矩陣時，則可將區域內未知節點坐標表示為：

1.2 3DDV-Hop定位算法存在的問題

由以上分析可知，利用3DDV-Hop 算法定位的重點是跳數與平均跳距的乘積。通過該值可獲取傳感器節點的距離，并在測出距離后計算各節點的位置坐標。

計算跳數時，在通信半徑內的所有覆蓋節點均會記為一跳，由此便會造成統計錯誤。同時在多個通信半徑內的節點通信路徑并非直線，這樣需經過多次跳數才能完成通信。此外在求解節點位置時，通常使用三邊定位法（Trilateral Positioning Method）來完成。但當三個節點在一條直線時，三邊定位法就會失效。因此，影響3DDV-Hop 精度的主要原因有三個：跳數、平均跳距及節點坐標計算方法。

1.3 算法改進

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

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

假定節點數據傳輸共有R和0.5R這兩種傳輸半徑，且錨點A分別在傳輸半徑R與0.5R處傳輸信息，由此測得的數據將會更加精確。從圖中可以看到，節點1、2 在0.5R半徑內，故這兩個節點的跳數均為0.5，而節點3、4 的跳數則為1。這使得拓撲更具真實性，也是提高定位精度的前提。

1.3.2 加權平均跳距改進方法

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

由偏導數可求解得到HopSizei的值如下所示：

式（8）-（9）為單個節點與其他節點的平均跳距，且當這兩個數值間的跳距相差較小時，就會引起誤差。因此，可以使用多個節點的加權值對精度進行提升，但節點過多會導致計算量激增。同時，若兩個節點相距過遠，對最終的結果影響也較小。所以選擇單個節點及與其距離最近三個節點的跳距平均值作為加權值，計算公式如下：

式中，Ni、Nj、Nk為某錨節點與其距離最近節點i、j、k的最小跳數值。節點α加權后的跳距可表示為：

1.3.3 最小最大節點坐標計算法

在坐標求解中，使用最小最大法（Min-Max）[13]對最終坐標進行求解。該方法使用求解完成的錨點坐標與計算完畢的跳距值，在空間中構建最小與最大區域限制函數。再通過計算各個限制函數所構成的限制圓質心求得坐標值。其在提升精確度的同時，還可減小了一定的計算量。Min-Max 算法的構造如圖3 所示。

圖3 Min-Max算法構造

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

式中，下限值的最大與最小值為各區域的交集，而這些交集所形成的圖形質心則為未知錨點的坐標值。

1.3.4 改進算法流程

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

1）定位節點初始化。由空間中的定位節點構建定位系統，且初始化的最大通信半徑為R，節點總數為P。

2）雙通信半徑傳播。根據雙通信半徑法設定R和0.5R的傳播半徑進行最小跳數修正，直至網絡中錨節點數據傳播完成為止。

3）計算平均跳距。依據加權法（Weighting Method）對錨點間的平均跳距加以計算，并選擇與未知節點距離最近的三個節點進行加權。

4）計算最終坐標。使用Min-Max 算法構建限制區域，同時計算上下限區域的質心，以得到未知節點的坐標，進而完成最終定位。

2 算法測試

2.1 實驗平臺

文中使用Matlab[15-16]對測繪空間數據進行生成與仿真。利用部署于測繪空間內部的錨節點個數、通信半徑及未知節點個數三方面進行算法性能的對比。所構建的仿真實驗環境如表1 所示。

表1 實驗環境

2.2 實驗測試

文中利用上述三方面的變化值對算法性能加以測試。選取了3D-DVHop、3D-WD-DVHop 及IPSODV-Hop 這三種經典算法來與所提方法進行對比。所使用的參數指標則為誤差距離，即測量值和實際值之間的歐式距離（Euclidean distance）。默認的實驗環境：200 個傳感器，20%的錨節點，80%的未知網絡節點，同時通信半徑為35 m，且做50 次實驗后取平均值[17-18]。

驗證通信半徑對定位精度的影響，取25～60 m之內的通信半徑，并測量定位誤差，所得結果如圖4所示。

圖4 通信半徑對定位精度的影響

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

除了通信半徑以外，錨節點個數對定位誤差也有較大的影響。當錨節點個數取10～40 個時，各算法的結果如圖5 所示。

圖5 錨點個數對定位精度的影響

從圖中可看到，在錨節點數量較少時，各算法誤差均較大。而隨著錨節點數量的增加，各算法的誤差均有所下降。由于該算法對跳距與跳數進行了優化，因此其定位誤差的平均值比其余三種算法的平均值下降了約6.8%。

此外，未知節點總數對網絡的連通性也有直接的影響。文中在節點數量為125～275 個之間進行了仿真，所得結果如圖6 所示。

圖6 節點數量對定位精度的影響

由圖6 可知，在節點數量較少時，由于網絡的連通性較差，所以其定位誤差較高。而隨著節點個數的增加，定位誤差也隨之下降。而該算法通過增加節點半徑來對節點數量的不足加以補償，比其他三種算法的定位誤差平均值降低了約5.4%。

綜上所述，該算法通過對最小跳數、跳距及定位算法進行了優化，其綜合性能較為理想，定位精度相較對比算法也有所提升。

3 結束語

傳統衛星測繪算法定位精度較差，該文針對算法存在的三個缺陷進行了改進。分別使用雙通信半徑法、加權平均法和最小最大法對算法進行了優化。實驗測試結果顯示，所提算法誤差指標在對比算法中均為最優，表明該算法可以有效提升衛星測繪的精確度。