張 琴(福州職業(yè)技術(shù)學(xué)院計算機系，福建福州 350108)

基于物聯(lián)網(wǎng)的RFID自適應(yīng)多叉樹防碰撞算法研究

張 琴
(福州職業(yè)技術(shù)學(xué)院計算機系，福建福州 350108)

如何設(shè)計高效實用的防碰撞算法是RFID系統(tǒng)實現(xiàn)中亟待解決的關(guān)鍵技術(shù)問題。本文對常見的多標(biāo)簽防碰撞算法的優(yōu)缺點進行分析，針對常見的二叉樹防碰撞算法存在的通信量大、搜索次數(shù)過多等問題，提出一種自適應(yīng)分裂樹的防碰撞算法。仿真結(jié)果表明，相對于基本二進制樹防碰撞算法，本文算法的系統(tǒng)吞吐率可以保持在50%以上，搜索次數(shù)和數(shù)據(jù)通信量也大大降低，非常適用于大量標(biāo)簽識別的物聯(lián)網(wǎng)。

物聯(lián)網(wǎng)；RFID；Manchester編碼；防碰撞算法

物聯(lián)網(wǎng)(Internert of Things)是利用射頻識別、傳感器等技術(shù)，按約定的協(xié)議將所有物品與互聯(lián)網(wǎng)連接起來，實現(xiàn)智能化識別和管理的下一代信息網(wǎng)絡(luò)，廣泛應(yīng)用于工商業(yè)、物流等領(lǐng)域[1]。RFID(Radio Frequency Identification)是一種非接觸的無線自動識別和獲取信息的技術(shù)，它與ZigBee技術(shù)、LTE技術(shù)和云計算并稱為物聯(lián)網(wǎng)四大關(guān)鍵性應(yīng)用技術(shù)[2]。一般來說RFID系統(tǒng)由閱讀器和標(biāo)簽兩部分組成，系統(tǒng)運行時，有多個標(biāo)簽處于閱讀器的作用范圍內(nèi)，在同一時刻這些標(biāo)簽向閱讀器回復(fù)信息時，將導(dǎo)致所傳輸信息相互干擾，這種干擾稱為“碰撞”，標(biāo)簽碰撞會對閱讀器識別標(biāo)簽和對標(biāo)簽進行讀寫操作產(chǎn)生不利影響。信息碰撞問題是影響RFID讀取效率的重要原因之一。因此設(shè)計高效的防碰撞算法是眾多學(xué)者研究的熱點問題。

針對標(biāo)簽識別過程中的碰撞問題，比較常用的解決技術(shù)有空分多址(SDMA)、時分多址(TDMA)、頻分多址(CDMA)和碼分多址(CDMA)等，其中時分多址是最常用的技術(shù)[3]?；赥DMA技術(shù)的防碰撞算法主要有兩類：一是ALOHA類算法，二是基于二進制樹機制的防碰撞算法。ALOHA算法檢測碰撞的過程完全依賴于閱讀器發(fā)送的命令，操作簡單、成本低，缺點是ALOHA算法發(fā)生碰撞的概率很高，尤其是當(dāng)標(biāo)簽數(shù)目較多的時候，該算法性能急劇下降。針對純ALOHA算法的種種局限性，一些改進的算法，如時隙ALOHA算法、幀時隙ALOHA算法、分組時隙ALOHA算法和動態(tài)幀時隙ALOHA算法陸續(xù)出現(xiàn)[4]。但是，基于ALOHA機制的防碰撞算法的時隙具有隨機性，是不確定的算法，都可能出現(xiàn)一些標(biāo)簽很長一段時間都不能被識別的情況，即“標(biāo)簽餓死”。

基于二進制樹機制的算法則是確定型的，是一種閱讀器控制算法。這類算法通過將大量待識別標(biāo)簽劃分到不同子集，直到某一個子集中出現(xiàn)可識別的標(biāo)簽，重復(fù)此類操作，逐步完成全部標(biāo)簽的識別[5]?；诙M制樹的搜索算法每一次僅產(chǎn)生兩個分裂子集，分裂速度慢，搜索次數(shù)多，如果標(biāo)簽數(shù)量過大，會存在大量碰撞時隙導(dǎo)致系統(tǒng)效率低。而基于查詢樹的算法由于需要進行標(biāo)簽匹配相關(guān)的操作而需要花費較大通信和處理成本。

針對上述一系列算法存在的缺陷，本文提出了一種改進的自適應(yīng)分裂樹防碰撞算法，根據(jù)碰撞位數(shù)，自適應(yīng)選擇分裂樹，提高搜索效率，減少標(biāo)簽與閱讀器之間的通信量。同時，定義狀態(tài)計數(shù)器并且運用矩陣思想對碰撞位進行處理，減少空閑時隙。最后通過MATLAB仿真對算法性能進行比較和分析。

1 算法約定

1.1 算法通信方式

為了準(zhǔn)確地確定碰撞位，本文中標(biāo)簽與閱讀器之間的數(shù)據(jù)通信采用曼徹斯特編碼。該編碼是采用電平的改變來表示數(shù)值，其中上升沿編碼為邏輯0，下降沿編碼為邏輯1。每一位的中間有一跳變，若無狀態(tài)跳變，則視為非法數(shù)據(jù)[6]。當(dāng)多個同時返回的標(biāo)簽編碼數(shù)位有不同之值時，碰撞位上的上升沿和下降沿就會相互抵消，以至無狀態(tài)跳變，閱讀器就能夠很準(zhǔn)確地檢測出碰撞位。假設(shè)有2個RFID標(biāo)簽，其EPC編碼(假定為8位)分別為tag1∶10111001和tag2∶10100001，當(dāng)2個標(biāo)簽同時向閱讀器發(fā)送自己的EPC編碼信息時，利用Manchester編碼檢測碰撞位置的示意圖如圖1所示。

圖1 Manchester編碼碰撞位識別原理示意圖

1.2 算法命令

1.2.1 查詢命令

CALL(NULL)：首次查詢時閱讀器要求其作用范圍的所有標(biāo)簽進行應(yīng)答，將自身的EPC值發(fā)送給閱讀器。

CALL(HP，HPValue，LP，LPvalue)：參數(shù)HP、LP分別表示檢測到碰撞的最高位和最低位，當(dāng)閱讀器檢測到碰撞位數(shù)大于2時發(fā)出此命令，要求標(biāo)簽返回其第HP-1至LP-1之間的數(shù)據(jù)。

CALL(HP，HPValue)：參數(shù)HP為檢測到碰撞的最高位，HPValue取值為0或1，是最高碰撞位的取值。

1.2.2 標(biāo)簽休眠

SLEEP(epc，m)：如果標(biāo)簽的epc碼與SLEEP命令中的epc碼前m位相等，那么這些標(biāo)簽進入睡眠狀態(tài)，不再響應(yīng)閱讀器的CALL命令。如果需要重新激活標(biāo)簽，則必須使該標(biāo)簽離開閱讀器作用范圍后重新進入。

1.2.3 選擇命令

SELECT：將標(biāo)簽的epc編碼作為參數(shù)，表示某一標(biāo)簽被選中，并作為執(zhí)行讀出或?qū)懭氲绕渌畹拈_關(guān)。

1.2.4 讀寫數(shù)據(jù)命令

ReadData：應(yīng)答了SELECT命令的標(biāo)簽將其存儲的數(shù)據(jù)發(fā)送給閱讀器。

2 算法原理及流程

閱讀器發(fā)送CALL(NULL)命令，其作用范圍內(nèi)的所有電子標(biāo)簽向閱讀器傳回其自身的EPC編碼信息，閱讀器接收到反饋信息時，檢測回傳標(biāo)簽信息的碰撞情況，如果檢測到碰撞發(fā)生，標(biāo)簽將根據(jù)碰撞位連續(xù)的情況自適應(yīng)選擇二叉樹或四叉樹分組。如果檢測到自最高碰撞位起連續(xù)2位及以上的EPC編碼碰撞，則由狀態(tài)計數(shù)器statue的值(1，2，3，4)確定HP、LP的值(00，01，10，11)，閱讀器發(fā)送命令CALL(HP，HPValue，LP，LPvalue)；標(biāo)簽在回傳信息時，由于標(biāo)簽編碼的HP之前和LP之后的信息是已知的，所以標(biāo)簽只要回傳最高碰撞位HP與最低碰撞位LP之間的數(shù)據(jù)，從而降低了電子標(biāo)簽和閱讀器之間的通信量。算法的流程圖如圖2所示。

圖2 自適應(yīng)多叉樹防碰撞算法流程圖

具體的程序?qū)崿F(xiàn)如下：

矩陣sHr，sLr，str為空，標(biāo)志狀態(tài)位statue=1;

//初始化操作。sHr(存儲最高碰撞位)，sLr(存儲最低碰撞位)，str(存儲當(dāng)前狀態(tài)計數(shù)器statue的值)

CALL(NULL);

If(碰撞位數(shù)==0) 識別標(biāo)簽并進行操作，算法結(jié)束;

If(碰撞位數(shù)==1) 碰撞位賦值0、1，識別標(biāo)簽并進行操作，算法結(jié)束;

If(碰撞位數(shù)==2) CALL(HP,HPValue)進行二叉樹查詢;

Else

While(碰撞位數(shù)>2)

{記錄HP,LP,;

While(statue<=4)

{CALL(HP,HPValue,LP,LPvalue);

If(碰撞位數(shù)==1) 碰撞位賦值0、1，識別標(biāo)簽并進行操作

If(碰撞位數(shù)==2) CALL(HP,HPValue)進行二叉樹查詢;

statue++;

If(sHr為空)算法結(jié)束;

else Pop sHr(HP),Pop sLr(LP),Pop str(statue);

If(碰撞位數(shù)>2) break;}

Push HP into sHr, Push LP into sLr, Push statue into str;}

3 算法仿真及結(jié)果分析

為了驗證本文中自適應(yīng)多叉樹防碰撞算法的有效性，下面利用Matlab軟件對該算法的查詢次數(shù)和吞吐量進行仿真實驗，比較的算法為基本二進制樹防碰撞算法，取標(biāo)簽編碼位數(shù)為8，仿真30次取平均值。兩種算法的搜索次數(shù)與標(biāo)簽數(shù)目的關(guān)系如圖3所示，吞吐量隨標(biāo)簽數(shù)目增多變化情況如圖4所示。

由圖3可知，EPG編碼位數(shù)為8的條件下，當(dāng)標(biāo)簽數(shù)目比較少時，兩種算法搜索次數(shù)差別不太大，隨著標(biāo)簽數(shù)目的增多，空閑時隙情況逐漸減少，本文中算法的優(yōu)勢越來越明顯?；镜亩M制樹防碰撞算法搜索次數(shù)隨標(biāo)簽數(shù)目增加接近線性增長，而本文中算法當(dāng)標(biāo)簽數(shù)目增加到200之后搜索次數(shù)基本上處于穩(wěn)定狀態(tài)，原因在于自適應(yīng)多叉樹算法可以降低查詢樹體復(fù)雜度，簡化搜索流程，進而使查詢次數(shù)大大減少。

圖3 兩種算法搜索次數(shù)對比圖

圖4 兩種算法吞吐量對比圖

由圖4可知，EPG編碼位數(shù)為8的條件下，隨著標(biāo)簽數(shù)量的增加，基本的二進制樹防碰撞算法吞吐量維持在10%～20%之間，而自適應(yīng)多叉樹算法吞吐量明顯高于比較算法，吞吐量基本上都高于50%。究其原因，一方面本文算法能進行自適應(yīng)搜索，避免搜索樹體過大出現(xiàn)過多無效搜索，閱讀器每一次的查詢命令都有有效應(yīng)答；另一方面如果連續(xù)碰撞位數(shù)等于1，算法能一次性識別兩個標(biāo)簽。所以本文提出的算法可以達到很高的吞吐量。

4 結(jié)語

針對傳統(tǒng)的二進制樹防碰撞算法存在的通信量大、搜索樹體龐大導(dǎo)致存在大量無效搜索等問題，本文提出了一種新穎的自適應(yīng)分裂樹防碰撞算法，該算法在二進制樹搜索算法的基礎(chǔ)上根據(jù)碰撞位數(shù)，自適應(yīng)選擇分裂樹，提高搜索效率，減少標(biāo)簽與閱讀器之間的通信量。同時定義狀態(tài)計數(shù)器并且運用矩陣思想對碰撞位進行處理，減少空閑時隙。最后通過實驗證明了本算法相較于常見的二進制樹算法在閱讀器問詢次數(shù)、系統(tǒng)搜索次數(shù)、閱讀器與標(biāo)簽之間的數(shù)據(jù)通信量等方面具有較大的優(yōu)越性，較大幅度地提高了RFID系統(tǒng)多標(biāo)簽同時識別的性能。

[1]Finkenzeller.RFID handbook fundamentals and applications in contact-less smart cards and identification[M].John Wiley and Sons Ltd,2003.

[2]寧煥生.RFID重大工程與國家物聯(lián)網(wǎng)[M].北京:機械工業(yè)出版社,2011.

[3]謝振華,賴聲禮,陳鵬.RFID技術(shù)和防碰撞算法[J].計算機工程與應(yīng)用,2007(6):223-230.

[4]單劍鋒,陳明,謝建兵.基于ALOHA算法的RFID防碰撞技術(shù)研究[J].南京郵電大學(xué)學(xué)報,2013(1):56-61.

[5]丁治國,郭立,朱學(xué)永,等.基于二叉樹分解的自適應(yīng)防碰撞算法[J].電子與信息學(xué)報,2009(6):1395-1399.

[6]Yinghua Cui,Yuping Zhao.Performance evaluation of a multi-branch tree algorithm in RFID[J].Communications, IEEE Transaction on Journals & Magazines,2010(58):1356-1364.

Research of RFID Adaptive Multi-tree Anti-collision Algorithm Based on the Internet of Things

ZHANG Qin

(Fuzhou Polytechnic, Fuzhou Fujian 350108,China)

How to design efficient and practical anti-collision algorithm is the key technology to be solved of RFID system implementation. In this paper, the advantages and disadvantages of the common multi-tag anti-collision algorithm are analyzed firstly. In view of problems in the binary tree anti-collision algorithm more or less: a large amount of communication, abundant total time slot, this paper proposes a adaptive multi-tree anti-collision algorithm. The simulation results show that the system throughput can be maintained at more than 50%, search number and data traffic are also greatly reduced compared with the basic binary anti collision algorithm. The algorithm is suitable for a large number of label identification of the Internet of things.

Internet of Things; RFID；Manchester encoding; anti-collision algorithm

2017-01-14

張 琴(1986- )，女，講師，從事計算機軟件應(yīng)用開發(fā)、信息處理與數(shù)據(jù)挖掘研究。

TP301.6

A

2095-7602(2017)06-0023-05