基于臨近信標節點修正的APIT算法改進

孟祥萍，付志學，紀 秀

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

基于臨近信標節點修正的APIT算法改進

孟祥萍1，3，付志學2*，紀 秀1，3

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

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

無線傳感器網絡；定位；APIT算法；節點修正

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

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

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

1　現有APIT算法分析

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

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

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

假設點M處于ΔABC內部，則有等式成立：

當點M處于ΔABC外部時，則有等式成立：

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

節點M與信標節點A、B、C的距離MA、MB、MC通過RSSI傳播的自由空間模型及對數-常態分布模型進行測算：

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

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

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

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

2　基于臨近信標節點的修正的N-APIT算法

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

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

圖1　信標節點修正

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

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

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

由于未知節點M與信標節點G距離很近，文獻［6］的試驗表明，RSSI信號強度在空間上具有區域性，即RSSI信號在某一特定的區域內有相近的屬性。所以，未知節點M和信標節點G具有相似的影響測距的因素，即：

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

同理，可得：

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

3　仿真結果及分析

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

使用matlab2012b仿真軟件檢驗N-APIT算法的性能。建立如下仿真環境：信標節點及未知節點隨機分布在100 m× 100 m的空間內，總數為N=60，節點的通信半徑為R=20 m。在APIT算法中，信標節點的通信半徑通常比未知節點的通信半徑大，本文設為3R。

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

圖2　節點連通圖

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

圖3　S-APIT定位誤差圖

圖4　N-APIT定位誤差圖

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

圖5是S-APIT與N-APIT在同一網絡環境下，重復實驗50次，每次節點重置，對50次結果求均值之后的定位誤差變化曲線。

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

圖5　測距誤差與定位誤差

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

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

圖6　信標節點與定位誤差

4　結束語

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

［1］彭宇，王丹.無線傳感器網絡定位技術綜述［J］.電子測量與儀器學報，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］湯文亮，周琳穎.基于三角形外接圓覆蓋的改進APIT定位算法［J］.傳感技術學報，2015（1）：121-125.

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

［5］程偉，史浩山，王慶文.基于差分修正的傳感器網絡加權質心定位算法［J］.系統仿真學報，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，FU 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）；吉林省發改委項目（20130206049G X）；長春市科技局項目（2014116）

孟祥萍（1961—），女，吉林長春人，博士。研究方向：無線傳感器網絡，智能電網技術。