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

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

基于聯合分步APIT定位算法的改進

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

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

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

無線傳感器網絡;APICT;UNION-APICT;錨節(jié)點密度;節(jié)點覆蓋率;定位精度

0 引言

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

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

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

1 UNION-APICT算法

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

1.1 UNION-APICT算法思想

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

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

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

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

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

(1)

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

(2)

UNION-APICT算法涉及RSSI的相關應用，無線信號在傳播過程中通過RSSI得到的PE和PR能算出傳播過程中的功率消耗，最后可以通過無線信號轉播模型將功率損耗即可推得兩者間的距離。

1.2 UNION-APICT算法流程

1.2.1 算法流程圖

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

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

2 仿真結果及分析

仿真實驗使用Matlab7.0實現。

2.1 仿真實驗相關參數設置

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

2.2 仿真實驗與結果分析

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

2.2.1 節(jié)點總數和錨節(jié)點比例不同

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

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

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

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

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

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

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

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

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

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

2.2.2 最大探測距離rmax不同

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

圖5 不同rmax的定位誤差圖

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

3 結論

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

[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] 彭 宇，王 丹.無線傳感器網絡的定位技術綜述[J].電子測量與儀器學報, 2011, 13(6) :25-29.

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

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

[7] 陳 偉. 基于壓縮感知的無線傳感網絡定位研究[D]. 南京：南京郵電大學，2014.

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

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

[10] 陳 濤. 無線傳感器網絡改進APIT定位算法[D]. 廣州：暨南大學, 2012.

[11] 吳 棟，紀志成，張 彪. 基于無線傳感器網絡的改進APIT定位算法[J]. 系統(tǒng)仿真學報，2015(27): 2965-2972.

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

[13] 馮秀芳, 崔秀鋒, 祈會波. 無線傳感器網絡中基于移動錨節(jié)點的APIT的改進定位算法[J]. 傳感技術學報, 2011, 24(2): 269-274.

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

[15] 楊成成. 基于ZigBee的CNG加氣站可燃氣體泄漏檢測與定位系統(tǒng)研究[D]. 北京：中國石油大學, 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年省科技計劃項目(2014X0012);2016年省科技計劃項目(20161BBE50092);2014年省教育規(guī)劃課題(14YD002)。

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

1671-4598(2016)12-0213-03

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

TP393.3

A