WSNS中基于箱線圖的誤差自校正定位算法*

金仁成,李應(yīng)琛,馬遠(yuǎn),趙繼鵬

(大連理工大學(xué) 遼寧省微納米技術(shù)及系統(tǒng)工程重點(diǎn)實(shí)驗(yàn)室，大連 116024)

WSNS中基于箱線圖的誤差自校正定位算法*

金仁成,李應(yīng)琛,馬遠(yuǎn),趙繼鵬

(大連理工大學(xué) 遼寧省微納米技術(shù)及系統(tǒng)工程重點(diǎn)實(shí)驗(yàn)室，大連 116024)

針對基于接收信號強(qiáng)度指示(RSSI)的無線傳感器網(wǎng)絡(luò)(WSNs)節(jié)點(diǎn)定位技術(shù)易受環(huán)境影響、算法運(yùn)算量大等問題，提出一種基于箱線圖的誤差自校正定位算法。該算法采用箱線圖法處理測距過程中的異常RSSI值，利用自校正最小二乘法消除測距誤差進(jìn)而實(shí)現(xiàn)節(jié)點(diǎn)定位。仿真和實(shí)驗(yàn)結(jié)果表明，該算法可以有效抑制異常RSSI值，顯著提高節(jié)點(diǎn)定位的準(zhǔn)確性和穩(wěn)定性，而且無需建立復(fù)雜的數(shù)據(jù)傳播模型或構(gòu)造RSSI位置指紋分布圖。

無線傳感器網(wǎng)絡(luò)；箱線圖；誤差自校正；定位算法

引 言

現(xiàn)有無線傳感器網(wǎng)路定位算法主要分為兩大類[4]：基于測距的定位算法和無需測距的定位算法。無需測距的定位算法依靠網(wǎng)絡(luò)的連通度、路由表及通信半徑等信息實(shí)現(xiàn)未知節(jié)點(diǎn)的定位，具有節(jié)點(diǎn)硬件要求低、網(wǎng)絡(luò)能耗開銷小的優(yōu)勢，但定位誤差高于基于測距的定位算法?；跍y距的定位算法主要包括兩個階段：測距階段和定位階段。測距階段通常采用的測距技術(shù)包括：到達(dá)時間(TOA)、到達(dá)時間差(TDOA)、接收信號強(qiáng)度指示(RSSI)、到達(dá)角度(AOA)。

國內(nèi)外研究者做了大量的研究工作。在測距階段，參考文獻(xiàn)[7]將測距誤差進(jìn)行了詳細(xì)分類，并用狄克遜檢驗(yàn)法去除異常RSSI值。參考文獻(xiàn)[8]將Hampel 濾波器與核密度(HF&KDE)估計相結(jié)合，利用置信指數(shù)來檢測測距誤差，但是該方法計算復(fù)雜，不適用于能耗受限的無線傳感器網(wǎng)絡(luò)。參考文獻(xiàn)[9]利用高斯雙峰的空間關(guān)聯(lián)度，有效地降低了障礙物對信號強(qiáng)度的影響，實(shí)現(xiàn)了復(fù)雜非視距環(huán)境下RSS定位。但在實(shí)際環(huán)境中，信號傳播模型實(shí)時變化，難以準(zhǔn)確評估。在定位階段，參考文獻(xiàn)[10]提出一種加權(quán)最小二乘估計算法(WLSE)，利用距離信息作為權(quán)重參考，但該算法沒有考慮測距誤差對定位階段的影響。參考文獻(xiàn)[11]也提出一種加權(quán)最小二乘定位算法，結(jié)合測距誤差和定位誤差作為加權(quán)權(quán)重，但該算法計算復(fù)雜度較大，環(huán)境適應(yīng)能力較差，不利于應(yīng)用于處理能力受限的無線傳感器網(wǎng)絡(luò)。

針對現(xiàn)有定位算法中計算復(fù)雜、能量損耗大、定位精度低等問題，本文提出一種基于箱線圖的誤差自校正定位算法，有效地降低了外界環(huán)境對測距精度的影響，提高了定位的精度且無需額外的通信開銷。

1 基于RSSI的測距階段

1.1 基于RSSI的測距模型

基于RSSI的測距方法是無線接收機(jī)通過測量接收的信號功率來確定與無線發(fā)射機(jī)之間的距離。其中無線信號的傳播模型通?？梢苑譃槔碚摲治瞿Ｐ?、經(jīng)驗(yàn)?zāi)Ｐ秃突旌夏Ｐ蚚13]。理想傳播環(huán)境下的自由空間模型(Friis)可以作為一種理論分析模型，如式(1)所示:

(1)

其中：PT為發(fā)射功率，PR(d)為接收功率，單位通常為W或者mW;GT為發(fā)射機(jī)的天線增益;GR為接收機(jī)天線增益;λ為發(fā)射信號的波長,單位為m;d為發(fā)射端與接收端之間的距離,單位為m;L為系統(tǒng)損耗因子。Friis模型主要用于估算接收端與發(fā)射端在無阻擋環(huán)境下視距路徑所接收的功率。在實(shí)際的環(huán)境中，傳播模型可能受到多徑反射、衍射、障礙物等因素的影響，導(dǎo)致測量精度發(fā)生很大變化。無論室內(nèi)還是室外信道，基于理論和測試的傳播模型平均接收信號功率隨距離變化而呈對數(shù)衰減。因此，本文采用對數(shù)路徑損耗模型，如式(2)所示:

(2)

其中：PR(d)為距離發(fā)射機(jī)d時接收的信號強(qiáng)度，P0(d0)為距離發(fā)射機(jī)d0(通常為1m)時接收的信號強(qiáng)度，n為路徑損耗指數(shù)，Xσ為均值為零、標(biāo)準(zhǔn)偏差為σ的高斯分布隨機(jī)變量，單位為dB。根據(jù)經(jīng)驗(yàn)，不同環(huán)境下的路徑損耗指數(shù)和標(biāo)準(zhǔn)偏差如表1所列。

1.2 基于箱線圖的異常RSSI檢測

在實(shí)際的測距場景中，接收信號強(qiáng)度指示(RSSI)不可避免會出現(xiàn)異常變化，導(dǎo)致測距出現(xiàn)較大偏差，為此提出了許多檢測方法濾除異常RSSI值，例如均值濾波法、3σ檢測法、狄克遜(Dixon)檢驗(yàn)法等。其中3σ異常值檢測[14]已經(jīng)被廣泛運(yùn)用到無線傳感器網(wǎng)絡(luò)中，但3σ檢測法需要假設(shè)RSSI值服從標(biāo)準(zhǔn)正態(tài)分布，但真實(shí)測量的RSSI值并不總是服從標(biāo)準(zhǔn)正態(tài)分布，且判斷異常值需要計算一包數(shù)據(jù)的均值和標(biāo)準(zhǔn)差，異常RSSI對均值和標(biāo)準(zhǔn)差會產(chǎn)生很大影響，因此利用3σ檢測法判斷異常RSSI值具有一定的適用范圍。

針對上述問題，本文提出一種基于箱線圖的異常RSSI檢測方法，該方法利用測量的數(shù)據(jù)中的5個統(tǒng)計量：最小值、第一四分位數(shù)(所有數(shù)據(jù)中由小到大排列后第25%的數(shù)字)、第二四分位數(shù)(所有數(shù)據(jù)中由小到大排列后第50%的數(shù)字)、第三四分位數(shù)(所有數(shù)據(jù)中由小到大排列后第75%的數(shù)字)和最大值剔除數(shù)據(jù)中的異常RSSI值，方法如下：

① 采集RSSI信號強(qiáng)度，如果lowerbounds

② 將測得的RSSI值序列RSSI∈Rn進(jìn)行從小到大排序：RSSI1

③ 計算出各分位數(shù)的位置，第一四分位數(shù)Q1=(n+1)/4，第二四分位數(shù)(中位數(shù))Q2=(n+1)/2，第三四分位數(shù)Q3=3(n+1)/4，通過3個四分位數(shù)將數(shù)據(jù)集合分成四組，每組數(shù)據(jù)占25%；計算四分位距(Interquartile Range, IQR)，IQR=Q3-Q1。

④ 計算出異常值截斷點(diǎn)(Outliers Cut-off Point)，OCP1=Q1-1.5IQR，OCP2=Q3+1.5IQR，異常值范圍為{RSSIol|RSSIOCP2}。

⑥ 重復(fù)上面步驟直至所有未知節(jié)點(diǎn)完成異常RSSI濾除。

圖1 箱線圖法處理流程圖

實(shí)驗(yàn)箱線圖處理異常RSSI值的流程如圖1所示。箱線圖法根據(jù)實(shí)際測量數(shù)據(jù)進(jìn)行異常值分析處理，既不需要數(shù)據(jù)服從某種特定的概率分布，也不需要對數(shù)據(jù)做任何限制性要求，可以真實(shí)直觀地反映出數(shù)據(jù)本身價值。此外，箱線圖判斷異常值的標(biāo)準(zhǔn)以四分位數(shù)和四分位距為基礎(chǔ)，其中四分位數(shù)具有較好的耐抗性，多達(dá)25%的數(shù)據(jù)可以變得任意遠(yuǎn)而不會很大地擾動四分位數(shù)，所以利用箱線圖處理異常RSSI值計算過程簡單，且具有較強(qiáng)的魯棒性，更適合應(yīng)用于能耗要求嚴(yán)格的無線傳感器網(wǎng)絡(luò)。

2 基于RSSI定位階段

2.1 經(jīng)典最小二乘法定位

圖2 最小二乘法定位原理圖

最小二乘法定位基本原理如圖2所示。已知隨機(jī)散布n個錨節(jié)點(diǎn)，其坐標(biāo)為(x1,y1)，(x2,y2)，…，(xn,yn)，未知節(jié)點(diǎn)坐標(biāo)為(x,y)。錨節(jié)點(diǎn)到未知節(jié)點(diǎn)間的距離為：d1，d2，…，dn。

可得定位方程組：

(3)

分別用方程組(3)中的前(n-1)個方程減去第n個方程，通過適當(dāng)簡化得到線性化方程：

(4)

其中：

由于受多種因素的影響，存在一定的測距誤差e，則實(shí)際線性方程為：

(5)

假設(shè)

(6)

利用最小二乘法原理保證Q(x)取得最小值,對上式求導(dǎo)數(shù)得

(7)

如果AAT是非奇異矩陣，則解X得

(8)

然而,可以看到定位方程組解的精度取決于最后一個方程所存在的誤差，即第n項的測量距離dn。如果dn的測距誤差較大，即使前(n-1)項方程的測距信息十分準(zhǔn)確，未知節(jié)點(diǎn)求解的位置估計值也會產(chǎn)生較大定位誤差。為了更好解釋這一問題，將方程(4)展開帶有誤差項，并用方程組的前(n-1)個方程減去第n個方程，可以得到方程組：

(9)

2.2 誤差自校正最小二乘定位算法

正如前面所述，信號衰減在無線信道內(nèi)傳播不可避免地會受到外界因素影響，實(shí)際RSSI值會出現(xiàn)一定的波動。但是如果節(jié)點(diǎn)間距離越近，外界因素對節(jié)點(diǎn)影響越小，進(jìn)而測距產(chǎn)生的誤差越低；反之，測距可能會產(chǎn)生較大的偏差。為了定量解釋這個現(xiàn)象，利用式(2)的對數(shù)路徑損耗模型對距離d求偏導(dǎo)數(shù)，得到式(10)：

(10)

(11)

其中：

(12)

根據(jù)上式近似有：

(13)

以此為前提，首先將測得的未知節(jié)點(diǎn)到n個錨節(jié)點(diǎn)之間的距離d1，d2，…，dn按大小進(jìn)行排序，得到式(3)所示的定位方程組,然后用相鄰的兩個方程進(jìn)行相減，簡化后得到線性方程：

(14)

其中：

2.3 基于箱線圖誤差自校正定位算法

通過上述對測距階段和定位階段分析改進(jìn)，提出一種基于箱線圖的誤差自校正定位算法，具體定位步驟如下：

① 錨節(jié)點(diǎn)以固定的發(fā)射功率周期性發(fā)送帶有節(jié)點(diǎn)ID和自身位置信息的數(shù)據(jù)包。

② 未知節(jié)點(diǎn)收到錨節(jié)點(diǎn)的位置信息后，用箱線圖法剔除異常RSSI值，求取平均值RSSIavg。

③ 在處理n個錨節(jié)點(diǎn)RSSI值后，將所有錨節(jié)點(diǎn)的RSSIavg值從大到小排序，構(gòu)建RSSIavg值與距離d的映射,建立3個集合：錨節(jié)點(diǎn)集合Anchor={A1，A2…，An}；距離集合Distance={d1，d2…，dn}，其中d1

④ 采用誤差自校正最小二乘定位算法獲取未知節(jié)點(diǎn)的位置坐標(biāo)。

3 算法仿真及結(jié)果

為了驗(yàn)證基于箱線圖的誤差自校正定位算法的可行性，與傳統(tǒng)的LS定位算法、加權(quán)最小二乘估計算法(WLSE)、加權(quán)最小二乘定位算法(WLS)進(jìn)行了比較。仿真軟件采用Matlab2016a進(jìn)行分析和評估，仿真環(huán)境如下：假設(shè)有6個錨節(jié)點(diǎn)和8未知節(jié)點(diǎn)隨機(jī)散布在12m×12m的范圍內(nèi)，節(jié)點(diǎn)間的通信半徑為12m。仿真使用對數(shù)路徑損耗模型，衰減因子n設(shè)為2，測量噪聲Xσ是均值為0、標(biāo)準(zhǔn)偏差為2的高斯隨機(jī)變量。根據(jù)傳感器實(shí)際性能設(shè)定距離為1m時，接收信號強(qiáng)度P0為40dB。作為衡量定位精度標(biāo)準(zhǔn)，定位誤差定義為：

(15)

仿真結(jié)果表明，基于箱線圖的誤差自校正定位算法具有很好的定位性能。為了降低節(jié)點(diǎn)分布對定位結(jié)果的影響，更好地驗(yàn)證算法的有效性，在不同的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)下進(jìn)行了50次仿真實(shí)驗(yàn)，仿真結(jié)果如圖3所示?？梢郧逦乜吹奖疚乃惴ㄆ骄ㄎ徽`差大約為15.03%，而LS、WLSE和WLS的平均定位誤差分別大約為27.49%、26.87%、26.52%。通過比較分析，基于箱線圖的誤差自校正定位算法定位誤差明顯低于其他算法。

圖3 平均定位誤差對比圖

在實(shí)際環(huán)境中，傳播模型實(shí)時變化、不同的仿真參數(shù)可能會導(dǎo)致不同定位誤差。為了更加貼合實(shí)際場景，分別對衰減因子n和測量噪聲Xσ進(jìn)行分析，對每個參數(shù)依次仿真50次，然后計算定位誤差均值。

圖4和圖5描述了對數(shù)路徑損耗模型中不同的測量噪聲和路徑損耗指數(shù)對定位誤差的影響?？梢郧逦乜吹剑罕疚乃惴ǘㄎ徽`差明顯低于其他三種定位算法定位誤差，即使在復(fù)雜多變環(huán)境下，基于箱線圖的誤差自校正定位算法仍能提供較好的定位信息服務(wù)，具有較高的穩(wěn)定性和耐抗性。

圖4 測量噪聲對定位誤差影響對比圖

圖5 路徑損耗指數(shù)對定位誤差影響對比圖

4 實(shí)驗(yàn)仿真及結(jié)果

4.1 實(shí)驗(yàn)平臺

實(shí)驗(yàn)中使用的無線傳感器節(jié)點(diǎn)為JN5148節(jié)點(diǎn)，是英國Jennic公司推出的高性能、低功耗的無線SoC模塊，集成了所有的射頻組件和無線微控制器。JN-5148有5種不同程度的功率消耗模式，考慮到能量功耗和通信性能，選擇標(biāo)準(zhǔn)模塊JN5148-001-M03，其分辨率為1 dB，獲得RSSI值的范圍是[20,108]。

4.2 測距實(shí)驗(yàn)分析

為了更好地理解RSSI的特性，利用兩個傳感器節(jié)點(diǎn)在學(xué)校體育場草地上進(jìn)行測距實(shí)驗(yàn)，地面22.7°，芯片20.6°，大氣濕度30%。傳感器節(jié)點(diǎn)一個作為發(fā)射端，一個作為接收端，測量沿直線從1 m到10 m,間隔1 m測量一次RSSI值，每個位置處測量100次。

由于多徑、遮蔽效應(yīng)的影響，RSSI值不可避免地出現(xiàn)

一些劇烈波動，如果不及時剔除異常RSSI值，可能會引起較大的測距誤差。為了進(jìn)一步分析RSSI分布，將10個位置采集的RSS正則化，利用概率密度函數(shù)描述每個位置處的RSS。如圖6所示，可以直觀地看到并不是所有的RSSI分布都服從標(biāo)準(zhǔn)正態(tài)分布，有時RSSI分布會出現(xiàn)左偏峰或者是雙峰的現(xiàn)象。

從表2中可以看到在某些位置處3σ檢測和HF&KDE檢測可能優(yōu)于箱線圖方法，但基于箱線圖法的平均距離誤差為0.60m，低于3σ檢測的0.71m以及HF&KDE檢測的0.94m。測距精度得到明顯改善，此外該方法計算簡單且行之有效，能較好地滿足無線傳感器網(wǎng)絡(luò)低功耗的需求。

圖6 正則化RSS概率密度函數(shù)

真實(shí)距離3σRSSI值3σ距離/m3σ絕對誤差HK&KDERSSI值HK&KDE距離/mHK&KDE絕對誤差BoxplotRSSI值Boxplot距離/mBoxplot絕對誤差1100．420．82-0．18100．420．86-0．14100．420．91-0．09295．671．73-0．2794．972．130．1395．232．020．02391．723．220．2291．923．520．5292．123．260．26488．395．441．4489．095．601．6089．394．961．96586．726．041．0486．726．041．0488．725．490．49687．196．570．5787．597．161．1687．346．790．79786．697．110．1186．608．301．3087．007．160．16886．467．37-0．6387．467．31-0．2386．467．77-0．23986．157．75-1．2587．157．69-1．3186．307．97-1．031085．498．60-1．4084．4811．921．9285．499．02-0．98平均誤差0．710．940．60

4.3 定位實(shí)驗(yàn)分析

圖7 定位實(shí)驗(yàn)節(jié)點(diǎn)分布示意圖

定位實(shí)驗(yàn)同樣在體育場草地上進(jìn)行。選用10個JN5148標(biāo)準(zhǔn)功率模塊節(jié)點(diǎn)，其中有6個錨節(jié)點(diǎn)和4個未知節(jié)點(diǎn)，隨機(jī)散布在12 m×12 m的區(qū)域內(nèi)，JN5148傳感器節(jié)點(diǎn)分布如圖7所示。

在定位過程中，未知節(jié)點(diǎn)UN1、UN2、UN3 和UN4分別接收來自6個錨節(jié)點(diǎn)的RSSI值，采用基于箱線圖的誤差自校正定位算法實(shí)現(xiàn)未知節(jié)點(diǎn)定位，分別與傳統(tǒng)的LS定位算法、加權(quán)最小二乘估計算法(WLSE)、加權(quán)最小二乘定位算法(WLS)進(jìn)行比較，定位誤差如表3所列。

表3 四種算法定位結(jié)果比較

結(jié) 語

參考文獻(xiàn)

[1] Yang K.Wireless sensor networks[J].Principles,Design and Applications,2014.

[2] Campos A N,Souza E L,Nakamura F G,et al.On the impact of localization and density control algorithms in target tracking applications for wireless sensor networks[J].Sensors,2012,12(6):6930-6952.

[3] Sacks L,Britton M,Wokoma I,et al.The development of a robust,autonomous sensor network platform for environmental monitoring[J].IOP Sensors and their applications XII,2003.

[4] Suo H,Wan J,Huang L,et al.Issues and challenges of wireless sensor networks localization in emerging applications[C]//Computer Science and Electronics Engineering (ICCSEE),2012 International Conference on IEEE,2012.

[5] Whitehouse K,Karlof C,Culler D.A practical evaluation of radio signal strength for ranging-based localization[J].ACM SIGMOBILE Mobile Computing and Communications Review,2007,11(1):41-52.

[6] Wu K,Xiao J,Yi Y,et al.CSI-based indoor localization[J].IEEE Transactions on Parallel and Distributed Systems,2013,24(7):1300-1309.

[7] Zhang C,Zhou X,Gao C,et al.On improving the precision of localization with gross error removal[C]//Distributed Computing Systems Workshops,28th International Conference on IEEE,2008.

[8] Chen Y C,Juang J C.Outlier-detection-based indoor localization system for wireless sensor networks[J].International Journal of Navigation and Observation,2012.

[9] Chuku N,Pal A,Nasipuri A.An RSSI based localization scheme for wireless sensor networks to mitigate shadowing effects[C]//Southeastcon, 2013 Proceedings of IEEE,2013:1-6.

[10] 王建剛,王福豹,段渭軍.加權(quán)最小二乘估計在無線傳感器網(wǎng)絡(luò)定位中的應(yīng)用[J].計算機(jī)應(yīng)用研究,2006(9):41-43.

[11] Jun Z G,Xin L,Long X Z,et al.Weighted Least Square Localization Algorithm Based on RSSI Values[C]//Instrumentation and Measurement,Computer,Communication and Control (IMCCC),2015 Fifth International Conference on IEEE,2015:1236-1239.

[12] Anderson D R,Sweeney D J,Williams T A,et al.Statistics for business & economics[M].Nelson Education,2016.

[13] Goldsmith A.Wireless communications[M].Oxford city:Cambridge university press,2005.

[14] Jin R,Xu H,Che Z,et al.Experimental evaluation of reducing ranging-error based on receive signal strength indication in wireless sensor networks[J].IET Wireless Sensor Systems,2015,5(5):228-234.

[15] Wang L,Baker A J.Critical Power for Vanishing of Isolated Nodes in Wireless Networks with Log-Normal Shadowing[C]//Mobile Ad-Hoc and Sensor Systems (MASS),2013 IEEE 10th International Conference on IEEE,2013:46-54.

[16] Jin R,Peng B,Meng L,et al.Research on localization method based on RSSI ranging-error compensation[C]//Wireless Communications,Networking and Mobile Computing,WiCom'09. 5th International Conference on IEEE,2009:1-3.

金仁成(副教授)，研究方向?yàn)闊o線傳感器網(wǎng)絡(luò)、物聯(lián)網(wǎng)；李應(yīng)琛(研究生)，研究方向?yàn)闊o線傳感器網(wǎng)絡(luò)定位技術(shù)、室內(nèi)定位技術(shù)；馬遠(yuǎn)(研究生)，研究方向?yàn)闊o線傳感器網(wǎng)絡(luò)定位技術(shù)；趙繼鵬(研究生)，研究方向?yàn)闊o線傳感器網(wǎng)絡(luò)路由技術(shù)。

Boxplot-based Error Self-calibration Localization Algorithm in WSNs

Jin Rencheng,Li Yingchen,Ma Yuan,Zhao Jipeng

(Key Laboratory for Micro/Nano Technology and System of Liaoning Province,Dalian University of Technology,Dalian 116024,China)

In order to solve the problem of wireless sensor network (WSNs) node location technology based on

signal strength indication (RSSI), which is easy to be influenced by the environment,and the algorithm has a large amount of computation and so on,a boxplot-based error self-calibration localization algorithm is proposed.The algorithm selects an adaptive distance estimation method based on boxplot to deal with outlier RSSI value,and uses a self-calibration least square algorithm to achieve localization by using ranging error self-elimination.The experiment results show that the proposed algorithm can effectively suppress outliers RSSI value and output a high and stable processing result while satisfying the high positioning accuracy requirement.For the above achievement,no hardware modification as well as time consuming RSSI-maps or complex signal propagation models are required.

wireless sensor networks;boxplot;error self-calibration;localization algorithm

國家重點(diǎn)基礎(chǔ)研究發(fā)展計劃(973計劃)資助項目(2009CB320300)；國家“十二五”科技支撐計劃資助項目(2011BAG05B02)；國家基金委創(chuàng)新群體項目(Science Fund for Creative Research Groups of NSFC)( 51621064)。

TP393.1

A

?士然

2017-02-20)