無線網絡定位技術分析及發展綜述

呂奇辰，龐麗莉，謝家燁

（1.中國人民解放軍94789部隊 江蘇 南京 210018；2.南京工程學院 江蘇 南京 211167）

無線網絡定位技術分析及發展綜述

呂奇辰1，龐麗莉2，謝家燁2

（1.中國人民解放軍94789部隊 江蘇 南京 210018；2.南京工程學院 江蘇 南京 211167）

基于梳理無線網絡定位技術的發展現狀、分析其現有定位算法和系統的優勢及存在問題的目的，依據定位技術的基本原理和評估標準，采用分類對比法，從定位精度、定位規模、算法復雜度、算法適應性、算法可行性等幾個方面對定位算法進行綜合分析，在考慮定位算法和系統的定位精度以及可行性的情況下，得出不同應用環境下，定位方案的具體分類和優化改進措施。

無線網絡；節點定位；二維定位；定位誤差

無線網絡中的定位技術是確定參考坐標系下物體的空間位置信息。對無線網絡中的節點而言，不知道位置而感知的數據是沒有意義的[1]。通過節點得到的數據只有與其位置、時間相對應，才能實現對探測目標和事件的定位和分析。現有的定位算法針對無線傳感器網絡中的節點定位及通信網絡中的移動目標定位做了大量研究，針對應用需求提出了很多解決方案，比如無線傳感器網絡中的定位算法要考慮到節點能耗、硬件成本、定位精度（區域定位或精確定位）等；移動通信中的定位算法需要考慮基站分布、目標的移動性、環境中的干擾等。每種算法都有側重及應用限制，但原理和過程基本一致，因此可以統稱為無線網絡中的節點定位。

獲取位置信息的直接方法就是配備GPS接收裝置，廣泛用于定位的GPS技術對大部分無線應用而言，成本高并會受到環境及系統能耗等限制，在非視距 （non-line-of-sight，NLOS）傳播環境中，微弱的衛星信號易被遮蔽。第二種方法是布置一定數量已知自身位置 （通過人工測量或者安裝GPS接收機）的錨節點（anchor node），采用某種測量手段及估計方法確定位置信息未知的節點（unknown node）的位置，可以是絕對位置信息或者相對位置信息。第三種方法是系統中無錨節點，節點依據相互的距離信息或跳數來獲得相對位置坐標。

1 定位算法的分類和評估指標

1.1 算法分類

獲得節點位置信息的算法有很多，如圖1所示按照定位范圍、定位結果、算法處理方式、信息獲取方式等進行分類，基于信息獲取方式的分類方法更側重于基本的定位原理且定位過程比較清晰，測距（range-based）定位法是對距離、角度等信息進行直接測量，然后對未知節點的位置進行計算或估計，定位精度相對較高，對節點本身硬件要求較高；非測距（range-free）定位法一般通過跳數或者通信范圍來估算未知節點與錨節點之間的距離或相對信息，主要依賴網絡部署，算法易實現，對硬件要求低，功耗低。

1.2 評估指標

評估指標包括精度、計算開銷、硬件支持等，幾種主要的評估標準如下。

定位誤差：定位誤差是評價定位算法性能的首要標準，通常可以用單點位置估計的均方誤差（MSE）及均方根誤差（RMSE）、與錨節點布局相關的幾何稀釋因子（GDOP）、誤差限克拉美羅下界 （CRLB）和考慮通信射程的相對定位誤差（RPE）等來表述。

算法開銷：計算開銷、通信開銷、算法復雜度等。

錨節點個數：越多的錨節點越能為定位提供更多的參考，但增加錨節點會增加系統成本、算法復雜度和計算難度。

定位規模：如果錨節點的數量有限，且要求適當的定位精度，能對多少節點進行定位也是一項重要的評價指標，關系到定位算法的普適性。

是否需要輔助硬件支持：為了提高定位精度，有時會采用輔助手段，如GPS、氣壓測高、超聲波輔助測距等，會增加系統的成本，限制算法的應用。

圖1 定位算法的分類

圖2 節點定位過程

2 節點定位過程

對未知節點進行定位可分為3個階段，信息獲取階段、位置估計階段和定位求精階段，如圖2所示。信息獲取階段是獲取未知節點和錨節點間的距離信息和連通度，距離信息包括測距/測角或距離估計，而連通度表征了未知節點能夠接收到來自錨節點的信息，可用于節點定位。位置估計階段包括用代數方法解方程，或用幾何方法對未知節點的位置進行約束。經過前兩個階段，可得到未知節點的位置信息，但誤差累積會嚴重影響定位結果，因此對每個階段產生的誤差進行修正和處理，才能得到更精確的定位信息。

2.1 信息獲取階段

TOA（Time of arrival）：對未知節點和錨節點之間的無線信號傳播時間進行測量，根據信號傳播速率求得距離。可分為單程測距和雙程測距，單程測距需要嚴格的時間同步；雙程測距包含了簡單的時間同步算法。基于TOA測距技術的定位算法精度很高，GPS全球定位系統就是其典型應用。

TDOA（Time Difference of Arrival）：一是采用不同的信號進行測距，需增加超聲波裝置等額外的硬件，根據兩種信號的到達時間差以及傳輸速率來計算未知節點與錨節點間的距離，典型的應用系統有Cricket系統和AHLos系統；二是Chan[2]采用的算法，用同一種無線信號，記錄未知節點和兩個不同錨節點的信號傳播時間差，只需錨節點時間同步即可。

AOA（Angel of Arrival）：能夠得到無線信號的發送或者接收方向，獲得未知節點和錨節點之間的角度信息。基于AOA的定位算法能確定節點的坐標和方位，需要天線陣列等硬件，通信能耗增加，且測距過程易受環境影響。E911系統中就采用此方案來確定目標方位，另外機器人導航系統中也常采用AOA技術。

RSSI（Received Signal Strength Indicator）：表示節點接收到的信號強度，定義為：RSSI（d）=PT-P（d），d為發送端到接收端間的距離，PT為發射信號強度，P（d）是與發送端距離為d處的信號強度，是在參考距離d0處的信號強度，n是路徑損耗因子，接收節點距離發射節點越近RSSI值越大。獲取RSSI值十分容易，無需額外硬件支持，典型的應用有RADAR和SpotON等。

距離估計方法：如DV-Hop（Distance Vector-Hop）算法[3]中，錨節點根據彼此之間的跳數和已知的距離來計算平均跳距，未知節點由此獲得與錨節點之間的估計距離。DV-Hop算法完全基于節點密度以及部署條件，交換距離的方式大大增加節點間的通信量，另外利用跳距對距離進行估計，會導致平均定位誤差增大。類似的還有 Amorphous定位算法[4]，與DV-Hop算法不同的是其平均跳距的確定與通信半徑和網絡連通度有關。

2.2 位置估計階段

主要包括代數法和幾何法，未知節點通過與錨節點間的距離或角度信息用代數法計算坐標，或者根據接收到的錨節點信號，及節點的通信半徑，建立幾何約束關系，確定位置。

2.2.1 代數求解方法（以二維空間為例）

三邊測量法：以錨節點為圓心畫半徑為錨節點到未知節點之間距離的圓，已知3個錨節點的坐標（x1，y1），（x2，y2）和（x3，y3）以及它們到未知節點的距離r1，r2和r3，估算出未知節點的坐標：。在不考慮測量誤差和NLOS誤差的理想情況下，如圖3所示，當3個錨節點位于一條直線上時方程無唯一解，需要更多錨節點或其它輔助措施作為參考來確定未知節點的位置坐標。

三角測量法：以AOA測角方法為基礎，錨節點的坐標和未知節點與錨節點的角度已知。如圖4所示，已知兩個錨節點A和C的坐標，X與A和C之間的角度為∠AXC，由α=∠AOC=，可唯一確定一個圓，得到圓心坐標（xo，yo）和半徑r1。同理可得另兩個圓的圓心坐標和半徑，由這3個圓的交點，用三邊測量法，可得未知節點坐標。

圖3 不能唯一確定未知節點的位置

圖4 三角測量法

多邊測量法：也可稱為極大似然估計法，是錨節點較多的情況下的一種優化解法，有n個錨節點，已知它們的坐標（x1，y1），…，（xi，yi），…，（xn，yn），以及到未知節點的距離 r1，…，ri，…，rn，然后列出一個二元二次方程組，用最小二乘法得到未知節點的坐標。

2.2.2 幾何約束方法

根據錨節點與未知節點的連通度或者通信情況，用多邊形、三角形等幾何形狀限定未知節點的范圍，并用其質心來估計未知節點的位置。幾何約束方法的定位精度與錨節點的密度和分布有密切關系。

南加州大學的Nirupama Bulusu等人提出的質心算法即多邊形約束，未知節點接收鄰近錨節點的信號，由錨節點組成多邊形的質心確定位置，算法基于網絡連通性，簡單易行。

APIT（Approximate point-in-triangulation test）算法[5]基于區域劃分，對網絡連通性有較高要求。未知節點接收所有鄰近錨節點的信息，每3個不同的錨節點組成三角形，窮舉所有錨節點的組合方案，根據PIT算法，判斷未知節點是否位于這些三角形內，位于其內的所有三角形的交集，就是未知節點可能的位置范圍，可用交集的質心作為未知節點的位置估計。

圓形區域約束是利用未知節點與錨節點之間的通信連接狀況，能夠通信的錨節點作為圓心，以節點的通信半徑為半徑，所有圓的交集（形成一個陰影）作為未知節點的存在范圍，能夠得到的錨節點信息越多，部署位置越接近未知節點，則約束范圍越小，但由于陰影的形狀不規則，較難選取最優的位置點，加利福利亞大學伯克利分校的Doherty等提出的Convex Position Estimatation算法中，將陰影的外矩形求出，并以矩形的質心作為未知節點的位置。

2.2.3 其它定位技術

除了上述方法，其它領域的技術也被應用于定位，如起源于心理測度學的數據分析技術多維標度法（MDS）、指紋識別（FP）等。前者可以獲取各點之間的相對位置關系，后者通過大量的現場數據建立指紋庫，對未知節點的信息進行判別，以達到定位的目的。

2.3 誤差主要來源和解決方法

2.3.1 信息獲取階段產生的誤差及針對性算法

在信息獲取階段，測距時就會產生測量誤差。其中NLOS傳播會給測距結果帶來極大的影響。精確的測距方法都是以視距傳播（Line of Sight，LOS）為基礎的，甚至RSSI值的獲取也會因為NLOS存在較大偏差。當無線傳輸信號受到遮擋、干擾時，節點之間的無線傳播是非直線的，只有反射和衍射路徑，導致無線信號中的LOS信號很弱，接收端無法檢測出直射路徑信號，產生NLOS誤差。在TOA測距方法中，由于NLOS傳播，使得信號傳播存在很大的延時，導致測量值大于實際距離，再利用三邊測量法或極大似然法進行定位時，無法得到精確的定位結果。而RSSI測距方法中，由于障礙干擾導致信號衰減過大，影響對未知點和錨節點之間距離的判斷。實際環境中NLOS傳播是普遍存在的，其統計特性在不同信道環境下有所不同，難以估計。由于與傳播環境有關，即使提高接收裝置對TOA的測量精度也無法消除NLOS誤差的影響。很多研究[6]都針對降低NLOS誤差做了大量的工作，P.C.Chen提出了殘差加權算法（Rwgh），利用定位殘差對定位結果進行加權，以抑制NLOS誤差，該算法無需信道的統計模型和先驗知識，但網絡規模變大時，算法的復雜度隨之增加。

除了NLOS誤差之外，TOA/TDOA算法的誤差來源主要是時間不能嚴格同步造成的，可用時鐘同步算法減小此類誤差，或采用協同算法同時完成時鐘同步和測距定位。TDOA算法雖然降低了對時間同步的要求，但輔助測量手段的引入也會帶來一定的測量誤差。

多徑傳播效應會干擾AOA測距算法的準確性，并會引起基于時間的定位算法的測量誤差，最小均方估計和邊緣檢測技術等能較好的抑制多徑干擾的影響。

RSSI算法是一種很粗略的測距技術，有可能產生±50%的測距誤差[7]，環境狀況對信道產生的影響難以用模型準確表達，文獻[8]對RSSI描述的對數衰減模型進行修正，將路徑損耗因子與未知節點與錨節點之間距離的變化用負指數函數表示，在節點覆蓋范圍較廣的情況下，采用此模型優勢較為明顯。如果節點覆蓋范圍不大（如室內等），也可以采用循環濾波等方法抑制噪聲，使RSSI和距離的關系趨于穩定。

文獻[9]中用K-means聚類方法通過聚類分析對誤差較大的距離信息進行篩選，有效的降低定位誤差。另外，采用兩種或以上定位技術或者采用其它輔助手段混合的數據融合定位法，如TOA/AOA，TOA/RSSI等，以互補的優勢和較高的精度被廣泛使用。

2.3.2 位置估計階段產生的誤差及針對性算法

當一些誤差較大的測距信息被排除掉后，如果只有兩3個錨節點與未知節點的距離（角度）信息，可直接進行定位，如果錨節點較多，如何利用這些距離（角度）信息進行定位，涉及到算法復雜度和最終的定位誤差。對某一個未知節點而言，錨節點的分布對其定位是有很大影響的，考慮到錨節點的布局規劃對整個網絡定位精度的影響，一些算法專門針對錨節點的幾何布局進行了研究。還有采用移動錨節點進行輔助定位的方法，相當于布設了大量的靜態錨節點，兼顧信號覆蓋率以及幾何位置對未知節點的定位影響，但移動錨節點的路徑規劃也存在許多待研究的問題。

在幾何約束方法中，定位精度直接受錨節點的數量和分布的影響，而對測量誤差不敏感，如果錨節點數量較少，定位誤差會非常大，因此為了改善定位效果，可將已定位的節點升級為錨節點或采用移動錨節點，或者直接采用MDS或FP方法減少錨節點數量對定位的影響。

2.4 定位方案優勢分析

根據節點定位過程，可以采用不同組合方式對未知節點進行定位，較常見的主要方案有：

TOA+三邊測量法/極大似然估計：適用于對定位要求較高的場合等。除了GPS系統采用這種方案，很多算法都會在考慮時間同步及抑制NLOS誤差的前提下采用此算法，如文獻[6]中提出的考慮非視距傳播影響的TOA定位算法，在惡劣的工業環境中的TOA優化定位方法[10]等。

TDOA+三邊測量法/極大似然估計：適用于范圍較小（若采用超聲波測距）的無線網絡中節點定位，對節點性能要求不高，算法復雜度適中。Cricket系統采用了TDOA+三邊測量法，適合錨節點較少的情況。AHLos系統則采用了TDOA+極大似然估計，并將已定位的節點升級為錨節點來緩解錨節點較少的問題，但會造成誤差累積。比較典型的Chan[2]算法，利用TDOA+極大似然估計對未知節點進行定位，在測量噪聲為零均值的高斯隨機噪聲時，其定位解能達到CRLB，定位精度高，但當存在NLOS干擾時，定位精度明顯下降，很多定位算法[6]都借鑒了其思想并加以改進。

RSSI+位置估計：無線傳感網絡一般會采用此方案，算法簡單、無需額外硬件、能耗低、精度不高，根據文獻[5]中的研究，當定位誤差小于傳感器節點無線通信半徑的40%時，對路由性能、目標跟蹤的精確度等影響不會很大。方案包括：RSSI+三邊測量法，如DV-distance算法[11]；RSSI+幾何定位法，例如采用RSSI值篩選錨節點，利用距離較近的錨節點用質心算法對未知節點定位[12]，定位精度介于測距與非測距算法之間，算法復雜度則與非測距算法類似；采用RSSI值（或節點連通度）+MDS建立相對坐標系統的MDS-MAP算法[13]，無需錨節點就可定位，如果提供幾個錨節點，也可實現絕對坐標定位；RSSI+指紋識別，微軟的RADAR系統是較早使用指紋識別的定位系統，采用匹配數據的方法定位，考慮了環境因素，需要大量的離線訓練數據，且對于不同的環境需要重新采集數據，成本較高，文獻[14]中提出無需訓練的指紋識別定位算法，通過時域有限差分（FDTD）仿真來建立指紋庫，節省離線訓練時間。

單獨使用AOA+三角測量法的算法較少，多作為輔助手段與其它算法配合定位。另外在特定的場合會采用特定的算法，比如適用于農田環境的無需錨節點的定位算法[15]，可以取得節點的相對位置坐標，但對環境知識的依賴度較高；在水下定位中，由于環境的特殊性以及不易部署固定的錨節點，RSSI測距以及幾何約束方法不適合應用于此。

3 結束語

大部分無線網絡應用都受限制于能量，而現有的定位算法中，高精度和低能耗的矛盾還沒有更好的解決方法，平衡精度和能耗且具有較廣的適用范圍，是定位算法需要考量的重要方向。其次，目前無線網絡的覆蓋率高、發展迅速，基于無線網絡的節點定位面臨著不能忽視的安全問題，如節點的定位過程中受到攻擊、對惡意節點定位造成的能耗等都會影響節點的正常工作。

根據現有的研究情況分析，二維定位算法的體系相對比較成熟，從定位精度、適用范圍等方面都有大量深入的研究，但其應用比較有局限性。需要定位的節點往往位于三維環境中，由于增加了一個維度，定位所需的硬件要求和算法復雜度增加，導致二維定位算法在三維定位中不一定適用，可能會引起定位多解的問題。因此，對三維定位算法的研究不能僅從定位精度考慮，需要新的思路以保證算法有效可行。

[1]王福豹，史龍，任豐原.無線傳感器網絡中的自身定位系統和算法[J].軟件學報，2005，16（5）:857-868.

[2]Chan Y T，Ho K C.A simple and efficient estimator for hyperbolic location[J].Signal Processing，IEEE Transactions on，1994，42（8）:1905-1915.

[3]Niculescu D，Nath B.Ad hoc positioning system （APS）[C]// GlobalTele-communications Conference，2001.GLOBECOM'01. IEEE.IEEE，2001（5）:2926-2931.

[4]Nagpal R，Shrobe H，Bachrach J.Organizing a global coordinate system from local information on an ad hoc sensor network [C]//Information Processing in Sensor Networks. Springer Berlin Heidelberg，2003:333-348.

[5]He T，Huang C，Blum B M，et al.Range-free localization schemes for large scale sensor networks[C]//Proceedings of the 9th annual international conference on Mobile computing and networking.ACM，2003:81-95.

[6]王昕，王宗欣，劉石.一種考慮非視線傳播影響的TOA定位算法[J].通信學報，2001，22（3）:1-8.

[7]Meguerdichian S，Slijepcevic S，Karayan V，et al.Localized algorithms in wireless ad-hoc networks:location discovery and sensor exposure[C]//Proceedings of the 2nd ACM international symposium on Mobile ad hoc networking&computing.ACM，2001:106-116.

[8]王日明，馮久超.改進的對數衰減動態非視距定位[J].應用科學學報，2014，32（4）:372-378.

[9]孫大洋.無線傳感器網絡中多邊定位的聚類分析改進算法[J].電子學報，2014，42（8）:1601-1607.

[10]Lewandowski A，Wietfeld C.A comprehensive approach for optimizing toa-localization in harsh industrial environments [C]//Position Location and Navigation Symposium（PLANS），2010 IEEE/ION.2010:516-525.

[11]Niculescu D，Nath B.DV based positioning in ad hoc networks[J].Telecommunication Systems，2003，22（1-4）: 267-280.

[12]王慧鋒，高瞻.認知無線電網絡中基于接收信號強度的定位算法[J].數據采集與處理，2014，29（3）:465-471.

[13]Shang Y，Ruml W，Zhang Y，et al.Localization from mere connectivity[C]//Proceedings of the 4th ACM international symposium on Mobile ad hoc networking&computing. ACM，2003:201-212.

[14]Bisio I，Cerruti M，Lavagetto F，et al.A trainingless WiFi fingerprint positioning approach over mobile devices[J].IEEE Antennas&Wireless Propagation Letters，2014，13（1）: 832-835.

[15]郭建全，趙偉，黃松嶺.農田環境無線傳感器網絡無錨節點定位算法[J].儀器儀表學報，2009，30（8）:1577-1583.

Analysis and development of positioning technology in wireless network

LV Qi-chen1，PANG Li-li2，XIE Jia-ye2
（1.94789 Troop，PLA，Nanjing 210018，China；2.Nanjing Institute of Technology，Nanjing 211167，China）

In the interest of combing through the development of wireless network positioning technology，and analyzing the advantages and problems of the existing positioning algorithms and systems，these positioning algorithms were compared from positioning accuracy，positioning scale，algorithm complexity，algorithm adaptability and feasibility based on the basic principle and evaluation criteria of the positioning technology.Considering the positioning accuracy and the feasibility of the positioning algorithms and systems，the specific classification and optimization of the positioning scheme for different applications are obtained.

wireless network；node-positioning；two-dimensional positioning；positioning error

TN98

A

1674－6236（2016）23-0162-04

2015-11-17稿件編號：201511161

江蘇省高校自然科學研究面上項目（15KJB510014）；南京工程學院高層次引進人才科研啟動基金項目（YKJ201444）

呂奇辰（1981—），男，湖北鐘祥人，碩士，工程師。研究方向：信號處理、無線定位等。