基于向量積同向技術(shù)的改進(jìn)APIT定位算法

韓春光，蔡彤琛，時(shí)廣華，王科峰，汪志成

(1.浙江工商職業(yè)技術(shù)學(xué)院 智能電子學(xué)院， 寧波 315012;2.東華理工大學(xué) 機(jī)械電子工程學(xué)院，南昌 330013；3.寧波大紅鷹學(xué)院 信息工程學(xué)院，寧波 315000；4.江西省新能源工藝及裝備工程技術(shù)研究中心，南昌 330013)

引 言

無線傳感器網(wǎng)絡(luò)[1](wireless sensor networks,WSN)是近年來國內(nèi)外高度重視的一種信息技術(shù)之一，在水產(chǎn)養(yǎng)殖業(yè)、物聯(lián)網(wǎng)、倉儲(chǔ)系統(tǒng)、軍事安全以及防火防盜等領(lǐng)域有著廣泛應(yīng)用。在大多數(shù)應(yīng)用中，在節(jié)點(diǎn)位置已知的情況下采集到的數(shù)據(jù)才有意義。常見的全球定位系統(tǒng)(global positioning system,GPS)雖然精度高，但面對規(guī)模龐大的無線傳感器網(wǎng)絡(luò)，使用GPS定位將導(dǎo)致整個(gè)系統(tǒng)成本高、功耗大，并制約了系統(tǒng)擴(kuò)展性。當(dāng)然也有利用傳感器[2]和其它算法[3]的定位方式，但考慮到成本以及功耗問題，本文中主要研究無線傳感器網(wǎng)絡(luò)定位算法。現(xiàn)階段，定位算法主要分為基于測距[4]和無需測距[5]?；跍y距的主要有接收信號(hào)強(qiáng)度指示(received signal strength indicator,RSSI)[6]、到達(dá)時(shí)間差(time difference of arrival,TDOA)[7]、到達(dá)時(shí)間 (time of arrival,TOA)[8]以及到達(dá)角(angle of arrival,AOA)[9]等定位算法，這些算法定位精度高，但對硬件要求高、成本高、計(jì)算度復(fù)雜，增加了系統(tǒng)的功耗。無需測距技術(shù)的定位算法主要有質(zhì)心[10]、DV-Hop(distance vector-hop)[11-14]、Amorphous[15]、凸規(guī)劃[16]以及近似三角形內(nèi)點(diǎn)測試法(approximate point-in-triangulation test,APIT)定位算法，其中APIT定位算法功耗低、成本低、定位性能好，且不依賴于硬件設(shè)施，因此被廣泛應(yīng)用。但由于信標(biāo)節(jié)點(diǎn)覆蓋率低、節(jié)點(diǎn)分布不均勻，在最佳三角形內(nèi)點(diǎn)測試法(perfect point-in-triangulation test,PIT)測試時(shí)容易出現(xiàn)in-to-out和out-to-in誤判，導(dǎo)致定位精度難以提高。針對以上問題，本文中提出一種基于向量積同向技術(shù)的改進(jìn)APIT定位算法，該定位算法在PIT測試時(shí)無需通過與鄰居節(jié)點(diǎn)交換信息來模擬節(jié)點(diǎn)移動(dòng)，而是通過利用RSSI定位算法對未知節(jié)點(diǎn)進(jìn)行初步定位，然后利用數(shù)學(xué)中向量積方向作為判據(jù)來替代PIT測試法，從而提高節(jié)點(diǎn)的定位精度。

1 APIT定位算法

1.1 基本原理

Fig.1 Positioning principle of APIT

1.1.1 PIT測試法原理 APIT定位算法的理論基礎(chǔ)是PIT測試法，通過PIT測試法篩選出包含未知節(jié)點(diǎn)的信標(biāo)三角形，如圖2所示。M為未知節(jié)點(diǎn)，A,B,C為信標(biāo)節(jié)點(diǎn)，假設(shè)M沿某方向移動(dòng)時(shí)，同時(shí)遠(yuǎn)離或靠近A,B,C這3個(gè)點(diǎn)，則點(diǎn)M在△ABC外面，相反點(diǎn)M在△ABC內(nèi)部。

由于在靜態(tài)網(wǎng)絡(luò)中節(jié)點(diǎn)是固定的，因此通過未知節(jié)點(diǎn)與其鄰節(jié)點(diǎn)間的信息交換來模擬未知節(jié)點(diǎn)移動(dòng)。

Fig.2 Principle of PITa—unknown nodes inside b—unknown nodes outside

假設(shè)未知節(jié)點(diǎn)M接收到信標(biāo)節(jié)點(diǎn)A,B,C的RSSI值分別為RA,RB,RC，那么未知節(jié)點(diǎn)M移動(dòng)至某一鄰居節(jié)點(diǎn)時(shí)，收到A,B,C的RSSI值就是該鄰居節(jié)點(diǎn)在此處收到A,B,C的RSSI值，分別為RA′,RB′,RC′，當(dāng)存在某一鄰居節(jié)點(diǎn)使得下面(1)式或(2)式成立時(shí)，則點(diǎn)M在△ABC外面，相反點(diǎn)M在△ABC內(nèi)部。

(2)

1.1.2 PIT測試法誤判問題 在節(jié)點(diǎn)分布稀疏或不均勻時(shí)PIT測試法很容易產(chǎn)生誤判。如圖3a所示，當(dāng)未知節(jié)點(diǎn)M與鄰居節(jié)點(diǎn)3交換信息時(shí)，判斷M在三角形外面，產(chǎn)生內(nèi)判外(in-to-out)的誤判；如圖3b所示，當(dāng)未知節(jié)點(diǎn)M與鄰居節(jié)點(diǎn)3或4交換信息時(shí)，判斷M在三角形里面，產(chǎn)生外判內(nèi)(out-to-in)的誤判。而in-to-out和out-to-in是造成APIT定位誤差的主要因素，因此，對APIT定位算法進(jìn)行改進(jìn)的關(guān)鍵是解決PIT測試法的誤判問題。

Fig.3 Misjudgment situationa—in-to-out b—out-to-in

1.2 APIT定位算法步驟

(1)信標(biāo)節(jié)點(diǎn)以廣播的方式發(fā)送自身信息(坐標(biāo)、信號(hào)強(qiáng)度等)，然后未知節(jié)點(diǎn)收集所有能與之通信的節(jié)點(diǎn)的信息；(2)未知節(jié)點(diǎn)與鄰節(jié)點(diǎn)之間交換信息，篩選出包含未知節(jié)點(diǎn)的信標(biāo)三角形；(3)求出篩選出的信標(biāo)三角形重疊區(qū)域，計(jì)算出其質(zhì)心位置作為未知節(jié)點(diǎn)的位置；(4)完成定位。

2 基于向量積同向技術(shù)的改進(jìn)APIT定位算法

2.1 算法基本原理

針對in-to-out和out-to-in誤判問題，本文中提出一種利用向量積方向是否相同來判斷未知節(jié)點(diǎn)是否在信標(biāo)三角形內(nèi)部的改進(jìn)APIT定位算法。

定義1：如圖4所示，A,B,C為信標(biāo)三角形的3個(gè)頂點(diǎn)，M為未知節(jié)點(diǎn)，當(dāng)同時(shí)滿足以下3個(gè)條件時(shí)，未知節(jié)點(diǎn)M在信標(biāo)三角形ABC內(nèi)部，否則未知節(jié)點(diǎn)M在信標(biāo)三角形ABC外面:(1)點(diǎn)M和點(diǎn)A在BC的同一側(cè)；(2)點(diǎn)M和點(diǎn)B在AC的同一側(cè)；(3)點(diǎn)M和點(diǎn)C在AB的同一側(cè)。

Fig.4 Unknown node outside and inside the beacon trianglea—inside b—outside

Fig.5 Vector product directiona—inside b—outside

Fig.6 To determine whether the unknown node is within the beacon triangle or not

a—inside b—outside

如圖6所示，A,B,C為信標(biāo)三角形3個(gè)頂點(diǎn)，M為未知節(jié)點(diǎn)，假設(shè)A,B,C,M坐標(biāo)分別為(xA,yA),(xB,yB),(xC,yC)，(xM,yM)，判斷M是否在△ABC內(nèi)，主要分以下3個(gè)步驟。

2.1.1 判斷點(diǎn)M和點(diǎn)C是否在AB同一側(cè)

(5)

(yB-yA)(xM-xA)

(6)

(yB-yA)(xC-xA)

(7)

2.1.2 判斷點(diǎn)M和點(diǎn)B是否在AC同一側(cè)

(yA-yC)(xM-xC)

(11)

(yA-yC)(xB-xC)

(12)

2.1.3 判斷點(diǎn)M和點(diǎn)A是否在BC同一側(cè)

(15)

(yC-yB)(xM-xB)

(16)

(yC-yB)(xA-xB)

(17)

根據(jù)定義1，如果點(diǎn)M和點(diǎn)A在BC的同一側(cè)；點(diǎn)M和點(diǎn)B在AC的同一側(cè)；點(diǎn)M和點(diǎn)C在AB的同一側(cè)。那么未知節(jié)點(diǎn)M則在信標(biāo)三角形內(nèi)部，否則未知節(jié)點(diǎn)M在信標(biāo)三角形外面。

如圖6a所示，滿足定義1和定義2，故未知節(jié)點(diǎn)M在信標(biāo)三角形內(nèi)部；如圖6b所示，不滿足定義1和定義2，故未知節(jié)點(diǎn)M在信標(biāo)△ABC外面。

本文中提出的改進(jìn)APIT算法最大優(yōu)勢是避免了未知節(jié)點(diǎn)與鄰居節(jié)點(diǎn)信息交換時(shí)產(chǎn)生的in-to-out和out-to-in誤判，并且不存在邊界點(diǎn)誤判的問題。

2.2 改進(jìn)APIT定位算法步驟

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

為了分析改進(jìn)APIT定位算法的性能，本文中使用MATLAB 2016b對該算法進(jìn)行仿真。仿真環(huán)境設(shè)定在一個(gè)1000m×1000m的2維平面內(nèi)，隨機(jī)分布300個(gè)節(jié)點(diǎn)，節(jié)點(diǎn)通信半徑設(shè)置為200m，信標(biāo)節(jié)點(diǎn)所占比例設(shè)置為0.2。首先對原APIT定位算法和改進(jìn)APIT定位算法進(jìn)行仿真對比，然后通過對不同參量設(shè)置不同值將APIT和改進(jìn)APIT定位算法進(jìn)行仿真對比。針對各種情況分別進(jìn)行50次仿真，取這50次仿真的平均值作為最后的仿真結(jié)果。

圖7是在節(jié)點(diǎn)通信半徑為200m、信標(biāo)節(jié)點(diǎn)占總節(jié)點(diǎn)比例為0.2的情況下，APIT定位算法與改進(jìn)APIT定位算法的仿真結(jié)果。圖中星號(hào)為信標(biāo)節(jié)點(diǎn)，圓圈為未知節(jié)點(diǎn)，直線為未知節(jié)點(diǎn)實(shí)際位置和定位位置的距離差。對比圖7b和圖7c可知，基于向量積同向技術(shù)的改進(jìn)APIT算法定位精度高于傳統(tǒng)APIT算法的定位精度。

為了便于對比APIT定位算法和改進(jìn)APIT定位算法的定位誤差，這里將兩種定位算法定位誤差整合到同一折線圖中，圖8中，橫坐標(biāo)為未知節(jié)點(diǎn)編號(hào)，縱坐標(biāo)為定位的誤差。

Fig.7 Positioning error of APIT and the improved APIT

a—node map b—positioning error of APIT c—positioning error of the improved APIT

從圖8a和圖8b中可以更清晰地看出，基于向量積同向技術(shù)的改進(jìn)APIT算法定位精度高于傳統(tǒng)APIT算法的定位精度。但仍然存在個(gè)別未知節(jié)點(diǎn)定位精度差，例如編號(hào)為212的節(jié)點(diǎn)，造成這種情況的原因是由于改進(jìn)算法篩選信標(biāo)三角形時(shí)準(zhǔn)確度更高，篩選到的信標(biāo)三角形更多，那么這些信標(biāo)三角形重疊區(qū)域就更大了，質(zhì)心位置則越偏離真實(shí)位置，因此定位精度就越差。但這種情況是極少數(shù)的，總體來說改進(jìn)APIT定位算法的定位精度更高。

圖9是APIT定位算法和基于向量積同向技術(shù)的改進(jìn)APIT定位算法在信標(biāo)節(jié)點(diǎn)不同比例下的定位誤差圖。分析圖9可以看出,隨著信標(biāo)節(jié)點(diǎn)比例的增加，定位誤差隨之減小，且改進(jìn)APIT定位算法的定位精度更高。通過以上分析，說明改進(jìn)APIT定位算法的性能優(yōu)于傳統(tǒng)APIT定位算法。

Fig.8 Positioning error integration of APIT and the improved APIT

a—comparison of 61～175 positioning error b—comparison of 176～300 positioning error

Fig.9 Comparison of positioning error with different proportions of beacon nodes

4 結(jié) 論

本文中從APIT定位算法內(nèi)點(diǎn)測試法產(chǎn)生的in-to-out和out-to-in誤判作為切入點(diǎn)，提出基于三角形同向技術(shù)的改進(jìn)APIT定位算法，該算法將數(shù)學(xué)中向量積知識(shí)和RSSI技術(shù)相結(jié)合提出新的內(nèi)點(diǎn)測試法，仿真實(shí)驗(yàn)表明：改進(jìn)的APIT定位算法比APIT定位算法在信標(biāo)節(jié)點(diǎn)比例不同時(shí)定位誤差更小、精度更高、算法簡單，且不存在邊界點(diǎn)誤判問題，仿真過程接近實(shí)際環(huán)境，在現(xiàn)實(shí)環(huán)境中有很大的實(shí)用性。當(dāng)然，影響定位精度的因素還有節(jié)點(diǎn)分布、節(jié)點(diǎn)密度以及通信半徑等，這將是下一步的研究工作。

[1] WU M, CHENG L L.Wireless sensor network node and realization method[J]. Instrument Technique and Sensor,2008,37(12) :14-16 (in Chinese).

[2] LONG L, LI Z F. 3-D position measurement algorithm based on laser displacement sensors[J].Laser Technology,2017,41(4):531-536(in Chinese).

[3] WU Ch, YUAN Y B,ZHANG M Y. Plane target positioning based on reflection intensity and K-means clustering method [J].Laser Technology, 2015,39(3):341-343(in Chinese).

[4] JIN R Ch，CHE Zh P,XU H,etal．RSSI-based localization algorithm for outliers suppression in wireless sensor networks.[J].Wireless Networks,2015,21(8):2561-2569.

[5] HE T, HUANG Ch D, BLUM B M,etal. Range-free localization schemes in large scale sensor networks[C]//Proceedings of the 9th Annual International Conference on Mobile Computing and Networking, MOBICOM’2003.New York,USA: ACM Press, 2003: 81-95.

[6] YAO Y， HAN Q， XU X，etal. A RSSI-based distributed weighted search localization algorithm for WSNs [J].International Journal of Distributed Sensor Networks, 2015, 11(4):1-11.

[7] XIONG H, CHEN Z， AN W，etal. Robust TDOA localization algorithm for asynchronous wireless sensor networks [J].International Journal of Distributed Sensor Networks, 2015, 11(5):1-10.

[8] YANG T Ch, JIN L, CHENG J.An improvement CHAN algorithm based on TOA position[J].Acta Electronica Sinica,2009,37(4):819-822 (in Chinese).

[9] MAO Y Y, LI M Y, ZHANG B J. AOA location algorithm based on RBF neural network[J].Journal of Computer Applications, 2008 , 28 (1) :1-3 (in Chinese).

[10] ZENG Zh L, GAO J M, WANG J H.Corrected range weighted centroid localization algorithm based on RSSI for WSN [M].Melbourne,Australia:Information Systems and Computer Engineering, 2010:453-460.

[11] TOMIC S， MEZEI I. Improvements of DV-Hop localization algorithm for wireless sensor networks [J].Telecommunication Systems,2015,61(1):93-106.

[12] LIU Y, CHEN J, XU Z.Improved DV-Hop localization algorithm based on bat algorithm in wireless sensor networks[J].KSII Transactions on Internet and Information Systems,2016,11(1):215-236.

[13] KUMAR S,LOBIYAL D K.Novel DV-Hop localization algorithm for wireless sensor networks[J].Telecommunication Systems,2016,64(3):509-524.

[14] LI X, YAN L, PAN W,etal. Optimization of DV-Hop localization algorithm in hybrid optical wireless sensor networks[J].Journal of Heuristics,2014,21(2):177-195.

[15] AN W X,ZHAO J M,LI D A.Research of localization algorithm for wireless sensor networks based on Amorphous[J].Transducer and Microsystem Technologies,2013,32(2):33-35 (in Chinese).

[16] DOHERTY L,PISTER K S J， GHAOUI L E．Convex position estimation in wireless sensor networks[J].Infocom Twentieth Joint Conference of the IEEE Computer & Communications Societies,2001,3(3): 1655-1663.