董長春，周 良

(南京航空航天大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，江蘇 南京 210016)

1 概 述

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

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

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

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

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

2 車庫模型建立

2.1 問題描述

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

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

2.2 RFID覆蓋模型選擇

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

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

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

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

圖2 覆蓋模型

3 基于RFID的商品車定位算法設(shè)計(jì)

3.1 RFID閱讀器放置

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

(44.9-6.55lgHb)lgd+Cm

(1)

其中，L為最大路徑損耗(db)；f為工作載波頻率(MHz)；Hb為基站天線高度(m)；Hm為移動(dòng)臺(tái)天線高度(m)；d為收發(fā)天線之間的距離(km)，實(shí)驗(yàn)中d為RFID閱讀器與RFID收發(fā)器之間的距離[19]。常數(shù)A和B會(huì)隨著頻率的不同而發(fā)生變化：當(dāng)頻率f在150～1 500 MHz之間時(shí)，A=69.55，B=26.16；當(dāng)f>1 500 MHz時(shí)，A=46.3，B=33.9。在實(shí)驗(yàn)中，基站天線高度與移動(dòng)臺(tái)天線高度視為0，即Hb與Hm均為0，樹木對于信號(hào)的影響為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可以看出距離與信號(hào)傳輸中的損耗是正相關(guān)的，當(dāng)距離足夠遠(yuǎn)時(shí)，損耗可以達(dá)到FRID初始信號(hào)的強(qiáng)度，則把此時(shí)的距離值記為RFID發(fā)射器發(fā)射信號(hào)的最遠(yuǎn)距離d。在空曠的地方，L的最大值可達(dá)到220，相應(yīng)的d的最大值為70 m。但是在實(shí)驗(yàn)環(huán)境并不是空曠的車庫，此時(shí)的傳輸半徑可達(dá)到的最大距離僅為60 m，對應(yīng)的六邊形網(wǎng)格的邊長設(shè)定為50 m。

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

3.2 正反饋機(jī)制與蟻群算法

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

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

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

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

(4)當(dāng)滿足終止條件時(shí)，算法終止；否則，重復(fù)步驟2和步驟3。

信息素的更新公式為：

(3)

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

3.3 多點(diǎn)定位及Chan定位算法基本思想

TDOA算法是最為常見的多點(diǎn)定位算法，在不強(qiáng)調(diào)到達(dá)時(shí)間必須嚴(yán)格同步的情況下，為了確保定位的準(zhǔn)確性，應(yīng)當(dāng)放置至少三個(gè)RFID閱讀器。假定目標(biāo)與地面上第i個(gè)接收站的距離用di表示，則距離計(jì)算公式為：

(4)

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

并且，根據(jù)RFID閱讀器接收到信號(hào)的時(shí)間差可以得到下列公式：

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

(5)

(6)

(7)

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

圖3 算法流程

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

3.4 Chan算法改進(jìn)

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

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

(8)

根據(jù)式8，當(dāng)i=1時(shí)，可以得到

(9)

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

2x1x+2y1y

(10)

在此，令

(11)

則用矩陣表達(dá)可得如下形式：

C=A*M

(12)

其中

運(yùn)用加權(quán)最小二乘法得到WLS為：

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

(13)

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

4 實(shí)驗(yàn)結(jié)果與分析

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

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

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

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

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

(5)對比計(jì)算出的車輛位置與找到車輛時(shí)的車輛位置，并計(jì)算相應(yīng)差值。

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

圖4 仿真環(huán)境

上述實(shí)驗(yàn)得到的結(jié)果如表1所示。

表1 算法改進(jìn)前后的測量誤差

由表1可以看出，改進(jìn)后的算法測出來的位置準(zhǔn)確性更高，并且誤差的方差值較小，因此，對于實(shí)驗(yàn)來說，改進(jìn)使得定位算法更精確。

5 結(jié)束語

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