無線傳感器網(wǎng)絡三維定位算法綜述

楊 利 ，閔 輝 ，劉琳嵐 ，舒 堅

(1.池州學院 數(shù)學與計算機科學系,安徽 池州247000;2.江西科技學院 商學院數(shù)字技術(shù)系,江西 南昌330029;3.南昌航空大學 a.物聯(lián)網(wǎng)技術(shù)研究所;b.軟件學院,江西 南昌 330063)

無線傳感器網(wǎng)絡定位技術(shù)是WSN最基礎(chǔ)的服務，是WSN管理與應用的重要組成部分[1]。沒有節(jié)點的定位信息，就無法獲取或者跟蹤具體位置發(fā)生的事件。比如，在森林部署火災預警傳感器節(jié)點，如果發(fā)生火災的預警信息，在無法確定空間具體位置前提下，這種應用是沒有實用價值的。進一步地來說，節(jié)點的定位技術(shù)是必要，在地圖導航、目標追蹤、定位相關(guān)的服務中，可以發(fā)揮關(guān)鍵的作用。

1 定位方法綜述

1.1 距離測量方法綜述

大量定位技術(shù)的基礎(chǔ)依賴于節(jié)點之間的物理距離的估算。這種距離估算一般可以通過信號達到的強度、信號的傳輸時間和到達的角度的手段來完成，通過幾何關(guān)系求解和估算待定節(jié)點與錨節(jié)點之間的距離，這是實現(xiàn)WSN定位過程的基礎(chǔ)。

⑴到達時間方法（Time of Arrival，ToA）

ToA方法也稱為Time of Flight方法。它的基本原理是根據(jù)信號的傳輸速度和達到時間來計算節(jié)點之間的距離，即利用往返時間來估測節(jié)點間距離。但是這種方法或者類似的方法要求發(fā)射節(jié)點和接收節(jié)點保持時鐘一致。否則，必須利用往返時間、扣除延時的時間來估測距離[2]。ToA方法主要分為以下三種，如圖1所示。

圖1 TOA的三種傳輸方式對比

對于上圖的A方式來說，節(jié)點i和節(jié)點j的距離disi,j計算公式為：disi,j=（t2-t1）×ν。 其中 t1和 t2分別是發(fā)射信號和接收信號的時間。ν表示信號的傳播速率。

⑵到達時間差方法（Time Difference of Arrival，TDoA）

TDoA的基本原理是在節(jié)點之間使用兩種信號以不同的速率進行節(jié)點的傳輸測距，測距原理類似ToA。比如，在節(jié)點之間首先發(fā)送一個無線電信號，分別記錄下發(fā)送和接收的時間t1和t2。同時發(fā)送一個聲波信號，記錄下間隔的時間twait=t3-t1。所以，接收節(jié)點能根據(jù)上述參數(shù)計算距離，dis=(ν1-ν2)×(t4-t2-twait)。基于TDoA的測距方法不需要發(fā)送和接收之間的時鐘同步并且可以獲得較高的精度。不足之處在于TDoA需要額外的硬件，比如發(fā)送聲波信號的話需要麥克風和揚聲器。

⑶到達角度方法（Angle of Arrival）

到達角度的測量方法是通過計算信號傳輸?shù)慕嵌葋硗瓿蓽y距的，需要額外的硬件獲取信號的夾角，但是精度不高。這種測距方法前提條件是已知兩個節(jié)點和它們之間的夾角或者三個節(jié)點組成的三角形，從而利用平面幾何的基本原理計算距離。

接收信號強度的方法是利用節(jié)點信號在傳輸過程中衰減特性來確定節(jié)點之間的距離。通常使用RSSI（Received Signal Strength Indicator）來表示信號接收強度的具體數(shù)值。RSSI的取值范圍一般是從 0到 RSSI_Max，RSSI_Max的 取 值 范 圍 為100，128 和 256。

使用RSSI方法，需要對噪聲針對分析并進行濾波，濾波方法對于線性的噪聲一般作用明顯，但是對于非線性噪聲則處理誤差較大，方法還不是很成熟。

定位算法的模型大都基于統(tǒng)計方法，要進行濾波，常用的方法有EKF[4]、貝葉斯濾波、卡爾曼濾波、擴展的卡爾曼濾波器和非差覺型卡爾曼濾波器等方法。

1.2 基于測距的定位算法綜述

基于測距的定位算法關(guān)鍵在于找出待定位節(jié)點和已知錨節(jié)點之間的幾何關(guān)系。基于幾何計算原理的比較常見的定位方法是三邊測量法（Triangulation）和基于的角度測量方式。

⑴三邊測量法

三邊測量法基本原理是利用平面幾何的三角形關(guān)系來計算節(jié)點的位置。三邊測量法是多邊測量法的特例，三邊測量法的關(guān)鍵在于獲取三邊的距離，距離的測量方法有多種，一般可以利用RSS、TOA、TDOA、RTOF、PDOA、NFER 近場電磁測距來獲得估測距離。

⑵基于GPS的節(jié)點定位系統(tǒng)

GPS主要實現(xiàn)原理是通過至少4顆衛(wèi)星的信號，獲取衛(wèi)星到終端的距離，從而列出3個距離的方程，利用三維坐標的計算公式求解三維坐標。類似的系統(tǒng)還有我國的北斗系統(tǒng)、歐洲的伽利略系統(tǒng)和俄羅斯的GLONASS系統(tǒng)。雖然在WSN中給每個節(jié)點安裝GPS的成本過高，功耗過大，但是為了保證定位的準確性，會給少量節(jié)點配置GPS模塊以作為其他節(jié)點定位的參考點。

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

在基于測距的算法中，節(jié)點距離的測量方法常用的有RSS，ToA，TDoA和AoA等。相比之下，距離無關(guān)的測距算法計算節(jié)點之間的距離依賴于連通度，不同于距離相關(guān)算法中的距離或者角度的計算。

距離無關(guān)算法的主要優(yōu)勢在于不需要額外的硬件設(shè)施支持，但是定位精度比不上基于測距的算法。主要距離無關(guān)的定位算法典型代表是APS算法。

APS[7]（Ad Hoc Positioning System）是一種分布式的基于連通度的定位算法。該算法在確定待定節(jié)點的位置至少需要三個或者以上的錨節(jié)點的具體坐標，而且錨節(jié)點越多，定位的誤差越小。在APS定位算法中，最常見的是DV-hop算法，基本原理和APS接近。在DV-hop算法中，節(jié)點首先建立一張表{Xi,Yi,hi}，其中{Xi,Yi}表示第i個節(jié)點的坐標，hi表示第個i節(jié)點和參考節(jié)點的跳數(shù)。當一個錨節(jié)點獲得和其他錨節(jié)點的距離，則得到一跳的平均距離（修正值）。

通常，第i個節(jié)點的平均跳距Ci定義為：

由公式可知，只要給出了足夠錨節(jié)點的坐標和平均跳距，就能獲取待定節(jié)點的坐標。

在DV-hop算法的基礎(chǔ)上，提出了一種改進的算法稱為DV-distance。在該算法中，待定節(jié)點和錨節(jié)點的距離的計算基于信號傳播的強度取代了跳數(shù)，該算法能提供更好的定位粒度，而且定位的魯棒性更好。

1.4 基于事件驅(qū)動定位算法綜述

基于事件驅(qū)動定位算法不同于前面兩類定位算法，它的核心思想是利用事件來計算節(jié)點間距離、角度和位置坐標，從而實現(xiàn)節(jié)點的定位。事件可以是關(guān)于某個傳感器節(jié)點的無線信號的到達、光信號和聲波信號的傳播。

作為其中典型代表的燈塔定位算法（The Lighthouse Approach）系統(tǒng)[8]在“微塵”項目中得到了運用，并取得了較高的定位精度。定位系統(tǒng)中的節(jié)點必須安裝光信號接收模塊，如圖2所示，在該系統(tǒng)中，存在一個光源信號發(fā)射節(jié)點，待定節(jié)點能夠接收光信號，節(jié)點和光源節(jié)點的距離d的計算有如下的公式：

t1表示待定節(jié)點首次接收到光信號的時間，t2表示待定節(jié)點中斷接收光信號的時間，表示節(jié)點再次接收光信號的時間。

圖2 燈塔法

2 三維定位算法綜述

現(xiàn)有的三維定位算法主要的研究方法歸納為兩類：第一類是直接將二維定位算法和機制推廣到三維定位上，由于三維空間不同于二維，許多二維空間的幾何問題因為問題難度的增加而變得異常復雜，算法的時間和空間復雜度也比二維多出一個或者多個數(shù)量級。總之，三維空間的不均勻性，使得三維定位必須要考慮網(wǎng)絡拓撲結(jié)構(gòu)的變化。第二類是將三維定位的問題規(guī)約到二維平面上解決，涉及到降維的過程。國內(nèi)外的主要相關(guān)研究成果綜述如下：

在WSN中，定位算法的研究仍然是一個研究熱點。傳統(tǒng)的定位算法主要分為距離相關(guān)算法（基于 RSS、TOA 和 TDOA）和無關(guān)的算法（DOA）兩大類。在節(jié)點距離或者角度測量手段中，大部分算法使用了TOA （到達時間）、DOA （到達時間差）[9-10]、RSS（接收信號強度）等手段。

文獻 [11]針對三維環(huán)境的節(jié)點的自定位，在ROCRSSI算法和ALS算法的基礎(chǔ)上，提出了基于非測距的分布式三維定位算法（DBRF-3D），該算法不需要測量節(jié)點實際距離，在錨節(jié)點一跳的通信范圍內(nèi)，由未知節(jié)點接收錨節(jié)點的廣播信息從而估計自身的位置。

文獻[12]為提高三維空間節(jié)點定位的精度，將節(jié)點分布的區(qū)域分割為若干空間立方體，同時利用中垂面進一步地縮小待定位節(jié)點的空間立方體，利用錨節(jié)點通信半徑作為約束條件，取待定區(qū)域的質(zhì)心作為定位的結(jié)果。文獻[13]在Landspace-3D算法的基礎(chǔ)上，提出了一種距離無關(guān)的SBLS三維定位算法，使用球面坐標構(gòu)建系數(shù)矩陣進行節(jié)點的定位計算，從而利用克萊姆法則求解線性方程組，并利用最小二乘法進行優(yōu)化。

文獻[14]在三維空間的節(jié)點定位背景下，提出3D-DRL算法（分布式非測距三維定位算法）將待定位區(qū)域立體網(wǎng)格化，通過立體網(wǎng)格投票的方式，選取最大值的網(wǎng)格質(zhì)心作為定位結(jié)果。文獻[15]在三維空間網(wǎng)絡劃分定位算法的基礎(chǔ)上，結(jié)合融合收斂迭代的思想，提出了功率分級收斂迭代定位算法，算法將定位區(qū)域劃分為球殼區(qū)域，對定位的球殼中的錨節(jié)點進行二次功率分級，取質(zhì)心作為定位的結(jié)果。

文獻 [16]提出了一種基于測距的三維定位算法，主要采用TDOA的節(jié)點測距手段，利用矩陣迭代優(yōu)化算法實現(xiàn)節(jié)點的定位。

文獻[17]在對普通三維質(zhì)心算法研究前提下，使用了距離函數(shù)和指數(shù)函數(shù)進行了加權(quán)的優(yōu)化。

文獻[18]在四邊測量和RSSI測距手段的基礎(chǔ)上，在定位優(yōu)化中采用加權(quán)平均的思想，通過自校正系數(shù)對RSSI測距誤差和網(wǎng)絡定位誤差進行自校正從而實現(xiàn)節(jié)點的定位。文獻[19]在RSSI和三邊測距法的基礎(chǔ)上，選擇RSSI值較大的錨節(jié)點參與定位，提出了利用動態(tài)修正三邊測量定位算法對RSSI值進行定位計算。文獻[20]在RSSI測距方法的基礎(chǔ)上，利用局部性原理來獲取RSSI的衰減系數(shù)，將二維定位擴展到三維，有效地減少測距的計算誤差，提高三維定位的精度。文獻[21]在RSSI測距的基礎(chǔ)上，引入粒子群算法進行迭代優(yōu)化計算。

文獻 [22]提出了DCP3D算法，該算法是在DV-Hop算法的基礎(chǔ)上，利用四邊定位手段和共面度的數(shù)學優(yōu)化思想，通過共面度閾值和跳數(shù)閾值的約束減少不良節(jié)點的比例，提高三維定位的性能。文獻[23]也是在DV-Hop算法的基礎(chǔ)上，提出了基于多重共線性的三維DV-Hop定位算法。通過在算法中引入共線度來約束節(jié)點之間的拓撲關(guān)系，設(shè)定多重共線性閥值，減少通信開銷，提高定位性能。

文獻[24]提出了基于Euclidean的三維定位算法。該算法將節(jié)點的測距轉(zhuǎn)化為六面體模型頂點間距離的求解。通過立體模型和坐標法，對未知節(jié)點和錨節(jié)點之間的距離進行計算和循環(huán)迭代求精。

文獻[25]將神經(jīng)網(wǎng)絡技術(shù)應用在節(jié)點定位中。為降低多跳距離累加產(chǎn)生的誤差，利用BPL算法（BP神經(jīng)網(wǎng)絡的多跳定位算法）來逼近有效距離和歐式距離的函數(shù)關(guān)系和建立樣本，通過泰勒級數(shù)展開的最小二乘迭代法進行定位求精，BPL算法通過消耗一定的能耗來提高定位精度，能有效地降低多跳距離對定位的影響。

文獻[26]在三維定位中利用距離相關(guān)的測距手段將節(jié)點之間歐式距離構(gòu)成相似度矩陣，在MDS（多維尺度分析算法）降維優(yōu)化的算法基礎(chǔ)上提出了Fast MDS MAP算法和LMDS算法，從而有效減少定位過程中的節(jié)點能耗和運算的時間復雜度。

文獻[27]在APIT距離無關(guān)的測距方法基礎(chǔ)上，提出了三維定位的APIT-3D定位算法，主要選取4個錨節(jié)點構(gòu)成四面體，通過計算四面體的重心獲取定位結(jié)果。文獻[28]在基于跳數(shù)和基于距離兩種方式的前提下，通過構(gòu)建球待定節(jié)點體區(qū)域，對三維空間節(jié)點的抽樣約束和進一步地加權(quán)篩選，實現(xiàn)節(jié)點的三維抽樣定位。

綜上，大多數(shù)三維定位算法是在二維經(jīng)典定位算法的基礎(chǔ)上發(fā)展而來，大部分還停留在理論仿真階段，缺少具體的通用的三維定位算法。大部分定位算法一般將待定區(qū)域劃分為理想的球面或者正方體網(wǎng)格區(qū)域，利用機器學習、統(tǒng)計方面的數(shù)學模型或者最優(yōu)化算法（最小二乘法等）進行定位的迭代和優(yōu)化，從而模擬現(xiàn)實的定位，提高定位的精度。總之，定位算法目前仍然是WSN的一個重要研究領(lǐng)域，因為定位是WSN基礎(chǔ)服務的重要支撐技術(shù)。綜上所述的定位算法各有優(yōu)點和不足，為每個節(jié)點提供準確的坐標位置是不可能的，如何在現(xiàn)有算法框架是盡可能提高定位精度仍然是重要的研究方向。結(jié)合實際的運用，在成本和定位性能兩者的前提制約下，目前主要采用測距算法同時對定位結(jié)果進行優(yōu)化，根據(jù)近幾年的文獻綜述，神經(jīng)網(wǎng)絡、支持向量機等機器學習技術(shù)成為定位算法提高定位精度和性能的研究熱點。基于事件驅(qū)動的定位算法是一個新興的研究領(lǐng)域，有待進一步地挖掘。

[1]于海斌，曾鵬.智能無線傳感器網(wǎng)絡系統(tǒng)[M].北京：科學出版社，2006.

[2]李曉維，徐勇軍，任豐原.無線傳感器網(wǎng)路技術(shù)[M].北京：北京理工大學出版社.2007.

[3]D.Niculescu B.Nath.Ad hoc positioning system(APS)using AoAa[C].SanFrancisco:IEEE INFOCOM,2003:1734-1743.

[4]H.Chen D.Ping Y.Xu X.Li.A Novel Localization Scheme Based on RSS Data for Wireless Sensor Networks[J].Advanced Web and Network Technologies and Applications，2006(16-18):315-320.

[5]Hofmann-Wellenhof,B.H.Lichtenegger J.Collins.Global Positioning System:Theory and Practice[M].Cham:Springer，2008.

[6]Dana,P.H.Global Positioning System(GPS):Time-disseminati on for real-time applications[J].Real-Time Systems,1997,12(1):9-40.

[7]Niculescu,D.B.Nath.Ad hoc positioning system (APS)[C]//IEEE Global Proc.of Telecommunications Conference(GLOBECOM),2001.

[8]R mer,K.The lighthouse location system for smart dust[C]//Proc.of the 1st International Conference on Mobile Systems,Applications and Services,2003:15-30.

[9]Zhao,F.W.Yao C.C.Logothetis Yonghua Song.Superresolution TOA Estimation in OFDM Systems for Indoor Environments[C]//IEEE InternationalConference on Networking,Sensing and Control,2007:723-728.

[10]Zanier,F.M.Luise.Fundamental issues in time-delay estimation of multicarrier signals with applications to next-generation GNSS [C]//International Workshop on Signal Processing for Space Communications,2008:1-8.

[11]朱紅霞,陳曙.一種新的基于非測距的無線傳感器網(wǎng)絡三維定位算法[J].傳感技術(shù)學報,2009,22(11):1656-1658.

[12]劉志強,王行甫.基于中垂面分割的 WSN三維定位方法[J].計算機工程,2010,36(14):90-93.

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

[14]王德華,邢建平,張軍.無線傳感網(wǎng)的分布式非測距三維定位算法[J].北京航空航天大學學報,2010,36(2):206-209.

[15]段榮鑫.無線傳感器網(wǎng)絡三維定位算法研究[D].濟南：山東大學,2011.

[16]鄒杰,李珊君.高精度無線傳感器網(wǎng)絡三維定位算法[J].計算機工程,2011,37(10):99-101.

[17]占宏,黎善斌,胥布工.基于WSNS中距離函數(shù)和指數(shù)函數(shù)的三維質(zhì)心定位算法[J].傳感器與微系統(tǒng),2011,30(5):136-138.

[18]李剛,陳俊杰.基于信標節(jié)點RSSI自校正的WSN三維定位[J].華中科技大學學報:自然科學版,2011(S2):347-350.

[19]宋婉甜,李智.一種新的無線傳感網(wǎng)絡三維定位方法[J].信息與電子工程,2012,10(3):257-259.

[20]崔秀鋒.無線傳感器網(wǎng)絡中基于RSSI三維定位改進算法研究[D].太原:太原理工大學,2011.

[21]趙成林,魏雄烈,孫學斌,等.一種基于粒子群算法的三維無線傳感器網(wǎng)絡定位方法 [J].中國電子科學研究院學報，2011，6(1):77-81.

[22]Keji,M.Z.Xiaomin S.Ben C.Qingzhang.Three Dimensional Localization Algorithm Based on Degree of Coplanarity for Wireless Sensor Networks[J].Chinese Journal Of Sensors And Actuators，2011(10):1484-1488.

[23]嚴筱永,錢煥延,高德民,等.一種基于多重共線性的三維DV-Hop定位算法[J].計算機科學,2011,38(5):37-39.

[24]唐良瑞,宮月,羅藝婷，等.一種基于Euclidean的無線傳感器網(wǎng)絡三維定位算法[J].電子學報,2012,40(4):821-823.

[25]郭曉雷,于寧,吳銀鋒,等.BP神經(jīng)網(wǎng)絡在無線傳感器網(wǎng)絡三維定位中的應用[J].高技術(shù)通訊，2011，21(5):471-477.

[26]周祖德,胡鵬,劉泉,等.一種基于MDS的無線傳感器網(wǎng)絡快速定位算法[J].傳感技術(shù)學報，2007，20(10):2303-2307.

[27]劉玉恒，蒲菊華，赫陽，等.無線傳感器網(wǎng)絡三維自身定位方法[J].北京航空航天大學學報，2008，34(6):647-651.

[28]于寧，萬江文，馬萬興.無線傳感器網(wǎng)絡三維抽樣定位[J].北京郵電大學學報，2008，31(3):13-15.