無線傳感器網絡三維定位算法綜述

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

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

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

1 定位方法綜述

1.1 距離測量方法綜述

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

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

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

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

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

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

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

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

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

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

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

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

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

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

⑴三邊測量法

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

⑵基于GPS的節點定位系統

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

1.3 距離無關的定位算法綜述

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

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

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

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

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

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

1.4 基于事件驅動定位算法綜述

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

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

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

圖2 燈塔法

2 三維定位算法綜述

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

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

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

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

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

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

文獻[17]在對普通三維質心算法研究前提下，使用了距離函數和指數函數進行了加權的優化。

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

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

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

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

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

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

綜上，大多數三維定位算法是在二維經典定位算法的基礎上發展而來，大部分還停留在理論仿真階段，缺少具體的通用的三維定位算法。大部分定位算法一般將待定區域劃分為理想的球面或者正方體網格區域，利用機器學習、統計方面的數學模型或者最優化算法（最小二乘法等）進行定位的迭代和優化，從而模擬現實的定位，提高定位的精度?？傊ㄎ凰惴壳叭匀皇荳SN的一個重要研究領域，因為定位是WSN基礎服務的重要支撐技術。綜上所述的定位算法各有優點和不足，為每個節點提供準確的坐標位置是不可能的，如何在現有算法框架是盡可能提高定位精度仍然是重要的研究方向。結合實際的運用，在成本和定位性能兩者的前提制約下，目前主要采用測距算法同時對定位結果進行優化，根據近幾年的文獻綜述，神經網絡、支持向量機等機器學習技術成為定位算法提高定位精度和性能的研究熱點。基于事件驅動的定位算法是一個新興的研究領域，有待進一步地挖掘。

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

[2]李曉維，徐勇軍，任豐原.無線傳感器網路技術[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]朱紅霞,陳曙.一種新的基于非測距的無線傳感器網絡三維定位算法[J].傳感技術學報,2009,22(11):1656-1658.

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

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

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

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

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

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

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

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

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

[21]趙成林,魏雄烈,孫學斌,等.一種基于粒子群算法的三維無線傳感器網絡定位方法 [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的無線傳感器網絡三維定位算法[J].電子學報,2012,40(4):821-823.

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

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

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

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