王遠(yuǎn)哲，毛陸虹，劉輝，肖基誥

(1.天津大學(xué) 電子信息工程學(xué)院，天津 300072；2.香港大學(xué) 電機(jī)電子工程系，香港)

1 引言

室內(nèi)定位就是要在室內(nèi)環(huán)境下對(duì)目標(biāo)進(jìn)行追蹤定位，且定位的誤差在許可的范圍之內(nèi)。與室外環(huán)境不同，室內(nèi)環(huán)境通常更為復(fù)雜，各種干擾因素更多，現(xiàn)有的很多定位技術(shù)，如GPS(global positioning system)定位，紅外定位等，考慮到定位精度、成本、可行性等方面，并不適合于室內(nèi)定位[1,2]。射頻識(shí)別定位技術(shù)以其非接觸、非視距、高靈敏度和低成本的優(yōu)點(diǎn)，正在成為室內(nèi)定位系統(tǒng)的優(yōu)選技術(shù)，受到人們?cè)絹?lái)越多的關(guān)注[3～6]。

射頻識(shí)別定位技術(shù)使用的定位依據(jù)包括入射信號(hào)的強(qiáng)度值、角度值和時(shí)間差等。GPS系統(tǒng)就是使用時(shí)間差進(jìn)行定位[7]，但是這種方法成本較高，主要是用在大范圍的定位，并不適合于空間狹小環(huán)境復(fù)雜的室內(nèi)定位。使用信號(hào)角度值進(jìn)行定位的原理是通過(guò)相鄰天線接收到的信號(hào)的相位差計(jì)算信號(hào)的入射角度。但是這種方法需要天線陣列，硬件開(kāi)銷較大?；诮邮招盘?hào)的強(qiáng)度值的定位方法需要閱讀器提供接收到的射頻標(biāo)簽信號(hào)的強(qiáng)度值作為定位依據(jù)。這種方法具有低功率和低成本的優(yōu)點(diǎn)，使得它已較多用于實(shí)際的定位系統(tǒng)中，如LANDMARC[3]、RADAR[8]、SpotOn[9]等?；趫?chǎng)強(qiáng)值進(jìn)行定位的現(xiàn)有的算法主要包括解析算法[10]、估值算法[11,12]、基于參考標(biāo)簽的最近鄰居算法[3]幾大類。

最近鄰居定位算法在 LANDMARC的定位系統(tǒng)中被采用。它在環(huán)境中按照一定的方式布置一定數(shù)目位置已知的參考標(biāo)簽作為定位的基準(zhǔn)，通過(guò)比較閱讀器測(cè)得目標(biāo)標(biāo)簽場(chǎng)強(qiáng)值與閱讀器測(cè)得參考標(biāo)簽場(chǎng)強(qiáng)值的相對(duì)大小來(lái)對(duì)目標(biāo)標(biāo)簽進(jìn)行定位。這種算法有以下幾個(gè)優(yōu)點(diǎn)。首先，這種算法采用多標(biāo)簽代替多閱讀器，可以降低系統(tǒng)成本。其次，參考標(biāo)簽和目標(biāo)標(biāo)簽處于同樣的環(huán)境之中，可以有效地抵消環(huán)境因素的影響。第三，這種算法對(duì)于非視距的定位效果較好。

但是，LANDMARC系統(tǒng)提供的精度有限。LANDMARC系統(tǒng)使用的閱讀器能夠提供信號(hào)強(qiáng)度的8個(gè)等級(jí)，而本文中使用的閱讀器能夠提供256個(gè)等級(jí)，硬件條件的升級(jí)給優(yōu)化算法提供了可能。同時(shí)，由于RFID標(biāo)簽讀取不穩(wěn)定的影響，經(jīng)常會(huì)出現(xiàn)某些閱讀器讀取某些標(biāo)簽的場(chǎng)強(qiáng)值失敗或者出錯(cuò)的情況。由于一個(gè)參考標(biāo)簽要同時(shí)被幾個(gè)閱讀器讀取，而只要有其中一個(gè)閱讀器的讀取失敗就會(huì)對(duì)這個(gè)參考標(biāo)簽參與定位造成很大影響，導(dǎo)致很多參考標(biāo)簽喪失了參考價(jià)值。另外，由于各個(gè)閱讀器的增益不同或者離目標(biāo)標(biāo)簽的距離不同，造成在目標(biāo)標(biāo)簽處的各向異性，即各個(gè)方向上同樣的距離反映出來(lái)的場(chǎng)強(qiáng)差不同，影響了最近鄰標(biāo)簽的選取和權(quán)值的設(shè)定。在這些惡劣的情況下，現(xiàn)有的最近鄰居算法定位精度不高，最大誤差比較大。為此，提出了動(dòng)態(tài)k值設(shè)定的方法，參考標(biāo)簽可信度的概念，最近鄰標(biāo)簽偏差校正算法并采用了目標(biāo)標(biāo)簽歷史軌跡算法。

基于Intel的R1000射頻識(shí)別開(kāi)發(fā)平臺(tái)，用多天線的時(shí)分復(fù)用代替多閱讀器，搭建了一個(gè)定位系統(tǒng)，并且開(kāi)發(fā)了相應(yīng)的界面軟件。通過(guò)實(shí)測(cè)，改進(jìn)后定位算法提高了定位精度和惡劣環(huán)境下的適應(yīng)能力。

2 最近鄰居定位算法介紹[3,13,14]

下面簡(jiǎn)要介紹最近鄰算法的具體實(shí)現(xiàn)。閱讀器和標(biāo)簽的排列方式如圖1所示。現(xiàn)假設(shè)共有m個(gè)閱讀器和n個(gè)參考標(biāo)簽以及u個(gè)目標(biāo)標(biāo)簽。m個(gè)閱讀器分別讀出n個(gè)參考標(biāo)簽和u個(gè)目標(biāo)標(biāo)簽發(fā)送給閱讀器的信號(hào)場(chǎng)強(qiáng)值，在LANDMARC系統(tǒng)中此場(chǎng)強(qiáng)值是1～8總共8個(gè)等級(jí)。把上述場(chǎng)強(qiáng)值寫(xiě)成向量的形式，記目標(biāo)標(biāo)簽的場(chǎng)強(qiáng)值向量為-→=(T1,T2,…,Tm)，其中T代表第j個(gè)閱讀器讀到目標(biāo)---標(biāo)-→簽的場(chǎng)強(qiáng)值；參考標(biāo)簽的場(chǎng)強(qiáng)值向量為Rj(i)=(R1(i),R2(i) ,…,Rm(i ))，其中 Rj(i)代表第j個(gè)閱讀器讀到參考標(biāo)簽i的場(chǎng)強(qiáng)值。為了判斷參考標(biāo)簽與目標(biāo)標(biāo)簽的近鄰程度，對(duì)于每個(gè)目標(biāo)標(biāo)簽p，p∈[1,u]，定義表征第i個(gè)參考標(biāo)簽與目標(biāo)標(biāo)簽的距離大小，Ei越小表示距離越近，i∈[1,n]。

通過(guò)比較Ei值的大小，選出k個(gè)離目標(biāo)標(biāo)簽最近的參考標(biāo)簽稱為最近鄰標(biāo)簽，其標(biāo)簽序號(hào)組成集合Κ。其中k值的大小可以根據(jù)不同的應(yīng)用環(huán)境人為設(shè)定。定義這k個(gè)最近鄰標(biāo)簽的權(quán)值為

這樣，目標(biāo)標(biāo)簽的位置可以由式(2)得出

LANDMARC系統(tǒng)使用16個(gè)參考標(biāo)簽，4個(gè)閱讀器（閱讀器可以得到信號(hào)強(qiáng)度的 8個(gè)等級(jí)值），參考標(biāo)簽之間距離約為 1～2m。在這種情況下，得到的定位誤差最大約為2m，平均誤差約為1m。

圖1 定位系統(tǒng)標(biāo)簽擺放示意圖

3 參考標(biāo)簽算法不同參數(shù)設(shè)定對(duì)于定位精度的影響

3.1 參考標(biāo)簽分布和最近鄰數(shù)目 k值的設(shè)定對(duì)于定位精度的影響

目標(biāo)標(biāo)簽位置的確定是根據(jù)一定數(shù)目的（k個(gè)）參考標(biāo)簽的位置加權(quán)得到的，故而參考標(biāo)簽的排列方式和最近鄰數(shù)目 k值的設(shè)定會(huì)對(duì)定位的結(jié)果產(chǎn)生極大的影響。在實(shí)際的應(yīng)用系統(tǒng)中，根據(jù)具體的定位需要，參考標(biāo)簽的分布和k值的設(shè)定可能大不相同。比如在空曠的環(huán)境中對(duì)物體進(jìn)行定位，一般采取網(wǎng)格式的參考標(biāo)簽排列方法。在生產(chǎn)流水線或者運(yùn)輸路線中對(duì)于貨物進(jìn)行定位，貨物一般來(lái)說(shuō)不會(huì)脫離流水線或者道路，故而只需要進(jìn)行一維的定位，參考標(biāo)簽一般沿著流水線或者道路線形排列，而k值一般取2（或者 3）。在倉(cāng)庫(kù)中對(duì)貨物進(jìn)行定位，貨物一般會(huì)位于某一個(gè)貨架上，故可以在每一個(gè)貨架的四周布置 4個(gè)參考標(biāo)簽，k值設(shè)置為4，就可以通過(guò)定位算法找到貨物所在的具體貨架，如圖2所示。

圖2 倉(cāng)庫(kù)內(nèi)參考標(biāo)簽擺放示意圖

3.2 權(quán)值定義方法對(duì)于定位精度的影響

最近鄰標(biāo)簽權(quán)值的確定有很多種方法，但是必須滿足2個(gè)基本的條件：1) 離目標(biāo)標(biāo)簽越近的參考標(biāo)簽（即E值越?。?，權(quán)值W必須越大。即W(E)必須是單調(diào)的減函數(shù)；2) 權(quán)值之和必須為1，即 W1+W2+…Wk=1。（注W的下標(biāo)對(duì)第2節(jié)中w的下標(biāo)進(jìn)行了重排。）除了最近鄰居算法中的二階權(quán)值的設(shè)定方法，還有一階權(quán)值和對(duì)數(shù)權(quán)值的設(shè)定方法，如下所示。

為了考察不同權(quán)值設(shè)定方法對(duì)結(jié)果的影響，定義單一標(biāo)簽依賴程度 ξ=(Wi)max，表征定位結(jié)果與距目標(biāo)標(biāo)簽最近的一個(gè)參考標(biāo)簽的接近程度。ξ越大代表距目標(biāo)最近的標(biāo)簽的權(quán)重越大，定位結(jié)果也就越接近這個(gè)標(biāo)簽。

下面用一個(gè)具體的例子分析3種權(quán)值設(shè)定方法的單一標(biāo)簽依賴程度。假設(shè)K=5，5個(gè)最近鄰標(biāo)簽的E值分別為其中x＜40，故剩下的4個(gè)標(biāo)簽E＞40。在x的不同取值下分別使用3種權(quán)值設(shè)定方法計(jì)算W值，得到3個(gè)不同的ξ，如圖3所示。由圖3可見(jiàn)，二階權(quán)值設(shè)定方法的單一標(biāo)簽依賴程度最高，一階權(quán)值次之，對(duì)數(shù)權(quán)值最低。在實(shí)際應(yīng)用中要根據(jù)不同的環(huán)境選擇不同的方法。如果信號(hào)強(qiáng)度隨著距離的增加衰減嚴(yán)重的話，一般采用單一標(biāo)簽依賴程度低的權(quán)值設(shè)定方法，否則目標(biāo)會(huì)完全定位到最近的一個(gè)參考標(biāo)簽的位置；如果信號(hào)強(qiáng)度隨著距離的增加衰減較小的話，一般可以采用單一標(biāo)簽依賴程度高的權(quán)值設(shè)定方法，否則目標(biāo)會(huì)完全定位在幾個(gè)最近鄰標(biāo)簽的幾何中心。

圖3 不同的權(quán)值設(shè)定方法單一標(biāo)簽依賴程度曲線

4 基于最近鄰居提出的新型定位算法

4.1 目標(biāo)標(biāo)簽歷史軌跡算法

該改進(jìn)來(lái)源于文獻(xiàn)[14]，由于在實(shí)際測(cè)試中發(fā)現(xiàn)加入該改進(jìn)對(duì)精度有一定作用，故予以采用。為了敘述的完整性，在這里進(jìn)行了簡(jiǎn)要的描述。詳細(xì)內(nèi)容可以參考文獻(xiàn)[14]。

由于目標(biāo)標(biāo)簽的運(yùn)動(dòng)速度有限，在一段很小的時(shí)間內(nèi)目標(biāo)標(biāo)簽的位置不可能發(fā)生很大的變化。因此，可以利用目標(biāo)標(biāo)簽的歷史位置加權(quán)估計(jì)當(dāng)前位置，這樣做的好處是可以減小隨機(jī)誤差和隨機(jī)電磁干擾對(duì)定位精度的影響。

設(shè)要獲取當(dāng)前時(shí)刻目標(biāo)標(biāo)簽的位置。在t0時(shí)刻和t0時(shí)刻之前與t0接近的s個(gè)時(shí)刻 t1,t2,t3,…,ts，分別進(jìn)行測(cè)量，每一次的測(cè)量均用上面所述的算法得到一個(gè)估計(jì)值。設(shè)當(dāng)前時(shí)刻估計(jì)值為(x0,y0)，設(shè)第i次歷史測(cè)量得到的估計(jì)值為(xi,yi)，i=1,2,…,s，考慮歷史軌跡后得到的估計(jì)值為(x,y)?？疾鞖埐罴訖?quán)函數(shù)[11]：

當(dāng)Q值取得極小值的時(shí)候，可以得到最佳的估計(jì)位置(x,y)。為此，上式對(duì)x和y分別求偏導(dǎo)數(shù)，令偏導(dǎo)數(shù)等于0，可以解出(x,y)值如下：

其中wi值如下，表示每個(gè)歷史位置的權(quán)值：

由wi的表達(dá)式可見(jiàn)，如果歷史位置(xi, yi)與當(dāng)前位置(x0,y0)之間距離越近，則wi越大，它在估計(jì)值中的權(quán)重也就越大。實(shí)踐表明，在進(jìn)行上述修改之后，算法能夠更好地克服隨機(jī)干擾的影響，準(zhǔn)確度和穩(wěn)定性得到了提高。

4.2 動(dòng)態(tài)k值設(shè)定方法

在實(shí)際的測(cè)量中經(jīng)常會(huì)出現(xiàn)某些參考標(biāo)簽的場(chǎng)強(qiáng)向量有一個(gè)或幾個(gè)分量讀不到的情況，如果這些標(biāo)簽正好離目標(biāo)標(biāo)簽最近，就可能導(dǎo)致目標(biāo)標(biāo)簽最近鄰標(biāo)簽選擇的極大偏差，從而導(dǎo)致定位結(jié)果偏離。例如在網(wǎng)格形的參考標(biāo)簽排列方式中，如果目標(biāo)標(biāo)簽周圍的4個(gè)標(biāo)簽同側(cè)2個(gè)有場(chǎng)強(qiáng)沒(méi)有讀到，則最近鄰標(biāo)簽很可能選成目標(biāo)標(biāo)簽另一側(cè)的網(wǎng)格4角的4個(gè)標(biāo)簽，導(dǎo)致定位結(jié)果誤差很大。為了避免這種狀況發(fā)生，可以增大k值的設(shè)定，使更多的最近鄰標(biāo)簽參與到目標(biāo)標(biāo)簽定位的加權(quán)中去，以減小定位誤差。

在定位程序的初始化時(shí)，可以先給k設(shè)一個(gè)初始值k0。在硬件操控程序中，對(duì)于讀不到的場(chǎng)強(qiáng)值分量，可以將其人為的設(shè)定成一個(gè)固定的場(chǎng)強(qiáng)值（一般可以設(shè)成一個(gè)負(fù)的大值）。在定位程序中，檢測(cè)出現(xiàn)了人為設(shè)定的場(chǎng)強(qiáng)值的標(biāo)簽的個(gè)數(shù)，即場(chǎng)強(qiáng)向量中有某一或幾個(gè)分量沒(méi)讀到的標(biāo)簽的個(gè)數(shù)。如果檢測(cè)到c個(gè)，則修正k值為 k=k0+c 。

4.3 參考標(biāo)簽可信度的概念

在實(shí)際測(cè)量過(guò)程中發(fā)現(xiàn)，在閱讀器讀取每個(gè)標(biāo)簽的場(chǎng)強(qiáng)時(shí)，總會(huì)出現(xiàn)個(gè)別場(chǎng)強(qiáng)值出錯(cuò)（過(guò)大或過(guò)小），或者甚至讀不到的情況（讀不到時(shí)一般由程序設(shè)置為負(fù)的一個(gè)大值）。而只要有一個(gè)參考標(biāo)簽的場(chǎng)強(qiáng)值偏離特別大，而偏離值恰好與目標(biāo)標(biāo)簽場(chǎng)強(qiáng)值接近的話，這個(gè)標(biāo)簽就會(huì)被選為最近鄰標(biāo)簽從而使定位出現(xiàn)極大的偏差。為了防止這種誤差，定義了參考標(biāo)簽的可信度的概念。一般來(lái)說(shuō)，一個(gè)參考標(biāo)簽在某個(gè)閱讀器上的場(chǎng)強(qiáng)值會(huì)在它周圍的4標(biāo)簽在這個(gè)閱讀器上場(chǎng)強(qiáng)值之間。假設(shè)共有m個(gè)閱讀器，則某個(gè)參考標(biāo)簽在各個(gè)閱讀器上會(huì)有m個(gè)場(chǎng)強(qiáng)值，它上下左右4個(gè)標(biāo)簽在各個(gè)閱讀器上也各有m個(gè)值。設(shè)x(j)為某個(gè)參考標(biāo)簽在第j個(gè)閱讀器上的場(chǎng)強(qiáng)值，min(j)為在第j個(gè)閱讀器上此標(biāo)簽上下左右4個(gè)標(biāo)簽場(chǎng)強(qiáng)值的最小值，max(j)為最大值(j=1,2,…,m）。設(shè)使 x(j)∈[min(j),max(j)]的j值共有M個(gè)?，F(xiàn)分段定義可信度Y如下：

Y在0到1之間取值，越大表示可信度越高。如果對(duì)于任意 j有 min(j)＜x(j)＜max(j)則 Y值取 1。在選擇最近鄰標(biāo)簽時(shí)，通過(guò)比較選擇 的值最小的k個(gè)標(biāo)簽。同時(shí)最近鄰標(biāo)簽的權(quán)值修正為

在實(shí)際的應(yīng)用中，由于各種原因可能導(dǎo)致某些參考標(biāo)簽失效，或者位置偏離了設(shè)定的位置（尤其是在野外），或者讀取時(shí)失敗或者出錯(cuò)的情況。進(jìn)行這種改進(jìn)之后，能有效地防止個(gè)別參考標(biāo)簽讀取出錯(cuò)對(duì)于結(jié)果的影響。

4.4 最近鄰標(biāo)簽偏差的自校正

閱讀器讀到的標(biāo)簽的場(chǎng)強(qiáng)值隨距離的變化關(guān)系并不是線性的，而是一條類似于負(fù)指數(shù)的曲線。在距離近的時(shí)候，場(chǎng)強(qiáng)值隨距離的變化比較快（場(chǎng)強(qiáng)對(duì)距離導(dǎo)數(shù)的絕對(duì)值大）；在距離遠(yuǎn)的時(shí)候，場(chǎng)強(qiáng)值隨距離的變化比較慢（場(chǎng)強(qiáng)對(duì)距離導(dǎo)數(shù)的絕對(duì)值?。?。這樣，如果目標(biāo)標(biāo)簽的位置離某一個(gè)閱讀器較近而離其他的閱讀器較遠(yuǎn)時(shí)，近處的閱讀器讀到的標(biāo)簽場(chǎng)強(qiáng)值變化陡峭，導(dǎo)致這個(gè)閱讀器的方向上的距離差L對(duì)于E值的貢獻(xiàn)大于其他3個(gè)方向上同樣的距離差L對(duì)于E值的貢獻(xiàn)。這樣會(huì)導(dǎo)致最近鄰標(biāo)簽選取的偏差和權(quán)值的偏差，對(duì)定位結(jié)果造成影響?；蛘哂捎诟鱾€(gè)方向上閱讀器的增益不同，導(dǎo)致各個(gè)方向上同樣距離讀到的場(chǎng)強(qiáng)值不同，也會(huì)導(dǎo)致各向異性，對(duì)定位結(jié)果造成影響。

為了解決這種各向異性導(dǎo)致的定位偏差，可以用最近鄰標(biāo)簽的定位偏差作為校正。具體操作如下。首先采用 4.1節(jié)中的方法選擇出 k個(gè)最近鄰標(biāo)簽，然后分別把這k個(gè)參考標(biāo)簽作為目標(biāo)標(biāo)簽，把剩下的n-1個(gè)參考標(biāo)簽作為參考標(biāo)簽，使用 4.1節(jié)中的方法進(jìn)行計(jì)算，得到每一個(gè)最近鄰參考標(biāo)簽的估計(jì)位置，記為(xi′,yi′)，i=1,2,…,k。然后把這k個(gè)最近鄰標(biāo)簽的估計(jì)位置和它們的實(shí)際位置作比較，得到修正值：

最后使用這個(gè)修正值對(duì)目標(biāo)標(biāo)簽的估計(jì)位置進(jìn)行校正，得到：

4.5 算法的最終流程

綜合以上幾點(diǎn)改進(jìn)，算法的最終流程如圖4所示。

下面是對(duì)算法流程的詳細(xì)說(shuō)明。

1) 設(shè)置各個(gè)參數(shù)的值，如閱讀器數(shù)目m，參考標(biāo)簽數(shù)目n，最近鄰標(biāo)簽數(shù)目k，歷史值讀取次數(shù)s；

2) 各個(gè)閱讀器讀取各個(gè)標(biāo)簽的場(chǎng)強(qiáng)值；

3) 檢測(cè)2中讀到的場(chǎng)強(qiáng)值中設(shè)定值的數(shù)量（即讀取失敗的場(chǎng)強(qiáng)值的數(shù)量），修正k值；

4) 計(jì)算各個(gè)參考標(biāo)簽的E值；

5) 計(jì)算各個(gè)參考標(biāo)簽的可信度Y；

6) 根據(jù)E值和Y值選擇k個(gè)最近鄰標(biāo)簽；

7) 計(jì)算各個(gè)最近鄰標(biāo)簽的權(quán)值；

8) 最近鄰標(biāo)簽位置加權(quán)得到估計(jì)值；

9) 以每個(gè)最近鄰標(biāo)簽當(dāng)做目標(biāo)標(biāo)簽，其他n-1個(gè)參考標(biāo)簽作為參考標(biāo)簽，重復(fù)4)～8)的步驟，得到各個(gè)最近鄰標(biāo)簽位置估計(jì)值，并計(jì)算其偏差；

10) 用偏差值對(duì)目標(biāo)標(biāo)簽估計(jì)值進(jìn)行校正，得到新的估計(jì)值；

11) 重復(fù)2)～10)的步驟s+1次，最后一次的估計(jì)值為當(dāng)前值，前s次的估計(jì)值為歷史值；

12) 計(jì)算各個(gè)歷史位置的權(quán)值；

13) 加權(quán)得到最后的目標(biāo)標(biāo)簽位置估計(jì)值。

5 硬件系統(tǒng)和實(shí)際測(cè)試結(jié)果

基于Intel的R1000射頻識(shí)別開(kāi)發(fā)平臺(tái)，搭建了定位的硬件系統(tǒng)。硬件系統(tǒng)的主要構(gòu)件包括Intel R1000射頻識(shí)別開(kāi)發(fā)平臺(tái)、PC機(jī)、遠(yuǎn)距離閱讀器天線、XCTF-8030a型無(wú)源RFID標(biāo)簽等。該系統(tǒng)可以讀出0～255共256個(gè)等級(jí)的信號(hào)強(qiáng)度值（遠(yuǎn)大于LANDMARC系統(tǒng)的8個(gè)等級(jí)[3]），使用3對(duì)天線的分時(shí)復(fù)用代替多閱讀器，用PC機(jī)作為主機(jī)。還根據(jù)上面提出的算法開(kāi)發(fā)了界面軟件，搭建了軟硬件協(xié)同的定位系統(tǒng)。軟件的界面如圖5所示。

圖5 定位界面軟件

分別在空曠的大廳和開(kāi)放實(shí)驗(yàn)室內(nèi)搭建了定位系統(tǒng)，參考標(biāo)簽按照界面上的排列方式擺放，網(wǎng)格的邊長(zhǎng)為0.7m。定義測(cè)量誤差[3]為其中(x,y)是目標(biāo)標(biāo)簽的估計(jì)，(x?,y?)表示目標(biāo)標(biāo)簽的實(shí)際位置。使用統(tǒng)計(jì)學(xué)概率分布函數(shù)的方法，e為實(shí)際測(cè)量中的定位誤差（單位為 m），L為概率分布函數(shù)的橫坐標(biāo)（單位也是m），定義測(cè)量誤差e小于橫坐標(biāo) L的測(cè)量結(jié)果出現(xiàn)的次數(shù)占總測(cè)量次數(shù)的百分比為P(e＜L)，如P(e＜0.5)即為所有測(cè)量誤差結(jié)果中，小于0.5m的e出現(xiàn)的次數(shù)占總測(cè)量次數(shù)的百分比。在連續(xù)10h內(nèi)進(jìn)行了大量的測(cè)量，根據(jù)測(cè)量結(jié)果繪制出 P(e＜L)的曲線。

為了研究各種參數(shù)的設(shè)置對(duì)于定位精度的影響，使用本文提出的算法，在其他條件相同的情況下，分別改變k0值設(shè)定和權(quán)值設(shè)定方法，對(duì)結(jié)果進(jìn)行分析。在空曠大廳中，采用本文提出的算法，權(quán)值設(shè)定為二階權(quán)值，分別令k0等于3、4、5進(jìn)行實(shí)驗(yàn)，得到的結(jié)果如圖6所示?？梢?jiàn)k0=4時(shí)定位效果最好，k0=5次之，k0=3較差。

圖6 不同k0值的設(shè)定對(duì)于定位結(jié)果的影響

圖7 不同的權(quán)值設(shè)定方法對(duì)于定位結(jié)果的影響

在空曠大廳中，采用本文提出的算法，k0設(shè)置為 4，分別采用一階、二階和對(duì)數(shù)的權(quán)值設(shè)定方法進(jìn)行實(shí)驗(yàn)，得到的結(jié)果如圖7所示。可見(jiàn)二階權(quán)值設(shè)定方法精度最好，一階權(quán)值在誤差較小的時(shí)候定位精度高于二階權(quán)值，但是當(dāng)環(huán)境惡劣時(shí)定位精度下降嚴(yán)重，最大定位誤差大于一階權(quán)值。對(duì)數(shù)權(quán)值定位精度較差。在最理想的情況下（k0設(shè)置為4，權(quán)值取二階權(quán)值），分別在開(kāi)放實(shí)驗(yàn)室和空曠大廳內(nèi)進(jìn)行實(shí)驗(yàn)，結(jié)果分別用原有的最近鄰居算法和本文提出的改進(jìn)后的算法進(jìn)行計(jì)算。其中原有的最近鄰居定位算法的測(cè)量也是在上面提出的 256等級(jí)的硬件系統(tǒng)上進(jìn)行的，因此排除了硬件不同的影響，原算法和改進(jìn)算法得到的不同結(jié)果均是由于算法改進(jìn)而非硬件升級(jí)造成的。得到的結(jié)果如圖8和圖9所示。由圖可見(jiàn)，在同樣的256等級(jí)的硬件平臺(tái)上，采用新提出的改進(jìn)算法比使用現(xiàn)有的最近鄰居算法定位精度明顯提高。不論是在空曠大廳還是在開(kāi)放實(shí)驗(yàn)室，均可看出2條曲線在L值較小的時(shí)候擬合較好，在L值比較大時(shí)有明顯分離。這表明在比較理想的測(cè)試結(jié)果中，2種算法定位結(jié)果的偏差不大。在測(cè)試結(jié)果情況比較惡劣的情況下，本文提出的算法的精確度顯著高于最近鄰居算法，說(shuō)明本文提出的算法在惡劣環(huán)境條件下會(huì)顯示出更精確與穩(wěn)定的定位結(jié)果。

圖8 空曠大廳內(nèi)定位誤差分布曲線

圖9 開(kāi)放實(shí)驗(yàn)室內(nèi)定位誤差分布曲線

經(jīng)過(guò)計(jì)算，在同樣的256等級(jí)的硬件平臺(tái)上，在空曠大廳內(nèi)，使用最近鄰居算法定位的平均誤差是0.404 6m，最大誤差是0.72m；使用新型改進(jìn)算法定位的平均誤差是0.331 0m，最大誤差是0.60m。在開(kāi)放實(shí)驗(yàn)室內(nèi)，使用最近鄰居算法定位的平均誤差是0.441 6m，最大誤差是0.81m；使用新型算法平均誤差是0.379 2m，最大誤差是0.69m。

6 結(jié)束語(yǔ)

本文基于最近鄰居定位算法，提出了新型的改進(jìn)算法。基于R1000射頻識(shí)別開(kāi)發(fā)平臺(tái)，使用多天線分時(shí)復(fù)用代替多閱讀器搭建了定位的硬件系統(tǒng)，并且開(kāi)發(fā)了定位的軟件界面。本文的測(cè)量都是在人員走動(dòng)、物品擺放、電磁干擾等情況都未加限制的情況下進(jìn)行的，貼近實(shí)際的應(yīng)用環(huán)境。通過(guò)實(shí)際測(cè)量，本文提出的改進(jìn)算法在惡劣環(huán)境下的適應(yīng)能力和穩(wěn)定度顯著提高，定位的最大誤差減小，且平均精度比最近鄰居算法有了20%左右的提高。

[1] YAMASAKI R,OGINO A,TAMAKI T.TDOA: location system for IEEE 802.11b WLAN[A].Wireless Communications and Networking Conference,2005 IEEE[C].New Orleans,LA,USA,2005.2338-2343.

[2] HEADLEY W,DASUVA C,BUEHRER R M.Indoor location positioning of non-active objects using ultra-wideband radios[A].Radio and Wireless Symposium,2007 IEEE[C].Long Beach,CA,USA,2007.105-108.

[3] NI L,LIU Y,LAU Y,PATIL A.LANDMARC: indoor location sensing using active RFID[A].Proceedings of the First IEEE International Conference on Pervasive Computing and Communications(Per-Com2003)[C].Dallas,Texas,USA,March 2003.407-415.

[4] SHIRAISHI T,KOMURO N,UEDA H.Indoor location estimation technique using UHF band RFID[A].Information Networking,2008 International Conference on[C].Busan,Korea,2008.1-5.

[5] SHIH S,HSIEH K,CHEN P.An improvement approach of indoor location sensing using active RFID[A].Innovative Computing,Information and Control,2006 First International Conference on[C].Beijing,China,2006.453-456.

[6] DAI H,SU D.Indoor location system using RFID and ultrasonic sensors[A].Personal,Indoor and Mobile Radio Communications,2006 IEEE 17th International Symposium on[C].Kunming,China,2006.1179-1181.

[7] GERTEN G.Protecting the global positioning system[J].Aerospace and Electronic Systems Magazine,IEEE,2005,20(11):3-8.

[8] BAHL P,PADMANABHAN V.RADAR: an in-building rf-based user location and tracking system[A].Nineteenth Annual Joint Conference of the IEEE Computer and Communications Societies,Proceedings IEEE[C].TelAviv,Israel,2000.775-784.

[9] HIGHTOWER J,WANT R,BORRIELLO G.SpotON: An Indoor 3D Location Sensing Technology Based on RF Signal Strength[R].Seattle,WA: UW CSE,2000.

[10] KRISHNAKUMAR A,KRISHNAN P.The theory and practice of signal strength-based location estimation[A].Collaborative Computing:Networking,Applications and Worksharing,2005 International Conference on[C].San Jose,CA,USA,2005.10-19.

[11] NI W,SHEN G,LENG X,GUI L.An indoor location algorithm based on taylor series expansion and maximum likelihood estimation[A].Personal,Indoor and Mobile Radio Communications,2006 IEEE 17th International Symposium on[C].Helsinki,2006.1-4.

[12] 熊瑾煜,王巍,朱中梁.基于泰勒級(jí)數(shù)展開(kāi)的蜂窩 TDOA 定位算法[J].通信學(xué)報(bào),2005,25(4):144-150.XIONG J,WANG W,ZHU Z.A new TDOA algorithm based-on taylor series expansion in cellular networks[J].Journal on Communications,2005,25(4): 144-150.

[13] BAHL P,PADMANABHAN V,BALACHANDRAN A.Enhancements to the RADAR User Location and Tracking System[R].Microsoft Research Technical Report,2009.

[14] 孫瑜,范平志.射頻識(shí)別技術(shù)及其在室內(nèi)定位中的應(yīng)用[J].計(jì)算機(jī)應(yīng)用,2005，(5):1205- 1208.SUN Y,FAN Z P.RFID technology and its application in indoor positioning[J].Journal of Computer Applications,2005,(5):1205- 1208.