一種新穎的RFID的防沖突算法

無線射頻識(shí)別（rfid）是一種非接觸式的自動(dòng)識(shí)別技術(shù)，其基本原理是利用射頻信號和空間耦合（電感或電磁耦合）的傳輸特性，實(shí)現(xiàn)對特定物體的自動(dòng)識(shí)別，rfid技術(shù)可以追溯至第二次世界大戰(zhàn)期間，后來發(fā)展應(yīng)用到鐵路、軍隊(duì)和貨物跟蹤甚至寵物識(shí)別上，在過去的半個(gè)多世紀(jì)里，rfid的發(fā)展經(jīng)歷了從技術(shù)探索、實(shí)驗(yàn)研究、商業(yè)應(yīng)用和標(biāo)準(zhǔn)化建立等幾個(gè)重要階段，從現(xiàn)有的發(fā)展趨勢看，rfid將構(gòu)建虛擬世界與物理世界的橋梁，可以預(yù)見在不久的將來，rfid技術(shù)不僅會(huì)在各行各業(yè)被廣泛采用，最終rfid技術(shù)還將會(huì)與普適計(jì)算技術(shù)相融合，對人類社會(huì)產(chǎn)生深遠(yuǎn)影響。

rfid系統(tǒng)一般由電子標(biāo)簽和讀寫器兩個(gè)部分組成，讀寫器具有同時(shí)讀取多個(gè)電子標(biāo)簽的功能，在多標(biāo)簽對一個(gè)讀寫器的rfid系統(tǒng)中，標(biāo)簽常會(huì)同時(shí)向讀寫器傳輸數(shù)據(jù)，這就要求rfid系統(tǒng)建立一種仲裁機(jī)制來避免數(shù)據(jù)發(fā)生碰撞，考慮到電子標(biāo)簽本身尺寸、能耗的限制，防碰撞機(jī)制在保障功能的同時(shí)還要求盡量簡單易行，這正是rfid系統(tǒng)設(shè)計(jì)的挑戰(zhàn)之一。

文獻(xiàn)[1]和[2]提出三種rfid系統(tǒng)的防碰撞算法。算法a基于隨機(jī)避讓、沖突檢測的原理，使用1個(gè)8位寄存器和1個(gè)8位隨機(jī)數(shù)產(chǎn)生器，最大可以仲裁標(biāo)簽的數(shù)量只有256個(gè)，算法b基于二進(jìn)制數(shù)的原理，使用1個(gè)8位寄存器和1個(gè)1位隨機(jī)數(shù)產(chǎn)生器，理論上最大可以實(shí)現(xiàn)2256個(gè)標(biāo)簽的仲裁。文獻(xiàn)[3]提出的對該算法的一個(gè)實(shí)現(xiàn)方案，文獻(xiàn)[4]對該算法作了很大改進(jìn)，算法c類似于算法a，使用1個(gè)16位寄存器和16個(gè)1位隨機(jī)數(shù)產(chǎn)生器，最大可以仲裁標(biāo)簽的數(shù)量是65536個(gè)。本文中，作者提出一種分群避讓、群內(nèi)沖突檢測的算法和其改進(jìn)算法，僅需要1個(gè)8位寄存器和1個(gè)1位隨機(jī)數(shù)產(chǎn)生器就可以實(shí)現(xiàn)最大1048576個(gè)標(biāo)簽的沖裁，而且碰撞次數(shù)相對于算法b要大大減少。

1 仲裁機(jī)制描述

本方法的核心思想是：首先把電子標(biāo)簽隨機(jī)分群，并將群隨機(jī)排序以實(shí)現(xiàn)群間的隨機(jī)避讓，然后在群內(nèi)進(jìn)行沖突檢測和標(biāo)簽的仲裁，實(shí)現(xiàn)時(shí)標(biāo)簽僅需一個(gè)寄存器：利用其高位存儲(chǔ)群號，低位存儲(chǔ)沖突檢測時(shí)退避的步數(shù)，實(shí)現(xiàn)極為簡單。下面以8位寄存器為例具體說明本算法的仲裁機(jī)制。

當(dāng)讀寫器初始化標(biāo)簽時(shí)，所有標(biāo)簽在0－15之間任選一個(gè)整數(shù)存入寄存器高4位（相當(dāng)于隨機(jī)權(quán)利一個(gè)群）并把寄存器低4位設(shè)為全0，同時(shí)產(chǎn)生一個(gè)0或1的隨機(jī)數(shù)加到寄存器中。如果此是寄存器中的8比特?cái)?shù)為全0則回傳該標(biāo)簽的id（id是指電子標(biāo)簽的唯一標(biāo)識(shí)，在不同的編碼系統(tǒng)中有不同的含義）。如果多個(gè)標(biāo)簽同時(shí)回傳數(shù)據(jù)，則沖突發(fā)生，發(fā)生沖突后，其他寄存器高4位為0的標(biāo)簽寄存器中的數(shù)加1，而寄存器中的8比特?cái)?shù)為全0的標(biāo)簽則再產(chǎn)生一個(gè)0或1的隨機(jī)數(shù)加到寄存器中。如果寄存器作加法后仍為全零，則繼續(xù)回傳該標(biāo)簽的id；如果回傳時(shí)不發(fā)生碰撞，則其他寄存器高4位為0的標(biāo)簽僅把寄存器低4位減1后重復(fù)前面的回傳操作。當(dāng)寄存器高4位全為0的標(biāo)簽全部回傳完id，則所有其他標(biāo)簽把寄存器高4位減1后重復(fù)前面的操作。

此外依本算法，由于所有標(biāo)簽隨機(jī)選擇群，有可能會(huì)出現(xiàn)某個(gè)群中的標(biāo)簽數(shù)目過大，使該群中的標(biāo)簽在仲裁過程中始終發(fā)生碰撞，標(biāo)簽寄存器始終加1，導(dǎo)致寄存器低4位向高4位進(jìn)位。進(jìn)位意味著所有進(jìn)位的標(biāo)簽的寄存器低4位清零而高4位加1，這使得這些標(biāo)簽不再屬于原有的群而歸入到下一個(gè)群中，從而優(yōu)化了因隨機(jī)選擇而產(chǎn)生的分布不均勻的群標(biāo)簽數(shù)。

本算法中，標(biāo)簽最大退讓步數(shù)為24＝16步，因此每個(gè)群最大能仲裁的標(biāo)簽數(shù)目為216＝65536，則本算法能仲裁的標(biāo)簽數(shù)理論上限是16×216＝1048576。

2 算法步驟

本節(jié)給出算法步驟，假設(shè)使用一個(gè)8位寄存器，則本算法包括以下步驟：

（1）在所述rfid系統(tǒng)的被動(dòng)方－標(biāo)簽中設(shè)計(jì)一個(gè)4＋4位的寄存器（rel）和1個(gè)“0”、“1”隨機(jī)數(shù)產(chǎn)生器（rg1），如圖1所示。

（2）在所述rfid系統(tǒng)的主動(dòng)方－讀寫器向所有處在等待態(tài)的標(biāo)簽發(fā)送初始化命令，標(biāo)簽因此進(jìn)入仲裁態(tài)，用rg1產(chǎn)生4比特隨機(jī)數(shù)，加載到rel高4位r7－r4，低4位r3－r0全部清零。

（3）讀寫器等待一定時(shí)間后發(fā)送允許回傳命令。

（4）rel為全零的標(biāo)簽向讀寫器件回傳標(biāo)簽id。

（5）如果當(dāng)前只有一個(gè)標(biāo)簽回轉(zhuǎn)id，讀寫器正確讀取該id，則發(fā)送確認(rèn)命令，附加命令參數(shù)“低位減1”?；貍髁薸d的標(biāo)簽接收到該命令后，進(jìn)入確認(rèn)態(tài)，其他高4位為全零的標(biāo)簽rel低4位減1，回到步驟（4）重復(fù)操作。

（6）如果當(dāng)前有多個(gè)標(biāo)簽會(huì)回傳id，讀寫器通過crc校驗(yàn)或碼長校驗(yàn)，檢測到錯(cuò)誤的id號，則發(fā)送確認(rèn)命令，附加命令參數(shù)“寄存器加1”，接收到讀寫器這個(gè)命令后，所有在仲裁態(tài)且rel為全零的標(biāo)簽由rg1產(chǎn)生1比特隨機(jī)數(shù)和寄存器上的數(shù)相加后重新載入到寄存器中，其他仲裁態(tài)且rel高4位為零而低4位不為零的標(biāo)簽rel加1，回到步驟（4）重復(fù)操作。

（7）如果當(dāng)前沒有標(biāo)簽回傳id，讀寫器等待一定時(shí)間后發(fā)送確認(rèn)命令，附加命令參數(shù)“低位減1”，所有在仲裁且高4位全零的標(biāo)簽rel低4位減1，回到步驟（4）重復(fù)操作。

（8）低4減1操作重復(fù)l次（l是一個(gè)系統(tǒng)參數(shù)，由系統(tǒng)設(shè)定，經(jīng)驗(yàn)值為4）后，讀寫器認(rèn)為所有在仲裁態(tài)且寄存器4位為零的標(biāo)簽都已經(jīng)被正確讀取，則發(fā)送確認(rèn)命令，附加命令參數(shù)“高4位減1”，回到步驟（4）。

（9）標(biāo)簽接收到附加“高位減1”參數(shù)的確認(rèn)命令后，所有rel高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)讀寫器鑒別命令時(shí)進(jìn)入的狀態(tài)；確認(rèn)態(tài)是指已被讀寫器鑒別的電子標(biāo)簽進(jìn)入的狀態(tài)，電子標(biāo)簽狀態(tài)轉(zhuǎn)移規(guī)則如下：上電后電子標(biāo)簽進(jìn)入等待態(tài)，處于等待態(tài)的電子標(biāo)簽可以進(jìn)入仲裁調(diào)態(tài)，處于仲裁態(tài)的電子標(biāo)簽可以返回等待態(tài)，處于仲裁態(tài)的電子標(biāo)簽可以進(jìn)入確認(rèn)態(tài)，處于確認(rèn)態(tài)的電子標(biāo)簽不能返回仲裁態(tài)；確認(rèn)態(tài)與等待態(tài)之間不能直接轉(zhuǎn)移。

針對上述算法步驟，在以下幾個(gè)地方加以改進(jìn)，形成本算法的改進(jìn)算法。

a、步驟（1）中，隨機(jī)數(shù)產(chǎn)生器產(chǎn)生兩組隨機(jī)數(shù)，分別加載寄存器高位和低4位，其中高位加載的位數(shù)m可以動(dòng)態(tài)設(shè)為1、2、3、或4。

b、步驟（10）中的重復(fù)操作次數(shù)為2m次，因?yàn)楦倪M(jìn)算法在寄存器第4位也加載了隨機(jī)數(shù)，使得標(biāo)簽在群間轉(zhuǎn)移的概率（即低4位向高位進(jìn)位的概率）大大增加，特別如果最后一個(gè)群中標(biāo)簽的寄存器低4位在退讓步驟中進(jìn)位，則會(huì)產(chǎn)生一個(gè)新群，因此需要額外增加一次高位減1操作。

3 電路實(shí)現(xiàn)

算法實(shí)現(xiàn)的電路框圖見圖1，其中rg1是一個(gè)“0”“1”隨機(jī)數(shù)產(chǎn)生器，rel是一個(gè)8位寄存器。加法器add1和add2的加減功能根據(jù)讀寫器命令來設(shè)定，當(dāng)執(zhí)行加法操作時(shí)，低4位的add2需向高4位的add1進(jìn)位；當(dāng)執(zhí)行減法操作時(shí)，兩個(gè)器件add1和add2相互獨(dú)立，加法器可以工作在同步狀態(tài)或異步狀態(tài)，工作在同步狀態(tài)時(shí)可以使用電子標(biāo)簽的最大時(shí)鐘。

4 仿真結(jié)果

仿真1：為了評估本算法的優(yōu)劣，特設(shè)計(jì)以下仿真：標(biāo)簽使用8位寄存器，高4位為高位。定義0個(gè)、2個(gè)和2個(gè)以上的標(biāo)簽同時(shí)發(fā)送數(shù)據(jù)時(shí)為傳輸沖突，只有一個(gè)標(biāo)簽發(fā)送數(shù)據(jù)時(shí)為傳輸成功，平均沖突次數(shù)定義為傳輸沖突總次數(shù)和傳輸成功總次數(shù)的比；空傳率定義0個(gè)標(biāo)簽發(fā)送數(shù)據(jù)的次數(shù)與傳輸成功總次數(shù)的比。觀察標(biāo)簽數(shù)為20－10000時(shí)的平均沖突次數(shù)。

仿真結(jié)果如圖2所示，本文提出的算法與二進(jìn)制算法性能接近，平均每成功傳輸1次都要伴隨2次傳輸沖突；而改進(jìn)算法則標(biāo)簽數(shù)為50－5000個(gè)時(shí)明顯減少了碰撞次數(shù)，同時(shí)也注意到當(dāng)標(biāo)簽個(gè)數(shù)小于50時(shí)，改進(jìn)算法性能下降，這是因?yàn)榇藭r(shí)標(biāo)簽數(shù)接近分群的群數(shù)導(dǎo)致空傳率上升所致，解決的辦法是減少分群的群數(shù)，針對該問題，特設(shè)仿真2來分析。

仿真2：為了分析低標(biāo)簽密度時(shí)改進(jìn)算法的性能，特設(shè)計(jì)以下仿真：采用改進(jìn)算法，分別使用5－8位寄存器，高1－4位為高位，即分群群數(shù)分別為2、4、8和16。仿真結(jié)果如圖3所示，可以看到的當(dāng)標(biāo)簽總數(shù)為20時(shí)，如果把高位寄存器的為數(shù)從4降到1，則平均碰撞次數(shù)從5.5回落到1.4。而當(dāng)標(biāo)簽總數(shù)為200和2000時(shí)，高位寄存器的位數(shù)的改變對平均碰撞次數(shù)的影響不大。因此如果某次仲裁中出現(xiàn)多次空傳，根據(jù)這個(gè)先驗(yàn)知識(shí)，讀寫器可以在下一次仲裁時(shí)指示標(biāo)簽改變寄存器高位個(gè)數(shù)，以此降低空傳率，進(jìn)而可以降低平均碰撞次數(shù)。

本文提出的防碰撞算法僅需在電子標(biāo)簽中配置1個(gè)8位寄存器、1個(gè)1位“0”、“1”隨機(jī)數(shù)產(chǎn)生器和2個(gè)4位加減1計(jì)數(shù)器以及少量選擇電路就能實(shí)現(xiàn)最多達(dá)1048576個(gè)標(biāo)簽的仲裁，仿真表明本算法產(chǎn)生的碰撞概率明顯小于二進(jìn)制算法，同時(shí)通過寄存器高位的靈活設(shè)置，還能有效解決低標(biāo)簽密度時(shí)空傳率高的問題，從而進(jìn)一步降低了碰撞概率。本算法實(shí)現(xiàn)簡單，復(fù)雜度低，非常適合在rfid系統(tǒng)中應(yīng)用，因而具有廣闊的應(yīng)用前景。