蘇國棟,徐世武,蔡碧麗

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

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

1 引言

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

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

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

2 LANDMARC算法簡介

LANDMARC算法的核心思想是通過利用引入?yún)⒖紭撕炋娲渴痖喿x器,借助閱讀器對參考標簽和目標標簽的接收信號強度感知并對比.原則上,實際位置越接近目標標簽的參考標簽,其在閱讀器上的感知應(yīng)該與目標標簽更為相似.故此,找出它們之間的關(guān)聯(lián)度,并借助已知坐標的參考標簽,從而估計目標標簽的坐標.

其算法通過計算,對于每個目標標簽均選取k個關(guān)聯(lián)度值最小的參考標簽作為k近鄰成員.其中,關(guān)聯(lián)度值計算采用它們信號強度的均方差來表示:

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

顯然,Eij越小,說明目標標簽與參考標簽的位置更接近.由此,對于每個目標標簽,從小至大選擇k個Eij值.

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

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

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

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

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

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

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

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

步驟6.結(jié)束.

3.2 自偏差修正算法

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

為了改進上述問題,通過對已知真實位置的參考標簽實施重定位,并將其定位差值反饋并修正待定位的目標標簽.具體的工作描述如下.

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

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

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

對于k近鄰成員的坐標估計總均偏差可描述為:

同理可得:

3.3 算法流程圖

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

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

4 仿真實驗與結(jié)果分析

4.1 仿真環(huán)境

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

4.2 結(jié)果分析

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

圖2 仿真布局圖

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

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

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

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

圖5 LANDMARC和改進算法各目標標簽定位誤差直方圖

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

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

5 結(jié)論與展望

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

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

表2 定位算法性能比較