冀常鵬　豐竹松　華一陽(yáng)

1(遼寧工程技術(shù)大學(xué)電子與信息工程學(xué)院　遼寧 葫蘆島 125100)

2(遼寧工程技術(shù)大學(xué)研究生院　遼寧 葫蘆島 125100)

?

無線傳感器網(wǎng)絡(luò)APIT算法邊界效應(yīng)的改進(jìn)

冀常鵬1豐竹松2華一陽(yáng)1

1(遼寧工程技術(shù)大學(xué)電子與信息工程學(xué)院遼寧 葫蘆島 125100)

2(遼寧工程技術(shù)大學(xué)研究生院遼寧 葫蘆島 125100)

摘要在無線傳感器網(wǎng)絡(luò)中，針對(duì)APIT算法存在邊界效應(yīng)導(dǎo)致定位精度不足的問題，提出一種基于節(jié)點(diǎn)信號(hào)強(qiáng)度和的改進(jìn)定位算法SAPIT(sum of signal strength based APIT)。該算法在PIT測(cè)試前，先確定三角形內(nèi)所有節(jié)點(diǎn)收到三個(gè)錨節(jié)點(diǎn)信號(hào)強(qiáng)度和的最小值，利用該最小值排除引起邊界效應(yīng)的鄰居節(jié)點(diǎn)；然后結(jié)合PIT測(cè)試和網(wǎng)格掃描算法，確定待定位節(jié)點(diǎn)的坐標(biāo)位置。仿真結(jié)果表明，SAPIT算法降低了In-To-Out Error和Out-To-In Error的發(fā)生概率，有效地提高了節(jié)點(diǎn)的定位精度。

關(guān)鍵詞無線傳感器網(wǎng)絡(luò)邊界效應(yīng)信號(hào)強(qiáng)度和定位精度

IMPROVEMENT OF BOUNDARY EFFECTS OF APIT IN WSN

Ji Changpeng1Feng Zhusong2Hua Yiyang1

1(School of Electronic and Information Engineering,Liaoning Technical University,Huludao 125100,Liaoning,China)2(Institute of Graduate,Liaoning Technical University,Huludao 125100,Liaoning,China)

AbstractIn wireless sensor networks, for the problem that the boundary effects existing in APIT algorithm cause the lack of localisation precision, we proposed an improved localisation algorithm which is based on the sum of signal strength of nodes (SAPIT). The SAPIT algorithm determines the minimum sum of signal strength of three anchor nodes received by all the nodes in triangle before the PIT test. Then the algorithm uses the minimum sum to eliminate the neighbour nodes incurring the boundary effects. Finally, it combines PIT test with gird scanning algorithm to determine the coordinate positions of the unknown nodes. Simulation results showed that the SAPIT algorithm reduced the probabilities of occurrence of in-to-out error and out-to-in error, and effectively improved the precision of nodes localisation.

KeywordsWireless sensor networksBoundary effectsSum of signal strengthLocalisation precision

0引言

在無線傳感器網(wǎng)絡(luò)中存在著大量隨機(jī)分布的傳感器節(jié)點(diǎn)，每一節(jié)點(diǎn)都可作為一個(gè)獨(dú)立的數(shù)據(jù)采集器，對(duì)檢測(cè)區(qū)域進(jìn)行實(shí)時(shí)監(jiān)控。對(duì)節(jié)點(diǎn)返回的數(shù)據(jù)信息進(jìn)行處理時(shí)，如果節(jié)點(diǎn)的位置信息不能得到確定，那么采集的數(shù)據(jù)將失去意義。因此，傳感器節(jié)點(diǎn)的自定位問題成為無線傳感器網(wǎng)絡(luò)的重要研究?jī)?nèi)容之一。如今傳感器在實(shí)際中被廣泛應(yīng)用，如環(huán)境檢測(cè)、汽車跟蹤、地理標(biāo)記以及水下傳感器[1]，都需要將節(jié)點(diǎn)位置信息作為一項(xiàng)重要指標(biāo)。此外，節(jié)點(diǎn)的位置信息也被用于改進(jìn)網(wǎng)絡(luò)方案，譬如在基于路由協(xié)議的網(wǎng)絡(luò)中，位置的確定能省去路由遍歷的過程，從而節(jié)省尋找路由所用的時(shí)間和能量[2]。

目前存在的定位算法根據(jù)其是否需要測(cè)定節(jié)點(diǎn)間的距離分為兩大類：一類是基于測(cè)距的定位算法，代表算法有RSSI、TDOA、TOA和AOA等定位算法[3]；一類是非基于測(cè)距的定位算法[4]，常用算法有質(zhì)心算法、APIT算法和DV-hop算法等[5]?；跍y(cè)距的定位算法比非基于測(cè)距的定位算法的定位精度高，但同時(shí)對(duì)硬件有較高要求，成本也隨之增加。非基于測(cè)距的定位算法雖然定位精度稍低，但完全可以滿足實(shí)際需要，且對(duì)硬件要求較低，在成本和功耗方面均具有優(yōu)勢(shì)。因此，非基于測(cè)距的定位算法一直是研究的熱點(diǎn)。

APIT算法由He等人在2003年提出[6]，相比于其他非基于測(cè)距的定位算法，APIT算法由于定位精度高，通信開銷小等優(yōu)點(diǎn)而備受關(guān)注。但是APIT算法一直存在邊界效應(yīng)問題，即In-To-Out Error和Out-To-In Error。針對(duì)Out-To-In Error問題，周勇等人提出了三角形重心掃描算法[7]，而針對(duì)In-To-Out Error問題，韓彪[8]等人通過設(shè)置影響因子來減小誤差。由于改進(jìn)后誤差仍然較大，王新生[9]等人在前人改進(jìn)的基礎(chǔ)上，設(shè)置計(jì)數(shù)器來減小誤差，但該方法增加了能量損耗。文獻(xiàn)[10]利用三角形面積和對(duì)有效三角形進(jìn)行判斷，文獻(xiàn)[11]利用角度和對(duì)有效三角形進(jìn)行判斷，但兩種方法計(jì)算量很大，致使定位時(shí)間加長(zhǎng)[10,11]。文獻(xiàn)[12-14]通過結(jié)合其他定位算法進(jìn)行改進(jìn)，在提高定位精度的同時(shí)加大了算法的復(fù)雜程度。Chiti和姚艷等人分別從掃描算法上對(duì)APIT算法進(jìn)行改進(jìn)，沒從根本上解決邊界效應(yīng)帶來的誤差[15,16]。以上算法均對(duì)APIT算法進(jìn)行了改進(jìn)，在一定程度上減小了定位誤差，但都沒有同時(shí)對(duì)In-To-Out Error和Out-To-In Error進(jìn)行很好地解決。本文從引起邊界效應(yīng)的根源入手，對(duì)APIT算法進(jìn)行改進(jìn)，提出一種基于節(jié)點(diǎn)信號(hào)強(qiáng)度和的定位算法—SAPIT算法。該算法較好地解決了邊界效應(yīng)的問題，明顯提高了節(jié)點(diǎn)的定位精度。

1APIT算法分析

APIT算法的主要思想：在初始階段，未知節(jié)點(diǎn)先收集鄰居錨節(jié)點(diǎn)信息;然后通過判斷確定包含未知節(jié)點(diǎn)的三角形，把多個(gè)三角形形成的重疊區(qū)域的質(zhì)心作為未知節(jié)點(diǎn)的坐標(biāo)。

1.1APIT算法步驟

第一步信息收集階段。未知節(jié)點(diǎn)收集鄰居錨節(jié)點(diǎn)的信息，包括信號(hào)強(qiáng)度、坐標(biāo)等，同時(shí)鄰居節(jié)點(diǎn)之間交換所接收到的錨節(jié)點(diǎn)信息。

第二步PIT測(cè)試階段。用三角形內(nèi)點(diǎn)測(cè)試法判斷未知節(jié)點(diǎn)是否位于錨節(jié)點(diǎn)組成的三角形內(nèi)，重復(fù)進(jìn)行直至所有錨節(jié)點(diǎn)組合測(cè)試完畢。

第三步利用網(wǎng)格掃描算法得出三角形重疊部分，求出該重疊區(qū)域的質(zhì)心位置，以此作為待定位節(jié)點(diǎn)的坐標(biāo)[17,18]。

1.2APIT算法誤差分析

在APIT算法中，判斷未知節(jié)點(diǎn)是否位于錨節(jié)點(diǎn)組成的三角形內(nèi)部是算法的關(guān)鍵步驟。該步驟以三角形內(nèi)點(diǎn)測(cè)試法(PIT)作為理論依據(jù)，其定義如下：若點(diǎn)M位于三角形外部，則存在一個(gè)方向，使得點(diǎn)M沿此方向移動(dòng)時(shí)，能夠同時(shí)靠近或遠(yuǎn)離三角形的三個(gè)頂點(diǎn)A、B、C；否則，點(diǎn)M位于三角形內(nèi)部。

在上述PIT測(cè)試中，節(jié)點(diǎn)M被假定為可移動(dòng)的。但在實(shí)際傳感器網(wǎng)絡(luò)中，待定位節(jié)點(diǎn)大多是靜止的，這使得APIT測(cè)試應(yīng)運(yùn)而生。其定義如下：假設(shè)節(jié)點(diǎn)M的所有鄰居節(jié)點(diǎn)均不同時(shí)靠近或遠(yuǎn)離3個(gè)錨節(jié)點(diǎn)A、B、C，那么點(diǎn)M位于三角形內(nèi)部；否則，點(diǎn)M位于三角形外部。

在APIT算法中，要想判斷未知節(jié)點(diǎn)是否位于三角形內(nèi)部，必須通過與鄰居節(jié)點(diǎn)交換信息，這使得算法判斷結(jié)果與鄰居節(jié)點(diǎn)的分布密切相關(guān)。并且APIT只能判斷有限的方向，因此，在實(shí)際測(cè)試中，常出現(xiàn)將內(nèi)部節(jié)點(diǎn)判斷為外部節(jié)點(diǎn)(In-To-Out Error)或?qū)⑼獠抗?jié)點(diǎn)判斷為內(nèi)部節(jié)點(diǎn)(Out-To-In Error)的情況，統(tǒng)稱為邊界效應(yīng)[19,20]。

如圖1中(a)所示，節(jié)點(diǎn)M原本位于三角形內(nèi)部，但鄰居節(jié)點(diǎn)1從三個(gè)錨節(jié)點(diǎn)收到的信號(hào)強(qiáng)度值均小于M收到錨節(jié)點(diǎn)的信號(hào)強(qiáng)度值。根據(jù)APIT定義，判定M位于三角形外部，發(fā)生In-To-Out Error。由此可知，只有當(dāng)鄰居節(jié)點(diǎn)沒有移出三角形外部時(shí)，PIT測(cè)試才能成立。

如圖1中(b)所示，節(jié)點(diǎn)M原本位于三角形外部，與鄰居節(jié)點(diǎn)1、2對(duì)比后，沒有同時(shí)遠(yuǎn)離或者同時(shí)接近三個(gè)錨節(jié)點(diǎn)的鄰居節(jié)點(diǎn)。根據(jù)APIT定義，判定M位于三角形內(nèi)部，發(fā)生Out-To-In Error。這是由于鄰居節(jié)點(diǎn)數(shù)目過少，節(jié)點(diǎn)密度低造成的。

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

2SAPIT算法

通過對(duì)APIT算法分析可知，APIT算法產(chǎn)生誤差的主要原因是部分鄰居節(jié)點(diǎn)導(dǎo)致了邊界效應(yīng)。若能減少此類鄰居節(jié)點(diǎn)，則可以提高節(jié)點(diǎn)定位的精確度?；谶@一思想，本文提出一種基于信號(hào)強(qiáng)度和的改進(jìn)算法。該算法在PIT測(cè)試前，先確定三角形內(nèi)所有節(jié)點(diǎn)收到三個(gè)錨節(jié)點(diǎn)信號(hào)強(qiáng)度和的最小值，利用該最小值排除引起邊界效應(yīng)的鄰居節(jié)點(diǎn)，然后結(jié)合PIT測(cè)試和網(wǎng)格掃描算法，確定待定位節(jié)點(diǎn)的坐標(biāo)位置。

2.1傳播模型

無線電傳播模型分為規(guī)則傳播模型和不規(guī)則傳播模型。其中不規(guī)則傳播模型更加接近于現(xiàn)實(shí)傳播[21,22]。不規(guī)則傳播模型相比規(guī)則傳播模型，增加了相關(guān)參數(shù)，但對(duì)SAPIT算法理論推導(dǎo)沒有影響，因此選擇規(guī)則傳播模型作為該算法推導(dǎo)的基礎(chǔ)。規(guī)則傳播模型公式如下：

(1)

其中，PR(d)是距離發(fā)送節(jié)點(diǎn)d米處收到的信號(hào)強(qiáng)度，Pr為發(fā)送節(jié)點(diǎn)的發(fā)送功率，PL(do)是參考距離為d0米的路徑損耗。參照規(guī)則傳播模型的經(jīng)典取值，將η取為4，A=Pr-PL(do)，d0=1m，故可寫成：

PR(d)=A-40logd

(2)

2.2確定最小信號(hào)強(qiáng)度和

在三角形內(nèi)，若某一節(jié)點(diǎn)收到的三個(gè)錨節(jié)點(diǎn)信號(hào)強(qiáng)度之和最小，那么三角形內(nèi)任意節(jié)點(diǎn)信號(hào)強(qiáng)度和均大于該最小信號(hào)強(qiáng)度和。又由于信號(hào)在傳播過程中逐漸減小，那么三角形外任意節(jié)點(diǎn)收到的信號(hào)強(qiáng)度和均小于該最小信號(hào)強(qiáng)度和。在APIT算法中，產(chǎn)生誤差的主要原因在于鄰居節(jié)點(diǎn)的合法性(即是否會(huì)產(chǎn)生邊界效應(yīng))不能保證。而在SAPIT算法中應(yīng)用上述理論，可對(duì)鄰居節(jié)點(diǎn)的合法性進(jìn)行判斷，通過最小信號(hào)強(qiáng)度和能夠把不合法的鄰居節(jié)點(diǎn)排除，從而使PIT測(cè)試更加準(zhǔn)確。下面推出此最小信號(hào)強(qiáng)度和的位置所在。

若某點(diǎn)處的節(jié)點(diǎn)收到三個(gè)錨節(jié)點(diǎn)信號(hào)強(qiáng)度之和最小，其中di、dj、dk為此點(diǎn)到三個(gè)錨節(jié)點(diǎn)的實(shí)際距離，那么：

Pmin=PR1(di)+PR2(dj)+PR3(dk)

=3A-40log(di×dj×dk)

(3)

圖2　錨節(jié)點(diǎn)構(gòu)成銳角三角形

令S= di×dj×dk，當(dāng)P取最小值時(shí)，S取最大值。因此，要想求得Pmin，可以通過求Smax獲得。

為求錨節(jié)點(diǎn)組成的三角形內(nèi)的Smax，分別對(duì)可能形成的銳角三角形、直角三角形、鈍角三角形進(jìn)行分析，每類三角形各取5點(diǎn)作為參考。圖2-圖4為三類三角形示意圖，表1-表3為三類三角形S值表。

表1　銳角三角形各點(diǎn)S值

對(duì)10個(gè)銳角三角形各取50個(gè)點(diǎn)計(jì)算其S值，最終確定S的最大值點(diǎn)位于最長(zhǎng)邊的中點(diǎn)處。

圖3　錨節(jié)點(diǎn)構(gòu)成直角三角形

取點(diǎn)位置N(最長(zhǎng)邊中點(diǎn))O(直角邊一點(diǎn))L(直角邊AC一點(diǎn))E(三角形外一點(diǎn))J(三角形內(nèi)一點(diǎn))S=di×dj×dk21693.39198.88284.64165.85

對(duì)10個(gè)直角三角形各取50個(gè)點(diǎn)計(jì)算其S值，最終確定S的最大值點(diǎn)位于最長(zhǎng)邊的中點(diǎn)處。

圖4　錨節(jié)點(diǎn)構(gòu)成鈍角三角形

取點(diǎn)位置T(三角形最長(zhǎng)邊中點(diǎn))K(靠近T的點(diǎn))M(三角形邊一點(diǎn))L(三角形邊一點(diǎn))F(三角形外一點(diǎn))S=di×dj×dk128.29137.19118.9975.20187.38

對(duì)10個(gè)鈍角三角形各取50個(gè)點(diǎn)計(jì)算其S值，其最大值點(diǎn)并非位于最長(zhǎng)邊的中點(diǎn)處。三邊S值分布大體趨勢(shì)如圖5所示，從圖中可以看出，最大值點(diǎn)位于最長(zhǎng)邊的中點(diǎn)附近。

圖5　鈍角三角形三邊各點(diǎn)的S值(AB最長(zhǎng))

通過對(duì)三類三角形分析可知，當(dāng)錨節(jié)點(diǎn)構(gòu)成的三角形為銳角三角形或直角三角形時(shí)，Smax點(diǎn)位于三角形最長(zhǎng)邊的中點(diǎn)處；當(dāng)錨節(jié)點(diǎn)構(gòu)成的三角形為鈍角三角形時(shí)，Smax點(diǎn)位于最長(zhǎng)邊中點(diǎn)的附近，由于誤差比(Smax-S中)/Smax最大約為5%，對(duì)算法判定影響很小，因此誤差可忽略，仍將Smax點(diǎn)看作位于最長(zhǎng)邊的中點(diǎn)處。錨節(jié)點(diǎn)組成的三角形越不規(guī)則，S最大值點(diǎn)偏離最長(zhǎng)邊中點(diǎn)處的程度越大。但在傳感器網(wǎng)絡(luò)中，傳播模型大致為圓形，錨節(jié)點(diǎn)組成三角形相對(duì)規(guī)則。綜上所述，三角形最長(zhǎng)邊中點(diǎn)處的S值最大，同時(shí)信號(hào)強(qiáng)度和最小。因此取三角形最長(zhǎng)邊中點(diǎn)處的信號(hào)強(qiáng)度和為最小信號(hào)強(qiáng)度和。

2.3改進(jìn)算法的步驟

1) 在進(jìn)行PIT測(cè)試前，錨節(jié)點(diǎn)通過廣播向其通信范圍內(nèi)的所有未知節(jié)點(diǎn)發(fā)送坐標(biāo)、標(biāo)識(shí)號(hào)、信號(hào)強(qiáng)度等信息，節(jié)點(diǎn)在傳感器內(nèi)寄存所接收到的信息。表4為節(jié)點(diǎn)收到的錨節(jié)點(diǎn)信息，其中A、B、C表示錨節(jié)點(diǎn)，(X,Y)為錨節(jié)點(diǎn)的坐標(biāo)信息，SS為節(jié)點(diǎn)接收的錨節(jié)點(diǎn)信號(hào)強(qiáng)度值。

表4　接收的錨節(jié)點(diǎn)信息

2) 在錨節(jié)點(diǎn)廣播信息后，待定位節(jié)點(diǎn)同其通信范圍的鄰居節(jié)點(diǎn)交換并存儲(chǔ)節(jié)點(diǎn)信息。表5為交換后的信息表。

表5　信息交換后節(jié)點(diǎn)的信息

3) 待定位節(jié)點(diǎn)收到廣播信息后，從接收到信號(hào)的所有錨節(jié)點(diǎn)中任意選取3個(gè)，計(jì)算所組成的三角形各邊長(zhǎng)以獲得最長(zhǎng)邊。求其中點(diǎn)坐標(biāo)，計(jì)算中點(diǎn)到三個(gè)錨節(jié)點(diǎn)距離，然后通過傳播模型計(jì)算三角形內(nèi)最小信號(hào)強(qiáng)度和。過程如下:anchor_i(xi，yi), anchor_j(xj，yj),anchor_k(xk，yk)分別為錨節(jié)點(diǎn)坐標(biāo)。

(4)

比較Dij、Dik、Djk，若Dij≥Dik≥Djk，取Dij中點(diǎn)M的坐標(biāo)為：

(5)

計(jì)算：

(6)

求得：

Pmin=PR1(Dmi)+PR2(Dmj)+PR3(Dmk)

=3A-40log(Dmi×Dmj×Dmk)

(7)

4) 確定Pmin后，將鄰居節(jié)點(diǎn)收到的三個(gè)錨節(jié)點(diǎn)信號(hào)強(qiáng)度相加，同最小信號(hào)強(qiáng)度和Pmin作比較。若鄰居節(jié)點(diǎn)的信號(hào)強(qiáng)度和滿足同時(shí)大于或同時(shí)小于該最小信號(hào)強(qiáng)度和，則進(jìn)行PIT測(cè)試。若不滿足，則對(duì)不滿足的鄰居節(jié)點(diǎn)進(jìn)行下一組錨節(jié)點(diǎn)測(cè)試準(zhǔn)備。重復(fù)步驟3)、步驟4)，直到所有錨節(jié)點(diǎn)組合測(cè)試完畢。

5) 利用網(wǎng)格掃描算法找出三角形重疊部分，對(duì)重疊區(qū)域求其質(zhì)心作為待定位節(jié)點(diǎn)的坐標(biāo)。

3算法仿真

本文采用MATLAB軟件對(duì)SAPIT算法和APIT算法進(jìn)行仿真，算法流程如圖6所示。

圖6　算法流程圖

1) 傳感器節(jié)點(diǎn)部署區(qū)域?yàn)?000 m×1000 m的正方形區(qū)域。

2) 300個(gè)節(jié)點(diǎn)隨機(jī)分布在網(wǎng)絡(luò)區(qū)域，普通節(jié)點(diǎn)的通信半徑為200 m，錨節(jié)點(diǎn)的通信半徑為普通節(jié)點(diǎn)的2倍，即400 m。

網(wǎng)絡(luò)連通度：網(wǎng)絡(luò)連通度表示在未知節(jié)點(diǎn)通信范圍內(nèi)的鄰居節(jié)點(diǎn)的個(gè)數(shù)。

圖7是錨節(jié)點(diǎn)個(gè)數(shù)為90，節(jié)點(diǎn)總數(shù)為300的隨機(jī)分布圖；圖8和圖9分別是用APIT算法和SAPIT算法得到的定位誤差圖。

將圖8和圖9進(jìn)行對(duì)比可以發(fā)現(xiàn)，相比于APIT算法，SAPIT算法的定位誤差更小。在APIT算法中，由于存在較嚴(yán)重的邊界效應(yīng)，導(dǎo)致PIT測(cè)試不準(zhǔn)確，有效三角形判斷錯(cuò)誤，從而產(chǎn)生多個(gè)重疊區(qū)域。這使得APIT算法的定位誤差不僅表現(xiàn)為數(shù)值較大，而且具有多個(gè)方向值。SAPIT算法通過判斷鄰居節(jié)點(diǎn)的合法性，在很大程度上抑制了邊界效應(yīng)的發(fā)生，使PIT測(cè)試更加準(zhǔn)確，重疊區(qū)域較好地反映了節(jié)點(diǎn)的實(shí)際位置，使定位更加精準(zhǔn)。

圖10為APIT算法和SAPIT算法在不同網(wǎng)絡(luò)連通度下歸一化的平均誤差(定位誤差和通信半徑之比)的比較。

圖7　節(jié)點(diǎn)分布圖　　　　　　圖8　APIT定位誤差圖

圖9　SAPIT定位誤差圖　　　圖10　不同連通度下的誤差

從圖10可以看出，在連通度較低的情況下，SAPIT算法比APIT算法定位精度要高，此時(shí)影響定位精度的因素絕大部分是 Out-To-In Error，這說明SAPIT算法在一定情況下有效地抑制了Out-To-In Error，具體情況如圖11所示。

隨著網(wǎng)絡(luò)連通度的增加，Out-To-In Error對(duì)精度的影響程度減小，In-To-Out Error對(duì)精度影響程度加大。從圖10可以看出，隨著連通度增加，APIT算法的定位誤差出現(xiàn)反彈現(xiàn)象，這是由于隨著鄰居節(jié)點(diǎn)的增加，致使APIT算法發(fā)生In-To-Out Error概率增大，從而導(dǎo)致短時(shí)間內(nèi)誤差增大。而SAPIT算法的定位誤差沒有出現(xiàn)反彈現(xiàn)象，這是由于在PIT測(cè)試前，通過把鄰居節(jié)點(diǎn)的合法性進(jìn)行判定，把不符合要求的鄰居節(jié)點(diǎn)排除，再進(jìn)行PIT測(cè)試，避免了大部分In-To-Out Error，較好地控制了反彈現(xiàn)象。從圖10中還可以看出，在網(wǎng)絡(luò)連通度達(dá)到10以后，SAPIT算法定位精度明顯高于APIT算法定位精度，說明對(duì)In-To-Out Error很好地解決，大大提高了定位精度。

圖12是節(jié)點(diǎn)總數(shù)為300個(gè)，不同錨節(jié)點(diǎn)個(gè)數(shù)的情況下兩種算法歸一化的平均誤差(定位誤差和通信半徑之比)的比較。

圖11　特殊的Out-To-In Error　圖12　不同錨節(jié)點(diǎn)數(shù)目下的誤差

圖12表明，當(dāng)錨節(jié)點(diǎn)個(gè)數(shù)占總體比為10%左右時(shí)，APIT算法和SAPIT算法定位誤差都較大。這是由于錨節(jié)點(diǎn)比例較小，很多未知節(jié)點(diǎn)不能收到錨節(jié)點(diǎn)信息所導(dǎo)致的。當(dāng)錨節(jié)點(diǎn)數(shù)目逐漸增多，可以看到SAPIT算法定位精度有顯著提升。其原因是SAPIT算法有效地解決了In-To-Out Error，并在一定程度上減少了Out-To-In Error，使有效三角形的數(shù)量增多，錯(cuò)誤三角形的數(shù)量減少，三角形重疊部分質(zhì)心很好地反映了未知節(jié)點(diǎn)的具體位置。在仿真實(shí)驗(yàn)中，隨著錨節(jié)點(diǎn)數(shù)目的增加，定位時(shí)間加長(zhǎng)，故選取最大錨節(jié)點(diǎn)個(gè)數(shù)占總體比例的50%，相較于APIT算法，SAPIT算法將定位精度提高了14%左右。

4結(jié)語(yǔ)

本文針對(duì)APIT算法中存在In-To-Out Error和Out-To-In Error，提出了一種基于節(jié)點(diǎn)信號(hào)強(qiáng)度和的SAPIT算法。仿真結(jié)果表明，SAPIT算法較于APIT算法，有效地提高了定位精度。相較于其他的APIT改進(jìn)算法，SAPIT算法不需要結(jié)合其他定位算法，也不需要進(jìn)行大量的計(jì)算和三角形分割，有效地節(jié)省了傳感器的能量，在實(shí)際應(yīng)用中具有廣闊前景。但SAPIT算法仍有不足，改進(jìn)算法只對(duì)一定情況下的Out-To-In Error進(jìn)行了修正。下一步的工作將集中針對(duì)Out-To-In Error做出更精確的修正，提高算法的定位精度。

參考文獻(xiàn)

[1] Guo Y,Liu Y.Localization for anchor-free underwater sensor networks[J].Computers & Electrical Engineering,2013,39(6):1812-1821.

[2] Zhang G,Ding Y,Xu J,et al.Tracking Algorithm of WSN Based on Improved Particle Filter[C]//2012 11thInternational Symposium on Distributed Computing and Applications to Business,Engineering & Science (DCABES).Guilin China:IEEE,2012:149-152.

[3] Zheng J,Wu C,Chu H,et al.An Improved RSSI Measurement In Wireless Sensor Networks[J].Procedia Engineering,2011(15):876-880.

[4] Luo X,Liu Y,Long C,et al.Range-free localization algorithms in wireless sensor networks[C]//Fifth International Conference on Machine Vision (ICMV 12).Wuhan China:SPIE,2013:87842A-8.

[5] Xiangqun L,Heng G,Linlin L.An improved APIT algorithm based on direction searching[C]//2009 5thInternational Conference on Wireless Communications,Net-working and Mobile Computing (WiCOM).Beijing China:IEEE,2009:1-4.

[6] He T,Huang C,Blum B M,et al.Range-free localization schemes for large scale sensor networks[C]//Proceedings of the 9thannual international conference on Mobile computing and networking.San Diego CAUSA:ACM,2003:81-95.

[7] 周勇,夏士雄,丁世飛,等.基于三角形重心掃描的改進(jìn)APIT無線傳感器網(wǎng)絡(luò)自定位算法[J].計(jì)算機(jī)研究與發(fā)展,2009,46(4):566-574.

[8] 韓彪,徐昌彪,袁海,等.無線傳感器網(wǎng)絡(luò)中一種改進(jìn)的APIT定位算法[J].計(jì)算機(jī)工程與應(yīng)用,2008,44(4):122-124.

[9] 王新生,廖世奇.基于區(qū)域分割的無線傳感器網(wǎng)絡(luò)定位算法[J].計(jì)算機(jī)應(yīng)用與軟件,2013,30(4):231-234.

[10] Wang J,Jin H.Improvement on APIT localization algorithms for wireless sensor networks[C]//International Conference on Networks Security,Wireless Communications and Trusted Computing (NSWCTC 2009).Wuhan.NY:IEEE,2009,1:719-723.

[11] Zeng F,Yu M,Zou C,et al.An Improved Point-in-Triangulation Localization Algorithm Based on Cosine Theorem[C]//Wireless Communications,Networking and Mobile Computing (WiCOM),2012 8th International Conference on.Shanghai China:IEEE,2012:1-4.

[12] Xiufang F,Huibo Q.Improvement and Simulation for a Localization Based on APIT[C]//2009 International Conference on Computer Technology and Development (ICCTD 2009).Kota Kinabalu Malaysia:IEEE,2009,2:68-72.

[13] 冀常鵬,陳美玲.無線傳感網(wǎng)絡(luò)APIT定位算法的改進(jìn)[J].儀表技術(shù)與傳感器,2012,8(8):84-86.

[14] 馮秀芳,崔秀鋒,祈會(huì)波.無線傳感器網(wǎng)絡(luò)中基于移動(dòng)錨節(jié)點(diǎn)的APIT的改進(jìn)定位算法[J].傳感技術(shù)學(xué)報(bào),2011,24(2):269-274.

[15] Chiti F,Pierucci L.API 2 T:a bit of improvement for applications in critical scenarios[C]//Proceedings of the 6th International Wireless Communications and Mobile Computing Conference.Chengdu China:ACM,2010:794-798.

[16] 姚艷,禹繼國(guó),郭強(qiáng).基于網(wǎng)格掃描的無線傳感器網(wǎng)絡(luò)定位算法[J].計(jì)算機(jī)工程,2012,38(9):86-89,96.

[17] Tan H,Liu F.Research and implementation of APIT positioning algorithm in WSN[C]//2012 9thInternational Conference on Fuzzy Systems and Knowledge Discovery (FSKD).Chongqing:IEEE,2012:2212-2215.

[18] 周四清,陳銳標(biāo).無線傳感器網(wǎng)絡(luò)APIT定位算法及其改進(jìn)[J].計(jì)算機(jī)工程,2009,35(7):87-89.

[19] Zhang S,Cao J,Zeng Y,et al.On accuracy of region based localization algorithms for wireless sensor networks[J].Computer Communications,2010,33(12):1391-1403.

[20] Chen B,Sun J,Xu W B,et al.A Mixed Localization Algorithm Based on RSSI and APIT with Fitness Analysis and Optimization[C]//2012 11th International Symposium on Distributed Computing and Applications to Business,Engineering & Science (DCABES).Guilin China:IEEE,2012:164-168.

[21] Chengxu F,Zhong L.A New Node Self-Localization Algorithm Based RSSI for Wireless Sensor Networks[C]//2013 Fifth International Conference on Computational and Information Sciences (ICCIS).Shiyan China:IEEE,2013:1616-1619.

[22] Wang S S,Shih K P,Chang C Y.Distributed direction-based localization in wireless sensor networks[J].Computer Communications,2007,30(6):1424-1439.

中圖分類號(hào)TP393

文獻(xiàn)標(biāo)識(shí)碼A

DOI:10.3969/j.issn.1000-386x.2016.02.025

收稿日期：2014-08-11。國(guó)家自然科學(xué)基金項(xiàng)目(61172144)。冀常鵬，教授，主研領(lǐng)域：計(jì)算機(jī)通信，無線網(wǎng)絡(luò)。豐竹松，碩士生。華一陽(yáng)，碩士生。