關(guān)輝

摘 要：射頻識(shí)別（RFID）技術(shù)是一種無接觸的自動(dòng)識(shí)別電子標(biāo)簽的技術(shù)，是物聯(lián)網(wǎng)感知層中的一種重要技術(shù)。隨著該技術(shù)在諸多領(lǐng)域的廣泛應(yīng)用，解決多標(biāo)簽識(shí)別問題的防碰撞算法顯得越來越重要。目前的RFID防碰撞算法主要分為兩大類：基于ALOHA的算法和基于樹的算法。針對(duì)傳統(tǒng)基于樹的防碰撞算法識(shí)別時(shí)間較長(zhǎng)、效率不高的問題，提出了一種基于四叉樹的改進(jìn)型RFID防碰撞算法，通過對(duì)電子標(biāo)簽的原始ID碼進(jìn)行分組后重新進(jìn)行編碼，消除了識(shí)別過程中的空閑時(shí)隙。經(jīng)數(shù)學(xué)分析和仿真實(shí)驗(yàn)表明，在同等數(shù)量的標(biāo)簽情況下，該算法的識(shí)別時(shí)間較其它傳統(tǒng)基于樹的算法平均降低40%左右，識(shí)別性能得到了較大的提升。

關(guān)鍵詞：射頻識(shí)別；防碰撞；四叉樹；標(biāo)簽識(shí)別

中圖分類號(hào)：TP393 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：2095-1302（2014）08-0024-04

0 引 言

RFID（Radio Frequency Identification）即射頻識(shí)別技術(shù)的英文縮寫，它利用射頻信號(hào)通過空間耦合（交變磁場(chǎng)或電磁場(chǎng)）在閱讀器和電子標(biāo)簽之間實(shí)現(xiàn)無接觸的信息傳遞，并通過所傳遞的信息達(dá)到自動(dòng)識(shí)別的目的[1]。作為物聯(lián)網(wǎng)感知層中的一種主要技術(shù)，RFID目前已經(jīng)在物流、倉(cāng)儲(chǔ)、交通等諸多領(lǐng)域廣泛使用。但是，在一個(gè)閱讀器的識(shí)別范圍內(nèi)如果有多個(gè)標(biāo)簽存在，當(dāng)這些標(biāo)簽同時(shí)向閱讀器傳遞信息時(shí)，閱讀器就會(huì)檢測(cè)到?jīng)_突，這稱之為“碰撞”，從而造成標(biāo)簽識(shí)別失敗[2]。為了解決這個(gè)問題，各種防碰撞算法被提了出來。

目前的RFID防碰撞算法主要分為兩大類：基于ALOHA的算法[3]和基于樹的算法[4]?；贏LOHA的算法運(yùn)用了時(shí)分多址的思想，標(biāo)簽隨機(jī)選擇一個(gè)時(shí)隙發(fā)送信息，若發(fā)生碰撞則隨機(jī)延遲一段時(shí)間再重發(fā)。這種算法由于對(duì)標(biāo)簽讀取時(shí)間的不確定性，容易出現(xiàn)標(biāo)簽長(zhǎng)時(shí)間不被閱讀器讀取的“餓死”現(xiàn)象[5]?；跇涞乃惴ú捎幂喸兊乃枷?，按照二進(jìn)制組合規(guī)律，運(yùn)用樹的遍歷算法對(duì)所有可能性進(jìn)行搜索，直到識(shí)別出正確的數(shù)據(jù)。這種算法的標(biāo)簽讀取時(shí)間是確定的，可以有效解決電子標(biāo)簽的“餓死”現(xiàn)象。但由于它對(duì)每種可能性都進(jìn)行遍歷，會(huì)導(dǎo)致讀取標(biāo)簽的時(shí)延較長(zhǎng)，標(biāo)簽數(shù)量較多時(shí)，算法的效率會(huì)明顯降低[6]。

在基于樹的防碰撞算法的基礎(chǔ)上，本文提出了一種基于四叉樹的改進(jìn)型RFID防碰撞算法，通過改進(jìn)四叉樹的結(jié)構(gòu)，降低標(biāo)簽識(shí)別時(shí)間，提高了識(shí)別效率。

1 基于樹的防碰撞算法

樹是一種重要的非線性數(shù)據(jù)結(jié)構(gòu)，它主要由結(jié)點(diǎn)和分枝組成。結(jié)點(diǎn)即樹中的每一個(gè)數(shù)據(jù)元素，除根結(jié)點(diǎn)和葉子結(jié)點(diǎn)外每個(gè)結(jié)點(diǎn)都有父結(jié)點(diǎn)和子結(jié)點(diǎn)；分枝即指向其子結(jié)點(diǎn)的分支[7]?；跇涞姆琅鲎菜惴ㄐ枰獙?duì)標(biāo)簽的ID按照一定的長(zhǎng)度進(jìn)行分組，當(dāng)分組長(zhǎng)度為1時(shí)，即為二叉樹算法；當(dāng)分組長(zhǎng)度為2時(shí)，即為四叉樹算法；當(dāng)分組長(zhǎng)度為3時(shí)，即為八叉樹算法……依此類推。在RFID系統(tǒng)中應(yīng)用最廣泛的是二叉樹算法，它的基本原理是：閱讀器給標(biāo)簽發(fā)送一個(gè)比特的查詢碼Q（0或1，相當(dāng)于形成兩個(gè)子樹，先查詢0子樹，再查詢1子樹），在閱讀器響應(yīng)范圍內(nèi)的每一個(gè)標(biāo)簽判斷自己的ID是否以Q開頭，若是則將自己的ID傳送給閱讀器。這時(shí)，有可能會(huì)出現(xiàn)三種情況：識(shí)別（僅有一個(gè)標(biāo)簽以Q開頭）、碰撞（有兩個(gè)或兩個(gè)以上標(biāo)簽以Q開頭）、空閑（無標(biāo)簽以Q開頭）[8]。若發(fā)生碰撞，則在前一個(gè)查詢碼后分別加上0和1，形成兩個(gè)新查詢碼（相當(dāng)于分裂成左右兩個(gè)子樹）。先發(fā)送末尾加上0的新查詢碼給標(biāo)簽，查詢左子樹；再發(fā)送末尾加上1的新查詢碼給標(biāo)簽，查詢右子樹。在查詢過程中如果再次發(fā)生了碰撞，則重復(fù)上述操作，直到成功識(shí)別出全部標(biāo)簽為止[9]。假設(shè)有三個(gè)標(biāo)簽，其ID分別為：0101、0110、1010，若采用二叉樹防碰撞算法，其識(shí)別過程如圖1所示。

由以上識(shí)別過程可以看出，在基于樹的防碰撞算法中，整個(gè)樹的結(jié)點(diǎn)可分為四種：初始結(jié)點(diǎn)、識(shí)別結(jié)點(diǎn)、碰撞結(jié)點(diǎn)和空閑結(jié)點(diǎn)。初始結(jié)點(diǎn)有且僅有一個(gè)，識(shí)別結(jié)點(diǎn)的數(shù)量與標(biāo)簽數(shù)量相等，這兩種結(jié)點(diǎn)的數(shù)量是確定的。因此，要提高識(shí)別效率，關(guān)鍵是想辦法減少碰撞結(jié)點(diǎn)和空閑結(jié)點(diǎn)的數(shù)量。

在基于樹的RFID防碰撞算法中除了應(yīng)用二叉樹外，多叉樹在很多場(chǎng)合也有實(shí)際應(yīng)用，如四叉樹。四叉樹中標(biāo)簽分組長(zhǎng)度為2，結(jié)點(diǎn)編碼共有四種組合：00、01、10、11。同樣是如前所述的三個(gè)標(biāo)簽：0101、0110、1010，采用四叉樹算法的識(shí)別過程如圖2所示。

將四叉樹和二叉樹識(shí)別過程作對(duì)比可以發(fā)現(xiàn)，四叉樹的碰撞結(jié)點(diǎn)較少，空閑結(jié)點(diǎn)較多。若能通過對(duì)四叉樹的結(jié)構(gòu)進(jìn)行改進(jìn)，減少甚至去除空閑結(jié)點(diǎn)，將大大提高識(shí)別效率。

2 基于四叉樹的改進(jìn)型防碰撞算法

基于四叉樹的改進(jìn)型防碰撞算法主要通過引入分組重編碼的機(jī)制，改進(jìn)生成樹的結(jié)構(gòu)，去除空閑時(shí)隙，縮短識(shí)別時(shí)間，從而提高識(shí)別效率[10]。整個(gè)算法主要由兩部分組成：分組重編碼和標(biāo)簽識(shí)別。

2.1 分組重編碼

該算法首先要對(duì)標(biāo)簽的原始ID碼進(jìn)行分組，將原始ID碼從最高位到最低位每?jī)晌环殖梢唤M，最后一組不足兩位則補(bǔ)0。這樣，每一組的兩位ID就有四種組合：00、01、10、11，對(duì)應(yīng)于四叉樹的四個(gè)分支。

下來再對(duì)這四種組合的兩位分組ID碼重新進(jìn)行編碼，用新的編碼來替換兩位分組ID碼[11]，重編碼的規(guī)則如表1所列。

從表1可以看出，用來替換兩位分組ID碼的新編碼最大長(zhǎng)度4位，最小長(zhǎng)度1位，平均長(zhǎng)度2.5位，比原分組ID碼的2位略有增加。新編碼有一個(gè)顯著的特點(diǎn)：最高位為1，低位全部為0。之所以采用這種編碼規(guī)則，目的是使閱讀器在識(shí)別過程中有更好的區(qū)分度，利用碰撞發(fā)生的位置就可以直接判斷出參與碰撞的標(biāo)簽的替換編碼。

以上的分組重編碼操作均由標(biāo)簽完成，因此要求標(biāo)簽要具有存儲(chǔ)和生成替換編碼的能力。

2.2 標(biāo)簽識(shí)別

在識(shí)別過程中，電子標(biāo)簽可能處于以下三種狀態(tài)[12]：

（1） 激活狀態(tài)

當(dāng)閱讀器對(duì)響應(yīng)范圍內(nèi)的標(biāo)簽發(fā)送初始化命令時(shí)，所有標(biāo)簽進(jìn)入激活狀態(tài)；另外，當(dāng)標(biāo)簽的編碼與閱讀器發(fā)送的請(qǐng)求編碼一致時(shí)，該標(biāo)簽也將處于激活狀態(tài)。

（2） 安靜狀態(tài)

當(dāng)標(biāo)簽的編碼與閱讀器當(dāng)前發(fā)出的請(qǐng)求編碼不同時(shí)，該標(biāo)簽將暫時(shí)退出通信連接，進(jìn)入到安靜狀態(tài)，等待下一次被激活。

（3） 休眠狀態(tài)

當(dāng)一個(gè)標(biāo)簽已經(jīng)被識(shí)別出來，它將進(jìn)入到休眠狀態(tài)，之后的通信過程不再進(jìn)行任何響應(yīng)，一直到整個(gè)識(shí)別過程全部結(jié)束。

具體識(shí)別過程如下：

（1） 閱讀器向進(jìn)入自己響應(yīng)范圍內(nèi)的所有標(biāo)簽發(fā)送初始化命令，并令分組序號(hào)n=0。

（2） 處于激活狀態(tài)的標(biāo)簽進(jìn)行響應(yīng)。若閱讀器檢測(cè)到未發(fā)生碰撞，則成功識(shí)別，轉(zhuǎn)（4）；若發(fā)生碰撞，則標(biāo)簽令分組序號(hào)n=n+1，并發(fā)送其第n組替換編碼。

（3） 閱讀器接收到標(biāo)簽發(fā)來的替換編碼，通過識(shí)別替換編碼中碰撞發(fā)生的位置和數(shù)量，判斷出響應(yīng)范圍內(nèi)標(biāo)簽的替換編碼的具體值，并將其和n值一起壓入堆棧s中。

（4） 閱讀器判斷堆棧s是否為空，不為空則轉(zhuǎn)（5），為空則轉(zhuǎn)（6）。

（5） 堆棧s頂部編碼和n值出棧，閱讀器發(fā)送棧頂編碼來請(qǐng)求標(biāo)簽，轉(zhuǎn)（2）。

（6） 所有標(biāo)簽識(shí)別完畢。

識(shí)別過程中指定四種替換編碼的壓棧順序?yàn)椋? 000、100、10、1。

2.3 算法舉例

假設(shè)在閱讀器響應(yīng)范圍內(nèi)有6個(gè)待識(shí)別的電子標(biāo)簽，其原始ID分別為：標(biāo)簽a：01101101、標(biāo)簽b：11000110、標(biāo)簽c：10011100、標(biāo)簽d：11001011、標(biāo)簽e：01001011、標(biāo)簽f：10101101，則各標(biāo)簽的原始ID經(jīng)過分組重編碼后對(duì)應(yīng)的替換編碼如表2所列。

3 性能分析與仿真

閱讀器完成響應(yīng)范圍內(nèi)所有電子標(biāo)簽的識(shí)別工作所花費(fèi)的時(shí)間一般用時(shí)隙數(shù)作為單位，它是衡量防碰撞算法性能的重要標(biāo)準(zhǔn)之一，時(shí)隙數(shù)越少的算法性能越優(yōu)越。因此，接下來用數(shù)學(xué)分析的方法推導(dǎo)出基于四叉樹的改進(jìn)型防碰撞算法的總時(shí)隙數(shù)值，并與二叉樹、四叉樹算法一起進(jìn)行比較和仿真。

3.1 數(shù)學(xué)分析

設(shè)m為待識(shí)別的標(biāo)簽數(shù)，為總時(shí)隙數(shù)期望值，為碰撞時(shí)隙數(shù)期望值，為空閑時(shí)隙數(shù)期望值，為識(shí)別時(shí)隙數(shù)期望值。在基于B叉樹的防碰撞算法中，

3.2 算法仿真

接下來對(duì)上述的數(shù)學(xué)分析用Matlab進(jìn)行模擬仿真。

4 結(jié) 語

基于四叉樹的改進(jìn)型RFID防碰撞算法通過對(duì)標(biāo)簽的原始ID碼采取分組重編碼的手段，優(yōu)化了生成樹的結(jié)構(gòu)，消除了空閑時(shí)隙，大大提高了標(biāo)簽的識(shí)別效率。通過數(shù)學(xué)分析和算法仿真，進(jìn)一步證明了在同等數(shù)目的標(biāo)簽情況下，該算法的識(shí)別時(shí)間要明顯低于傳統(tǒng)的二叉樹和四叉樹算法，并且隨著標(biāo)簽數(shù)目的增多，這種優(yōu)勢(shì)就更加明顯。因此，該算法對(duì)于解決標(biāo)簽密集環(huán)境下的RFID防碰撞問題具有一定的實(shí)際意義。

參 考 文 獻(xiàn)

[1]劉云浩. 物聯(lián)網(wǎng)導(dǎo)論[M]. 北京：科學(xué)出版社， 2011，3：23-24.

[2] K.Dheeraj， K.W.Chin， and R.Raad. A survey and tutorial of RFID anti-collision protocols[C]. IEEE Transactions on Wireless Communication， 2010（12）：105-117.

[3] Finkenzeller K. RFID handbook， fundamentals and applications in contactless smart cards and identification[M]. New York： Wiley， 2003.

[4] Myung J.， Lee W.，Srivastava J. Adaptive binary splitting for efficient RFID tag anti-collision[C]. IEEE Communications Letters， 2006，10（3）：144-146.

[5] Jihoon Myung， Wonjun Lee. Adaptive binary splitting： a RFID tag collision arbitration protocol for tag identification[J]. Mobile Networks and Applications， 2006，11（2）：711-722

[6]蘇暉. 射頻識(shí)別防碰撞算法研究[D]. 重慶：重慶大學(xué)， 2012.

[7]嚴(yán)蔚敏，吳偉民. 數(shù)據(jù)結(jié)構(gòu)[M]. 北京：清華大學(xué)出版社， 2011.

[8] Jae-Dong Shin，Sang-Soo Yeo，etc. Hybrid tag anti-collision algorithms in RFID systems[C]. ICCS 2007 Part IV， 2007：693-700.

[9]吳博，周銅，王棟. RFID防碰撞算法分析與研究[J]. 微電子學(xué)與計(jì)算機(jī)， 2009，26（8）：237-239.

[10]張學(xué)軍，王緒海，蔡文琦. 基于分組碼的改進(jìn)型防碰撞算法研究[J]. 計(jì)算機(jī)應(yīng)用研究， 2012，29（11）：4266-4267.

[11] Kuo-Hui Yeh， N.W.Lo. An efficient tree-based tag identification protocol for RFID systems[C]. 22nd International Conference on Advanced Information Networking and Applications， WAINA， 2008，220：966-970.

[12]田蕓，陳恭亮，李建華. Bi-slotted binary tree algorithm with stack for radio frequency identification tag anti-collision[J]. Journal of Shanghai Jiaotong University（Science）， 2013，18（2）：173-179.

[13] Hush D R and Wood C. Analysis of tree algorithms for RFID arbitration[C]. Proceedings of IEEE Symposium on Information Theory， Cambridge， MA， USA. 1998：107-116.

（1） 激活狀態(tài)

當(dāng)閱讀器對(duì)響應(yīng)范圍內(nèi)的標(biāo)簽發(fā)送初始化命令時(shí)，所有標(biāo)簽進(jìn)入激活狀態(tài)；另外，當(dāng)標(biāo)簽的編碼與閱讀器發(fā)送的請(qǐng)求編碼一致時(shí)，該標(biāo)簽也將處于激活狀態(tài)。

（2） 安靜狀態(tài)

當(dāng)標(biāo)簽的編碼與閱讀器當(dāng)前發(fā)出的請(qǐng)求編碼不同時(shí)，該標(biāo)簽將暫時(shí)退出通信連接，進(jìn)入到安靜狀態(tài)，等待下一次被激活。

（3） 休眠狀態(tài)

當(dāng)一個(gè)標(biāo)簽已經(jīng)被識(shí)別出來，它將進(jìn)入到休眠狀態(tài)，之后的通信過程不再進(jìn)行任何響應(yīng)，一直到整個(gè)識(shí)別過程全部結(jié)束。

具體識(shí)別過程如下：

（1） 閱讀器向進(jìn)入自己響應(yīng)范圍內(nèi)的所有標(biāo)簽發(fā)送初始化命令，并令分組序號(hào)n=0。

（2） 處于激活狀態(tài)的標(biāo)簽進(jìn)行響應(yīng)。若閱讀器檢測(cè)到未發(fā)生碰撞，則成功識(shí)別，轉(zhuǎn)（4）；若發(fā)生碰撞，則標(biāo)簽令分組序號(hào)n=n+1，并發(fā)送其第n組替換編碼。

（3） 閱讀器接收到標(biāo)簽發(fā)來的替換編碼，通過識(shí)別替換編碼中碰撞發(fā)生的位置和數(shù)量，判斷出響應(yīng)范圍內(nèi)標(biāo)簽的替換編碼的具體值，并將其和n值一起壓入堆棧s中。

（4） 閱讀器判斷堆棧s是否為空，不為空則轉(zhuǎn)（5），為空則轉(zhuǎn)（6）。

（5） 堆棧s頂部編碼和n值出棧，閱讀器發(fā)送棧頂編碼來請(qǐng)求標(biāo)簽，轉(zhuǎn)（2）。

（6） 所有標(biāo)簽識(shí)別完畢。

識(shí)別過程中指定四種替換編碼的壓棧順序?yàn)椋? 000、100、10、1。

2.3 算法舉例

假設(shè)在閱讀器響應(yīng)范圍內(nèi)有6個(gè)待識(shí)別的電子標(biāo)簽，其原始ID分別為：標(biāo)簽a：01101101、標(biāo)簽b：11000110、標(biāo)簽c：10011100、標(biāo)簽d：11001011、標(biāo)簽e：01001011、標(biāo)簽f：10101101，則各標(biāo)簽的原始ID經(jīng)過分組重編碼后對(duì)應(yīng)的替換編碼如表2所列。

3 性能分析與仿真

閱讀器完成響應(yīng)范圍內(nèi)所有電子標(biāo)簽的識(shí)別工作所花費(fèi)的時(shí)間一般用時(shí)隙數(shù)作為單位，它是衡量防碰撞算法性能的重要標(biāo)準(zhǔn)之一，時(shí)隙數(shù)越少的算法性能越優(yōu)越。因此，接下來用數(shù)學(xué)分析的方法推導(dǎo)出基于四叉樹的改進(jìn)型防碰撞算法的總時(shí)隙數(shù)值，并與二叉樹、四叉樹算法一起進(jìn)行比較和仿真。

3.1 數(shù)學(xué)分析

設(shè)m為待識(shí)別的標(biāo)簽數(shù)，為總時(shí)隙數(shù)期望值，為碰撞時(shí)隙數(shù)期望值，為空閑時(shí)隙數(shù)期望值，為識(shí)別時(shí)隙數(shù)期望值。在基于B叉樹的防碰撞算法中，

3.2 算法仿真

接下來對(duì)上述的數(shù)學(xué)分析用Matlab進(jìn)行模擬仿真。

4 結(jié) 語

基于四叉樹的改進(jìn)型RFID防碰撞算法通過對(duì)標(biāo)簽的原始ID碼采取分組重編碼的手段，優(yōu)化了生成樹的結(jié)構(gòu)，消除了空閑時(shí)隙，大大提高了標(biāo)簽的識(shí)別效率。通過數(shù)學(xué)分析和算法仿真，進(jìn)一步證明了在同等數(shù)目的標(biāo)簽情況下，該算法的識(shí)別時(shí)間要明顯低于傳統(tǒng)的二叉樹和四叉樹算法，并且隨著標(biāo)簽數(shù)目的增多，這種優(yōu)勢(shì)就更加明顯。因此，該算法對(duì)于解決標(biāo)簽密集環(huán)境下的RFID防碰撞問題具有一定的實(shí)際意義。

參 考 文 獻(xiàn)

[1]劉云浩. 物聯(lián)網(wǎng)導(dǎo)論[M]. 北京：科學(xué)出版社， 2011，3：23-24.

[2] K.Dheeraj， K.W.Chin， and R.Raad. A survey and tutorial of RFID anti-collision protocols[C]. IEEE Transactions on Wireless Communication， 2010（12）：105-117.

[3] Finkenzeller K. RFID handbook， fundamentals and applications in contactless smart cards and identification[M]. New York： Wiley， 2003.

[4] Myung J.， Lee W.，Srivastava J. Adaptive binary splitting for efficient RFID tag anti-collision[C]. IEEE Communications Letters， 2006，10（3）：144-146.

[5] Jihoon Myung， Wonjun Lee. Adaptive binary splitting： a RFID tag collision arbitration protocol for tag identification[J]. Mobile Networks and Applications， 2006，11（2）：711-722

[6]蘇暉. 射頻識(shí)別防碰撞算法研究[D]. 重慶：重慶大學(xué)， 2012.

[7]嚴(yán)蔚敏，吳偉民. 數(shù)據(jù)結(jié)構(gòu)[M]. 北京：清華大學(xué)出版社， 2011.

[8] Jae-Dong Shin，Sang-Soo Yeo，etc. Hybrid tag anti-collision algorithms in RFID systems[C]. ICCS 2007 Part IV， 2007：693-700.

[9]吳博，周銅，王棟. RFID防碰撞算法分析與研究[J]. 微電子學(xué)與計(jì)算機(jī)， 2009，26（8）：237-239.

[10]張學(xué)軍，王緒海，蔡文琦. 基于分組碼的改進(jìn)型防碰撞算法研究[J]. 計(jì)算機(jī)應(yīng)用研究， 2012，29（11）：4266-4267.

[11] Kuo-Hui Yeh， N.W.Lo. An efficient tree-based tag identification protocol for RFID systems[C]. 22nd International Conference on Advanced Information Networking and Applications， WAINA， 2008，220：966-970.

[12]田蕓，陳恭亮，李建華. Bi-slotted binary tree algorithm with stack for radio frequency identification tag anti-collision[J]. Journal of Shanghai Jiaotong University（Science）， 2013，18（2）：173-179.

[13] Hush D R and Wood C. Analysis of tree algorithms for RFID arbitration[C]. Proceedings of IEEE Symposium on Information Theory， Cambridge， MA， USA. 1998：107-116.

（1） 激活狀態(tài)

當(dāng)閱讀器對(duì)響應(yīng)范圍內(nèi)的標(biāo)簽發(fā)送初始化命令時(shí)，所有標(biāo)簽進(jìn)入激活狀態(tài)；另外，當(dāng)標(biāo)簽的編碼與閱讀器發(fā)送的請(qǐng)求編碼一致時(shí)，該標(biāo)簽也將處于激活狀態(tài)。

（2） 安靜狀態(tài)

當(dāng)標(biāo)簽的編碼與閱讀器當(dāng)前發(fā)出的請(qǐng)求編碼不同時(shí)，該標(biāo)簽將暫時(shí)退出通信連接，進(jìn)入到安靜狀態(tài)，等待下一次被激活。

（3） 休眠狀態(tài)

當(dāng)一個(gè)標(biāo)簽已經(jīng)被識(shí)別出來，它將進(jìn)入到休眠狀態(tài)，之后的通信過程不再進(jìn)行任何響應(yīng)，一直到整個(gè)識(shí)別過程全部結(jié)束。

具體識(shí)別過程如下：

（1） 閱讀器向進(jìn)入自己響應(yīng)范圍內(nèi)的所有標(biāo)簽發(fā)送初始化命令，并令分組序號(hào)n=0。

（2） 處于激活狀態(tài)的標(biāo)簽進(jìn)行響應(yīng)。若閱讀器檢測(cè)到未發(fā)生碰撞，則成功識(shí)別，轉(zhuǎn)（4）；若發(fā)生碰撞，則標(biāo)簽令分組序號(hào)n=n+1，并發(fā)送其第n組替換編碼。

（3） 閱讀器接收到標(biāo)簽發(fā)來的替換編碼，通過識(shí)別替換編碼中碰撞發(fā)生的位置和數(shù)量，判斷出響應(yīng)范圍內(nèi)標(biāo)簽的替換編碼的具體值，并將其和n值一起壓入堆棧s中。

（4） 閱讀器判斷堆棧s是否為空，不為空則轉(zhuǎn)（5），為空則轉(zhuǎn)（6）。

（5） 堆棧s頂部編碼和n值出棧，閱讀器發(fā)送棧頂編碼來請(qǐng)求標(biāo)簽，轉(zhuǎn)（2）。

（6） 所有標(biāo)簽識(shí)別完畢。

識(shí)別過程中指定四種替換編碼的壓棧順序?yàn)椋? 000、100、10、1。

2.3 算法舉例

假設(shè)在閱讀器響應(yīng)范圍內(nèi)有6個(gè)待識(shí)別的電子標(biāo)簽，其原始ID分別為：標(biāo)簽a：01101101、標(biāo)簽b：11000110、標(biāo)簽c：10011100、標(biāo)簽d：11001011、標(biāo)簽e：01001011、標(biāo)簽f：10101101，則各標(biāo)簽的原始ID經(jīng)過分組重編碼后對(duì)應(yīng)的替換編碼如表2所列。

3 性能分析與仿真

閱讀器完成響應(yīng)范圍內(nèi)所有電子標(biāo)簽的識(shí)別工作所花費(fèi)的時(shí)間一般用時(shí)隙數(shù)作為單位，它是衡量防碰撞算法性能的重要標(biāo)準(zhǔn)之一，時(shí)隙數(shù)越少的算法性能越優(yōu)越。因此，接下來用數(shù)學(xué)分析的方法推導(dǎo)出基于四叉樹的改進(jìn)型防碰撞算法的總時(shí)隙數(shù)值，并與二叉樹、四叉樹算法一起進(jìn)行比較和仿真。

3.1 數(shù)學(xué)分析

設(shè)m為待識(shí)別的標(biāo)簽數(shù)，為總時(shí)隙數(shù)期望值，為碰撞時(shí)隙數(shù)期望值，為空閑時(shí)隙數(shù)期望值，為識(shí)別時(shí)隙數(shù)期望值。在基于B叉樹的防碰撞算法中，

3.2 算法仿真

接下來對(duì)上述的數(shù)學(xué)分析用Matlab進(jìn)行模擬仿真。

4 結(jié) 語

基于四叉樹的改進(jìn)型RFID防碰撞算法通過對(duì)標(biāo)簽的原始ID碼采取分組重編碼的手段，優(yōu)化了生成樹的結(jié)構(gòu)，消除了空閑時(shí)隙，大大提高了標(biāo)簽的識(shí)別效率。通過數(shù)學(xué)分析和算法仿真，進(jìn)一步證明了在同等數(shù)目的標(biāo)簽情況下，該算法的識(shí)別時(shí)間要明顯低于傳統(tǒng)的二叉樹和四叉樹算法，并且隨著標(biāo)簽數(shù)目的增多，這種優(yōu)勢(shì)就更加明顯。因此，該算法對(duì)于解決標(biāo)簽密集環(huán)境下的RFID防碰撞問題具有一定的實(shí)際意義。

參 考 文 獻(xiàn)

[1]劉云浩. 物聯(lián)網(wǎng)導(dǎo)論[M]. 北京：科學(xué)出版社， 2011，3：23-24.

[2] K.Dheeraj， K.W.Chin， and R.Raad. A survey and tutorial of RFID anti-collision protocols[C]. IEEE Transactions on Wireless Communication， 2010（12）：105-117.

[3] Finkenzeller K. RFID handbook， fundamentals and applications in contactless smart cards and identification[M]. New York： Wiley， 2003.

[4] Myung J.， Lee W.，Srivastava J. Adaptive binary splitting for efficient RFID tag anti-collision[C]. IEEE Communications Letters， 2006，10（3）：144-146.

[5] Jihoon Myung， Wonjun Lee. Adaptive binary splitting： a RFID tag collision arbitration protocol for tag identification[J]. Mobile Networks and Applications， 2006，11（2）：711-722

[6]蘇暉. 射頻識(shí)別防碰撞算法研究[D]. 重慶：重慶大學(xué)， 2012.

[7]嚴(yán)蔚敏，吳偉民. 數(shù)據(jù)結(jié)構(gòu)[M]. 北京：清華大學(xué)出版社， 2011.

[8] Jae-Dong Shin，Sang-Soo Yeo，etc. Hybrid tag anti-collision algorithms in RFID systems[C]. ICCS 2007 Part IV， 2007：693-700.

[9]吳博，周銅，王棟. RFID防碰撞算法分析與研究[J]. 微電子學(xué)與計(jì)算機(jī)， 2009，26（8）：237-239.

[10]張學(xué)軍，王緒海，蔡文琦. 基于分組碼的改進(jìn)型防碰撞算法研究[J]. 計(jì)算機(jī)應(yīng)用研究， 2012，29（11）：4266-4267.

[11] Kuo-Hui Yeh， N.W.Lo. An efficient tree-based tag identification protocol for RFID systems[C]. 22nd International Conference on Advanced Information Networking and Applications， WAINA， 2008，220：966-970.

[12]田蕓，陳恭亮，李建華. Bi-slotted binary tree algorithm with stack for radio frequency identification tag anti-collision[J]. Journal of Shanghai Jiaotong University（Science）， 2013，18（2）：173-179.

[13] Hush D R and Wood C. Analysis of tree algorithms for RFID arbitration[C]. Proceedings of IEEE Symposium on Information Theory， Cambridge， MA， USA. 1998：107-116.