改進(jìn)內(nèi)測點(diǎn)測試算法在無線傳感網(wǎng)絡(luò)中的定位研究

龔　健

（廣州鐵路職業(yè)技術(shù)學(xué)院，廣州　510430）

改進(jìn)內(nèi)測點(diǎn)測試算法在無線傳感網(wǎng)絡(luò)中的定位研究

龔健

（廣州鐵路職業(yè)技術(shù)學(xué)院，廣州510430）

在無線傳感網(wǎng)絡(luò)定位算法中，三角形內(nèi)點(diǎn)測試APIT算法和最佳三角內(nèi)測點(diǎn)PIT算法受節(jié)點(diǎn)密度影響較大，在特定情況下會出現(xiàn)In-To-Out Error和Out-To-In Error錯誤，導(dǎo)致目的節(jié)點(diǎn)實(shí)際坐標(biāo)往往與三角重疊區(qū)域質(zhì)心位置相差較遠(yuǎn)，影響定位精準(zhǔn)度；新算法提出利用內(nèi)測點(diǎn)三角成形面積有效檢測和避免上述兩類錯誤，并在重疊區(qū)域采取指紋分布概率以投票方式計算目的節(jié)點(diǎn)坐標(biāo)；仿真實(shí)驗(yàn)證明，新算法受節(jié)點(diǎn)密度影響較小，擁有更高的定位精度和準(zhǔn)確性。

三角形內(nèi)點(diǎn)測試；In-To-Out Error；Out-To-In Error；RSSI

0　引言

無線傳感器網(wǎng)絡(luò)定位算法分為基于測距和無需測距算法兩類［1-2］。三角形內(nèi)點(diǎn)測試APIT算法屬于無需測距算法，與同類基于跳數(shù)的DV-Hop算法、凸規(guī)劃定位算法、改進(jìn)跳數(shù)測距的Amorphous算法和最佳三角內(nèi)測點(diǎn)PIT算法相比，在同等條件下其定位精度較高，對節(jié)點(diǎn)分布密度依賴性較小，滿足低開銷、低能耗工程需求，在無線傳感網(wǎng)絡(luò)定位中應(yīng)用最廣。

APIT算法在定位過程中，網(wǎng)絡(luò)中各節(jié)點(diǎn)周期性廣播自身位置坐標(biāo)信息。目的錨節(jié)點(diǎn)根據(jù)接收信號強(qiáng)度計算彼此之間的距離和位置，以此判斷該節(jié)點(diǎn)是否在其他節(jié)點(diǎn)組成的三角形內(nèi)。設(shè)集合有n個節(jié)點(diǎn)，則存在C3n種選取方式組成不同的三角形，窮盡所有組合并逐一測試是否位于每個三角形內(nèi)部，找出滿足條件的所有三角形并利用網(wǎng)格掃描方法計算重疊區(qū)域質(zhì)心，從而定位目的節(jié)點(diǎn)。網(wǎng)格掃描方式見圖1。

APIT算法定位精度依賴于節(jié)點(diǎn)密度，節(jié)點(diǎn)越多，定位精度越高，當(dāng)鄰近節(jié)點(diǎn)較疏或不能組成三角形時容易產(chǎn)生較大誤差，這是由于算法的In-To-Out和Out-To-In兩種計算錯誤造成的［3］。

圖1　APIT定位算法

1　In-To-Out Error和Out-To-In Error

1.1In-To-Out Error

目的節(jié)點(diǎn)M和相鄰節(jié)點(diǎn)1、2、3都處于△ABC內(nèi)部，節(jié)點(diǎn)3在△ABC外部并且與節(jié)點(diǎn)1、2、3的距離大于節(jié)點(diǎn)M的距離時，APIT根據(jù)算法會誤將M判為在△ABC外部，導(dǎo)致In-To-Out Error，又稱為邊界效應(yīng)見圖2。

1.2Out-To-In Error

目的節(jié)點(diǎn)M和相鄰節(jié)點(diǎn)1、2、3都處于△ABC外部，其中節(jié)點(diǎn)2、4較目的節(jié)點(diǎn)M更靠近三角形的邊AB，此時節(jié)點(diǎn)2接收到來自A的信號強(qiáng)度和節(jié)點(diǎn)4接收到來自B、C的信號強(qiáng)度都高于其他節(jié)點(diǎn)，APIT根據(jù)算法會誤將M判為在△ABC內(nèi)部，導(dǎo)致Out-To-In Error，見圖3。

In-To-Out Error和Out-To-In Error兩種錯誤是由于節(jié)點(diǎn)分布不均造成的。APIT遍歷找出所有三角形的重疊區(qū)域，當(dāng)目的節(jié)點(diǎn)距離重疊區(qū)域質(zhì)心較遠(yuǎn)時，算法只能在有限方向上進(jìn)行判斷，產(chǎn)生兩類錯誤，導(dǎo)致較大定位誤差［45］。因此，如何發(fā)現(xiàn)和避免In-To-Out Error和Out-To-In Error兩類錯誤是提高APIT定位精度的有效方式，也是目前亟待解決的問題［67］。

圖2　In-To-Out Error

圖3　Out-To-In Error

2　新算法設(shè)計

新算法利用內(nèi)測點(diǎn)三角成形面積判斷內(nèi)測點(diǎn)所處△ABC的位置，以此發(fā)現(xiàn)上述兩類錯誤的產(chǎn)生。當(dāng)新算法對每個三角內(nèi)測點(diǎn)位置判斷和APIT算法不同時，即判為發(fā)生In-To-Out Error和Out-To-In Error。此時若仍簡單的利用網(wǎng)格掃描計算重疊區(qū)域質(zhì)心位置必會產(chǎn)生較大誤差［89］。新算法采用在三角重疊區(qū)域基于指紋分布概率對重疊區(qū)域網(wǎng)格進(jìn)行投票，以此估算目的節(jié)點(diǎn)坐標(biāo)。

2.1內(nèi)測點(diǎn)位置的判斷

目的節(jié)點(diǎn)M與A、B、C可組成3個三角形△AMC、△BMC和△AMB。若面積S△AMC+S△BMC+S△AMB=S△ABC，則即可判斷M在△ABC內(nèi)部，反之，若S△AMC+S△BMC+S△AMB＞S△ABC，則M在△ABC外部，見圖4所示，以此發(fā)現(xiàn)APIT算法中可能出現(xiàn)的兩類錯誤。

圖4　內(nèi)測點(diǎn)位置判斷示意圖

2.2基于指紋分布概率的投票方式

第一步：根據(jù)RSSI接收信號強(qiáng)度初始化RADAR損耗模型公式為：

第二步：以三角重疊區(qū)域質(zhì)心O（Xo，Yo）為中心，建立直角坐標(biāo)系，然后在范圍內(nèi)進(jìn)行網(wǎng)格劃分以及初始化。

第三步：根據(jù)RADAR損耗模型建立重疊區(qū)域位置指紋強(qiáng)度概率，建立概率分布直方圖。如第i個網(wǎng)格接收到第k個節(jié)點(diǎn)的概率直方圖為HRssi，見圖5。

圖5　概率分布直方圖

定義C為第n個樣本測量次數(shù)，Pck是每個樣本接收到到鄰居節(jié)點(diǎn)指紋為Rssck的概率，則Pck概率為：

其中Count（RSSck）是同一樣本測量C次后的信號強(qiáng)度值為Rssck的出現(xiàn)次數(shù)。

第四步：設(shè)當(dāng)前網(wǎng)格坐標(biāo)為Lxy，信號強(qiáng)度為RSSxy，根據(jù)貝葉斯公式有：

其中：P（Lxy）在網(wǎng)格i內(nèi)均勻分布。

由于無線傳感網(wǎng)絡(luò)中的錨節(jié)點(diǎn)信號相互獨(dú)立，對于網(wǎng)絡(luò)中每個節(jié)點(diǎn)存在以下關(guān)系：

則P（Rssi|Ln）在網(wǎng)格i信號強(qiáng)度向量為Rssi的條件概率，其值為：

P（Rssi|Ln）=P（（Rssi1，Rssi2，…，Rssin）|Ln）（5）

第五步：在三角重疊區(qū)域網(wǎng)格內(nèi)根據(jù)P（Rssi|Ln）概率進(jìn)行投票。投票過程所有節(jié)點(diǎn)具有相同權(quán)重，若節(jié)點(diǎn)在網(wǎng)格P（Rssi|Ln）概率有效覆蓋范圍內(nèi)，則對其投票，格子票數(shù)越多，則越多三角形認(rèn)可目的節(jié)點(diǎn)位置，得票最多的網(wǎng)格顏色最深，該網(wǎng)格即為目的節(jié)點(diǎn)位置，見圖6。

2.3定位偏差

設(shè)l（x1，y1）為三角重疊區(qū)域A內(nèi)任意一點(diǎn)，l（x1，y1）∈A，

圖6　區(qū)域投票定位圖

j（x2，y2）為新算法計算的節(jié)點(diǎn)位置，定位偏差為：

則重疊區(qū)域A上的定位偏差滿足公式：

3　仿真測試

3.1測試環(huán)境

仿真環(huán)境采用基于網(wǎng)格節(jié)點(diǎn)放置模型，節(jié)點(diǎn)在100×100區(qū)域內(nèi)隨機(jī)分布，其中節(jié)點(diǎn)數(shù)量50，目的錨節(jié)點(diǎn)數(shù)10，節(jié)點(diǎn)通信半徑20，利用MATLAB7.0軟件對兩種算法仿真比較。為減少節(jié)點(diǎn)隨機(jī)分布導(dǎo)致的誤差，所有結(jié)果均為在同等參數(shù)下仿真20次的平均值。

3.2定位偏差測試

如圖7所示，3種算法定位偏差都隨測距距離增加而加大。其中PIT算法定位偏差最大，APIT次之，這兩種算法造成偏差的主要原因是受節(jié)點(diǎn)密度影響較大，節(jié)點(diǎn)分布不均會產(chǎn)生部分內(nèi)測點(diǎn)測試失敗的問題，導(dǎo)致In-To-Out Error和Out-To-In Error。內(nèi)測點(diǎn)測試失敗，目的節(jié)點(diǎn)實(shí)際位置必定和三角重疊區(qū)域質(zhì)心相差較遠(yuǎn)，此時求其質(zhì)心以計算節(jié)點(diǎn)坐標(biāo)已無太大意義。新算法偏差最小，這是由于新算法利用內(nèi)測點(diǎn)三角成形面積有效發(fā)現(xiàn)上述兩類錯誤的發(fā)生，并在重疊區(qū)域采取指紋分布概率以投票方式計算目的節(jié)點(diǎn)坐標(biāo)，定位結(jié)果最為精準(zhǔn)。3.3節(jié)點(diǎn)密度對算法的影響

圖7　定位偏差圖

目前，幾乎所有的定位算法都存在一個共性：定位偏差隨節(jié)點(diǎn)密度增大而減小。在圖8中，PIT和APIT算法的In-To-Out Error和Out-To-In Error受節(jié)點(diǎn)密度影響較大，當(dāng)節(jié)點(diǎn)較為稀疏時偏差較大。但隨著節(jié)點(diǎn)密度的增加，區(qū)域內(nèi)達(dá)15個節(jié)點(diǎn)以上時，三角形內(nèi)點(diǎn)測試可以參考更多的成形三角形加以參考，誤判率明顯降低，偏差都在3米以下。而新算法能有效避免兩類錯誤的發(fā)生，在同樣15個節(jié)點(diǎn)情況下，誤差保持在1米以內(nèi)。

圖8　節(jié)點(diǎn)密度對誤差的影響

4　結(jié)束語

新算法利用內(nèi)測點(diǎn)三角成形面積有效發(fā)現(xiàn)和避免In-To-Out Error和Out-To-In Error兩類錯誤的產(chǎn)生，并在三角重疊區(qū)域采取指紋分布概率以網(wǎng)格投票方式估算目的節(jié)點(diǎn)坐標(biāo)，受節(jié)點(diǎn)密度影響較小，算法更為科學(xué)。下一步工作將著眼于改進(jìn)傳統(tǒng)RADAR損耗模型以修正指紋概率分布，進(jìn)一步提高算法定位的精準(zhǔn)度。

［1］唐明虎，張長宏，昝風(fēng)彪.無線傳感器網(wǎng)絡(luò)APIT定位算法［J］.微型機(jī)與應(yīng)用，2010（21）：114-120.

［2］周四清，陳銳標(biāo).無線傳感器網(wǎng)絡(luò)APIT定位算法及其改進(jìn)［J］.計算機(jī)工程，2009（7）：275-279.

［3］徐云劍，郭艾寅.基于APIT的三維移動代理路由算法研究［J］.計算機(jī)應(yīng)用研究，2010（6）：142-146.

［4］韓彪，徐昌彪，袁海，等.無線傳感器網(wǎng)絡(luò)中一種改進(jìn)的APIT定位算法［J］.計算機(jī)工程與應(yīng)用，2008（04）：23-28.

［5］He T，Huang C D，Blumb M.Range-free localiza-tion schemes for large scale sensor networks［A］.Proc of the 9th An-nual International MobiCom［C］.2013，22（14）：163-170.

［6］Ganeriwal S，Kumar R，Srivastava M B.Timing-Sync Protocol for Sensor Network［A］.Proceedings of the 1st international conference on Embedded networked sensor systems［C］.2013，16（6）：328-332.

［7］Agrawal P，Ghosh R K，Das S K.Localization of wireless sensor nodes using proximity information［A］.Proc of the16th Int Conf on Computer Communications and Networks（ICCCN2007）［C］. 2007，19（7）：1232-1240.

［8］Niewiadomska SzynkiewiczE，Marks.Optimization Schemes for Wireless Sensor Networks Localization［J］.Int.J.Appl. Math.Comput.Sci.2009，4（2）：398-403.

［9］Lazos L，Poovendran R.HiRLoc：High-Resolution robust localization for wireless sensor networks［J］.IEEE Journal on Selected Areas in Communications.2006，15（4）：1896-1911.

Research on The Localization of Improved Triangle Measured Point Test Algorithm in Wireless Sensor Networks

Gong jian
（Guangzhou Institute of Railway Technology，Guangzhou510430，China）

In wireless sensor network localization algorithm，the triangular test APIT algorithm and optimal triangulation measured point PIT algorithm are influenced by the density of nodes，and can lead to error Out-To-In and error In-To-Out.When these two types errors occur，the coordinates of node are often different from the centric of the triangle.New algorithm put forwards use the triangular area to avoid these two kinds of errors，and calculation fingerprint distribution probability in overlapping area to locate nodes.Finally，simulation show that the new algorithm can avoid the above two kinds of errors effectively and has higher positioning accuracy.

triangle interior point test；In-To-Out error；Out-To-In error；RSSI

1671-4598（2016）05-0309-03

10.16526/j.cnki.11-4762/tp.2016.05.085

TP393

A

2015-11-08；

2016-01-04。

中國高等教育學(xué)會2011年教育科學(xué)研究年度專項(xiàng)課題。

龔?。?968-），男，碩士研究生，講師，主要從事計算機(jī)應(yīng)用和高等職業(yè)教育研究。