無線傳感器網絡基于測距的節點定位算法綜述

羅蘭花　梁海英　任子亭

【摘 要】基于測距的定位方法對測量的距離信息運用幾何知識求解未知節點的位置，常用在定位精度較高的領域，可在誤差、能耗、受環境因素影響等方面進行優化。本文對基于測距的無線傳感器網絡節點定位算法進行詳細地分析和比較。

【關鍵詞】無線傳感器網絡；節點定位；三邊測量法；最大似然估計法

【Abstract】The node localization based on distance always using geometric knowledge to solve the unknown nodes position. Its used in the field of high positioning accuracy， and it can bring optimization in error， energy consumption， and influenced by environmental factors. The paper detailed analysis and comparison of the node localization algorithm based on ranging of wireless sensor networks.

【Key words】Wireless sensor network； Node localization； Three sided measurement； Maximum likelihood estimate

0 引言

近十年來，無線傳感器網絡得到了前所未有的發展，在眾多領域中得到了廣泛的實際應用，被認為是影響人類發展的十大技術之一。盡管節點定位在定位精度、定位時間、能量開銷等方面有了很大改進，但仍然是制約和影響無線傳感器網絡應用的關鍵技術之一。

1 常見定位方法分類

無線傳感器網絡中節點定位方法根據不同手段和角度有不同的分類方法，典型的分類有以下幾種。

1.1 絕對定位和相對定位

絕對定位為網絡命名空間提供一個唯一的地址，定位結果為坐標位置，如經緯度等。此類定位方法對網絡變動時適應性較好；相對定位則以網絡中某些節點作為參考節點，為其他節點建立坐標，相對定位不提供唯一的地址，無需信標節點，網絡變動時適應性差。

1.2 粗粒度與細粒度

根據信號強度、角度或時間等信息計算未知節點的位置稱為細粒度定位，如Radio Camera定位系統中的信號模式匹配技術（signal pattern matching）[1]；根據逐漸接近信標節點的信息來度量未知節點的方法稱為粗粒度定位，如質心、衰減模型、凸規劃、Active Badge和ParcTAB均屬于粗粒度定位。

1.3 集中式定位和分布式定位

集中式定位先將所需的信息傳遞到中心節點然后進行計算，該方法側重于對定位信息的集中處理，可以獲得相對精確的定位，缺點[1]是中心節點能耗大，容易造成個別節點過快耗盡能量，從而影響其他節點定位。

分布式定位則依賴于節點間的信息交換和協調，獲得足夠信息后節點自行定位計算。分布式定位通過節點間合作減少了整體定位時間，且能耗比較均衡，但會放大和累積定位過程的誤差，從而影響定位精度。

1.4 基于測距定位和無需測距定位

基于測距定位方法測量節點間的距離、角度、信號強度和傳輸時間等信息，然后借助三邊測量、三角測量、最小二乘法或最大似然估計法計算未知節點的位置；無需測距定位方法則通過網絡連通度、節點間相對距離計算未知節點位置。

基于測距定位方法能實現較精確的定位，但對節點硬件要求高、功耗大和易受環境因素的影響，常用于精度要求較高的專業領域，如國防軍事、國家安全等。無需測距的定位方法具有硬件要求低、成本低、能耗小等優點，但存在誤差較大、定位精度較低等問題，常用在精度要求相對較低的領域，如環境監測等。

2 節點位置計算方法及其分析

2.1 三邊測量法

三邊測量法利用三個已知信標節點的坐標和未知節點的距離推導出未知節點的坐標。假設已知A、B、C三個節點，坐標分別為（xa，ya），（xb，yb），（xc，yc），A、B、C到未知節點D的距離為別為d1、d2、d3，未知節點可用幾何圖形表示為以已知節點為圓心，節點距離為半徑三個圓的交點，如下圖1所示。

三邊測量法的缺點是節點距離誤差較大時，可能出現三個圓無法交于一點，方程無解即定位失敗。

2.2 三角測量法

三角測量法根據三個信標節點與未知節點的角度和三個節點的坐標信息計算節點間的距離，然后計算出未知節點坐標。該方法也是一種基于幾何運算的定位方法。

三邊測量法和三角測量法屬于形式化數學方法，并不能很好地直接應用在無線傳感器網絡中。因此，國內外研究人員對這兩種方法進行了優化和適應性修改，以適用無線傳感器網絡。

2.3 最大似然估計法

最大似然估計（maximum likelihood estimation， MLE）是通用的數學估計方法，當測試數據量大時具有逼近特性，是三邊測量法的擴展方法。

2.4 最小二乘法

最大似然估計求解時利用方程相減的方法消去二次項，這會損失已知坐標信息。如上述實數方程組（1）不存在任何一組值（x，y）使其滿足方程組，那么可以通過找到一組值（x'，y'）使得方程組兩邊的值最接近，即求近似解。另外考慮到誤差，誤差的平方稱為二乘方，誤差最小就是最小二乘法。實際使用中常將最小二乘法常和最大似然法結合起來求解。

上述方法是節點計算的基本方法，隨著研究不斷深入和應用領域的不斷擴展，涌現了很多改進方法，同時三維節點位和智能定位等新的定位技術的出現，使得節點計算方法得到了很大的優化。

3 基于測距的節點定位算法分析及比較

3.1 RSSI定位算法

RSSI定位算法基本思想通過接收到的射頻信號（Radio Frequency，RF）強弱，根據傳播衰減模型計算已知節點到未知節點的距離。RSSI算法優點是實現簡單、硬件要求低和能耗低；缺點是易受實際環境的影響，導致平均定位誤差較大。目前很多研究人員對該算法進行了改進并獲得了較好的仿真和實際使用效果。

丁恩杰等[3]提出的基于RSSI和加權質心結合定位算法，該算法先通過RSSI測距得到4個信標節點到未知節點的距離，再任選其中3個距離為半徑，以信標節點為圓心畫圓得到3個圓的交疊區域，構成一個三角形，求出這個三角形的質心。按照該方法求出4個質心坐標，利用加權質心定位算法求出未知節點的坐標。仿真結果表明定位精度有很大的提高。

秦念慶[4]針對傳統的基于RSSI定位算法存在不適定問題，提出基于Tikhonov正則化方法的多邊定位算法，通過分析和大量實驗最終確定最優信道衰減指數n為4，最優參考點數為5，通過實驗發現基于Tikhonov正則化方法比最大似然估計法減少了定位誤差，部分實驗結果如表1所示。

該算法未增加硬件開銷，但降低了距離誤差和定位誤差，算法性能優于傳統的基于RSSI的最大似然估計法節點定位。

3.2 Hop-terrain迭代算法

Hop-terrain迭代算法是基于測距和無需測距相結合的定位方法。該算法分兩步進行，第一步先用距離無關定位方法估算各節點的初始位置，然后用基于測距的定位方法對節點位置迭代計算以減小定位誤差。實驗表明，Hop-terrain算法能較好地改善稀疏信標節點問題和測量誤差對節點定位的影響[5]，當網絡連通度較低時，收斂性變差。

張松濤[5]提出的一個改進的基于距離約束迭代定位算法DCR（Distance Control Refinement），主要針對Hop-terrain算法在網絡連通度比較低時，迭代過程收斂性下降，成功定位節點比例很低等問題。DCR算法定位過程中刷選上次迭代結果作為最新迭代結果。該算法也分為兩步，第一步是節點坐標估算；第二步刷選節點位置進行迭代更新。仿真結果表明在連通度低的網絡中，DCR算法節點定位成功率比Hop-terrain算法提高了20-30%，精度較高節點比例比Hop-terrain算法平均提高了6.5%[5]。

3.3 基于信號傳輸距離（TOA）定位算法

TOA（Time of Arrival）定位算法根據信號傳播時間和速率計算信標節點到未知節點的距離。該算法分為三步。第一步測距。測量未知節點到信標節點的距離或方位，至少包含三個以上信標節點的距離信息；第二步定位。通過極大似然估計等方法計算；第三步修正。進一步矯正節點坐標，以保證精度。TOA算法測量精度較高，但要求節點之間嚴格的時間同步，因此對硬件需求高，成本和能耗高，應用在對精度要求高的專業領域。

劉鵬[6]提出的改進的TOA定位算法，信標節點同時發送兩種不同速率的無線信號，未知節點根據接收的信號時間差計算出節點間的距離。該方法解決了時間嚴格同步和硬件延遲問題，仿真實驗表明改進的TOA算法能獲得更好的定位精度。

綜合上述幾類算法，從算法實現的難易程度、硬件需求、能耗、誤差和需已知節點比例等方面進行比較，結果如表2所示。

除了上述基于距離的節點定位算法外，還有基于信號傳輸時間差（TDOA）的基本定位方法及其改進算法、基于信號到達角度（AOA）的基本定位方法及其改進算法等。總的來說，基于RSSI的定位算法具有實現簡單、低成本等特點，眾多研究人員對算法進行改進使其誤差不斷降低而更受歡迎。

4 總結

基于測距的定位方法是目前無線傳感器網絡使用最廣泛的定位技術，它能獲得較高定位精度而備受關注。本文首先對定位方法分類進行了綜述，然后分析了經典的節點位置計算方法的特點，最后對無線傳感器網絡中幾種具有代表性的基于測距的節點定位算法進行了詳細分析和比較。

【參考文獻】

[1]汪煬.無線傳感器網絡定位技術研究[D].中國科學技術大學，2007.4：19-21.

[2]于寧.無線傳感器網絡定位優化方法[D].北京郵電大學，2008.4：15.

[3]丁恩杰，喬欣，常飛，喬莉.基于RSSI的WSNs加權質心定位算法的改進[J].傳感器與微系統，2013.7：53-56.

[4]秦念慶.基于RSSI的無線傳感器網絡多邊定位算法研究[D].山東大學論文，2009.4：35-36.

[5]張松濤.無線傳感器網絡定位問題研究[D].華中科技大學，2010.5.

[6]劉鵬，宋迪，牛斗.WSN中一種改進的丁OA空間定位算法研究[J].微計算機信息，2009（25）：283-284.

[責任編輯：王楠]