基于稀疏傅里葉變換和RSSI測距的低復雜度RSSI定位算法

王宇鵬，代 玉,王樂寧

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

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

1 基于RSSI定位算法原理

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

1.1 RSSI測距方法

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

(1)

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

RSSI=Pt-PL(d)

(2)

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

(3)

1.2 最小二乘定位方法

(4)

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

(5)

待測節(jié)點的坐標同N個錨節(jié)點之間的坐標關系計算公式如式(6)所示。

(6)

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

QX=B

(7)

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

(8)

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

min‖QX-B‖2

(9)

則待測節(jié)點的最優(yōu)坐標(x′,y′)為：

X=(QTQ)-1QTB

(10)

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

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

圖1 稀疏傅里葉變換結構示意圖

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

(11)

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

(12)

對濾波結果降采樣為：

(13)

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

圖2 算法流程圖

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

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

(14)

本文所提出的定位算法的復雜度為：

(15)

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

(16)

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

3 性能驗證

3.1 仿真參數(shù)設置

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

(17)

3.2 仿真結果分析

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

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

圖5 文中算法的定位結果圖

圖6 3個隨機錨節(jié)點的定位結果圖

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

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

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

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

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

4 結論

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