基于區(qū)間分析的WSNs定位算法

方余丞， 王洪誠， 崔勝利， 何俊儒， 朱　駿

(1.西南石油大學 機電工程學院，四川 成都 610500；2.西南石油大學 電氣信息學院，四川 成都 610500)

基于區(qū)間分析的WSNs定位算法

方余丞1， 王洪誠2， 崔勝利2， 何俊儒1， 朱駿2

(1.西南石油大學 機電工程學院，四川 成都 610500；2.西南石油大學 電氣信息學院，四川 成都 610500)

摘要:為了降低接收信號強度指示(RSSI)的測量誤差對節(jié)點定位精度的影響并提高算法的魯棒性，提出一種新的基于區(qū)間分析的無線傳感器網(wǎng)絡(luò)(WSNs)定位算法。該算法在測距階段運用自助抽樣法消除RSSI的測量誤差并構(gòu)建測距的置信區(qū)間；在定位階段，結(jié)合B-box定位法和集員辨識求出未知節(jié)點位置坐標的可行解集，通過網(wǎng)格掃描得到未知節(jié)點的估算位置。該算法通過仿真分析驗證了可行性，并與傳統(tǒng)的定位算法進行了誤差比較，實驗結(jié)果表明:該算法具有更高的定位精度且魯棒性更好。

關(guān)鍵詞:無線傳感器網(wǎng)絡(luò)； 定位算法； 接收信號強度指示； 自助抽樣法； 置信區(qū)間； 集員辨識

0引言

節(jié)點定位技術(shù)是無線傳感器網(wǎng)絡(luò)(wirelesssensornetworks,WSNs)的核心技術(shù)之一[1]。定位方法都是根據(jù)網(wǎng)絡(luò)中部分已知位置的節(jié)點(信標節(jié)點)來確定未知節(jié)點的位置坐標。當前的定位算法根據(jù)是否需要測量節(jié)點之間的實際距離分為：基于測距的定位算法和測距無關(guān)的定位算法。

測距無關(guān)的定位算法僅僅依靠網(wǎng)絡(luò)的連通等實現(xiàn)節(jié)點定位，其定位精度較低?；跍y距的定位算法是通過實際測量的節(jié)點間的距離或方位實現(xiàn)定位，其定位精度較之測距無關(guān)更高[2]。在基于測距的定位算法中，有到達時間(TOA)、到達時間差(TDOA)、到達角度(AOA)和接收信號強度指示(RSSI)等常見的測距方法[3]。其中,RSSI測距法是利用信號在傳輸過程中的損耗情況，根據(jù)理論和經(jīng)驗?zāi)Ｐ凸浪愠龉?jié)點間的距離，由于節(jié)點模塊本身可以滿足RSSI值的測量，無需增添額外的硬件支持，RSSI測距法在目前的定位技術(shù)中運用最為廣泛[4]。

基于測距的定位算法主要分為兩個階段：測距階段和定位階段。而大量的研究表明這類定位算法的誤差主要來自于測距階段[5]。因此,降低測距過程的誤差已成為近幾年WSNs定位技術(shù)的重點研究對象?；赗SSI測距法的測距階段，誤差來源主要來自RSSI與距離關(guān)系模型導(dǎo)致的誤差和環(huán)境因素導(dǎo)致RSSI值本身的測量誤差。其中RSSI與距離關(guān)系模型導(dǎo)致的誤差，可利用現(xiàn)場實驗測得數(shù)據(jù)，結(jié)合系統(tǒng)辨識理論得到模型的參數(shù)值，從而降低該誤差。而對RSSI值測量誤差的校正，近幾年的文獻中也提出了許多優(yōu)秀的方法。如文獻[6]提出了一種基于高斯加權(quán)的算法，該算法通過設(shè)定一個閾值將偏差較大的RSSI值篩選出來，從而避免了這些偏差較大的數(shù)據(jù)所帶來的誤差；文獻[7]則首次引入了統(tǒng)計學方法，該算法計算一定量的RSSI數(shù)據(jù)的中值，然后給所有信號強度值進行加權(quán)從而降低了RSSI值的測量誤差。

本文以降低RSSI測量誤差并提高定位算法的定位精度和魯棒性為目的，提出了一種新的基于RSSI測距的WSNs節(jié)點定位算法。該算法在測距階段引入統(tǒng)計學的知識，運用自助法降低RSSI的測量誤差，并構(gòu)建測距的置信區(qū)間；在定位階段，結(jié)合B-box定位法和集員辨識求出未知節(jié)點位置的可行解集，最后通過網(wǎng)格掃描法得到未知節(jié)點的最終估算位置。

1算法模型

1.1基于自助法構(gòu)建測距置信區(qū)間

自助(bootstrap)法由Efron于1979年提出，與刀切法(Jacknife)類似，是一種推斷樣本變化的重采樣方法[8]。與刀切法相比，它更易于構(gòu)造置信區(qū)間?；谧灾?gòu)建測距的置信區(qū)間的具體步驟如下：

1)在測距階段，未知節(jié)點接收到來自鄰近信標節(jié)點的信號指示，假設(shè)未知節(jié)點接收到某一個信標節(jié)點的信號指示為m次，從中隨機選取n個構(gòu)成一個集合，可表示為RSSI=(RSSI1，RSSI2，…，RSSIn)，計算出該樣本的平均值

(1)

(2)

3)重復(fù)步驟(2),N次，得到一個N維的數(shù)據(jù)集合，分別為

4)將上一步得到的RSSI值代入式(3)，得到對應(yīng)的距離值

(3)

式中i=1，…，N;RSSI(d0),d0, n,ε已知。

5)將上一步求的的距離值從小到大排序

(4)

1.2基于集員辨識的定位估計

集員(setmembership)法是一種假設(shè)噪聲在未知但有界(UBB)情況下的辨識方法，常用于處理非線性定位問題，相對于一般的概率方法，在處理強非線性問題時它有更好的適應(yīng)性。集員辨識的結(jié)果不是一個標稱值(點)，而是一個集合(可行解集)，隨著樣本容量的增大，集合所包含的范圍逐漸縮小，當樣本容量趨于無窮大時，解集最終將收斂為系統(tǒng)的真實值[9]。

在測距階段，本文成功地構(gòu)建了測距的置信區(qū)間。通過置信區(qū)間的上限界值和下限界值得到每一個信標節(jié)點和未知節(jié)點之間距離的有效區(qū)間。選取其中距離未知節(jié)點最近的三個信標節(jié)點，如圖1所示,將會產(chǎn)生一個交集(即未知節(jié)點位置的可行解集)。為了降低計算的復(fù)雜程度，如圖2所示使用方形邊界(即B-box定位法)代替圓形邊界構(gòu)建一個更具規(guī)律性的交集。

圖1　圓形邊界可行解集Fig 1　Feasible solution set of circle bounding

圖2　方形邊界可行解集Fig 2　Feasible solution set of square bounding

將測距的置信區(qū)間表示為UI=[UI-，UI+]，其中,UI為測距真實值的閉區(qū)間，UI-和UI+分別為UI的上限界值和下限界值。根據(jù)集合的相關(guān)理論，兩個區(qū)間的交集可表示為

(5)

因此，運用集員辨識理論可以得到未知節(jié)點坐標的可行性解如下所示

(6)

將未知節(jié)點的可行解集Θ劃分到n個獨立的正方形里，Θ={Ω1，Ω2，…，Ωn}，其中,每個正方形Ωi質(zhì)心可表示為

(7)

為了得到未知節(jié)點最優(yōu)估算坐標Ω0，通過網(wǎng)格計算出最終估算坐標，公式如下

(8)

式中Aj為信標節(jié)點的坐標，dj為信標節(jié)點與未知節(jié)點的距離。

2仿真分析

本次研究在Matlab(2010b)仿真平臺進行仿真以驗證該算法的有效性。

首先通過仿真分析算法在測距階段的測距誤差，并與文獻[6]和文獻[7]中提出的算法進行測距誤差對比分析。設(shè)置WSNs在大小為30m×30m的室內(nèi)非自由空間，距離轉(zhuǎn)換模型采用式(3)，n和ε根據(jù)經(jīng)驗法分別配置為2.7和6.8，在該區(qū)域內(nèi)隨機設(shè)置7個信標節(jié)點，已知這7個信標節(jié)點坐標位置分別為(2，12),(4，10),(5，14),(8，4).(8，7),(9，14),(10，11)m，任取一個作為計算節(jié)點并計算該節(jié)點到其他節(jié)點的距離，然后分別運用高斯加權(quán)法[6]、中值加權(quán)法[7]、自助抽樣法計算出測距，并重復(fù)10次得到測距結(jié)果如表1所示，測距偏差值如表2所示。

表1　測距結(jié)果

表2　測距偏差值

在表2 中，采用自助抽樣法所測的距離偏差值最大為2.15m，其余偏差值皆穩(wěn)定在0.61～1.13m；高斯加權(quán)法的偏差值最大為2.97m，最小為0.47m，波動較大，穩(wěn)定性較低；中值加權(quán)法最大偏差值為2.49m，最小為0.52m，穩(wěn)定性也明顯低于自助抽樣法。接下來采用以測距結(jié)果的倒數(shù)作為權(quán)值給每一個節(jié)點的測距偏差值進行加權(quán)的方法，計算出三種方法的測距平均誤差，結(jié)果如表3所示。

表3　測距平均誤差

從表3可以看出使用本文提出的基于自助抽樣法校正RSSI值后得到的測距結(jié)果，其誤差明顯低于另外兩種算法，這說明自助抽樣法對RSSI值的校正效果優(yōu)于其它兩種算法。

分析了算法的測距誤差后，再次運用Matlab仿真，對比分析本文所提出的基于區(qū)間分析的WSNs定位算法與傳統(tǒng)的加權(quán)質(zhì)心定位算法[10]，兩種算法在測距階段均分析定位誤差和算法的魯棒性。

設(shè)置WSNs環(huán)境與上面一致，在該區(qū)域內(nèi)隨機設(shè)置1個未知節(jié)點和若干信標節(jié)點。這里設(shè)置未知節(jié)點坐標為(8，7)m，信標節(jié)點的個數(shù)為4個，隨機分布在未知節(jié)點的周圍，分別使用基于區(qū)間分析的定位算法和加權(quán)質(zhì)心定位算法進行5次循環(huán)定位，得到定位結(jié)果，然后計算出每次定位結(jié)果的定位誤差，定位誤差表如表4所示。

表4　定位誤差(1)

從表4可以看出：采用本文提出的算法得到的定位誤差最大為1.1m左右，最小為0.8m左右，波動范圍較小，而加權(quán)質(zhì)心定位算法的定位誤差最大達到2.3m，最小僅有0.9m，波動范圍較大。這說明本文提出的定位算法與傳統(tǒng)的加權(quán)質(zhì)心定位算法相比，具有更好的魯棒性。

逐漸增加信標節(jié)點個數(shù)(從4個開始)，分別使用兩種算法得到其定位結(jié)果，并計算出定位誤差如表5所示。網(wǎng)絡(luò)環(huán)境與前兩次仿真保持一致，未知節(jié)點坐標位置為(8，7)m，信標節(jié)點隨機的分布在未知節(jié)點周圍，每次定位均循環(huán)10次，取其平均值作為最終定位結(jié)果。

由表5可知，本文所提出的定位算法在定位誤差上明顯小于傳統(tǒng)的加權(quán)質(zhì)心定位算法。而隨著信標節(jié)點個數(shù)的增加兩種算法的定位精度都在不斷提高，這也驗證了信標節(jié)點的密度對節(jié)點定位的精度影響較大。

表5　定位誤差(2)

3結(jié)論

為了降低RSSI的測量誤差對節(jié)點定位精度的影響并提高算法的魯棒性，本文結(jié)合統(tǒng)計學的理論提出一種新的基于區(qū)間分析的WSNs定位算法。仿真實驗驗證結(jié)果表明:該算法具有RSSI校正效果好、定位精度高，并且具備更好的魯棒性，與傳統(tǒng)的其他算法比較，具有明顯的優(yōu)勢。

參考文獻:

[1]姚艷, 禹繼國, 郭強.基于網(wǎng)格掃描的無線傳感器網(wǎng)絡(luò)定位算法[J].計算機工程, 2012, 38(9):86-89.

[2]劉玉軍, 蔡猛, 高立恒，等.基于RSSI測距的傳感器節(jié)點質(zhì)心定位修正算法[J].計算機測量與控制, 2014(9):2860-2862.

[3]宋慧敏, 楊社堂, 趙棟棟.基于人工神經(jīng)網(wǎng)絡(luò)的無線傳感器定位算法[J].計算機測量與控制, 2014, 22(2):473-475.

[4]彭宇, 王丹.無線傳感器網(wǎng)絡(luò)定位技術(shù)綜述[J].電子測量與儀器學報, 2011, 25(5):389-399.

[5]胡文鵬.一種基于RSSI的無線傳感器網(wǎng)絡(luò)定位算法的設(shè)計與實現(xiàn)[D].長春：吉林大學, 2009.

[6]文春武, 宋杰, 姚家振.基于RSSI校正的無線傳感器網(wǎng)絡(luò)定位算法[J].傳感器與微系統(tǒng), 2014, 33(12):134-136.

[7]朱忠記, 何熊熊, 章曉，等.基于RSSI的四邊測距改進加權(quán)質(zhì)心定位算法[J].杭州電子科技大學學報, 2014 (1):17-20.

[8]鄧海軍, 查亞兵.自助法中若干問題研究及其在命中精度評估中的應(yīng)用[J].飛行器測控學報, 2005, 24(1):59-63.

[9]梁禮明, 鐘敏.集員辨識理論發(fā)展及算法綜述[J].自動化技術(shù)與應(yīng)用, 2007, 26(11):7-9.

[10] 陳維克, 李文鋒, 首珩，等.基于RSSI的無線傳感器網(wǎng)絡(luò)加權(quán)質(zhì)心定位算法[J].武漢理工大學學報: 交通科學與工程版, 2006, 30(2): 265-268.

WSNslocalizationalogrithmbasedonintervalanalysis

FANGYu-cheng1,WANGHong-cheng2,CUISheng-li2,HEJun-ru1,ZHUJun2

(1.SchoolofMechatronicsEngineering,SouthwestPetroleumUniversity,Chengdu610500，China;2.SchoolofElectricalInformation,SouthwestPetroleumUniversity,Chengdu610500，China)

Abstract:To reduce effect of measurement error of received signal strength indication (RSSI) on localization precision of node and improve robustness of algorithm, propose a new wireless sensor networks(WSNs) localization algorithm based on interval analysis.This algorithm uses bootstrap sampling method in ranging phase to eliminate measurement error of RSSI and build confidence intervals of ranging; in positioning phase, solve set of feasible solution sets of unknown node position coordinates,combined with B-box positioning method and set membership identification, then obtain estimated position of unknown nodes by grid scanning.Feasibility of algorithm is verified by simulation analysis, compared this algorithm with the traditional localization algorithm in error, the experimental results show that this algorithm has higher precision and better robustness.

Key words:wireless sensor networks(WSNs);localization algorithm; received signal strength indication(RSSI); bootstrap sampling method; confidence interval; set membership identification

DOI:10.13873/J.1000—9787(2016)04—0141—03

收稿日期：2015—07—29

中圖分類號:TP 393.1

文獻標識碼:A

文章編號:1000—9787(2016)04—0141—03

作者簡介:

方余丞(1991-)，男，四川南充人，碩士研究生，主要研究方向為測試計量技術(shù)與儀器。