基于臨近信標(biāo)節(jié)點修正的APIT算法改進(jìn)

孟祥萍，付志學(xué)，紀(jì) 秀

（1.長春工程學(xué)院 電氣與信息工程學(xué)院，吉林 長春　130012；2.長春工業(yè)大學(xué) 電氣與電子工程學(xué)院，吉林 長春　130012；3.吉林省配電自動化工程研究中心，吉林長春　130012）

基于臨近信標(biāo)節(jié)點修正的APIT算法改進(jìn)

孟祥萍1，3，付志學(xué)2*，紀(jì) 秀1，3

（1.長春工程學(xué)院 電氣與信息工程學(xué)院，吉林 長春130012；2.長春工業(yè)大學(xué) 電氣與電子工程學(xué)院，吉林 長春130012；3.吉林省配電自動化工程研究中心，吉林長春130012）

定位技術(shù)在無線傳感器網(wǎng)絡(luò)中占有重要的地位。近似三角形內(nèi)點測試算法（APIT）是一種硬件要求低，定位性能良好的定位算法。APIT算法在節(jié)點密度較低的場合，易產(chǎn)生PIT誤判，S-APIT算法采用面積和判斷進(jìn)行近似三角形內(nèi)點測試，改善了APIT算法的PIT測試，但是在存在測距誤差時，S-APIT算法并不能有效的減少PIT誤判的發(fā)生。針對該問題，提出了一種將未知節(jié)點的臨近信標(biāo)節(jié)點作為修正節(jié)點的N-APIT算法，仿真結(jié)果表明：算法能夠改善環(huán)境因素的影響，減少測距誤差，改善定位精度。

無線傳感器網(wǎng)絡(luò)；定位；APIT算法；節(jié)點修正

網(wǎng)絡(luò)節(jié)點定位是無線傳感網(wǎng)絡(luò)中的關(guān)鍵技術(shù)，節(jié)點位置信息在無線傳感網(wǎng)絡(luò)中占有重要的地位。目前定位算法主要分為兩大類，基于測距算法（Range-based）和無需測距算法（Range-free）［1］。無需測距定位算法是根據(jù)網(wǎng)絡(luò)連通性等信息來實現(xiàn)對節(jié)點的位置定位，主要有APIT（Approximate Point-In-Triangulation）算法、質(zhì)心法（Centroid Algorithm）算法、DV-hop算法等［2］。

APIT算法是一種基于無需測距的定位算法，相比其他的無需測距算法，該算法在硬件成本、定位精度等方面性能良好，但是在節(jié)點密度小的時候誤差大。文獻(xiàn)［3］提出了一種基于三角形面積圓覆蓋的APIT改進(jìn)算法，該密度較低的時候取得了比較好的定位效果。文獻(xiàn)［4］提出了基于面積和PIT測試的S-APIT算法，簡化了PIT測試，提高了精度。但是文獻(xiàn)［3］、文獻(xiàn)［4］的算法均易受到硬件、環(huán)境等因素的影響，導(dǎo)致其在測距誤差存在的情況下，容易產(chǎn)生PIT誤判，影響了定位精度。

針對上述問題，本文提出了一種基于臨近信標(biāo)節(jié)點修正的N-APIT算法，該算法以S-APIT算法為基礎(chǔ)，利用臨近信標(biāo)節(jié)點來進(jìn)行測距修正，改善測距誤差的影響，減少未知節(jié)點誤判情況的發(fā)生，最終提高了定位的精度。

1　現(xiàn)有APIT算法分析

APIT算法亦稱近似三角形內(nèi)點測試算法。未知節(jié)點M周圍有n個信標(biāo)節(jié)點，任選取其中3個節(jié)點，形成以這3個節(jié)點為頂點的3角形，總數(shù)為。設(shè)個三角形的交集區(qū)域為D，則節(jié)點包含在D內(nèi)部，對D運用質(zhì)心算法，所得出的結(jié)果作為未知節(jié)點M的估測位置。

APIT算法是利用PIT測試來判定未知節(jié)點處于三角形內(nèi)部與否的。但是這種PIT測試需要未知節(jié)點與相鄰節(jié)點交換信息，在節(jié)點密度低以及分布不均勻的情況下，原始APIT算法容易發(fā)生PIT誤判，產(chǎn)生EIT（External To Internal）錯誤及ITE（Internal To External）錯誤。

文獻(xiàn)［4］提出了用計算三角形面積和來進(jìn)行PIT測試的S-APIT算法，在沒有測距誤差的情況下，效果顯著。

假設(shè)點M處于ΔABC內(nèi)部，則有等式成立：

當(dāng)點M處于ΔABC外部時，則有等式成立：

由兩式分析可得，判定點M是否處于外部可以使用如下不等式：

節(jié)點M與信標(biāo)節(jié)點A、B、C的距離MA、MB、MC通過RSSI傳播的自由空間模型及對數(shù)-常態(tài)分布模型進(jìn)行測算：

式中，Ps是信號發(fā)射點的發(fā)射功率，Pa是信號放大功率，PL（d0）是信號傳播后信號的損耗的功率，d是信號傳播的距離，Xδ是考慮到環(huán)境因素的平均值為零的高斯隨機(jī)變量，理論中，其標(biāo)準(zhǔn)差為4～10，n是路徑衰減因子，通常的取值范圍為2～5。

根據(jù)（4）求得d的可確定MA、MB、MC的長度，結(jié)合AB、BC、CA的長度，運用海倫公式可以計算出各個三角形的面積，海倫公式如下：

其中，S是三角形的面積，a、b、c是三角形三邊的長，p= （a+b+c）/2。

將獲得SΔMAB、SΔMBC、SΔMCA、SΔABC的值，根據(jù)公式（3）便可判斷定未知節(jié)點與三角形的關(guān)系，不需要經(jīng)過節(jié)點間的信息交換。

2　基于臨近信標(biāo)節(jié)點的修正的N-APIT算法

S-APIT算法在判定未知節(jié)點M是否位于內(nèi)具有明顯的便捷性。但是，該算法僅在RSSI信息能夠精確測量，RSSI損耗經(jīng)驗公式精確情況下才能達(dá)到較高的準(zhǔn)確度，并不能減少誤判的發(fā)生。當(dāng)環(huán)境、測量設(shè)備與理想狀況有差異時，RSSI值不易準(zhǔn)確測量，此時容易發(fā)生較大的誤判。假設(shè)點M原本處于ΔABC內(nèi)，但是測算的MA、MB、MC的距離存在誤差，那么算得到的SΔMAB、SΔMBC、SΔMCA與 SΔABC并不能嚴(yán)格的符合 SΔMAB+SΔMBC+SΔMCA= SΔABC，甚至有惡性的結(jié)果SΔMAB+SΔMBC+SΔMCA＞SΔABC，導(dǎo)致 ITE錯誤的發(fā)生。同理，在另一種情況下亦可能導(dǎo)致ETI錯誤的發(fā)生。

為了減少實際應(yīng)用中環(huán)境等因素的影響，本文提出一種N-APIT算法，引入臨近信標(biāo)節(jié)點作為修正信標(biāo)節(jié)點，用修正信標(biāo)節(jié)點的測距誤差因子來修正未知節(jié)點的測距結(jié)果［5］，經(jīng)過修正后的測距結(jié)果要比原始的測距結(jié)果具有更高的可信度，更能精確的反應(yīng)節(jié)點間的距離信息，達(dá)到了提高定位精度的目的。

圖1　信標(biāo)節(jié)點修正

如圖1所示，假設(shè)點G（xG，yG）是與未知節(jié)點M距離最近的信標(biāo)節(jié)點，將其作為修正節(jié)點。設(shè)A（x1，y1）、B（x2，y2）、C（x3，y3）由于A、G都是信標(biāo)節(jié)點，所以其實際距離dGA：

信標(biāo)節(jié)點G與信標(biāo)節(jié)點A進(jìn)行通信，通過公式（4）、（5）、（6）相互測距可以得到信標(biāo)G、A間的估測距離d′GA，此時，我們可以得到在信標(biāo)節(jié)G點相對于信信標(biāo)節(jié)點A的誤差因子β1：

定位過程中，未知節(jié)點M通過與信標(biāo)節(jié)點A通信測距獲得的距離的估計d′GA，設(shè)其實際的距離為dGA，誤差因子為α1，則：

由于未知節(jié)點M與信標(biāo)節(jié)點G距離很近，文獻(xiàn)［6］的試驗表明，RSSI信號強(qiáng)度在空間上具有區(qū)域性，即RSSI信號在某一特定的區(qū)域內(nèi)有相近的屬性。所以，未知節(jié)點M和信標(biāo)節(jié)點G具有相似的影響測距的因素，即：

用G點的測距誤差因子代替M點的誤差因子，有等式（7）、等式（8）可得修正后的測距值：

同理，可得：

將dMA、dMB、dMC代替MA、MB、MC的估測距離，修正了環(huán)境等因素導(dǎo)致的誤差影響。結(jié)合信標(biāo)節(jié)點A、B、C之間的實際距離dAB，dBC，dCA以及海倫公式（7）可以得到相比于S-APIT算法中未知節(jié)點M與三角形ABC更為準(zhǔn)確的關(guān)系，減少了ITE錯誤、ETI錯誤的發(fā)生。

3　仿真結(jié)果及分析

在定位算法中，普遍采用相對定位誤差衡量定位誤差。（xi，yi）是算法求得的未知節(jié)點估測位置，（x′i，y′i）為節(jié)點的實際位置，R為節(jié)點的通信半徑，未知節(jié)點的數(shù)目為N。則相對定位誤差Ei、平均定位誤差E有如下表達(dá)式：

使用matlab2012b仿真軟件檢驗N-APIT算法的性能。建立如下仿真環(huán)境：信標(biāo)節(jié)點及未知節(jié)點隨機(jī)分布在100 m× 100 m的空間內(nèi)，總數(shù)為N=60，節(jié)點的通信半徑為R=20 m。在APIT算法中，信標(biāo)節(jié)點的通信半徑通常比未知節(jié)點的通信半徑大，本文設(shè)為3R。

圖2所示的為信標(biāo)節(jié)點總數(shù)為20，未知節(jié)點為40時，節(jié)點間的連通圖，為方便觀察，僅將信標(biāo)節(jié)點的連通圖給出。其中，圓圈為未知節(jié)點，星號為信標(biāo)節(jié)點。測距誤差設(shè)為2%。

圖2　節(jié)點連通圖

圖3與圖4分別為S-APIT算法及N-APIT算法下的定位誤差圖，其中圓圈為定位后的結(jié)果，叉號表示該點不能被定位，定位后的節(jié)點位置與定位前的節(jié)點位置用線相連，線越長表示誤差越大。在圖4中，S-APIT算法受測距誤差的影響，箭頭指向處的節(jié)點有較大的誤差；圖5中，N-APIT算法使用了臨近信標(biāo)節(jié)點對其進(jìn)行了修正，定位效果得到了明顯改善。

圖3　S-APIT定位誤差圖

圖4　N-APIT定位誤差圖

表1中S-APIT與N-APIT定位誤差對比數(shù)據(jù)表明，NAPIT算法能夠明顯改善最大誤差及平均誤差，平均誤差減少了46.68%。

圖5是S-APIT與N-APIT在同一網(wǎng)絡(luò)環(huán)境下，重復(fù)實驗50次，每次節(jié)點重置，對50次結(jié)果求均值之后的定位誤差變化曲線。

表1　S-APIT與N-APIT誤差對比

圖5　測距誤差與定位誤差

由圖5曲線可以看出，在不存在測距誤差的時，S-APIT 與N-APIT定位誤差相同，均為0.1772。隨著測距誤差的出現(xiàn)并增大，兩種定位算法的PIT測試均受到測距誤差的影響，不能夠準(zhǔn)確的判定節(jié)點與三角形的位置關(guān)系，導(dǎo)致定位出現(xiàn)了偏差，精度下降。測距誤差由0%增加到4%，S-APIT定位誤差上升非常明顯，超過4%時，誤差的增加不明顯。N-APIT定位誤差同樣隨著測距誤差的增大而增加，但是由于采用了臨近信標(biāo)節(jié)點進(jìn)行了測距修正，定位誤差增長曲線較S-APIT曲線有明顯的改善。

圖6是總節(jié)點數(shù)為60，信標(biāo)節(jié)點數(shù)量從10增加到50時，S-APIT算法與N-APIT算法的定位誤差曲線圖。由圖可得，在S-APIT算法中，信標(biāo)節(jié)點密度的增加并不能顯著的增加定位的精度，圖中，信標(biāo)節(jié)點從10增加到50，定位誤差僅從0.697 7降低至0.532 9，降低了23.62%。N-APIT算法在信標(biāo)節(jié)點稀疏的情況下，未知節(jié)點較難獲得臨近信標(biāo)節(jié)點的信息對測距誤差進(jìn)行修正，對定位誤差的改善并不明顯，信標(biāo)節(jié)點從10增加到25時，定位誤差僅從0.687 2降低到0.569 5，降低了17.13%。當(dāng)信標(biāo)節(jié)點從25增加到50時，定位誤差從0.569 5降低到了0.287 1，降低了49.59%，其原因是，信標(biāo)節(jié)點密度增加后，N-APIT算法中的未知節(jié)點能夠更容易獲得臨近信標(biāo)節(jié)點的信息，修正測距誤差，提高PIT測試的準(zhǔn)確性，改善定位的精度。

圖6　信標(biāo)節(jié)點與定位誤差

4　結(jié)束語

傳統(tǒng)的APIT及其改進(jìn)算法在實際應(yīng)用中沒有充分考慮環(huán)境因素導(dǎo)致的測物誤差的影響。本文提出的N-APIT算法使用臨近信標(biāo)節(jié)點的信息對未知節(jié)點進(jìn)行測距修正，能夠修正S-APIT算法中由于環(huán)境等因素造成的測距誤差對定位精度的影響，提高定位精度，明顯的改善定位的性能。同時，基于臨近信標(biāo)節(jié)點修正的N-APIT算法相比S-APIT算法，只需要增加對權(quán)值修正的計算環(huán)節(jié)，算法復(fù)雜程度略有增加，不需要增加額外的硬件成本，具有較好的工程可擴(kuò)展性和實用性。

［1］彭宇，王丹.無線傳感器網(wǎng)絡(luò)定位技術(shù)綜述［J］.電子測量與儀器學(xué)報，2011（5）：389-399.

［2］Niculescu D，Nath B.DV based positioning in Ad Hoc networks［J］.Journal of Telecommunication Systems，2003，22 （14）：267-280.

［3］湯文亮，周琳穎.基于三角形外接圓覆蓋的改進(jìn)APIT定位算法［J］.傳感技術(shù)學(xué)報，2015（1）：121-125.

［4］胡中棟，徐唱.基于面積和判斷APIT的無線傳感器網(wǎng)絡(luò)定位算法［J］.傳感器與微系統(tǒng)，2013（8）：125-127，130.

［5］程偉，史浩山，王慶文.基于差分修正的傳感器網(wǎng)絡(luò)加權(quán)質(zhì)心定位算法［J］.系統(tǒng)仿真學(xué)報，2012（2）：389-393.

［6］Heurtefeux K，Valois F.Is RSSI A Good Choice for Localization in Wireless Sensor Network［C］//IEEE International Conference on Advanced Information Networking and Applications.IEEE，2012：732-739.

Improved APIT algorithm based on adjacent beacon node

MENG Xiang-ping1，3，F(xiàn)U Zhi-xue2*，JI Xiu1，3
（1.School of Electrical Engineering and Information Technology，Changchun Institute of Technology，Changchun 130012，China；2.School of Electrical and Electronic Engineering，Changchun University of Technology，Changchun 130012，China；3.Jilin Province Distribution Automation Engineering Research Center，Changchun 130012，China）

Positioning technology occupies an important position in the wireless sensor network.Approximate Point-In-Triangulation（APIT）is a kind of algorithm that has low hardware requirements and good positioning performance.APIT algorithm is prone to PIT misjudgment when the node density is low.SAPIT algorithm uses summation of areas to do the Point-In-Triangulation test，and improves the PIT test of APIT.But when there is a ranging error，S-APIT algorithm cannot reduce PIT misjudgment effectively.A new kind of N-APIT algorithm that used adjacent beacon node as fixed beacon node is proposed，which can be dealt with the problem of S-APIT's easily affected by the ranging error caused by PIT's misjudgment. The simulation results show that the new algorithm can decrease the influence of ranging error，and improve the positioning accuracy that influenced by the environment factors.

wireless sensor networks；localization；APIT algorithm；error correction

TN925

A

1674－6236（2016）06-0005-03

2015-05-20稿件編號：201505189

吉林省教育廳項目（2014317）；吉林省發(fā)改委項目（20130206049G X）；長春市科技局項目（2014116）

孟祥萍（1961—），女，吉林長春人，博士。研究方向：無線傳感器網(wǎng)絡(luò)，智能電網(wǎng)技術(shù)。