無(wú)線傳感器網(wǎng)絡(luò)基于測(cè)距的節(jié)點(diǎn)定位算法綜述

羅蘭花　梁海英　任子亭

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

【關(guān)鍵詞】無(wú)線傳感器網(wǎng)絡(luò)；節(jié)點(diǎn)定位；三邊測(cè)量法；最大似然估計(jì)法

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

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

1 常見(jiàn)定位方法分類

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

1.1 絕對(duì)定位和相對(duì)定位

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

1.2 粗粒度與細(xì)粒度

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

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

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

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

1.4 基于測(cè)距定位和無(wú)需測(cè)距定位

基于測(cè)距定位方法測(cè)量節(jié)點(diǎn)間的距離、角度、信號(hào)強(qiáng)度和傳輸時(shí)間等信息，然后借助三邊測(cè)量、三角測(cè)量、最小二乘法或最大似然估計(jì)法計(jì)算未知節(jié)點(diǎn)的位置；無(wú)需測(cè)距定位方法則通過(guò)網(wǎng)絡(luò)連通度、節(jié)點(diǎn)間相對(duì)距離計(jì)算未知節(jié)點(diǎn)位置。

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

2 節(jié)點(diǎn)位置計(jì)算方法及其分析

2.1 三邊測(cè)量法

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

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

2.2 三角測(cè)量法

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

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

2.3 最大似然估計(jì)法

最大似然估計(jì)（maximum likelihood estimation， MLE）是通用的數(shù)學(xué)估計(jì)方法，當(dāng)測(cè)試數(shù)據(jù)量大時(shí)具有逼近特性，是三邊測(cè)量法的擴(kuò)展方法。

2.4 最小二乘法

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

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

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

3.1 RSSI定位算法

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

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

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

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

3.2 Hop-terrain迭代算法

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

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

3.3 基于信號(hào)傳輸距離（TOA）定位算法

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

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

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

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

4 總結(jié)

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

【參考文獻(xiàn)】

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

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

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

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

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

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

[責(zé)任編輯：王楠]