無線傳感網絡分段線性融合定位算法*

李 鋒，魏楚強

(廣東交通職業技術學院，廣東 廣州510650)

0 引言

無線傳感網絡是一種由大量傳感節點構成的無線多跳式自組織網絡。由于節點采集到的環境信息通常與其自身位置相關，如何實現對節點的精確定位是其首要解決的關鍵問題[1]。在三維立體空間中，要實現對未知節點定位，至少需要三個立體空間錨節點坐標[2]。基于此原理，業界提出三維跳段距離向量3D-DVHop算法、基于接收信號強度的RSSI-3D算法、近似球形內點測試APIS-3D算法和近似三角形內點測試APIT-3D算法等。在以上經典算法中，3D-DVHop算法定位原理與二維平面類似，會因相鄰節點接力的“繞彎”現象[3]導致平均跳距誤差較大，定位精度較低；RSSI-3D算法將未知節點采集到的指紋特征與數據庫進行最近匹配以估算節點坐標，但RSSI接收信號強度易受環境信號波動和多徑衰減影響[4]，定位結果隨機性較大；APIS-3D算法利用節點自身存儲本地位置信息，定位精度對節點密度依賴過大[5]，當節點分布不均時定位精度不高；APIT-3D算法通過計算四面三棱椎體重疊區域質心來計算節點坐標，算法成熟，平均定位精度較高，但容易陷入“In-To-Out”和“Out-To-In”[6]兩類內測點測試錯誤，導致邊緣節點定位偏差較大[7]。根據APIT算法，目的節點需要判斷是否處于其附近任意三個錨節點所組成的三角形中，“In-To-Out”和“Out-To-In”錯誤就是目的節點對所處三角形區域的兩種誤判形式。

由于三維空間定位比傳統二維平面復雜很多，算法目前尚屬改善階段[8]，無法在移動環境中對節點進行精確定位[9]。然而，傳感節點會隨機部署在某一三維區域，并會隨周圍環境變化而變換位置。如何在現有二維平面定位算法基礎上，延伸至三維空間，并對其內移動節點精確定位，是目前無線傳感網絡研究的難點。

有鑒于此，本文提出一種基于APIT-3D的移動節點定位模型和算法，綜合3D-DVHop跳段距離和RSSI測距技術，在計算內測點與最近椎面距離基礎上，利用與椎體成形體積判斷內測點位置，有效避免“In-To-Out”和“Out-To-In”兩類錯誤的產生。在確定椎體重疊區域后，通過最小二乘法結合空間分段線性融合方式計算節點位置，判斷運動趨勢，描述運動軌跡，實現對移動三維節點的精確定位。

1 分段線性融合定位算法對內測點的判斷

在APIT算法中，當鄰近節點較疏或不能組成三角形時會導致內測點判斷錯誤，即“In-To-Out”與“Out-To-In”兩種錯誤類 型[10-11]。APIT-3D算 法將傳統的二維平面延伸至三維立體空間，同理也會導致上述錯誤。本文分段線性融合定位算法通過內測點與椎體成形體積判斷其位置，從而避免上述兩種錯誤類型的產生，解決方案和步驟如下：

引入RSSI信號衰減模型計算內測點N與四面椎體ABCD之間距離。RSSI衰減模型為：

式中，RSSI(d)為距離源節點d處接收到的信號強度，RSSI(d0)為距離源節點d0處測到的信號強度值，df為內測點與障礙物之間距離，ΣWAF為標準偏差和。

為減少相鄰節點因接力“繞彎”導致的誤差，采用平均跳距增益η對節點通信距離進行修正，η為平均跳距和節點平均通信半徑之比：

利用跳數增益修正內測點與四面椎體頂點之間的參考跳距：

則椎體頂點錨節點i與內測點N之間參考跳距為：

設hopsij為錨節點i到j之間的跳數，則通過未知 節 點N測 得 從 錨 節 點A，B，C，D收 到 的RSSI值，轉換為參考跳距為：

在計算出內測點N與四面椎體頂點錨節點參考距離基礎上，通過平面夾角三角函數計算N與椎體最近平面的最短距離為：

利用內測點與椎體成形體積判斷其位置，見圖1所示。若內測點N在四面椎體ABCD內，則其與椎體四面組成的體積與四面椎體ABCD體積相同；若N在四面椎體外，其與椎體四面組成的體積必定大于四面椎體ABCD體積。因此，判斷內測點N是否在椎體內部的問題，可以轉換為求以ΔACD為底，BH和BN為高的多面體體積上。當BH≤BN時，內測點N在四面椎體內部，反之則在椎體外部，從而避免APIT-3D算法中內測點誤判現象。

2 靜止節點定位方式

為實現無線傳感網絡對目的靜態節點的定位，內測點判斷完成后，通過計算重疊區域質心獲得目的節點位置。設鄰居節點數量為n，依次與未知節點組成四面椎體，共有種組合。判斷所有組合中內測點與四面椎體的位置關系，確定內測點在椎體內部的所有三棱椎體重疊區域，利用網格掃描計算區域質心，如圖2(a)所示，則未知節點坐標為：

其 中，X，Y，Z分 別 為 目 的 節 點 在x軸，y軸 和z軸坐標，xa，xb，xc，xd分別為有效三棱錐的四個錨節點的x軸 坐 標，ya，yb，yc，yd分 別 為 有 效 三 棱 錐 的 四 個錨節點的y軸坐標，za，zb，zc，zd分別為有效三棱錐的四個錨節點的z軸坐標，RSSIa，RSSIb，RSSIc，RSSId分別為目的節點接收到的錨節點信號強度。

3 分段線性融合定位算法對移動節點的定位

3.1 定位過程

受環境影響，無線傳感節點位置處于不斷變化中[12-13]。在確定重疊區域和節點位置后，分段線性融合定位算法利用最小二乘法結合空間分段線性融合方式判斷節點運動趨勢，即將節點曲線運動看成是多個分段直線運動的疊加，從而描述運動軌跡，如圖2(b)所示。設k時刻未知節點(xk，yk，zk)所在的第一段空間直線標準方程為：

式 中，k-1為k時 刻 的 上 一 時 刻，(xk-1，yk-1，zk-1)為目的節點在k-1時刻的坐標。

空間直線在XZ平面投影方程為：

為達到差值最小，將a、b、c、d取值為方程系數，滿足關系：

根據式(10)和式(11)，有：

其 中，A=[a b]′，X=[x1，x2，…，xm]′，B=[c d]′，Y=[y1，y2，…，ym]′。

求解m組數據點集方程組，得到融合直線參數a、b、c、d值[14]。

同樣原理，在k+1，k+2，…，k+n時刻對目的節點測得的三維坐標分別為(xk+1，yk+1，zk+1)，(xk+2，yk+2，zk+2)，…，(xk+n，yk+n，zk+n)，分段線性融合定位算法在三維空間對直線融合并預測節點移動方向和速度，以此更新融合直線參數a、b、c、d值，從而確定曲線方程。

3.2 算法流程圖

本文提出的分段線性融合定位算法，通過窮盡各目的節點與鄰居節點組合形成的四面椎體，基于測距算法計算目的節點與椎體之間距離，利用與椎體成形體積判斷內測點位置，將底高大于距離的三棱錐作為有效三棱錐，計算其質心坐標。最后，在確定椎體重疊區域后，通過最小二乘法結合空間分段線性融合方式計算節點位置，得到所述目的節點運動軌跡，整個流程如圖3所示。

圖3 分段線性融合定位算法流程圖

3.3 定位誤差分析

假設三維空間中，目的節點N距網絡錨節點i、n實際距離分別為估算距離分別為di和dn，則：

在式(15)中，將n和n-1分別帶入參數n中，求得第n和第n-1項表達式，并計算n項-(n-1)項：

則未知節點定位誤差為：

4 仿真測試

4.1 靜態節點定位偏差測試

將錨節點隨機部署在l00×l00×100三維立體空間內，最大錨節點上限數量為100，節點通信半徑為20，為讓測試環境更貼近實際工程，隨機產生DOI信號擾動系數[0，0.65]，利用MATLAB7.0軟件對算法仿真比較，如圖4所示。從圖中可以看出，四種算法定位誤差伴隨錨節點密度增加而減少。由于節點非均勻分布，3D-DVHop在計算平均跳距時因節點“繞彎”路徑復雜，定位偏差最大；RSSI-3D易受電磁環境和信號波動影響，曲線擾動明顯，若增大DOI信號擾動系數則會進一步加大定位誤差，在復雜電磁環境影響下尤為明顯；而本文提出的分段線性融合定位算法能有效避免APIT-3D導致的內測點測試錯誤現象，根據式(16)、式(17)計算平均定位偏差為1.76%，算法優勢明顯。

圖4 靜態節點定位偏差圖

4.2 移動節點定位偏差測試

由于其余三種算法不能在三維環境下對移動節點定位，文章只對本文分段線性融合定位算法進行測試，結果如圖5。未知節點數量為100，在區間[0，5]隨機初始化節點移動速率，根據式(16)，節點在百分之25th，50th和75th定位偏差值分別是1.81 m，2.45 m和3.32 m，平均偏差為2.26%，如表1所示。

圖5 移動節點定位偏差圖

表1 移動節點定位偏差表 (m)

4.3 移動節點軌跡模擬

錨節點數量為100，引入虛擬力場在x、y、z方向隨機賦予未知節點牽引力度，時間間隔k=1 s，分段直線運動融合后曲線軌跡如圖6所示。

圖6 移動節點軌跡模擬圖

5 結論

本文提出一種基于APIT-3D的移動節點定位模型和算法，解決無線傳感網絡中邊緣節點定位精度不高的問題，并能判斷運動趨勢，描繪運動軌跡，為三維環境下節點定位提供算法借鑒和創新。由于多個信號源電磁波在傳播時會產生反射、繞射和散射現象，影響定位精度和跟蹤準確率，下一步工作將著眼于在復雜電磁環境下實現對目的節點的精確定位。