無線傳感器網絡節點定位研究綜述*

呂淑芳

(山西農業大學 信息學院，山西 晉中 030800)

綜述與評論

無線傳感器網絡節點定位研究綜述*

呂淑芳

(山西農業大學 信息學院，山西 晉中 030800)

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

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

0引言

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

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

1定位算法的研究現狀

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

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

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

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

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

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

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

1.2距離相關的定位算法

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

1.2.1TOA

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

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

1.2.2TDOA

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

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

1.2.3AOA

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

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

1.2.4RSSI

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

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

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

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

1.3距離無關的定位算法

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

1.3.1質心定位算法

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

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

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

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

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

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

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

1.4計算節點位置的主要方法

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

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

2新型無線傳感器網絡定位算法

在傳統定位方法—靜態的定位技術的基礎上，新型的無線傳感器網絡定位算法應運而生。如，信標節點由靜止的變為動態的，用移動的錨節點去定位未知節點；將二維空間的定位拓展到三維空間；定位算法初步定位，智能優化算法實現進一步的優化，提高定位精度等。

2.1移動信標節點定位

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

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

2.2三維空間定位技術

現有的多數定位技術都是針對二維空間,然而隨著傳感器網絡三維空間定位需求的不斷發展,三維空間定位成為研究的趨勢與熱點。

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

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

2.3智能優化定位

隨著無線傳感器網絡定位技術的發展，傳感器節點本身性能的提升，對定位要求越來越高，智能優化定位算法成為趨勢。

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

3結束語

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

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

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

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

參考文獻:

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

[2]王亮,曹建安.無線傳感器網絡定位算法研究進展[J].現代電子技術,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]王晟.無線傳感器網絡節點定位與覆蓋控制理論及技術研究[D].武漢:武漢理工大學,2006:40-42.

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

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

[12] 胡詠梅,張歡.一種改進的無線傳感器網絡質心定位算法[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] 肖碩,魏學業,王鈺.基于信標優化選擇的無線傳感網絡定位方法研究[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] 劉志華,趙壽君,齊冬梅.三維無線傳感器網絡節點的序列垂心定位[J].信息系統與網絡,2010,40(4):4-6.

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

[18] 戴桂蘭,趙沖沖,邱巖.一種基于球面坐標的無線傳感器網絡三維定位機制[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-)，女，山西呂梁人，碩士研究生，研究方向為無線傳感器網絡定位、物聯網。