龔　健

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

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

龔健

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

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

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

0　引言

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

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

APIT算法定位精度依賴于節(jié)點密度，節(jié)點越多，定位精度越高，當(dāng)鄰近節(jié)點較疏或不能組成三角形時容易產(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é)點M和相鄰節(jié)點1、2、3都處于△ABC內(nèi)部，節(jié)點3在△ABC外部并且與節(jié)點1、2、3的距離大于節(jié)點M的距離時，APIT根據(jù)算法會誤將M判為在△ABC外部，導(dǎo)致In-To-Out Error，又稱為邊界效應(yīng)見圖2。

1.2Out-To-In Error

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

In-To-Out Error和Out-To-In Error兩種錯誤是由于節(jié)點分布不均造成的。APIT遍歷找出所有三角形的重疊區(qū)域，當(dāng)目的節(jié)點距離重疊區(qū)域質(zhì)心較遠時，算法只能在有限方向上進行判斷，產(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)測點三角成形面積判斷內(nèi)測點所處△ABC的位置，以此發(fā)現(xiàn)上述兩類錯誤的產(chǎn)生。當(dāng)新算法對每個三角內(nèi)測點位置判斷和APIT算法不同時，即判為發(fā)生In-To-Out Error和Out-To-In Error。此時若仍簡單的利用網(wǎng)格掃描計算重疊區(qū)域質(zhì)心位置必會產(chǎn)生較大誤差［89］。新算法采用在三角重疊區(qū)域基于指紋分布概率對重疊區(qū)域網(wǎng)格進行投票，以此估算目的節(jié)點坐標。

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

目的節(jié)點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)測點位置判斷示意圖

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

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

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

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

圖5　概率分布直方圖

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

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

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

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

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

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

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

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

2.3定位偏差

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

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

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

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

3　仿真測試

3.1測試環(huán)境

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

3.2定位偏差測試

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

圖7　定位偏差圖

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

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

4　結(jié)束語

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

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

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

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

［4］韓彪，徐昌彪，袁海，等.無線傳感器網(wǎng)絡(luò)中一種改進的APIT定位算法［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é)研究年度專項課題。

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