適應山頭地形的無線傳感器網絡三維定位機制*

胡中棟，謝金偉

(江西理工大學 信息工程學院，江西 贛州341000)

0 引 言

無線傳感器網絡(wireless sensor networks，WSNs)在智能生活、環境監測、軍事偵察、災難預防和生物統計等領域都有著廣泛使用。因帶有GPS 功能的無線傳感器的價格較高，所以，部署的傳感器有較大部分無法確定自己的位置，而無法確定位置的傳感器在大部分情況下不具有實際意義。隨著無線傳感器的廣泛使用，無線傳感器的定位便成為了研究的熱點。起初主要研究二維的無線傳感器的定位，文獻［1］總結了一些典型的二維定位算法。隨著應用的要求越來越高，無線傳感器二維定位已無法滿足生產的需要，三維定位就成為了研究的熱點。有許多學者都提出了三維無線傳感器網絡定位算法，其中有些是二維定位的延伸，有些是專為三維定位而設計的算法。近似三角形內點測試(APIT)算法是二維定位中常用的算法，在文獻［2］中APIT 算法被擴展到了三維;Constrained 3D［3］算法是利用三角計算的方法，通過自身與錨節點之間的距離來推算自身的距離;戴桂蘭等人［4］將最小二乘法引入了球面三維定位中;江禹生等人［5］引入了位置估算偏差值，利用加權質心算法進行位置估算。

適應山頭地形的無線傳感器網絡三維定位算法首先用三維DV-Hop 定位算法求出未知節點的初始位置P，然后，將P 點投影到山頭地形表面上，用該投影點代替原計算結果，較好地修正了計算結果，提高了無線傳感器網絡在山頭地形中的定位精度。

1 三維DV－Hop 定位算法

1.1 DV-Hop 算法

DV-Hop 算法是由Niculescu D 等人提出的，此算法利用了距離矢量路由原理來具體實現［6，7］。算法的具體步驟為:

1)計算無線傳感網絡中所有節點之間的最小跳數。

2)錨節點通過自身的位置和其與其他錨節點之間的位置計算出平均每跳距離。

3)未知節點通過到錨節點之間的最小跳數估算自己到所有錨節點的距離。

4)通過最小二乘法(極大似然估計法)或四邊測量法計算自身坐標［8］。

最小二乘法求解方程組具體步驟如下［9］:

1)設未知節點的坐標為(x，y，z)，由三維DV-Hop 算法可得到未知節點到n(n≥4)個錨節點的距離為d1，d2，…dn，且已知對應錨節點的坐標為(x1，y1，z1)，(x2，y2，z2)，…，(xn，yn，zn)。

2)由已知條件可以得到矛盾方程組［9］

其中

3)若矛盾方程組有解，則可得

龍套，也叫文堂，是傳統戲曲中扮演兵卒、夫役等群眾角色的統稱；由于所穿都是各色龍套衣飾而得名。現在大家將其引申為各類組織、團體或班子中的邊緣角色或非主要角色。與龍套對應的是主角，主角光彩奪目，龍套就顯得黯然失色。

1.2 性能評價

用相對定位誤差來判斷定位算法的優劣，具體計算方法為［10］:

若某個未知節點的估算坐標為(xi，yi，zi)，實際坐標為(ai，bi，ci)，則兩個坐標的差距Δdi可表示為

相對定位誤差不僅與估算坐標與實際坐標之間的距離有關，還和無線傳感器節點的通信半徑R 有關，則無線傳感器網絡中n 個未知節點的平均定位誤差Δ 可表示為

2 適應山頭地形的三維定位算法

為了方便投影操作，截取部分球體模擬山頭，如圖1 所示。H 表示山體的高度，可以看到，不同的H 值可以模擬不同坡度的山頭。

圖1 山頭模型Fig 1 Hilltop model

投影方法如圖2 所示，當所估算的位置節點的坐標位置在山體內部，如圖2 中的A 點所示，過圓心O 點和A 點作直線 與山體交于B 點，B 點即為效正后的未知節點的坐標點。若所估算的節點坐標位置在山體外，如圖2 中C 點所示，作直線L2，則可得到投影效正后的未知節點的坐標點為圖中的D 點。

圖2 投影方法Fig 2 Projection method

在如圖2 所示的坐標系中，設圓的半徑為R，圓心在坐標原點。設用三維DV-Hop 算法所求未知節點的坐標為X=(a，b，c)，則可以得到過坐標原點和X 點的直線L。由直線L 與圓方程聯立，且在z≥0 的條件下可求出唯一投影點X'，X'即為投影效正后的未知節點坐標，具體方程式如下:

以坐標原點為起點且過X 點的射線方程式為

半圓球的方程式為

3 仿真實驗

采用Matlap 對本文設計的適應地形的投影算法進行了仿真實驗。為了驗證算法的有效性，實驗分為山頭高度不同、信標節點比例不同與節點總數不同三種情況進行了對比實驗。實驗中圓半徑R 設為50 m，信標節點的通信半徑設置為20 m，其它參數根據不同的情況進行設置，節點隨機分布如圖3 所示。

圖3 傳感器節點隨機分布圖Fig 3 Randomly distributed map of sensor nodes

1)不同山頭高度的實驗

實驗中的無線傳感器總數為200，信標節點數為20，占總節點數的10%。圖2 中的H 分別設置為20，25，30，35，40，45，50 m 的情況下進行實驗，對每種不同的山頭高度H均進行100 次實驗，每次實驗的傳感器節點都是隨機分布的，實驗結果如圖4 所示。

圖4 不同山頭高度的平均定位誤差Fig 4 Average localization error with different hilltop height

從圖4 可以看到經過投影修正處理的定位精度有明顯的提高。在不同的山頭高度的情況下，典型的三維DV-Hop定位誤差為60%左右，在實際應用中有較大的偏差，而經過投影修正后的定位誤差僅為30%左右，較大幅度提高了節點定位精度。

2)信標節點比例不同的實驗

實驗中H 的值設定為35 m，傳感器總節點數設置為200，信標節點的比例分別為5%，10%，15%，20%，25%，30%和35%進行對比實驗，對每種不同比例分別進行100 次模擬實驗，每次實驗的傳感器節點分布都是隨機的，實驗結果如圖5 所示。

由圖5 可知，不論是典型的三維DV-Hop 定位算法，還是投影改進后的定位算法，隨著錨節點比例的增加，定位精度也相應提高，當錨節點比例增加到15%之后，精度便不再明顯提高，這可以為傳感器節點的合理部署提供參考。而經過投影處理的定位誤差明顯減小，當錨節點比例較合理時，定位誤差僅為30%左右。

3)傳感器節點數不同的實驗

圖5 不同錨節點比例的平均定位誤差Fig 5 Average localization error with different anchor node proportion

實驗中，H 的值設定為35 m，信標節點的比例保持為10%不變，在傳感器節點總數分別為140，150，160，170，180，190，200 的情況下進行對比實驗，對每種不同傳感器節點總數分別進行100 次實驗，每次實驗時傳感器節點分布都是隨機的，實驗結果如圖6 所示。

圖6 不同節點總數的平均定位誤差Fig 6 Average localization error with different node numbers

通過實驗可知，典型的三維DV-Hop 定位算法和經過投影處理的定位算法都是總節點數越多，定位誤差越小。典型的三維DV-Hop 定位算法的定位誤差在65%左右，而經過投影處理的定位算法的定位誤差僅為35%左右，當節點數為200 時，定位誤差已經小于30%。

4 結 論

在經典的三維DV-Hop 的定位算法基礎上，應用地形的特點，對經典算法所求的結果進行投影優化，有效地利用了外部環境的特點。通過多角度的仿真對比實驗證明:在不增加任何其他硬件設備的前提下，有效降低了定位誤差，提高了無線傳感器網絡非測距定位算法精度。本文所用的實例雖然有一定的局限性，但較好地體現了投影修正的思想，為下一步實際山區地形的無線傳感器節點定位研究奠定了基礎。

［1］ 王福豹，史 龍，任豐原.無線傳感器網絡中的自身定位系統和算法［J］.軟件學報，2005，16(5):857-868.

［2］ 劉玉恒，蒲菊華，赫 陽.無線傳感器網絡三維自身定位方法［J］.北京航天航空大學學報，2008，34(6):647-651.

［3］ Liang J L，Shao J，Xu Y，et al.Sensor network localization in constrained 3D spaces［C］∥Proc of IEEE International Conference on Mechatronics and Automation，Luoyang:IEEE，2006:49-54.