1. 引言

　　射頻識別(RFID: Radio Frequency Identification)技術(shù)是近年來發(fā)展較快的一項技術(shù)。RFID技術(shù)通過射頻信號，非接觸式的在電子標簽與閱讀器之間雙向的傳遞信息，以達到自動識別的目的。由于其具有識別速度快、識別準確率高、可以非接觸識別等優(yōu)點，目前被廣泛應用于交通運輸管理、物流管理、商業(yè)自動化等眾多領(lǐng)域之中，被譽為二十一世紀最具發(fā)展?jié)摿Φ氖髴?zhàn)略性產(chǎn)業(yè)之一[1] 。

　　RFID系統(tǒng)區(qū)別于傳統(tǒng)條形碼系統(tǒng)的一個重要特點就是它一次可識讀多個電子標簽。RFID系統(tǒng)中的每個電子標簽都有唯一標識的編碼，閱讀器的主要任務就是正確識讀這些信息[2] 。而當一個RFID系統(tǒng)中閱讀器工作范圍內(nèi)存在多個電子標簽時，同一時刻就可能會有不止一個標簽向閱讀器發(fā)送信息。這樣，多個標簽的發(fā)送信號之間就可能會相互干擾，使得閱讀器無法正確的接收標簽發(fā)出的信息，這種情況即為標簽碰撞。而解決標簽碰撞問題的方法稱為防碰撞算法。

　　本文將對目前幾種常見ALOHA算法和二進制搜素算法進行介紹，并在此基礎(chǔ)上提出一種全新的防碰撞算法，以提高RFID系統(tǒng)的標簽識別效率。

　　2. 現(xiàn)有防碰撞算法

　　目前時分多路法中最常見的兩類防碰撞算法是ALOHA算法和二進制搜索算法。ALOHA算法是一種隨機性算法，有可能會出現(xiàn)某一標簽在很長時間內(nèi)不被閱讀器識別的情況，即存在標簽饑渴的問題，因此也稱為不確定算法。二進制搜索算法是一種確定性算法，這類算法與ALOHA算法相比較為復雜，識別時間也相對較長，但是不存在標簽饑渴的問題[3] 。

　　各種防碰撞算法之間沒有絕對的優(yōu)劣之分，不同的防碰撞算法適用于不同的環(huán)境。在高頻頻段，一般采用ALOHA算法，絕大多數(shù)的高頻閱讀器能夠同時識讀幾十個標簽。在超高頻頻段中，目前主要采用的是二進制搜索算法。

　　2.1. ALOHA算法

　　ALOHA算法是一種數(shù)據(jù)信號隨機接入的方法[4] 。當碰撞發(fā)生時，所有發(fā)生碰撞的標簽發(fā)送的數(shù)據(jù)都會出現(xiàn)差錯而導致發(fā)送失敗，因此所有碰撞方都必須進行數(shù)據(jù)重傳。但各方不能在碰撞之后立即開始重傳，因為這樣必定會導致再次碰撞。ALOHA算法采用的重傳策略是發(fā)生碰撞的標簽隨機等待一段時間后再重新發(fā)送數(shù)據(jù)。由于每個標簽數(shù)據(jù)的傳輸時間相對于重傳等待時間來說非常短，因此標簽兩次數(shù)據(jù)發(fā)送之間有相對較長的時間間隔，這樣就存在一定的概率，使得多個電子標簽選擇不同的時間發(fā)送數(shù)據(jù)，以避免碰撞的發(fā)生。

　　2.2. 時隙ALOHA算法

　　時隙ALOHA算法是一種隨機時分多址方式的用戶信息通訊收發(fā)算法[5] 。在這種算法中，將數(shù)據(jù)的傳輸時間劃分成許多個等長的時隙，時隙的長度為一個數(shù)據(jù)包發(fā)送成功所需要的時間。時隙ALOHA算法規(guī)定標簽只能在一個時隙開始的時候傳輸數(shù)據(jù)。這樣，數(shù)據(jù)包只存在兩種狀態(tài)：發(fā)送成功或完全沖突[6] 。用于傳輸數(shù)據(jù)的時隙由閱讀器控制，只有當閱讀器分配完所有的時隙之后，標簽才允許利用這些時隙來傳輸數(shù)據(jù)。

　　為了簡化對時隙ALOHA算法的分析，我們假設(shè)標簽數(shù)據(jù)包的發(fā)送符合泊松分布。設(shè)一個時隙為T0，即在T0時間內(nèi)有k個數(shù)據(jù)包發(fā)送的概率為：

　　2.3. 二進制搜索算法

　　二進制搜索算法又名二叉樹算法，它是基于樹分叉搜索算法實現(xiàn)的。要求閱讀器能夠準確識別出數(shù)據(jù)碰撞的位置。之后根據(jù)一系列循環(huán)操作，識別所有標簽。二進制搜索算法實現(xiàn)流程如圖1所示。

　　其識別步驟說明如下：1) 閱讀器設(shè)置初始篩選條件為全1，向其工作范圍內(nèi)的標簽發(fā)出請求信號。2) 所有標簽均符合篩選條件所以全部響應，并向閱讀器返回自身序列號。3) 閱讀器分析各標簽返回的信息，若發(fā)生碰撞，閱讀器檢測出所有碰撞位置，重新修改篩選條件，將最高碰撞位置0，其余低位置1，重新發(fā)送請求信號。4) 編碼小于等于閱讀器請求信號的標簽響應閱讀器請求，并返回自身序列號。5) 重復上述識別過程，閱讀器重復發(fā)送請求指令，直至有唯一標簽響應，即無碰撞產(chǎn)生時，閱讀器讀取該標簽信息，并令該標簽進入“去活”狀態(tài)。6) 若閱讀器工作范圍內(nèi)仍有待識別標簽，閱讀器重置篩選條件為全1，重新發(fā)送請求信號，重復上述識別過程。直至所有標簽識別完畢，此次識別過程結(jié)束。

　　圖1. 二進制搜索算法流程

　　2.4. 改進型動態(tài)二進制搜索算法

　　二進制搜索算法在識別的過程中，標簽信息直接出現(xiàn)在閱讀器的請求信號和標簽的應答信號中，這有可能會引起RFID系統(tǒng)被遠距離竊聽等安全方面的問題[7] 。為了保證標簽與閱讀器通信過程中的數(shù)據(jù)安全性和數(shù)據(jù)傳輸?shù)母咝?，改進的動態(tài)二進制搜索算法被提出。改進的動態(tài)二進制搜索算法識別流程如圖2所示[8] 。

　　其識別步驟說明如下1) 置全體標簽休眠程度為0。閱讀器向其工作范圍內(nèi)的標簽發(fā)送REQUEST(NULL，X)請求指令。X為標簽編碼位數(shù)，該指令為全體響應指令。2) 閱讀器工作范圍內(nèi)全體標簽響應該指令，并向閱讀器發(fā)送自身序列號。3) 閱讀器分析標簽返回的信息，找出最高碰撞位K，向標簽發(fā)出REQUEST(0，K)指令;4) 滿足條件的標簽響應并返回自身序列號，其余未響應標簽令其休眠程度加1。5) 重復上述識別過程，直至有唯一標簽響應，即無碰撞產(chǎn)生時，閱讀器讀取該標簽信息，之后將該標簽去活。6) 閱讀器成功識別一個標簽之后，向休眠標簽發(fā)出激活指令，令其休眠程度減1。休眠程度歸0的標簽進入待命態(tài)，算法進入上行搜索策略。7) 閱讀器分析待命態(tài)標簽的序列號信息，找出最低碰撞位K，發(fā)出REQUEST(1，K)指令。8) 重復上行搜索過程，直至最高碰撞位置1后，算法重新進入下行搜索策略。9) 重復以上搜索過程，直至所有標簽識別完畢，此次識別過程結(jié)束。

　　圖2. 改進的動態(tài)二進制搜索算法實現(xiàn)流程

　　3. 新型防碰撞算法

　　通過第二章對四種防碰撞算法的分析描述，我們可知，在隨機性防碰撞算法中，時隙ALOHA算法的算法性能好于純ALOHA算法，而在確定性防碰撞算法中，改進的動態(tài)二進制搜索算法不僅實現(xiàn)較為簡單，而且數(shù)據(jù)傳輸量小，數(shù)據(jù)安全性高。時隙ALOHA算法和改進的動態(tài)二進制搜索算法在標簽數(shù)量不是很大的條件下都有較好的識別效率。

　　下面我們通過控制變量法對時隙ALOHA算法和改進的動態(tài)二進制搜索算法的識讀時間進行計算。令標簽數(shù)量為5，編碼為8位，時隙ALOHA算法中數(shù)據(jù)重發(fā)最大時隙為5，標簽隨機選擇發(fā)送時隙。多次運行時隙ALOHA算法和改進的動態(tài)二進制搜索算法程序，其識讀時間統(tǒng)計結(jié)果如表1所示。

　　由表1可以看出，采用時隙ALOHA算法的RFID系統(tǒng)閱讀器識讀同等數(shù)量標簽所用時間要小于改進的動態(tài)二進制搜索算法。在這里必須指出上表中所列出的時間只是程序執(zhí)行算法的時間，沒有包括數(shù)據(jù)傳輸?shù)臅r間。由于改進的動態(tài)二進制搜索算法需要傳輸?shù)臄?shù)據(jù)多于時隙ALOHA算法的數(shù)據(jù)，因此在實際情況中，時隙ALOHA算法的識讀速率會遠高于改進的動態(tài)二進制搜索算法。但是，時隙ALOHA算法是一種隨機搜索算法，即不確定算法，存在一定的幾率使得兩個或兩個以上的標簽長時間處于相互碰撞的狀態(tài)下。為了保證RFID系統(tǒng)較高的工作效率，并盡可能的減少數(shù)據(jù)傳輸量，同時保證不會出現(xiàn)電子標簽信息漏讀的情況，本文提出一種基于時隙ALOHA算法和改進的動態(tài)二進制搜索算法結(jié)合的混合算法，為了方便后文表述，將其命名為二進制ALOHA算法。該算法工作流程如圖3所示。

　　具體實現(xiàn)方法如下：1) 當兩個及以上的標簽同時進入閱讀器識別范圍后，向閱讀器發(fā)送信息，閱讀器檢測到碰撞，并確定當前標簽數(shù)量n。2) 閱讀器分配n個時隙，時隙的長度為標簽發(fā)送完成全部數(shù)據(jù)所需時間。每個電子標簽隨機選擇一個時隙作為其數(shù)據(jù)發(fā)送時間。3) 閱讀器依次檢查每個時隙，若該時隙內(nèi)只有唯一標簽發(fā)送數(shù)據(jù)，則選中該標簽并與之進行通信，讀取完成后令其進入“去活”狀態(tài);若有多個標簽同時發(fā)送數(shù)據(jù)，則閱讀器檢測到碰撞，不對這些標簽進行任何處理。4) 所有時隙檢查完成后，所有未被“去活”的標簽進入第二輪篩選。5) 同改進的動態(tài)二進制搜索算法，閱讀器首先發(fā)送全體請求信號，未被去活的所有標簽響應，之后閱讀器根據(jù)標簽的響應信號判斷其碰撞位，并通過循環(huán)不斷發(fā)出請求信號，最終完成對所有標簽的識別。

　　特別需要指出的是，在閱讀器對n個電子標簽進行識讀的過程中，當有其他標簽進入時，若其在時隙ALOHA算法階段入站，則該標簽參與二進制搜索算法識別過程;若其是在二進制搜索算法階段入站的，則其等待閱讀器下一輪的識別。

　　在二進制ALOHA算法中，由于標簽隨機選擇閱讀器初始分配的n個時隙，因此我們可知，標簽成功發(fā)送的概率為：

　　圖3. 改進的動態(tài)二進制搜索算法實現(xiàn)流程

　　在改進的動態(tài)二進制搜索算法中，閱讀器在識讀電子標簽時，電子標簽至少要響應三次閱讀器請求。第一次是響應閱讀器的全部請求信號，第二次響應閱讀器檢測到碰撞后的條件請求信號，第三次是響應閱讀器讀取請求。因此x的值一定大于等于3，由此可知，對于時隙ALOHA算法、改進的動態(tài)二進制搜索算法、二進制ALOHA算法，識別10個標簽的數(shù)據(jù)傳輸量分別為：272、76 + 80x、126.4 + 50.4x，而由于x大于等于三，因此二進制ALOHA算法相比改進的動態(tài)二進制搜索算法具有更小的數(shù)據(jù)傳輸量。

　　三種算法程序運行結(jié)果如表3所示。

　　由表3數(shù)據(jù)可知，利用二進制ALOHA算法的程序運行時間要長于時隙ALOHA算法，但小于改進的動態(tài)二進制搜索算法。且采用二進制ALOHA算法避免了由于時隙ALOHA算法隨機性而造成的數(shù)據(jù)無法準確識讀的情況[9] ，保證了RFID系統(tǒng)采集數(shù)據(jù)的可靠性。同時相比于改進的二進制搜索算法，不僅縮短了標簽的識讀時間，而且減少了數(shù)據(jù)的傳輸量，提高了算法的綜合性能。

　　表2. 二進制ALOHA算法第一階段識別成功的概率　　

　　表3. 三種算法程序運行結(jié)果

　　4. 結(jié)束語

　　本文在對現(xiàn)有的幾種防碰撞算法進行簡要介紹后，提出了一種新型防碰撞算法：二進制ALOHA算法，通過對比在不同標簽數(shù)量下與時隙ALOHA算法和改進的動態(tài)二進制搜索算法程序運行時間，識讀相同數(shù)量標簽的數(shù)據(jù)傳輸量，證明該算法不僅能夠有效避免時隙ALOHA算法可能出現(xiàn)漏讀的問題，同時相比于二進制搜索算法有較小的數(shù)據(jù)傳輸量和較高的識讀效率。

　　在下一步的工作中，將對如何進一步提升閱讀器的標簽識別效率和降低系統(tǒng)建設(shè)成本進行研究，同時將對如何減少在標簽識別過程中的數(shù)據(jù)傳輸量進行深入研究，以期進一步優(yōu)化標簽識別過程。