無線傳感網(wǎng)絡(luò)分段線性融合定位算法*

李 鋒，魏楚強(qiáng)

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

0 引言

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

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

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

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

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

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

式中，RSSI(d)為距離源節(jié)點(diǎn)d處接收到的信號(hào)強(qiáng)度，RSSI(d0)為距離源節(jié)點(diǎn)d0處測到的信號(hào)強(qiáng)度值，df為內(nèi)測點(diǎn)與障礙物之間距離，ΣWAF為標(biāo)準(zhǔn)偏差和。

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

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

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

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

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

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

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

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

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

3 分段線性融合定位算法對移動(dòng)節(jié)點(diǎn)的定位

3.1 定位過程

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

式 中，k-1為k時(shí) 刻 的 上 一 時(shí) 刻，(xk-1，yk-1，zk-1)為目的節(jié)點(diǎn)在k-1時(shí)刻的坐標(biāo)。

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

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

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

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

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

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

3.2 算法流程圖

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

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

3.3 定位誤差分析

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

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

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

4 仿真測試

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

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

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

4.2 移動(dòng)節(jié)點(diǎn)定位偏差測試

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

圖5 移動(dòng)節(jié)點(diǎn)定位偏差圖

表1 移動(dòng)節(jié)點(diǎn)定位偏差表 (m)

4.3 移動(dòng)節(jié)點(diǎn)軌跡模擬

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

圖6 移動(dòng)節(jié)點(diǎn)軌跡模擬圖

5 結(jié)論

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