劉 宣, 鄒寬城, 吳海飛

(長春工業(yè)大學計算機科學與工程學院,吉林長春 130012)

0 引 言

射頻識別即RFID(Radio Frequency IDentification)技術(shù)是一種快速、安全且具有高效自動識別的技術(shù),利用射頻信號通過空間耦合(交變磁場或電磁場)實現(xiàn)無接觸信息傳遞,并通過所傳遞的信息達到識別目的[1]。RFID技術(shù)最早應用于第二次世界大戰(zhàn)期間,在20世紀80年代走向成熟,經(jīng)過幾十年的發(fā)展,RFID技術(shù)已在各行各業(yè)得到廣泛應用。目前,它已經(jīng)逐漸成為提高現(xiàn)代物流工作效率的技術(shù)工具和手段?，F(xiàn)代物流充分運用信息技術(shù),將運輸、倉儲、裝卸、加工整理、配送等有機結(jié)合,形成完整的供應鏈,并越來越呈現(xiàn)出信息化、網(wǎng)絡(luò)化、自動化、模塊、標準化等發(fā)展趨勢,其中信息化是現(xiàn)代物流的核心。在近幾年物流業(yè)的快速發(fā)展中,現(xiàn)代物流已經(jīng)采用了大量信息及自動化技術(shù)來提高效率,但有很多工作仍主要依靠人工來完成,例如數(shù)據(jù)錄入、貨物的清點和盤庫等,而手持式條形碼識別器等輔助工具對上述問題也不能根本有效解決。正是由于這種信息采集手段落后或工作效率的問題而造成信息采集和傳輸過程中的錯誤,從而影響了物流效率。無線射頻識別技術(shù)(RFID)在數(shù)據(jù)采集、數(shù)據(jù)傳遞方面具有獨到的優(yōu)勢。與條碼技術(shù)相比,具有識別速度快,閱讀距離遠,使用壽命長,無需對準識別等諸多優(yōu)點,并且可以實現(xiàn)多目標識別和運動目標識別。它作為信息傳遞的載體,可以有效避免人工輸入可能出現(xiàn)的失誤,大大提高入庫、出庫、驗貨、盤點、補貨等工作效率,在物流供應鏈管理領(lǐng)域具有很大的應用潛力。推廣RFID技術(shù),讓該技術(shù)盡快發(fā)揮其對物流行業(yè)強大推動作用,是國際物流企業(yè)技術(shù)應用的大趨勢。

射頻識別系統(tǒng)主要由電子標簽和讀寫器兩部分組成,電子標簽是電子產(chǎn)品代碼的載體,附著于需跟蹤的物體上,讀寫器通過無線信道按照一定的協(xié)議讀寫標簽。RFID系統(tǒng)工作時,經(jīng)常有一個以上電子標簽同時處于閱讀器的作用范圍內(nèi)。當這些電子標簽同時將自身攜帶的數(shù)據(jù)傳送給讀寫器時,就會出現(xiàn)沖突,這將導致讀寫器不能正確讀出數(shù)據(jù),這就是標簽的防沖突算法解決的問題。常用的防碰撞算法主要有基于二進制搜索的確定性算法[2]和基于時隙的隨機標簽防沖突算法ALOHA[3]。二進制搜索算法是以標簽的唯一序列號為基礎(chǔ)來實現(xiàn)防沖突的,采用Manchester編碼準確地找到?jīng)_突位,然后強迫其中一方的標簽暫時退出,以此類推,在判斷完整個序列號之后,將得到唯一的序列號。隨機性算法的特點是標簽向讀寫器發(fā)送數(shù)據(jù)的時間是隨機的,沖突發(fā)生后利用退避算法思想進行重發(fā),目前各種隨機性算法都是在ALOHA算法上發(fā)展起來。文中主要研究由EPC global組織制訂的EPC-C1G2[4]標準的時隙隨機算法防碰撞算法SR(Slot Random)[5],并在此算法基礎(chǔ)上進行改進。

1 基于EPC-C1G2標準的時隙隨機算法

基于EPC-C1G2的防碰撞算法是在動態(tài)幀時隙ALOHA(Dynamic Framed Slotted ALOHA,DFSA)算法基礎(chǔ)上改進的時隙隨機算法,該算法沒有幀的概念,取而代之的是識別周期,即讀寫器兩次發(fā)送Query指令的間隔。時隙隨機算法同樣需要標簽隨機選擇響應時隙,區(qū)別在于,該算法可以在識別周期內(nèi)的任何時刻更改時隙數(shù),使未識別標簽重新選擇響應時隙,以實現(xiàn)識別時隙的自適應。

EPC-C1G2標簽包含一個16 bit的隨機數(shù)生成器和一個15 bit的時隙計數(shù)器。在識別標簽的過程中,所涉及的主要命令有Query,QueryAdjust,QueryRep,并通過這3個命令來調(diào)節(jié)時隙數(shù)量。

在每個識別周期,讀寫器首先通過Query指令開啟新的盤存周期,并確定哪個標簽參與該盤存周期。Query命令含有時隙計數(shù)器參數(shù)Q,Q的取值范圍為0～15。收到Query命令后,參與標簽應在0至2Q-1內(nèi)挑選一個15 bit的隨機數(shù),并應將該數(shù)值載入其時隙計數(shù)器。

挑選時隙為0的標簽應轉(zhuǎn)換成應答狀態(tài)。

1)若只有一個標簽應答,閱讀器發(fā)送QueryRep命令,使標簽時隙計數(shù)器中的時隙減1。

2)若沒有標簽應答,閱讀器發(fā)送QueryRep命令,使標簽時隙計數(shù)器中的時隙減1,或發(fā)送QueryAdjust命令減小Q的值,使所有未被識別的標簽進入到下一輪周期識別循環(huán)操作中。

3)若有多個標簽應答,閱讀器發(fā)送QueryRep命令或發(fā)送QueryAdjust命令增大Q的值,使所有未被識別的標簽進入到下一輪周期識別循環(huán)操作中。

從SR算法中可以看出,Q值越大,時隙的范圍也就越大,發(fā)生沖突的可能性就會越小,但將導致空閑時隙增加;反之,Q值越小,標簽發(fā)生沖突的可能性就會越大,導致沖突時隙增加。過多的空閑時隙和沖突時隙都會降低識別效率,因此讀寫器需要不斷地調(diào)整Q值,使時隙數(shù)量接近于標簽的數(shù)量,從而使得標簽在最為合理的取值范圍內(nèi)隨機選擇時隙。

在EPC-C1G2標準中提出了一個選取Q值的方法[3],如圖1所示。

圖1 時隙計數(shù)器參數(shù)Q算法

其中,Qfp為Q的浮點表示,讀寫器將Qfp四舍五入為一個整數(shù)值,并用這個整數(shù)值代替Query命令中的Q值。C的典型值為0.1＜C＜0.5。當Q值較大時,讀寫器一般用C的較小值,如果Q值較小,則用C的較大值[6]。

2 改進的算法

在理想通信狀態(tài)下,發(fā)生沖突的概率和出現(xiàn)時隙閑置的概率是不同的,而在SR算法中Q值固定的情況下,發(fā)生沖突時和出現(xiàn)空閑時隙時的Q的改變量是相同的,這樣不利于時隙的分布達到最佳的狀態(tài)。且當沖突發(fā)生時,沖突標簽只能在新的識別周期操作中重新隨機選擇時隙,而重新選擇后仍會存在沖突時隙與空閑時隙的數(shù)量無法調(diào)整的現(xiàn)象,這將影響標簽的識別速度,從而影響了RFID的信息采集,不利于物流的信息化平臺的建設(shè)。針對這些問題,文中做出了改進。

2.1 算法的改進

文中對Q的改變量Qchange做出了改進,并在此基礎(chǔ)上重新通過實驗設(shè)置Cn的分段值,以及對發(fā)生沖突后的標簽的時隙的調(diào)整做出了改進。

2.1.1 Q的改變量Qchange的改進

定義待識別的標簽數(shù)n,時隙數(shù)N,成功識別標簽的時隙數(shù)n1。

由于標簽時隙計數(shù)器的值是隨機選取的,則每個標簽選取時隙的概率相同,即1/N,符合貝努利分布[7]。

成功識別一個標簽的概率為:

出現(xiàn)空閑時隙的概率為:

發(fā)生碰撞的概率為:

對p1求導,可得當N=n時,p1可以取得最大值為36.8%[8]。

當N=n時,p0≈p1=36.8%,則pc=1-p0-p1=26.4%,即在理想狀態(tài)下,讀寫器可達到成功識別標簽的概率為36.8%,空閑時隙的概率為36.8%,發(fā)生碰撞的概率為26.4%,則p0/p1=1.4。

為了快速地使標簽的讀取效率達到此種狀態(tài),設(shè)定Q的改變量Qchange為:

2.1.2 Cn分段取值的調(diào)整

在運用式(1)改變Q值的基礎(chǔ)上,為了找到Q與Cn之間的一般規(guī)律,對Q算法按Cn取值的不同進行了仿真。由于Q算法是一種基于概率的算法,仿真采用計算10次求平均的方法,在C分別取不同值、Q初始值均為4的情況下計算當標簽數(shù)按2的冪次方規(guī)律變化時的系統(tǒng)吞吐率,即標簽數(shù)與所用時隙數(shù)的比值,仿真環(huán)境為Matlab7.0,仿真結(jié)果保留四位小數(shù),具體結(jié)果見表1。

表1 Cn取不同值時系統(tǒng)吞吐量的變化

根據(jù)表1可以得出,在Q不同值時,對應的Cn的取值見表2。

表2 Q不同值時對應Cn的取值

2.1.3 沖突標簽的時隙調(diào)整

對發(fā)生沖突后的標簽的時隙調(diào)整做出了改進,算法將發(fā)生沖突的標簽在其臨近時隙內(nèi)重新分布。定義1個命令random0:對時隙為0的標簽在0和1中隨機選取時隙。這樣可以使發(fā)生沖突的標簽能夠盡快得到識別。

改進后的算法實現(xiàn)的過程如下:

1)設(shè)置Q的初始值為4.0,執(zhí)行Query命令,為標簽隨機分配時隙。

2)讀寫器接收應答,會出現(xiàn)2),3),4)三種狀態(tài)中的一種。

3)只有一個標簽應答,則成功識別次標簽,執(zhí)行Queryrep命令。

4)沒有標簽應答,則根據(jù)當前Q的值,選擇Cn來調(diào)節(jié)Q的值,即Qchange=Qfp-Cn。

5)有多個標簽應答,則根據(jù)當前Q的值,選擇Cn來調(diào)節(jié)Q的值,即Qchange=Qfp+1.4*Cn。執(zhí)行random0命令,為發(fā)生沖突的標簽在0和1中隨機分配時隙,其它標簽的時隙都加1,開始新的周期的識別,會出現(xiàn)6),7),8)三種狀態(tài)。

6)讀寫器接收應答,會出現(xiàn)7),8),9)三種狀態(tài)中的一種。

7)只有一個標簽應答,則成功識別標簽,轉(zhuǎn)到11)。

8)沒有標簽應答,則Queryrep命令,讀寫器接收應答,random0為時隙為0的標簽在0和1中重新隨機分配時隙。未達到指定的循環(huán)次數(shù),則轉(zhuǎn)到6),否則轉(zhuǎn)到11)。

9)有多個標簽應答,則random0為時隙為0的標簽在0和1中重新隨機分配時隙。未達到指定的循環(huán)次數(shù),則轉(zhuǎn)到6),否則轉(zhuǎn)到11)。

10)若達到制定的循環(huán)次數(shù)后,沒能識別標簽,則改變Q的值,重新為標簽分配時隙。

11)判斷Q的值是否改變,若改變執(zhí)行Queryadjust,否則Queryrep命令識別下一個標簽返回2),否則退出。

2.2 改進前后兩種算法性能的比較

采用了基于在EPC-Gen2協(xié)議中標簽的防碰撞算法的研究,為了便于仿真分析并假設(shè)檢測到一個標簽響應信息時,即認為該標簽可以被正識別,仿真中調(diào)整沖突標簽的時隙的循環(huán)次數(shù)為3次,采用計算100次求平均的方法通過仿真結(jié)果,得到標簽數(shù)量和系統(tǒng)吞吐率之間的關(guān)系,采用原算法和改進算法識別一定數(shù)目的標簽所需的總時隙數(shù)和系統(tǒng)吞吐率如圖2所示。

仿真結(jié)果顯示和原算法相比,改進后的算法可以大大提高標簽識別率,系統(tǒng)吞吐率提高了7%。

圖2 改進的算法與SR算法比較

3 結(jié) 語

研究一種基于EPC-Gen2協(xié)議,針對Q的改變量進行了分析,并提出了改進計算方法,對發(fā)生沖突后標簽的時隙的調(diào)整做出了改進,通過仿真完成了對防沖突算法的優(yōu)化與實現(xiàn),經(jīng)過測試,改進后算法能夠快速識別大量標簽,對射頻識別技術(shù)的研制具有一定的意義。

[1] 游戰(zhàn)清,李蘇劍.無線射頻識別技術(shù)(RFIO)理論與應用[M].北京:電子工業(yè)出版社,2004.

[2] 姜麗芬,盧桂章,辛遠幃.射頻識別系統(tǒng)中的防碰撞算法研究[J].計算機工程與應用,2007,43(15):29-32.

[3] Klaus Finkenzeller.射頻識別技術(shù)[M].3版.北京:電子工業(yè)出版社,2006.

[4] EPC Clasa1 Gen2 Standard[EB/OL].[2011-03-23].http://www.epcglobalinc.org/standards/uhfclg2/.

[5] 劉佳,張有光.基于時隙的RFID防碰撞算法分析[J].電子技術(shù)應用,2007,33(5):94-96.

[6] 王曉東,戎蒙恬.基于Q-選擇的RFID防碰撞算法的研究[J].計算機仿真,2008,25(6):124-126.

[7] 徐凌云.EPC C1G2防碰撞算法仿真研究[J].通信技術(shù),2010,43(5):53-55.

[8] 唐海琳.RFID讀寫器設(shè)計與防沖突算法研究[D]:[碩士學位論文].長沙:國防科學技術(shù)大學,2007.