改進的二進制防碰撞識別算法及其FPGA仿真實現

汪　紅，田莎莎，王芳芳

(中南民族大學 計算機科學學院，武漢 430074)

?

改進的二進制防碰撞識別算法及其FPGA仿真實現

汪紅，田莎莎，王芳芳

(中南民族大學 計算機科學學院，武漢 430074)

摘要對RFID系統(tǒng)中的多標簽防碰撞問題進行了研究，在3種經典的確定性防碰撞算法的基礎上，提出了改進的二進制防碰撞識別算法.為了降低數據傳輸量，改進算法采用閱讀器前綴查詢和標簽后綴應答相結合的方式；為了降低查詢次數，查詢算法針對不同數量的碰撞位采用不同的處理方式.對4種算法進行了Matlab仿真和Spartan6硬件平臺實現，實驗結果表明：改進算法較3種經典算法具有較高的識別效率和較低的數據傳輸量.

關鍵詞無線射頻識別；防碰撞識別；查詢；數據傳輸

在RFID系統(tǒng)工作過程中，常常會發(fā)生多路電子標簽同時出現在RFID閱讀器工作范圍內的情況，由于各標簽工作信道頻率、編碼方式相同，閱讀器發(fā)出詢問指令后，兩個或兩個以上的標簽同時應答發(fā)送自身數據，從而產生碼元上的串擾，即為碰撞[1,2].為了減少和防止碰撞的產生，達到短時間內逐個識別標簽的目的，需要采取相應的措施來解決碰撞(沖突)引起的識別盲區(qū)，目前主要有兩種策略，即隨機性防碰撞算法和確定性防碰撞算法.前者基于隨機存儲思想，后者基于二叉樹逐位分割識別思想[3,4].本文對確定性防碰撞算法進行深入研究，并提出了改進算法.

1確定性防碰撞算法

1.1基本二進制防碰撞算法

該算法是最基本的基于二叉樹搜索的識別算法，它通過閱讀器發(fā)送不同請求命令區(qū)分不同的待識別標簽，標簽通過檢查自身數據序列號與請求命令的參數是否匹配來確定是否向閱讀器發(fā)送消息，若標簽序列號不大于閱讀器發(fā)送的命令參數，該標簽就將自身序列號通過射頻信號發(fā)送給閱讀器，接著閱讀器對接收到的數據進行分析后，判斷是否發(fā)生碰撞，如果反饋回來的數據序列發(fā)生了碰撞，下輪查詢時閱讀器發(fā)送的命令中會根據反饋數據改變參數以減少反饋標簽數目，通過此命令繼續(xù)查詢，直到反饋回唯一的一個序列號為止，這時表示成功識別了該標簽.

設共存在N個待測標簽，則閱讀器總查詢次數為：Q=log2(N)+log2(N-1)+…+log22+log21+N=

log2(N!)+N.

(1)

在RFID系統(tǒng)中，閱讀器識讀標簽是一個半雙工通信過程.閱讀器讀到標簽反饋回來的數據需要兩個步驟，第一步是閱讀器發(fā)送查詢命令，第二步是符合條件的標簽發(fā)送數據到閱讀器端.假設標簽序列號的長度為L，則閱讀器和標簽傳輸的總信息量P為：

P=2QL=2L(log2(N!)+N).

(2)

1.2動態(tài)二進制算法

動態(tài)二進制識別算法從減少通信數據量上對基本算法進行了改進.對于同樣的待識別標簽組，兩種算法需要的查詢次數是一樣的，所以二者的系統(tǒng)吞吐量相等.動態(tài)二進制防碰撞算法的優(yōu)勢在于：在每次查詢時，閱讀器的命令行與標簽返回數據序列長度都會動態(tài)地調整，具體而言，體現在下面兩個方面：一是算法實現過程中系統(tǒng)總的數據通信量；二是完成標簽識別所花的時間.為了便于分析，假定數據交換過程中，閱讀器和標簽之間都只傳遞標簽序列號相關信息，那么在基本二進制查詢算法中，閱讀器與標簽二者都傳送了完整的序列號，但是在動態(tài)二進制防碰撞查詢算法中，閱讀器只發(fā)送前綴序列號，通過匹配的標簽會返回自身序列號除去前綴后的剩余位，閱讀器收到回復后，把前綴和標簽返回序列連接后得出完整的標簽序列號.顯然，在算法運行過程中，動態(tài)二進制查詢算法相當于傳送了兩倍于基本二進制搜索算法的數據量.由此可見，動態(tài)二進制防碰撞算法在傳送的信息量方面較基本二進制查詢算法提高了近一倍.設閱讀器可識別范圍內標簽數目為N，標簽序列號的長度為L，閱讀器和標簽傳輸的總信息量P為：

(3)

1.3后退式二進制算法

由于基本二進制查詢算法成功識別一個標簽后，閱讀器返回二叉樹的根節(jié)點，恢復最初的命令，從二叉樹的根部重新開始逐位查詢標簽，對多標簽系統(tǒng)的識別效率有很大影響.后退式二進制防碰撞算法吸收了返回退避思想，當閱讀器成功識別一個標簽后，算法返回上級(父節(jié)點)，轉向另外一個分支查詢，而無需返回整棵二叉樹的根節(jié)點.當標簽數目很多時，對系統(tǒng)效率的提高有很大幫助.

設閱讀器可識別范圍內標簽數目為N，閱讀器總查詢次數Q為：

Q=2N-1.

(4)

設標簽序列號的長度為L，閱讀器和標簽傳輸的總信息量P為：

P=2QL=2L(2N-1).

(5)

2改進的二進制防碰撞算法

2.1算法思路

二進制防碰撞識別算法在RFID多標簽自動識別系統(tǒng)中的應用很廣泛.在確定性防碰撞識別算法中，存在兩個影響識別時間的重要因素：查詢次數和通信數據量.基于此，主要的改進思路有兩個.

(1)盡量減少每次閱讀器和標簽通信過程中數據傳輸的總比特數.在基本二進制查詢算法(BS)中，閱讀器和標簽互通的數據位數至少是整個標簽序列號的長度N，讀寫器和標簽都重復發(fā)送了許多數據比特位，含有大量的冗余信息，動態(tài)二進制查詢算法(DBS)在查詢次數上有所提高，它將發(fā)生碰撞的最高位和之前的部分位一起作為查詢前綴，所有前綴與這個查詢前綴相同的標簽都返回自身序列號，在傳輸數據比特數方面，動態(tài)二進制算法比基本二進制算法減少至一半.由于數據傳輸量減少了一半，從時間上來看，系統(tǒng)識別效率也得到了極大的提高.于是改進的算法采用動態(tài)二進制查詢算法閱讀器前綴查詢和標簽后綴應答相結合的方式.

(2)降低閱讀器識別標簽過程中的查詢次數.無論哪一種算法，閱讀器首次發(fā)出標簽讀取命令后，閱讀器可識別范圍內的所有標簽都會做出答復，讀寫器將接收的數據進行譯碼后，有n個比特位不確定“0”、“1”的情況，即接收數據序列有n個碰撞位，根據碰撞位所在位置作如下處理.

1) 碰撞位是連續(xù)的兩位，采用四叉樹查詢搜索，即00 01 10 11；

2) 碰撞位不連續(xù)或連續(xù)碰撞位數超過兩位，繼續(xù)采用二叉樹查詢法搜索，即：0和1；

3) 碰撞位只有一位，理論上閱讀器可以直接識別出兩個碰撞標簽，所以在這種情況下閱讀器不再發(fā)送確認命令，而是直接識別碰撞位分別是0和1的兩種標簽，以達到減少查詢次數的效果.

2.2算法性能分析

設閱讀器可識別范圍內標簽數目為N，在使用改進算法的過程中，出現一個碰撞位的情況依實際應用場合而定，最壞情況下，是沒有一次出現單個碰撞位的情況，此時查詢次數與后退式二進制防碰撞查詢算法一樣為2N-1，在此基礎上出現單碰撞位的次數為x，查詢次數就縮減2x，即總查詢次數Q為：

Q=2N-1-2x.

(6)

設標簽序列號的長度為L，對N個標簽進行查詢的過程中出現單碰撞位的概率為：

(7)

則對N個標簽進行查詢時可能出現單個碰撞位的平均數量為：

(8)

用X替換式(6)中的x可得：

(9)

改進算法的數據傳輸量從宏觀上看是兩個部分：來自閱讀器的前綴查詢命令和來自標簽的匹配返回序列數據.閱讀器和標簽發(fā)送的都不是完整的序列號，組合起來才是一個完整的長度為L的序列號，因此從理論上講，改進算法的系統(tǒng)數據傳輸量會比后退式二進制算法減少一半.

當待識別的標簽數量N>2時，由于閱讀器第一次發(fā)送的請求指令為null，標簽返回的數據是L個比特位，在隨后的查詢式識別通信中，閱讀器發(fā)出的屏蔽指令若為m個比特位.經過屏蔽后的標簽序列號的位數變?yōu)長-m，總之，每次通信標簽響應信息和閱讀器命令信息長度之和等于L，于是得出改進算法識別所有標簽需要的數據傳輸量為：

P=LQS=L(2N-2x-1).

(10)

用X替換式(10)中的x可得：

(11)

3仿真結果與分析

3.1算法識別過程實驗分析與比較

假定閱讀器識讀范圍內有4個電子標簽，標簽A：0110101；標簽B：0010011；標簽C：0011010；標簽D：0110111；閱讀器首先發(fā)送請求命令給在其作用范圍內的標簽，此時4個標簽都響應閱讀器.由于有多個標簽同時回復閱讀器，返回的數據存在碰撞情況，這時閱讀器端的二進制防碰撞搜索算法開始執(zhí)行，直至4個標簽全部都被識別出來.基本二進制查詢算法的具體識別過程如表1所示，表1列出了每輪查詢閱讀器發(fā)送的命令參數，以及對它做出響應的標簽和在此次查詢中成功識別的標簽.

表1　基本二進制查詢算法的識別過程

動態(tài)識別算法識別過程如表2所示，特點是閱讀器只發(fā)送前綴命令，具備特定前綴的標簽只返回自身序列號除去前綴后的那一部分數據.

表2　動態(tài)二進制識別算法的識別過程

后退式二進制防碰撞算法是基于基本二進制算法，吸收了返回退避思想進行改進的.閱讀器成功識別一個標簽后，算法就返回上級(父節(jié)點)，轉向另外一個分支查詢，而不是返回整棵二叉樹的根節(jié)點.具體識別過程見表3.

表3　后退式二進制識別算法的識別過程

改進算法的識別過程如表4所示.

表4　改進算法的識別過程

從4種算法的識別過程看出，對4個序列長度為7的標簽進行識別時，改進算法較3種經典算法擁有最小的查詢次數和最低的數據傳輸量.

3.2查詢次數與數據傳輸量比較

為了驗證改進算法在對任意數量的標簽進行識別時的性能，以序列長度為7的標簽為例，對4種算法進行了Matlab仿真.因為長度為7，所以可以組成的不同標簽的數目最多為128個，所以N可以取1～128，仿真結果如圖1、圖2所示.

從圖1可以看出，基本二進制算法和動態(tài)二進制算法在查詢次數方面性能相同，它們的曲線基本重合.改進算法的查詢次數遠遠低于基本二進制算法和動態(tài)二進制算法，也低于后退式二進制算法.

圖1　4種算法的查詢次數比較Fig.1　Search frequencies comparation of four algorithms

圖2　4種算法的數據傳輸量比較Fig.2　Data transmission quantity comparation of four algorithms

從圖2可以看出，在數據傳輸量方面改進算法比每一種經典算法都小了一半以上.

在標簽總數相同的情況下，改進后的算法較3種經典算法效果都要好，而且隨著RFID系統(tǒng)中待識別標簽數目的增加，在傳輸數據量方面，改進算法的優(yōu)勢更加明顯.

4FPGA實現

4.1FPGA實現總體設計方案

目前在RFID多標簽識別系統(tǒng)的防碰撞算法的實現中，大多數使用軟件實現的方式，但當對系統(tǒng)有較高處理速度要求時，采用硬件實現可以更好地滿足要求.利用FPGA對算法進行功能仿真在一定程度上能提高系統(tǒng)的實時性[5,6].圖3是FPGA實現RFID系統(tǒng)防碰撞策略的總體規(guī)劃.

為了實現算法的功能仿真，系統(tǒng)由以下幾個模塊構成：模擬標簽編碼模塊、Manchester解碼及定位碰撞模塊、LIFO棧模塊、狀態(tài)機控制模塊.

圖3　防碰撞識別算法總體框圖Fig.3　Block diagram of the anti-collision recognition algorithm

4.2系統(tǒng)狀態(tài)機及防碰撞算法的仿真實現

4.2.1閱讀器控制狀態(tài)機的實現

狀態(tài)機控制模塊是算法的核心，類似于系統(tǒng)CPU的作用.它向標簽(Manchester編碼模塊)發(fā)送查詢指令，接收來自多標簽(Manchester解碼模塊)的返回數據；根據數據碰撞情況來選擇下一步命令；同時控制對LIFO模塊的存取指令操作，保證各子模塊準確、有序地工作.

VerilogHDL狀態(tài)機有兩種：Mealy狀態(tài)機和Moore狀態(tài)機.在本系統(tǒng)的狀態(tài)機轉換模塊的設計中，指令狀態(tài)由當前狀態(tài)和LIFO棧頂元素決定，所以采用Moore型狀態(tài)機實現主控模塊的狀態(tài)轉移，如圖 4所示.該模塊總共使用8種狀態(tài)，含義如下：

空閑：系統(tǒng)復位操作下默認的初始化狀態(tài)；

查詢：對可識別范圍的標簽首次廣播查詢命令，轉入等待狀態(tài)；

等待：等待響應狀態(tài)，若接收到解碼模塊的ready信號，轉至接收狀態(tài)；若系統(tǒng)等待超時，轉回查詢狀態(tài)，重新廣播查詢命令；

接收：收到解碼器翻譯后的數據，檢查數據系列有無碰撞位，若無或只有一位，則轉入識別狀態(tài)；若有多位碰撞，則轉至入棧狀態(tài)；

入棧：依據碰撞位信息分析后，將下一步右子樹查詢指令存入堆棧，同時將命令更新成左子樹查詢，繼而跳回查詢狀態(tài)；

選擇：對于確定序列號的標簽，閱讀器直接識別，對于解碼得到的單碰撞位的序列閱讀器通過分析間接識別，不再發(fā)送查詢識別指令.之后轉入休眠狀態(tài)；

休眠：閱讀器發(fā)送休眠命令給選擇狀態(tài)識別或分析出來的標簽，休眠指令作用后的標簽便不再響應之后的查詢指令.接著檢查LIFO是否為空，若為空，跳至空閑狀態(tài)；若非空，轉至出棧狀態(tài)；

出棧：取出上一次存入LIFO的標簽查詢命令，轉到查詢狀態(tài).

圖4　狀態(tài)機狀態(tài)轉換圖Fig.4　State transition diagrams of the state machine

4.2.2防碰撞識別算法的仿真實現

經過對算法的各個功能模塊分別進行功能仿真，驗證了各模塊的正確性，在此基礎上實現各子模塊級聯(lián)后，對算法進行綜合仿真測試.

測試模塊內部的數據表示如下：

clk：系統(tǒng)時鐘；

rst：系統(tǒng)復位信號；

SN_Rd：閱讀器查詢命令使能信號；

SNi：RFID系統(tǒng)中標簽i的SN碼輸入端(i=1,2,…,6)；

SN_OUT：成功識別的標簽SN碼輸出端.

測試中設定閱讀器識別區(qū)域內共有6個RFID標簽，代表標簽的SN碼為8位二進制碼.這些標簽的序列號分別設定為：SN1=10100011，SN2=10011011，SN3=00010001，SN4=10100101，SN5=10010011，SN6=00010101.

圖5為改進型二進制防碰撞識別算法的仿真結果，圖中的SN_Rd信號上升沿有效，表示閱讀器識別標簽過程中的查詢指令使能標志，該信號共有8個脈沖電平跳變，表示完成6個標簽的識別共執(zhí)行了8次查詢命令.SN_OUT表示成功識別的標簽的SN碼輸出端，因此圖中SN_OUT的輸出可以驗證該算法的正確性.

圖5　多標簽的防碰撞算法的仿真結果Fig.5　Simulation results of the multiple tags anti-collision algorithm

5結論

本文在對RFID系統(tǒng)確定性多標簽防碰撞算法進行比較研究的基礎上，結合二進制動態(tài)識別算法和后退式二進制算法的優(yōu)點，加入單碰撞位智能識別方法，得出改進式前綴查詢算法的基本思路.實驗結果和FPGA仿真均證明該算法具有較強的可操作性，與單一式動態(tài)二進制算法和后退式二進制算法相比，識別效率有所提高.

參考文獻

[1]吳躍前，辜大光，范振粵.RFID系統(tǒng)防碰撞算法比較分析及其改進算法[J].計算機工程與應用，2009,45(3): 210-213.

[2]劉金艷，馮全源. 無線射頻識別多標簽防碰撞算法綜述[J]. 計算機集成制造系統(tǒng)，2014,20(2): 440-451.

[3]孫科學，張瑛，周明秀. 跳躍式二進制防碰撞算法的設計與實現[J]. 計算機技術與發(fā)展, 2013, 23(4): 59-62.

[4]IannelloF,SimeoneO,PopovskiP,etal.Energygroup-baseddynamicframedALOHAforwirelessnetworkswithenergyharvesting[J].InformationSciencesandSystems(CISS), 2012, 1(6):21-23.

[5]李鵬，高遠，黃志敏，等.RFID系統(tǒng)中基于ISO18000-6的信號編解碼設計[J]. 測繪信息與工程，2008, 33(5): 29-30.

[6]張捍東，張淳. 基于FPGA的RFID閱讀器設計[J].自動化儀表, 2009, 30(5): 60-62.

ImprovedBinaryAnti-CollisionRecognitionAlgorithmandItsFPGASimulationImplementation

Wang Hong，Tian Shasha，Wang Fangfang

(CollegeofComputerScience,South-CentralUniversityforNationalities,Wuhan430074,China)

AbstractMultipletagsanti-collisionproblemofRFIDsystemwasstudied.Onthebasisofthethreeclassicanti-collisionalgorithms,animprovedbinaryanti-collisionrecognitionalgorithmwaspresented.Inordertoreducetheamountofdatatransmission,theimprovedalgorithmusesthecombinationmethodofthereaderprefixqueriesandthetagsuffixresponse.Inordertoreducethenumberofquery,queryalgorithmadoptsdifferentapproachforthedifferentnumberofcollisions.MatlabsimulationandSpartan6implementationwereusedtothefouralgorithms,andtheexperimentalresultsshowedthattheimprovedalgorithmhashigherrecognitionefficiencyandloweramountofdatatransmissionthanthethreeclassicalgorithms.

KeywordsRFID;anti-collisionrecognition;query;datatransmission

收稿日期2016-03-03

作者簡介汪紅(1968-)，女，副教授，碩士生導師，研究方向：計算機系統(tǒng)結構，嵌入式系統(tǒng)，E-mail:wanghong_2010@foxmail.com

基金項目湖北省自然科學基金面上項目(2015CFC876)；中央高?；究蒲袠I(yè)務費專項資金資助(青年)項目(CZQ14010)；中南民族大學教學研究項目(JYX13047)

中圖分類號TP309.7

文獻標識碼A

文章編號1672-4321(2016)02-0122-06