RFID系統(tǒng)中多電子標(biāo)簽防碰撞改進算法

射頻識別(RFID)技術(shù)是一種非接觸式的自動識別技術(shù)，通常由讀寫器、電子標(biāo)簽和計算機數(shù)據(jù)管理系統(tǒng)三部分組成，通過DSRC短程通信技術(shù)進行數(shù)據(jù)傳輸和交換。RFID系統(tǒng)工作時，如果遇到兩個以上電子標(biāo)簽都在讀寫器信號的覆蓋范圍內(nèi)，則各個電子標(biāo)簽會同時對讀寫器發(fā)出信號，從而造成各電子標(biāo)簽間數(shù)據(jù)的碰撞，使讀寫器不能正常讀取各個電子標(biāo)簽內(nèi)的有關(guān)數(shù)據(jù)，這就是RFID系統(tǒng)中的多路存取問題。因此只有解決好電子標(biāo)簽的碰撞問題，才能使RFID系統(tǒng)正常工作，而解決電子標(biāo)簽防碰撞問題的關(guān)鍵是優(yōu)化的防碰撞算法。

現(xiàn)有的RFID防碰撞算法都是基于TDMA算法，可劃分為Aloha防碰撞算法和基于二進制搜索BS(Binary search)算法兩大類。Aloha是一種隨機接入算法，這種算法多采取“標(biāo)簽先發(fā)言”的方式，即標(biāo)簽一旦進入閱讀器的閱讀區(qū)域就自動向閱讀器發(fā)送其自身的ID，隨即標(biāo)簽和閱讀器間開始通信。在標(biāo)簽發(fā)送數(shù)據(jù)的過程中，若有其他標(biāo)簽也在發(fā)送數(shù)據(jù)，將發(fā)生信號重疊從而導(dǎo)致完全沖突或部分沖突，閱讀器檢測接收到的信號來判斷有無沖突。如果發(fā)生沖突，閱讀器將發(fā)送命令讓標(biāo)簽停止發(fā)送，隨機等待一段時間后再重新發(fā)起查詢。該算法特點是：算法簡單、便于實現(xiàn)，適用于低成本RFID系統(tǒng)。但是由于該算法的時隙是隨機分配的，當(dāng)大量標(biāo)簽并存時，幀沖突嚴(yán)重。而基于BS算法是通過多次比較，不斷篩選出不同的標(biāo)簽號，時分復(fù)用地進行讀寫器和射頻卡之間的信號交換，以一個獨特的序列號識別射頻卡為基礎(chǔ)。為了從一組射頻卡中選出其中的一個，讀寫器需要發(fā)出一個請求命令，有意識地將射頻卡序列號傳輸時的數(shù)據(jù)碰撞引導(dǎo)到讀寫器上，即讓讀寫器來判斷是否發(fā)生碰撞。如發(fā)生碰撞，則縮小范圍進行進一步搜索。這類算法雖然識別效率高，但是算法比較復(fù)雜，識別時間較長。本文在二進制防碰撞算法的基礎(chǔ)上提出一種改進的防碰撞算法。

1兩種典型的二進制防碰撞算法的分析

1.1二進制搜索算法

實現(xiàn)BS算法系統(tǒng)的必要前提是能夠辨認(rèn)出在讀寫器中數(shù)據(jù)沖突位的準(zhǔn)確位置，因此必須選用合適的編碼。曼徹斯特編碼能夠按位識別出碰撞位，這樣可以根據(jù)碰撞的位置，按一定的規(guī)則重新搜索標(biāo)簽。因此，使用曼徹斯特編碼是實現(xiàn)二進制搜索防碰撞算法的必要前提。BS算法的工作流程如下：

(1)電子標(biāo)簽進入讀寫器的作用范圍時，讀寫器發(fā)送命令REQUEST(≤11111111)，所有滿足此條件的電子標(biāo)簽響應(yīng)此命令，并將自己的EPC號傳給讀寫器。

(2)讀寫器對比電子標(biāo)簽響應(yīng)的EPC碼相同位數(shù)上的數(shù)，根據(jù)Manchester編碼規(guī)則，若出現(xiàn)不一致現(xiàn)象，即可判斷出該比特位有碰撞。

(3)當(dāng)確定有碰撞后，將此次發(fā)生碰撞的最高位置“0”，最高碰撞位之前的比特位不變，最高碰撞位后的所有比特位都置“1”，并產(chǎn)生新的請求命令REQUEST，依次排除序列號大的標(biāo)簽，直到讀寫器對比電子標(biāo)簽響應(yīng)的序列號中相同位數(shù)上的數(shù)完全一致時，則說明無碰撞。此時，使用選擇命令(SELECT)選出一個唯一的標(biāo)簽。

(4)選出唯一的標(biāo)簽后，使用READ-DATA命令完成讀寫器與該電子標(biāo)簽的數(shù)據(jù)交換。并使用選擇命令(UNSELECT)進入“無聲”狀態(tài)，此時在讀寫器范圍內(nèi)不再響應(yīng)(重新進入讀寫器范圍可再次響應(yīng))。為了重新激活電子標(biāo)簽，必須進行復(fù)位操作。

(5)重復(fù)前4個步驟，并選擇剩余的電子標(biāo)簽數(shù)據(jù)交換。多次循環(huán)后即可完成所有電子標(biāo)簽的讀取。

1.2動態(tài)二進制搜索算法(DBS)

在BS搜索算法中，從讀寫器和單個電子標(biāo)簽的數(shù)據(jù)流可以看出，讀寫器發(fā)出的請求命令中，最高碰撞位后的所有比特位都被置“1”，對標(biāo)簽的識別不能提供任何的信息。而標(biāo)簽返回的數(shù)據(jù)中，最高碰撞位以前的比特位及最高碰撞位不包含給讀寫器的補充信息，因為這些位是已知且給定的，屬于多余的重復(fù)信息。基于此人們提出了動態(tài)二進制搜索算法(DBS)，當(dāng)讀寫器檢測到碰撞后，下一次讀寫器在請求命令中只發(fā)送搜索序列號中的最高位和最高碰撞位之間的部分作為搜索依據(jù)，然后中斷傳輸，所有在與最高位和最高碰撞位之間的部分相同的電子標(biāo)簽響應(yīng)并送回它們序列號的剩余各位，即最高碰撞位之后的比特位作為應(yīng)答。因此，DBS算法避免了序列號中多余部分的傳輸，數(shù)據(jù)傳輸時間明顯縮短。DBS算法較BS算法在傳輸數(shù)據(jù)量和所需時間上可減少50%。

2改進的二進制搜索算法

2.1算法約定

鑒于BS算法的缺點，本文提出了一種改進的二進制搜索算法，算法約定如下：

(1)采用曼徹斯特編碼的電子標(biāo)簽序列號每個比特位上的取值不是“0”就是“1”。因此，如果當(dāng)讀寫器探測到僅有一位碰撞位時，讀寫器不需要發(fā)送請求命令，可以直接識別出2個標(biāo)簽。

(2)讀寫器如果檢測到有N個碰撞位，則說明這N個碰撞位的比特位對讀寫器來說是未知的，而其他的比特位對讀寫器來說是已知的。因此讀寫器只需要對未知的碰撞位處理，而不需要傳輸那些已知的比特位，從而減少傳輸時延。

為了便于描述以及實現(xiàn)該算法，給出如下防碰撞命令：

①查詢命令request(DX，MX;DX1，MX1)。參數(shù)DX、DX1分別為檢測到碰撞位的最高位和次高位，參數(shù)MX、MX1為0、1的二維排列組合，例如檢測到1?1?00?1，那么讀寫器發(fā)送request(D6，0;D4，0)符合條件的標(biāo)簽響應(yīng)并返回沖突位及相關(guān)信息。

②退出選擇命令unselect.取消事先選中的電子標(biāo)簽，使標(biāo)簽進入“無聲”狀態(tài)。在這種狀態(tài)下標(biāo)簽完全是非激活的，對收到的request命令不做應(yīng)答。為了重新激活標(biāo)簽，必須暫時離開讀寫器的作用范圍，然后再次進入該讀寫器范圍。

2.2算法原理

下面以讀寫器作用范圍內(nèi)的8個編碼為8 bit的標(biāo)簽為例說明該算法，8個標(biāo)簽的編碼如下：tag1：01001000，tag2：01010100，tag3：01011010，tag4：01000000，tag5：01000010，

tag6：01010000，tag7：01001010，tag8：01011000.

(1)request≤11111111命令，讀寫器作用范圍內(nèi)的所有標(biāo)簽應(yīng)答，讀寫器譯碼的結(jié)果為010????0碰撞位為D4，D3，D2，D1，最高碰撞位為D4，次高碰撞位為D3，因此下次查詢命令為request(D4，0;D3，0)。

(2)讀寫器發(fā)送查詢命令request(D4，0;D3，0)，標(biāo)簽通過比較各自的D4、D3位，與之相同的標(biāo)簽則發(fā)送自己的相關(guān)信息給讀寫器。通過比較后標(biāo)簽4和標(biāo)簽5響應(yīng)，編碼后得到010000?0，讀寫器檢測到僅只有一位碰撞，可以直接識別出標(biāo)簽4和標(biāo)簽5.讀寫器正確識別它們之后，執(zhí)行unselect命令，使標(biāo)簽4和標(biāo)簽5處于“無聲”狀態(tài)。

(3)讀寫器發(fā)送查詢命令request(D4，0;D3，1)，標(biāo)簽1和標(biāo)簽7響應(yīng)，編碼后得到010010?0，讀寫器檢測到僅只有一位碰撞，可以直接識別出標(biāo)簽1和標(biāo)簽7.讀寫器正確識別它們之后，執(zhí)行unselect命令，使標(biāo)簽1和標(biāo)簽7處于“無聲”狀態(tài)。

(4)讀寫器發(fā)送查詢命令request(D4，1;D3，0)，標(biāo)簽2和標(biāo)簽6響應(yīng)，編碼后得到01010?00，讀寫器檢測到僅只有一位碰撞，可以直接識別出標(biāo)簽2和標(biāo)簽6.讀寫器正確識別它們之后，執(zhí)行unselect命令，使標(biāo)簽1和標(biāo)簽7處于“無聲”狀態(tài)。

(5)讀寫器發(fā)送查詢命令request(D4，1;D3，1)，標(biāo)簽3和標(biāo)簽8響應(yīng)，編碼后得到010110?0，讀寫器檢測到僅只有一位碰撞，可以直接識別出標(biāo)簽3和標(biāo)簽8.讀寫器正確識別它們之后，執(zhí)行unselect命令，使標(biāo)簽1和標(biāo)簽7處于“無聲”狀態(tài)。至此，讀寫器作用范圍內(nèi)的所有標(biāo)簽都別正確識別完畢。算法流程如圖1所示。

3算法性能比較

假設(shè)讀寫器作用范圍內(nèi)有N個電子標(biāo)簽，則BS算法完成所有標(biāo)簽識別的搜索命令次數(shù)S(N)為：

通過理論和仿真比較，采用改進后的二進制搜索算法較其他兩個算法有三個方面的優(yōu)勢：其一減少了查詢標(biāo)簽次數(shù)，使計算時間減小;其二減少了系統(tǒng)數(shù)據(jù)傳輸量，提高了標(biāo)簽的識別速率;其三較大地提高了系統(tǒng)的吞吐率。

本文對BS算法及DBS算法過程進行了分析，找出了其中的不足之處，在此基礎(chǔ)上提出了一種改進的二進制搜索算法，并通過Matlab仿真得到該算法的查詢次數(shù)和吞吐率方面的數(shù)據(jù)。通過實驗數(shù)據(jù)表明，該改進算法可以減少系統(tǒng)的查詢次數(shù)，提高系統(tǒng)的吞吐率。從而驗證了該改進算法的優(yōu)越性。