呂淑芳

(山西農(nóng)業(yè)大學 信息學院，山西 晉中 030800)

綜述與評論

無線傳感器網(wǎng)絡節(jié)點定位研究綜述*

呂淑芳

(山西農(nóng)業(yè)大學 信息學院，山西 晉中 030800)

摘要:深入探討分析了無線傳感器網(wǎng)絡定位技術，從無線傳感器網(wǎng)絡定位算法分類、評價指標、距離相關和距離無關定位算法等方面進行分析，重點對比了幾種典型算法，結果表明：不同的算法具有應用環(huán)境單一性，應結合實際需求選擇合適的算法。研究分析了新型無線傳感器網(wǎng)絡定位方法，主要包括移動錨節(jié)點定位算法、三維空間定位算法和智能定位優(yōu)化算法。總結當前無線傳感器網(wǎng)絡定位研究中存在的問題，并給出未來改進的研究方向。

關鍵詞:無線傳感器網(wǎng)絡；定位技術；算法分類；新型無線傳感器網(wǎng)絡定位方法；智能定位

0引言

無線傳感器網(wǎng)絡(WSNs)[1]研究涉及廣泛且多個學科交叉融合，是一種獲取、處理信息的全新技術，廣泛應用在國防、醫(yī)療、環(huán)境、目標跟蹤、入侵檢測等領域。在無線傳感器網(wǎng)絡中，傳感器節(jié)點所監(jiān)測到的信息,如壓力、溫度、濕度等，如果沒有相對應的位置信息是毫無研究價值的，因此，位置信息對監(jiān)測活動至關重要。

無線傳感器網(wǎng)絡的節(jié)點通常是動態(tài)隨機地拋灑在一些人類不可到達或比較危險復雜的區(qū)域，這樣的網(wǎng)絡要求能夠協(xié)作地來感知、采集、處理網(wǎng)絡分布區(qū)域內的各種環(huán)境和監(jiān)測對象的信息，并傳送給監(jiān)測者。但由于能耗、計算能力、通信能力等因素極大地限制了無線傳感器網(wǎng)絡節(jié)點，因此，具有分布式、低復雜性、高精度、良好通用性等特點的節(jié)點定位方法就被極大的需求。

1定位算法的研究現(xiàn)狀

1.1定位算法的性能評價指標和算法分類

經(jīng)典的評價標準[2]有：定位精度、網(wǎng)絡規(guī)模、節(jié)點密度、錨節(jié)點密度、功耗、成本代價、容錯性、自適應性、網(wǎng)絡連通度等。這些性能評價指標不僅可以用來評價無線傳感器網(wǎng)絡算法和自身定位系統(tǒng)，同時也是其設計并實現(xiàn)的改進目標?？紤]到實際應用中，這些性能指標并不是獨立，而是相互關聯(lián)的，需要結合具體的應用背景來權衡設計，實現(xiàn)適合的定位技術。

無線傳感器網(wǎng)絡的定位方法有很多種，目前比較普遍的分類方法[1]有以下三種：

1)根據(jù)是否測量節(jié)點之間的距離可劃分為：距離相關算法和距離無關算法。距離相關法定位精度高于距離無關法,但對硬件要求較高、在距離難以測量的場合，需要用距離無關法估算節(jié)點間距離。

2)根據(jù)網(wǎng)絡連通度和拓撲結構可劃分為：單跳算法和多跳算法。單跳算法適用范圍小，但簡單易實現(xiàn)；在一些測量范圍比較廣的場合則需要采用多跳算法。

3)根據(jù)處理信息的方式可劃分為：集中式算法和分布式算法。集中式算法適用于監(jiān)測和控制的應用場景，該算法有較高的精度但需要消耗較大的通信量；分布式算法由于其數(shù)據(jù)處理實現(xiàn)方式的不同，能夠降低網(wǎng)絡通信量，但卻受到節(jié)點能量、計算和存儲能力的限制。

目前公認的分類算法是距離相關算法和距離無關算法。

1.2距離相關的定位算法

距離相關算法的定位測量方法分為兩大類，基于時間的方法有到達時間(time of arrival,TOA)和到達時間差(time difference of arrival,TDOA)；基于角度的方法有到達角(angle of arrival，AOA)和接收信號強度指示(received signal strength indication,RSSI)。

1.2.1TOA

基于TOA定位測量方法簡單，有較高的定位精度，但是要做到嚴格的時間同步比較難，如何精確測量時間也是一大難點且受外界環(huán)境影響比較大。

TOA[3]的發(fā)展始于雙程測距，定位精度受傳播距離的限制，只有在視距(line-of-sight,LOS)范圍內才有較高的精度。文獻[4]Hangoo Kang 等人提出了TOA誤差補償算法，并將其應用到多徑環(huán)境中，取得了較好的效果。隨之，文獻[5]中Andreas Lewandowski等人在工業(yè)應用背景下，提出了一種加權TOA算法，實驗結果表明，該算法使系統(tǒng)容錯性有所提高，并且可降低自身對測距系統(tǒng)的干擾。

1.2.2TDOA

基于TDOA的測距方法，在視距情況下有較高的定位效果，但對硬件的要求較高且信號在傳輸過程中極易受環(huán)境影響，應用的場合也比較單一。

TDOA最早的應用是結合RF信號與超聲波信號。加州大學伯克利分校采用TDOA測距技術開發(fā)出了Calamari定位系統(tǒng)[6]。一些學者將TDOA測距原理與NTP協(xié)議時間同步機制[7]相結合，提出了一種新的時間同步和節(jié)點測距的混合算法，不僅可以將時間同步，甚至可得到相對測距。

1.2.3AOA

基于的AOA測距方法,需要額外的硬件設備如天線陣列或有向天線來支持。

由于其實用性，AOA測距并沒有得到廣泛的應用，最早的應用是文獻[8]提出在室內采集角度信息來實現(xiàn)定位。之后在少數(shù)節(jié)點有定位能力的應用場景下，有些學者提出了確定全部節(jié)點的方向和位置信息的定位算法。

1.2.4RSSI

RSSI的方法由于每個傳感器節(jié)點都有通信測距的能力，因此,RSSI測距方法成本低，但實際應用中，對錨節(jié)點數(shù)量的要求很高，也容易受到多路徑反射、非視線問題等環(huán)境因素的影響。

RSSI測距方法最早源于室內定位系統(tǒng)，目前使用廣泛的RSSI測距方法有兩種：一種是提前設置好定位區(qū)域，該方法計算量很小，只需查表或根據(jù)事先做好的擬合曲線進行計算即可，但是對實驗環(huán)境的要求很苛刻，一旦環(huán)境有所變化，原有實驗結果將失去價值，需要建立新的模型。另一種方法是現(xiàn)場部署定位區(qū)域，引入露珠洪泛思想[9]，結合迭代的分布式算法或雙曲線模型法，提出了RSSI機制的HCRL(hop-count-ratio-based localization)算法[10]。該算法計算過程較為繁瑣復雜，但有較強的適用性。

上述4種測距方法各有適用范圍，但綜合考慮其優(yōu)缺點，多數(shù)學者研究RSSI測距方法。表1為距離相關的測距技術的性能比較。

表1　距離相關測距技術比較

1.3距離無關的定位算法

距離無關的定位算法[11]相比較距離相關的定位算法，不需要測量距離或角度信息，而是根據(jù)網(wǎng)絡連通度來估計未知節(jié)點的坐標。以下介紹幾種典型的距離無關定位算法。

1.3.1質心定位算法

質心(Centroid)定位算法，是美國加州大學的Bulusu等人研究提出的，雖然實現(xiàn)簡單，但對錨節(jié)點密度的要求比較高，且定位誤差比較大。

1.3.2距離向量—跳段定位算法

距離向量—跳段(distance vector-hop，DV-Hop)定位算法是由Niculescu D等人提出，該算法適用場景比較單一，只能用在各向同性的密集網(wǎng)絡中，且定位誤差較大。大量實驗表明，無線傳感器網(wǎng)絡中的平均連通度為10時，且錨節(jié)點比例為10 %時，定位精準度約為33 %[13]。

1.3.3近似三角形內點測試算法

近似三角形內點測試(approximate point-in-triangulation test，APIT)算法，是由He等人提出的。APIT定位算法的理論基礎是最佳三角形內點測試(perfect point-in-triangulation test，PIT)法。APIT定位算法對錨節(jié)點密度的要求很高。

上述三種典型的測距無關定位算法可看出，測距無關算法是通過網(wǎng)絡連通度來進行定位的，且與節(jié)點密度緊密相關，大多偏重于理論研究，定位精度較低，適用范圍不是很廣。不同算法的側重點有所不同，DV-Hop算法側重于估計距離，能相對較好地估計出未知節(jié)點與錨節(jié)點之間的距離；Centroid、APIT算法側重于估計位置，能夠根據(jù)網(wǎng)絡連通度得到比較精確的位置信息。三種算法的性能比較如表2。

表2　距離無關定位算法性能比較

1.4計算節(jié)點位置的主要方法

由距離相關的測距方法得到未知節(jié)點與鄰居錨節(jié)點之間的距離或者角度信息后，需要用三邊測量、三角測量或者極大似然估計法、極大極小定位算法來計算未知節(jié)點的實際位置。

在實際環(huán)境下，需要根據(jù)具體的情況選擇合適的計算方法，所有計算的前提都是信標節(jié)點是準確無誤的。文獻[14]提出了一種基于信標優(yōu)化選擇(OBS)的定位算法，通過減小定位過程中可能產(chǎn)生的誤差來達到提高定位精度的效果。

2新型無線傳感器網(wǎng)絡定位算法

在傳統(tǒng)定位方法—靜態(tài)的定位技術的基礎上，新型的無線傳感器網(wǎng)絡定位算法應運而生。如，信標節(jié)點由靜止的變?yōu)閯討B(tài)的，用移動的錨節(jié)點去定位未知節(jié)點；將二維空間的定位拓展到三維空間；定位算法初步定位，智能優(yōu)化算法實現(xiàn)進一步的優(yōu)化，提高定位精度等。

2.1移動信標節(jié)點定位

移動錨節(jié)點定位的應用，最早是Sichitiu M L利用單個移動錨節(jié)點與RSSI測距相結合來估計未知節(jié)點的位置[15]。

移動錨節(jié)點定位采用移動錨節(jié)點代替了傳統(tǒng)的靜止的錨節(jié)點，降低了網(wǎng)絡中因多跳和傳輸距離遠而產(chǎn)生的定位誤差累計，減少了錨節(jié)點所需數(shù)量，降低了定位成本，提高了定位的精度。如何將路徑優(yōu)化，達到較高的定位性能，并將移動信標節(jié)點定位技術廣泛應用到大規(guī)模的無線傳感器網(wǎng)絡還需要更加深入的研究。

2.2三維空間定位技術

現(xiàn)有的多數(shù)定位技術都是針對二維空間,然而隨著傳感器網(wǎng)絡三維空間定位需求的不斷發(fā)展,三維空間定位成為研究的趨勢與熱點。

很多學者將二維空間的定位技術延伸運用到三維空間中,如,四面體質心定位算法、三維DV-Hop，APIT，RSSI定位等，都取得了較好的效果，并得到了一定程度的應用。如，文獻[16]提出的三維序列垂心算法；杜巧玲將三邊測量法延伸運用到三維空間中進行定位的算法[17]；文獻[18]提出的APIS(approximate point in sphere)非距離定位算法等。

三維定位算法將無線傳感器網(wǎng)絡定位推向了更好更高的前端研究領域，雖取得了一定的研究成果，但仍需要不斷完善和進步，如如何縮短定位時間、如何獲取優(yōu)良的錨節(jié)點等。

2.3智能優(yōu)化定位

隨著無線傳感器網(wǎng)絡定位技術的發(fā)展，傳感器節(jié)點本身性能的提升，對定位要求越來越高，智能優(yōu)化定位算法成為趨勢。

文獻[19]采用粒子濾波技術，在三維無線傳感器網(wǎng)絡戶外定位中取得了較好的效果；亦可采用神經(jīng)網(wǎng)絡優(yōu)化定位問題[22]，通過訓練建立合適的網(wǎng)絡模型，也可通過增加網(wǎng)絡節(jié)點密度降低定位誤差。針對平面空間中節(jié)點定位受非視距問題的影響，采用直推式回歸的定位算法[20]代替機器學習中的支持向量回歸SVR方法，更高的降低定位誤差。也有很多智能算法，如遺傳算法、模擬退火算法、爬山算法、粒子群算法等，結合定位測量方法和技術用在定位問題中，用作后期優(yōu)化，達到更好的定位效果。

3結束語

到目前為止，無線傳感器網(wǎng)絡定位研究已取得了一定的成果，但仍存在很多問題。如何考慮硬件成本的限制；如何平衡節(jié)點能耗與定位精度；如何解決算法應用環(huán)境單一性問題，尋求更加通用性的定位算法或者系統(tǒng)成為迫切的需求；如何將模擬仿真定位算法應用于具體的現(xiàn)實環(huán)境，設計出切合實際的算法或系統(tǒng)尤為重要。

新型的移動無線傳感器網(wǎng)絡定位、三維空間定位、智能定位技術的研究尚在起步階段，很多問題需要解決和完善，

這就對算法的適應性和實時性提出了更高的要求；現(xiàn)有算法在安全和隱私問題上都比較脆弱，分布式算法能夠有效減少信息被傳遞的次數(shù)，增強安全性，同時也可通過加密、不合法探測與隔離、魯棒位置計算、位置校驗等手段來實現(xiàn)安全性。

隨著定位技術的發(fā)展、人類生活的需要，無線傳感器網(wǎng)絡將在能耗、成本、實用性、安全定位、隨時變化的節(jié)點定位、三維定位等方面著力研究。

參考文獻:

[1]王媛媛,周小佳,閆斌.無線傳感器網(wǎng)絡定位技術研究[J].山東輕工業(yè)學院學報，2011,25(1):59-61.

[2]王亮,曹建安.無線傳感器網(wǎng)絡定位算法研究進展[J].現(xiàn)代電子技術,2011,34(23):27-30.

[3]Sahinoglu Z,Gezici S.Ranging in the IEEE 802.15.4a stan-dard[C]∥IEEE Wireless and Microwave Technology Conference(WAMICON),2006:1-5.

[4]Zafer S,Sinan G.Ranging in the IEEE 802.15.4a standard[C]∥IEEE Wireless and Microwave Technology Conference(WAMICON),2006:1-5.

[5]Andreas L,Christian W.A comprehensive approach for optimizing TOA-localization in harsh industrial environments[C]∥Position Location and Navigation Symposium(PLANS),2010 IEEE/ION,2010:516-525.

[6]Whitehouse K,Karlof C,Woo A,et al.The effects of ranging noise on multihop localization:An empirical study[C]∥The Fourth International Conference on Information Processing in Sensor Networks,IPSN’05,2005:73-80.

[7]Prakash Ranganathan,Kendall Nygard.Time synchronization in wireless sensor networks:A survey[J].Internation Journal of UbiComp(IJU),2010,1(2):92-100.

[8]Niculescu D,Nath B.Ad Hoc positioning system(APS)using AOA[C]∥Twenty-Second Annual Joint Conference of the IEEE Computer and Communications,IEEE Societies,2003:1734-1743.

[9]王晟.無線傳感器網(wǎng)絡節(jié)點定位與覆蓋控制理論及技術研究[D].武漢:武漢理工大學,2006:40-42.

[10] 杜存功,丁恩杰,苗曙光.無線傳感器網(wǎng)絡改進型節(jié)點定位算法的研究[J].傳感器與微系統(tǒng),2010,29(1):52-54.

[11] 肖忠義,馮秀芳.無線傳感器網(wǎng)絡四面質心定位算法研究[D].太原:太原理工大學,2012:31-33.

[12] 胡詠梅,張歡.一種改進的無線傳感器網(wǎng)絡質心定位算法[J].計算機工程與科學,2012,34(2):45-49.

[13] Niculescu D,Nath B.DV-based positioning in Ad Hoc network-s[J].Journal of Telecommunication Systems,2003,22(1/4):267-280.

[14] 肖碩,魏學業(yè),王鈺.基于信標優(yōu)化選擇的無線傳感網(wǎng)絡定位方法研究[J].電子測量與儀器學報,2009,23(3):65-68.

[15] Sichitiu M L,Ramadurai V.Localization of wireless sensor networks with a mobile beacon[C]∥2004 IEEE International Conference on Mobile Ad Hoc and Sensor Systems,Fort Lauderdale,2004:174-183.

[16] 劉志華,趙壽君,齊冬梅.三維無線傳感器網(wǎng)絡節(jié)點的序列垂心定位[J].信息系統(tǒng)與網(wǎng)絡,2010,40(4):4-6.

[17] 杜巧玲.無線傳感器網(wǎng)絡三維節(jié)點定位問題的研究[D].長春:吉林大學,2009:34-46.

[18] 戴桂蘭,趙沖沖,邱巖.一種基于球面坐標的無線傳感器網(wǎng)絡三維定位機制[J].電子學報,2008,36(7):1297-1303.

[19] Shareef A,Zhu Y F,Musavi M.Localization using neural networks in wireless sensor networks[C]∥Mobilware’08,Innsbruck,Austria,2008:12-15.

[20] Shaifu R,Mohammad R,Youngil P,et al.Localization of wireless sensor networks using artificial neural networks[C]∥9th International Symposium on Communications and Information Technology,ISCIT 2009,2009:639-642.

Research review on wireless sensor networks node localization*

Lü Shu-fang

(College of Information,Shanxi Agricultural University,Jinzhong 030800,China)

Abstract:Localization technology of wiress sensor networks(WSNs)is deeply discussed and analyzed in some aspects such as classification of WSNs localization algorithms,evaluation criteria,range-based and range-free localization algorithms.Several typical algorithms are mainly compared,analysis results show that different algorithms adapt to a single application environment,appropriate algorithm should be selected combined with actual needs.Several new-style localization methods including mobile beacons node localization algorithm,three dimensional space localization algorithm and intelligent localization optimization algorithms are analyzed.Problems exist in WSNs localization research is summarized and improved research direction in the future is given.

Key words:wireless sensor networks(WSNs);localization technology;algorithms classification;new type WSNs localization method;intelligent localization

DOI:10.13873/J.1000—9787(2016)05—0001—03 10.13873/J.1000—9787(2016)05—0009—04

收稿日期：2015—09—06

*基金項目：山西省科技基礎條件平臺建設項目(20110910003—0103)；山西省回國留學人員科研資助項目(2011—029)

中圖分類號:TP 393

文獻標識碼:A

文章編號:1000—9787(2016)05—0001—03

作者簡介:

呂淑芳(1988-)，女，山西呂梁人，碩士研究生，研究方向為無線傳感器網(wǎng)絡定位、物聯(lián)網(wǎng)。