1. 引言

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

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

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

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

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

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

　　2.1. ALOHA算法

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

　　2.2. 時隙ALOHA算法

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

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

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

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

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

　　圖1. 二進(jìn)制搜索算法流程

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

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

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

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

　　3. 新型防碰撞算法

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

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

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

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

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

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

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

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

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

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

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

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

　　4. 結(jié)束語

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

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