登錄
注冊
RFID世界網(wǎng) >
技術文章 >
其他 >
正文
一種新穎的RFID防沖突算法
作者：張明 張建華 徐國鑫 張平
來源：RFID世界網(wǎng)
日期：2007-06-11 15:47:20
摘要：提出一種應用于RFID系統(tǒng)上行鏈路的多標簽沖突檢測算法，并給出了參考安現(xiàn)電路。依算法，對電子標簽進行隨機分群，在群間做隨機避讓，在群內(nèi)進行沖突檢測和標簽的仲裁。與現(xiàn)有的隨機避讓算法和二進制樹算法相比，該算法不但有效降低了碰撞次數(shù)，實現(xiàn)電路也更簡單。
無線射頻識別(RFID)是一種非接觸式的自動識別技術，其基本原理是刺用射頻信號和空間耦合(電感或電磁耦合)的傳輸特性，實現(xiàn)對特定物體的自動識別。RFID技術可以追溯至第二次世界大戰(zhàn)期間。后來發(fā)展應用到鐵路、軍隊的貨物跟蹤甚至寵物識別上。在過去的半個多世紀里，RFID的發(fā)展經(jīng)歷了從技術探索、試驗研究、商業(yè)應用和標準化建立等幾個重要階段。從現(xiàn)有發(fā)展趨勢看，RHD將構建虛擬世界與物理世界的橋梁?？梢灶A見在不久的將來，RFID技術不僅會在各行各業(yè)被廣泛采用，最終RFID技術還將會與普適計算技術相融合，對人類社會產(chǎn)生深遠影響。
RFID系統(tǒng)一般由電子標簽和讀寫器兩個部分組成，讀寫器具有同時讀取多個電子標簽的功能。在多標簽對一個讀寫器的RFID系統(tǒng)中，標簽經(jīng)常會同時向讀寫器傳輸數(shù)據(jù)，這就要求RFID系統(tǒng)建立一種仲裁機制來避免數(shù)據(jù)發(fā)生碰撞。考慮到電子標簽本身尺寸、能耗的限制，防碰撞機制在保障功能的同時還要求盡量簡單易行，這正是RFID系統(tǒng)設計的挑戰(zhàn)之一。
文獻[1]和[2]提出了三種RFID系統(tǒng)的防碰撞算法。
算法A基于隨機避讓、沖突檢測的原理，使用1個8位寄存器和1個8位隨機數(shù)產(chǎn)生器，最大可以仲裁標簽的數(shù)量只有256個。算法B基于二進制數(shù)的原理，使用1個8位寄存器和1個l位隨機數(shù)產(chǎn)生器，理論上最大可以實現(xiàn)2256個標簽的仲裁。文獻提出了對該算法的一個實現(xiàn)方案，文獻對該算法做了很大改進。算法C類似于算法A，使用1個16位寄存器和16個l位隨機數(shù)產(chǎn)生器，最大可以仲裁標簽的數(shù)量是65536個。本文中，作者提出一種分群避讓、群內(nèi)沖突檢測的算法和其改進算法，僅需要1個8位寄存器和1個1位隨機數(shù)產(chǎn)生器就可以實現(xiàn)最大1048 576個標簽的仲裁．而且碰撞次數(shù)相對干算法B要大大減少。
1 仲裁機制描述
本算法中，標簽最大退讓步數(shù)為24=16步，因此每個群最大能仲裁的標簽數(shù)目為216=65536，則本算法能仲裁的標簽數(shù)理論上限是16×216=1048576。
2 算法步驟
本節(jié)給出算法步驟，假設使用一個8位寄存器，則本算法包括以下步驟：
(1)在所述RFID系統(tǒng)的被動方一標簽中設計一個4+4位的寄存器(Rel)和1個“0”、“l(fā)”隨機數(shù)產(chǎn)生器(RGI)，如圖l所示。
(2)在所述RFID系統(tǒng)的主動方一讀寫器向所有處在等待態(tài)的標簽發(fā)送初始化命令。標簽因此進入仲裁態(tài)，用RGI產(chǎn)生4比特隨機數(shù)，加載到Rel高4位R7~R4，低4位R3~R0全部清零。
(3)讀寫器等待一定時間后發(fā)送允許回傳命令。
(4)Rel為全零的標簽向讀寫器回傳標簽ID。
(5)如果當前只有一個標簽回傳ID，讀寫器正確讀取該ID，則發(fā)送確認命令，附加命令參數(shù)“低位減l”。回傳了ID的標簽接收到該命令后，進入確認態(tài)，其他高4位為全零的標簽Re1低4位減1，回到步驟(4)重復操作。
(6)如果當前有多個標簽回傳ID，讀寫器通過CRC校驗或碼長校驗，檢測到錯誤的ID號，則發(fā)送確認命令，附加命令參數(shù)“寄存器加1”。接收到讀寫器這個命令后，所有在仲裁態(tài)且Rel為全零的標簽由RGI產(chǎn)生1比特隨機數(shù)和寄存器上的數(shù)相加后重新載入到寄存器中；其他仲裁態(tài)且Rel高4位為零而低4位不為零的標簽Rel加1，回到步驟(4)重復操作。
(7)如果當前沒有標簽回傳ID，讀寫器等待一定時間后發(fā)送確認命令，附加命令參數(shù)“低位減1”。所有在仲裁態(tài)且高4為全零的標簽Rel低4位減1，回到步驟(4)重復操作。
(8)低4位減1操作重復L次(L是一個系統(tǒng)參數(shù)，由系統(tǒng)設定，經(jīng)驗值為4)后，讀寫器認為所有在仲裁態(tài)且寄存器高4位為零的標簽都已經(jīng)被正確讀取，則發(fā)送確認命令，附加命令參數(shù)“高4位減l”，回到步驟(4)。
(9)標簽接收到附加“高位減l”參數(shù)的確認命令后，所有Rel高4位不為零的標簽高4位減l，回到步驟4重復操作；在被要求高位減1前已為零的標簽則回到等待態(tài)。
(10)重復15次高位減1操作后．讀寫器認為所有在仲裁態(tài)的標簽都已經(jīng)被讀取，則仲裁過程停止，所有還處于仲裁態(tài)的標簽返回等待態(tài)。
算法步驟中所述等待態(tài)是指電子標簽上電后的初始狀態(tài)；仲裁態(tài)是指未被讀寫器鑒別的電子標簽開始響應讀寫器鑒別命令時進入的狀態(tài)；確認態(tài)是指已被讀寫器鑒別的電子標簽進入的狀態(tài)。電子標簽狀態(tài)轉移規(guī)則如下：上電后電子標簽進入等待態(tài)；處于等待態(tài)的電子標簽可以進入仲裁態(tài)；處于仲裁態(tài)的電子標簽可以返回等待態(tài)；處于仲裁態(tài)的電子標簽可以進入確認態(tài)；處于確認態(tài)的電子標簽不能返回仲裁態(tài)；確認態(tài)與等待態(tài)之間不能直接轉移。
針對上述算法步驟，在以下幾個地方加以改進，形成本算法的改進算法。
A、步驟(1)中，隨機數(shù)產(chǎn)生器產(chǎn)生兩組隨機數(shù)，分別加載到寄存器高位和低4位。其中高位加載的位數(shù)M可以動態(tài)設為1、2、3或4。
B、步驟(10)中的重復操作次數(shù)為2M次。因為改進算法在寄存器低4位也加載了隨機數(shù)，使得標簽在群間轉移的概率(即低4位向高位進位的概率)大大增加，特別如果最后一個群中標簽的寄存器低4位在退讓步驟中進位，則會產(chǎn)生一個新群，因此需要額外增加一次高位減l操作。
3 電路實現(xiàn)
算法實現(xiàn)的參考電路框圖見圖l，其中RGI是一個“0”“1”隨機數(shù)產(chǎn)生器；Rel是一個8位寄存器。加法器ADDl和ADD2的加減功能根據(jù)讀寫器命令來設定：當執(zhí)行加法操作時，低4位的ADD2需向高4位的ADDl進位；當執(zhí)行減法操作時，兩個器件ADDl和ADD2相互獨立。加法器可以工作在同步狀態(tài)或異步狀態(tài)，工作在同步狀態(tài)時可以使用電子標簽的最大時鐘。
4 仿真結果
仿真l：為了評估本算法的優(yōu)劣，特設計以下仿真：標簽使用8位寄存器，高4位為高位。定義0個、2個和2個以上的標簽同時發(fā)送數(shù)據(jù)時為傳輸沖突；只有一個標簽發(fā)送數(shù)據(jù)時為傳輸成功，平均沖突次數(shù)定義為傳輸沖突總次數(shù)和傳輸成功總次數(shù)的比；空傳率定義O個標簽發(fā)送數(shù)據(jù)的次數(shù)與傳輸成功總次數(shù)的比。觀察標簽數(shù)為20~10000時的平均沖突次數(shù)。
仿真結果如圖2所示，本文提出的算法與二進制算法性能接近，平均每成功傳輸1次都要伴隨2次傳輸沖突；而改進算法則在標簽數(shù)為50~5000個時明顯減少了碰撞次數(shù)。同時也注意到當標簽個數(shù)少于50時，改進算法性能下降，這是因為此時標簽數(shù)接近分群的群數(shù)導致空傳率上升所致，解決的辦法是減少分群的群數(shù)。針對該問題，特設計仿真2來分析。
仿真2：為了分析低標簽密度時改進算法的性能，特設計以下仿真：采用改進算法，分別使用5~8位寄存器。高l~4位為高位，即分群群數(shù)分別為2、4、8和16。仿真結果如圖3所示，可以看到當標簽總數(shù)為20時，如果把高位寄存器的位數(shù)從4降到l，則平均碰撞次數(shù)從5 5回落到1．4。而當標簽總數(shù)為200和2000時，高位寄存器位數(shù)的改變對平均碰撞次數(shù)的影響不大。因此如果在某次仲裁中出現(xiàn)多次空傳，根據(jù)這個先驗知識，讀寫器可以在下一次仲裁時指示標簽改變寄存器高位個數(shù)，以此降低空傳率，進而可以降低平均碰撞次數(shù)。
本文提出的防碰撞算法僅需在電子標簽中配置1個8位寄存器、1個l位“O”、“l(fā)”隨機數(shù)產(chǎn)生器和2個4位加減l 計數(shù)器以及少量選擇電路就能實現(xiàn)最多達1048 576個標簽的仲裁。仿真表明本算法產(chǎn)生的碰撞概率明顯小于二進制數(shù)算法，同時通過寄存器高位的靈活設置，還能有效解決低標簽密度時空傳率高的問題，從而進一步降低了碰撞概率。本算法實現(xiàn)簡單，復雜度低，非常適合在RFID系統(tǒng)中應用，因而具有廣闊的應用前景。
RFID系統(tǒng)一般由電子標簽和讀寫器兩個部分組成，讀寫器具有同時讀取多個電子標簽的功能。在多標簽對一個讀寫器的RFID系統(tǒng)中，標簽經(jīng)常會同時向讀寫器傳輸數(shù)據(jù)，這就要求RFID系統(tǒng)建立一種仲裁機制來避免數(shù)據(jù)發(fā)生碰撞。考慮到電子標簽本身尺寸、能耗的限制，防碰撞機制在保障功能的同時還要求盡量簡單易行，這正是RFID系統(tǒng)設計的挑戰(zhàn)之一。
文獻[1]和[2]提出了三種RFID系統(tǒng)的防碰撞算法。
算法A基于隨機避讓、沖突檢測的原理，使用1個8位寄存器和1個8位隨機數(shù)產(chǎn)生器，最大可以仲裁標簽的數(shù)量只有256個。算法B基于二進制數(shù)的原理，使用1個8位寄存器和1個l位隨機數(shù)產(chǎn)生器，理論上最大可以實現(xiàn)2256個標簽的仲裁。文獻提出了對該算法的一個實現(xiàn)方案，文獻對該算法做了很大改進。算法C類似于算法A，使用1個16位寄存器和16個l位隨機數(shù)產(chǎn)生器，最大可以仲裁標簽的數(shù)量是65536個。本文中，作者提出一種分群避讓、群內(nèi)沖突檢測的算法和其改進算法，僅需要1個8位寄存器和1個1位隨機數(shù)產(chǎn)生器就可以實現(xiàn)最大1048 576個標簽的仲裁．而且碰撞次數(shù)相對干算法B要大大減少。
1 仲裁機制描述
本算法中，標簽最大退讓步數(shù)為24=16步，因此每個群最大能仲裁的標簽數(shù)目為216=65536，則本算法能仲裁的標簽數(shù)理論上限是16×216=1048576。
2 算法步驟
本節(jié)給出算法步驟，假設使用一個8位寄存器，則本算法包括以下步驟：
(1)在所述RFID系統(tǒng)的被動方一標簽中設計一個4+4位的寄存器(Rel)和1個“0”、“l(fā)”隨機數(shù)產(chǎn)生器(RGI)，如圖l所示。
(2)在所述RFID系統(tǒng)的主動方一讀寫器向所有處在等待態(tài)的標簽發(fā)送初始化命令。標簽因此進入仲裁態(tài)，用RGI產(chǎn)生4比特隨機數(shù)，加載到Rel高4位R7~R4，低4位R3~R0全部清零。
(3)讀寫器等待一定時間后發(fā)送允許回傳命令。
(4)Rel為全零的標簽向讀寫器回傳標簽ID。
(5)如果當前只有一個標簽回傳ID，讀寫器正確讀取該ID，則發(fā)送確認命令，附加命令參數(shù)“低位減l”。回傳了ID的標簽接收到該命令后，進入確認態(tài)，其他高4位為全零的標簽Re1低4位減1，回到步驟(4)重復操作。
(6)如果當前有多個標簽回傳ID，讀寫器通過CRC校驗或碼長校驗，檢測到錯誤的ID號，則發(fā)送確認命令，附加命令參數(shù)“寄存器加1”。接收到讀寫器這個命令后，所有在仲裁態(tài)且Rel為全零的標簽由RGI產(chǎn)生1比特隨機數(shù)和寄存器上的數(shù)相加后重新載入到寄存器中；其他仲裁態(tài)且Rel高4位為零而低4位不為零的標簽Rel加1，回到步驟(4)重復操作。
(7)如果當前沒有標簽回傳ID，讀寫器等待一定時間后發(fā)送確認命令，附加命令參數(shù)“低位減1”。所有在仲裁態(tài)且高4為全零的標簽Rel低4位減1，回到步驟(4)重復操作。
(8)低4位減1操作重復L次(L是一個系統(tǒng)參數(shù)，由系統(tǒng)設定，經(jīng)驗值為4)后，讀寫器認為所有在仲裁態(tài)且寄存器高4位為零的標簽都已經(jīng)被正確讀取，則發(fā)送確認命令，附加命令參數(shù)“高4位減l”，回到步驟(4)。
(9)標簽接收到附加“高位減l”參數(shù)的確認命令后，所有Rel高4位不為零的標簽高4位減l，回到步驟4重復操作；在被要求高位減1前已為零的標簽則回到等待態(tài)。
(10)重復15次高位減1操作后．讀寫器認為所有在仲裁態(tài)的標簽都已經(jīng)被讀取，則仲裁過程停止，所有還處于仲裁態(tài)的標簽返回等待態(tài)。
算法步驟中所述等待態(tài)是指電子標簽上電后的初始狀態(tài)；仲裁態(tài)是指未被讀寫器鑒別的電子標簽開始響應讀寫器鑒別命令時進入的狀態(tài)；確認態(tài)是指已被讀寫器鑒別的電子標簽進入的狀態(tài)。電子標簽狀態(tài)轉移規(guī)則如下：上電后電子標簽進入等待態(tài)；處于等待態(tài)的電子標簽可以進入仲裁態(tài)；處于仲裁態(tài)的電子標簽可以返回等待態(tài)；處于仲裁態(tài)的電子標簽可以進入確認態(tài)；處于確認態(tài)的電子標簽不能返回仲裁態(tài)；確認態(tài)與等待態(tài)之間不能直接轉移。
針對上述算法步驟，在以下幾個地方加以改進，形成本算法的改進算法。
A、步驟(1)中，隨機數(shù)產(chǎn)生器產(chǎn)生兩組隨機數(shù)，分別加載到寄存器高位和低4位。其中高位加載的位數(shù)M可以動態(tài)設為1、2、3或4。
B、步驟(10)中的重復操作次數(shù)為2M次。因為改進算法在寄存器低4位也加載了隨機數(shù)，使得標簽在群間轉移的概率(即低4位向高位進位的概率)大大增加，特別如果最后一個群中標簽的寄存器低4位在退讓步驟中進位，則會產(chǎn)生一個新群，因此需要額外增加一次高位減l操作。
3 電路實現(xiàn)
算法實現(xiàn)的參考電路框圖見圖l，其中RGI是一個“0”“1”隨機數(shù)產(chǎn)生器；Rel是一個8位寄存器。加法器ADDl和ADD2的加減功能根據(jù)讀寫器命令來設定：當執(zhí)行加法操作時，低4位的ADD2需向高4位的ADDl進位；當執(zhí)行減法操作時，兩個器件ADDl和ADD2相互獨立。加法器可以工作在同步狀態(tài)或異步狀態(tài)，工作在同步狀態(tài)時可以使用電子標簽的最大時鐘。
4 仿真結果
仿真l：為了評估本算法的優(yōu)劣，特設計以下仿真：標簽使用8位寄存器，高4位為高位。定義0個、2個和2個以上的標簽同時發(fā)送數(shù)據(jù)時為傳輸沖突；只有一個標簽發(fā)送數(shù)據(jù)時為傳輸成功，平均沖突次數(shù)定義為傳輸沖突總次數(shù)和傳輸成功總次數(shù)的比；空傳率定義O個標簽發(fā)送數(shù)據(jù)的次數(shù)與傳輸成功總次數(shù)的比。觀察標簽數(shù)為20~10000時的平均沖突次數(shù)。
仿真結果如圖2所示，本文提出的算法與二進制算法性能接近，平均每成功傳輸1次都要伴隨2次傳輸沖突；而改進算法則在標簽數(shù)為50~5000個時明顯減少了碰撞次數(shù)。同時也注意到當標簽個數(shù)少于50時，改進算法性能下降，這是因為此時標簽數(shù)接近分群的群數(shù)導致空傳率上升所致，解決的辦法是減少分群的群數(shù)。針對該問題，特設計仿真2來分析。
仿真2：為了分析低標簽密度時改進算法的性能，特設計以下仿真：采用改進算法，分別使用5~8位寄存器。高l~4位為高位，即分群群數(shù)分別為2、4、8和16。仿真結果如圖3所示，可以看到當標簽總數(shù)為20時，如果把高位寄存器的位數(shù)從4降到l，則平均碰撞次數(shù)從5 5回落到1．4。而當標簽總數(shù)為200和2000時，高位寄存器位數(shù)的改變對平均碰撞次數(shù)的影響不大。因此如果在某次仲裁中出現(xiàn)多次空傳，根據(jù)這個先驗知識，讀寫器可以在下一次仲裁時指示標簽改變寄存器高位個數(shù)，以此降低空傳率，進而可以降低平均碰撞次數(shù)。
本文提出的防碰撞算法僅需在電子標簽中配置1個8位寄存器、1個l位“O”、“l(fā)”隨機數(shù)產(chǎn)生器和2個4位加減l 計數(shù)器以及少量選擇電路就能實現(xiàn)最多達1048 576個標簽的仲裁。仿真表明本算法產(chǎn)生的碰撞概率明顯小于二進制數(shù)算法，同時通過寄存器高位的靈活設置，還能有效解決低標簽密度時空傳率高的問題，從而進一步降低了碰撞概率。本算法實現(xiàn)簡單，復雜度低，非常適合在RFID系統(tǒng)中應用，因而具有廣闊的應用前景。
