隨著RFID技術(shù)在物聯(lián)網(wǎng)中的大量應(yīng)用，大量標(biāo)簽進(jìn)入閱讀器的識別范圍，閱讀器應(yīng)能準(zhǔn)確及時地識別出所有標(biāo)簽。但是同一RFID系統(tǒng)中所有的標(biāo)簽工作在相同的頻率，同一時刻多個標(biāo)簽從閱讀器獲得能量并向閱讀器發(fā)送信息，這時就會出現(xiàn)相互干擾，使閱讀器不能正確識別標(biāo)簽，稱為標(biāo)簽沖突。為此出現(xiàn)了防沖突協(xié)議，以解決識別過程中多個標(biāo)簽的信道共享和訪問沖突的問題。在無源電子標(biāo)簽系統(tǒng)中，存在著如下約束：標(biāo)簽自身不能提供電能，需要閱讀器在通信時為它提供能量；識讀范圍內(nèi)的標(biāo)簽總數(shù)未知，標(biāo)簽間不能通信；標(biāo)簽的內(nèi)存和計(jì)算能力有限。因此，理想的防沖突協(xié)議應(yīng)當(dāng)具有如下特點(diǎn)：(1)標(biāo)簽端電路簡單；(2)最小的識別時延，閱讀器與標(biāo)簽的通信數(shù)據(jù)量應(yīng)盡可能少，識別時間應(yīng)盡可能短；(3)識別過程中電能消耗盡可能少，否則可能因電能不足而不能完成識別;(4)識別率應(yīng)能達(dá)到100%，即處于識別范圍內(nèi)的所有標(biāo)簽都能全部正確識別[1]。
    現(xiàn)有的各種防沖突協(xié)議可以分為兩類：隨機(jī)性協(xié)議和確定性協(xié)議[2]。隨機(jī)性協(xié)議發(fā)生沖突時標(biāo)簽延遲一個隨機(jī)時間后響應(yīng)閱讀器，目前形成了以 Aloha為基礎(chǔ)的隨機(jī)性協(xié)議簇，如純 Aloha、時隙Aloha、幀時隙Aloha。確定性協(xié)議中，閱讀器不斷發(fā)送要查詢的標(biāo)簽ID的前綴，與前綴匹配的標(biāo)簽響應(yīng)閱讀器，閱讀器根據(jù)檢測到?jīng)_突信息，將待識別的標(biāo)簽進(jìn)行分組，在組內(nèi)重復(fù)進(jìn)行上述查詢過程（識別修正下次發(fā)送的查詢前綴），直至識別出一個標(biāo)簽。對每一組內(nèi)所有標(biāo)簽進(jìn)行識別，閱讀器范圍內(nèi)的所有標(biāo)簽都被識別。確定性協(xié)議按照識別過程中標(biāo)簽是否需要內(nèi)存儲器可以分為內(nèi)存協(xié)議和無內(nèi)存協(xié)議，目前形成了以二進(jìn)制樹搜索協(xié)議為基礎(chǔ)的系列協(xié)議，如位仲裁搜索（BA）、查詢樹搜索（Q-tree）、基本二進(jìn)制搜索（BS）、動態(tài)二進(jìn)制搜索（DBS）、自適應(yīng)二進(jìn)制搜索（ABS）[1]、具有后退索引的二進(jìn)制搜索(BDBS)[2]及其他改進(jìn)協(xié)議[3-5]。隨機(jī)性協(xié)議比確定性協(xié)議識別速度快，但存在不穩(wěn)定工作區(qū)間, 理論吞吐量被限制在 1/e以內(nèi)，會導(dǎo)致“標(biāo)簽饑餓問題”, 即特定的標(biāo)簽可能會在很長一段時間內(nèi)都無法被正確識別。確定性協(xié)議能提供100%的識別成功率，因而得到了廣泛的應(yīng)用。
    本文提出了一種時間優(yōu)先級分組二進(jìn)制樹搜索協(xié)議TGBS(Time-based Grouping  Binary Splitting)，該協(xié)議以確定性協(xié)議為基礎(chǔ)，首先根據(jù)進(jìn)入閱讀器識別范圍內(nèi)的時間長短將范圍內(nèi)的標(biāo)簽進(jìn)行分組，然后再利用動態(tài)二進(jìn)制樹搜索協(xié)議對組內(nèi)標(biāo)簽進(jìn)行識別。該協(xié)議對先進(jìn)入閱讀器范圍內(nèi)的標(biāo)簽先識別，符合先來先服務(wù)的思想。同時由于將眾多標(biāo)簽先按時間分組，降低了各組內(nèi)標(biāo)簽的沖突概率，縮短了識別時間。該協(xié)議實(shí)現(xiàn)簡單，標(biāo)簽端開銷小，僅需要在每個標(biāo)簽中設(shè)定一個時間計(jì)數(shù)器（分組計(jì)數(shù)器）。
1 二進(jìn)制樹搜索協(xié)議
     基于二進(jìn)制樹的防沖突協(xié)議必須解決好以下三個問題:(1)沖突檢測方法，確定通信信道處于何種狀態(tài)（空閑、沖突、使用）。目前普遍采用曼徹斯特編碼來檢測沖突。(2)以何種策略來搜索樹。目前有確定地址法和隨機(jī)地址法。確定地址法以ID中的每一位（0或1）決定是搜索左子樹還是右子樹，具有吞吐率高，搜索樹深度確定的優(yōu)點(diǎn)，在二進(jìn)制樹搜索協(xié)議中得到廣泛使用。(3)在一個沖突解決期CRI(Conflict Resolution in-Interval)內(nèi)到達(dá)的新標(biāo)簽, 應(yīng)以何種策略決定是否參與信道的競爭。可分為阻塞型信道訪問策略和自由信道訪問策略。前者要求在CRI內(nèi)到達(dá)的新標(biāo)簽不能加入到當(dāng)前CRI中, 直到當(dāng)前CRI結(jié)束, 然后加入下一次CRI的信道競爭; 后者則是任何新到達(dá)的標(biāo)簽都被加入到當(dāng)前CRI競爭中。一般情形下，在二進(jìn)制搜索協(xié)議中均假定RFID沖突解決過程有比較明顯的間歇性和突發(fā)性。如超市自動結(jié)帳系統(tǒng)、出入庫管理系統(tǒng)等每隔一段時間就會有一批數(shù)據(jù)集中到達(dá), 在短時間內(nèi), 閱讀器必須讀出所有的數(shù)據(jù),然后閱讀器停止工作等待下一批數(shù)據(jù)的到達(dá)。因此可以假定“RFID系統(tǒng)在一個CRI內(nèi)不會有新的標(biāo)簽到達(dá)”[6]。在上述前提下，出現(xiàn)了基本二進(jìn)制搜索、動態(tài)二進(jìn)制搜索、自適應(yīng)二進(jìn)制搜索等典型算法及其他改進(jìn)算法[7]。下面的分析中假定標(biāo)簽ID的長度為N，有M個標(biāo)簽待識別。
1.1 基本二進(jìn)制搜索算法
    基本二進(jìn)制搜索算法中，閱讀器發(fā)送一長度為N的查詢序列號，各個標(biāo)簽將自身的ID與接收的序列號比較，其值小于或等于查詢序列號的標(biāo)簽返回其ID。閱讀器檢測信道的沖突情況，按確定地址法先后選擇進(jìn)入左子樹和右子樹，修正發(fā)出的查詢序列號，重復(fù)沖突檢測過程，直至識別出一個標(biāo)簽（到達(dá)葉結(jié)點(diǎn)），然后將其去激活（不再響應(yīng)閱讀器命令）。重復(fù)上述過程，直到完成所有標(biāo)簽的識別（樹搜索）。
    完成所有標(biāo)簽的識別過程主要由閱讀器發(fā)出查詢命令的次數(shù)、發(fā)送命令參數(shù)的長度及標(biāo)簽響應(yīng)數(shù)據(jù)的長度決定。在基本二進(jìn)制樹搜索協(xié)議中，閱讀器在發(fā)送的序列號和標(biāo)簽返回的序列號長度均為N，而請求命令中最高沖突位后面的部分被置為1，對標(biāo)簽的識別無用，同時標(biāo)簽返回命令中最高沖突位的前部分對閱讀器來說是已知的，也是多余的。在識別出一個標(biāo)簽后又從樹根開始下一輪的識別，沒有充分利用前面檢測到的沖突信息，來減少查詢次數(shù)。
1.2 對基本二進(jìn)制搜索協(xié)議的改進(jìn)
    對二進(jìn)制樹形搜索協(xié)議的改進(jìn)主要從減少查詢次數(shù)、減少發(fā)送數(shù)據(jù)和響應(yīng)數(shù)據(jù)的長度著手。
1.2.1降低通信數(shù)據(jù)位長度的改進(jìn)
     降低數(shù)據(jù)長度的改進(jìn)協(xié)議主要有動態(tài)二進(jìn)制搜索協(xié)議、引入預(yù)處理的二進(jìn)制搜索協(xié)議、傳輸沖突位位置的二進(jìn)制搜索協(xié)議[8]。
     動態(tài)二進(jìn)制協(xié)議中，閱讀器檢測到最高沖突位（假設(shè)第M位）后，下一次查詢命令的序列號是最高沖突位在前的（N-M）位加上1位0。各個標(biāo)簽將自身ID號的前N-M+1位與查詢序列號比較，匹配標(biāo)簽返回其序列號的后面M-1位。在一次發(fā)送和響應(yīng)過程中，發(fā)送數(shù)據(jù)長度和標(biāo)簽響應(yīng)數(shù)據(jù)長度的和為N，與基本二進(jìn)制協(xié)議中一次發(fā)送和響應(yīng)數(shù)據(jù)的長度2N相比降低了50%。
     預(yù)處理的二進(jìn)制樹搜索協(xié)議在基本算法之前進(jìn)行一次預(yù)處理：閱讀器第一次發(fā)送查詢命令，所有標(biāo)簽都返回自己的ID，閱讀器檢測所有沖突位，有沖突的標(biāo)簽為1，無沖突的標(biāo)記為0。將此沖突信息發(fā)給各標(biāo)簽，以后各標(biāo)簽只返回有沖突標(biāo)記的位。這樣也可降低發(fā)送和響應(yīng)的數(shù)據(jù)位長度。
    傳輸沖突位位置的二進(jìn)制樹搜索協(xié)議在發(fā)送查詢命令時不是發(fā)送查詢ID或前綴，而是根據(jù)檢測到的沖突信息發(fā)送最高沖突位的位置信息，這對ID長度較長的標(biāo)簽，也可降低發(fā)送的數(shù)據(jù)長度。
1.2.2 降低查詢次數(shù)的改進(jìn)
     降低查詢次數(shù)的方法主要有基于堆棧的二進(jìn)制搜索、基于分組的二進(jìn)制搜索等協(xié)議。
     基于堆棧的二進(jìn)制搜索協(xié)議[9]將搜索過程中發(fā)送的查詢命令參數(shù)放入堆棧，在識別出一個標(biāo)簽從堆棧中取出上一次的查詢命令修改后即可進(jìn)入另一右子樹的搜索，不需要再次從根結(jié)點(diǎn)搜索來識別下一個結(jié)點(diǎn)。這樣可以大大減少發(fā)送查詢命令的次數(shù)。
    基于分組的二進(jìn)制搜索協(xié)議[4,9-11]則是根據(jù)某種策略將待識別標(biāo)簽進(jìn)行分組，然后依次識別出各組標(biāo)簽。分組后組內(nèi)標(biāo)簽碰撞概率降低，再利用二進(jìn)制搜索協(xié)議就可以降低查詢次數(shù)。如ABS協(xié)議、自適應(yīng)多叉樹協(xié)議、不平衡完全區(qū)組協(xié)議。
    此外降低查詢次數(shù)的協(xié)議是基于只有1位碰撞位的互斥特性，可以直接識別兩個標(biāo)簽。
2 時間優(yōu)先級分組的二進(jìn)制搜索協(xié)議
    隨著RFID在物聯(lián)網(wǎng)中的大量應(yīng)用，出現(xiàn)了這樣一種場景[12]：在RFID應(yīng)用于物流生產(chǎn)線、傳送帶、物流等快速移動領(lǐng)域時，多個標(biāo)簽以分組的形式快速進(jìn)入閱讀器的識別范圍內(nèi)，然后又快速移出。如圖1所示。虛線表示閱讀器的閱讀范圍，多個標(biāo)簽以分組的形式（如一個托盤）依次通過閱讀器。

    在這種場景下，使以前的二進(jìn)制搜索協(xié)議遇到了挑戰(zhàn)。“RFID系統(tǒng)在一個 CRI 內(nèi)不會有新的標(biāo)簽到達(dá)”這一假定不太適用。在標(biāo)簽快速移動的場景下，在識別前一標(biāo)簽組的過程（沖突解決期）內(nèi)有新的標(biāo)簽到達(dá)，而新進(jìn)入的標(biāo)簽采用自由信道訪問策略則會加大先進(jìn)入標(biāo)簽組的識別延時。如圖2所示。

    當(dāng)先進(jìn)入的標(biāo)簽A、B、C、D利用二進(jìn)制搜索協(xié)議識別標(biāo)簽B時，有兩個標(biāo)簽E、F進(jìn)入，其中標(biāo)簽E位于B的左邊，標(biāo)簽F位于標(biāo)簽B的右邊。此時由于標(biāo)簽E的ID前綴與查詢前綴ID不匹配，將不影響B(tài)右邊結(jié)點(diǎn)的C、D的識別延遲。但結(jié)點(diǎn)F的加入，造成了和結(jié)點(diǎn)C、D的沖突，為解決此沖突，加大了識別結(jié)點(diǎn)C和D的延遲時間。如果進(jìn)一步考慮識別出結(jié)點(diǎn)F后閱讀器的讀寫數(shù)據(jù)的通訊時間，則識別結(jié)點(diǎn)D的時間將進(jìn)一步延遲。若有多個后進(jìn)入的標(biāo)簽都位于結(jié)點(diǎn)D的前面，就可能導(dǎo)致結(jié)點(diǎn)D已經(jīng)離開閱讀器的讀寫范圍，造成漏讀。但由于標(biāo)簽在快速移動，導(dǎo)致標(biāo)簽離開了閱讀器的識別范圍，從而導(dǎo)致了漏讀現(xiàn)象。因此，必須對二進(jìn)制搜索協(xié)議進(jìn)行改進(jìn)。
　時間優(yōu)先級二進(jìn)制協(xié)議采用先進(jìn)先出FIFO(First In First Out)的服務(wù)原則，結(jié)合標(biāo)簽分組識別的思想，按照標(biāo)簽進(jìn)入閱讀器閱讀范圍的時間長短進(jìn)行確定識別優(yōu)先級，并根據(jù)優(yōu)先級將標(biāo)簽劃分為若干待識別標(biāo)簽組，按照時間優(yōu)先級的高低依次識別各組標(biāo)簽。該協(xié)議與二進(jìn)制搜索協(xié)議的實(shí)現(xiàn)過程不同的地方有：
    (1)在閱讀器中設(shè)置一查詢優(yōu)先級變量Q, 每個標(biāo)簽中各設(shè)一個動態(tài)優(yōu)先級變量P。標(biāo)簽在獲得能量后，將其動態(tài)優(yōu)先級P設(shè)定為0。
　 (2)閱讀器每隔一定時間T,發(fā)出一個優(yōu)先級更新命令，各標(biāo)簽收到此命令后，將動態(tài)優(yōu)先級P加1。
　 (3)閱讀器在發(fā)送查詢命令時,除了發(fā)送查詢前綴外,還附加一查詢優(yōu)先級Q，Q的取值按照輪詢的方法來賦值即Q依次為Pmax,Pmax-1,…,1,0，其中Pmax為標(biāo)簽中動態(tài)優(yōu)先級的最大值。
　 (4)標(biāo)簽在響應(yīng)查詢命令時，只有其動態(tài)優(yōu)先級P與查詢優(yōu)先級Q相符的標(biāo)簽才返回其ID的后輟部分。
　 (5)對于相同優(yōu)先級的防沖突過程，采用基于堆棧的動態(tài)二進(jìn)制搜索協(xié)議。
3 協(xié)議性能分析
    二進(jìn)制搜索協(xié)議的性能主要從降低識別延時和提高識別率來考慮，延遲時間主要由識別過程中要傳輸?shù)臄?shù)據(jù)量多少決定，具體由查詢命令次數(shù)及每次查詢中傳輸?shù)臄?shù)據(jù)位來決定。時間分組二進(jìn)制搜索協(xié)議，在每次查詢命令參數(shù)中增加優(yōu)先級這一參數(shù)，增加了每次的傳輸通信量，但由于將閱讀器范圍內(nèi)的標(biāo)簽進(jìn)行了分組，每組內(nèi)標(biāo)簽的個數(shù)大大減少，降低了組內(nèi)標(biāo)簽碰撞的概率，降低了查詢次數(shù)，總體上降低了傳輸通信量，減少了識別延時。下面將時間分組二進(jìn)制搜索協(xié)議與動態(tài)二進(jìn)制搜索協(xié)議、基于堆棧的動態(tài)二進(jìn)制搜索協(xié)議進(jìn)行比較，以說明其性能的提高。設(shè)閱讀器范圍內(nèi)有N個標(biāo)簽，標(biāo)簽ID長度為L位，依據(jù)時間分組的組數(shù)為G。
　對于動態(tài)二進(jìn)制搜索協(xié)議，其查詢次數(shù)為N(N+1)/2, 每次查詢的數(shù)據(jù)量為(L+1)/2，則總的傳輸數(shù)據(jù)量S1為：

    圖3顯示了堆棧動態(tài)二進(jìn)制協(xié)議與時間分組二進(jìn)制協(xié)議的通信數(shù)量。其中L為32位，P=4?？梢钥闯鲎R別一組內(nèi)標(biāo)簽的數(shù)據(jù)量遠(yuǎn)小于識別所有標(biāo)簽的數(shù)據(jù)量，即識別延時大大降低。

    圖4顯示了在L=32,N=500的情況下，分組數(shù)P與數(shù)據(jù)量的變化關(guān)系?？梢钥闯鲭S著分組數(shù)的增加，識別一組內(nèi)標(biāo)簽所需的延時將急劇降低。

    動態(tài)二進(jìn)制搜索協(xié)議在面向越來越普及的快速移動的物聯(lián)網(wǎng)應(yīng)用時遇到了漏讀率提高的新挑戰(zhàn)。本文提出了一種時間優(yōu)先級分組的二進(jìn)制搜索協(xié)議TGBS。TGBS協(xié)議按照先來先服務(wù)（FCFS）的公平原則，將進(jìn)入閱讀器范圍內(nèi)的多個標(biāo)簽按進(jìn)入時間的長短進(jìn)行優(yōu)先級分組，并按優(yōu)先級高低進(jìn)行分組識別。與動態(tài)二進(jìn)制搜索協(xié)議相比，在標(biāo)簽內(nèi)只需增加一個優(yōu)先級變量，電路實(shí)現(xiàn)簡單；閱讀器發(fā)送查詢命令時增加查詢優(yōu)先級參數(shù)，盡管單次查詢發(fā)送的數(shù)據(jù)量有所增加，但分組后組內(nèi)碰撞標(biāo)簽數(shù)大幅減少，后進(jìn)入的標(biāo)簽組不對先進(jìn)入的標(biāo)簽組產(chǎn)生識別干擾，可以有效地保證先進(jìn)入的標(biāo)簽?zāi)芡暾卣_識別，降低了標(biāo)簽漏讀率。理論分析和仿真表明，在移動場景下在識別的準(zhǔn)確率上，協(xié)議比動態(tài)二進(jìn)制協(xié)議更優(yōu)。
參考文獻(xiàn)
[1] PRAPASSARA P, BELASTANTIC. Unified q-ary tree for RFID tag anti-collision resolution[C]. the 20th Australasian Database Conference.2009.
[2] 魏欣. RFID標(biāo)簽及閱讀器防沖突算法研究[D].成都：電子科技大學(xué),2009.
[3] 丁治國,朱學(xué)永,郭立,等.自適應(yīng)多叉樹防碰撞算法研究[J]. 自動化學(xué)報(bào)，2010，36(2):237-241.
[4] 李世煜,馮全源,魯飛. 基于 BIBD(4,2,1)的 RFID防碰撞算法[J].計(jì)算機(jī)工程,2009,35(3):279-281.
[5] 向垂益,何怡剛,李兵,等.動態(tài)二進(jìn)制樹搜索算法的改進(jìn)[J]. 計(jì)算機(jī)工程, 2010,36(2):260-262.
[6] 馮波,李錦濤,鄭為民. 一種新的RFID標(biāo)簽識別防沖突算法[J]. 自動化學(xué)報(bào),2008,34(6):632-638.
[7] DONG Her Shih, SUN Po Ling, YEN D C. Taxonomy and survey of RFID anti-collision protocols[J]. Computer Communications,2006(29):2150-2166.
[8] SHI X L, SHI X W, HUANG Q L, et al. An enhanced  binary anti-collision algorithm of backtracking in RFID system[J]. Progress In Electromagnetics Research B,2008(4):263-271.
[9] MYUNG J, LEE W J, SRIVASTAVA J. Adaptive binary splitting for effcient RFID tag anti-collision[J].IEEE Communications Letters,2006,10(3):144-146.
[10] WANG Tsan Pin. Enhanced binary search with cutthrough operation for anti-collision in RFID systems[J]. IEEE Communications Letters,2006,10(4):236-238.
[11] 尹君,何怡剛,李兵,等.基于分組動態(tài)幀時隙的RFID防碰撞算法[J]. 計(jì)算機(jī)工程,2009,35(20):267-269.
[12] 趙曦，張有光. 一種新穎的 RFID多標(biāo)簽防碰撞算法[J].北京航空航天大學(xué)學(xué)報(bào),2008(3):276-279.