基于iBeacon的室內(nèi)定位算法優(yōu)化研究

林信川, 游貴榮

(1.福建商學院 信息管理工程系，福建 福州 350012；2.福建商學院 信息網(wǎng)絡中心，福建 福州 350012)

基于iBeacon的室內(nèi)定位算法優(yōu)化研究

林信川1, 游貴榮2

(1.福建商學院 信息管理工程系，福建 福州 350012；2.福建商學院 信息網(wǎng)絡中心，福建 福州 350012)

針對無線傳感網(wǎng)絡中室內(nèi)定位算法定位精度不高、算法收斂慢的問題，依托基于BLE 4.0的iBeacon基站設備，為提升室內(nèi)定位算法精度和效率，提出IIDWC定位算法。該算法結(jié)合基于測距的RSSI技術(shù)、加權(quán)質(zhì)心算法和倒數(shù)距離加權(quán)插值定位思想，在確定多個廣播重疊區(qū)域加權(quán)質(zhì)心坐標及其權(quán)重系數(shù)的過程中，反復利用倒數(shù)距離加權(quán)插值方法，通過提升關鍵錨節(jié)點在確定加權(quán)質(zhì)心坐標過程中的重要性，進一步優(yōu)化權(quán)重系數(shù)，在仿真環(huán)境中提升了定位精度和收斂速度。通過合理設置錨節(jié)點的功率、通信半徑、部署密度和測量時間，該算法的定位精度能夠達到0.8 m，滿足了多數(shù)室內(nèi)定位場景的技術(shù)要求。

無線傳感網(wǎng)絡; iBeacon錨節(jié)點; RSSI; 加權(quán)質(zhì)心

隨著數(shù)據(jù)業(yè)務和多媒體業(yè)務的飛速增長，基于無線傳感器網(wǎng)絡(Wireless Sensor Networks，WSNs)[1]進行室內(nèi)精確定位的技術(shù)已成為當前研究的一個新熱點。室內(nèi)節(jié)點定位作為無線傳感網(wǎng)絡的一項關鍵技術(shù)，其基本要求是獲取室內(nèi)節(jié)點的位置坐標。當前廣泛使用的GPS定位技術(shù)主要應用于室外場景，對于室內(nèi)定位場景，有可能出現(xiàn)多徑現(xiàn)象導致定位結(jié)果不準確或無法定位。目前常用的室內(nèi)定位技術(shù)有基于超聲波、紅外線、超寬帶的定位技術(shù)和射頻識別定位技術(shù)(WLAN、ZigBee)等?？紤]到測量過程中，不同節(jié)點間的角度數(shù)據(jù)或距離數(shù)據(jù)的關聯(lián)性，測距(range-based)算法和測距無關(range-free)算法[2]是比較常見的兩類定位算法。前者在收集節(jié)點間的距離或角度信息的基礎上，待測節(jié)點的位置可通過三邊測量法、三角測量法或最大似然估計法[3]進行計算，RSSI、TOA、TDOA和AOA等[4]都是此類算法的代表，此類算法對硬件有一定要求，但定位精度相對較高。后者分析過程中不依賴于距離和角度數(shù)據(jù)，通常利用網(wǎng)絡對通性等數(shù)據(jù)進行分析，常見的有質(zhì)心算法、Amorphous算法和DV-Hop算法[5]等。雖然此類算法對硬件要求較低，但反射、散射和繞射現(xiàn)象往往對定位誤差影響較大。

目前國內(nèi)外研究者針對基于WSNs的室內(nèi)定位算法和方案進行了大量研究。石欣等[6]提出了改進的RSSI多維標度室內(nèi)定位算法，通過建立各節(jié)點信號強度的相異性矩陣，相繼應用多維標度法、平面四參數(shù)模型記性坐標計算和轉(zhuǎn)換、粒子群算法確定了優(yōu)化參數(shù)，最終計算出移動節(jié)點坐標。余刨等[7]通過設定平均分布的三類基準點獲取測試場景內(nèi)具有不同定位標簽的RSSI向量，在依據(jù)判定規(guī)則確定基準點后，利用無線信號室內(nèi)傳播模型得到移動權(quán)值，用于計算待測節(jié)點的坐標數(shù)據(jù)。李石榮等[8]提出了一種基于RSSI概率統(tǒng)計分布的加權(quán)K最近鄰算法，利用SPD方法和SVM算法，進行指紋節(jié)點RSSI向量區(qū)間構(gòu)建和K個近鄰指紋點選擇，并利用測試點RSSI向量到每個近鄰指紋點的最小歐氏距離，通過WKNN算法獲取定位結(jié)果。黃海輝等[9]提出了W-Centroid加權(quán)質(zhì)心算法，采用測距倒數(shù)之和替代測距之和的倒數(shù)，并將其作為減小定位誤差的權(quán)重，強化了關鍵節(jié)點的因子。丁恩杰等[10]提出了WR-Centroid算法，將RSSI與加權(quán)質(zhì)心算法相結(jié)合，相較加權(quán)質(zhì)心算法在提升定位精度的同時降低了通信節(jié)點的成本。劉云等[11]提出了WCBD算法，通過優(yōu)化權(quán)重系數(shù)，加快了算法的收斂速度，進一步論證了其對于定位算法結(jié)果精度的重要性。

iBeacon是由蘋果公司于2013年發(fā)布的基于低功耗藍牙4.0(BLE 4.0)的技術(shù)，目前已普遍用于各類室內(nèi)定位場景，但存在定位方式單一、定位精度不高的問題，且針對其定位精度和效率優(yōu)化的研究成果較少。本文研究和仿真環(huán)境主要基于配備DA14850芯片的iBeacon基站設備，結(jié)合基于測距的RSSI技術(shù)、加權(quán)質(zhì)心算法和插值定位思想，通過進一步優(yōu)化iBeacon在室內(nèi)通信過程中的權(quán)重系數(shù)，提出IIDWC算法。

1 RSSI測距技術(shù)

iBeacon的通信過程遵循無線電通訊模型，因此在本文將利用無線信號傳播路徑損耗模型中的對數(shù)-常態(tài)分布模型[12]進行研究。該模型定義如下：

PL(d)=PL(d0)+10nlg(d/d0)+ε,

(1)

其中d和d0為待測節(jié)點位于不同位置時與錨節(jié)點間的歐式距離，PL(d)和PL(d0)分別為傳輸距離為d和d0時的接收功率，其單位為dBm；n為信號的衰減因子，與無線傳感網(wǎng)絡環(huán)境密切相關；ε為一個均值為0且同時服從高斯分布的隨機變量。在iBeacon室內(nèi)定位技術(shù)中將d0固定為1 m，那么PL(d0)即為距離iBeacon錨節(jié)點1 m處的接收功率，對于采用確定芯片的iBeacon錨節(jié)點，其值將為固定值。可將以上傳播模型簡化為iBeacon在室內(nèi)環(huán)境下的信號傳播模型：

RSSI=T-10nlgd+ε,

(2)

其中T表示距離iBeacon錨節(jié)點1 m處的無線信號強度RSSI值，T和n需要通過對大量測量數(shù)據(jù)進行擬合后得到。當前位置與不同錨節(jié)點間的RSSI值可通過藍牙終端測得，d為通過計算得到歐氏距離，以下分析中將其與實際距離進行比較進而確定算法誤差。

2 加權(quán)質(zhì)心定位算法模型

三角質(zhì)心定位算法[13]和多邊形質(zhì)心定位算法[14]是基于RSSI的常見定位算法。加權(quán)質(zhì)心算法[15]是在常見質(zhì)心算法的基礎上，利用待測節(jié)點和錨節(jié)點間距離信息值(RSSI值)，計算出該錨節(jié)點的權(quán)重系數(shù)，該值可用于衡量每一個錨節(jié)點對質(zhì)心位置的影響力，并反映出待測節(jié)點和錨節(jié)點間的內(nèi)在關系。

加權(quán)質(zhì)心算法可以表示為：

(3)

其中(x,y)為待測節(jié)點的坐標，錨節(jié)點共N個，第i個的坐標為(xi,yi)，其中1≤i≤N，ωi為第i個錨節(jié)點對應的權(quán)重系數(shù)。常見的權(quán)重系數(shù)的取值為待測節(jié)點與錨節(jié)點之間距離d的函數(shù)，通常該函數(shù)滿足d越大權(quán)重系數(shù)ωi越小的規(guī)律。若待測節(jié)點不在測量范圍內(nèi)，則相應錨節(jié)點的權(quán)重系數(shù)值為0。

3 改進的加權(quán)插值定位算法

本文提出的IIDWC(Improved Inverse Distance on Weighted Centroid)算法，是在倒數(shù)距離加權(quán)插值[15]的基礎上，首先分別取得各錨節(jié)點位置與廣播邊界交點的距離倒數(shù)之和，作為確定廣播重疊區(qū)域質(zhì)心的權(quán)重系數(shù)，進而得到經(jīng)過加權(quán)優(yōu)化計算的該區(qū)域的加權(quán)質(zhì)心坐標。通過上述所得的多個加權(quán)質(zhì)心坐標，可反復利用倒數(shù)距離加權(quán)插值的方法，基于各錨節(jié)點的位置優(yōu)化各加權(quán)質(zhì)心的權(quán)重系數(shù)，最終可通過加權(quán)質(zhì)心算法計算得到待測節(jié)點的理論坐標。此舉進一步使距離較近的錨節(jié)點在定位過程中起到更加主要的作用，即錨節(jié)點與待測節(jié)點的距離越近，傳播路徑損耗值越小，在權(quán)重系數(shù)的計算過程中影響力就越大。這就避免了一些算法中非關鍵錨節(jié)點對定位結(jié)果產(chǎn)生的干擾。

首先在待測節(jié)點M(x,y)的四周部署4個iBeacon錨節(jié)點A、B、C、D，坐標分別為OA(xA,yA)、OB(xB,yB)、OC(xC,yC)、OD(xD,yD)，4個錨節(jié)點持續(xù)性地向待測節(jié)點M發(fā)送廣播信號，d1為錨節(jié)點A與待測節(jié)點M間的歐式距離，d2為錨節(jié)點B與待測節(jié)點M間的歐式距離，d3為錨節(jié)點C與待測節(jié)點M間的歐式距離，d4為錨節(jié)點D與待測節(jié)點M間的歐式距離。

分別以其中的3個錨節(jié)點A、B、C為圓心，d1、d2和d3為半徑作圓。假設3個圓存在廣播重疊區(qū)域，且邊界交點分別為O1、O2和O3。其中交點O1坐標(xO1,yO1)的計算方法為：

(4)

O2(xO2,yO2)和O3(xO3,yO3)的坐標值同理可得。以O1、O2和O3為頂點可構(gòu)成一個三角形。多數(shù)研究方法通過求得的O1、O2和O3的坐標，利用三角質(zhì)心算法得到該區(qū)域的三角質(zhì)心坐標。此舉未充分考慮待測節(jié)點與各錨節(jié)點之間的距離對后續(xù)定位算法精度的影響，因此本文也對該區(qū)域的質(zhì)心坐標的計算過程進行了改進。

通過A、B、C三點和O1的相對位置，可得O1的優(yōu)化后的權(quán)重系數(shù)為

(5)

其中dAO1、dBO1和dCO1分別為O1到錨節(jié)點A、B、C的歐式距離。同理分別將O2和O3視為待測節(jié)點，那么

(6)

則以O1、O2和O3為3個頂點的三角形區(qū)域的加權(quán)質(zhì)心坐標N1(x1,y1)為

(7)

圖1 定位模型

(8)

4 算法過程

4.1 算法步驟

由以上的定位模型分析，將本文提出的IIDWC算法的實現(xiàn)步驟歸納如下：

1)將待測節(jié)點部署在多個錨節(jié)點的廣播范圍內(nèi)，已部署的多個錨節(jié)點均按照一定頻率持續(xù)進行廣播，其廣播數(shù)據(jù)包中包含其ID及其位置信息；

2)待測節(jié)點對接收到的來自各錨節(jié)點的數(shù)據(jù)包進行濾波和數(shù)據(jù)擬合，根據(jù)iBeacon在室內(nèi)環(huán)境下的信號傳播模型，利用式(2)分別通過測得的RSSI值計算出待測節(jié)點與其附近錨節(jié)點的歐式距離；

3)將以上步驟求得的多個歐氏距離值按照升序排列，優(yōu)先選取與待測節(jié)點距離最近的4個錨節(jié)點，若其中任意3個錨節(jié)點無法構(gòu)成圖1所示區(qū)域，那么可使用與待測節(jié)點間歐式距離更大的錨節(jié)點代替該節(jié)點，直到可構(gòu)成圖1所示區(qū)域為止；

4)利用以上步驟中4個錨節(jié)點中的任意3個進行待測節(jié)點定位，廣播重疊區(qū)域交點的坐標通過式(4)可得，進而通過改進的加權(quán)插值定位算法求出重疊三角區(qū)域的加權(quán)質(zhì)心坐標；

5)重復步驟(4)，將余下錨節(jié)點中的任意3個反復組合，可求得另外3個重疊三角區(qū)域的加權(quán)質(zhì)心坐標；

6)通過式(8)對步驟(4)和步驟(5)中所得的4個加權(quán)質(zhì)心節(jié)點，重復利用倒數(shù)距離加權(quán)插值定位算法，計算待測節(jié)點的理論坐標值；

7)比較待測節(jié)點的計算所得的理論坐標與實際坐標之間的誤差。

4.2 誤差分析

可通過公式(9)計算本算法的誤差:

(9)

其中(x,y)和(xe，ye)分別為待測節(jié)點的實際坐標和理論坐標。若存在n個待測節(jié)點，則可通過平均誤差E衡量本算法的精度，表述如下:

(10)

5 仿真分析

5.1 測距并擬合

選擇一個80 m×80 m的空曠場所作為測試場所完成iBeacon傳播模型的測定實驗。首先將1個iBeacon錨節(jié)點固定在房間中的一個位置，然后分別距離該錨節(jié)點2、6、10、…、78 m處設置40個測試點，通過在每個待測節(jié)點處使用支持BLE 4.0的藍牙設備采集RSSI值，每個測試點采集100組樣本數(shù)據(jù)。反復采集80個不同錨節(jié)點的樣本數(shù)據(jù)經(jīng)處理后進行高斯濾波，將濾波后的樣本的平均值作為該位置的RSSI值，最后使用MATLAB 2015b對RSSI值與距離值d之間的關系，通過式(2)進行擬合，擬合曲線如圖2所示，得到擬合函數(shù)為：

RSSI=-20lgd-67。

(11)

圖2 RSSI值與距離d擬合關系

5.2 仿真論證

使用MATLAB2015b針對IIDWC算法進行仿真，實驗環(huán)境相同。與一些分析過程中信號衰減因子n多以經(jīng)驗值進行假設分析不同，本文根據(jù)式(11)可知信號衰減因子n=2.0，信道中的隨機高斯噪聲在5～10之間。在80 m×80 m場所內(nèi)分別均勻布置10、20、30、40、50、60、70、80個iBeacon錨節(jié)點，同時在該場所內(nèi)隨機選取100個點作為待測節(jié)點位置。對W-Centroid算法、WR-Centroid算法、WCBD算法和本文提出的IIDWC算法進行仿真，如圖3—圖5所示。

圖3 平均誤差隨時間變化

圖3在錨節(jié)點數(shù)量和錨節(jié)點通信半徑固定不變的前提下，4種算法的平均誤差雖然都隨時間呈現(xiàn)出逐漸下降并最終收斂的趨勢，但IIDWC算法的收斂速度明顯快于其他3種算法，在28 s后基本收斂，且最終收斂后的平均誤差達到1.4 m，與其他3種算法相比，定位精度明顯提高。

圖4 平均誤差隨通信半徑變化

圖4在錨節(jié)點數(shù)量和采樣間隔時間固定不變的前提下，通過逐步調(diào)整錨節(jié)點的通信半徑，4種算法的定位精度都不斷提高并呈現(xiàn)收斂的趨勢。IIDWC算法的平均誤差值均小于其他3種算法，且在錨節(jié)點通信半徑達到10 m時平均誤差已收斂于1.7 m以內(nèi)，隨著錨節(jié)點通信半徑增加，其該算法的定位精度還將進一步提升。

圖5在錨節(jié)點的通信半徑設定為30 m且采樣間隔時間固定不變的前提下，通過增加均勻部署的錨節(jié)點的數(shù)量，可以有效提升4種算法定位的精確度。當均勻部署的錨節(jié)點的數(shù)量達到45個時，IIDWC算法的精度已經(jīng)控制在1 m以內(nèi)，較之誤差僅次于該算法的WCBC算法定位精度提高了41.6%。在錨節(jié)點數(shù)量多于50個時，平均誤差明顯開始收斂，其收斂時機要早于其他3種算法。

圖5 平均誤差隨錨節(jié)點數(shù)量變化

6 結(jié) 語

無線傳感網(wǎng)絡中室內(nèi)定位算法研究的主要問題集中在如何提升算法的定位精度以及收斂速度兩個方面。本文基于iBeacon技術(shù)，結(jié)合RSSI技術(shù)、加權(quán)質(zhì)心算法和倒數(shù)距離加權(quán)插值定位思想，利用定位過程中起主要作用的錨節(jié)點與待測節(jié)點的位置關系，優(yōu)化了加權(quán)質(zhì)心坐標及其權(quán)重系數(shù)的計算方法，提出了IIDWC算法。由仿真結(jié)果可知本算法在同等條件下，較其他定位算法具有更快的收斂速度和更高的定位精度。在后續(xù)的工作中，準備將本算法應用于實體的室內(nèi)定位項目，以進一步驗證和改進，為以后的空間精確定位算法起一定的指導作用。

[1] 馬曉賢,彭力.一種改進的無線傳感器網(wǎng)絡DV-Hop定位算法[J].計算機工程與應用,2015,51(21):97-101.

[2] 郄劍文,賈方秀,李興隆,等.基于組合測距的無線傳感器網(wǎng)絡自定位算法[J].傳感技術(shù)學報,2016,29(5):739-744.

[3] 金艷,李曙光,姬紅兵.基于柯西分布的跳頻信號參數(shù)最大似然估計方法[J].電子與信息學報,2016,38(7):1696-1702.

[4] 張怡,席彥彪,李剛偉,等.基于卡爾曼濾波的TDOA/AOA混合定位算法[J].計算機工程與應用,2015,51(20):62-66.

[5] 向滿天,王勝,楊友華.基于閾值機制與距離校正的WSN改進DV-Hop定位算法[J].傳感技術(shù)學報,2016,29(6):920-926.

[6] 石欣，印愛民，陳曦.基于RSSI的多維標度室內(nèi)定位算法[J].儀器儀表學報,2014,35(2):261-268.

[7] 余刨，戰(zhàn)蔭偉.基于RSSI的移動權(quán)值定位算法[J].計算機應用研究,2016,33(5):1450-1452.

[8] 李石榮,李飛騰.基于RSSI概率統(tǒng)計分布的室內(nèi)定位方法[J].計算機工程與應用,2016,52(11):119-124.

[9] 黃海輝,李龍連.WSN中一種基于RSSI的移動節(jié)點改進定位算法[J].電子技術(shù)應用,2015,41(1):86-89.

[10] 丁恩杰，喬欣，常飛，等．基于RSSI的WSNs加權(quán)質(zhì)心定位算法的改進[J]，傳感器與微系統(tǒng)，2013，32(7)：53-56．

[11] 劉云,劉菁原.基于RSSI的加權(quán)質(zhì)心定位算法優(yōu)化研究[J].華中師范大學學報(自然科學版),2016,50(3):358-362

[12] 尹海峰.基于移動信標節(jié)點的無線傳感器網(wǎng)絡定位算法設計[D].南京：南京理工大學,2014.

[13] 趙大龍,白鳳山,董思宇,等.一種基于卡爾曼和線性插值濾波的改進三角質(zhì)心定位算法[J].傳感技術(shù)學報,2015(7):1086-1090.

[14] 崔法毅,邵冠蘭.基于RSSI多邊定位誤差的加權(quán)質(zhì)心定位算法[J].紅外與激光工程,2015,44(7):2162-2168.

[15] 樊子德,李佳霖,鄧敏.顧及多因素影響的自適應反距離加權(quán)插值方法[J].武漢大學學報(信息科學版),2016,41(6):842-847.

[責任編輯：張存鳳]

Study on optimization of indoor location algorithm based on iBeacon

LIN Xin-chuan1,YOU Gui-rong2

(1. Department of Information Management and Engineering,Fujian Commercial College,Fuzhou 350012,China;2. Information Network Center,Fujian Commercial College,Fuzhou 350012,China)

Aiming at the problems of low localization accuracy and slow convergence of wireless sensor networks,this paper proposes a newly improved algorithm named IIDWC based on iBeacon technology to improve the precision and efficiency. This algorithm is based on RSSI ranging technology,weighted centroid algorithm and inverse distance weighted interpolation ideas. In the process of determining multiple broadcasts overlapped the weighted centroid coordinates and their weights,by repeatedly using the inverse distance weighted interpolation method,it optimizes the weight coefficient,and promotes the weight of key anchors for calculating the weighted centroid coordinates. In the simulation environment by setting power,communication deployed RADIUS,density of anchor nodes and the measurement of time,localization accuracy of the algorithm can achieve less than 0.8 m. It can meet the requirements for the indoor location project.

wireless sensor networks; iBeacon anchor node; RSSI; weighted centroid

2096-3998(2017)03-0067-07

2016-11-21

2017-03-13

福建省教育廳A類基金資助項目(JA15730)

林信川(1981—),男，福建省福州市人，福建商學院講師，碩士，主要研究方向為物聯(lián)網(wǎng)、移動互聯(lián)網(wǎng)構(gòu)建；游貴榮(1974—)，男，福建省龍巖市人，福建商學院副教授，主要研究方向為智能信息處理。

TP212.9； TP391

A