湯文亮,周琳穎

(華東交通大學(xué)軟件學(xué)院,南昌 330013)

?

基于三角形外接圓覆蓋的改進(jìn)APIT定位算法*

湯文亮*,周琳穎

(華東交通大學(xué)軟件學(xué)院,南昌 330013)

在無線傳感器網(wǎng)絡(luò)(WSN)中,傳感器節(jié)點定位在整個WSN體系中占有重要地位。APIT(Approximate Point-In-Triangulation Test近似三角形內(nèi)點測試法)相對于其他定位算法,具有硬件要求較低,定位性能較好等優(yōu)點。該算法在節(jié)點密集的網(wǎng)絡(luò)中,可以得到比較合理的定位精度,性能也相對穩(wěn)定。然而,在節(jié)點隨機(jī)分布的網(wǎng)絡(luò)中,其定位誤差是不容忽視的,且定位覆蓋率也相對較低。針對此問題,分析了APIT測試中的典型錯誤——三角形內(nèi)外覆蓋判斷錯誤以及產(chǎn)生的原因,提出了一種基于三角形外接圓覆蓋的改進(jìn)APIT算法——APICT(Approximate Point-In-Circumcircle Test)算法,并將此算法與APIT算法的仿真結(jié)果進(jìn)行比較,證明了此算法的定位精度具有顯著優(yōu)勢。

無線傳感器網(wǎng)絡(luò);定位算法;三角形外接圓覆蓋;定位精度;APIT算法;三角形內(nèi)外覆蓋

無線傳感器網(wǎng)絡(luò)[1]WSN(Wireless Sensor Networks)是由傳感器節(jié)點、感知對象和觀察者3個基本要素構(gòu)成。傳感器節(jié)點是WSN的基本組成實體。WSN的典型工作方式[2]為:大量無線傳感器網(wǎng)絡(luò)節(jié)點布設(shè)在監(jiān)測區(qū)域內(nèi)或監(jiān)測對象周圍,節(jié)點之間通過自組織快速形成一個感知網(wǎng)絡(luò)。

在WSN中,由于傳感器節(jié)點所采集的數(shù)據(jù)或探測的事件通常都需要有相對應(yīng)的地理信息作標(biāo)識,所以節(jié)點具備定位能力(如借助GPS或其他定位方法)對于許多應(yīng)用來說是一個非常重要的前提[3]。另外,節(jié)點的位置信息也常常被某些通信協(xié)議所利用,如利用節(jié)點間地理位置信息控制節(jié)點的發(fā)送功率以及約束波束的方向性,以降低節(jié)點通信能耗以及提高網(wǎng)絡(luò)容量;利用節(jié)點間的相對地理位置信息進(jìn)行路由決策,以降低路由控制開銷,提高網(wǎng)絡(luò)的能量有效性及可擴(kuò)展性。因此,節(jié)點定位技術(shù)在WSN中才尤為重要[4]。

由于傳感器網(wǎng)絡(luò)節(jié)點能量、存儲及處理能力的限制,必然要求定位算法是低復(fù)雜性的[5]。提高測距準(zhǔn)確度是提高節(jié)點定位精度的一個有效途徑,難點是測距的實現(xiàn)要受節(jié)點能量、硬件復(fù)雜度及體積的限制。而且在實際應(yīng)用中,測距準(zhǔn)確度是不可能無線提高的,這就需要從算法的角度來進(jìn)一步提高定位精度。

定位算法分類標(biāo)準(zhǔn)各異,學(xué)術(shù)界也已經(jīng)提出了很多基于WSN的節(jié)點定位算法,對算法的分類和總結(jié)也已經(jīng)出現(xiàn)在一些文獻(xiàn)中[6]。從算法采用的手段來看,可以分為兩大類:基于測距的定位機(jī)制和非基于測距的定位機(jī)制。第1種類型的算法基于節(jié)點間距離長度或方位角度信息,通常的測距技術(shù)包括基于時間的測距技術(shù)(TOA/TDOA)和基于接收信號能量的測距技術(shù)(RSSI)等,通過以上這些不同的測距技術(shù),獲得節(jié)點間點到點的距離或角度信息,然后再使用三角測量法、三邊測量法或多邊測量法等計算出節(jié)點位置;第2種類型的算法則無需距離和角度信息,而僅僅需要得到待定位節(jié)點與相鄰節(jié)點間的連通信息,然后實現(xiàn)節(jié)點定位,這類定位機(jī)制中的一些典型算法有質(zhì)心定位算法、APS算法、APIT算法等?；跍y距的定位技術(shù)一般定位精度較高,但是對無線傳感器網(wǎng)絡(luò)節(jié)點的硬件要求也比較高,因此在WSN的的現(xiàn)發(fā)展階段性價比不高;而非基于測距的定位算法雖然在對硬件要求不高且技術(shù)上實現(xiàn)簡單的情況下,能夠滿足大多數(shù)應(yīng)用的定位精度,但其產(chǎn)生的誤差也往往較大。APIT算法相對其他幾種基于距離無關(guān)定位算法,在定位精度、硬件成本、節(jié)點密度、節(jié)點分布等方面性能較好。

然而,在PIT測試中,APIT由于相鄰節(jié)點密度較低,在三角形內(nèi)外覆蓋問題上有時會做出錯誤的判斷,最終影響定位精度。

目前,雖然有很多學(xué)者做了APIT的改進(jìn)算法[7-10],但他們大多都是在節(jié)點密集程度較高的情況下,對定位精度進(jìn)行了各方面提高,而本文的APIT改進(jìn)算法是考慮了即使在節(jié)點密集程度不高的情況下,仍能保持較高的定位精度。

APIT算法中,待定位節(jié)點通過PIT測試得出自己可能位于3個錨節(jié)點所構(gòu)成的三角形區(qū)域集合后,便直接計算包含待定位節(jié)點的所有三角形交集的質(zhì)心,并將其作為自己的位置估算。然而,由于三角形內(nèi)外覆蓋判斷錯誤的存在,這些三角形區(qū)域并不總是包含待定位節(jié)點。因此PIT測試得到的位置估計往往精度不高。

然而針對以上問題,本文提出了一種基于三角形外接圓覆蓋的無線傳感器網(wǎng)絡(luò)定位算法APICT(Approximate Point-In-Circumcircle Test)。該算法不同于APIT中的PIT測試,不用通過相鄰節(jié)點間信息交換來模擬PIT測試的節(jié)點移動,而是通過PICT測試:求出3個錨節(jié)點所構(gòu)成的三角形的外接圓,并計算這個外接圓的圓心及半徑,然后測量待定位節(jié)點到圓心距離,最后通過與半徑的對比確定待定位節(jié)點是否在園內(nèi)。接著再用重復(fù)PICT(Point-In-Circumcircle Test)測試直到窮盡所有組合或達(dá)到所需定位精度,最后計算包含待定位節(jié)點的所有圓的交集質(zhì)心,最終得到的坐標(biāo)平均值便是所求節(jié)點位置。

1 APIT定位算法及不足之處

1.1 APIT定位算法

一般來說,WSN中有兩種節(jié)點:一種是已知自己物理位置信息的,稱為錨節(jié)點,另一種不知道自己物理位置信息的,需要定位的節(jié)點,稱為待定位節(jié)點或未知節(jié)點。

APIT算法的主要思想是:一個待定位節(jié)點任選3個相鄰錨節(jié)點,通過PIT測試自己是否位于它們所構(gòu)成的三角形中,使用不同參考節(jié)點組合重復(fù)測試直到窮盡所有組合或達(dá)到所需定位精度,最后計算包含待定位節(jié)點的所有三角形的交集質(zhì)心,并以這一點作為待定位節(jié)點位置。

APIT(Approximate PIT Test)算法理論基礎(chǔ)[11]是PIT:假如存在一個方向,沿著這個方向待定位節(jié)點M會同時遠(yuǎn)離或接近錨節(jié)點A、B、C,那么節(jié)點M位于△ABC外;否則,節(jié)點M位于△ABC內(nèi)。

為了在靜態(tài)網(wǎng)絡(luò)中執(zhí)行PIT測試,定義了APIT測試:假如節(jié)點M的相鄰節(jié)點沒有同時遠(yuǎn)離或靠近錨節(jié)點A、B、C,則節(jié)點M就在△ABC內(nèi);否則,在△ABC外。它利用WSN較高的節(jié)點密度來模擬節(jié)點移動,同時,在給定方向上,節(jié)點離錨節(jié)點越遠(yuǎn),接收信號強(qiáng)度越弱的無線傳播特性來判斷其與錨節(jié)點的遠(yuǎn)近。通過相鄰節(jié)點間信息交換來模擬PIT測試的節(jié)點移動,從而判斷自身是否在△ABC內(nèi)。使用不同錨節(jié)點組合重復(fù)PIT測試直至窮盡,最后計算包含待定位節(jié)點的區(qū)域的交集質(zhì)心,以此作為所求位置。

1.2 APIT定位算法的不足之處及原因分析

如上所述,由于APIT測試必須通過與相鄰節(jié)點間信息交換才能判斷是否位于三角形內(nèi),所以,APIT測試的正確性與周圍鄰居節(jié)點的分布情況密切相關(guān)[12]。然而在實際測試中,算法有時僅僅分析有限的幾個方向(依賴于相鄰節(jié)點數(shù)量),導(dǎo)致PIT測試有時會做出錯誤的判斷。

在圖1中,待定位節(jié)點M本應(yīng)位于△ABC外部,當(dāng)節(jié)點M通過與相鄰節(jié)點1交換信息,得知自己如果運(yùn)動至節(jié)點1處,則將遠(yuǎn)離錨節(jié)點B和C,但會接近錨節(jié)點A,與相鄰節(jié)點2,3和4通信和判斷過程類似。因此,根據(jù)PIT測試?yán)碚?最終判斷M位于△ABC內(nèi)部,這種錯誤簡稱為ETI(External To Internal)錯誤。

圖1 EIT錯誤

如圖2所示,待定位節(jié)點M本應(yīng)位于△ABC內(nèi)部,但由于某些相鄰節(jié)點在△ABC之外且離錨節(jié)點A、B和C都比較遠(yuǎn),所以,當(dāng)節(jié)點M通過與相鄰節(jié)點2交換信息,得知自己如果運(yùn)動至節(jié)點2處,則將同時遠(yuǎn)離錨節(jié)點A,B和C。因此,根據(jù)PIT測試?yán)碚?最終判斷M位于△ABC外部,這種錯誤簡稱為ITE(Internal To External)錯誤。

圖2 ITE錯誤

那么,產(chǎn)生這兩種錯誤的原因究竟是什么呢?

針對ETI錯誤,本文認(rèn)為主要原因是,相鄰節(jié)點的不規(guī)則部署,造成待定位節(jié)點在進(jìn)行PIT測試時有效的鄰居節(jié)點數(shù)目過少,最終導(dǎo)致EIT錯誤。

針對ITE錯誤,本文認(rèn)為究其原因主要是,節(jié)點密度過低,所以選擇了在△ABC之外且離錨節(jié)點A、B和C都較遠(yuǎn)的相鄰節(jié)點,最終導(dǎo)致ITE錯誤。

2 基于三角形外接圓覆蓋的改進(jìn)APIT定位算法

根據(jù)以上分析可知,待定位節(jié)點的相鄰節(jié)點的密度的高低是影響定位結(jié)果精確度的最大因素。故本文提出的APIC算法在相鄰節(jié)點密度較低的情況下仍能保持較高精確度。

2.1 三角形外接圓覆蓋的APICT算法

APICT算法具體實現(xiàn)步驟:

①假定節(jié)點M(x,y)是待定位節(jié)點,任取3個錨節(jié)點A(xA,yA)、B(xB,yB)和C(xC,yC),以A、B和C所構(gòu)成的△ABC,畫△ABC的外接圓C1,如圖3所示。

圖3 APICT算法圖解

②求出圓C1的圓心O(xO,yO)的坐標(biāo),以及O點到A、B和C任意一點的距離,即圓的半徑r。

③使用某種技術(shù)[13]實現(xiàn)M點到圓心O的測距,假設(shè)為l,通過對比,如果l<=r,則說明待定位節(jié)點M在圓C1內(nèi),否則在圓C1外。

④使用不同錨節(jié)點組合重復(fù)上述測試,直到窮盡所有組合或達(dá)到所需的定位精度。

⑤找出待定位節(jié)點所在的所有圓形區(qū)域的交集,最后估算這個區(qū)域的質(zhì)心,并以質(zhì)心作為未知節(jié)點的估計位置。

2.2 算法性能和效率分析

若不存在ETI和ITE錯誤,則文獻(xiàn)[14-15]中的APIT算法和本文中的APICT算法最終獲得的估計坐標(biāo)值相差不大。然而在實際測試中,這兩種錯誤都是很難避免的。試驗顯示[15]:APIT測試錯誤概率最壞情況下接近14%。

在算法執(zhí)行效率上,APIT算法由于要和鄰居節(jié)點多次交換信息,故需要多次和三角形3個頂點距離進(jìn)行比對;而APICT算法僅需要計算三角形外接圓圓心O和半徑r,而O和r只需通過三角形的3個頂點即可推算。所以,相比較而言,APICT算法具有更高的執(zhí)行效率。

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

3.1 APICT算法性能仿真分析

為了檢驗APICT定位算法的性能,本文使用MATLAB 7.0仿真工具對該算法進(jìn)行了仿真實驗。為方便體現(xiàn)錨節(jié)點數(shù)量及節(jié)點的分布情況對APICT算法定位精度的影響程度,本文將對APICT算法中單個節(jié)點的定位誤差率做分析。

如下圖4所示描述了錨節(jié)點數(shù)量在3～15時,節(jié)點定位誤差率。

圖4 APICT算法仿真(1)

由上圖分析得出:隨著錨節(jié)點數(shù)量的增加,APICT算法定位誤差率逐漸減小,并且在錨節(jié)點數(shù)量達(dá)到某個值時,趨于穩(wěn)定。

如下圖5所示描述了在節(jié)點數(shù)目100的情況下,節(jié)點定位誤差率與節(jié)點分布情況的關(guān)系。

圖5 APICT算法仿真(2)

由上圖分析得出:在節(jié)點數(shù)目固定的情況下,隨著錨節(jié)點比率的增加,APICT算法平均定位誤差率逐漸減小。由此說明:節(jié)點分布情況對定位誤差率有著很大的影響。

3.2 APICT和APIT算法性能分析比較

為方便理解,本文假設(shè)每單位面積內(nèi)布設(shè)1個節(jié)點的密度為1。如圖6描述了在100 m×100 m的通信區(qū)域內(nèi),節(jié)點密度從0.05到0.6時,APIT算法和APICT算法節(jié)點平均定位誤差率的比較。

圖6 APICT與APIT算法仿真比較

由圖可知,在節(jié)點密度改變的條件下,兩種算法的性能也各不相同。根據(jù)本文以上分析可知,APICT算法中節(jié)點定位僅與錨節(jié)點相關(guān),而不需要其鄰居節(jié)點參與定位,所以該算法在節(jié)點密度改變的情況下其定位誤差影響較低,可以說幾乎無變化,而對于APIT算法,其定位精度則與網(wǎng)絡(luò)節(jié)點密集程度有著很大的影響,定位誤差率隨著節(jié)點密度的增大而減小,所以可得出此結(jié)論:在節(jié)點密度一定的情況下,APICT算法的性能優(yōu)于APIT。

4 結(jié)束語

本文通過分析當(dāng)前較常用的一種基于區(qū)域重疊定位算法APIT,通常產(chǎn)生的ETI和ITE錯誤及其產(chǎn)生的原因,從而影響節(jié)點定位精度及執(zhí)行效率的缺點,提出一種基于三角形外接圓覆蓋的APICT算法,有效改進(jìn)了算法的定位精度和執(zhí)行效率。仿真實驗表明,基于三角形外接圓覆蓋的改進(jìn)的APIT算法,在隨機(jī)分布的網(wǎng)絡(luò)中,不但可以有效地降低ETI和ITE兩類錯誤發(fā)生的概率,改善算法的性能,而且能提高平均定位精度。影響APIT定位算法的最終定位精度的因素有很多,除了本文中討論的錨節(jié)點密度、相鄰節(jié)點部署外,定位精度還與通信半徑,無效節(jié)點等其他因素有關(guān),這些將是下一步研究的內(nèi)容。

[1]王汝傳,孫力娟.無線傳感器網(wǎng)絡(luò)技術(shù)導(dǎo)論[M].出版地:清華大學(xué)出版社,2012.

[2]王小強(qiáng),歐陽駿,黃寧淋.ZigBee無線傳感器網(wǎng)絡(luò)設(shè)計與實現(xiàn)[M].出版地:化學(xué)工業(yè)出版社,2012.

[3]崔立,鞠海玲,苗永,等.無線傳感器網(wǎng)絡(luò)研究進(jìn)展[J].計算機(jī)研究與發(fā)展,2005,42(1):163-174.

[4]韓光潔.智能空間中傳感器網(wǎng)絡(luò)節(jié)點精確定位與路徑規(guī)劃[M].北京:科學(xué)出版社,2012.

[5]熊小華,何通能,徐中勝,等.無線傳感器網(wǎng)絡(luò)節(jié)點定位算法的研究綜述[J].機(jī)電工程,2009,26(2):13-17.

[6]王福豹,史龍,任豐原.無線傳感器網(wǎng)絡(luò)中的自身定位系統(tǒng)和算法[J].軟件學(xué)報,2005,16(5):857-868.

[7]馮秀芳,曹美麗,孫超.無線傳感器網(wǎng)絡(luò)基于APIT的混合定位算法[J].微電子學(xué)與計算機(jī),2009,29(6):58-61.

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

[9]相衛(wèi)華,賈超,王華奎,等.無線傳感器網(wǎng)絡(luò)三維APIT網(wǎng)格化算法[J].傳感技術(shù)學(xué)報,2012,25(5):639-643.

[10]胡偉,朱西平,文紅,等.基于四面體質(zhì)心迭代的三維APIT定位算法研究[J].傳感技術(shù)學(xué)報,2013,26(10):1432-1436.

[11]Nirupama Bulusu,Deborah Estrin,John Herdemann.Tradeoffs in Location Support System:The Case for Quality-Exprossive Location Models for Applications[C]//Proceedings of the Ubicomp 2001 Workshop on Location Modeling Atlanatn.Gerogia,USA:2001:7-12.

[12]Harter A,Hopper A,Steggles P,et al.The anatomy of a Context-Aware Application[C]//Proceedings of the 5th Annual ACM/IEEE International Conference on Moblie Computing and Networking.Seattle:ACM Press,1999:59-68.

[13]Andreas Savvides,Chih Chieh Han,Mani B Srivastava.Dynamic Fine-Grained Location in Ad-Hoc Networks of Sensors[C]//Proceedings of Moblie Computing and Networking(MobiCom’01),Rome,Italy:ACM Press,2001:166-179.

[14]He T,Huang C D,Blum B M,et al.Range Free Localization Schemes in Large Scale Sensor Networks[C]//Proc of the 9th Annual Int Conf on Moblie Computing and Networking.New York:ACM,2003:81-95.

[15]Tian He,Chengdu Huang,Brian M Blum et al.Range-Free Localization Schemes in Large Scale Sensor Networks[C]//Proceeding of the 9th Annual International Conference on Mobile Computing and Networking(MobiCom),San Diego,California,USA:ACM Press,2003:81-95.

An Improved APIT Localization Algorithm Based on Triangle-Circumcircle Cover*

TANGWenliang*,ZHOULinying

(School of Software,East China Jiaotong University,Nanchang 330013,China)

The sensor node localization plays an important role in wireless sensor network.Comparing with other localization algorithm,APIT(Approximate Point-In-triangulation Test)has the advantages of lower hardware requirement and better positioning performance and so on.In the network which nodes distribute densely,APIT algorithm can help get a more reasonable positioning accuracy,and its performance is relatively stable.However,in the network which nodes distribute randomly,the positioning error is not allow to ignore,and positioning coverage rate is relative lower.To solve this problem,this article analyzed a typical mistake in the APIT test and its causes,which is called the inside and outside triangle cover judgment errors,and its put forward an improved APIT algorithm,which is named APICT(Approximate Point-In-circumcircle Test)algorithm,that based on triangle circumcircle cover algorithm.Comparing with APIT algorithm,the simulation result of this algorithm proved that the positioning accuracy has improved significantly.

wireless sensor network;localization algorithm;triangle circumcircle cover;positioning accuracy;APIT algorithm;inside and outside triangle cover

湯文亮(1969-),男,教授,碩士研究生導(dǎo)師,主要研究方向為無線傳感器網(wǎng)絡(luò);

周琳穎(1991-),女,碩士研究生,主要研究方向為無線傳感器網(wǎng)絡(luò),joline0331@sina.com。

項目來源:國家自然科學(xué)基金項目(61162001);2013年省科技支撐項目(20132BBF60083);2013年省教育廳科技項目(GJJ13340)

2014-09-11 修改日期:2014-11-04

C:7230

10.3969/j.issn.1004-1699.2015.01.021

TP393

A

1004-1699(2015)01-0121-05