李 鋒，魏楚強

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

0 引言

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

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

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

1 分段線性融合定位算法對內(nèi)測點的判斷

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

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

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

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

利用跳數(shù)增益修正內(nèi)測點與四面椎體頂點之間的參考跳距：

則椎體頂點錨節(jié)點i與內(nèi)測點N之間參考跳距為：

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

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

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

2 靜止節(jié)點定位方式

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

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

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

3.1 定位過程

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

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

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

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

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

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

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

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

3.2 算法流程圖

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

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

3.3 定位誤差分析

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

在式(15)中，將n和n-1分別帶入?yún)?shù)n中，求得第n和第n-1項表達式，并計算n項-(n-1)項：

則未知節(jié)點定位誤差為：

4 仿真測試

4.1 靜態(tài)節(jié)點定位偏差測試

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

圖4 靜態(tài)節(jié)點定位偏差圖

4.2 移動節(jié)點定位偏差測試

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

圖5 移動節(jié)點定位偏差圖

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

4.3 移動節(jié)點軌跡模擬

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

圖6 移動節(jié)點軌跡模擬圖

5 結(jié)論

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