一種魯棒的RSSI測距定位算法

程炳華,嚴(yán)筱永

(1.金陵科技學(xué)院計算機(jī)工程學(xué)院,江蘇 南京 211169;2.金陵科技學(xué)院智能科學(xué)與控制工程學(xué)院，江蘇 南京 211169)

無線傳感器網(wǎng)絡(luò)(Wireless Sensor Network,WSN)是一門集通信、微電子和傳感器技術(shù)為一體的技術(shù),具有廣泛的應(yīng)用領(lǐng)域,常常被應(yīng)用在軍事、醫(yī)療衛(wèi)生、遠(yuǎn)程監(jiān)控、搶險救災(zāi)等領(lǐng)域[1]。對于大多數(shù)應(yīng)用,知道傳感器節(jié)點的位置至關(guān)重要。有關(guān)研究表明傳感器節(jié)點為用戶所提供監(jiān)測部署區(qū)域上下文相關(guān)信息,與位置信息有關(guān)占80%以上[2]。“低耗自主”[3]一直是WSN的基本特征,因此在全部節(jié)點加裝GPS實現(xiàn)位置估計顯然行不通,此外GPS僅適用于室外無遮擋條件下,因而在實際應(yīng)用中,僅在部分節(jié)點上安裝GPS,對于其他節(jié)點而言,其位置則需通過一定的算法估計出來。

目前,節(jié)點自定位算法常被分為基于測距和無須測距的定位算法兩大類[4]。無須測距的定位算法相對簡單,它利用路由跳數(shù)、網(wǎng)絡(luò)連通性等信息進(jìn)行定位,然而,其精度受網(wǎng)絡(luò)拓?fù)湟约靶艠?biāo)節(jié)點密度等因素影響,因而誤差也普遍較大?；跍y距定位方法精度較高,但其精度受制于節(jié)點間的測量精度。最為常見的測距技術(shù)有RSSI、TOA、TDOA和AOA。RSSI測量數(shù)據(jù)可以在節(jié)點之間的每次數(shù)據(jù)交流中獲取,并且不占有額外的帶寬和能量,硬件花費相對簡單和便宜[5]。這使得使用RSSI測量數(shù)據(jù)進(jìn)行定位成為研究熱點。然而基于RSSI測距的定位算法易受環(huán)境影響,定位精度不高,因此如何規(guī)避環(huán)境影響,提高定位精度是一個比較有意義的問題。

基于測距的定位算法一般分為兩步,即:測距階段和計算坐標(biāo)階段[5]。由于傳感器節(jié)點常常部署在復(fù)雜環(huán)境中,且受到硬件老化、惡意攻擊、電力不足、惡劣環(huán)境等因素的影響,使得在測距階段獲取的信號中含有較多誤差,若不對這些誤差采取有效抑制和處理,有時能產(chǎn)生±50%的測距誤差[6],從而嚴(yán)重影響定位結(jié)果;此外信標(biāo)節(jié)點分布[7]也會在一定程度上影響最終的坐標(biāo)估計,使得計算坐標(biāo)階段估計不穩(wěn)定。通過分析基于RSSI的定位技術(shù)存在的問題,提出一種新的魯棒定位算法(robust location estimation,RLE),算法分別針對定位過程中的兩個階段,最大程度地減少誤差和計算不穩(wěn)定的影響,提高定位精度。

1 主要相關(guān)工作

1.1 測距階段相關(guān)工作

在無線測距中,常用對數(shù)正態(tài)陰影模型作為節(jié)點間的距離測量方法[8]。其公式如下:

(1)

在實際應(yīng)用中,RSSI信號總受到很多不穩(wěn)定因素的干擾,在獲得測距數(shù)據(jù)中不僅包含數(shù)量較多、幅度較小的測距誤差(隨機(jī)噪聲),而且還包含少量幅度較大的測距誤差(奇異點或粗差),在文獻(xiàn)[9]中實驗驗證了RSSI這些干擾的存在。

隨機(jī)噪聲可以通過多次測量獲取的均值來提高數(shù)據(jù)的精確度;而粗差則不能簡單用統(tǒng)計均值的方法來消除其對精度的影響,因而對于最終的位置估計影響也最大。Huber[10]曾用含不同數(shù)量的粗差數(shù)據(jù)進(jìn)行統(tǒng)計分析,當(dāng)1 000個數(shù)據(jù)包含2個粗差時,足以使均值估計方法不可用。鑒于此,有關(guān)研究人員[11]借鑒概率論里的3 Sigma,通過選取高概率發(fā)生區(qū)的RSSI 值,然后再取其幾何均值,這樣處理是假設(shè)RSSI數(shù)值符合正態(tài)分布且假設(shè)粗差出現(xiàn)的比例不高的情況下,而實際環(huán)境下的RSSI數(shù)值并不符合正太分布,且出現(xiàn)的頻率高于3 Sigma所假設(shè)的比例,因此定位估計使用此方法效果并不理想。Li[12]等研究人員利用中位數(shù)與最小二乘相結(jié)合的LMS估計對未知節(jié)點進(jìn)行估計,LMS估計具有較高的魯棒性和容錯能力,這是因為中位數(shù)是拉普拉斯分布的極大似然估計,在理論上LMS可以抵抗含有50%的粗差的干擾。然而實際上包含粗差RSSI信號數(shù)據(jù)并不一定是執(zhí)行錯誤所致,可能是固有的信號數(shù)據(jù)變異的結(jié)果,簡單地剔除它們,有可能會導(dǎo)致重要的隱藏信息丟失,當(dāng)然對待包含粗差的信號數(shù)據(jù)也不應(yīng)當(dāng)與正常數(shù)據(jù)一樣對待,較為合理的做法是根據(jù)它們出現(xiàn)的分布概率,分別賦予相應(yīng)權(quán)值以減少異常數(shù)據(jù)的影響。本文受到中位數(shù)抗噪思想的啟發(fā),結(jié)合實際情況,在測距階段利用一種基于統(tǒng)計中值的加權(quán)測距方法,即在兩節(jié)點之間通信交流一段時間,并獲取一定數(shù)量RSSI數(shù)據(jù)后,在信號序列中,找到RSSI信號強(qiáng)度的中值,再對信號序列中每一信號強(qiáng)度都以此中值為基礎(chǔ)計算其權(quán)值,最后讓各個信號與相應(yīng)權(quán)值相乘再求和,作為兩節(jié)點之間的RSSI信號值并輸出,然后再利用數(shù)正態(tài)陰影模型將其轉(zhuǎn)化為相應(yīng)的距離。

1.2 計算階段相關(guān)工作

從理論上來講,不屬區(qū)域內(nèi)信標(biāo)節(jié)點越多,節(jié)點估計越精確。但事實上信標(biāo)節(jié)點之間的幾何分布以及信標(biāo)節(jié)點與未知節(jié)點之間形成幾何結(jié)構(gòu)會很大程度上影響未知節(jié)點定位結(jié)果。如圖1所示,未知節(jié)點U和信標(biāo)節(jié)點B1、B2、B3的距離已知,由于3個信標(biāo)節(jié)點近似在一條直線上,也就是說3點近似共線,那么未知節(jié)點U的估計位置就可能是U或者U′,此時無法確定U的實際位置。研究顯示用于定位的3個信標(biāo)節(jié)點組成的三角形完全共線時,僅僅簡單地利用最小二乘法將導(dǎo)致最大的位置誤差,可達(dá)200%[13]。

圖1 信標(biāo)節(jié)點近似共線Fig.1 Collinearity of beacon nodes

最小二乘法是一種無偏估計方法,具有局部最優(yōu)的特點。目前,理論和實際工程中克服共線性影響的方法多樣,研究人員提出了多種診斷方法和補(bǔ)救措施,其中最為常用且簡單的方法是嶺回歸方法(Ridge Regression,RR)。嶺回歸由A.E.Hoerl[14]提出,通過引入偏移量k(又稱為嶺參數(shù)),以犧牲估計的無偏性換取估計方差的大幅減小,最終達(dá)到提高估計精度和穩(wěn)定性的目的。對于估計模型ATAx=Ab,在引入嶺參數(shù)k后,得到新的估計模型(ATA+kI)x=ATb。由于嶺參數(shù)的引入使得位置估計不在是無偏的,但卻解決了共線問題,使得估計值方差變小,同時使得估計變得穩(wěn)定。嶺回歸方法簡單易行,在一定程度克服了多重共線對估計值的影響,因而被廣泛應(yīng)用于工程實踐中。嶺回歸方法的關(guān)鍵是如何選取合適的嶺參數(shù),嶺參數(shù)的選擇可以通過交叉檢驗獲得,但其計算量較大,考慮到一般‖ATA‖<0.01為病態(tài)矩陣,因此本文設(shè)定k=0.01。

本文受此啟發(fā),在計算階段引入嶺回歸方法,用它代替原先最小二乘法估計節(jié)點坐標(biāo)方法。改進(jìn)方法通過消除少部分有害信息以達(dá)到多重共線性,提高計算的穩(wěn)定性,達(dá)到提高定位精度的目的。

2 RLE算法過程

針對測距和計算坐標(biāo)階段的不同性質(zhì)的誤差,分別采用一種基于統(tǒng)計中值的加權(quán)測距方法和RR方法改進(jìn)了RSSI測距,進(jìn)而提高了定位的精度。

J.W.Tukey[15]在1960年提出了一種接近實際的分布模型,其被稱為污染分布,可表示為

f=(1-α)fg+αfo

(2)

其中,主體部分分布fg為正態(tài)分布,fo是干擾部分分布;α是污染率,表示污染部分所占比例。主體部分占據(jù)數(shù)據(jù)的主要部分,干擾部分是次要部分。對于正態(tài)分布,利用均值方法即可有效消除其誤差;而對于干擾部分的分布,著名的魯棒估計學(xué)者Huber[10]指出,許多干擾分布模式接近拉普拉斯分布,對于拉普拉斯分布,其極大似然估計是中位數(shù),它是抗差能力最強(qiáng)的一種參數(shù)估計。受此啟發(fā),采用基于中位數(shù)加權(quán)的RLE算法,其具體過程如下。

1) 每個信標(biāo)節(jié)點周期性的通過可控泛洪廣播自身位置,在其有效通信半徑內(nèi)的未知節(jié)點收到該位置信息,在通信一段時間后,相應(yīng)的未知節(jié)點得到相應(yīng)信標(biāo)節(jié)點RSSI信號序列。

2) 在每個RSSI信號序列中找到相應(yīng)的中值Med_RSSI，可定義為:在獲取的某個RSSI信號序列RSSI1,RSSI2…RSSIn中,先按數(shù)值大小排序,則信號序列的中值表示為

(3)

3) 式求信號序列中各個RSSI信號強(qiáng)度值在序列中相對應(yīng)的權(quán)值。假設(shè)每個信號序列中有n個RSSI信號強(qiáng)度值,首先求每個RSSI信號值與中值的方差di;為了防止某些與中值相近的含粗差的信號的影響,在算法中加一閾值Thre,若方差大于閾值,則權(quán)值由方差決定;若方差小于閾值,則由閾值決定。每個序列中各個RSSI 信號的權(quán)值可按下式計算:

(4)

其中Thre可由下式表示:

(5)

其中,RSSIi為序列內(nèi)第i個RSSI信號值?？梢钥闯?RSSIi和Med_RSSI相差越大,相對應(yīng)的加權(quán)系數(shù)越小,而Thre隨著RSSIi和Med_RSSI方差而變化。

5) 式中未知節(jié)點在其通信半徑內(nèi)收到3個以上信標(biāo)節(jié)點信號,則可以構(gòu)造下列公式:

(6)

其中,(x1,y1),(x2,y2),…,(xn,yn)為信標(biāo)節(jié)點坐標(biāo);(x,y)為未知節(jié)點。上述方程組可以轉(zhuǎn)化為Ax=b的形式,其中：

(7)

當(dāng)ATA可逆時,方程可以用最小二乘法求得未知節(jié)點估計坐標(biāo):

(8)

在實際部署時,用于估計位置的信標(biāo)節(jié)點常出現(xiàn)共線或者近似共線現(xiàn)象,這時|ATA|=0或|ATA|≈0,即矩陣出現(xiàn)多重共線性現(xiàn)象,算法運用嶺回歸方法,則未知位置節(jié)點坐標(biāo)

(9)

3 算法性能模擬與性能分析

節(jié)點定位的精度、功耗、適用環(huán)境與規(guī)模、信標(biāo)節(jié)點比例、網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)適應(yīng)性、自適應(yīng)和容錯性等通常是評價定位方法常用的技術(shù)標(biāo)準(zhǔn)[11]。本文所提出的RLE算法主要針對定位過程信標(biāo)節(jié)點位置關(guān)系和噪聲對定位精度的影響,因此定位精度和信標(biāo)節(jié)點比例是分析、評價的重點,因此,文中用方均根誤差(Root Mean Square error,RMS) 這個具體性能參數(shù)指標(biāo)考量算法的精度。RMS定義如文獻(xiàn)[4]中所述。

仿真實驗還需要配置另外一些參數(shù),如:節(jié)點的通信半徑,信標(biāo)節(jié)點比例,粗差比例等。試驗首先通過設(shè)置不同的信標(biāo)節(jié)點比例比較改進(jìn)RSSI算法與不考慮共線問題的RSSI定位算法。仿真實驗假設(shè)節(jié)點分布在120*120區(qū)域,在此區(qū)域中隨機(jī)部署200個節(jié)點,節(jié)點的通信半徑設(shè)置為50,使用公式(1)作為RSSI信號值與距離關(guān)系的公式。同時為了降低隨即部署場景中節(jié)點分布隨機(jī)性對實驗結(jié)果的影響,每種實驗都進(jìn)行了50次仿真,每次試驗里節(jié)點都將重新隨機(jī)分布在實驗區(qū)域,統(tǒng)計每次的實驗結(jié)果,并取均值作為評價依據(jù)。本文從兩組實驗對改進(jìn)的RSSI進(jìn)行考量,首先是假設(shè)信標(biāo)節(jié)點一定,考量RMS隨粗差比例變化,通過實驗可以考察改進(jìn)算法抗躁性是否魯棒;其次是假設(shè)粗差比例一定,考量RMS隨信標(biāo)節(jié)點個數(shù)的增加的變化,信標(biāo)節(jié)點個數(shù)出現(xiàn)越多共線的機(jī)會越大,通過實驗可以考察出改進(jìn)算法是否穩(wěn)定。

實驗1:設(shè)定信標(biāo)節(jié)點從10開始逐漸增加到20,粗差比例為9%。由于噪聲和信標(biāo)節(jié)點拓?fù)滟|(zhì)量等原因使得均值算法的RMS數(shù)值曲線呈上下起伏狀,可以看出其定位效果較差且不穩(wěn)定;利用3sigma方法去除了部分的粗差影響,但是僅去除了部分粗差,且3sigma方法并沒消除共線的影響,因此從圖2(a)看出RMS數(shù)值曲線同樣呈上下起伏狀,有時因為拓?fù)滟|(zhì)量極差3sigma的RMS甚至比均值算法的RMS還高;而RLE算法通過對定位數(shù)據(jù)重新構(gòu)造,將有用信息與噪聲、共線信息重新排隊,通過設(shè)定一定的閾值去除共線信息,使得RLE算法的RMS曲線隨著信標(biāo)節(jié)點增加而減小,且RLE算法的RMS都比相應(yīng)的其他兩種算法RMS低不少,其中RLE算法的平均RMS數(shù)值比3sigma方法低了約8.7%;而比均值方法低了約40.2%。

實驗2:統(tǒng)計學(xué)家長期研究發(fā)現(xiàn)粗差存在的比例為1%～10%[10]。因此設(shè)定粗差設(shè)定為1%～10%,同時設(shè)定信標(biāo)節(jié)點數(shù)為16。從圖2(b)中看出均值算法和3sigma方法隨粗差比例增長其兩者RMS曲線急劇增大,且當(dāng)有信標(biāo)節(jié)點共線時3sigma的RMS數(shù)值可能大于均值算法,可以看出這兩種算法對粗差很敏感且算法很不穩(wěn)定;而RLE算法的RMS值相對較為低,RMS曲線緩慢增長,可以看出RLE算法對粗差不敏感且算法較為穩(wěn)定。從圖3可以看出,RLE算法的平均RMS數(shù)值比3 sigma方法低了約4.7%;而比均值方法低了約33.7%。

(a)隨信標(biāo)點數(shù)量變化的方均根誤差

(b) 隨粗差比例變化的方均根誤差

4 結(jié) 論

文中針對RSSI定位算法的定位精度受到多種測距誤差和信標(biāo)節(jié)點拓?fù)溆绊戇@一現(xiàn)象,在其定位過程中首先利用統(tǒng)計中值的加權(quán)測距方法消除部署環(huán)境中測距信號誤差的影響,而后在此基礎(chǔ)上用基于嶺回歸回歸方法消除共線所造成影響。RLE算法從實驗結(jié)果來看較原先的估計方法更穩(wěn)定,精度更高。同時也可以看出,本文所提的算法思想不僅僅在基于RSSI測距的位置估計算法中可以適用,也可以在其他的測距定位的算法中使用,作為其提高精度和穩(wěn)定性的優(yōu)化策略。

[1] Zheng J,Jamalipour A.Wireless Sensor Networks:A Networking Perspective[M].Hoboken:A John & Sons,Inc,2009

[2] 周艷.智能空間中定位參考點的優(yōu)化選擇及誤差分析[D].沈陽:東北大學(xué),2009

[3] 倪明選,李明祿,薛廣濤.無線傳感器的基礎(chǔ)理論及關(guān)鍵技術(shù)研究[C].北京：清華大學(xué)出版社,2008,384-413

[4] 竇如林,閻浩,嚴(yán)筱永.基于偏最小二乘的無線傳感網(wǎng)絡(luò)多跳定位算法[J].金陵科技學(xué)院學(xué)報,2014,30(3):19-25

[5] Mao G,Fidan B.Localization Algorithms and Strategies for Wireless Sensor Networks:Monitoring and Surveillance Techniques for Target Tracking[M].New York:Information Science Reference,2009

[6] Liu Y,Yang Z.Location,Localization,and Localizability Location-awareness Technology for Wireless Networks[M].New York:Springer,2011

[7] 嚴(yán)筱永,錢煥延,高德民,等.一種基于多重共線性的三維DV-Hop定位算法[J].計算機(jī)科學(xué),2011,38(5):37-40

[8] 孫佩剛,海趙,羅玎玎,等.智能空間中 RSSI 定位問題研究[J].電子學(xué)報,2007,35(7):1240-1245

[9] 趙方,馬嚴(yán),羅海勇,等.基于頑健估計的室內(nèi)節(jié)點定位算法[J].通信學(xué)報,2008,29(11):113-120

[10] Huber P J,Ronchetti E M.Robust Statistics[M].2nd ed.New York:Wiley,2009

[11] Zhang C,Zhou X,Gao C,et al.On Improving the Precision of Localization with Gross Error Removal[C].28th International Conference on Distributed Computing Systems Workshops,2008:144-149

[12] Li X,Hua B,Shang Y,et al.A Robust Localization Algorithm in Wireless Sensor Networks[J].Frontiers of Computer Science in China,2008,2(4):438-450

[13] Tian S,Zhang X,Wang X,et al.A Selective Anchor Node Localization Algorithm for Wireless Sensor Networks[C].ICCIT Proceedings of the 2007 International Conference on Convergence Information Technology,2007:358-362

[14] Ae H.Application of Ridge Analysis to Regression Problems[J].Chemical Engineering Progress,1962,58:54-59

[15] J W Tukey.A Survey of Sampling from Contaiminated Distributions[M].California:Stanford University Press,1960