無線射頻識別(RFID)是一種非接觸式的自動識別技術(shù),，其基本原理是利用射頻信號和空間耦合(電感或電磁耦合)的傳輸特性,，實現(xiàn)對特定物體的自動識別。RFID技術(shù)可以追溯至第二次世界大戰(zhàn)期間,，后來發(fā)展應(yīng)用到鐵路,、軍隊的貨物跟蹤甚至寵物識別上。在過去的半個多世紀(jì)里,，RFID的發(fā)展經(jīng)歷了從技術(shù)探索,、試驗研究、商業(yè)應(yīng)用和標(biāo)準(zhǔn)化建立等幾個重要階段,。從現(xiàn)有發(fā)展趨勢看,，RFID 將構(gòu)建虛擬世界與物理世界的橋梁?？梢灶A(yù)見在不久的將來,，RFID 技術(shù)不僅會在各行各業(yè)被廣泛采用，最終RFID 技術(shù)還將會與普適計算技術(shù)相融合,，對人類社會產(chǎn)生深遠(yuǎn)影響,。
　　RFID系統(tǒng)一般由電子標(biāo)簽和讀寫器" title="讀寫器">讀寫器兩個部分組成，讀寫器具有同時讀取多個電子標(biāo)簽的功能,。在多標(biāo)簽對一個讀寫器的RFID系統(tǒng)中,，標(biāo)簽經(jīng)常會同時向讀寫器傳輸數(shù)據(jù)，這就要求RFID系統(tǒng)建立一種仲裁機制來避免數(shù)據(jù)發(fā)生碰撞,?？紤]到電子標(biāo)簽本身尺寸、能耗的限制,，防碰撞機制在保障功能的同時還要求盡量簡單易行,，這正是RFID系統(tǒng)設(shè)計的挑戰(zhàn)之一,。
　　文獻^[1]和^[2]提出了三種RFID系統(tǒng)的防碰撞算法。算法A基于隨機避讓,、沖突檢測的原理,，使用1個8位寄存器和1個8位隨機數(shù)" title="隨機數(shù)">隨機數(shù)產(chǎn)生器" title="產(chǎn)生器">產(chǎn)生器，最大" title="最大">最大可以仲裁標(biāo)簽的數(shù)量只有256個,。算法B基于二進制數(shù)的原理，使用1個8位寄存器和1個1位隨機數(shù)產(chǎn)生器,，理論上最大可以實現(xiàn)2²⁵⁶個標(biāo)簽的仲裁,。文獻^[3]提出了對該算法的一個實現(xiàn)方案，文獻^[4]對該算法做了很大改進,。算法C類似于算法A,，使用1個16位寄存器和16個1位隨機數(shù)產(chǎn)生器，最大可以仲裁標(biāo)簽的數(shù)量是65 536個,。本文中,，作者提出一種分群避讓、群內(nèi)沖突檢測的算法和其改進算法,，僅需要1個8位寄存器和1個1位隨機數(shù)產(chǎn)生器就可以實現(xiàn)最大1 048 576個標(biāo)簽的仲裁,，而且碰撞次數(shù)相對于算法B要大大減少。
1 仲裁機制描述
　　本方法的核心思想是：首先把電子標(biāo)簽隨機分群,，并將群隨機排序以實現(xiàn)群間的隨機避讓,，然后在群內(nèi)進行沖突檢測和標(biāo)簽的仲裁。實現(xiàn)時標(biāo)簽僅需一個寄存器：利用其高位存儲群號,，低位存儲沖突檢測時退避的步數(shù),，實現(xiàn)極為簡單。下面以8位寄存器為例具體說明本算法的仲裁機制,。
　　當(dāng)讀寫器初始化標(biāo)簽時,，所有標(biāo)簽在0～15之間任選一個整數(shù)存入寄存器高4位(相當(dāng)于隨機選擇一個群)并把寄存器低4位設(shè)為全0，同時產(chǎn)生一個0或1的隨機數(shù)加到寄存器中,。如果此時寄存器中的8比特數(shù)為全0則回傳該標(biāo)簽的ID(ID是指電子標(biāo)簽的惟一標(biāo)識,，在不同的編碼系統(tǒng)中有不同的含義)。如果多個標(biāo)簽同時回傳數(shù)據(jù),，則沖突發(fā)生,。發(fā)生沖突后，其他寄存器高4位為0的標(biāo)簽寄存器中的數(shù)加1,，而寄存器中的8比特數(shù)為全0的標(biāo)簽則再產(chǎn)生一個0或1的隨機數(shù)加到寄存器中,。如果寄存器作加法后仍為全零，則繼續(xù)回傳該標(biāo)簽的ID,；如果回傳時不發(fā)生碰撞,，則其他寄存器高4位為0的標(biāo)簽僅把寄存器低4位減1后重復(fù)前面的回傳操作,。當(dāng)寄存器高4位全為0的標(biāo)簽全部回傳完ID，則所有其他標(biāo)簽把寄存器高4位減1后重復(fù)前面的操作,。
　　此外依本算法,，由于所有標(biāo)簽隨機選擇群，有可能會出現(xiàn)某個群中的標(biāo)簽數(shù)目過大,，使該群中的標(biāo)簽在仲裁過程中始終發(fā)生碰撞,，標(biāo)簽寄存器始終加1，導(dǎo)致寄存器低4位向高4位進位,。進位意味著所有進位的標(biāo)簽的寄存器低4位清零而高4位加1,，這使得這些標(biāo)簽不再屬于原有的群而歸入到下一個群中，從而優(yōu)化了因隨機選擇而產(chǎn)生的分布不均勻的群標(biāo)簽數(shù),。
　　本算法中,，標(biāo)簽最大退讓步數(shù)為2⁴=16步，因此每個群最大能仲裁的標(biāo)簽數(shù)目為2¹⁶＝65 536,，則本算法能仲裁的標(biāo)簽數(shù)理論上限是16×2¹⁶＝1 048 576,。
2 算法步驟
　　本節(jié)給出算法步驟，假設(shè)使用一個8位寄存器,，則本算法包括以下步驟：
　　(1)在所述RFID系統(tǒng)的被動方－標(biāo)簽中設(shè)計一個4+4
　　位的寄存器(Re1)和1個“0”,、“1”隨機數(shù)產(chǎn)生器(RG1)，如圖1所示,。

　　(2)在所述RFID系統(tǒng)的主動方－讀寫器向所有處在等待態(tài)的標(biāo)簽發(fā)送初始化命令,。標(biāo)簽因此進入仲裁態(tài)，用RG1產(chǎn)生4比特隨機數(shù),，加載" title="加載">加載到Re1高4位R7~R4,，低4位R3~R0全部清零。
　　(3)讀寫器等待一定時間后發(fā)送允許回傳命令,。
　　(4)Re1為全零的標(biāo)簽向讀寫器回傳標(biāo)簽ID,。
　　(5)如果當(dāng)前只有一個標(biāo)簽回傳ID，讀寫器正確讀取該ID,，則發(fā)送確認(rèn)命令,，附加命令參數(shù)“低位減1”?；貍髁薎D的標(biāo)簽接收到該命令后,，進入確認(rèn)態(tài)，其他高4位為全零的標(biāo)簽Re1低4位減1,，回到步驟(4)重復(fù)操作,。
　　(6)如果當(dāng)前有多個標(biāo)簽回傳ID，讀寫器通過CRC校驗或碼長校驗,，檢測到錯誤的ID號,，則發(fā)送確認(rèn)命令,，附加命令參數(shù)“寄存器加1”。接收到讀寫器這個命令后,，所有在仲裁態(tài)且Re1為全零的標(biāo)簽由RG1產(chǎn)生1比特隨機數(shù)和寄存器上的數(shù)相加后重新載入到寄存器中,；其他仲裁態(tài)且Re1高4位為零而低4位不為零的標(biāo)簽Re1加1，回到步驟(4)重復(fù)操作,。
　　(7)如果當(dāng)前沒有標(biāo)簽回傳ID,，讀寫器等待一定時間后發(fā)送確認(rèn)命令，附加命令參數(shù)“低位減1”,。所有在仲裁態(tài)且高4為全零的標(biāo)簽Re1低4位減1,，回到步驟(4)重復(fù)操作。
　　(8)低4位減1操作重復(fù)L次(L是一個系統(tǒng)參數(shù),，由系統(tǒng)設(shè)定，經(jīng)驗值為4)后,，讀寫器認(rèn)為所有在仲裁態(tài)且寄存器高4位為零的標(biāo)簽都已經(jīng)被正確讀取,，則發(fā)送確認(rèn)命令，附加命令參數(shù)“高4位減1”,，回到步驟(4),。
　　(9)標(biāo)簽接收到附加“高位減1”參數(shù)的確認(rèn)命令后，所有Re1高4位不為零的標(biāo)簽高4位減1,，回到步驟4重復(fù)操作,；在被要求高位減1前已為零的標(biāo)簽則回到等待態(tài)。
　　(10)重復(fù)15次高位減1操作后,，讀寫器認(rèn)為所有在仲裁態(tài)的標(biāo)簽都已經(jīng)被讀取,，則仲裁過程停止，所有還處于仲裁態(tài)的標(biāo)簽返回等待態(tài),。
　　算法步驟中所述等待態(tài)是指電子標(biāo)簽上電后的初始狀態(tài),；仲裁態(tài)是指未被讀寫器鑒別的電子標(biāo)簽開始響應(yīng)讀寫器鑒別命令時進入的狀態(tài)；確認(rèn)態(tài)是指已被讀寫器鑒別的電子標(biāo)簽進入的狀態(tài),。電子標(biāo)簽狀態(tài)轉(zhuǎn)移規(guī)則如下：上電后電子標(biāo)簽進入等待態(tài),；處于等待態(tài)的電子標(biāo)簽可以進入仲裁態(tài)；處于仲裁態(tài)的電子標(biāo)簽可以返回等待態(tài),；處于仲裁態(tài)的電子標(biāo)簽可以進入確認(rèn)態(tài),；處于確認(rèn)態(tài)的電子標(biāo)簽不能返回仲裁態(tài)；確認(rèn)態(tài)與等待態(tài)之間不能直接轉(zhuǎn)移,。
　　針對上述算法步驟,，在以下幾個地方加以改進，形成本算法的改進算法,。
　　A,、步驟(1)中,，隨機數(shù)產(chǎn)生器產(chǎn)生兩組隨機數(shù)，分別加載到寄存器高位和低4位,。其中高位加載的位數(shù)M可以動態(tài)設(shè)為1,、2、3或4,。
　　B,、步驟(10)中的重復(fù)操作次數(shù)為2^M次。因為改進算法在寄存器低4位也加載了隨機數(shù),，使得標(biāo)簽在群間轉(zhuǎn)移的概率(即低4位向高位進位的概率)大大增加,，特別如果最后一個群中標(biāo)簽的寄存器低4位在退讓步驟中進位，則會產(chǎn)生一個新群,，因此需要額外增加一次高位減1操作,。
3 電路實現(xiàn)
　　算法實現(xiàn)的參考電路框圖見圖1，其中RG1是一個“0”“1”隨機數(shù)產(chǎn)生器,；Re1是一個8位寄存器,。加法器ADD1和ADD2的加減功能根據(jù)讀寫器命令來設(shè)定：當(dāng)執(zhí)行加法操作時，低4位的ADD2需向高4位的ADD1進位,；當(dāng)執(zhí)行減法操作時,，兩個器件ADD1和ADD2相互獨立。加法器可以工作在同步狀態(tài)或異步狀態(tài),，工作在同步狀態(tài)時可以使用電子標(biāo)簽的最大時鐘,。
4 仿真結(jié)果
　　仿真1:為了評估本算法的優(yōu)劣，特設(shè)計以下仿真：標(biāo)簽使用8位寄存器,，高4位為高位,。定義0個、2個和2個以上的標(biāo)簽同時發(fā)送數(shù)據(jù)時為傳輸沖突,；只有一個標(biāo)簽發(fā)送數(shù)據(jù)時為傳輸成功,，平均沖突次數(shù)定義為傳輸沖突總次數(shù)和傳輸成功總次數(shù)的比；空傳率定義0個標(biāo)簽發(fā)送數(shù)據(jù)的次數(shù)與傳輸成功總次數(shù)的比,。觀察標(biāo)簽數(shù)為20～10 000時的平均沖突次數(shù),。
　　仿真結(jié)果如圖2所示，本文提出的算法與二進制算法性能接近,，平均每成功傳輸1次都要伴隨2次傳輸沖突,；而改進算法則在標(biāo)簽數(shù)為50～5 000個時明顯減少了碰撞次數(shù)。同時也注意到當(dāng)標(biāo)簽個數(shù)少于50時,，改進算法性能下降,，這是因為此時標(biāo)簽數(shù)接近分群的群數(shù)導(dǎo)致空傳率上升所致，解決的辦法是減少分群的群數(shù),。針對該問題,，特設(shè)計仿真2來分析,。

?

　　仿真2：為了分析低標(biāo)簽密度時改進算法的性能，特設(shè)計以下仿真：采用改進算法,，分別使用5～8位寄存器,，高1～4位為高位，即分群群數(shù)分別為2,、4,、8和16。仿真結(jié)果如圖3所示,，可以看到當(dāng)標(biāo)簽總數(shù)為20時,，如果把高位寄存器的位數(shù)從4降到1，則平均碰撞次數(shù)從5.5回落到1.4,。而當(dāng)標(biāo)簽總數(shù)為200和2000時,，高位寄存器位數(shù)的改變對平均碰撞次數(shù)的影響不大。因此如果在某次仲裁中出現(xiàn)多次空傳,，根據(jù)這個先驗知識,，讀寫器可以在下一次仲裁時指示標(biāo)簽改變寄存器高位個數(shù)，以此降低空傳率,，進而可以降低平均碰撞次數(shù)。
　　本文提出的防碰撞算法僅需在電子標(biāo)簽中配置1個8位寄存器,、1個1位“0”,、“1”隨機數(shù)產(chǎn)生器和2個4位加減1計數(shù)器以及少量選擇電路就能實現(xiàn)最多達1 048 576個標(biāo)簽的仲裁。仿真表明本算法產(chǎn)生的碰撞概率明顯小于二進制數(shù)算法,，同時通過寄存器高位的靈活設(shè)置,，還能有效解決低標(biāo)簽密度時空傳率高的問題，從而進一步降低了碰撞概率,。本算法實現(xiàn)簡單,，復(fù)雜度低，非常適合在RFID系統(tǒng)中應(yīng)用,，因而具有廣闊的應(yīng)用前景,。
參考文獻
1 ISO18000-6C標(biāo)準(zhǔn)：Information technology-Radio-frequency identification for item management - Part 6C: Parameters for air interface communications at 860 MHz to 960MHz.
2 ISO18000-6A/B標(biāo)準(zhǔn):Information technology automatic iden-tification and data capture techniques - Radio frequency identification for item management air interface-Part 6:Parameters for air interface communications at 860-960MHz.
3 Fukmnizu Y, Ohno S, Nagata M, etc. A highly collision resistive RFID system. In：proc. of APSITT 2003, Nov.2003:223～228
4 Zhou, F, Jing, D, Huang C et al. Optimizing the power consumption of passive electronic tags for Anti-collision schemes. In:Proceedings of the 5th ASICON, Beijing,China, October 2003:1213～1217