基于RFID及改進Chan算法的商品車定位方法

董長春，周 良

(南京航空航天大學 計算機科學與技術學院，江蘇 南京 210016)

1 概 述

射頻識別(radio frequency identification，RFID)是一種利用射頻信號自動識別目標信號對象并獲取相關信息的技術，具有無需人工干預、方便定位、精度高等優(yōu)點，因此，在室內無線定位系統(tǒng)中有著廣泛的應用。RFID技術最初起源于英國，當前活躍在RFID舞臺上的具有影響力的國際五大標準組織分別是：EPCglobal(electronic product code global，產品電子代碼全球組織)、ISO/IEC JC1 SC3第四工作組、UID(ubiquitous ID center)、AIM(automatic identification manufacturers association)和IP-X[1]。該技術作用距離短，一般最長為幾十米。但它可以在幾毫秒內得到精確度為厘米的信息，且具有傳輸范圍很大，成本較低的特點。目前，RFID技術已經在日常生活中的各個行業(yè)里得到了廣泛的應用，特別是在物流供應鏈上，從商品的入庫、檢查、定位、生產到之后的零售等環(huán)節(jié)都用到了RFID定位技術[2]。

目前，美國福特公司為了嚴格控制福特Essex發(fā)動機的生產質量，采用基于RFID的數據自動采集系統(tǒng)使發(fā)動機生產過程流水線化及數據采集自動化[3]。國內的RFID技術主要應用于商業(yè)企業(yè)流通領域、防偽領域、金融收費領域、民航領域等。

基于RFID的系統(tǒng)一般由三個基本部分組成：(1)標簽(tag)，標簽是每一個RFID的身份證明，即具有唯一性；(2)識別器或讀寫器(reader)，識別器和讀寫器的作用是讀取并識別RFID發(fā)射出的信號，有利于在實驗過程中測量閱讀器與RFID發(fā)射器之間的距離；(3)天線(antenna)，天線的作用即為傳遞RFID信號，RFID的傳播需要通過特定的天線，即天線也是RFID系統(tǒng)中不可或缺的一部分[4]。具體如圖1所示。

圖1 基于RFID的系統(tǒng)基本組成

RFID定位算法通常有兩種：基于測距的定位算法和基于非測距的定位算法?；跍y距的定位算法主要有方向測量定位(AOA)、到達時間定位(TOA)、到達時差定位(TDOA)以及信號強度定位(RSSI)[5]。文獻[6]提出了定位失效RFID閱讀器的距離向量算法，適用于存在定位失效的RFID閱讀器的情況。文獻[7]詳細闡述了網格劃分在RFID定位技術中的應用。文獻[8]主要對比了上述四種常見的基于測距的定位方法在室內定位中的效果與準確度。文獻[9]主要描述了定位技術在倉庫中的應用，提升數字倉庫系統(tǒng)中的智慧化、信息化、數字化和精細化管理。文獻[10]主要描述在改進定位算法之后，圖書館的借還書的效率以及服務的質量。這種算法要求節(jié)點具備測距能力或角度信息，通常定位精度較高，但對節(jié)點的硬件也提出了很高的要求，定位過程中消耗的能量較多[11]。同時，定位精度也易受溫度、濕度、障礙物等環(huán)境因素的影響。非測距定位算法主要有DV-Hop定位算法、APIT定位算法、凸規(guī)劃算法等[12]。這種算法不需要測量節(jié)點間的相對距離或方位，對節(jié)點硬件的要求低，定位性能受環(huán)境因素的影響較小，而且在成本和功耗方面也比基于測距的方式有優(yōu)勢，但是，定位誤差較大[13]。文中對于定位的精準度要求高，因此使用的是基于測距的定位算法。

2 車庫模型建立

2.1 問題描述

東澤國際物流有限公司是一家專注于進口整車、汽車零部件等高端產品的整體物流供應鏈操作和管理企業(yè)，每一輛汽車進關入庫時都會擁有一個含有RFID標簽的電子標識，即電子車牌，是車輛輔助管理的智能卡片，有利于實現(xiàn)對車輛的遠距離、非接觸、不停車等多種方式的管理[14-15]。

商品車的定位簡單來說，就是如何快速在車庫之中找到商品車的準確位置。先將車庫的平面系統(tǒng)進行合理的區(qū)塊劃分，每一個區(qū)塊要有多個RFID閱讀器，區(qū)塊內的每一個位置都可以被多個RFID閱讀器的閱讀范圍覆蓋，再在區(qū)塊內進行最優(yōu)解的搜索，得到初始解集，再通過改進的Chan算法得到車輛最終的位置[16]。

2.2 RFID覆蓋模型選擇

在車庫模型中，當企業(yè)接收到訂單時，根據訂單之中車輛的類型找出相應車輛的傳感器信號，通過無線定位技術確定此種車型所在的區(qū)域，然后根據不同的車輛距離出口的位置以及停車坪的距離和所?？臻g決定是否即可提取車輛。在實驗中，需要讓RFID的信號覆蓋整個車庫，因此需要考慮覆蓋模型的選擇問題[17-18]。

覆蓋問題可根據覆蓋對象的不同分為三種：點覆蓋(point coverage)、區(qū)域覆蓋(area coverage)以及柵欄覆蓋(barrier coverage)。該實驗采用的是區(qū)域覆蓋。

在解決覆蓋問題時，可以因為覆蓋對象的不一樣而選擇不同的方法。由于該實驗環(huán)境是車庫，因此可以選擇區(qū)域覆蓋。在一個封閉的環(huán)境中，區(qū)域覆蓋可以保證其中的每一個節(jié)點都會被感知而不會對RFID閱讀器的個數產生過高的要求。如圖2所示，可以看出車庫被劃分成的矩形區(qū)域完全被多個RFID閱讀器的覆蓋區(qū)域半徑包括在內，且對于車輛這種較大的物品來說，基本不存在覆蓋漏洞。

在該實驗中，如圖2所示，雖然每個車輛是非連續(xù)的點，但由于車輛排放位置具有不確定性，因此，需要覆蓋的范圍是整個車庫。所以，將覆蓋模式看作區(qū)域覆蓋是較為合理，較為實際的。

圖2 覆蓋模型

3 基于RFID的商品車定位算法設計

3.1 RFID閱讀器放置

L=A+Blgf-13.82lgHb-α(Hm)+

(44.9-6.55lgHb)lgd+Cm

(1)

其中，L為最大路徑損耗(db)；f為工作載波頻率(MHz)；Hb為基站天線高度(m)；Hm為移動臺天線高度(m)；d為收發(fā)天線之間的距離(km)，實驗中d為RFID閱讀器與RFID收發(fā)器之間的距離[19]。常數A和B會隨著頻率的不同而發(fā)生變化：當頻率f在150～1 500 MHz之間時，A=69.55，B=26.16；當f>1 500 MHz時，A=46.3，B=33.9。在實驗中，基站天線高度與移動臺天線高度視為0，即Hb與Hm均為0，樹木對于信號的影響為0，即Cm為0，RFID的頻率為433 MHz。在150～1 500 MHz之間，通過上述判斷可以得到A=69.55，B=26.16，f=433 MHz，Cm=0，Hb=0，Hm=0，則式1可以簡化為：

L=69.55+69.00+44.9lgd

(2)

從式2可以看出距離與信號傳輸中的損耗是正相關的，當距離足夠遠時，損耗可以達到FRID初始信號的強度，則把此時的距離值記為RFID發(fā)射器發(fā)射信號的最遠距離d。在空曠的地方，L的最大值可達到220，相應的d的最大值為70 m。但是在實驗環(huán)境并不是空曠的車庫，此時的傳輸半徑可達到的最大距離僅為60 m，對應的六邊形網格的邊長設定為50 m。

在實驗過程中，必須保證每一個六邊形的內部可被至少三個RFID閱讀器的閱讀范圍覆蓋，因此，每個六邊形中，選出三個不相鄰的節(jié)點放置RFID閱讀器即可。

3.2 正反饋機制與蟻群算法

蟻群算法(ant colony optimization，ACO)是一種基于群體的啟發(fā)式算法，是一種結合了正反饋機制的算法。算法中，螞蟻觀察到的范圍是一個方格世界，相關參數為速度半徑，一般為3。在該實驗中，將六邊形內部劃分邊長為1的正方形，設定螞蟻一次移動一格。螞蟻在行動的時候會留下屬于自己的信息素用來區(qū)分是否遇到障礙物(車輛)，并且，信息素會以一定速率消失，因此，長度較短的邊信息素的水平較高，而信息素高又會吸引更多的螞蟻，形成了一格正反饋機制，長度較長的邊正好相反。蟻群算法正是利用這種正反饋機制的優(yōu)點，通過信息素的不斷更新得到最優(yōu)解。蟻群算法求解初始解的過程如下：

(1)將所有路徑的信息素初始值置為0，再將螞蟻的初始位置設為六邊形的一角；

(2)基于路徑上的信息素濃度，選擇任意方向向前進一格；

(3)進行一次迭代之后，找到當前情況下的最優(yōu)路徑解，再以該解集為基礎進行下一輪迭代；

(4)當滿足終止條件時，算法終止；否則，重復步驟2和步驟3。

信息素的更新公式為：

(3)

其中，τold、τnew分別表示更新前后的邊(i,j)的信息素的值；ρ為信息素消失速率，一般情況下，0<ρ<1；r為迭代后得到的解集或全局最優(yōu)解。通過迭代之后，可以得到實驗所需的初始解集，再通過對初始解集的優(yōu)化得到車輛的最終放置位置。

3.3 多點定位及Chan定位算法基本思想

TDOA算法是最為常見的多點定位算法，在不強調到達時間必須嚴格同步的情況下，為了確保定位的準確性，應當放置至少三個RFID閱讀器。假定目標與地面上第i個接收站的距離用di表示，則距離計算公式為：

(4)

其中，[xi,yi,zi]表示地面上第i個接收站的空間坐標；[x,y,z]表示信號發(fā)射端的空間坐標。

并且，根據RFID閱讀器接收到信號的時間差可以得到下列公式：

di,j=di-dj=v(ti-tj)

(5)

(6)

(7)

在多點定位中對于目標位置的計算通常采用Chan算法。算法會首先假設定位目標距離各個基站很遠，則可以將移動目標到基站的距離與定位目標到基站的距離、測量噪聲的協(xié)方差矩陣與矢量的協(xié)方差矩陣近似相等。然后通過加權最小二乘法(WLS)獲得定位目標的近似坐標。但是，Chan算法中存在定位目標距離各個基站都很近的情況，此時移動目標到基站的距離與定位目標到基站的距離不可能相等。此情況下，要假設基站與目標位置距離很遠，滿足移動目標到基站的距離與定位目標到基站的距離的前提再進行求解。具體流程如圖3所示。

圖3 算法流程

實驗過程中，首先利用正反饋機制以及遺傳蟻群算法在整個車庫空間中搜尋最優(yōu)解；將最優(yōu)解賦值設定為初值并帶入式5～式7求解，得到初始解的估計矩陣，即為矩陣H，再以矩陣H為基礎運用Chan算法進行WLS求解。該方法的顯著優(yōu)勢在于不受Chan算法中目標位置與接收站位置距離的限制，并且融合了蟻群算法和遺傳算法的優(yōu)點，避免了遺傳算法和蟻群算法存在的明顯缺陷，相比而言，擁有更好的求解效率和時間效率。

3.4 Chan算法改進

文中的定位目標與RFID閱讀器之間的距離都比較接近，因此需要首先假設目標位置與RFID閱讀器較遠，利用正反饋機制與改進型遺傳蟻群算法在空間搜尋最優(yōu)解，將最優(yōu)解賦值作為初始猜測值，并將其引入矩陣求解初始估計矩陣H，然后基于此，運用Chan算法進行WLS的求解。在實際情況中，大多數情況下，目標在二維平面上運動，因此可以使用二維坐標表示目標的空間位置，具體求解步驟如下：

(xi-x)2+(yi-y)2=

(8)

根據式8，當i=1時，可以得到

(9)

將式9帶入式8，可以化簡得到

2x1x+2y1y

(10)

在此，令

(11)

則用矩陣表達可得如下形式：

C=A*M

(12)

其中

運用加權最小二乘法得到WLS為：

M1=argmin(C-AM)T(C-AM)

(13)

則可以根據已知站點的位置得出最優(yōu)解，其中M為通過正反饋與蟻群算法在空間中搜尋的初始解集，M1為通過WLS得到的最終解。

4 實驗結果與分析

文中所有程序采用MATLAB2016b工具編寫，在Inter(R)Core(TM) i3-4160 CPU @ 3.60 GHz、內存4.0 GB的計算機上運行。實驗步驟如下：

(1)通過模型覆蓋算法確定RFID閱讀器的個數與放置位置；

(2)根據正反饋機制與蟻群算法得到初始最優(yōu)解；

(3)將初始解集帶入優(yōu)化后的Chan算法中得到多組(x，y)坐標值；

(4)根據最小二乘法得到車輛的準確位置，并回步驟2至訂單中所有車輛全部找到；

(5)對比計算出的車輛位置與找到車輛時的車輛位置，并計算相應差值。

實驗仿真環(huán)境如圖4所示。將10 m*10 m的正方形區(qū)域劃分成邊長為1 m的格子，在該區(qū)域的內部放置了四個RFID閱讀器，閱讀器的位置坐標分別為(2.5，2.5)，(2.5，7.5)，(7.5，2.5)，(7.5，7.5)，用星號“*”表示；需要測量的車輛坐標分別為(0，1)，(2，3)，(3，7)，(4，3)，(5，2)，(7，6)，(8，5)，(9，10)，(10，4)，用圓圈“°”表示：

圖4 仿真環(huán)境

上述實驗得到的結果如表1所示。

表1 算法改進前后的測量誤差

由表1可以看出，改進后的算法測出來的位置準確性更高，并且誤差的方差值較小，因此，對于實驗來說，改進使得定位算法更精確。

5 結束語

隨著車輛需求的日益增加，車輛的裝載與運輸變得格外重要，而如何提高車輛裝車效率也成了至關重要的問題，因此，定位技術的選擇格外重要。多點定位系統(tǒng)因為具有定位精度較高、安裝方便等特點而應用廣泛。文中結合正反饋機制、蟻群算法以及Chan算法的優(yōu)點，提出了一種基于RFID技術的無線定位的商品車裝車算法，避免了兩種傳統(tǒng)經典算法存在的局限性。通過與原先算法的比對，發(fā)現(xiàn)改進算法的定位更為準確。