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

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

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

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

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

    動(dòng)態(tài)二進(jìn)制搜索協(xié)議在面向越來越普及的快速移動(dòng)的物聯(lián)網(wǎng)應(yīng)用時(shí)遇到了漏讀率提高的新挑戰(zhàn)。本文提出了一種時(shí)間優(yōu)先級(jí)分組的二進(jìn)制搜索協(xié)議TGBS。TGBS協(xié)議按照先來先服務(wù)（FCFS）的公平原則，將進(jìn)入閱讀器范圍內(nèi)的多個(gè)標(biāo)簽按進(jìn)入時(shí)間的長(zhǎng)短進(jìn)行優(yōu)先級(jí)分組，并按優(yōu)先級(jí)高低進(jìn)行分組識(shí)別。與動(dòng)態(tài)二進(jìn)制搜索協(xié)議相比，在標(biāo)簽內(nèi)只需增加一個(gè)優(yōu)先級(jí)變量，電路實(shí)現(xiàn)簡(jiǎn)單；閱讀器發(fā)送查詢命令時(shí)增加查詢優(yōu)先級(jí)參數(shù)，盡管單次查詢發(fā)送的數(shù)據(jù)量有所增加，但分組后組內(nèi)碰撞標(biāo)簽數(shù)大幅減少，后進(jìn)入的標(biāo)簽組不對(duì)先進(jìn)入的標(biāo)簽組產(chǎn)生識(shí)別干擾，可以有效地保證先進(jìn)入的標(biāo)簽?zāi)芡暾卣_識(shí)別，降低了標(biāo)簽漏讀率。理論分析和仿真表明，在移動(dòng)場(chǎng)景下在識(shí)別的準(zhǔn)確率上，協(xié)議比動(dòng)態(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] 丁治國(guó),朱學(xué)永,郭立,等.自適應(yīng)多叉樹防碰撞算法研究[J]. 自動(dòng)化學(xué)報(bào)，2010，36(2):237-241.
[4] 李世煜,馮全源,魯飛. 基于 BIBD(4,2,1)的 RFID防碰撞算法[J].計(jì)算機(jī)工程,2009,35(3):279-281.
[5] 向垂益,何怡剛,李兵,等.動(dòng)態(tài)二進(jìn)制樹搜索算法的改進(jìn)[J]. 計(jì)算機(jī)工程, 2010,36(2):260-262.
[6] 馮波,李錦濤,鄭為民. 一種新的RFID標(biāo)簽識(shí)別防沖突算法[J]. 自動(dòng)化學(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] 尹君,何怡剛,李兵,等.基于分組動(dòng)態(tài)幀時(shí)隙的RFID防碰撞算法[J]. 計(jì)算機(jī)工程,2009,35(20):267-269.
[12] 趙曦，張有光. 一種新穎的 RFID多標(biāo)簽防碰撞算法[J].北京航空航天大學(xué)學(xué)報(bào),2008(3):276-279.