基于APIT算法的三維定位方法解析

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

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

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

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

1 算法描述

1．1 術(shù)語定義

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

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

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

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

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

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

1．2 APIT算法

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

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

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

PIT測(cè)試誤差分析如下：

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

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

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

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

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

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

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

1．3．1 TDAPIT算法原理

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

1．3．2 TDAPIT測(cè)試

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

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

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

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

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

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

1．3．3 TDAPIT算法流程

TDAPIT算法流程步驟如下：

①節(jié)點(diǎn)部署完成后，網(wǎng)絡(luò)初始化配置。信標(biāo)節(jié)點(diǎn)向網(wǎng)絡(luò)廣播消息（消息應(yīng)該包含信標(biāo)節(jié)點(diǎn)的ID、位置坐標(biāo)等信息），而未知節(jié)點(diǎn)監(jiān)聽信標(biāo)節(jié)點(diǎn)的消息。此階段未知節(jié)點(diǎn)應(yīng)隨時(shí)更新接收到的信息，以防止岡網(wǎng)絡(luò)的拓?fù)渥兓斐傻恼`差影響。

②設(shè)未知節(jié)點(diǎn)M監(jiān)聽到的信標(biāo)節(jié)點(diǎn)數(shù)目為n（n=0，1，2，3，4，5，6…）。信標(biāo)節(jié)點(diǎn)的坐標(biāo)為A1，A2，A3，A4，…，An，未知節(jié)點(diǎn)將監(jiān)聽到的信標(biāo)節(jié)點(diǎn)的坐標(biāo)存入數(shù)組，如果n小于5則繼續(xù)下一步，否則轉(zhuǎn)向步驟④；

③當(dāng)n=4、3或2時(shí)，即未知節(jié)點(diǎn)只能監(jiān)聽到4、3或2個(gè)信標(biāo)節(jié)點(diǎn)。以未知節(jié)點(diǎn)所能監(jiān)聽到的信標(biāo)節(jié)點(diǎn)為圓心，以通信距離為半徑分別作球，兩球分別相交，分別求出4個(gè)球體、3個(gè)球體、2個(gè)球體重疊區(qū)域的質(zhì)心作為未知節(jié)點(diǎn)的坐標(biāo)。

當(dāng)n=1或0時(shí)，即未知節(jié)點(diǎn)只能監(jiān)聽到1或0個(gè)信標(biāo)節(jié)點(diǎn)。此時(shí)，未知節(jié)點(diǎn)等待一段時(shí)間t（這里t應(yīng)設(shè)置為略小于定位周期）后，向其所有鄰居節(jié)點(diǎn)廣播消息，請(qǐng)求獲知鄰居節(jié)點(diǎn)的坐標(biāo)信息。若沒有鄰居節(jié)點(diǎn)返回消息，那么重復(fù)執(zhí)行此步驟；若有鄰居節(jié)點(diǎn)返回消息但鄰居節(jié)點(diǎn)尚未定位，則信標(biāo)節(jié)點(diǎn)繼續(xù)等待一小段隨機(jī)的時(shí)間后，重復(fù)請(qǐng)求消息；若有鄰居節(jié)點(diǎn)返回消息并且鄰居節(jié)點(diǎn)已經(jīng)定位完畢，此時(shí)鄰居節(jié)點(diǎn)成為已知節(jié)點(diǎn)，則未知節(jié)點(diǎn)把已知節(jié)點(diǎn)當(dāng)成信標(biāo)節(jié)點(diǎn)，重復(fù)執(zhí)行步驟①。

④從n個(gè)信標(biāo)節(jié)點(diǎn)中任取4個(gè)節(jié)點(diǎn)組成i（i=1，2，3，4，…，C4n）個(gè)四面體，得到包含未知節(jié)點(diǎn)的所有四面體，根據(jù)四面體相交后的重疊區(qū)域計(jì)算此重疊區(qū)域的質(zhì)心坐標(biāo)作為未知節(jié)點(diǎn)的坐標(biāo)。

1．3．4 算法分析

信標(biāo)節(jié)點(diǎn)廣播消息時(shí)，采用洪泛的方法，使得通信距離內(nèi)的未知節(jié)點(diǎn)都可以監(jiān)聽到消息，而且未知節(jié)點(diǎn)只負(fù)責(zé)監(jiān)聽消息，并不需要和相鄰節(jié)點(diǎn)進(jìn)行消息交換。這樣就大大減少了網(wǎng)絡(luò)中未知節(jié)點(diǎn)的通信量，增加了網(wǎng)絡(luò)生命周期。但是為了使得未知節(jié)點(diǎn)能夠監(jiān)聽到更多的信標(biāo)節(jié)點(diǎn)，我們?cè)O(shè)定能量較多的信標(biāo)節(jié)點(diǎn)來廣播兩次消息。第一次廣播消息時(shí)同時(shí)監(jiān)聽周圍的信標(biāo)節(jié)點(diǎn)的廣播，將監(jiān)聽到的其他信標(biāo)節(jié)點(diǎn)的消息記錄下來。第二次廣播時(shí)，將所知道的所有的信標(biāo)節(jié)點(diǎn)的信息都廣播出去，此時(shí)監(jiān)聽的節(jié)點(diǎn)將接收到的消息和第一次接收的消息對(duì)比，若發(fā)現(xiàn)有新的信標(biāo)節(jié)點(diǎn)則及時(shí)更新信息。

對(duì)于未知節(jié)點(diǎn)監(jiān)聽到的信標(biāo)節(jié)點(diǎn)，不能構(gòu)成四面體相交的，利用球體重合區(qū)域的質(zhì)心作為未知節(jié)點(diǎn)的坐標(biāo)。如果未知節(jié)點(diǎn)監(jiān)聽到的信標(biāo)節(jié)點(diǎn)數(shù)目較少，可以利用已經(jīng)定位完畢的節(jié)點(diǎn)來對(duì)未知節(jié)點(diǎn)進(jìn)行定位。在求解球體重合區(qū)域的質(zhì)心時(shí)，可以利用網(wǎng)格掃面算法，計(jì)算量較大、誤差較??；也可以利用四面體質(zhì)心掃面算法，計(jì)算量較小但是誤差較大，根據(jù)實(shí)際情況予以選擇。

1．4 算法流程

整個(gè)算法的流程如圖2所示。

2 實(shí)驗(yàn)仿真與評(píng)估

本文中采用的仿真軟件是Visual C++與Matlab7．5，選取的實(shí)驗(yàn)參數(shù)是定位覆蓋率和定位誤差。仿真實(shí)驗(yàn)中，200個(gè)節(jié)點(diǎn)是隨機(jī)部署在邊長(zhǎng)為80 m的正方體監(jiān)測(cè)區(qū)域內(nèi)，信標(biāo)節(jié)點(diǎn)和未知節(jié)點(diǎn)的通信半徑都是一樣的。為了減少隨機(jī)分布和偶然因素帶來的影響，仿真的結(jié)果是在相同的參數(shù)下仿真50次的平均值。通過比較二維空間中的APIT和文中提出的三維TDAPIT算法在不同的信標(biāo)節(jié)點(diǎn)比例的情況下的定位覆蓋率和定位誤差，最后來分析擴(kuò)展后算法的優(yōu)劣。

2．1 定位覆蓋率

定位覆蓋率隨信標(biāo)節(jié)點(diǎn)比例變化圖如圖3所示。在信標(biāo)節(jié)點(diǎn)比例為5％時(shí)，APIT定位覆蓋率約為10％，而TDAPIT約為30％，這說明相對(duì)于二維空間中的APIT定位，TDAPIT定位在三維空間中的定位覆蓋率在信標(biāo)節(jié)點(diǎn)比例較小時(shí)，仍能發(fā)揮相當(dāng)?shù)男в谩ｋS著信標(biāo)節(jié)點(diǎn)比例的上升，TDAPIT的定位覆蓋率更是明顯地上升，在信標(biāo)節(jié)點(diǎn)比例為20％左右時(shí)，定位覆蓋率就達(dá)到了90％以上。在這以后，信標(biāo)節(jié)點(diǎn)比例的增加對(duì)定位覆蓋率的影響大大降低。這是因?yàn)樵谒惴ㄖ胁捎昧搜h(huán)擴(kuò)散的思想，即將已知節(jié)點(diǎn)當(dāng)做信標(biāo)節(jié)點(diǎn)來實(shí)現(xiàn)定位，最大限度地減少了不良節(jié)點(diǎn)的數(shù)目。在信標(biāo)節(jié)點(diǎn)比例達(dá)到30％左右時(shí)，APIT算法的定位覆蓋率在85％左右，而且仍然還有上升的趨勢(shì)，說明APIT算法對(duì)信標(biāo)節(jié)點(diǎn)比例的依賴程度比較高。

2．2 定位誤差

定位誤差隨信標(biāo)節(jié)點(diǎn)比例變化圖如圖4所示。該仿真結(jié)果說明，在網(wǎng)絡(luò)部署一定時(shí)，當(dāng)兩種算法的定位誤差達(dá)到35％左右時(shí)，兩者的定位精度很難再得到明顯改善。在信標(biāo)節(jié)點(diǎn)比例為5％左右時(shí)，TDAPIT的定位誤差明顯大于APIT的定位誤差，這是因?yàn)樵诰W(wǎng)絡(luò)的初始階段，APIT可定位的節(jié)點(diǎn)數(shù)目較少，而TDAPIT能夠定位的節(jié)點(diǎn)相對(duì)較多，而且TDAPIT定位時(shí)，利用了本身定位就有誤差的已知節(jié)點(diǎn)，使得定位出的節(jié)點(diǎn)的誤差得到累加，明顯加大了定位誤差。當(dāng)信標(biāo)節(jié)點(diǎn)比例在20％左右時(shí)，兩種算法的定位誤差變化不明顯，此時(shí)增加信標(biāo)節(jié)點(diǎn)比例時(shí)，TDAP IT略顯優(yōu)秀，但定位誤差仍然在30％以上，由此可見這種非基于測(cè)距的定位方法雖然成本較低、實(shí)現(xiàn)簡(jiǎn)單，但是定位誤差比較大，而且當(dāng)信標(biāo)節(jié)點(diǎn)比例達(dá)到30％時(shí)，定位誤差仍然在30％以上，此時(shí)即使增加信標(biāo)節(jié)點(diǎn)的比例也很難改變定位誤差。

結(jié)語

本文基于平面中的APIT算法，提出了擴(kuò)展的三維TDAPIT算法。并在分析APIT誤差來源的基礎(chǔ)上，對(duì)TDAPIT進(jìn)行了相應(yīng)的改進(jìn)。擴(kuò)展的TDAPIT算法能夠較好的在三維空間中實(shí)現(xiàn)節(jié)點(diǎn)的定位。通過仿真實(shí)驗(yàn)，雖然在網(wǎng)絡(luò)的初始階段，TDAPIT的定位覆蓋率在信標(biāo)節(jié)點(diǎn)很少的情況下較高，但這是以增加定位誤差為代價(jià)的。
責(zé)任編輯；zl