董永峰，周艷聰，孫陸楠，曹 瑩

（1.河北工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與軟件學(xué)院，天津300401；2.天津商業(yè)大學(xué) 信息工程學(xué)院，天津300134；3.河北金融學(xué)院 信息管理與工程系，河北 保定071051）

0 引 言

目前基于RFID （射頻識(shí)別）［1］的定位算法大多是二維的，關(guān)于三維室內(nèi)定位算法的研究還比較少。

SpotON 系統(tǒng)［2］是比較經(jīng)典的三維位置感知系統(tǒng)，SpotON 標(biāo)簽應(yīng)用接收到的無(wú)線電信號(hào)強(qiáng)度信息來(lái)估算標(biāo)簽間的距離，使用聚合算法對(duì)目標(biāo)標(biāo)簽進(jìn)行定位，然而，到現(xiàn)在為止還沒(méi)有一套完整的SpotON 系統(tǒng)可用。文獻(xiàn) ［3］提出了LANDMARC－3D 算法，主要是將最近鄰居算法拓展到三維，實(shí)現(xiàn)目標(biāo)標(biāo)簽的三維定位，該算法的定位誤差較大；文獻(xiàn) ［4］提出了包容性約束和排他性約束，然而該算法存在有些標(biāo)簽無(wú)法定位成功的問(wèn)題；文獻(xiàn) ［5］提出了基于空間分割的三維定位算法，通過(guò)選擇最鄰近參考標(biāo)簽確定目標(biāo)標(biāo)簽所在的六面體，之后利用鄰近參考標(biāo)簽的權(quán)值大小分割空間，最后將目標(biāo)標(biāo)簽鎖定在一個(gè)劃分好的四面體之內(nèi)，取內(nèi)心作為待定位標(biāo)簽的位置。取內(nèi)心，是對(duì)定位目標(biāo)在一定范圍內(nèi)的大體估測(cè)，該算法存在誤差較大；文獻(xiàn) ［6］提出了一種將LANDMARC 和質(zhì)心算法相結(jié)合的方法，對(duì)三維空間內(nèi)的標(biāo)簽進(jìn)行定位，定位精度一般。

本文提出了一種將最近鄰居算法和空間分割相結(jié)合的室內(nèi)三維定位算法，動(dòng)態(tài)插入虛擬參考標(biāo)簽，使目標(biāo)標(biāo)簽所在的空間最小化，加權(quán)最鄰近參考標(biāo)簽求得待定位標(biāo)簽的三維坐標(biāo)。本文算法既節(jié)約了系統(tǒng)成本，同時(shí)也提高了定位精度，更具有實(shí)用性價(jià)值。

1 關(guān)鍵技術(shù)

1.1 RFID技術(shù)

RFID 的信號(hào)傳播模型，也叫 “距離－損耗”模型，由于信號(hào)在傳輸?shù)倪^(guò)程中會(huì)發(fā)生損耗，所以可通過(guò)信號(hào)的衰減程度來(lái)表示距離。使用理論或經(jīng)驗(yàn)的信號(hào)傳播模型將傳播損耗轉(zhuǎn)化為節(jié)點(diǎn)間的距離［7］。其在室內(nèi)的路徑損耗計(jì)算公式如式 （1）所示

式中：PL（d）——經(jīng)過(guò)距離d 后的路徑損耗，單位為dB；Xδ——平均值為0的高斯分布隨機(jī)變量，其標(biāo)準(zhǔn)差一般為4～10［8］。N——路徑衰減因子，依賴于障礙物的結(jié)構(gòu)和使用的材料，它的范圍為2～5；d0為參考距離，通常取值1m。

接收到的信號(hào)強(qiáng)度值可以由式 （2）表示

式中：Pt——發(fā)射功率加天線增益，稱其為發(fā)射信號(hào)功率，單位為dB。Pr（d）——讀寫器接收到標(biāo)簽反射的信號(hào)強(qiáng)度，單位為dB。將式 （1）帶入式 （2）整理可得式 （3）

式 （3）經(jīng)簡(jiǎn)化可得到式 （4）

參數(shù)φ＝Pr（d0）－Xδ表示讀寫器在距離標(biāo)簽1m 處的接收信號(hào)強(qiáng)度值及其波動(dòng)性，γ＝10·N 包含著實(shí)際環(huán)境中的信號(hào)衰減指數(shù)。φ的值可將采集大量數(shù)據(jù)中的有效數(shù)據(jù)取均值得到，γ值可根據(jù)理論式 （4）反推得到。

1.2 LANDMARC－3D算法

LANDMARC所采用的思想見(jiàn)文獻(xiàn) ［9］，本文在LANDMARC算法的基礎(chǔ)之上，通過(guò)引入 ‘Z’坐標(biāo)，擴(kuò)展到三維空間，將二維定位算法轉(zhuǎn)化成三維定位算法，即LANDMARC－3D［3］三維室內(nèi)定位系統(tǒng)。LANDMARC－3D定位算法將可以反映標(biāo)簽的空間位置，這樣對(duì)需要高度信息的目標(biāo)定位來(lái)說(shuō)是一種很好的解決方案。

假設(shè)M 個(gè)讀寫器，U 個(gè)參考標(biāo)簽，N 個(gè)待定位標(biāo)簽。

歐式距離的公式如式 （5）所示。關(guān)于歐式距離公式的詳解請(qǐng)參見(jiàn)文獻(xiàn) ［9］

式中：E——參考標(biāo)簽與待定位標(biāo)簽之間的歐氏距離，E 越小參考標(biāo)簽和待定位標(biāo)簽距離越近。選取K 個(gè)E 值最小的參考標(biāo)簽作為與待定位標(biāo)簽的最鄰近參考標(biāo)簽，可以推算出待定位標(biāo)簽的坐標(biāo)為

式中：wj——第j 個(gè)鄰近參考標(biāo)簽的權(quán)重j＝ （1，2，…K，K＜U），根據(jù)經(jīng)驗(yàn)式 （7）計(jì)算

通過(guò)待定位標(biāo)簽的實(shí)際位置和算法理論估計(jì)得到的位置比較，可以計(jì)算出定位誤差，如式 （8）所示

式中：（x，y，z）——待定位標(biāo)簽的實(shí)際坐標(biāo)， （x0，y0，z0）——待定位標(biāo)簽的估計(jì)坐標(biāo)。

2 改進(jìn)的三維定位算法

2.1 改進(jìn)算法中參考標(biāo)簽和讀寫器的部署

在一個(gè)空曠室內(nèi)的地板和天花板上對(duì)稱排列參考標(biāo)簽，參考標(biāo)簽以邊長(zhǎng)為2m 正方形的形式覆蓋至地板和天花板上，讀寫器分布在室內(nèi)的8個(gè)角上。圖1為參考標(biāo)簽和讀寫器的排列方式。

圖1 參考標(biāo)簽排列方式

如圖1所示，天花板和地板上的參考標(biāo)簽成對(duì)稱形式排列，參考標(biāo)簽將整個(gè)室內(nèi)區(qū)域分割成若干個(gè)六面體。這個(gè)六面體由上下各4個(gè)參考標(biāo)簽組成。當(dāng)待定位標(biāo)簽進(jìn)入室內(nèi)定位空間時(shí)，必定會(huì)出現(xiàn)在由某8個(gè)參考標(biāo)簽組成的六面體中。這8個(gè)參考標(biāo)簽將作為待定位標(biāo)簽的鄰近參考標(biāo)簽，這時(shí)需要把K （鄰近參考標(biāo)簽的個(gè)數(shù)）的值設(shè)定為8。

2.2 改進(jìn)算法的空間分割

本文提出算法的主要思想是將最近鄰居三維定位算法與空間分割相結(jié)合，通過(guò)兩次選擇鄰近參考標(biāo)簽不斷的縮減待定位標(biāo)簽所在的空間。在第一次選擇待定位標(biāo)簽的鄰近參考標(biāo)簽后，確定待定位參考標(biāo)簽在某個(gè)六面體內(nèi)，這時(shí)就實(shí)現(xiàn)了待定位標(biāo)簽所在空間的縮減，也就是定位空間第一次分割，這樣將定位空間縮小到了圖1 中整個(gè)空間的1/9。

通過(guò)式 （5）計(jì)算出所有參考標(biāo)簽的歐氏距離E，這時(shí)每個(gè)參考標(biāo)簽對(duì)應(yīng)一個(gè)E 值。用冒泡排序法將所有參考標(biāo)簽按E值從小到大的順序排序。首先找出一個(gè)面上 （地板或天花板）E值最小的4個(gè)參考標(biāo)簽，如果這4 個(gè)參考標(biāo)簽?zāi)芙M成一個(gè)正方形，則將其和其映射到對(duì)應(yīng)層上的4個(gè)參考標(biāo)簽全部列入鄰近參考標(biāo)簽集合；反之，如果E 值最小的4個(gè)參考標(biāo)簽不能組成一個(gè)正方形，則找下一個(gè)E 值較小的參考標(biāo)簽，一直到4個(gè)標(biāo)簽?zāi)芙M成正方形為止。

如圖2 所示，Q 是待定位標(biāo)簽，參考標(biāo)簽A、B、C、D、A’、B’、C’、D’表示Q 的8 個(gè)鄰近參考標(biāo)簽，它們組成了一個(gè)六面體。由于參考標(biāo)簽的歐幾里得距離越小距離待定位標(biāo)簽越近，將8個(gè)鄰近參考標(biāo)簽按E 值 （歐氏距離）大小排序。

圖2 最鄰近參考標(biāo)簽組成的六面體

如圖3所示的正六面體ABCDA’B’C’D’，假設(shè)EA＜EB＜ED＜EC＜EA’＜EB’＜ED’＜EC’，由于E （A，B，C，D）＜E （A’，B’，C’，D’）可知待定位標(biāo)簽Q 在靠近參考標(biāo)簽A，B，C，D 那一層。做一個(gè)平面，平分上下兩層，Q 將被劃到下層空間。這時(shí)只需判斷下層參考標(biāo)簽歐氏距離的大小劃分空間。在下層平面，因?yàn)镋A＜EB＜ED＜EC可知待定位標(biāo)簽Q 在靠近參考標(biāo)簽A，B，D 的方向；在正方形ABCD 中，分別作AB，AD 的垂直平分線，根據(jù)定理線段垂直平分線上的點(diǎn)到這條線段兩個(gè)端點(diǎn)距離相等，可知待定位標(biāo)簽Q 在正方形AFOG 所對(duì)的空間中，將A、F、O、G 這4個(gè)點(diǎn)映射到中層平面，做與之對(duì)稱的點(diǎn)H、F’、O’、G’。那么待定位標(biāo)簽Q 則圈定在六面體AFOGHF’O’G’中，完成了空間的二次分割，這時(shí)待定位標(biāo)簽Q 所在的空間將是第一次分割出來(lái)的六面體的1/8。

2.3 改進(jìn)算法中虛擬標(biāo)簽信號(hào)強(qiáng)度的計(jì)算

在第二次分割出來(lái)的六面體AFOGHF’O’G’中，通過(guò)一些幾何定理和正方形的性質(zhì)可求出除去已知參考標(biāo)簽A 以外的所有標(biāo)簽的三維坐標(biāo)。由于定位精度會(huì)受參考標(biāo)簽密度的影響，當(dāng)參考標(biāo)簽間距變小時(shí)，它們之間的信號(hào)干擾強(qiáng)度就會(huì)變大，這時(shí)會(huì)影響讀寫器讀取的參考標(biāo)簽信號(hào)強(qiáng)度，對(duì)定位精度會(huì)起到相反的作用。然而，增加參考標(biāo)簽的密度的同時(shí)也加大了系統(tǒng)定位的成本。如果每定位一個(gè)標(biāo)簽都要在二次分割好的空間內(nèi)手動(dòng)插入幾個(gè)參考標(biāo)簽，這也是不可實(shí)現(xiàn)的?？紤]到這些因素，可以把F、O、G、H、F’、O’、G’當(dāng)成臨時(shí)插入的虛擬參考標(biāo)簽來(lái)看待，它們的間距在1 m 左右。由2.1節(jié)中介紹的信號(hào)傳播模型可知，信號(hào)強(qiáng)度值與距離是對(duì)數(shù)關(guān)系的，這樣可以考慮將短距離內(nèi)信號(hào)強(qiáng)度與距離的關(guān)系近似成直線。本文采用拉格朗日插值法找出兩個(gè)參考標(biāo)簽，用這兩個(gè)參考標(biāo)簽信號(hào)強(qiáng)度值與距離的關(guān)系構(gòu)造出一個(gè)函數(shù)。再利用這個(gè)函數(shù)來(lái)計(jì)算虛擬標(biāo)簽的信號(hào)強(qiáng)度值。

圖3 第二次空間分割

例如：如圖3所示，虛擬參考標(biāo)簽F，計(jì)算F 在各個(gè)讀寫器的信號(hào)強(qiáng)度，這時(shí)需要找到離虛擬參考標(biāo)簽距離較近的兩個(gè)參考標(biāo)簽A、B，這兩個(gè)參考標(biāo)簽需滿足 （＜＜，其中為虛擬參考標(biāo)簽F 到讀寫器i的距離，和分別表示參考標(biāo)簽A 和B到讀寫器i的距離）。式（9）為計(jì)算虛擬標(biāo)簽信號(hào)強(qiáng)度的公式

第二次分割得到的六面體AFOGHF’O’G’中，找到8個(gè)參考標(biāo)簽：A、F、O、G、H、F’、O’、G’，計(jì)算出它們的歐氏距離，利用經(jīng)驗(yàn)式 （7）得到它們的權(quán)值，最后經(jīng)式 （6）加權(quán)得到待定位標(biāo)簽的位置。

2.4 定位步驟

（1）初始化定位模型：在室內(nèi)空間的天花板和地板上布置參考標(biāo)簽和讀寫器，參考標(biāo)簽之間的間隔為2 m，在室內(nèi)房間的8個(gè)頂點(diǎn)布置8個(gè)讀寫器，如圖1所示。

（2）采集數(shù)據(jù)：讀寫器讀取所有參考標(biāo)簽的信號(hào)強(qiáng)度，由于周圍環(huán)境干擾等原因采集相同距離的信號(hào)強(qiáng)度可能有較小波動(dòng)，本文采取將多次測(cè)量的有效值 （出現(xiàn)頻率較高的值）取平均的方法，建立信號(hào)強(qiáng)度值與距離關(guān)系的模型。

（3）讀取待定位標(biāo)簽的信號(hào)強(qiáng)度值。

（4）計(jì)算每個(gè)參考標(biāo)簽的E值 （歐幾里得距離）。

（5）第一次分割定位空間：用冒泡排序法將所有參考標(biāo)簽按E值從小到大排序。由于K＝8為了節(jié)省計(jì)算時(shí)間，只需找到能組成一個(gè)六面體且E 值最小的8個(gè)參考標(biāo)簽即可。這8個(gè)參考標(biāo)簽將待定位標(biāo)簽圈定在一個(gè)六面體內(nèi)，縮小了定位空間。

（6）第二次分割定位空間：按組成六面體的8 個(gè)最鄰近參考標(biāo)簽的E值大小再次分割空間，這時(shí)需要在六面內(nèi)動(dòng)態(tài)插入虛擬參考標(biāo)簽，將原來(lái)六面體劃分成8份，將待定位標(biāo)簽的定位空間再次縮減到原六面體的1/8。

（7）計(jì)算虛擬參考標(biāo)簽的信號(hào)強(qiáng)度：定位空間經(jīng)二次分割后得到的六面體中有7個(gè)虛擬參考標(biāo)簽，利用幾何定理計(jì)算出虛擬參考標(biāo)簽的三維坐標(biāo)。選擇虛擬參考標(biāo)簽附近的參考標(biāo)簽，利用式 （9）計(jì)算出每個(gè)虛擬參考標(biāo)簽的信號(hào)強(qiáng)度值。之后組成新六面體的這8個(gè)參考標(biāo)簽和虛擬參考標(biāo)簽將作為待定位標(biāo)簽的最鄰近參考標(biāo)簽。

（8）加權(quán)求得待定位標(biāo)簽的位置：用式 （7）計(jì)算出最鄰近參考標(biāo)簽的權(quán)值，根據(jù)式 （6）求得待定位標(biāo)簽的位置。

3 實(shí)驗(yàn)結(jié)果及分析

仿真實(shí)驗(yàn)，在一個(gè)空曠的長(zhǎng)6m、寬6m、高3m 的室內(nèi)空間。如圖1所示，在地板上和天花板上布置參考標(biāo)簽，它們之間的間隔為2m。8個(gè)讀寫器分布在室內(nèi)空間的8個(gè)角上。

將空間分割算法、CPS三維質(zhì)心定位算法、改進(jìn)算法采用相同的參考標(biāo)簽定位模型在空曠的室內(nèi)環(huán)境下，進(jìn)行定位精度對(duì)比。本文采用標(biāo)準(zhǔn)差來(lái)判斷每次定位誤差偏離平均誤差的程度，從而推斷出定位算法的穩(wěn)定性。式 （10）為標(biāo)準(zhǔn)差的計(jì)算公式

式中：σ——標(biāo)準(zhǔn)差，N——待定位標(biāo)簽的個(gè)數(shù) （在1.2 中有介紹），error——定位誤差，——平均誤差。這里用誤差的標(biāo)準(zhǔn)差大小來(lái)評(píng)判算法的穩(wěn)定性。σ越小，證明算法越穩(wěn)定，反之則證明算法的波動(dòng)性越大。

如圖4所示，隨機(jī)取20個(gè)待定位標(biāo)簽，分別用空間分割算法、CPS算法和本文改進(jìn)算法進(jìn)行仿真實(shí)驗(yàn)對(duì)比定位精度，分割算法的定位誤差在0.27m～1.32m 之間波動(dòng)；CPS定位算法的定位誤差在0.16m～1.4m 之間波動(dòng)。改進(jìn)算法的定位誤差在0.07m～0.76m 之間波動(dòng)。從圖4可以看出改進(jìn)算法的定位誤差是最小的?？臻g分割算法和CPS定位算法的波動(dòng)性較大，而改進(jìn)算法的定位誤差比較穩(wěn)定。

圖4 定位誤差對(duì)比

圖4中的20個(gè)待定位標(biāo)簽，經(jīng)計(jì)算分割算法的平均定位誤差為0.8515m，標(biāo)準(zhǔn)差為0.34；CPS定位算法的平均誤差為0.7085m，標(biāo)準(zhǔn)差為0.33；改進(jìn)算法的平均誤差為0.335m，標(biāo)準(zhǔn)差為0.19。由標(biāo)準(zhǔn)差的大小可知分割算法的誤差波動(dòng)幅度最大，其次是CPS定位算法，而改進(jìn)算法的誤差分布很穩(wěn)定。

圖5表示隨機(jī)取20個(gè)待定位標(biāo)簽，3種算法的累積分布函數(shù)對(duì)比。橫坐標(biāo)表示定位誤差，單位是米；縱坐標(biāo)表示概率累積量。例如定位誤差為0.2 m 時(shí)對(duì)應(yīng)的概率累積量 （縱坐標(biāo)）即為所有測(cè)量結(jié)果中定位誤差小于0.2 m 的標(biāo)簽數(shù)占總測(cè)量標(biāo)簽數(shù)的百分比。

圖5 20個(gè)待定位標(biāo)簽的累積分布函數(shù)比較

如圖5所示，改進(jìn)算法的定位誤差全部小于0.8m，分割算法和CPS定位算法的定位誤差全部小于1.4 m。改進(jìn)算法的誤累積函數(shù)比較陡，收斂速度快。改進(jìn)算法的定位精度比空間分割算法提高了60.7%，比CPS三維質(zhì)心定位算法的定位精度提高了52.72%。

圖6表示任取50個(gè)待定位標(biāo)簽，3種算法的誤差累積分布函數(shù)。改進(jìn)算法的定位誤差全部小于0.8 m，分割算法和CPS的定位誤差全部小于1.6 m。經(jīng)計(jì)算分割算法的平均定位誤差為0.8376 m，標(biāo)準(zhǔn)差為0.34；CPS 定位算法的平均誤差為0.7342 m，標(biāo)準(zhǔn)差為0.34；改進(jìn)算法的平均誤差為0.3074m，標(biāo)準(zhǔn)差為0.18。改進(jìn)算法比空間分割算法的定位精度提高63%，比CPS算法定位精度提高了58%。高銳［5］和馬斌［6］等的研究已將LANDMARC－3D 三維定位算法實(shí)現(xiàn)，在相同的定位環(huán)境下對(duì)分割算法和CPS定位算法進(jìn)行對(duì)比，對(duì)比結(jié)果表明這兩個(gè)定位算法的定位精度都高于LANDMARC－3D 算法，并且，本文改進(jìn)算法的定位精度也將遠(yuǎn)高于LANDMARC－3D算法。

圖6 50個(gè)待定位標(biāo)簽的累積分布函數(shù)比較

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

在本文提出的改進(jìn)算法中，為了提高算法的定位精度，所有的仿真實(shí)驗(yàn)都是基于256等級(jí)的硬件平臺(tái)，將信號(hào)強(qiáng)度值分成256個(gè)等級(jí)，而LANDMARC系統(tǒng)只有8個(gè)等級(jí)；為了節(jié)約系統(tǒng)成本減小信號(hào)間的干擾，改進(jìn)算法采用臨時(shí)插入虛擬參考標(biāo)簽的方法；為了使計(jì)算出來(lái)的虛擬參考標(biāo)簽信號(hào)強(qiáng)度值更接近于讀寫器接收到的真實(shí)值，以離虛擬參考標(biāo)簽最近的兩個(gè)參考標(biāo)簽為參考，采用拉格朗日插值法計(jì)算出虛擬標(biāo)簽信號(hào)強(qiáng)度值。仿真結(jié)果表明，改進(jìn)算法的定位精度與空間分割算法、CPS 三維質(zhì)心定位算法和LANDMARC－3D相比都有明顯提高，能滿足人們對(duì)于室內(nèi)定位的需求。

［1］Welbourne E，Battle L，Cole G，et al.Building the internet of things using RFID：The RFID ecosystem experience ［J］.Internet Computing，IEEE，2009，13 （3）：48－55.

［2］Ni LM，Zhang D，Souryal MR.RFID－based localization and tracking technologies ［J］.Wireless Communications，IEEE，2011，18 （2）：45－51.

［3］Khan MA，Antiwal VK.Location estimation technique using extended 3－D LANDMARC algorithm for passive RFID tag［C］//IEEE International Advance Computing Conference，2009：249－253.

［4］Bouet M，Pujolle G.L－VIRT：Range－free 3－D localization of RFID tags based on topological constraints ［J］.Computer Communications，2009，32 （13）：1485－1494.

［5］GAO Rui，CHENG Lianglun，HU Xin.Indoor positioning method based on space division using passive RFID ［J］.Application Research of Computers，2012，29 （1）：184－186 （in Chinese）.［高銳，程良倫，胡莘.一種基于空間分割的無(wú)源RFID室內(nèi)定位方法 ［J］.計(jì)算機(jī)應(yīng)用研究，2012，29 （1）：184－186.］

［6］MA Bin，XIE Ya’nan，QIU Haibin，et al.Three－dimensional centroid algorithm for building environment location based on CPS［J］.Journal of Shenyang Jianzhu University （Natural Science），2013，29 （2）：372－377（in Chinese）.［馬斌，解亞男，邱海斌，等.基于CPS的建筑內(nèi)環(huán)境三維質(zhì)心定位算法 ［J］.沈陽(yáng)建筑大學(xué)學(xué)報(bào)（自然科學(xué)版），2013，29 （2）：372－377.］

［7］Wang Chong，Wu Hongyi，Tzeng NF.RFID－based 3－D positioning schemes［C］//26th IEEE International Conference on Computer Communications.IEEE，2007：1235－1243.

［8］ZHANG Jieying，SUN Maoheng，WANG Xia.Dynamic distance estimation method based on RSSI and LQI［J］.Electronic Measurement Technology，2007，30 （2）：142－145 （in Chinese）.［張潔穎，孫懋珩，王俠.基于RSSI和LQI的動(dòng)態(tài)距離估計(jì)算法 ［J］. 電子測(cè)量技術(shù)，2007，30 （2）：142－145.］

［9］DENG Huifang，MA Qiping，ZHOU Shangwei.Use of RFID technology for indoor localization ［J］.Computer Application，2008，28 （7）：1858－1860 （in Chinese）. ［鄧輝舫，馬啟平，周尚偉.使用無(wú)線射頻識(shí)別 （RFID）技術(shù)進(jìn)行室內(nèi)定位 ［J］.計(jì)算機(jī)應(yīng)用，2008，28 （7）：1858－1860.］