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

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

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

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

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

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

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

0 引言

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

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

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

1 UNION-APICT算法

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

1.1 UNION-APICT算法思想

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

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

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

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

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

(1)

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

(2)

UNION-APICT算法涉及RSSI的相關(guān)應(yīng)用，無線信號在傳播過程中通過RSSI得到的PE和PR能算出傳播過程中的功率消耗，最后可以通過無線信號轉(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é)將對聯(lián)合APICT定位算法以及三邊測量法或極大似然估計(jì)、RSSI測距技術(shù)、基于連通性的測距技術(shù)等進(jìn)行分步的UNION-APICT算法進(jìn)行仿真實(shí)驗(yàn)，并分別從不同的節(jié)點(diǎn)總數(shù)N、錨節(jié)點(diǎn)比例H、最大探測距離r和通信半徑R等方面和APICT 定位算法在定位精度上進(jìn)行對比分析。

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時，UNION-APICT定位算法與APICT定位算法的定位誤差對比如圖2和圖3所示。

圖2 N=100定位誤差對比圖

圖3 N=200定位誤差對比圖

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

對比分析上述兩圖數(shù)據(jù)可知：不論當(dāng)N相同時，H不同，或者當(dāng)H相同，N不同時，UNION-APICT定位算法的定位誤差都相對APICT定位算法趨于平穩(wěn)，也就是說即使在低密度節(jié)點(diǎn)總數(shù)覆蓋下或低密度錨節(jié)點(diǎn)比率覆蓋情況下，UNION-APICT相對APICT定位算法算法定位誤差仍舊相差無幾。由此可得出結(jié)論：在復(fù)雜WSN中(尤其低密度WSN情況下)，UNION-APICT定位算法相對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)的探測距離r的范圍為(0.1R，0.5R)時，UNION-APICT定位算法與APICT 定位算法的定位誤差對比如圖4所示。

圖4 不同R的定位誤差對比圖

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

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

2.2.2 最大探測距離rmax不同

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

圖5 不同rmax的定位誤差圖

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

3 結(jié)論

本文在APICT定位算法的基礎(chǔ)提出了聯(lián)合分步定位算法UNION-APICT，通過實(shí)驗(yàn)及分析可知UNION-APICT算法是一種適應(yīng)在低密度的環(huán)境下也能保證較高定位精度和較高定位覆蓋的定位算法，此算法在APICT算法的基礎(chǔ)之上平均定位誤差減少了10%～25%，定位性能有了明顯的提升；另外，當(dāng)通信半徑R和最大探測距離上面rmax，隨著R和rmax的增加時，定位誤差也在逐漸減小，相比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ǎng)絡(luò)的定位技術(shù)綜述[J].電子測量與儀器學(xué)報(bào), 2011, 13(6) :25-29.

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

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

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

[8] 石 欣，印愛民，陳 曦.基于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ǎng)絡(luò)改進(jìn)APIT定位算法[D]. 廣州：暨南大學(xué), 2012.

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

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

[13] 馮秀芳, 崔秀鋒, 祈會波. 無線傳感器網(wǎng)絡(luò)中基于移動錨節(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泄漏檢測與定位系統(tǒng)研究[D]. 北京：中國石油大學(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ǎng)絡(luò)和信息安全方向的研究。

1671-4598(2016)12-0213-03

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

TP393.3

A