RFID系統中多電子標簽防碰撞改進(jìn)算法

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

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

　　1兩種典型的二進(jìn)制防碰撞算法的分析

　　1.1二進(jìn)制搜索算法

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

　　(1)電子標簽進(jìn)入讀寫(xiě)器的作用范圍時(shí)，讀寫(xiě)器發(fā)送命令REQUEST(≤11111111)，所有滿(mǎn)足此條件的電子標簽響應此命令，并將自己的EPC號傳給讀寫(xiě)器。

　　(2)讀寫(xiě)器對比電子標簽響應的EPC碼相同位數上的數，根據Manchester編碼規則，若出現不一致現象，即可判斷出該比特位有碰撞。

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

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

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

　　1.2動(dòng)態(tài)二進(jìn)制搜索算法(DBS)

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

　　2改進(jìn)的二進(jìn)制搜索算法

　　2.1算法約定

　　鑒于BS算法的缺點(diǎn)，本文提出了一種改進(jìn)的二進(jìn)制搜索算法，算法約定如下：

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

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

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

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

　?、谕顺鲞x擇命令unselect.取消事先選中的電子標簽，使標簽進(jìn)入“無(wú)聲”狀態(tài)。在這種狀態(tài)下標簽完全是非激活的，對收到的request命令不做應答。為了重新激活標簽，必須暫時(shí)離開(kāi)讀寫(xiě)器的作用范圍，然后再次進(jìn)入該讀寫(xiě)器范圍。

　　2.2算法原理

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

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

　　(1)request≤11111111命令，讀寫(xiě)器作用范圍內的所有標簽應答，讀寫(xiě)器譯碼的結果為010????0碰撞位為D4，D3，D2，D1，最高碰撞位為D4，次高碰撞位為D3，因此下次查詢(xún)命令為request(D4，0;D3，0)。

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

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

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

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

　　3算法性能比較

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

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

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