基于APIT的無線傳感器網(wǎng)絡(luò)三維定位算法

摘要：根據(jù)經(jīng)典的APIT算法特點，將其擴展到三維空間中實現(xiàn)節(jié)點的定位。針對APIT算法的不足，提出了一種改進的TDAPIT算法，并從節(jié)點定位誤差和定位覆蓋率兩個方面分析算法的性能。在改進的算法中利用了循環(huán)的思想，大大減少了不良節(jié)點的數(shù)量。仿真實驗結(jié)果證明，TDAPIT算法可以較好地應(yīng)用于三維空間定位，而且在定位覆蓋率上比APIT有了明顯提高。

關(guān)鍵詞：無線傳感器；定位；APIT；TDAPlT

引言

通常，無線傳感器網(wǎng)絡(luò)(Wireless Sensor Networks，WSN)信息采集節(jié)點是被隨機放置或是從飛機上隨機拋撒的。因此如何確定節(jié)點的具體位置成為無線傳感器網(wǎng)絡(luò)研究的難點和重點。

WSN的定位主要分對節(jié)點自身的定位和對外部目標(biāo)的跟蹤定位。WSN自身定位方法分為基于測距的方法和非基于測距的方法。基于測距的定位通過測量相鄰節(jié)點之間的絕對距離或方位等來計算未知節(jié)點的位置，需要特定的硬件設(shè)備，定位精度較高。而非基于測距的定位機制無需測距或角度信息，不用直接測量這些信息，僅根據(jù)網(wǎng)絡(luò)的連通性等信息實現(xiàn)節(jié)點的定位，典型的有質(zhì)心算法、DV-Hop算法、凸規(guī)劃算法和APIT算法等。

參考文獻提出了一種IAPIT的定位方法，主要思路是將3邊測量法以及幾何上的由已知兩點在輔助條件下求解兩圓交點的方法融入到APIT算法中，但是算法仍然局限于二維宅間中的定位。參考文獻通過對單跳質(zhì)心算法進行多跳擴展以改善定位比率，并加入場強加權(quán)過程和去中心化過程以提高定位精度。參考文獻提出將所有收集到的來自于同一信標(biāo)節(jié)點的RSSI值做平均，作為未知節(jié)點接收到此固定信標(biāo)節(jié)點的RSSI值，進行定位計算。參考文獻結(jié)合三角形測試原理(PIT)，主要針對信標(biāo)節(jié)點分布不均勻的情況提出了CBPIT算法。參考文獻提出了一種節(jié)點自身的定位方法，能夠通過相對準確的測試來確定節(jié)點所在的區(qū)域，但是沒有考慮未知節(jié)點監(jiān)聽到信標(biāo)節(jié)點數(shù)目較少的情況。

本文針對三維空間的節(jié)點定位提出了改進的TDAPIT算法。

1 算法描述

1．1 術(shù)語定義

①信標(biāo)節(jié)點：已知位置并能協(xié)助未知節(jié)點定位的節(jié)點，也稱錨節(jié)點。

②鄰居節(jié)點：在節(jié)點的通信范圍內(nèi)，并可與這個節(jié)點直接通信的所有節(jié)點。

③未知節(jié)點：不知道自身的位置，需使用信標(biāo)節(jié)點的位置信息并運用一定的算法得到估計位置的節(jié)點，也稱待定位節(jié)點。

④已知節(jié)點：圩始時不知道自身的位置信息，但是經(jīng)過一段時間的定位后，已經(jīng)通過信標(biāo)節(jié)點的位置信息并用一定的算法得到了位置信息的節(jié)點。

⑤不良節(jié)點：定位過程結(jié)束后，仍然不能夠?qū)崿F(xiàn)定位的節(jié)點。

實際上，WSN的節(jié)點定位即未知節(jié)點在信標(biāo)節(jié)點的協(xié)助下轉(zhuǎn)變成已知節(jié)點的過程。在實際定位過程中，由于種種原因，難免會出現(xiàn)不良節(jié)點，應(yīng)當(dāng)盡力減少不良節(jié)點的個數(shù)。

1．2 APIT算法

APIT算法的基本思想是未知節(jié)點任選3個相鄰信標(biāo)節(jié)點，測試是否位于它們所組成的三角形中，使用不同信標(biāo)節(jié)點組合重復(fù)測試，直到窮盡所有組合或達到所需定位精度。最后，計算包含目標(biāo)節(jié)點的所有三角形交集的質(zhì)心位置，并以此作為目標(biāo)節(jié)點位置。

APIT算法理論基礎(chǔ)是PIT測試。如果存在一個方向，并且沿著此方向運動的未知節(jié)點會同時遠離或者是接近三角形的三個頂點，那么此未知節(jié)點在三角形的外部，否則在三角形的內(nèi)部。

在實際測試中，可以用未知節(jié)點和它的鄰居節(jié)點來模擬此運動。若未知節(jié)點的鄰節(jié)點都沒有同時遠離或靠近3個信標(biāo)節(jié)點，那么此未知節(jié)點就在三角形內(nèi)，否則在三角形外。PIT測試時，一般采用信號強度來判斷遠離或者是接近信標(biāo)節(jié)點。

PIT測試誤差分析如下：

①PIT測試中容易出現(xiàn)InToOut和OutToIn錯誤。InToOut錯誤即將三角形內(nèi)部的點誤判為在三角形外面。PIT測試圖像如圖1所示。當(dāng)未知節(jié)點靠近或者正好在三角形的一條邊上時，就容易出現(xiàn)上述的錯誤。

②如果信標(biāo)節(jié)點和未知節(jié)點的鄰居節(jié)點密度過小，對定位結(jié)果的影響很大，抑或使得有些節(jié)點不能被定位，定位覆蓋率較低。

③在網(wǎng)絡(luò)的中間部分和未知節(jié)點相鄰的信標(biāo)節(jié)點可能很多，但是其中任意3個節(jié)點所組成的三角形可能都不包括未知節(jié)點，因此在算法完成后仍不能定位這類節(jié)點。

④在網(wǎng)絡(luò)的邊緣部分，容易造成無法滿足APIT的定位條件，當(dāng)和未知節(jié)點相鄰的信標(biāo)節(jié)點數(shù)目少于3個時，造成未知節(jié)點無法定位。

⑤對重疊區(qū)域的重心計算中，采用的是網(wǎng)格掃描的算法，效率較低，計算精度不高。

⑥算法中，未知節(jié)點不僅要與信標(biāo)節(jié)點交互信息，還要與其他的鄰居節(jié)點進行協(xié)調(diào)信息處理，使得網(wǎng)絡(luò)中節(jié)點的計算量增大，通信開銷也上升了很多。

1．3 基于APIT的三維定位方法

1．3．1 TDAPIT算法原理

信標(biāo)節(jié)點是WSN空間中已經(jīng)知道自身坐標(biāo)位置的固定節(jié)點(如通過GPRS定位等)，空間中的任意一個未知節(jié)點，能夠監(jiān)聽到信標(biāo)節(jié)點的數(shù)目為n，那么從n中任意選取4個點組成一個四面體，共有C4n個四面體；然后，測試該未知節(jié)點是否在這4個信標(biāo)節(jié)點組成的四面體內(nèi)，重復(fù)這種測試，直到監(jiān)聽到所有信標(biāo)節(jié)點的組合或者是達到了要求的精度；最后，計算包含未知節(jié)點的所有四面體的重疊區(qū)域，將重疊區(qū)域的質(zhì)心作為未知節(jié)點的位置。

1．3．2 TDAPIT測試

若存在一個方向，沿著這個方向未知節(jié)點M會同時遠離或接近四面體的四個頂點，則M位于四面體外，否則M位于四面體內(nèi)部。

在隨機部署的傳感器網(wǎng)絡(luò)中，有一些節(jié)點偵聽到的信標(biāo)節(jié)點個數(shù)小于4，則這些節(jié)點不能進行PIT測試；有些節(jié)點盡管接收到的信標(biāo)節(jié)點數(shù)目大于或等于4個，也能進行PIT測試，但是卻仍然無法判斷其位置。在測試中，利用如下方法判斷未知節(jié)點位置：

①通過未知節(jié)點接收到信標(biāo)節(jié)點的RSS值大小來判斷節(jié)點和信標(biāo)節(jié)點之間的距離。

②通過未知節(jié)點的鄰居節(jié)點來模擬未知節(jié)點的移動，即假設(shè)未知節(jié)點移動到它的鄰居節(jié)點。

③通過對未知節(jié)點所有鄰居節(jié)點的模擬來近似地遍歷未知節(jié)點的所有方向。

④為了減少InToOut和OutToIn錯誤，我們可以通過在節(jié)點上設(shè)置相應(yīng)的MAXrss和MINrss閾值來進一步判斷。對于初步判定為在三角形外部的節(jié)點，如果未知節(jié)點接收到的信號強度值大于設(shè)置的閾值，則認為判定錯誤；同樣，對于判定為在三角形內(nèi)部的節(jié)點，如果接收到的信號強度小于設(shè)定的閾值，則認為發(fā)生OutToIn錯誤。