1. 引言

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

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

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

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

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

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

　　2.1. ALOHA算法

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

　　2.2. 時(shí)隙ALOHA算法

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

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

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

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

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

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

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

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

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

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

　　3. 新型防碰撞算法

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

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

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

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

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

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

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

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

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

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

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

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

　　4. 結(jié)束語(yǔ)

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

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