基于動(dòng)態(tài)幀時(shí)隙ALOHA的危險(xiǎn)品運(yùn)輸RFID防碰撞算法*

魏福祿，劉 攀，李志斌，孫 鋒，郭永青，曹寧博

(1.東南大學(xué) 交通學(xué)院，南京 210096；2.山東理工大學(xué) 交通與車輛工程學(xué)院，山東 淄博 255000；3.長(zhǎng)安大學(xué) 經(jīng)濟(jì)與管理學(xué)院，西安 710064)

射頻識(shí)別(radio frequency identification，RFID)技術(shù)在物聯(lián)網(wǎng)應(yīng)用中需要對(duì)大量的標(biāo)簽進(jìn)行實(shí)時(shí)處理[1]，可能會(huì)出現(xiàn)兩個(gè)以上的電子標(biāo)簽同時(shí)處于閱讀器工作范圍內(nèi)的情況，如果這些電子標(biāo)簽同時(shí)發(fā)送數(shù)據(jù)將會(huì)造成通信沖突；類似地，也會(huì)有多個(gè)標(biāo)簽同時(shí)處于多個(gè)閱讀器工作范圍內(nèi)的情況，這些標(biāo)簽在傳輸數(shù)據(jù)時(shí)也會(huì)造成數(shù)據(jù)間通信的干擾，以上問(wèn)題是當(dāng)前需要解決的難題.射頻識(shí)別系統(tǒng)的相關(guān)算法常用于工業(yè)、物聯(lián)網(wǎng)、交通運(yùn)輸?shù)阮I(lǐng)域，通過(guò)設(shè)定一些相應(yīng)的規(guī)則、命令和研判策略來(lái)減少?zèng)_突問(wèn)題的產(chǎn)生，這些規(guī)則、命令和研判策略則被稱為防碰撞算法.

目前，ALOHA算法主要有純ALOHA算法、時(shí)隙ALOHA算法、幀時(shí)隙ALOHA算法、動(dòng)態(tài)幀時(shí)隙ALOHA算法等.同時(shí)，二進(jìn)制樹(shù)算法又包含：查詢樹(shù)算法、二進(jìn)制樹(shù)搜索算法、動(dòng)態(tài)二進(jìn)制樹(shù)搜索算法、回退式索引二進(jìn)制樹(shù)搜索、跳躍式動(dòng)態(tài)搜索算法等[2-5].結(jié)合ALOHA算法和二進(jìn)制樹(shù)算法這兩種算法的混合型算法在理論層面可以實(shí)現(xiàn)識(shí)別速度的提升，然而在RFID系統(tǒng)的應(yīng)用層面上，此類防碰撞算法的識(shí)別能力和識(shí)別率卻并不理想[6].

動(dòng)態(tài)幀時(shí)隙ALOHA算法能夠動(dòng)態(tài)調(diào)整時(shí)隙的數(shù)量，實(shí)現(xiàn)對(duì)標(biāo)簽的快速識(shí)別[7].通過(guò)優(yōu)化達(dá)到最佳幀長(zhǎng)的步數(shù)，將沖突時(shí)隙進(jìn)一步劃分，降低輪詢空時(shí)隙，從而可以使動(dòng)態(tài)幀時(shí)隙ALOHA算法延時(shí)降低，系統(tǒng)運(yùn)行效率提高[8].Haida等人采用分布式方法，通過(guò)引入多通道協(xié)議能夠提高RFID讀取器對(duì)RFID網(wǎng)絡(luò)資源的利用率，該算法能有效減少標(biāo)簽識(shí)別時(shí)間，從而提高了成功詢問(wèn)速度[9].王達(dá)等[10]對(duì)動(dòng)態(tài)RFID環(huán)境準(zhǔn)確識(shí)別標(biāo)簽估計(jì)的動(dòng)態(tài)幀時(shí)隙ALOHA算法進(jìn)行改進(jìn)，從而能夠有效降低標(biāo)簽的丟失率，提高標(biāo)簽的準(zhǔn)確識(shí)別率.

為了降低標(biāo)簽的碰撞率，提升標(biāo)簽的識(shí)別效率，可通過(guò)對(duì)識(shí)別標(biāo)簽進(jìn)行分組，設(shè)置一定閥值再確定優(yōu)先級(jí)，然后優(yōu)先響應(yīng)當(dāng)前需要響應(yīng)的標(biāo)簽，從而提升效率[11].基于時(shí)分多址/頻分多址建立的RFID閱讀器防碰撞算法對(duì)信標(biāo)進(jìn)行分析和管理，可以使無(wú)法訪問(wèn)信道的閱讀器在下一個(gè)輪回中通過(guò)信標(biāo)信息發(fā)送優(yōu)先級(jí)碼，從而更有機(jī)會(huì)訪問(wèn)該信道.為了解決現(xiàn)有動(dòng)態(tài)幀時(shí)隙ALOHA標(biāo)簽防碰撞算法的系統(tǒng)吞吐率及效率低等問(wèn)題，部分學(xué)者提出一種可并行識(shí)別的分組動(dòng)態(tài)幀時(shí)隙ALOHA標(biāo)簽防碰撞算法，在很大程度上提升了算法的識(shí)別效率[12-13].

危險(xiǎn)品在運(yùn)輸過(guò)程始終處于一個(gè)動(dòng)態(tài)變化的環(huán)境中，需要對(duì)大量的標(biāo)簽進(jìn)行實(shí)時(shí)處理，標(biāo)簽在進(jìn)入和離開(kāi)閱讀范圍時(shí)，會(huì)降低幀結(jié)束時(shí)估算標(biāo)簽數(shù)量的精確度，這就對(duì)防碰撞算法提出了更高的標(biāo)準(zhǔn).鑒于危險(xiǎn)品運(yùn)輸?shù)奶厥庑裕绾翁岣逺FID系統(tǒng)識(shí)別標(biāo)簽的效率和通過(guò)率便成為最為關(guān)鍵的問(wèn)題之一.本文提出了基于動(dòng)態(tài)幀時(shí)隙ALOHA的危險(xiǎn)品運(yùn)輸RFID防碰撞算法，將RFID系統(tǒng)應(yīng)用在危險(xiǎn)品運(yùn)輸管理過(guò)程中，可以為危險(xiǎn)品運(yùn)輸管理提供更安全、準(zhǔn)確的服務(wù).

1 基于ALOHA的系統(tǒng)防碰撞算法

1.1 RFID系統(tǒng)工作原理

RFID作為一種射頻系統(tǒng)，主要包括電子標(biāo)簽、讀寫器、RFID應(yīng)用系統(tǒng)三部分，RFID系統(tǒng)結(jié)構(gòu)如圖1所示.電子標(biāo)簽指的是內(nèi)置天線和芯片的微型收發(fā)裝置，包含電壓調(diào)節(jié)器、調(diào)制器、解調(diào)器和存儲(chǔ)單元.讀寫器用來(lái)收集數(shù)據(jù)并將其寫入RFID標(biāo)簽中.RFID應(yīng)用系統(tǒng)包括中間件和應(yīng)用軟件，中間件是提供系統(tǒng)軟件和應(yīng)用軟件之間連接的軟件，能夠?qū)?shù)據(jù)進(jìn)行采集、過(guò)濾、信息整合與傳遞；應(yīng)用軟件對(duì)讀寫器和標(biāo)簽內(nèi)的信息交互進(jìn)行控制，從而對(duì)信息進(jìn)行接收、采集、統(tǒng)計(jì)與執(zhí)行.

圖1 RFID系統(tǒng)結(jié)構(gòu)

1.2 標(biāo)簽防碰撞算法

RFID系統(tǒng)主要采取兩種防碰撞算法來(lái)解決標(biāo)簽的防碰撞問(wèn)題，第一種是確定性防碰撞算法，這種算法比較復(fù)雜，工作效率低，識(shí)別過(guò)程中延遲比較明顯；第二種是隨機(jī)性防碰撞算法，它是一種概率性算法，包括ALOHA算法、幀時(shí)隙ALOHA算法、動(dòng)態(tài)幀時(shí)隙ALOHA算法等.判斷算法的可行性需要對(duì)多個(gè)指標(biāo)進(jìn)行考察，如平均數(shù)據(jù)包交換量、吞吐量以及信號(hào)傳輸?shù)钠骄舆t等指標(biāo).

1.3 幀時(shí)隙ALOHA算法(FSA)

幀時(shí)隙ALOHA算法是以時(shí)隙ALOHA算法為基礎(chǔ)，把m個(gè)時(shí)隙打包成一幀的算法，算法示意圖如圖2所示.

圖2 幀時(shí)隙ALOHA算法示意圖

圖2中，N為幀長(zhǎng)，它表示每幀中含有的時(shí)隙數(shù)，中心標(biāo)有圓圈的方塊表示每個(gè)標(biāo)簽在對(duì)應(yīng)的時(shí)隙內(nèi)發(fā)送的數(shù)據(jù)包.這種算法首先是由閱讀器發(fā)送N值來(lái)限定周圍標(biāo)簽發(fā)送的時(shí)隙，然后標(biāo)簽選擇一個(gè)整數(shù)來(lái)加載自身的時(shí)隙計(jì)數(shù)器，這個(gè)數(shù)是隨機(jī)選擇出來(lái)的；隨著時(shí)隙的推移，每個(gè)時(shí)隙中時(shí)隙計(jì)數(shù)器為0的標(biāo)簽可以立即響應(yīng)，其它標(biāo)簽各自的時(shí)隙計(jì)數(shù)器為-1；對(duì)于幀中發(fā)生碰撞的標(biāo)簽將在下一幀中被處理，未碰撞成功識(shí)別的標(biāo)簽退出系統(tǒng)，幀時(shí)隙ALOHA算法過(guò)程如表1所示.

表1中每幀包含3個(gè)時(shí)隙，前后連續(xù)兩幀，分別為第1幀和第2幀.最初開(kāi)始讀取數(shù)據(jù)時(shí)，標(biāo)簽1和標(biāo)簽3、標(biāo)簽2和標(biāo)簽5分別在時(shí)隙1和時(shí)隙2中傳輸數(shù)據(jù)，但一個(gè)時(shí)隙只能同時(shí)傳輸一組序列號(hào)，所以這些標(biāo)簽將在下一幀即第2幀中進(jìn)行傳輸，標(biāo)簽4在時(shí)隙3中成功被識(shí)別后從系統(tǒng)中撤離出去.假設(shè)有n個(gè)待識(shí)讀標(biāo)簽，且每個(gè)標(biāo)簽選擇任意一個(gè)時(shí)隙的概率相等，幀長(zhǎng)為N，則標(biāo)簽選擇任意時(shí)隙i響應(yīng)的概率為

表1 幀時(shí)隙ALOHA算法過(guò)程

p=1/N

(1)

根據(jù)二項(xiàng)式定理，有r個(gè)標(biāo)簽同時(shí)響應(yīng)時(shí)隙i的概率為

(2)

當(dāng)r=1時(shí)，該時(shí)隙成功識(shí)別的概率為

(3)

當(dāng)r=0時(shí)，該時(shí)隙空閑的概率為

(4)

當(dāng)r的取值超過(guò)1時(shí)，時(shí)隙由于有多個(gè)標(biāo)簽同時(shí)響應(yīng)，故產(chǎn)生碰撞，則碰撞概率為

pcoll=1-psucc-pidle=

(5)

FSA算法的系統(tǒng)吞吐率為

(6)

當(dāng)N=n時(shí)，S取得最大值且S≈0.367 88

幀時(shí)隙ALOHA算法的優(yōu)點(diǎn)是簡(jiǎn)單易行，而且?guī)拇笮∠鄬?duì)來(lái)說(shuō)比較固定；缺點(diǎn)是識(shí)別標(biāo)簽的吞吐率較低，在每一個(gè)時(shí)隙中都會(huì)有多個(gè)標(biāo)簽發(fā)生碰撞，從而使讀取過(guò)程易陷入無(wú)限循環(huán).

1.4 動(dòng)態(tài)幀時(shí)隙ALOHA算法(DFSA)

為了對(duì)標(biāo)簽進(jìn)行動(dòng)態(tài)管理，使標(biāo)簽的數(shù)量和幀長(zhǎng)相等，幀長(zhǎng)N的大小要隨著標(biāo)簽數(shù)量變化動(dòng)態(tài)地進(jìn)行調(diào)節(jié)，這需要對(duì)待讀標(biāo)簽數(shù)目進(jìn)行估計(jì).

1)標(biāo)簽數(shù)量估算方法.DFSA算法的核心工作是盡可能地使幀長(zhǎng)N接近待讀標(biāo)簽數(shù)量n，所以對(duì)DFSA算法進(jìn)行改進(jìn)必須圍繞這個(gè)工作前提展開(kāi).時(shí)隙ALOHA算法的工作流程為：

① 讀寫器通過(guò)發(fā)送Query指令來(lái)對(duì)時(shí)隙數(shù)幀長(zhǎng)Ln進(jìn)行規(guī)定；

② 電子標(biāo)簽隨機(jī)選擇幀長(zhǎng)范圍內(nèi)的一個(gè)時(shí)隙來(lái)對(duì)讀寫器的指令進(jìn)行響應(yīng)并返回信息包；

③ 算法會(huì)根據(jù)之前一幀的信息反饋(即觀測(cè)值，包括成功時(shí)隙數(shù)Csucc，空閑時(shí)隙數(shù)Cidle以及碰撞時(shí)隙數(shù)Ccoll)，運(yùn)用電子標(biāo)簽估算方法對(duì)工作場(chǎng)區(qū)內(nèi)的標(biāo)簽數(shù)量進(jìn)行估算，并根據(jù)估算出的標(biāo)簽數(shù)量來(lái)選擇一個(gè)適合的時(shí)隙數(shù)幀長(zhǎng)Ln+1；

④ 將選擇值Ln+1作為下一幀的幀長(zhǎng)，重復(fù)上述方法步驟進(jìn)行電子標(biāo)簽的識(shí)讀，直到讀寫器工作場(chǎng)區(qū)中的電子標(biāo)簽全部被識(shí)別完全.

Crate的理想值為

(7)

因此，碰撞時(shí)隙中期望的標(biāo)簽數(shù)為

(8)

假設(shè)碰撞標(biāo)簽的數(shù)量分布符合泊松分布，即在每一個(gè)時(shí)隙中平均有2.39個(gè)電子標(biāo)簽發(fā)生碰撞.這種方法是通過(guò)對(duì)碰撞標(biāo)簽數(shù)量Ccoll的估計(jì)來(lái)對(duì)未識(shí)別標(biāo)簽的數(shù)量n進(jìn)行估計(jì)，并據(jù)此方法進(jìn)行幀長(zhǎng)的動(dòng)態(tài)調(diào)整，從而獲得較高的系統(tǒng)效率.通過(guò)分析比對(duì)不同初始幀長(zhǎng)(N=64，N=128，N=256)，采用Schoute算法來(lái)估計(jì)系統(tǒng)吞吐量，可以看出幀長(zhǎng)與未標(biāo)簽數(shù)量越接近，用來(lái)調(diào)節(jié)幀長(zhǎng)的時(shí)隙就越少，效率就越高.

2)幀長(zhǎng)調(diào)整.若要有效減少幀長(zhǎng)的調(diào)整次數(shù)，需要減少每一幀內(nèi)電子標(biāo)簽產(chǎn)生碰撞的概率，增加每一幀內(nèi)成功識(shí)別的電子標(biāo)簽的時(shí)隙數(shù).通過(guò)增加幀內(nèi)時(shí)隙數(shù)幀長(zhǎng)L可以減少幀長(zhǎng)的調(diào)整次數(shù)，但當(dāng)L增大時(shí)，系統(tǒng)的吞吐率會(huì)隨之下降，所以既想要增大L的值又想要保持一定的系統(tǒng)吞吐率需要進(jìn)行討論.定義系統(tǒng)的吞吐率為35%，則

(9)

運(yùn)用線性回歸統(tǒng)計(jì)方法求出L和n的關(guān)系.表2中列出了當(dāng)S=0.35時(shí)，L和n的數(shù)據(jù)情況.通過(guò)觀察表2中的數(shù)據(jù)可知，L/n的值平均在1.40左右，因此L和n的關(guān)系符合一元線性回歸L=an+b，即需要對(duì)a和b進(jìn)行優(yōu)化取值.采用最小平方誤差的方法，并運(yùn)用Matlab軟件中的polyfit函數(shù)求出a和b的最優(yōu)值，線性回歸擬合方程如圖3所示.

表2 時(shí)隙數(shù)幀長(zhǎng)與標(biāo)簽數(shù)n的對(duì)應(yīng)關(guān)系

通過(guò)圖3可以看到，所繪制的7組數(shù)據(jù)基本都在一條直線上，擬合準(zhǔn)確度較高.通過(guò)理論計(jì)算和實(shí)驗(yàn)分析，在滿足系統(tǒng)的吞吐率為35%的情況下，得到時(shí)隙數(shù)幀長(zhǎng)和標(biāo)簽數(shù)量的關(guān)系為

L=1.36n+3.08

(10)

將式(10)代入到式(9)中得到

(11)

檢驗(yàn)結(jié)果符合系統(tǒng)吞吐率為35%的最初設(shè)定，對(duì)于所有的正整數(shù)n，算法能保證系統(tǒng)吞吐率在35%以上.

2 實(shí)例仿真驗(yàn)證

2.1 仿真實(shí)驗(yàn)設(shè)計(jì)

本文選取廣州市某公司的危險(xiǎn)品運(yùn)輸數(shù)據(jù)進(jìn)行實(shí)例分析，通過(guò)對(duì)不同數(shù)量的標(biāo)簽系統(tǒng)效率狀態(tài)進(jìn)行仿真，比較動(dòng)態(tài)幀時(shí)隙和固定幀時(shí)隙ALOHA算法來(lái)確定最優(yōu)的方案，從而對(duì)市區(qū)道路和倉(cāng)庫(kù)危險(xiǎn)品進(jìn)行有效管理.

選取珠海至中山的危險(xiǎn)品運(yùn)輸路線，危險(xiǎn)品運(yùn)輸車的額定載重量最大不超過(guò)20 t，中山市危險(xiǎn)品每天運(yùn)輸車輛約為1 489輛，其中珠海市到中山市的貨運(yùn)占比為5%.經(jīng)計(jì)算，每天從珠海市運(yùn)輸?shù)街猩绞械奈ｋU(xiǎn)品運(yùn)輸車輛約為75輛.設(shè)L的初值為8，隨著標(biāo)簽數(shù)目的增多，以2的倍數(shù)增長(zhǎng).一天內(nèi)在一條公路上危險(xiǎn)品的運(yùn)輸車輛約為75輛，即設(shè)置在道路旁的閱讀器最少需要對(duì)75個(gè)標(biāo)簽進(jìn)行識(shí)別.

2.2 仿真結(jié)果及分析

固定幀時(shí)隙ALOHA算法和動(dòng)態(tài)幀時(shí)隙ALOHA算法的系統(tǒng)效率對(duì)比如圖4所示.在固定幀時(shí)隙中時(shí)隙數(shù)幀長(zhǎng)L=64，標(biāo)簽數(shù)為60時(shí)，系統(tǒng)最高效率為35.2%，但之后隨著標(biāo)簽數(shù)增多，系統(tǒng)效率迅速下降；在動(dòng)態(tài)幀時(shí)隙算法中，在標(biāo)簽數(shù)為0～100時(shí)，隨著n的增加，系統(tǒng)的效率在隨之逐漸上漲，最后保持在35.2%穩(wěn)定不變.

圖4 仿真結(jié)果對(duì)比

由此可知，動(dòng)態(tài)幀時(shí)隙ALOHA算法能夠更好地解決系統(tǒng)防碰撞問(wèn)題，使其能夠在標(biāo)簽數(shù)量較多的情況下發(fā)揮自身的優(yōu)勢(shì)，在危險(xiǎn)品運(yùn)輸中能夠避免更多麻煩，更好地解決實(shí)際問(wèn)題.物流危險(xiǎn)品運(yùn)輸公司運(yùn)到中山市產(chǎn)生的標(biāo)簽數(shù)至少為75，而且中山市道路每天產(chǎn)生的標(biāo)簽數(shù)在1 000以上，通過(guò)圖4仿真結(jié)果可知，動(dòng)態(tài)幀時(shí)隙ALOHA算法穩(wěn)定性更好，且省時(shí)、省力.

3 結(jié) 論

本文分析了RFID系統(tǒng)的工作原理及幀時(shí)隙ALOHA算法的優(yōu)缺點(diǎn)，在此基礎(chǔ)上提出了利用動(dòng)態(tài)幀時(shí)隙來(lái)處理危險(xiǎn)品運(yùn)輸中RFID系統(tǒng)標(biāo)簽沖突的方法.建立了基于固定幀時(shí)隙ALOHA和基于動(dòng)態(tài)幀時(shí)隙ALOHA的危險(xiǎn)品運(yùn)輸RFID防碰撞模型，并通過(guò)理論分析和仿真驗(yàn)證，論證了基于動(dòng)態(tài)幀時(shí)隙ALOHA的危險(xiǎn)品運(yùn)輸RFID防碰撞算法的實(shí)用性.在固定幀時(shí)隙ALOHA算法基礎(chǔ)上發(fā)展的動(dòng)態(tài)幀時(shí)隙ALOHA算法的系統(tǒng)效率有所提高，動(dòng)態(tài)幀時(shí)隙ALOHA算法在危險(xiǎn)品運(yùn)輸RFID系統(tǒng)中更加穩(wěn)定、高效，對(duì)于危險(xiǎn)品運(yùn)輸管理具有重要意義.