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

    現有的RFID防碰撞算法都是基于TDMA算法,可劃分為Aloha防碰撞算法和基于二進制搜索BS（Binary search）算法兩大類[2-3]。Aloha是一種隨機接入算法，這種算法多采取“標簽先發言”的方式，即標簽一旦進入閱讀器的閱讀區域就自動向閱讀器發送其自身的ID,隨即標簽和閱讀器間開始通信。在標簽發送數據的過程中，若有其他標簽也在發送數據，將發生信號重疊從而導致完全沖突或部分沖突，閱讀器檢測接收到的信號來判斷有無沖突。如果發生沖突，閱讀器將發送命令讓標簽停止發送，隨機等待一段時間后再重新發起查詢。該算法特點是：算法簡單、便于實現，適用于低成本RFID系統。但是由于該算法的時隙是隨機分配的，當大量標簽并存時，幀沖突嚴重[4]。而基于BS算法是通過多次比較，不斷篩選出不同的標簽號，時分復用地進行讀寫器和射頻卡之間的信號交換，以一個獨特的序列號識別射頻卡為基礎。為了從一組射頻卡中選出其中的一個，讀寫器需要發出一個請求命令，有意識地將射頻卡序列號傳輸時的數據碰撞引導到讀寫器上，即讓讀寫器來判斷是否發生碰撞。如發生碰撞，則縮小范圍進行進一步搜索。這類算法雖然識別效率高， 但是算法比較復雜， 識別時間較長[5-6]。本文在二進制防碰撞算法的基礎上提出一種改進的防碰撞算法。
1 兩種典型的二進制防碰撞算法的分析
1.1 二進制搜索算法
    實現BS算法系統的必要前提是能夠辨認出在讀寫器中數據沖突位的準確位置，因此必須選用合適的編碼。曼徹斯特編碼能夠按位識別出碰撞位，這樣可以根據碰撞的位置，按一定的規則重新搜索標簽。因此，使用曼徹斯特編碼是實現二進制搜索防碰撞算法的必要前提[7-8]。BS算法的工作流程如下：
    （1）電子標簽進入讀寫器的作用范圍時，讀寫器發送命令REQUEST（≤11111111），所有滿足此條件的電子標簽響應此命令，并將自己的EPC號傳給讀寫器。
   （2）讀寫器對比電子標簽響應的EPC碼相同位數上的數，根據Manchester編碼規則，若出現不一致現象，即可判斷出該比特位有碰撞。
   （3）當確定有碰撞后，將此次發生碰撞的最高位置“0”，最高碰撞位之前的比特位不變，最高碰撞位后的所有比特位都置“1”，并產生新的請求命令REQUEST，依次排除序列號大的標簽，直到讀寫器對比電子標簽響應的序列號中相同位數上的數完全一致時，則說明無碰撞。此時，使用選擇命令(SELECT)選出一個唯一的標簽。
    （4）選出唯一的標簽后，使用READ-DATA命令完成讀寫器與該電子標簽的數據交換。并使用選擇命令(UNSELECT)進入“無聲”狀態，此時在讀寫器范圍內不再響應(重新進入讀寫器范圍可再次響應)。為了重新激活電子標簽，必須進行復位操作。
    （5）重復前4個步驟，并選擇剩余的電子標簽數據交換。多次循環后即可完成所有電子標簽的讀取。
1.2 動態二進制搜索算法(DBS)
    在BS搜索算法中，從讀寫器和單個電子標簽的數據流可以看出，讀寫器發出的請求命令中，最高碰撞位后的所有比特位都被置“1”，對標簽的識別不能提供任何的信息。而標簽返回的數據中，最高碰撞位以前的比特位及最高碰撞位不包含給讀寫器的補充信息，因為這些位是已知且給定的，屬于多余的重復信息。基于此人們提出了動態二進制搜索算法(DBS)[9]，當讀寫器檢測到碰撞后，下一次讀寫器在請求命令中只發送搜索序列號中的最高位和最高碰撞位之間的部分作為搜索依據，然后中斷傳輸，所有在與最高位和最高碰撞位之間的部分相同的電子標簽響應并送回它們序列號的剩余各位，即最高碰撞位之后的比特位作為應答。因此，DBS算法避免了序列號中多余部分的傳輸，數據傳輸時間明顯縮短。DBS算法較BS算法在傳輸數據量和所需時間上可減少50%[10]。
2 改進的二進制搜索算法
2.1算法約定
    鑒于BS算法的缺點，本文提出了一種改進的二進制搜索算法，算法約定如下：
    （1）采用曼徹斯特編碼的電子標簽序列號每個比特位上的取值不是“0”就是“1”。因此，如果當讀寫器探測到僅有一位碰撞位時，讀寫器不需要發送請求命令,可以直接識別出2個標簽。
     （2）讀寫器如果檢測到有N個碰撞位，則說明這N個碰撞位的比特位對讀寫器來說是未知的,而其他的比特位對讀寫器來說是已知的。因此讀寫器只需要對未知的碰撞位處理，而不需要傳輸那些已知的比特位，從而減少傳輸時延。
    為了便于描述以及實現該算法,給出如下防碰撞命令：
     ①查詢命令request(DX,MX;DX1,MX1)。參數DX、DX1分別為檢測到碰撞位的最高位和次高位，參數MX、MX1為0、1的二維排列組合，例如檢測到1?1?00?1，那么讀寫器發送request（D6,0;D4,0）符合條件的標簽響應并返回沖突位及相關信息。
     ②退出選擇命令unselect。取消事先選中的電子標簽，使標簽進入“無聲”狀態。在這種狀態下標簽完全是非激活的，對收到的request命令不做應答。為了重新激活標簽，必須暫時離開讀寫器的作用范圍，然后再次進入該讀寫器范圍。
2.2 算法原理
　 下面以讀寫器作用范圍內的8個編碼為8 bit的標簽為例說明該算法，8個標簽的編碼如下：tag1:01001000，tag2:01010100，tag3：01011010，tag4:01000000，tag5:01000010，
tag6：01010000，tag7:01001010，tag8:01011000。
    （1）request≤11111111命令，讀寫器作用范圍內的所有標簽應答，讀寫器譯碼的結果為010????0碰撞位為D4,D3,D2,D1,最高碰撞位為D4，次高碰撞位為D3，因此下次查詢命令為request（D4,0;D3,0）。
    （2）讀寫器發送查詢命令request（D4,0;D3,0）,標簽通過比較各自的D4、D3位，與之相同的標簽則發送自己的相關信息給讀寫器。通過比較后標簽4和標簽5響應，編碼后得到010000?0，讀寫器檢測到僅只有一位碰撞，可以直接識別出標簽4和標簽5。讀寫器正確識別它們之后，執行unselect命令，使標簽4和標簽5處于“無聲”狀態。
    （3）讀寫器發送查詢命令request（D4,0;D3,1）,標簽1和標簽7響應，編碼后得到010010?0，讀寫器檢測到僅只有一位碰撞，可以直接識別出標簽1和標簽7。讀寫器正確識別它們之后，執行unselect命令，使標簽1和標簽7處于“無聲”狀態。
    （4）讀寫器發送查詢命令request（D4,1;D3,0）,標簽2和標簽6響應，編碼后得到01010?00，讀寫器檢測到僅只有一位碰撞，可以直接識別出標簽2和標簽6。讀寫器正確識別它們之后，執行unselect命令，使標簽1和標簽7處于“無聲”狀態。
    （5）讀寫器發送查詢命令request（D4,1;D3,1）,標簽3和標簽8響應，編碼后得到010110?0，讀寫器檢測到僅只有一位碰撞，可以直接識別出標簽3和標簽8。讀寫器正確識別它們之后，執行unselect命令，使標簽1和標簽7處于“無聲”狀態。至此，讀寫器作用范圍內的所有標簽都別正確識別完畢。算法流程如圖1所示。
3 算法性能比較
    假設讀寫器作用范圍內有N個電子標簽，則BS算法完成所有標簽識別的搜索命令次數S(N)為:
    
    系統的吞吐率η1為:
    

    對三種算法采用Matlab軟件進行仿真， 其結果如圖2所示。

    通過理論和仿真比較可見，采用改進后的二進制搜索算法較其他兩個算法有三個方面的優勢：其一減少了查詢標簽次數，使計算時間減小；其二減少了系統數據傳輸量，提高了標簽的識別速率；其三較大地提高了系統的吞吐率。
    本文對BS算法及DBS算法過程進行了分析，找出了其中的不足之處，在此基礎上提出了一種改進的二進制搜索算法，并通過Matlab仿真得到該算法的查詢次數和吞吐率方面的數據。通過實驗數據表明，該改進算法可以減少系統的查詢次數，提高系統的吞吐率。從而驗證了該改進算法的優越性。
參考文獻
[1] 李曉東．射頻識別技術中的隱私安全問題及策略[J]．微電子學與計算機，2005，22(9)：137-140．
[2] FINKENZELLER K． RFID Handbook：Fundamentals and  applications in contactless smart cards and identification[M]．New York：John Wiley and Sons，2003．
[3] 廖傳書，付泰．射頻識別系統的防碰撞算法研究[J]．國外電子元器件，2008，16(9)：6-8．
[4] LEE S R，JOO S D，LEE C W．An enhanced dynamic  framed slotted ALOHA algorithm for RFID tag identification[C]. The Proceedings of the 2nd Annual International Conference on Mobile and Ubiquitous Systems，2005．
[5] 莫磊．RFID位屏蔽二進制搜索防碰撞算法研究[J]．河北科技大學學報，2010，31(5)：458-462．
[6] TSAN P W．Enhanced binary search with cut through operation for anti-collision in RFID systems[J]．Communications Letter IEEE，2005,10(4):236-238．
[7] 余松森，詹宜巨,彭衛東，等．基于返回式索引的二進制樹形搜索反碰撞算法及其實現[J]． 計算機工程與應用, 2004,40(16)：26-28．
[8] 姜麗芬，盧桂章，辛運帷，等．射頻識別系統中防碰撞算法研究[J]．計算機工程與應用，2007，43(5)：29-32．
[9] 王忠勇，高向川．基于回溯的RFID防碰撞算法[J]．微計算機信息，2009，25(2)：187-188.
[10] FINKENZELLER K．射頻識別技術—無線電感應的標簽和非接觸式IC卡的原理與應用[M]．陳大才,譯.北京：電子工業出版社，2001．