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

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

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

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

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

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

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

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

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

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

1 算法約定

1.1 算法通信方式

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

圖1 Manchester編碼碰撞位識(shí)別原理示意圖

1.2 算法命令

1.2.1 查詢命令

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

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

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

1.2.2 標(biāo)簽休眠

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

1.2.3 選擇命令

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

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

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

2 算法原理及流程

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

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

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

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

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

CALL(NULL);

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

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

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

Else

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

{記錄HP,LP,;

While(statue<=4)

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

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

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

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àn)證本文中自適應(yīng)多叉樹(shù)防碰撞算法的有效性，下面利用Matlab軟件對(duì)該算法的查詢次數(shù)和吞吐量進(jìn)行仿真實(shí)驗(yàn)，比較的算法為基本二進(jìn)制樹(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í)，兩種算法搜索次數(shù)差別不太大，隨著標(biāo)簽數(shù)目的增多，空閑時(shí)隙情況逐漸減少，本文中算法的優(yōu)勢(shì)越來(lái)越明顯?；镜亩M(jìn)制樹(shù)防碰撞算法搜索次數(shù)隨標(biāo)簽數(shù)目增加接近線性增長(zhǎng)，而本文中算法當(dāng)標(biāo)簽數(shù)目增加到200之后搜索次數(shù)基本上處于穩(wěn)定狀態(tài)，原因在于自適應(yīng)多叉樹(shù)算法可以降低查詢樹(shù)體復(fù)雜度，簡(jiǎn)化搜索流程，進(jìn)而使查詢次數(shù)大大減少。

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

圖4 兩種算法吞吐量對(duì)比圖

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

4 結(jié)語(yǔ)

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

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

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

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

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

[5]丁治國(guó),郭立,朱學(xué)永,等.基于二叉樹(shù)分解的自適應(yīng)防碰撞算法[J].電子與信息學(xué)報(bào),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- )，女，講師，從事計(jì)算機(jī)軟件應(yīng)用開(kāi)發(fā)、信息處理與數(shù)據(jù)挖掘研究。

TP301.6

A

2095-7602(2017)06-0023-05