基于動態(tài)質心迭代與偏差修正的室內定位方法①

蘇國棟,徐世武,蔡碧麗

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

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

1 引言

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

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

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

2 LANDMARC算法簡介

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

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

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

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

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

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

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

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

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

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

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

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

步驟6.結束.

3.2 自偏差修正算法

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

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

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

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

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

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

同理可得:

3.3 算法流程圖

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

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

4 仿真實驗與結果分析

4.1 仿真環(huán)境

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

4.2 結果分析

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

圖2 仿真布局圖

圖3 LANDMARC和質心迭代改進算法仿真結果圖

圖4 LANDMARC質心迭代及偏差修正算法仿真結果圖

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

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

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

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

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

5 結論與展望

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

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

表2 定位算法性能比較