基于EPC-C1G2標準的標簽防碰撞算法

2011-07-09 01:40:16鄒寬城吳海飛

長春工業大學學報 2011年3期

劉宣, 鄒寬城, 吳海飛

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

0 引言

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

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

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

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

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

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

挑選時隙為0的標簽應轉換成應答狀態。

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

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

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

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

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

圖1 時隙計數器參數Q算法

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

2 改進的算法

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

2.1 算法的改進

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

2.1.1 Q的改變量Qchange的改進

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

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

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

出現空閑時隙的概率為:

發生碰撞的概率為:

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

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

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

2.1.2 Cn分段取值的調整

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

表1 Cn取不同值時系統吞吐量的變化

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

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

2.1.3 沖突標簽的時隙調整

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

改進后的算法實現的過程如下:

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

2)讀寫器接收應答,會出現2),3),4)三種狀態中的一種。

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

4)沒有標簽應答,則根據當前Q的值,選擇Cn來調節Q的值,即Qchange=Qfp-Cn。

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

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

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

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

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

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

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

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

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

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