羅蘭花　梁海英　任子亭

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

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

【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 引言

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

1 常見定位方法分類

無線傳感器網(wǎng)絡中節(jié)點定位方法根據(jù)不同手段和角度有不同的分類方法，典型的分類有以下幾種。

1.1 絕對定位和相對定位

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

1.2 粗粒度與細粒度

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

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

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

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

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

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

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

2 節(jié)點位置計算方法及其分析

2.1 三邊測量法

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

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

2.2 三角測量法

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

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

2.3 最大似然估計法

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

2.4 最小二乘法

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

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

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

3.1 RSSI定位算法

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

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

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

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

3.2 Hop-terrain迭代算法

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

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

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

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

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

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

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

4 總結(jié)

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

【參考文獻】

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

[2]于寧.無線傳感器網(wǎng)絡定位優(yōu)化方法[D].北京郵電大學，2008.4：15.

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

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

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

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

[責任編輯：王楠]