基于動(dòng)態(tài)質(zhì)心迭代與偏差修正的室內(nèi)定位方法①

蘇國(guó)棟,徐世武,蔡碧麗

1(福建師范大學(xué)福清分校 電子與信息工程學(xué)院,福清 350300)

2(福建師范大學(xué) 協(xié)和學(xué)院 信息技術(shù)系,福州 350117)

1 引言

隨著計(jì)算科學(xué)技術(shù)的不斷發(fā)展,無(wú)線(xiàn)通信技術(shù)深度滲透,越來(lái)越多實(shí)際應(yīng)用需要知道物體的精確物理位置信息,并因此產(chǎn)生各式各樣的基于位置的服務(wù),由此定位問(wèn)題受到了相當(dāng)大的關(guān)注.毫無(wú)疑問(wèn),GPS定位技術(shù)已基本滿(mǎn)足了我們?cè)谑彝鈭?chǎng)景中對(duì)于位置服務(wù)的多樣化需求.然而,80%的人類(lèi)活動(dòng)行為是在室內(nèi)進(jìn)行的[1]; 同時(shí),服務(wù)機(jī)器人、新型物聯(lián)網(wǎng)終端設(shè)備等大量室內(nèi)定位需求也發(fā)生在室內(nèi); 而室內(nèi)場(chǎng)景受到各類(lèi)障礙物的遮擋,GPS信號(hào)快速衰減,定位能力嚴(yán)重受限制,無(wú)法滿(mǎn)足室內(nèi)場(chǎng)景中導(dǎo)航定位的需要[2].

其中,射頻識(shí)別(RFID)以非接觸、非視距、低成本等優(yōu)點(diǎn),成為熱門(mén)技術(shù).尤其,以倪明選、劉云浩等提出的非測(cè)距算法LANDMARC[3]定位技術(shù)較為典型.它通過(guò)引入?yún)⒖紭?biāo)簽,統(tǒng)計(jì)分析目標(biāo)標(biāo)簽、參考標(biāo)簽以及閱讀器間的接收信號(hào)強(qiáng)度(RSS),利用k近鄰法估計(jì)坐標(biāo)位置,節(jié)約成本.針對(duì)算法存在的問(wèn)題,文獻(xiàn)[4]通過(guò)LANDMARC定位算法測(cè)得目標(biāo)標(biāo)簽的理論坐標(biāo),并利用三角測(cè)定法對(duì)N個(gè)已知參考標(biāo)簽重定位且獲得理論坐標(biāo),進(jìn)而求出N個(gè)坐標(biāo)位置得平均誤差,從而修正目標(biāo)坐標(biāo),但該誤差修正無(wú)法準(zhǔn)確反映實(shí)際目標(biāo)的位置偏差,定位精度較為有限; VIRE[5]算法考慮到LANDMARC定位精度受參考標(biāo)簽密集度影響較大,從而引入虛擬參考標(biāo)簽,細(xì)化實(shí)際參考標(biāo)簽區(qū)域內(nèi)網(wǎng)格,把它當(dāng)作實(shí)際參考標(biāo)簽使用,參與k近鄰法選擇,提高定位精度,但是存在虛擬參考標(biāo)簽RSS值計(jì)算與實(shí)際偏差較大; 文獻(xiàn)[6]提出了一種基于貝葉斯概率和LANDMARC相結(jié)合的室內(nèi)定位算法,利用高斯濾波器可以過(guò)濾一些異常的RSS值,降低多徑和環(huán)境干擾引起的位置波動(dòng)和誤差,減少定位誤差.文獻(xiàn)[7]提出了一種改進(jìn)的三維LANDMARC室內(nèi)定位算法,引入數(shù)據(jù)融合算法和自適應(yīng)算法,提高LANDMARC算法的定位精度和適應(yīng)性.

上述方法從不同角度去改進(jìn)LANDMARC定位精度,但存在近鄰成員更新替代機(jī)制引起定位精度不高等問(wèn)題.本文提出了以最小關(guān)聯(lián)度為準(zhǔn)則,通過(guò)計(jì)算該近鄰區(qū)域的質(zhì)心作為下一個(gè)參考標(biāo)簽依次迭代近鄰成員,直至與目標(biāo)標(biāo)簽的關(guān)聯(lián)度低于閾值,從而估計(jì)目標(biāo)標(biāo)簽的坐標(biāo),實(shí)現(xiàn)預(yù)定位; 通過(guò)實(shí)施k近鄰成員重定位并引入修正系數(shù),對(duì)預(yù)定位坐標(biāo)進(jìn)行偏差修正.

2 LANDMARC算法簡(jiǎn)介

LANDMARC算法的核心思想是通過(guò)利用引入?yún)⒖紭?biāo)簽替代部署閱讀器,借助閱讀器對(duì)參考標(biāo)簽和目標(biāo)標(biāo)簽的接收信號(hào)強(qiáng)度感知并對(duì)比.原則上,實(shí)際位置越接近目標(biāo)標(biāo)簽的參考標(biāo)簽,其在閱讀器上的感知應(yīng)該與目標(biāo)標(biāo)簽更為相似.故此,找出它們之間的關(guān)聯(lián)度,并借助已知坐標(biāo)的參考標(biāo)簽,從而估計(jì)目標(biāo)標(biāo)簽的坐標(biāo).

其算法通過(guò)計(jì)算,對(duì)于每個(gè)目標(biāo)標(biāo)簽均選取k個(gè)關(guān)聯(lián)度值最小的參考標(biāo)簽作為k近鄰成員.其中,關(guān)聯(lián)度值計(jì)算采用它們信號(hào)強(qiáng)度的均方差來(lái)表示:

其中,M、N和U分別是是閱讀器、參考標(biāo)簽和目標(biāo)標(biāo)簽的數(shù)目;Eij表示第i個(gè)目標(biāo)標(biāo)簽和第j個(gè)參考標(biāo)簽的關(guān)聯(lián)度;Sip表示第p個(gè)閱讀器獲得第i個(gè)目標(biāo)標(biāo)簽的RSS值;θip表示第p個(gè)閱讀器獲得第j個(gè)參考標(biāo)簽的RSS值.由此可得,關(guān)聯(lián)度矩陣[8]:

顯然,Eij越小,說(shuō)明目標(biāo)標(biāo)簽與參考標(biāo)簽的位置更接近.由此,對(duì)于每個(gè)目標(biāo)標(biāo)簽,從小至大選擇k個(gè)Eij值.

最后,依據(jù)權(quán)重質(zhì)心法[9]和參考標(biāo)簽的已知坐標(biāo),估計(jì)目標(biāo)標(biāo)簽的位置:

其中,Eij表示第i個(gè)目標(biāo)標(biāo)簽的第j個(gè)近鄰的位置的權(quán)重,其計(jì)算公式如下:

表示離目標(biāo)標(biāo)簽近的鄰居參考標(biāo)簽的權(quán)重理論上要大于離待定位目標(biāo)標(biāo)簽遠(yuǎn)的權(quán)重.

3 動(dòng)態(tài)質(zhì)心迭代與自偏差修正算法研究

3.1 動(dòng)態(tài)質(zhì)心迭代算法

盡管LANDMARC算法通過(guò)引入?yún)⒖紭?biāo)簽,提高了目標(biāo)標(biāo)簽的定位精度.但k近鄰成員的選擇機(jī)制是靜態(tài)的,既當(dāng)選取參考標(biāo)簽與目標(biāo)標(biāo)簽之間關(guān)聯(lián)度最接近的k個(gè)近鄰參考標(biāo)簽后,缺乏k近鄰成員的動(dòng)態(tài)迭代機(jī)制.在k值確定的情況下,若k近鄰成員中存在與目標(biāo)標(biāo)簽關(guān)聯(lián)度較低的標(biāo)簽,盡管通過(guò)弱化權(quán)重,但是對(duì)目標(biāo)標(biāo)簽位置估計(jì)的影響仍然存在,這是不利的.如果能夠動(dòng)態(tài)迭代k近鄰成員,將該關(guān)聯(lián)度低的參考標(biāo)簽剔除,引入關(guān)聯(lián)度高的標(biāo)簽,使得近鄰成員逐漸逼近目標(biāo)標(biāo)簽,就可以克服這個(gè)不利影響.因此,本文提出了以最小關(guān)聯(lián)度為準(zhǔn)則,即將當(dāng)前估計(jì)質(zhì)心納入近鄰成員,并按從小到大對(duì)其關(guān)聯(lián)度值進(jìn)行排序,剔除關(guān)聯(lián)度最大的近鄰成員,從而實(shí)現(xiàn)動(dòng)態(tài)質(zhì)心迭代k近鄰成員,直至與目標(biāo)標(biāo)簽的關(guān)聯(lián)度低于設(shè)定閾值,從而計(jì)算目標(biāo)標(biāo)簽的坐標(biāo).基本算法流程描述如下.

步驟1.通過(guò)LANDMARC算法,求出首批k近鄰參考標(biāo)簽,k近鄰參考標(biāo)簽與目標(biāo)標(biāo)簽i的最小關(guān)聯(lián)度矩陣Ei={Eij|i:當(dāng)前目標(biāo)標(biāo)簽序號(hào)，j=1，2，...，k};

步驟4.根據(jù)式(1)計(jì)算目標(biāo)標(biāo)簽i與該估計(jì)質(zhì)心位置的關(guān)聯(lián)度;

步驟6.結(jié)束.

3.2 自偏差修正算法

通過(guò)計(jì)算目標(biāo)標(biāo)簽近鄰區(qū)域的加權(quán)質(zhì)心,以最小關(guān)聯(lián)度為準(zhǔn)則,動(dòng)態(tài)迭代更新其k近鄰,實(shí)現(xiàn)對(duì)目標(biāo)標(biāo)簽的逼近,但其比較依賴(lài)于準(zhǔn)確的RSS值.在實(shí)際環(huán)境中,不可避免的存在電磁波的反射、折射、多徑效應(yīng)等現(xiàn)象.這些因素會(huì)導(dǎo)致不同區(qū)域或不同標(biāo)簽位置的信號(hào)衰落程度不同,因此閱讀器感知到參考標(biāo)簽和目標(biāo)標(biāo)簽的信號(hào)受到影響,接收信號(hào)強(qiáng)度值RSS發(fā)生偏差.而整個(gè)LANDMARC算法對(duì)于RSS值的依賴(lài)性高,若RSS偏差較大將導(dǎo)致較大的目標(biāo)標(biāo)簽定位誤差.為此,應(yīng)該適當(dāng)?shù)膶?duì)估計(jì)位置進(jìn)行偏差修正,從而盡可能的降低其對(duì)定位結(jié)果的影響.

為了改進(jìn)上述問(wèn)題,通過(guò)對(duì)已知真實(shí)位置的參考標(biāo)簽實(shí)施重定位,并將其定位差值反饋并修正待定位的目標(biāo)標(biāo)簽.具體的工作描述如下.

步驟1.通過(guò)上文提出的動(dòng)態(tài)質(zhì)心迭代算法估計(jì)目標(biāo)標(biāo)簽i的坐標(biāo),設(shè)為

步驟2.對(duì)目標(biāo)標(biāo)簽i的k個(gè)近鄰成員作為待定位目標(biāo)標(biāo),已知真實(shí)坐標(biāo)為并利用基于動(dòng)態(tài)質(zhì)心迭代的改進(jìn)型LANDMARC算法實(shí)施重定位,得到k個(gè)近鄰成員的估計(jì)坐標(biāo)

對(duì)于目標(biāo)標(biāo)簽i的近鄰區(qū)域內(nèi),對(duì)k近鄰成員的重定位,據(jù)已知真實(shí)坐標(biāo)和估計(jì)坐標(biāo)評(píng)估統(tǒng)計(jì)該區(qū)域內(nèi)標(biāo)簽的誤差量,進(jìn)行優(yōu)化擬合,得到該區(qū)域內(nèi)的修正系數(shù)同一區(qū)域內(nèi),該修正系數(shù)能夠較好的反映該區(qū)域內(nèi)的偏差以便補(bǔ)償.對(duì)此,我們以橫坐標(biāo)x為例:

對(duì)于k近鄰成員的坐標(biāo)估計(jì)總均偏差可描述為:

同理可得:

3.3 算法流程圖

在LANDMARC算法基礎(chǔ)上,通過(guò)引入動(dòng)態(tài)質(zhì)心迭代與自偏差修正算法相結(jié)合的算法提高定位準(zhǔn)確性和可靠性.其算法流程如圖1所示.首先,通過(guò)設(shè)定門(mén)限閾值,據(jù)此循環(huán)評(píng)估估計(jì)質(zhì)心坐標(biāo)與目標(biāo)標(biāo)簽的關(guān)聯(lián)度,實(shí)現(xiàn)了動(dòng)態(tài)更新目標(biāo)標(biāo)簽的k近鄰成員,使預(yù)定位坐標(biāo)逐漸逼近目標(biāo)標(biāo)簽,克服了靜態(tài)k近鄰選擇機(jī)制問(wèn)題,提高了定位精度和穩(wěn)定性.在此基礎(chǔ)上,計(jì)算環(huán)境修正系數(shù)并對(duì)預(yù)定位坐標(biāo)進(jìn)行偏差修正,解決了預(yù)定位坐標(biāo)受區(qū)域內(nèi)環(huán)境因素影響而產(chǎn)生誤差問(wèn)題,減少環(huán)境對(duì)定位結(jié)果的影響,提高了定位準(zhǔn)確性,使算法更具良好的環(huán)境適應(yīng)性和穩(wěn)定性.

圖1 動(dòng)態(tài)質(zhì)心迭代及偏差修正算法流程圖

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

4.1 仿真環(huán)境

為了更好地驗(yàn)證改進(jìn)算法的性能,使用Matlab R2014a對(duì)經(jīng)典LANDMARC算法及本文提出的改進(jìn)算法進(jìn)行定位性能仿真實(shí)驗(yàn).本次仿真實(shí)驗(yàn)采用的信道傳輸模型是對(duì)數(shù)距離路徑損耗模型,路徑損耗因子取值為2,參考距離取值為0.1 m.設(shè)定定位區(qū)域范圍為 8 m×8 m 的空間[10],并將坐標(biāo) (0,0)、(0,8)、(8,0)、(8,0)設(shè)置為閱讀器所在位置.同時(shí),在該區(qū)域內(nèi)部均勻部署16個(gè)參考標(biāo)簽,水平和垂直方向上相鄰參考標(biāo)簽的間距均為2 m,外層參考標(biāo)簽與區(qū)域邊界的距離為1 m;另外,在該區(qū)域內(nèi)設(shè)定了20個(gè)目標(biāo)標(biāo)簽,布局如圖2所示.并假設(shè)所有標(biāo)簽均在各閱讀器的覆蓋范圍之內(nèi).

4.2 結(jié)果分析

設(shè)定近鄰參考標(biāo)簽數(shù)k=4,并于仿真環(huán)境中對(duì)LANDMARC算法及改進(jìn)算法進(jìn)行仿真.定位結(jié)果如圖3和圖4所示.圖3為L(zhǎng)ANDMARC和質(zhì)心迭代改進(jìn)法定位結(jié)果比較; 圖4為L(zhǎng)ANDMARC質(zhì)心迭代及偏差修正法定位結(jié)果比較.

圖2 仿真布局圖

圖3 LANDMARC和質(zhì)心迭代改進(jìn)算法仿真結(jié)果圖

圖4 LANDMARC質(zhì)心迭代及偏差修正算法仿真結(jié)果圖

結(jié)果表明,本文提出的動(dòng)態(tài)質(zhì)心迭代改進(jìn)算法在定位精度上,相比于LANDMARC,整體上有明顯提高.換言之,以最小關(guān)聯(lián)度為準(zhǔn)則,通過(guò)計(jì)算該近鄰區(qū)域的質(zhì)心作為下一個(gè)參考標(biāo)簽依次迭代近鄰成員,直至與目標(biāo)標(biāo)簽的關(guān)聯(lián)度低于閾值的方法,使得對(duì)目標(biāo)標(biāo)簽的估計(jì)值越接近實(shí)際位置,從而實(shí)現(xiàn)定位精度提高.與此同時(shí),對(duì)于RSS固有偏差,采取的基于參考標(biāo)簽重定位與引入?yún)^(qū)域修正因子的誤差反饋相結(jié)合,對(duì)目標(biāo)標(biāo)簽定位進(jìn)行校正,進(jìn)一步有效提高了定位精度,效果更為明顯.但是,在邊界區(qū)域的定位精度盡管提高了,但差距仍較為明顯.

由圖5可知,基于動(dòng)態(tài)質(zhì)心迭代的改進(jìn)算法相比于LANDMARC,在各個(gè)目標(biāo)位置上均由較大提升.而對(duì)質(zhì)心迭代后的定位結(jié)果進(jìn)行適當(dāng)?shù)恼`差修正,定位精度定進(jìn)一步得到提高,誤差較小,更接近目標(biāo)標(biāo)簽.但在編號(hào)14、20上,改進(jìn)前后的誤差仍較大,發(fā)現(xiàn)這三個(gè)點(diǎn)處于較為邊緣區(qū)域位置,主要原因在于邊緣區(qū)域?yàn)椴渴鹣鄳?yīng)參考標(biāo)簽或提出針對(duì)的解決方法,這也是下一步需改進(jìn)的工作.

圖5 LANDMARC和改進(jìn)算法各目標(biāo)標(biāo)簽定位誤差直方圖

為了進(jìn)一步比較LANDMARC和改進(jìn)算法的性能,表1列出了若干個(gè)目標(biāo)標(biāo)簽的定位結(jié)果數(shù)據(jù).表2列出了幾種算法的最大誤差、平均誤差.

表1和表2進(jìn)一步驗(yàn)證了本文提出的基于質(zhì)心迭代與偏差修正的方法有效的提高了定位精度,平均誤差為0.282 m.當(dāng)去除邊緣目標(biāo)標(biāo)簽后,本文提出的算法的最大誤差為0.488 m,平均誤差達(dá)0.153 m.

5 結(jié)論與展望

針對(duì)RFID環(huán)境下,傳統(tǒng)LANDMARC算法當(dāng)k近鄰成員選定后,沒(méi)有更新迭代逼近機(jī)制等問(wèn)題,從而影響了定位精度.本文提出了以最小關(guān)聯(lián)度為準(zhǔn)則,通過(guò)計(jì)算該近鄰區(qū)域的質(zhì)心作為下一個(gè)參考標(biāo)簽依次迭代近鄰成員,直至與目標(biāo)標(biāo)簽的關(guān)聯(lián)度低于閾值,從而估計(jì)目標(biāo)標(biāo)簽的坐標(biāo),實(shí)現(xiàn)預(yù)定位; 通過(guò)實(shí)施k近鄰成員重定位并引入修正系數(shù),對(duì)預(yù)定位坐標(biāo)進(jìn)行偏差修正.通過(guò)Matlab 仿真結(jié)果表明,基于動(dòng)態(tài)質(zhì)心迭代和偏差修正相結(jié)合的算法比LANDMARC具有更高的定位精度.當(dāng)然,也存在著諸如邊緣區(qū)域定位精度誤差仍較大等問(wèn)題,這也是下一步需要改進(jìn)的工作.

表1 定位結(jié)果數(shù)據(jù)比較

表2 定位算法性能比較