基于RFID的虛擬參考標簽三維室內定位算法

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

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

0 引 言

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

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

本文提出了一種將最近鄰居算法和空間分割相結合的室內三維定位算法，動態插入虛擬參考標簽，使目標標簽所在的空間最小化，加權最鄰近參考標簽求得待定位標簽的三維坐標。本文算法既節約了系統成本，同時也提高了定位精度，更具有實用性價值。

1 關鍵技術

1.1 RFID技術

RFID 的信號傳播模型，也叫 “距離－損耗”模型，由于信號在傳輸的過程中會發生損耗，所以可通過信號的衰減程度來表示距離。使用理論或經驗的信號傳播模型將傳播損耗轉化為節點間的距離［7］。其在室內的路徑損耗計算公式如式 （1）所示

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

接收到的信號強度值可以由式 （2）表示

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

式 （3）經簡化可得到式 （4）

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

1.2 LANDMARC－3D算法

LANDMARC所采用的思想見文獻 ［9］，本文在LANDMARC算法的基礎之上，通過引入 ‘Z’坐標，擴展到三維空間，將二維定位算法轉化成三維定位算法，即LANDMARC－3D［3］三維室內定位系統。LANDMARC－3D定位算法將可以反映標簽的空間位置，這樣對需要高度信息的目標定位來說是一種很好的解決方案。

假設M 個讀寫器，U 個參考標簽，N 個待定位標簽。

歐式距離的公式如式 （5）所示。關于歐式距離公式的詳解請參見文獻 ［9］

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

式中：wj——第j 個鄰近參考標簽的權重j＝ （1，2，…K，K＜U），根據經驗式 （7）計算

通過待定位標簽的實際位置和算法理論估計得到的位置比較，可以計算出定位誤差，如式 （8）所示

式中：（x，y，z）——待定位標簽的實際坐標， （x0，y0，z0）——待定位標簽的估計坐標。

2 改進的三維定位算法

2.1 改進算法中參考標簽和讀寫器的部署

在一個空曠室內的地板和天花板上對稱排列參考標簽，參考標簽以邊長為2m 正方形的形式覆蓋至地板和天花板上，讀寫器分布在室內的8個角上。圖1為參考標簽和讀寫器的排列方式。

圖1 參考標簽排列方式

如圖1所示，天花板和地板上的參考標簽成對稱形式排列，參考標簽將整個室內區域分割成若干個六面體。這個六面體由上下各4個參考標簽組成。當待定位標簽進入室內定位空間時，必定會出現在由某8個參考標簽組成的六面體中。這8個參考標簽將作為待定位標簽的鄰近參考標簽，這時需要把K （鄰近參考標簽的個數）的值設定為8。

2.2 改進算法的空間分割

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

通過式 （5）計算出所有參考標簽的歐氏距離E，這時每個參考標簽對應一個E 值。用冒泡排序法將所有參考標簽按E值從小到大的順序排序。首先找出一個面上 （地板或天花板）E值最小的4個參考標簽，如果這4 個參考標簽能組成一個正方形，則將其和其映射到對應層上的4個參考標簽全部列入鄰近參考標簽集合；反之，如果E 值最小的4個參考標簽不能組成一個正方形，則找下一個E 值較小的參考標簽，一直到4個標簽能組成正方形為止。

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

圖2 最鄰近參考標簽組成的六面體

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

2.3 改進算法中虛擬標簽信號強度的計算

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

圖3 第二次空間分割

例如：如圖3所示，虛擬參考標簽F，計算F 在各個讀寫器的信號強度，這時需要找到離虛擬參考標簽距離較近的兩個參考標簽A、B，這兩個參考標簽需滿足 （＜＜，其中為虛擬參考標簽F 到讀寫器i的距離，和分別表示參考標簽A 和B到讀寫器i的距離）。式（9）為計算虛擬標簽信號強度的公式

第二次分割得到的六面體AFOGHF’O’G’中，找到8個參考標簽：A、F、O、G、H、F’、O’、G’，計算出它們的歐氏距離，利用經驗式 （7）得到它們的權值，最后經式 （6）加權得到待定位標簽的位置。

2.4 定位步驟

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

（2）采集數據：讀寫器讀取所有參考標簽的信號強度，由于周圍環境干擾等原因采集相同距離的信號強度可能有較小波動，本文采取將多次測量的有效值 （出現頻率較高的值）取平均的方法，建立信號強度值與距離關系的模型。

（3）讀取待定位標簽的信號強度值。

（4）計算每個參考標簽的E值 （歐幾里得距離）。

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

（6）第二次分割定位空間：按組成六面體的8 個最鄰近參考標簽的E值大小再次分割空間，這時需要在六面內動態插入虛擬參考標簽，將原來六面體劃分成8份，將待定位標簽的定位空間再次縮減到原六面體的1/8。

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

（8）加權求得待定位標簽的位置：用式 （7）計算出最鄰近參考標簽的權值，根據式 （6）求得待定位標簽的位置。

3 實驗結果及分析

仿真實驗，在一個空曠的長6m、寬6m、高3m 的室內空間。如圖1所示，在地板上和天花板上布置參考標簽，它們之間的間隔為2m。8個讀寫器分布在室內空間的8個角上。

將空間分割算法、CPS三維質心定位算法、改進算法采用相同的參考標簽定位模型在空曠的室內環境下，進行定位精度對比。本文采用標準差來判斷每次定位誤差偏離平均誤差的程度，從而推斷出定位算法的穩定性。式 （10）為標準差的計算公式

式中：σ——標準差，N——待定位標簽的個數 （在1.2 中有介紹），error——定位誤差，——平均誤差。這里用誤差的標準差大小來評判算法的穩定性。σ越小，證明算法越穩定，反之則證明算法的波動性越大。

如圖4所示，隨機取20個待定位標簽，分別用空間分割算法、CPS算法和本文改進算法進行仿真實驗對比定位精度，分割算法的定位誤差在0.27m～1.32m 之間波動；CPS定位算法的定位誤差在0.16m～1.4m 之間波動。改進算法的定位誤差在0.07m～0.76m 之間波動。從圖4可以看出改進算法的定位誤差是最小的。空間分割算法和CPS定位算法的波動性較大，而改進算法的定位誤差比較穩定。

圖4 定位誤差對比

圖4中的20個待定位標簽，經計算分割算法的平均定位誤差為0.8515m，標準差為0.34；CPS定位算法的平均誤差為0.7085m，標準差為0.33；改進算法的平均誤差為0.335m，標準差為0.19。由標準差的大小可知分割算法的誤差波動幅度最大，其次是CPS定位算法，而改進算法的誤差分布很穩定。

圖5表示隨機取20個待定位標簽，3種算法的累積分布函數對比。橫坐標表示定位誤差，單位是米；縱坐標表示概率累積量。例如定位誤差為0.2 m 時對應的概率累積量 （縱坐標）即為所有測量結果中定位誤差小于0.2 m 的標簽數占總測量標簽數的百分比。

圖5 20個待定位標簽的累積分布函數比較

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

圖6表示任取50個待定位標簽，3種算法的誤差累積分布函數。改進算法的定位誤差全部小于0.8 m，分割算法和CPS的定位誤差全部小于1.6 m。經計算分割算法的平均定位誤差為0.8376 m，標準差為0.34；CPS 定位算法的平均誤差為0.7342 m，標準差為0.34；改進算法的平均誤差為0.3074m，標準差為0.18。改進算法比空間分割算法的定位精度提高63%，比CPS算法定位精度提高了58%。高銳［5］和馬斌［6］等的研究已將LANDMARC－3D 三維定位算法實現，在相同的定位環境下對分割算法和CPS定位算法進行對比，對比結果表明這兩個定位算法的定位精度都高于LANDMARC－3D 算法，并且，本文改進算法的定位精度也將遠高于LANDMARC－3D算法。

圖6 50個待定位標簽的累積分布函數比較

4 結束語

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

［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）.［高銳，程良倫，胡莘.一種基于空間分割的無源RFID室內定位方法 ［J］.計算機應用研究，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的建筑內環境三維質心定位算法 ［J］.沈陽建筑大學學報（自然科學版），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的動態距離估計算法 ［J］. 電子測量技術，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）. ［鄧輝舫，馬啟平，周尚偉.使用無線射頻識別 （RFID）技術進行室內定位 ［J］.計算機應用，2008，28 （7）：1858－1860.］