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

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

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

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

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

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

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

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

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

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

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

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

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

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

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