隨著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)存和計算能力有限。因此,理想的防沖突協(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é)議實現(xiàn)簡單,標(biāo)簽端開銷小,僅需要在每個標(biāo)簽中設(shè)定一個時間計數(shù)器(分組計數(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)以何種策略決定是否參與信道的競爭?煞譃樽枞托诺涝L問策略和自由信道訪問策略。前者要求在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é)議的實現(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)先級的最大值。
來源:電子技術(shù)應(yīng)用