RFID中基于動(dòng)態(tài)二進(jìn)制的改進(jìn)樹型搜索算法及其實(shí)現(xiàn)

1、第 PAGE11 頁 共 NUMPAGES11 頁RFID中基于動(dòng)態(tài)二進(jìn)制的改進(jìn)樹型搜索算法及其實(shí)現(xiàn) 【摘要】RFID技術(shù)作為物聯(lián)網(wǎng)應(yīng)用的核心關(guān)鍵技術(shù)，已經(jīng)普及到生產(chǎn)和生活的各個(gè)領(lǐng)域，而如何提高RFID系統(tǒng)防沖突能力，減少總識(shí)別時(shí)間已成為當(dāng)前急需解決的關(guān)鍵。本文提出的基于動(dòng)態(tài)二進(jìn)制的改進(jìn)樹型搜索算法通過簡化閱讀器發(fā)送的指令和沖突檢測過程，并利用棧來保存已經(jīng)被閱讀器接收到的標(biāo)簽EPC數(shù)據(jù)，能最大化的降低閱讀器與標(biāo)簽之間的通信量，有效的提高標(biāo)簽的識(shí)別速度。仿真結(jié)果表明，相比于常規(guī)的確定性標(biāo)簽防沖突算法，該算法顯著提高了性能，尤其在待識(shí)別標(biāo)簽數(shù)量較大的情況下，具有良好的應(yīng)用前景。 【關(guān)鍵詞】RFID

2、；物聯(lián)網(wǎng)；防沖突；樹型搜索；EPC 引言 隨著由物聯(lián)網(wǎng)引領(lǐng)的第三次全球信息化產(chǎn)業(yè)浪潮的不斷推進(jìn)，RFID（射頻識(shí)別）技術(shù)已成為制造全球化、貿(mào)易全球化和物流全球化的核心推動(dòng)力。無線射頻識(shí)別技術(shù)（RadioFrequencyIdentification，RFID）是一種利用無線射頻方式在閱讀器和標(biāo)簽之間進(jìn)行非接觸雙向數(shù)據(jù)傳輸，以達(dá)到目標(biāo)識(shí)別和數(shù)據(jù)交換目的的技術(shù)1。由于其具有非接觸識(shí)別、可識(shí)別高速運(yùn)動(dòng)物體、抗惡劣環(huán)境、保密性強(qiáng)、可同時(shí)識(shí)別多個(gè)識(shí)別對(duì)象等優(yōu)點(diǎn)，射頻識(shí)別技術(shù)已成為當(dāng)今自動(dòng)識(shí)別數(shù)據(jù)收集行業(yè)發(fā)展最快的一種技術(shù)，目前其在交通管理、倉儲(chǔ)管理和生產(chǎn)線自動(dòng)化管理等諸多領(lǐng)域得到了越來越廣泛的應(yīng)用。 在

3、RFID系統(tǒng)中，當(dāng)有多個(gè)電子標(biāo)簽進(jìn)入一個(gè)或多個(gè)閱讀器感應(yīng)區(qū)域的時(shí)候，閱讀器與多個(gè)電子標(biāo)簽的同時(shí)通信會(huì)使得無線通信信號(hào)互相干擾，以致閱讀器無法接收到正確的信息，這種情況一般稱之為“沖突”或“碰撞”等。為了避免沖突的影響，RFID系統(tǒng)定義了一系列當(dāng)沖突發(fā)生時(shí)的操作，而基于這些操作的方法就是防沖突算法2。 一、典型防沖突算法 對(duì)于要求低復(fù)雜度、低功耗以及低成本的RFID系統(tǒng)，最為通用的防沖突機(jī)制是時(shí)分多址復(fù)用（TDMA）。目前流行的兩類標(biāo)簽防沖突算法，主要包括隨機(jī)性算法中的純ALOHA、時(shí)隙ALOHA、動(dòng)態(tài)幀時(shí)隙ALOHA算法等，確定性算法中的二進(jìn)制樹型搜索算法、BBT算法、QT算法等3。隨機(jī)性防沖

4、突算法由于隨機(jī)性大，當(dāng)大量標(biāo)簽讀取時(shí)，幀沖突嚴(yán)重，正確率難以達(dá)到100%。相比而言，確定性防沖突算法的識(shí)別精度和識(shí)別效率有較大提高，因此被廣泛應(yīng)用。本文主要研究和分析基于TDMA的確定性防沖突算法，但是目前的二進(jìn)制算法由于存在較大的通信量和識(shí)別延時(shí)，因此有進(jìn)一步改進(jìn)的空間，本文的動(dòng)態(tài)二進(jìn)制的改進(jìn)樹型搜索算法便是為此而改進(jìn)設(shè)計(jì)的。 二、確定性標(biāo)簽防沖突算法 確定性標(biāo)簽防碰撞算法是以閱讀器為主動(dòng)控制器，進(jìn)入射頻場的所有標(biāo)簽同時(shí)由閱讀器進(jìn)行控制和檢查。閱讀器依據(jù)標(biāo)簽的ID號(hào)首先向標(biāo)簽發(fā)射不同的詢問信號(hào)或指令，閱讀器根據(jù)沖突的信號(hào)，按照二叉樹深度優(yōu)先搜索的思想，逐步縮小搜索范圍，搜索符合條件的標(biāo)簽，直

5、到找到規(guī)定的射頻標(biāo)簽。該方法杜絕了隨機(jī)性算法中的標(biāo)簽“餓死”的情況，具有100%的高識(shí)別率4。最典型的是二進(jìn)制樹型搜索算法，在此基礎(chǔ)上，又出現(xiàn)了逐位比較的二進(jìn)制樹搜索算法5（Bit-by-BitBinaryTreeAlgorithm，BBT），問詢樹算法6（QueryBinaryTreeAlgorithm，QT）等。 1.二進(jìn)制樹型搜索算法 二進(jìn)制樹型搜索算法中為了能辨認(rèn)出閱讀器中數(shù)據(jù)碰撞的比特位的準(zhǔn)確位置，采用的是Manchester編碼1，該編碼約定邏輯1表示發(fā)送信號(hào)由1到0的轉(zhuǎn)變即下降沿跳變，而邏輯0表示發(fā)送信號(hào)由0到1的轉(zhuǎn)變即上升沿跳變。若無狀態(tài)跳變，視為非法數(shù)據(jù)，作為錯(cuò)誤被識(shí)別。當(dāng)兩

6、個(gè)或多個(gè)標(biāo)簽同時(shí)返回的某一數(shù)位有不同的值，則接收到的上升沿和下降沿相互抵消，以致出現(xiàn)“沒有變化”的狀態(tài)，閱讀器由此可判斷該位出現(xiàn)了碰撞。假設(shè)標(biāo)簽1和標(biāo)簽2的ID分別是0 xxxx和0 xxxx，利用曼徹斯特編碼能按位識(shí)別出碰撞位的示意圖如圖1所示。由于標(biāo)簽1和2是同時(shí)傳送其數(shù)據(jù)，利用曼徹斯特編碼閱讀器解碼為07X6X514X302X110，于是閱讀器檢測出1th，3th，5th和6th出現(xiàn)碰撞。 二進(jìn)制樹型搜索算法是由一個(gè)閱讀器和多個(gè)電子標(biāo)簽之間規(guī)定的相互作用（命令和電子標(biāo)簽）順序（規(guī)則）構(gòu)成，根據(jù)電子標(biāo)簽的序列號(hào)大小，按從小到到大的順序依次將所有標(biāo)簽識(shí)別出來。 2.BBT算法 采用BTT算法

7、的標(biāo)簽內(nèi)部都設(shè)有一個(gè)指針，初始時(shí)指針指向標(biāo)簽識(shí)別碼的最高比特位，所有標(biāo)簽處于休眠狀態(tài)。在每一個(gè)查詢輪次，閱讀器首先激活所有未識(shí)別的標(biāo)簽，然后發(fā)送一個(gè)查詢比特0，要求所有標(biāo)簽返回其序列號(hào)的最高位。若標(biāo)簽指針指向的比特和閱讀器查詢比特相同，則發(fā)送它識(shí)別碼的下一個(gè)比特，否則標(biāo)簽就進(jìn)入休眠狀態(tài)而不再參與接下去的查詢。若閱讀器檢測到標(biāo)簽的響應(yīng)沒有沖突，則把接收的比特作為下一步的查詢比特，否則，就用1作為下一步的查詢比特。當(dāng)某個(gè)標(biāo)簽的指針指向識(shí)別碼的最低位，則表明一張標(biāo)簽被識(shí)別，從而一輪識(shí)別過程結(jié)束。而其他標(biāo)簽被重新激活，指針被重置，新的一輪循環(huán)開始。 3.QT算法 QT算法中閱讀器維持了一個(gè)前綴，閱讀器

8、用這個(gè)前綴來問詢標(biāo)簽，記為q1q2qi,只有識(shí)別碼的前綴與這個(gè)問詢前綴相匹配的標(biāo)簽才響應(yīng)并發(fā)送其識(shí)別碼的剩余比特qi+1qjqend，其它不匹配的標(biāo)簽自動(dòng)進(jìn)入休眠狀態(tài)，等待下一次查詢命令。當(dāng)只有一張標(biāo)簽響應(yīng)時(shí)，閱讀器成功識(shí)別標(biāo)簽。若有多張標(biāo)簽響應(yīng)則發(fā)生沖突，則分別增加0和1到閱讀器的前綴中，然后更新問詢前綴為q1q2qiqi0和q1q2qiqi1，開始下一次查詢。整個(gè)識(shí)別過程從問詢前綴0和1開始，通過重復(fù)問詢，直到識(shí)別出所有標(biāo)簽。 三、改進(jìn)的動(dòng)態(tài)二進(jìn)制樹型搜索算法 二進(jìn)制樹型搜索算法是基于確定性策略的，只要時(shí)間足夠，識(shí)別精度可達(dá)100%，因此識(shí)別時(shí)間的長短就成為了評(píng)價(jià)其性能優(yōu)劣的重要標(biāo)準(zhǔn)?；?/p>

9、動(dòng)態(tài)二進(jìn)制的改進(jìn)防碰撞算法簡化了閱讀器發(fā)送的指令和沖突檢測過程，并采用動(dòng)態(tài)方式傳輸標(biāo)簽數(shù)據(jù)。 （一）改進(jìn)的動(dòng)態(tài)二進(jìn)制樹型搜索算法特點(diǎn) 該改進(jìn)算法中每個(gè)標(biāo)簽都有二個(gè)計(jì)數(shù)器flag和count，flag是表示標(biāo)簽是否被屏蔽的標(biāo)志位，為0表示沒有被屏蔽，可以響應(yīng)閱讀器的命令，傳送從計(jì)數(shù)器count指向的對(duì)應(yīng)位開始的EPC（電子產(chǎn)品代碼）數(shù)據(jù)，大于零則表示標(biāo)簽被屏蔽，不響應(yīng)閱讀器的命令。同時(shí)保留了動(dòng)態(tài)調(diào)整二進(jìn)制算法中的后退策略，當(dāng)只檢測到一位碰撞位時(shí)直接識(shí)別兩個(gè)標(biāo)簽，與目前的二進(jìn)制搜索算法相比具有以下一些特點(diǎn)。 （1）閱讀器每次發(fā)送的指令為上一次搜索過程中標(biāo)簽第一次碰撞的位置，減少了指令長度。 （2）

10、閱讀器檢測到有2次比特位發(fā)生沖突時(shí)即停止接受標(biāo)簽傳送的數(shù)據(jù)。該算法只需接受3個(gè)數(shù)據(jù)比特后（0XX）就立刻對(duì)標(biāo)簽沖突做出處理，這樣有效的減少了標(biāo)簽的識(shí)別延時(shí)和閱讀器與標(biāo)簽之間的通信量。 （3）閱讀器利用棧stack和string來保存已經(jīng)被閱讀器接收到的標(biāo)簽數(shù)據(jù)，因此每次搜索中標(biāo)簽只需傳送部分?jǐn)?shù)據(jù)，減少了大量的傳輸時(shí)間。 （二）改進(jìn)的動(dòng)態(tài)二進(jìn)制樹型搜索算法描述 該算法是應(yīng)用于RFID的防碰撞算法，算法的實(shí)施依賴于閱讀器與標(biāo)簽，因此下面分兩部分描述算法的詳細(xì)流程，初始狀態(tài)棧stack和string均為空，標(biāo)簽的EPC為n位，每個(gè)標(biāo)簽的計(jì)數(shù)器flag和count均為0。算法中符號(hào)EPC(i，j)表示

11、標(biāo)簽傳送從ith到j(luò)th比特的EPC數(shù)據(jù)位。+表示連接的操作，例如0110+1010=0 xxxx。 閱讀器部分的算法流程： 1.設(shè)置初始值t=n-1，PushtintoT（將t入棧T），進(jìn)入標(biāo)簽搜索過程。 2.While棧T不為空 (1)t=Pop(T)取出棧頂元素，Request(t)發(fā)送請(qǐng)求命令 (2)接收標(biāo)簽的應(yīng)答并檢測沖突 (3)if有2位沖突碰撞 1)PushtintoT當(dāng)前t參數(shù)入棧 2)獲取第一次碰撞發(fā)生的位置s。t=s，將t入棧T。 3)Pushstring+EPC(count, s-1)+1intostack 保存被屏蔽標(biāo)簽比特位到棧stack 4)string=strin

12、g+EPC(count,s-1)+0 保存未被屏蔽標(biāo)簽比特位 elseif只有一位沖突碰撞 5)標(biāo)簽ID1=string+EPC(count,s-1)+0+EPC(s+1,n-1) 識(shí)別標(biāo)簽 6)標(biāo)簽ID2=string+EPC(count,s-1)+1+EPC(s+1,n-1) 識(shí)別標(biāo)簽 7)string=Pop(stack)取出被屏蔽標(biāo)簽比特位 8)選擇標(biāo)簽，讀取數(shù)據(jù)后去選擇 else 9)標(biāo)簽ID=string+EPC(count,n-1)無沖突發(fā)生，識(shí)別標(biāo)簽 10)string=Pop(stack)取出被標(biāo)簽屏蔽比特位 11)選擇標(biāo)簽，讀取數(shù)據(jù)后去選擇； 標(biāo)簽部分的算法流程： swit

13、ch閱讀器發(fā)送的命令 1.caseRequest(t)：請(qǐng)求命令 (1)ift=n-1 所有未被去選擇的標(biāo)簽傳送比特位EPC(count,n-1) else (2)ift+1count且flag=0 count=t+1； (3)if標(biāo)簽第t比特位為0且flag=0 傳送比特位EPC(count,n-1)； (4)elseflag+； break； 2.caseSelect(EPC)： if(flag0)flag-；標(biāo)簽被識(shí)別后被屏蔽的標(biāo)簽flag值減 break； （三）改進(jìn)的動(dòng)態(tài)二進(jìn)制樹型搜索算法性能分析與比較 我們假設(shè)標(biāo)簽EPC長度是64，每個(gè)標(biāo)簽的EPC值是隨機(jī)分配的。閱讀器和標(biāo)簽的數(shù)據(jù)

14、傳輸速率均為40Kbps，tdelay為20s，一個(gè)空閑時(shí)隙為40s。從算法的通信量和識(shí)別時(shí)間兩個(gè)方面與QT算法、動(dòng)態(tài)調(diào)整二進(jìn)制算法、BTT算法進(jìn)行比較，并通過計(jì)算機(jī)軟件對(duì)系統(tǒng)仿真分析，仿真結(jié)果如圖2和圖3所示。 從圖2可以看出，改進(jìn)算法隨著標(biāo)簽數(shù)量的增加，信息量節(jié)省越加明顯；由圖3中的仿真結(jié)果可見，改進(jìn)算法在識(shí)別效率上也明顯優(yōu)于其他二進(jìn)制搜索算法，這正是改進(jìn)算法對(duì)信息量優(yōu)化的結(jié)果。 四、結(jié)束語 射頻識(shí)別系統(tǒng)是一個(gè)不小的系統(tǒng)工程，要考慮相當(dāng)多的因素。RFID中基于動(dòng)態(tài)二進(jìn)制的改進(jìn)樹型搜索算法著重減少閱讀器與標(biāo)簽之間的通信量，從而有效提高標(biāo)簽的識(shí)別速度。仿真結(jié)果表明，算法性能優(yōu)于目前的二進(jìn)制搜索

15、算法。由于標(biāo)簽內(nèi)部沒有電源，就要求標(biāo)簽消耗的能量盡量小，即最小化標(biāo)簽和讀寫器間的傳遞信息。本文提出的改進(jìn)算法較好地降低了標(biāo)簽與閱讀器之間的通信量，減少了標(biāo)簽的功率消耗。在標(biāo)簽中設(shè)置計(jì)數(shù)器的成本很低，采用本算法是有實(shí)用價(jià)值和可行的。 參考文獻(xiàn)： 1寧煥生.RFID重大工程與國家物聯(lián)網(wǎng)M.北京:機(jī)械工業(yè)出版社,2010. 2K.Finkenzeller,RFIDHandbook:Radio-frequencyidentificationfundamentalsandapplications.Secondedition,UK:JohnWileyandSonsLtd,2003. 3朱曉榮,齊麗娜,孫君等.物聯(lián)網(wǎng)與泛在通信技術(shù)M.北京:人民郵電出版社,2010. 4江岸.無線射頻識(shí)別系統(tǒng)中防碰撞問題的研究D.武漢:計(jì)算機(jī)與通信學(xué)院,2010. 5陳博.一種類二進(jìn)制搜索的RFID系統(tǒng)防碰撞算法及其實(shí)現(xiàn)J.電子器件,2006,29(1):286-289. 6KashifAli,HossamHassanein,Abd-ElhamidM.Taha.RFIDAnti-collisionProtocolforDensePassiveTagEnvironments.