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

呂淑芳

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

綜述與評論

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

呂淑芳

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

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

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

0引言

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

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

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

1.1定位算法的性能評價指標(biāo)和算法分類

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

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

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

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

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

目前公認(rèn)的分類算法是距離相關(guān)算法和距離無關(guān)算法。

1.2距離相關(guān)的定位算法

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

1.2.1TOA

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

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

1.2.2TDOA

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

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

1.2.3AOA

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

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

1.2.4RSSI

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

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

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

表1　距離相關(guān)測距技術(shù)比較

1.3距離無關(guān)的定位算法

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

1.3.1質(zhì)心定位算法

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

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

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

1.3.3近似三角形內(nèi)點測試算法

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

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

表2　距離無關(guān)定位算法性能比較

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

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

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

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

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

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

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

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

2.2三維空間定位技術(shù)

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

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

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

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

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

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

3結(jié)束語

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

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

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

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

參考文獻(xiàn):

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

[2]王亮,曹建安.無線傳感器網(wǎng)絡(luò)定位算法研究進(jìn)展[J].現(xiàn)代電子技術(shù),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)絡(luò)節(jié)點定位與覆蓋控制理論及技術(shù)研究[D].武漢:武漢理工大學(xué),2006:40-42.

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

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

[12] 胡詠梅,張歡.一種改進(jìn)的無線傳感器網(wǎng)絡(luò)質(zhì)心定位算法[J].計算機(jī)工程與科學(xué),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] 肖碩,魏學(xué)業(yè),王鈺.基于信標(biāo)優(yōu)化選擇的無線傳感網(wǎng)絡(luò)定位方法研究[J].電子測量與儀器學(xué)報,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)絡(luò)節(jié)點的序列垂心定位[J].信息系統(tǒng)與網(wǎng)絡(luò),2010,40(4):4-6.

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

[18] 戴桂蘭,趙沖沖,邱巖.一種基于球面坐標(biāo)的無線傳感器網(wǎng)絡(luò)三維定位機(jī)制[J].電子學(xué)報,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

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

中圖分類號:TP 393

文獻(xiàn)標(biāo)識碼:A

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

作者簡介:

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