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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

S-APIT算法在判定未知節(jié)點(diǎn)M是否位于內(nèi)具有明顯的便捷性。但是，該算法僅在RSSI信息能夠精確測(cè)量，RSSI損耗經(jīng)驗(yàn)公式精確情況下才能達(dá)到較高的準(zhǔn)確度，并不能減少誤判的發(fā)生。當(dāng)環(huán)境、測(cè)量設(shè)備與理想狀況有差異時(shí)，RSSI值不易準(zhǔn)確測(cè)量，此時(shí)容易發(fā)生較大的誤判。假設(shè)點(diǎn)M原本處于ΔABC內(nèi)，但是測(cè)算的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錯(cuò)誤的發(fā)生。同理，在另一種情況下亦可能導(dǎo)致ETI錯(cuò)誤的發(fā)生。

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

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

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

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

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

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

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

同理，可得：

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

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

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

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

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

圖2　節(jié)點(diǎn)連通圖

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

圖3　S-APIT定位誤差圖

圖4　N-APIT定位誤差圖

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

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

表1　S-APIT與N-APIT誤差對(duì)比

圖5　測(cè)距誤差與定位誤差

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

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

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

4　結(jié)束語(yǔ)

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

［1］彭宇，王丹.無(wú)線傳感器網(wǎng)絡(luò)定位技術(shù)綜述［J］.電子測(cè)量與儀器學(xué)報(bào)，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é)報(bào)，2015（1）：121-125.

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

［5］程偉，史浩山，王慶文.基于差分修正的傳感器網(wǎng)絡(luò)加權(quán)質(zhì)心定位算法［J］.系統(tǒng)仿真學(xué)報(bào)，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稿件編號(hào)：201505189

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

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