一種改進(jìn)的APIT定位算法

一、節(jié)點(diǎn)定位技術(shù)的重要性首先，無線傳感器網(wǎng)絡(luò)中，節(jié)點(diǎn)所采集的數(shù)據(jù)或探測的事件，通常都需要有相應(yīng)的地理位置信息作為標(biāo)識(shí)，對大多數(shù)應(yīng)用來說，不知道傳感器位置，所感知的數(shù)據(jù)是沒有意義的。比如：一個(gè)被監(jiān)控的車輛的地點(diǎn)、森林火災(zāi)發(fā)生的位置、戰(zhàn)場上敵方車輛的運(yùn)動(dòng)區(qū)域等。

其次，無線傳感器網(wǎng)絡(luò)的一些系統(tǒng)功能需要節(jié)點(diǎn)的位置信息。例如：確定無線傳感器網(wǎng)絡(luò)的覆蓋范圍等。第1頁/共35頁第一頁，共36頁。最后，許多無線傳感器網(wǎng)絡(luò)協(xié)議也都利用了節(jié)點(diǎn)的位置信息，比如利用節(jié)點(diǎn)間的地理位置信息控制節(jié)點(diǎn)的發(fā)送功率以及約束波束的方向性、進(jìn)行路由決策等。

因此，傳感器的節(jié)點(diǎn)定位在整個(gè)無線傳感器網(wǎng)絡(luò)中占有重要地位，是無線傳感器網(wǎng)絡(luò)的支持技術(shù)之一。第2頁/共35頁第二頁，共36頁。二、節(jié)點(diǎn)定位技術(shù)的分類無線傳感器網(wǎng)絡(luò)的節(jié)點(diǎn)地位技術(shù)分主要為兩類：基于測距的定位技術(shù)和免于測距的定位技術(shù)。

基于測距的定位技術(shù)(Range-BasedLocalizationSchemes)：需要通過不同的測距技術(shù)，如到達(dá)時(shí)間測量法（TOA）、到達(dá)時(shí)間差測量法（TDOA）、基于接收信號(hào)能量的測距技術(shù)(RSSI）等得到節(jié)點(diǎn)間的距離或角度信息，然后再使用相應(yīng)定位方法計(jì)算節(jié)點(diǎn)位置。第3頁/共35頁第三頁，共36頁。

免于測距的定位技術(shù)(Range-FreeLocalizationSchemes)：無需節(jié)點(diǎn)間的距離或角度信息，而利用節(jié)點(diǎn)間的鄰近關(guān)系和連通性實(shí)現(xiàn)定位。

一般說來，免于測距的定位技術(shù)定位精度不如基于測距的定位技術(shù)高，但是基于測距的定位技術(shù)對硬件要求很高，而且在測量距離和角度的準(zhǔn)確性方面需要大量的研究，而免于測距的定位技術(shù)不需要知道未知節(jié)點(diǎn)到錨節(jié)點(diǎn)的距離，在成本和功耗方面比基于測距的技術(shù)具有優(yōu)勢，因此得到了廣泛應(yīng)用。第4頁/共35頁第四頁，共36頁。

常用的免于測距的定位技術(shù)質(zhì)心定位算法、APS算法、MDS-MAP算法、APIT定位算法等。APIT定位算法的基本思想簡單，實(shí)現(xiàn)容易。而且由于其定位功耗小、成本低、節(jié)點(diǎn)定位精度高等特點(diǎn)得到廣泛應(yīng)用和研究。第5頁/共35頁第五頁，共36頁。三、APIT定位算法

APIT算法的理論基礎(chǔ)是PIT（pointin-triangulationtest）算法（三角形內(nèi)點(diǎn)測試法）：假如存在一個(gè)方向，沿著這個(gè)方向節(jié)點(diǎn)M會(huì)同時(shí)遠(yuǎn)離或接近參考節(jié)點(diǎn)A、B、C，那么節(jié)點(diǎn)M位于三角形ABC外部，如圖1所示；否則，M位于三角形ABC內(nèi)部，如圖2所示。

圖1

圖2AMCBAMCB第6頁/共35頁第六頁，共36頁。

PIT算法中假設(shè)待定位節(jié)點(diǎn)M是運(yùn)動(dòng)的，然而，在大多數(shù)WSN中，待定位節(jié)點(diǎn)通常是靜止的。為了在靜態(tài)網(wǎng)絡(luò)中執(zhí)行PIT測試，我們定義了APIT算法，即近似三角形內(nèi)點(diǎn)測試法（approximatepoint-in-triangulationtest）：假如待定位節(jié)點(diǎn)M的相鄰節(jié)點(diǎn)沒有同時(shí)遠(yuǎn)離或靠近參考節(jié)點(diǎn)A、B、C，則節(jié)點(diǎn)M位于三角形ABC內(nèi)部；否則，位于三角形ABC外部。第7頁/共35頁第七頁，共36頁。

APIT算法是利用WSN較高的節(jié)點(diǎn)密度，同時(shí)在給定方向上，節(jié)點(diǎn)離參考點(diǎn)越遠(yuǎn)，信號(hào)強(qiáng)度越弱的特性，通過與相鄰節(jié)點(diǎn)的信息交換來模擬PIT算法的。下面以圖來說明。第8頁/共35頁第八頁，共36頁。

在圖3中，節(jié)點(diǎn)M與相鄰節(jié)點(diǎn)1都通過發(fā)送信號(hào)的強(qiáng)弱得知自己與參考節(jié)點(diǎn)A、B、C的遠(yuǎn)近，然后節(jié)點(diǎn)M與節(jié)點(diǎn)1通過交換信息，得知自己如果運(yùn)動(dòng)至1處，將遠(yuǎn)離B、C，但會(huì)接近A，與2、3、4點(diǎn)的判斷也類似，最終確定自己位于三角形ABC內(nèi)部。

圖3ACB1M423第9頁/共35頁第九頁，共36頁。在圖4中，待定位節(jié)點(diǎn)M通過上述類似的通信判斷知如果運(yùn)動(dòng)至相鄰節(jié)點(diǎn)2處，則將同時(shí)遠(yuǎn)離參考節(jié)點(diǎn)A、B、C，所以可以得知自己位于三角形ABC的外部。

圖4A13M42CB第10頁/共35頁第十頁，共36頁。在判斷出M位于三角形內(nèi)后，則將其標(biāo)記（在三角形外部則不標(biāo)記），依次對M周圍的所有鄰近參考節(jié)點(diǎn)（在發(fā)送功率范圍內(nèi)的參考節(jié)點(diǎn)）進(jìn)行各種不同的組合并檢測，最終找出所有滿足要求的三角形的重疊區(qū)域，求其質(zhì)心位置以替代待定位節(jié)點(diǎn)在網(wǎng)絡(luò)中的具體位置坐標(biāo)，如圖5所示。

圖5第11頁/共35頁第十一頁，共36頁。通過以上關(guān)于APIT算法思想的描述,可以得出其實(shí)現(xiàn)過程分為以下4個(gè)階段:(1)節(jié)點(diǎn)間信息接收和交換。待定位節(jié)點(diǎn)接收參考節(jié)點(diǎn)的位置信息、節(jié)點(diǎn)ID和信號(hào)強(qiáng)度等信息,以及未知節(jié)點(diǎn)之間相互交換各自接收到的參考節(jié)點(diǎn)信息。(2)執(zhí)行APIT測試。使用APIT測試方法判斷未知節(jié)點(diǎn)是否位于參考節(jié)點(diǎn)三元組合形成的三角形內(nèi)部。第12頁/共35頁第十二頁，共36頁。(3)計(jì)算重疊區(qū)域。計(jì)算多個(gè)三角形覆蓋區(qū)域的重疊部分，計(jì)算重疊區(qū)域的方法為格子掃描法（GridScan)：將WSN所監(jiān)測區(qū)域分為大小相同的網(wǎng)格，每個(gè)網(wǎng)格初始值設(shè)為0，如果判斷出待測節(jié)點(diǎn)位于三角形內(nèi)，相應(yīng)三角形所在網(wǎng)格區(qū)域值加1；反之，相應(yīng)三角形所在網(wǎng)格區(qū)域值減1，不斷重復(fù)上述步驟，最后得到網(wǎng)格數(shù)值最大的區(qū)域就是要求的重疊區(qū)域。(4)計(jì)算質(zhì)心。計(jì)算(3)中所求得的重疊區(qū)域的質(zhì)心,作為未知節(jié)點(diǎn)的估計(jì)位置。

第13頁/共35頁第十三頁，共36頁。四、APIT算法的不足通過上述分析發(fā)現(xiàn)，APIT算法僅僅分析幾個(gè)有限的方向，而且定位覆蓋率（可實(shí)現(xiàn)定位的未知節(jié)點(diǎn)數(shù)目與總的未知節(jié)點(diǎn)數(shù)目之比）與相鄰節(jié)點(diǎn)數(shù)量及分布密切相關(guān)，因此APIT算法有時(shí)會(huì)做出不正確的判斷以及存在大量無法定位的節(jié)點(diǎn)。下面以圖例進(jìn)行分析。第14頁/共35頁第十四頁，共36頁。如圖6所示，由于相鄰節(jié)點(diǎn)2在三角形ABC之外且離參考節(jié)點(diǎn)A、B、C都較M點(diǎn)距這三個(gè)參考點(diǎn)遠(yuǎn)，從而當(dāng)模擬M點(diǎn)朝2處運(yùn)動(dòng)時(shí)，會(huì)使M點(diǎn)錯(cuò)誤的判斷自身在三角形ABC之外。

圖6AB12M4C3第15頁/共35頁第十五頁，共36頁。如圖7所示，由于相鄰節(jié)點(diǎn)1、2、3的不規(guī)則部署，從而使得M點(diǎn)模擬朝1、2、3的任何一個(gè)方向運(yùn)動(dòng)時(shí)，都不會(huì)同時(shí)遠(yuǎn)離或靠近A、B、C，從而M點(diǎn)錯(cuò)誤的判斷自身在三角形ABC之內(nèi)。

圖7A12M3CB第16頁/共35頁第十六頁，共36頁。如圖8、9所示，待定位節(jié)點(diǎn)M的鄰近參考節(jié)點(diǎn)少于三個(gè)或M在三角形ABC的外部，造成APIT算法無法應(yīng)用，這樣M點(diǎn)就成了無法定位的節(jié)點(diǎn)。

圖8

圖9ABMMACB第17頁/共35頁第十七頁，共36頁。由于上述客觀原因的存在，影響了整個(gè)WSN的定位覆蓋率及定位精度。因此，文章針對上述問題，提出了改進(jìn)算法。第18頁/共35頁第十八頁，共36頁。五、改進(jìn)的APIT算法在節(jié)點(diǎn)定位中，我們最關(guān)心的莫過于定位精度和定位覆蓋率這兩個(gè)性能參數(shù)。我們先對定位精度這個(gè)問題進(jìn)行分析。

定位精度的問題，與圖6和圖7情況下的兩種錯(cuò)誤判決密切相關(guān)，這兩種錯(cuò)誤WSN中將其稱為In-to-outerror和Out-to-inerror。下面以圖的形式分析如何將其改進(jìn)。第19頁/共35頁第十九頁，共36頁。

如圖10所示，假設(shè)圖中所得到的兩個(gè)頂點(diǎn)為空心圓的三角形區(qū)域均為正確的。節(jié)點(diǎn)經(jīng)過APIT測試后獲得了一個(gè)錯(cuò)誤的Out-To-In區(qū)域(用實(shí)心頂點(diǎn)的三角形標(biāo)識(shí))。假設(shè)該錯(cuò)誤的三角形區(qū)域覆蓋了grid(2,5)這個(gè)網(wǎng)格，則該網(wǎng)格對應(yīng)的值將要加1，即變?yōu)?。本來，原本正確的交集區(qū)域的中心應(yīng)該位于grid(5,3)對應(yīng)的網(wǎng)格附近。然而，Out-To-Inerror將中心位置移至了grid(3,4)對應(yīng)的網(wǎng)格附近。

圖10假設(shè)網(wǎng)格大小為0.1R，R為參考節(jié)點(diǎn)的通信半徑，則定位精度將因此增加大于20%的誤差。000011110001021110001111100012111000022110000111100000第20頁/共35頁第二十頁，共36頁。針對以上問題，文章提出了計(jì)算未知節(jié)點(diǎn)可能存在的所有三角形區(qū)域的重心坐標(biāo)法，通過計(jì)算重心坐標(biāo)所構(gòu)成圖形的質(zhì)心作為未知節(jié)點(diǎn)的估計(jì)位置。如圖11所示。

圖11000011110001021110001111100012111000022110000111100000第21頁/共35頁第二十一頁，共36頁。

通過對比圖10和圖11可以發(fā)現(xiàn)，求三角形重心坐標(biāo)比網(wǎng)格掃描法更加接近grid(5,3)，主要是因?yàn)槿切沃匦膾呙杷惴ㄊ且渣c(diǎn)為出發(fā)點(diǎn)，而網(wǎng)格掃描法是以區(qū)域?yàn)槌霭l(fā)點(diǎn)，從而網(wǎng)格掃描算法更易受Out-To-In或In-To-Out錯(cuò)誤區(qū)域的影響。這樣，重心掃描算法相比網(wǎng)格掃描法可以提高定位精度。第22頁/共35頁第二十二頁，共36頁。定位覆蓋率的問題，主要受圖8和圖9所示問題的影響，在這兩種情況下，WSN無法對相應(yīng)節(jié)點(diǎn)進(jìn)行定位。

為了提高定位覆蓋率，可以將已經(jīng)定位的未知節(jié)點(diǎn)升級(jí)為參考節(jié)點(diǎn)，這樣就有效提高了參考節(jié)點(diǎn)的比例。為了保證定位的精確性，新的參考節(jié)點(diǎn)在進(jìn)行定位時(shí)所用到參考節(jié)點(diǎn)組成三角形的數(shù)量須大于等于4個(gè)。這樣，如果部分處于圖8和圖9情況下的待定位節(jié)點(diǎn)的鄰近參考節(jié)點(diǎn)變得大于等于三個(gè)且其處于三角形內(nèi)部，就可以用APIT算法進(jìn)行定位了。第23頁/共35頁第二十三頁，共36頁。

但是，即使使用上面的方法，仍然可能有一些未知節(jié)點(diǎn)的鄰近節(jié)點(diǎn)數(shù)少于三個(gè)或者處于所有三角形的外部，這樣造成無法定位。為了進(jìn)一步擴(kuò)大定位覆蓋率，我們可以再引入基于測距的定位技術(shù)中的RSSI算法。RSSI算法，即基于接收信號(hào)能量的測距技術(shù)，其原理是已知發(fā)射節(jié)點(diǎn)的發(fā)射信號(hào)強(qiáng)度，接收節(jié)點(diǎn)根據(jù)接收到的信號(hào)強(qiáng)度，然后利用無線信號(hào)能量與距離的公式：d=d0*10[Pr(d0)-Pr(d)]/10n

得出發(fā)射節(jié)點(diǎn)與接收節(jié)點(diǎn)的距離d。第24頁/共35頁第二十四頁，共36頁。

這里可以引入RSSI算法的理論基礎(chǔ)是在APIT算法中，節(jié)點(diǎn)間交換信息時(shí)，本身就存在著所謂的能量強(qiáng)度信息的交換，而且能量與距離公式的計(jì)算方法也不復(fù)雜，因此，引入RSSI算法基本不會(huì)增加硬件成本。第25頁/共35頁第二十五頁，共36頁。

在得出距離后，便可以利用一些定位方法，如三邊測量法，多邊測量法等得出待定位節(jié)點(diǎn)的位置坐標(biāo)了。由于RSSI算法不涉及角度信息，因此，對于鄰近節(jié)點(diǎn)只有兩個(gè)或兩個(gè)以下的未知節(jié)點(diǎn)，仍然無法定位。同時(shí)，為了減少開銷，對于大于等于三個(gè)鄰近節(jié)點(diǎn)的未知節(jié)點(diǎn)，我們只得出其與其中三個(gè)鄰近參考節(jié)點(diǎn)的距離信息就可以了，因此，估計(jì)未知節(jié)點(diǎn)坐標(biāo)時(shí)，采用三邊測量法比較合理。第26頁/共35頁第二十六頁，共36頁。整個(gè)改進(jìn)算法流程圖如下所示：

NYYN

YN網(wǎng)絡(luò)布置初始化節(jié)點(diǎn)信息交換參考節(jié)點(diǎn)>=3且處于三角形內(nèi)?重心掃描法對未知節(jié)點(diǎn)定位新定位節(jié)點(diǎn)升級(jí)結(jié)束參考節(jié)點(diǎn)>=3且處于4個(gè)三角形內(nèi)？參考節(jié)點(diǎn)>3?標(biāo)記為routernode執(zhí)行RSSI技術(shù)和三邊掃描第27頁/共35頁第二十七頁，共36頁。六、仿真結(jié)果及分析平均定位誤差（即定位精度）隨錨節(jié)點(diǎn)比例變化曲線，節(jié)點(diǎn)總數(shù)不變。定位覆蓋率隨錨節(jié)點(diǎn)比例變化曲線，節(jié)點(diǎn)總數(shù)不變。第28頁/共35頁第二十八頁，共36頁。平均定位誤差（即定位精度）隨節(jié)點(diǎn)總數(shù)變化曲線，錨節(jié)點(diǎn)比例不變。定位覆蓋率隨節(jié)點(diǎn)總數(shù)變化曲線，錨節(jié)點(diǎn)比例不變。第29頁/共35頁第二十九頁，共36頁。

上述兩組圖是傳統(tǒng)APIT算法和改進(jìn)算法在不同錨節(jié)點(diǎn)比例和節(jié)點(diǎn)總數(shù)時(shí)平均定位誤差和定位覆蓋率的比較。從圖中可以看出，改進(jìn)后的算法的平均定位誤差明顯小于傳統(tǒng)算法，而定位覆蓋率明顯高于傳統(tǒng)算法，說明改進(jìn)后的APIT算法在算法上的確優(yōu)于傳統(tǒng)的APIT算法。

第30頁/共35頁第三十頁，共36頁。

再從通信開銷上來看，改進(jìn)算法和傳統(tǒng)算法的區(qū)別只在于傳送最后升級(jí)的已定位未知節(jié)點(diǎn)的數(shù)據(jù)包，由于改進(jìn)算法中對已定位未知節(jié)點(diǎn)的升級(jí)有一定的限制條件，故算法中最終升級(jí)的未知節(jié)點(diǎn)數(shù)量不會(huì)太多，而且在無限傳感器網(wǎng)絡(luò)中，節(jié)點(diǎn)本身在間隔一定的時(shí)間后會(huì)廣播自己的位置信息，故改進(jìn)算法與原算法比較，通信開銷的增加不是特別明顯。

在計(jì)算開銷方面，改進(jìn)算法在近似三角形內(nèi)點(diǎn)測試前先比較了未知節(jié)點(diǎn)與錨節(jié)點(diǎn)所組成三角形一邊的兩個(gè)頂點(diǎn)距離之和與三角形的邊長，在計(jì)算開銷中增加了未知節(jié)點(diǎn)與錨節(jié)點(diǎn)、錨節(jié)點(diǎn)之間距離的估計(jì)。但是，改進(jìn)算法在進(jìn)行未知計(jì)算時(shí)沒有采用傳統(tǒng)的網(wǎng)格掃描方式，而是直接計(jì)算錨節(jié)點(diǎn)所組成三角形重心的質(zhì)心，在這個(gè)過程中省去了網(wǎng)格掃描時(shí)三角形區(qū)域與每個(gè)網(wǎng)格邊界的比較，大大的減小了計(jì)算開銷。第31頁/共35頁第三十一頁，共36頁。

綜合以上分析結(jié)果可知，改進(jìn)后的算法與原算法相比較，在通信開銷上有所增加，并且因?yàn)槲粗?jié)點(diǎn)的能量要比錨節(jié)點(diǎn)小，升級(jí)的部分未知節(jié)點(diǎn)會(huì)因?yàn)槟芰窟^早耗盡而產(chǎn)生失效的問題，但是考慮到無線傳感器網(wǎng)絡(luò)中節(jié)點(diǎn)一般是密集布置，因此這樣的缺點(diǎn)基本上不會(huì)對網(wǎng)絡(luò)構(gòu)成威脅。在計(jì)算開銷方面，改進(jìn)的算法節(jié)省了大量的計(jì)算開銷，可以降低傳感器節(jié)點(diǎn)的能量損耗速度?？偟膩碚f，改進(jìn)算法在無需添加硬件設(shè)備的情況下改善了定位的精度和覆蓋率，在無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位研究中具有一定的意義。第32頁/共35頁第三十二頁，共36頁。七、參考文獻(xiàn)[1]SavareseC,RabaeyJ,Beutel.Locationingindistributedad-hocwirelesssensornetwork.Proceedingsofthe2001IEEEInternationalConferenceonAcoustics,Speech,AndSingal(ICASS’01),Vol.4,SaltLake:IEEESingalProcessingSociety,2001:2037-2040.[2]于宏毅，李鷗，張效義等.無線傳感器網(wǎng)絡(luò)理論、技術(shù)與實(shí)現(xiàn).北京：國防工業(yè)出版社，2010,9重印.[3]馬剛，陳盛云.WSN中APIT