湯文亮，蔡 靜，周琳穎，桂玉杰

(1.華東交通大學(xué) 軟件學(xué)院，南昌 330013； 2.華東交通大學(xué) 圖書(shū)館，南昌 330013)

基于聯(lián)合分步APIT定位算法的改進(jìn)

湯文亮1，蔡 靜1，周琳穎1，桂玉杰2

(1.華東交通大學(xué) 軟件學(xué)院，南昌 330013； 2.華東交通大學(xué) 圖書(shū)館，南昌 330013)

針對(duì)無(wú)線傳感網(wǎng)絡(luò)(wireless sensor network,WSNs)APIT節(jié)點(diǎn)定位算法在錨節(jié)點(diǎn)低密度環(huán)境下的節(jié)點(diǎn)誤判和節(jié)點(diǎn)失效等問(wèn)題給出了改進(jìn)，在APICT定位算法的基礎(chǔ)上提出了聯(lián)合分步定位算法UNION-APICT(union approximate point-in-circumcircle Test)，該算法是結(jié)合連通性的測(cè)距技術(shù)，RSSI測(cè)距技術(shù)以及質(zhì)心定位和APICT等技術(shù)，來(lái)聯(lián)合解決對(duì)未知節(jié)點(diǎn)定位問(wèn)題;通過(guò)仿真實(shí)驗(yàn)結(jié)果表明，改進(jìn)后的UNION-APICT在APICT算法的基礎(chǔ)之上平均定位誤差減少了10%～25%，定位性能有了明顯的提升；隨著通信半徑R和最大探測(cè)距離rmax的增加，定位誤差也在逐漸減小，該算法較APIT和APICT定位算法在錨節(jié)點(diǎn)密度、節(jié)點(diǎn)覆蓋率和定位精度上都有所提高。

無(wú)線傳感器網(wǎng)絡(luò);APICT;UNION-APICT;錨節(jié)點(diǎn)密度;節(jié)點(diǎn)覆蓋率;定位精度

0 引言

無(wú)線傳感網(wǎng)絡(luò)(wireless sensor networks，WSNs)廣泛應(yīng)用于醫(yī)療衛(wèi)生，環(huán)境監(jiān)測(cè)(如：森林突發(fā)火災(zāi)，石油管道破裂具體地點(diǎn)監(jiān)測(cè))，軍事等領(lǐng)域[1]。節(jié)點(diǎn)定位作為一項(xiàng)基本技術(shù)，它是無(wú)線傳感器網(wǎng)絡(luò)中收集環(huán)境信息、目標(biāo)檢測(cè)和跟蹤的應(yīng)用的基礎(chǔ)[2]。因此如何讓無(wú)線傳感網(wǎng)絡(luò)更廣泛地應(yīng)用到實(shí)際領(lǐng)域里面去是近幾年的研究熱點(diǎn)，國(guó)內(nèi)外專家學(xué)者在提高定位節(jié)點(diǎn)的定位精度付出了很多的努力[3]。因而，研究定位算法，提高節(jié)點(diǎn)定位精度，實(shí)現(xiàn)傳感網(wǎng)絡(luò)的普及是有著重要意義。

目前，根據(jù)定位過(guò)程中是否測(cè)量實(shí)際節(jié)點(diǎn)間的距離，大致可以分為測(cè)距(range-based)和非測(cè)距( range-free) 算法[4]定位算法；在眾多的定位算法中[5-9]，APIT (approximate point-in-triangulation test) 定位算法具有實(shí)現(xiàn)起來(lái)簡(jiǎn)單，定位功耗較小、精度高且成本低的優(yōu)點(diǎn)，它是節(jié)點(diǎn)定位技術(shù)研究領(lǐng)域中的一大熱點(diǎn)[10]。但是APIT算法會(huì)因?yàn)槲粗?jié)點(diǎn)臨近錨節(jié)點(diǎn)分布不均勻或錨節(jié)點(diǎn)由于在一條直線上不能組成三角形等原因，其節(jié)點(diǎn)定位受到了影響，達(dá)不到合適定位精度[11]。文獻(xiàn)[12]引入了移動(dòng)錨節(jié)點(diǎn)的概念，通過(guò)使用移動(dòng)錨節(jié)點(diǎn)讓錨節(jié)點(diǎn)分布起來(lái)更均勻；并且將異構(gòu)傳感器添加進(jìn)來(lái)進(jìn)行節(jié)點(diǎn)布置，該文獻(xiàn)中還使用了RSSI模型對(duì)改進(jìn)的APIT算法進(jìn)行修正，但是缺點(diǎn)也在這里，由于RSSI進(jìn)行取值，所以RSSI的誤差也就成了定位精度里的最大影響因子；文獻(xiàn)[13]采用分步定位算法對(duì)未知節(jié)點(diǎn)進(jìn)行測(cè)量，該算法是只需要3個(gè)參考節(jié)點(diǎn)進(jìn)行定位，有效地避免使用三邊測(cè)量法無(wú)解的情況，適應(yīng)性強(qiáng)、實(shí)用性強(qiáng)，但該文僅用一種算法使在錨節(jié)點(diǎn)密度低的情況下無(wú)法定位。

文獻(xiàn)[14]提出了一種基于三角形外接圓覆蓋的改進(jìn)APIT定位算法。該算法改進(jìn)后，在節(jié)點(diǎn)密度一定的情況下性能優(yōu)于APIT。但APICT(approximate point-in-circumcircle test) 算法在針對(duì)節(jié)點(diǎn)應(yīng)用在復(fù)雜環(huán)境下，沒(méi)有考慮怎么使用最少的錨節(jié)點(diǎn)達(dá)到節(jié)點(diǎn)覆蓋率最優(yōu)的狀態(tài)，所以本文在研究APICT算法的基礎(chǔ)上，發(fā)現(xiàn)了一種可以參考各未知節(jié)點(diǎn)之間的位置關(guān)系來(lái)實(shí)現(xiàn)定位的方法，并擬名為聯(lián)合分步定位算法UNION-APICT(union approximate point-in-circumcircle test)，它將定位技術(shù)聯(lián)合起來(lái)對(duì)未知節(jié)點(diǎn)進(jìn)行分步協(xié)同定位，這樣得出在錨節(jié)點(diǎn)低密度分布情形下的一個(gè)新的高精度定位算法。

1 UNION-APICT算法

聯(lián)合分步定位算法UNION-APICT利用三邊測(cè)量法或極大似然估計(jì)、基于接收信號(hào)能量(RSSI)的測(cè)距技術(shù)、基于連通性的測(cè)距技術(shù)以及質(zhì)心定位等技術(shù)對(duì)待定位節(jié)點(diǎn)的估測(cè)位置進(jìn)行多次定位，從而達(dá)到提高網(wǎng)絡(luò)定位覆蓋率和定位精度的目的。

1.1 UNION-APICT算法思想

UNION-APICT定位算法的基本思想是：

1)若待定位節(jié)點(diǎn)S不能與錨節(jié)點(diǎn)進(jìn)行相互通信，則通過(guò)基于連通性的測(cè)距方法獲得相鄰節(jié)點(diǎn)間的距離，利用三邊測(cè)量法或極大似然估計(jì)法對(duì)待定位節(jié)點(diǎn)M進(jìn)行定位，得到最終位置坐標(biāo)；

2)若S能與錨節(jié)點(diǎn)進(jìn)行通信，則按照 APICT 定位算法的步驟[14]求出S的估測(cè)位置P；

3)S向以P為圓心，以r(r<=R)為半徑的目標(biāo)圓形區(qū)域內(nèi)發(fā)射探測(cè)信號(hào)，假設(shè)ESSI和RSSI的值分別為PE和PR，當(dāng)圓形區(qū)域內(nèi)的節(jié)點(diǎn)一旦接收到來(lái)自S的探測(cè)信號(hào)，則立刻將帶有S的標(biāo)識(shí)ID、信號(hào)強(qiáng)度和位置坐標(biāo)等信息向周圍廣播出去，S接收并記錄探測(cè)信號(hào)覆蓋范圍內(nèi)錨節(jié)點(diǎn)的節(jié)點(diǎn)信息及PE和PR，求出每個(gè)錨節(jié)點(diǎn)的PE和S的PR之間的差值，最后通過(guò)S位置坐標(biāo)計(jì)算公式求得S的最終坐標(biāo)(x,y)。

在理論基礎(chǔ)下，可得出無(wú)線信號(hào)傳播模型中信號(hào)的強(qiáng)度和距離兩者之間的關(guān)系如式(1)所示:

(1)

PR(d)表示在參距離等于d時(shí)，在接收點(diǎn)處得到的RSSI值；PR(d0)則表示在參考距離等于d0時(shí)的RSSI值；n表示路徑消耗指數(shù)，由公式(1)式可以得到PE與PR之間的差值：

(2)

UNION-APICT算法涉及RSSI的相關(guān)應(yīng)用，無(wú)線信號(hào)在傳播過(guò)程中通過(guò)RSSI得到的PE和PR能算出傳播過(guò)程中的功率消耗，最后可以通過(guò)無(wú)線信號(hào)轉(zhuǎn)播模型將功率損耗即可推得兩者間的距離。

1.2 UNION-APICT算法流程

1.2.1 算法流程圖

UNION-APICT算法流程如圖1所示。

圖1 UNION-APICT定位算法流程圖

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

仿真實(shí)驗(yàn)使用Matlab7.0實(shí)現(xiàn)。

2.1 仿真實(shí)驗(yàn)相關(guān)參數(shù)設(shè)置

本實(shí)驗(yàn)中為凸顯復(fù)雜環(huán)境下出現(xiàn)的低密度節(jié)點(diǎn)分布情況，將實(shí)驗(yàn)參數(shù)初步設(shè)定如下：通信區(qū)域?yàn)?00 m×300 m，錨節(jié)點(diǎn)的R與待定位節(jié)點(diǎn)的R的比例系數(shù)為1，即兩者的R相同。

2.2 仿真實(shí)驗(yàn)與結(jié)果分析

本節(jié)將對(duì)聯(lián)合APICT定位算法以及三邊測(cè)量法或極大似然估計(jì)、RSSI測(cè)距技術(shù)、基于連通性的測(cè)距技術(shù)等進(jìn)行分步的UNION-APICT算法進(jìn)行仿真實(shí)驗(yàn)，并分別從不同的節(jié)點(diǎn)總數(shù)N、錨節(jié)點(diǎn)比例H、最大探測(cè)距離r和通信半徑R等方面和APICT 定位算法在定位精度上進(jìn)行對(duì)比分析。

2.2.1 節(jié)點(diǎn)總數(shù)和錨節(jié)點(diǎn)比例不同

當(dāng)錨節(jié)點(diǎn)數(shù)量N=100和200，且錨節(jié)點(diǎn)比例H分別為0.05、0.1、0.15、0.2、0.25、0.3時(shí)，UNION-APICT定位算法與APICT定位算法的定位誤差對(duì)比如圖2和圖3所示。

圖2 N=100定位誤差對(duì)比圖

圖3 N=200定位誤差對(duì)比圖

根據(jù)上圖數(shù)據(jù)我們可以推出UNION-APICT的定位誤差總是比APICT低，且在N不同時(shí)，隨著H的增大，UNION-APICT的定位誤差逐漸降低，APICT的定位誤差基本維持在0.42左右。經(jīng)計(jì)算可知：當(dāng)錨節(jié)點(diǎn)數(shù)量N=100和N=200時(shí)，UNION-APICT算法比APICT算法的平均定位誤差分別減少12.5%和21%。

對(duì)比分析上述兩圖數(shù)據(jù)可知：不論當(dāng)N相同時(shí)，H不同，或者當(dāng)H相同，N不同時(shí)，UNION-APICT定位算法的定位誤差都相對(duì)APICT定位算法趨于平穩(wěn)，也就是說(shuō)即使在低密度節(jié)點(diǎn)總數(shù)覆蓋下或低密度錨節(jié)點(diǎn)比率覆蓋情況下，UNION-APICT相對(duì)APICT定位算法算法定位誤差仍舊相差無(wú)幾。由此可得出結(jié)論：在復(fù)雜WSN中(尤其低密度WSN情況下)，UNION-APICT定位算法相對(duì)APIT定位算法更適用，且精度更高。

2.2.2 節(jié)點(diǎn)通信半徑R不同

當(dāng)錨節(jié)點(diǎn)數(shù)量N=200，錨節(jié)點(diǎn)比例H=0.2，節(jié)點(diǎn)通信半徑R分別為 20 m、60 m、100 m、140 m、180 m，待定位節(jié)點(diǎn)的探測(cè)距離r的范圍為(0.1R，0.5R)時(shí)，UNION-APICT定位算法與APICT 定位算法的定位誤差對(duì)比如圖4所示。

圖4 不同R的定位誤差對(duì)比圖

由圖4可知，UNION-APICT算法的定位誤差明顯比APICT 的定位誤差小，在隨著測(cè)距半徑R的增大，UNION-APICT定位算法誤差呈現(xiàn)下降的趨勢(shì)，而APICT的誤差基本上是保持不變的。原因是隨著R的逐漸增大，待定位節(jié)點(diǎn)發(fā)射探測(cè)信號(hào)的r也跟著增大，與此同時(shí)探測(cè)目標(biāo)區(qū)域內(nèi)錨節(jié)點(diǎn)密度也隨之增大，這樣就使得最終的節(jié)點(diǎn)定位誤差有所降低，但是APICT的定位誤差雖然從R開(kāi)始增大的時(shí)候就開(kāi)始慢慢減小，但是當(dāng)R增大到250 m后，基本維持在0.42不變，這就說(shuō)明了UNION-APICT定位算法的良好可擴(kuò)展性。

通過(guò)上述分析可得出結(jié)論：在R逐漸增大時(shí)，UNION-APICT定位算法的平均定位誤差比APICT定位算法減小18%，且隨著R的增大，UNION-APICT的定位誤差也在逐漸降低。

2.2.2 最大探測(cè)距離rmax不同

圖5是當(dāng)N=100，H=0.2，R=60 m，待定位節(jié)點(diǎn)最大探測(cè)距離rmax分別為 0.5 R，0.6 R，0.7 R，0.8 R，0.9 R時(shí)，UNION-APICT定位算法的定位誤差圖。如圖可知，隨著rmax增大，UNION-APICT算法的定位誤差不斷減小，但是減小幅度不大，當(dāng)rmax=0.7R時(shí)，UNION-APICT算法的定位誤差趨于穩(wěn)定了，這是因?yàn)楫?dāng)rmax逐漸增大時(shí)，待定位節(jié)點(diǎn)的探測(cè)圓形咪表區(qū)域內(nèi)錨節(jié)點(diǎn)的密度也隨之增大，這樣使得待定位節(jié)點(diǎn)和錨節(jié)點(diǎn)之間的二次通信后的所得到的定位精度有所提高，而當(dāng)目標(biāo)區(qū)域內(nèi)的錨節(jié)點(diǎn)數(shù)量達(dá)到一定值時(shí)，UNION-APICT定位算法的誤差也隨之趨于穩(wěn)定。

圖5 不同rmax的定位誤差圖

因此，經(jīng)過(guò)以上實(shí)驗(yàn)及分析可知：在一定范圍內(nèi)，UNION-APICT算法會(huì)隨著rmax的增大，節(jié)點(diǎn)定位精度會(huì)跟著也會(huì)有所提高。

3 結(jié)論

本文在APICT定位算法的基礎(chǔ)提出了聯(lián)合分步定位算法UNION-APICT，通過(guò)實(shí)驗(yàn)及分析可知UNION-APICT算法是一種適應(yīng)在低密度的環(huán)境下也能保證較高定位精度和較高定位覆蓋的定位算法，此算法在APICT算法的基礎(chǔ)之上平均定位誤差減少了10%～25%，定位性能有了明顯的提升；另外，當(dāng)通信半徑R和最大探測(cè)距離上面rmax，隨著R和rmax的增加時(shí)，定位誤差也在逐漸減小，相比APIT算法可擴(kuò)展性有所提升。

[1] Ahmadalipour A, Sadeghzadeh J, Vafaei A A, et al. Effects of environmental enrichment on behavioral deficits and alterations in hippocampal BDNF induced by prenatal exposure to morphine in juvenile rats[J]. Neuroscience, 2015, 305(10): 37-43.

[2] Zhu C, Zheng C, Shu L, et al. A survey on coverage and connectivity issues in wireless sensor networks[J]. Journal of Network & Computer Applications, 2012, 35(2):619-632.

[3] Han G J, Chao J, Zhang C Y. The impacts of mobility models on DV-hop based localization in Mobile Wireless Sensor Networks[J]. Science(S1084-8045), Journal of Network & Computer Applications, 2014, 42(4): 70-79.

[4] 彭 宇，王 丹.無(wú)線傳感器網(wǎng)絡(luò)的定位技術(shù)綜述[J].電子測(cè)量與儀器學(xué)報(bào), 2011, 13(6) :25-29.

[5] 毛利洋，林秀晶，邵開(kāi)來(lái)，等.基于RSSI的無(wú)線傳感網(wǎng)絡(luò)協(xié)同定位算法及其應(yīng)用[J].機(jī)電工程，2012(1):116-119.

[6] 陳鳳娟. 無(wú)線傳感器網(wǎng)絡(luò)中的節(jié)點(diǎn)定位算法[J]. 信息安全與技術(shù), 2013, 4(10): 60-61.

[7] 陳 偉. 基于壓縮感知的無(wú)線傳感網(wǎng)絡(luò)定位研究[D]. 南京：南京郵電大學(xué)，2014.

[8] 石 欣，印愛(ài)民，陳 曦.基于RSSI的多維標(biāo)度室內(nèi)定位算法[J].儀器儀表學(xué)報(bào)，2014(35):261-268.

[9] 夏心江, 胡 鋼, 王燁華. 基于錨球交域重心的WSN三維定位算法研究[J]. 計(jì)算機(jī)工程與應(yīng)用, 2013(10): 76-79.

[10] 陳 濤. 無(wú)線傳感器網(wǎng)絡(luò)改進(jìn)APIT定位算法[D]. 廣州：暨南大學(xué), 2012.

[11] 吳 棟，紀(jì)志成，張 彪. 基于無(wú)線傳感器網(wǎng)絡(luò)的改進(jìn)APIT定位算法[J]. 系統(tǒng)仿真學(xué)報(bào)，2015(27): 2965-2972.

[12] 馬正華, 章 明, 李 敏, 等. 分步定位法在ZigBee定位系統(tǒng)中的應(yīng)用[J]. 測(cè)控技術(shù), 2012, 31(4): 111-113.

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

[14] 湯文亮, 周琳穎. 基于三角形外接圓覆蓋的改進(jìn)APIT定位算法[J]. 傳感技術(shù)學(xué)報(bào), 2015(1): 121-125.

[15] 楊成成. 基于ZigBee的CNG加氣站可燃?xì)怏w泄漏檢測(cè)與定位系統(tǒng)研究[D]. 北京：中國(guó)石油大學(xué), 2011.

Improved APIT Localization Algorithm Based on Joint Step

Tang Wenliang1，Cai Jing1，Zhou Linying1, Gui Yujie2

(1.School of Software, East China Jiaotong University, Nanchang 330013, China; 2.Library, East China Jiaotong University, Nanchang 330013, China)

The classic APIT(approximate Point-in-Triangulation test) algorithm has been utilized in node localization in wireless sensor networks for major applications, however, it is easily fall into nodes misjudgments and node failure as its accuracy can not be guaranteed in low node density scenarios. To solve this problem, this paper proposes an improved node localization algorithm UNION-APICT(union approximate Point-in-Circumcircle test) which focuses on improving the localization accuracy by combining the connected ranging method, the RSSI ranging technology, the centroid localization and APICT together, which can solve the unknown node localization problem effectively. The simulation experiment results demonstrate that the UNION-APICT can achieve the lower average location error as much as 10% to 25% than APICT scheme. And when the communication radius R and the maximum detection range Rmax increasing, the node localization error decreasing accordingly. Compared with the APIT and APICT localization algorithms, the new UNION-APICT can get performance improvement significantly both in anchor nodes density, the coverage, and localization accuracy.

wireless sensor networks; APIT; UNION-APICT; anchor node density; node coverage; positioning accuracy

2016-07-17；

2016-08-04。

2014年省科技計(jì)劃項(xiàng)目(2014X0012);2016年省科技計(jì)劃項(xiàng)目(20161BBE50092);2014年省教育規(guī)劃課題(14YD002)。

湯文亮(1969-)，男，教授，碩士生導(dǎo)師，主要從事無(wú)線傳感器網(wǎng)絡(luò)和信息安全方向的研究。

1671-4598(2016)12-0213-03

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

TP393.3

A