王宇鵬，代 玉,王樂寧

(1.沈陽航空航天大學(xué) 電子信息工程學(xué)院，沈陽 110136；2.中國民用航空飛行校驗(yàn)中心 校驗(yàn)部,北京 100000)

無線定位通過直接或者間接測量接收到的無線電信號的到達(dá)時間、頻率、到達(dá)角度等參數(shù)的變化，確定參考點(diǎn)與目標(biāo)間的一些位置信息(如距離、方位等)，進(jìn)而得到目標(biāo)的位置信息(如坐標(biāo)、經(jīng)緯度等)。無線定位技術(shù)近年來發(fā)展十分迅速，在現(xiàn)實(shí)網(wǎng)絡(luò)中已有諸多應(yīng)用，例如航空干擾檢測系統(tǒng)，倉庫物品管理、游戲開發(fā)等。針對WSN(Wireless Sensor Network)的定位算法有很多，在現(xiàn)如今的定位算法研究中，根據(jù)是否需要測距可以將定位算法分為基于測距算法和基于非測距算法?；跍y距算法是測量各通信節(jié)點(diǎn)之間的角度或距離等進(jìn)行定位，比如基于AOA 的定位算法通過計(jì)算待測節(jié)點(diǎn)與錨節(jié)點(diǎn)所形成的夾角進(jìn)行測量[1-3]；基于TOA的定位算法通過信號的傳輸時間來推算出節(jié)點(diǎn)間的距離[4-9]；基于RSSI的定位算法通過測量接收到的信號強(qiáng)度計(jì)算信號在傳輸過程中的能量損耗，推算出兩個節(jié)點(diǎn)間的距離[10-11]。基于非測距的定位算法通過錨節(jié)點(diǎn)間的傳遞信息進(jìn)行定位，比如三邊測量法選取待測節(jié)點(diǎn)周邊鄰近的三個錨節(jié)點(diǎn)分別以其到待測節(jié)點(diǎn)之間的距離為半徑，各錨節(jié)點(diǎn)坐標(biāo)為圓心作圓，則三個圓相交的點(diǎn)即視為待測節(jié)點(diǎn)坐標(biāo)的估計(jì)位置[12]；質(zhì)心定位算法通過錨節(jié)點(diǎn)不斷地向周邊節(jié)點(diǎn)發(fā)送自己的坐標(biāo)位置，待測節(jié)點(diǎn)接收到相應(yīng)的信息并存儲，當(dāng)存儲的錨節(jié)點(diǎn)數(shù)超過一定的閾值時連接這些錨節(jié)點(diǎn)形成多邊形，其質(zhì)心視為待測節(jié)點(diǎn)的估計(jì)坐標(biāo)[13-15]；基于APIT的定位算法是錨節(jié)點(diǎn)定時廣播自己位置坐標(biāo)，待測節(jié)點(diǎn)通過與周邊錨節(jié)點(diǎn)交換位置信息來確定這些錨節(jié)點(diǎn)是否會形成包含自己的三角形，從而確定待測節(jié)點(diǎn)的位置[16-18]。但是現(xiàn)如今的定位算法，都通過增加錨節(jié)點(diǎn)的個數(shù)來提高定位精度，并未考慮錨節(jié)點(diǎn)所攜帶信息的有效性，因此算法復(fù)雜度很高，為了解決這一問題，本文提出一種將稀疏傅里葉算法與RSSI測距相結(jié)合的定位算法來降低算法復(fù)雜度，同時保證了定位精度。

1 基于RSSI定位算法原理

RSSI即接收信號強(qiáng)度指示，用于指示接收信號強(qiáng)度的大小，主要通過測量接收無線信號的振幅大小獲得。RSSI主要用于信號質(zhì)量評估、信道測量、定位等應(yīng)用。

1.1 RSSI測距方法

在使用RSSI測距時，主要通過計(jì)算額定發(fā)射功率與RSSI之間的強(qiáng)度差值計(jì)算傳輸損耗，之后利用路徑損耗模型將路徑損耗轉(zhuǎn)化為相應(yīng)的傳輸距離。本文采用對數(shù)-正態(tài)分布模型進(jìn)行距離的測量，如下所示：

(1)

其中，PL(d)為無線信號傳輸距離為d的路徑能量損耗；PL(d0)是在參考距離為d0處的能量損耗；η代表受環(huán)境因素影響的路徑損耗參數(shù)，其相應(yīng)的經(jīng)驗(yàn)值一般會根據(jù)應(yīng)用場景選??；X表示服從均值為零的隨機(jī)變量；d0為參考距離，通常設(shè)為1 m；d為待測節(jié)點(diǎn)與錨節(jié)點(diǎn)之間的距離，則傳感器節(jié)點(diǎn)接收到的RSSI值滿足

RSSI=Pt-PL(d)

(2)

式中，RSSI為接收到的信號強(qiáng)度，Pt為信號發(fā)送功率，PL(d)是路徑損耗。根據(jù)(2)中所得到參與定位的各錨節(jié)點(diǎn)RSSI值后，可按公式(3)轉(zhuǎn)換為其相應(yīng)的距離。

(3)

1.2 最小二乘定位方法

(4)

其中，ei是測量誤差值，(x′,y′)是估算出的待測節(jié)點(diǎn)坐標(biāo)，可改寫公式(4)為：

(5)

待測節(jié)點(diǎn)的坐標(biāo)同N個錨節(jié)點(diǎn)之間的坐標(biāo)關(guān)系計(jì)算公式如式(6)所示。

(6)

公式(6)還可以轉(zhuǎn)換為如公式(7)所示的矩陣形式：

QX=B

(7)

其中，Q是(N-1)*2維矩陣，X為坐標(biāo)向量，B為(N-1)維向量。分別表示為：

(8)

公式(8)可以轉(zhuǎn)化線性最小二乘問題：

min‖QX-B‖2

(9)

則待測節(jié)點(diǎn)的最優(yōu)坐標(biāo)(x′,y′)為：

X=(QTQ)-1QTB

(10)

2 基于稀疏傅里葉和RSSI測距的低復(fù)雜度定位算法

對于無線電信號，信號在傳播過程中發(fā)生反射、衍射等現(xiàn)象，導(dǎo)致錨節(jié)點(diǎn)接收到的信號強(qiáng)度可能是多路信號的疊加，從而使得測量精度降低，同時錨節(jié)點(diǎn)的選擇對于測量精度也有一定影響。為解決上述問題，通常通過增加錨節(jié)點(diǎn)個數(shù)來提高定位信息的冗余度提高測量精度，如多邊測量等方法。但是參與錨節(jié)點(diǎn)個數(shù)的增加將顯著提高定位算法的復(fù)雜度及定位算法的計(jì)算時間，從而降低算法的有效性。稀疏傅里葉變換主要是對信號進(jìn)行降維處理，可以充分利用信號的稀疏特性來簡化傳統(tǒng)的時頻處理方法。當(dāng)接收到信號后，可以將該信號經(jīng)過重排、濾波和降采樣后確定大值點(diǎn)的頻率，精確估計(jì)大值點(diǎn)頻點(diǎn)對應(yīng)的傅里葉系數(shù)，將所確定的大值點(diǎn)從原信號中去除，并循環(huán)迭代之前的步驟。利用這種思想，本文通過引入稀疏傅里葉變換的方式對參與定位的錨節(jié)點(diǎn)質(zhì)量進(jìn)行預(yù)選，以降低算法的復(fù)雜度，同時保證定位精度，其基本結(jié)構(gòu)如圖1所示[19-20]。

圖1 稀疏傅里葉變換結(jié)構(gòu)示意圖

圖中RSSI(N)為區(qū)域內(nèi)錨節(jié)點(diǎn)接收到的RSSI值集合，將其表示為：

(11)

N為錨節(jié)點(diǎn)總數(shù)，RSSIi為第i個錨節(jié)點(diǎn)的RSSI值，數(shù)組重排即指將所得到的RSSI值進(jìn)行從大到小排序。通過濾波器g(n)濾除無用的RSSI值，如式(12)所示。

(12)

對濾波結(jié)果降采樣為：

(13)

其中Ns為采樣出錨節(jié)點(diǎn)個數(shù)。通過對錨節(jié)點(diǎn)的RSSI值進(jìn)行稀疏傅里葉變換，采樣出指定個數(shù)的最優(yōu)RSSI值，然后代入到第二部分所提到的RSSI測距及最小二乘定位方法中，最終得出待測節(jié)點(diǎn)位置。本文所提出算法的具體實(shí)現(xiàn)流程如圖2所示。首先設(shè)置錨節(jié)點(diǎn)坐標(biāo)用于接收無線電信號，并記錄下各錨節(jié)點(diǎn)接收到的信號強(qiáng)度RSSI值，設(shè)定一個閾值旨在接收指定數(shù)量的RSSI值，然后采用稀疏傅里葉變換采樣出質(zhì)量較好的RSSI值，最后采用最小二乘法對待測節(jié)點(diǎn)進(jìn)行坐標(biāo)估計(jì)，將測得的坐標(biāo)值與真實(shí)坐標(biāo)值進(jìn)行比較，得出測量誤差。

圖2 算法流程圖

算法的復(fù)雜程度主要由空間復(fù)雜度和時間復(fù)雜度進(jìn)行衡量，本文所提出的算法主要在時間復(fù)雜度上對定位過程進(jìn)行優(yōu)化。在保證定位精度的同時，通過減少算法運(yùn)行時間來降低復(fù)雜度。傳統(tǒng)使用全部錨節(jié)點(diǎn)定位算法的復(fù)雜度為：

C傳統(tǒng)=O(Nlog2N)

(14)

本文所提出的定位算法的復(fù)雜度為：

(15)

其中k為稀疏度。兩者復(fù)雜度相除并求極限，當(dāng)n趨于無窮大時有：

(16)

由式(16)可知，本文所提出的定位算法復(fù)雜度要低于傳統(tǒng)算法復(fù)雜度。

3 性能驗(yàn)證

3.1 仿真參數(shù)設(shè)置

為驗(yàn)證本文中所提出算法的性能，本文建立了如圖3所示的計(jì)算機(jī)模擬仿真環(huán)境，假設(shè)待測節(jié)點(diǎn)與錨節(jié)點(diǎn)隨機(jī)分布在一個80 m×80 m的正方形區(qū)域內(nèi)，其中錨節(jié)點(diǎn)用‘*’表示，待測節(jié)點(diǎn)用‘’表示。其中部署的錨節(jié)點(diǎn)用于接收信號得到RSSI值。仿真平臺的具體參數(shù)配置如表1所示。定位誤差δ可由式(17)計(jì)算。

(17)

3.2 仿真結(jié)果分析

圖4～6展示了待測節(jié)點(diǎn)在(x=40，y=45)位置時錨節(jié)點(diǎn)篩選及定位結(jié)果。圖5展示了使用本文中算法的定位結(jié)果，從結(jié)果我們可以看出，待測節(jié)點(diǎn)位置在x軸向上偏差0.101 9 m，y軸向上偏差0.106 3 m，平均偏差0.104 1 m，對應(yīng)的距離偏差0.147 2 m。在圖5所示使用隨機(jī)錨節(jié)點(diǎn)篩選方法得到的結(jié)果中，可以看到待測節(jié)點(diǎn)在x軸向上偏差0.089 4 m，在y軸向上偏差0.618 8 m，平均偏差0.354 1 m，距離偏差0.625 2 m。對比兩種方法的定位結(jié)果，發(fā)現(xiàn)針對這一待測節(jié)點(diǎn)位置，本文中所提出算法相對于隨機(jī)錨節(jié)點(diǎn)篩選方法在坐標(biāo)偏差上降低86.25%，在距離偏差上減少87.4%。

圖4 挑選3個錨節(jié)點(diǎn)的節(jié)點(diǎn)分布示意圖

圖5 文中算法的定位結(jié)果圖

圖6 3個隨機(jī)錨節(jié)點(diǎn)的定位結(jié)果圖

表2展示了當(dāng)待測節(jié)點(diǎn)在待測區(qū)域內(nèi)隨機(jī)選擇待測位置時，三種不同定位方法的定位結(jié)果分析。從仿真結(jié)果可以看出，使用全部錨節(jié)點(diǎn)的多邊定位方法因?yàn)榭墒褂玫奈恢眯畔⑤^多，因此定位精度最好。同時由于使用過多的參考錨節(jié)點(diǎn)，計(jì)算復(fù)雜度也最高，計(jì)算時間最長。使用隨機(jī)篩選錨節(jié)點(diǎn)的定位方法減少了使用的錨節(jié)點(diǎn)個數(shù)，但由于篩選過程具有隨機(jī)性，挑選到無用錨節(jié)點(diǎn)的概率很大，還需要重新篩選出性能好的錨節(jié)點(diǎn)進(jìn)行定位，導(dǎo)致計(jì)算時間較長，定位精度差。而本文所提出的定位算法，在減少錨節(jié)點(diǎn)參與定位的同時快速篩選出合適的錨節(jié)點(diǎn)，大大縮短了計(jì)算時間，且定位精度相較于隨機(jī)篩選錨節(jié)點(diǎn)的定位方法提高74.5%，相對于全部錨節(jié)點(diǎn)的多邊定位方法下降僅42.2%。為了更好地展示本文所提出算法的復(fù)雜度情況，圖7展示了在定位錨節(jié)點(diǎn)個數(shù)不同的情況下，使用三種不同定位方法進(jìn)行定位的計(jì)算時間分析。從結(jié)果中可以看出，使用本文提出的定位算法所用時間最少，而且不會隨著錨節(jié)點(diǎn)個數(shù)的增加而大幅度增加計(jì)算時間，由此可以看出，使用本文所提出的算法可以有效降低算法的復(fù)雜度。

圖7 不同定位方法對隨機(jī)待測節(jié)點(diǎn)位置的定位結(jié)果計(jì)算時間比較

表2 隨機(jī)待測節(jié)點(diǎn)位置的定位結(jié)果分析

圖8所示為當(dāng)待測節(jié)點(diǎn)在待測區(qū)域內(nèi)隨機(jī)選擇待測位置時，在定位錨節(jié)點(diǎn)個數(shù)不同的情況下，使用三種不同定位方法進(jìn)行定位的誤差結(jié)果分析。從結(jié)果中我們可以看出，采用隨機(jī)篩選錨節(jié)點(diǎn)定位方法及本文方法時，隨著錨節(jié)點(diǎn)數(shù)量的增多，定位誤差逐漸下降，且隨機(jī)篩選方法定位誤差遠(yuǎn)大于本文中提出的方法；而使用本文所提出的定位方法隨著錨節(jié)點(diǎn)數(shù)量的增加，定位精度逐漸趨近于使用全部錨節(jié)點(diǎn)定位方法。由此可見，本文所提出的算法，在降低算法復(fù)雜度的同時，保證了定位精度。

圖8 不同定位方法對隨機(jī)待測節(jié)點(diǎn)位置的定位結(jié)果誤差比較

4 結(jié)論

為了獲得更高的定位精度，傳統(tǒng)的RSSI定位算法需要所有的錨節(jié)點(diǎn)參與到定位過程中，導(dǎo)致計(jì)算復(fù)雜度較大。本文采用稀疏傅里葉方法，篩選出部分性能較好的錨節(jié)點(diǎn)進(jìn)行定位計(jì)算，大大減少了錨節(jié)點(diǎn)的參與個數(shù)，從而降低了算法的復(fù)雜度。實(shí)驗(yàn)結(jié)果表明，本文所提出的定位算法，相較于傳統(tǒng)定位算法，誤差增益為42.2%，計(jì)算時間增益為68.2%；相較于隨機(jī)篩選錨節(jié)點(diǎn)的定位方法，誤差增益為74.5%，計(jì)算時間增益為41.9%。因此，本文所提出的算法在保證定位精度的同時又有效降低了算法的復(fù)雜度。