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

關(guān)輝

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

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

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

0 引 言

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

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

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

1 基于樹的防碰撞算法

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

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

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

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

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

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

2.1 分組重編碼

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

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

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

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

2.2 標(biāo)簽識別

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

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

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

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

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

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

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

具體識別過程如下：

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

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

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

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

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

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

識別過程中指定四種替換編碼的壓棧順序為：1 000、100、10、1。

2.3 算法舉例

假設(shè)在閱讀器響應(yīng)范圍內(nèi)有6個待識別的電子標(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)過分組重編碼后對應(yīng)的替換編碼如表2所列。

3 性能分析與仿真

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

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

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

3.2 算法仿真

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

4 結(jié) 語

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

參 考 文 獻(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]蘇暉. 射頻識別防碰撞算法研究[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ī)， 2009，26（8）：237-239.

[10]張學(xué)軍，王緒海，蔡文琦. 基于分組碼的改進(jìn)型防碰撞算法研究[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)閱讀器對響應(yīng)范圍內(nèi)的標(biāo)簽發(fā)送初始化命令時，所有標(biāo)簽進(jìn)入激活狀態(tài)；另外，當(dāng)標(biāo)簽的編碼與閱讀器發(fā)送的請求編碼一致時，該標(biāo)簽也將處于激活狀態(tài)。

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

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

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

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

具體識別過程如下：

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

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

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

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

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

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

識別過程中指定四種替換編碼的壓棧順序為：1 000、100、10、1。

2.3 算法舉例

假設(shè)在閱讀器響應(yīng)范圍內(nèi)有6個待識別的電子標(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)過分組重編碼后對應(yīng)的替換編碼如表2所列。

3 性能分析與仿真

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

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

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

3.2 算法仿真

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

4 結(jié) 語

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

參 考 文 獻(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]蘇暉. 射頻識別防碰撞算法研究[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ī)， 2009，26（8）：237-239.

[10]張學(xué)軍，王緒海，蔡文琦. 基于分組碼的改進(jìn)型防碰撞算法研究[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)閱讀器對響應(yīng)范圍內(nèi)的標(biāo)簽發(fā)送初始化命令時，所有標(biāo)簽進(jìn)入激活狀態(tài)；另外，當(dāng)標(biāo)簽的編碼與閱讀器發(fā)送的請求編碼一致時，該標(biāo)簽也將處于激活狀態(tài)。

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

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

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

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

具體識別過程如下：

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

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

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

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

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

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

識別過程中指定四種替換編碼的壓棧順序為：1 000、100、10、1。

2.3 算法舉例

假設(shè)在閱讀器響應(yīng)范圍內(nèi)有6個待識別的電子標(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)過分組重編碼后對應(yīng)的替換編碼如表2所列。

3 性能分析與仿真

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

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

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

3.2 算法仿真

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

4 結(jié) 語

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

參 考 文 獻(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]蘇暉. 射頻識別防碰撞算法研究[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ī)， 2009，26（8）：237-239.

[10]張學(xué)軍，王緒海，蔡文琦. 基于分組碼的改進(jìn)型防碰撞算法研究[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.