王佩瑋

摘 要：在無(wú)線射頻識(shí)別系統(tǒng)中，讀寫(xiě)器通過(guò)廣播方式向標(biāo)簽傳輸指令。而標(biāo)簽通過(guò)多路存取的方式返回自身標(biāo)識(shí)數(shù)據(jù)給讀寫(xiě)器。具體防碰撞算法有很多，為了合理選擇最優(yōu)的防碰撞算法，文中將對(duì)基本二進(jìn)制樹(shù)防碰撞算法以及后退二進(jìn)制樹(shù)防碰撞算法進(jìn)行比較分析。得出了后退二進(jìn)制樹(shù)防碰撞算法優(yōu)于基本二進(jìn)制樹(shù)防碰撞算法的結(jié)論。

關(guān)鍵詞：無(wú)線射頻識(shí)別；讀寫(xiě)器；基本二進(jìn)制樹(shù)防碰撞算法；后退二進(jìn)制樹(shù)防碰撞算法

中圖分類(lèi)號(hào)：TP391 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：2095-1302（2017）04-00-04

0 引 言

當(dāng)無(wú)線射頻識(shí)別系統(tǒng)工作時(shí)，若有多個(gè)電子標(biāo)簽進(jìn)入讀寫(xiě)器的廣播范圍，并同時(shí)發(fā)送信號(hào)給讀寫(xiě)器，數(shù)據(jù)碰撞就無(wú)法避免。碰撞會(huì)導(dǎo)致數(shù)據(jù)發(fā)送失敗，因此必須采取合適的方法以防止碰撞產(chǎn)生。標(biāo)簽防碰撞問(wèn)題的實(shí)質(zhì)是將電子標(biāo)簽依次放入讀寫(xiě)器，區(qū)分出不同的電子標(biāo)簽，確保通信沒(méi)有遺漏。

1 基本二進(jìn)制樹(shù)防碰撞算法

基于樹(shù)的標(biāo)簽防碰撞算法在執(zhí)行過(guò)程中，讀寫(xiě)器不斷更新廣播請(qǐng)求碼，通過(guò)返回結(jié)果將電子標(biāo)簽分成兩個(gè)分支，直至確定每個(gè)電子標(biāo)簽。在判斷尋找過(guò)程中，對(duì)應(yīng)的請(qǐng)求命令參數(shù)會(huì)以節(jié)點(diǎn)的形式進(jìn)行儲(chǔ)存，最后將得到一個(gè)類(lèi)似二叉樹(shù)的數(shù)據(jù)結(jié)構(gòu)，而且由于這些請(qǐng)求命令參數(shù)都用二進(jìn)制形式表示，該算法又被稱(chēng)為“二進(jìn)制樹(shù)”算法。在介紹算法時(shí)，由于在不同協(xié)議下序列號(hào)的數(shù)據(jù)位數(shù)、數(shù)據(jù)格式以及編碼方式都有所不同，本文預(yù)先設(shè)定一個(gè)長(zhǎng)度為8的二進(jìn)制數(shù)。

基本二進(jìn)制樹(shù)防碰撞算法識(shí)別標(biāo)簽時(shí)，讀寫(xiě)器需要多次發(fā)送電子標(biāo)簽的標(biāo)簽序列號(hào)。這時(shí)定義數(shù)據(jù)傳送的順序?yàn)橛傻臀坏礁呶灰来伟l(fā)送。在讀寫(xiě)器或電子標(biāo)簽內(nèi)部比較數(shù)據(jù)時(shí)也遵循這一原則。按照標(biāo)簽序列號(hào)由低位再到高位的順序比較，約定0<1。根據(jù)該順序，判斷數(shù)據(jù)的大小時(shí)從最低位開(kāi)始。即兩個(gè)數(shù)A，B相比，從最右邊的低位開(kāi)始，直到遇到不相等數(shù)位。當(dāng)兩個(gè)數(shù)的所有數(shù)位都相同時(shí)，這兩個(gè)數(shù)就是相等的。

基本二進(jìn)制樹(shù)防碰撞算法的步驟如圖1所示。

因?yàn)槊總€(gè)電子標(biāo)簽的序列號(hào)都不相同，所以當(dāng)多于兩個(gè)的電子標(biāo)簽同時(shí)給讀寫(xiě)器發(fā)送數(shù)據(jù)時(shí)，就不可避免地發(fā)生碰撞。當(dāng)碰撞發(fā)生后，請(qǐng)求碼中相應(yīng)碰撞最高位的數(shù)值將被設(shè)定為0，低于碰撞位的數(shù)值保持不變，高于碰撞位的數(shù)值設(shè)定為1，生成新請(qǐng)求碼。讀寫(xiě)器將更新后的請(qǐng)求碼傳遞給電子標(biāo)簽，電子標(biāo)簽會(huì)繼續(xù)用自己的序列號(hào)與新請(qǐng)求碼進(jìn)行比較。如果序列號(hào)不大于請(qǐng)求碼，則會(huì)返回自身的序列號(hào)給讀寫(xiě)器。

反復(fù)執(zhí)行上述步驟，直到選出序列號(hào)最小的電子標(biāo)簽，讀寫(xiě)器將給該標(biāo)簽發(fā)送指令使其進(jìn)入休眠狀態(tài)。換言之，下次讀寫(xiě)器發(fā)送最大序列號(hào)請(qǐng)求碼時(shí)，該電子標(biāo)簽不會(huì)做出回應(yīng)。

循環(huán)全部步驟，最終將所有電子標(biāo)簽按序列號(hào)由小到大的順序識(shí)別出來(lái)。但需注意的是，循環(huán)全部步驟應(yīng)從算法的最開(kāi)始重復(fù)，即讀寫(xiě)器確定一個(gè)電子標(biāo)簽后，將重新發(fā)送最大序列號(hào)的請(qǐng)求碼。

以四個(gè)標(biāo)簽同時(shí)進(jìn)入讀寫(xiě)器的廣播范圍為例。標(biāo)簽1的序列號(hào)為（11011001），標(biāo)簽2的序列號(hào)為（11101101），標(biāo)簽3的序列號(hào)為（10111001），標(biāo)簽4的序列號(hào)為（10001001）?；径M(jìn)制樹(shù)防碰撞算法識(shí)別標(biāo)簽過(guò)程如圖2所示。

（1）讀寫(xiě)器首先會(huì)發(fā)送一個(gè)為最大序列號(hào)的請(qǐng)求碼（11111111），所有在其廣播范圍內(nèi)的標(biāo)簽都會(huì)回應(yīng)此請(qǐng)求碼。由曼徹斯特編碼可知，上述四個(gè)標(biāo)簽序列號(hào)的第3位、第5位、第6位、第7位不同，意味著標(biāo)簽識(shí)別過(guò)程中在上述位置會(huì)發(fā)生碰撞，由此可得其解碼為1XXX1X01。由上述分析可知，標(biāo)簽識(shí)別過(guò)程中碰撞的最高位為第7位，因此讀寫(xiě)器使高于第7位的數(shù)值保持不變，第7位的數(shù)值設(shè)為0，低于第7位的數(shù)值全部設(shè)置為1，由此可獲得新的請(qǐng)求碼——10111111。

（2）讀寫(xiě)器發(fā)送請(qǐng)求碼（10111111），電子標(biāo)簽收到請(qǐng)求碼后會(huì)將自身序列號(hào)與請(qǐng)求碼（10111111）進(jìn)行比較，序列號(hào)不大于請(qǐng)求碼的標(biāo)簽會(huì)應(yīng)答，由此可知標(biāo)簽3和標(biāo)簽4會(huì)應(yīng)答。由曼徹斯特編碼可知，這兩個(gè)標(biāo)簽的序列號(hào)會(huì)在第3位、第5位、第6位發(fā)生碰撞，由此讀寫(xiě)器會(huì)將碰撞最高位第6位的數(shù)值設(shè)為0，高于第6位的數(shù)值保持不變，而低于第6位的數(shù)值則全部設(shè)置為1，由此可獲得新的請(qǐng)求碼——10011111。

（3）讀寫(xiě)器發(fā)送請(qǐng)求碼（10011111），電子標(biāo)簽收到請(qǐng)求碼后會(huì)將自身序列號(hào)與請(qǐng)求碼（10011111）進(jìn)行比較，序列號(hào)不大于請(qǐng)求碼的標(biāo)簽會(huì)進(jìn)行應(yīng)答，此次只有標(biāo)簽4應(yīng)答。讀寫(xiě)器將給標(biāo)簽4發(fā)送指令使其進(jìn)入休眠狀態(tài)，不再響應(yīng)。然后算法需返回根節(jié)點(diǎn)，新的請(qǐng)求碼為最大序列號(hào)，即11111111。

（4）讀寫(xiě)器發(fā)送請(qǐng)求碼（11111111），所有在其廣播范圍內(nèi)的標(biāo)簽都會(huì)回應(yīng)此請(qǐng)求碼。收到請(qǐng)求碼的標(biāo)簽1、標(biāo)簽2和標(biāo)簽3都會(huì)應(yīng)答。由曼徹斯特編碼可知，上述三個(gè)標(biāo)簽的序列號(hào)會(huì)在第3位、第5位、第6位、第7位發(fā)生碰撞，由此讀寫(xiě)器會(huì)將碰撞最高位第7位的數(shù)值設(shè)為0，高于第7位的數(shù)值保持不變，而低于第7位的數(shù)值都設(shè)為1，由此可獲得新的請(qǐng)求碼，即10111111。

（5）讀寫(xiě)器發(fā)送請(qǐng)求碼（10111111），電子標(biāo)簽收到請(qǐng)求碼后會(huì)將自身序列號(hào)與請(qǐng)求碼（10111111）進(jìn)行比較，序列號(hào)不大于請(qǐng)求碼的標(biāo)簽會(huì)進(jìn)行應(yīng)答，此次只有標(biāo)簽3應(yīng)答。讀寫(xiě)器將給標(biāo)簽3發(fā)送指令使其進(jìn)入休眠狀態(tài)，不再響應(yīng)。同時(shí)算法需返回根節(jié)點(diǎn)，新的請(qǐng)求碼為最大序列號(hào)，即11111111。

（6）讀寫(xiě)器發(fā)送請(qǐng)求碼（11111111），所有在其廣播范圍的標(biāo)簽都會(huì)回應(yīng)此請(qǐng)求碼。收到請(qǐng)求碼的標(biāo)簽1、標(biāo)簽2會(huì)進(jìn)行應(yīng)答。由曼徹斯特編碼可知，上述兩個(gè)標(biāo)簽的序列號(hào)會(huì)在第3位、第5位、第6位發(fā)生碰撞，由此讀寫(xiě)器會(huì)將碰撞最高位第6位的數(shù)值設(shè)為0，高于第6位的則保持不變，低于第6位的數(shù)值則全設(shè)為1，由此可得到新的請(qǐng)求碼，即11011111。

（7）讀寫(xiě)器發(fā)送請(qǐng)求碼（11011111），電子標(biāo)簽收到請(qǐng)求碼后會(huì)將自身序列號(hào)與請(qǐng)求碼（11011111）進(jìn)行比較，此次只有標(biāo)簽1會(huì)進(jìn)行應(yīng)答。讀寫(xiě)器將給標(biāo)簽1發(fā)送指令使其進(jìn)入休眠狀態(tài)，不再響應(yīng)。同時(shí)算法需返回根節(jié)點(diǎn)，新的請(qǐng)求碼為最大序列號(hào)，即11111111。

（8）讀寫(xiě)器發(fā)送請(qǐng)求碼（11111111），所有在其廣播范圍內(nèi)的標(biāo)簽都會(huì)回應(yīng)此請(qǐng)求碼。此次只有標(biāo)簽2進(jìn)行應(yīng)答。讀寫(xiě)器將給標(biāo)簽2發(fā)送指令使其進(jìn)入休眠狀態(tài)，不再響應(yīng)。至此所有標(biāo)簽識(shí)別完成。

由前文描述的二進(jìn)制樹(shù)搜索法的工作流程可知，在無(wú)線射頻識(shí)別系統(tǒng)中發(fā)生標(biāo)簽碰撞的情況下，讀寫(xiě)器會(huì)根據(jù)序號(hào)位數(shù)從高到低不斷調(diào)整請(qǐng)求碼來(lái)達(dá)到標(biāo)簽識(shí)別的目的，且每次標(biāo)簽響應(yīng)閱讀器的請(qǐng)求碼時(shí)傳輸?shù)男蛄刑?hào)都是完整的。顯然，識(shí)別所有電子標(biāo)簽所需的次數(shù)與無(wú)線射頻識(shí)別系統(tǒng)中存在的電子標(biāo)簽數(shù)目成正比關(guān)系，同時(shí)標(biāo)簽識(shí)別所需的時(shí)間也與標(biāo)簽數(shù)目成正比關(guān)系。不妨假設(shè)無(wú)線射頻識(shí)別系統(tǒng)中存在N個(gè)電子標(biāo)簽，根據(jù)算法的特點(diǎn)，需要循環(huán)遍歷搜索。

2 后退二進(jìn)制樹(shù)防碰撞算法

在基本二進(jìn)制樹(shù)防碰撞算法中，每次比對(duì)查找標(biāo)簽的過(guò)程均需對(duì)完整的標(biāo)簽序列號(hào)進(jìn)行傳輸。而現(xiàn)實(shí)中無(wú)線射頻識(shí)別標(biāo)簽的ID號(hào)較長(zhǎng)，且一個(gè)成功的搜索算法都須從頭搜索，當(dāng)標(biāo)簽數(shù)量增多，便會(huì)產(chǎn)生大量無(wú)效的檢測(cè)步驟和冗余數(shù)據(jù)。因此針對(duì)這兩個(gè)問(wèn)題，又提出了后退二進(jìn)制樹(shù)防碰撞算法。

讀寫(xiě)器發(fā)送最大序列號(hào)的請(qǐng)求碼后，所有其廣播范圍內(nèi)的標(biāo)簽都將響應(yīng)請(qǐng)求。當(dāng)發(fā)生碰撞后，序列號(hào)中只有碰撞位的信息不可知，需要查驗(yàn)。所以后退二進(jìn)制防碰撞算法解決了過(guò)量無(wú)用信息的重復(fù)發(fā)送與過(guò)多侵占資源等問(wèn)題。

在操作過(guò)程中，由于標(biāo)簽都位于二進(jìn)制數(shù)的葉子節(jié)點(diǎn)，且基本二進(jìn)制樹(shù)防碰撞算法每次成功識(shí)別出一個(gè)標(biāo)簽后，算法就要返回根節(jié)點(diǎn)再開(kāi)始下一輪查找，這樣不僅浪費(fèi)時(shí)間，而且算法的復(fù)雜度很高。不同于基本二進(jìn)制樹(shù)防碰撞算法，該后退二進(jìn)制樹(shù)防碰撞算法每成功識(shí)別出一個(gè)標(biāo)簽后，就先返回該節(jié)點(diǎn)的父節(jié)點(diǎn)以查找兄弟節(jié)點(diǎn)，以有效減少搜索時(shí)間。后退二進(jìn)制樹(shù)防碰撞算法步驟如下：

（1）當(dāng)讀寫(xiě)器檢測(cè)到有電子標(biāo)簽進(jìn)入其廣播范圍內(nèi)時(shí)，就會(huì)發(fā)送一個(gè)最大序列號(hào)的請(qǐng)求碼，命令所有電子標(biāo)簽都將自身完整的序列號(hào)返回給讀寫(xiě)器。

（2）當(dāng)多個(gè)標(biāo)簽同時(shí)給讀寫(xiě)器發(fā)送序列號(hào)時(shí)，碰撞在所難免。碰撞發(fā)生后，碰撞最高位將被設(shè)定為0，高于碰撞位的數(shù)值設(shè)為1，低于碰撞位的數(shù)值不發(fā)送，并生成下次搜索序列號(hào)命令所需的新請(qǐng)求碼。

（3）讀寫(xiě)器將新請(qǐng)求碼發(fā)送給電子標(biāo)簽，電子標(biāo)簽收到后會(huì)將自己對(duì)應(yīng)請(qǐng)求碼的最高幾位序列號(hào)與請(qǐng)求碼進(jìn)行比較，序列號(hào)不大于請(qǐng)求碼的標(biāo)簽會(huì)應(yīng)答，并將自身剩余的序列號(hào)位返回讀寫(xiě)器。

（4）循環(huán)上述過(guò)程，最終選出序列號(hào)最小的電子標(biāo)簽。發(fā)送指令使其進(jìn)入休眠狀態(tài)，不再響應(yīng)。即下一次讀寫(xiě)器發(fā)送最大序列號(hào)請(qǐng)求碼時(shí)，該電子標(biāo)簽不會(huì)回應(yīng)。返回其父節(jié)點(diǎn)重新獲取發(fā)送序列號(hào)命令所需的搜索請(qǐng)求碼。

（5）反復(fù)執(zhí)行以上步驟，當(dāng)發(fā)出最大序列號(hào)的請(qǐng)求碼也無(wú)碰撞發(fā)生，成功識(shí)別出最后一個(gè)標(biāo)簽后結(jié)束。

繼續(xù)使用上例所使用的四個(gè)標(biāo)簽，運(yùn)用后退二進(jìn)制樹(shù)防碰撞算法識(shí)別標(biāo)簽的過(guò)程如圖3所示。

（1）讀寫(xiě)器發(fā)送最大序列號(hào)請(qǐng)求碼（11111111），所有在其廣播范圍的標(biāo)簽都會(huì)回應(yīng)此請(qǐng)求碼。由曼徹斯特編碼可知，上述四個(gè)標(biāo)簽序列號(hào)的第3位、第5位、第6位、第7位不同，意味著標(biāo)簽識(shí)別過(guò)程中在上述位置會(huì)發(fā)生碰撞，由此可得其解碼為1XXX1X01。由上述分析可知，標(biāo)簽識(shí)別過(guò)程中碰撞的最高位為第7位，因此讀寫(xiě)器會(huì)使高于第7位的數(shù)值保持不變，第7位的數(shù)值設(shè)為0，低于第7位的數(shù)值不發(fā)送，由此可得新的請(qǐng)求碼，即10。

（2）讀寫(xiě)器發(fā)送請(qǐng)求碼（10），電子標(biāo)簽收到請(qǐng)求碼后會(huì)將自身序列號(hào)對(duì)應(yīng)請(qǐng)求碼的最高兩位與請(qǐng)求碼（10）進(jìn)行比較，序列號(hào)不大于請(qǐng)求碼的標(biāo)簽會(huì)進(jìn)行應(yīng)答，由此可知標(biāo)簽3和標(biāo)簽4會(huì)應(yīng)答，并返回各自剩余的后6位序列號(hào)。由曼徹斯特編碼可知，這兩個(gè)標(biāo)簽后6位序列號(hào)會(huì)在第3位、第5位、第6位發(fā)生碰撞，由此讀寫(xiě)器將碰撞最高位第6位的數(shù)值設(shè)為0，高于第6位的數(shù)值保持不變，低于第6位的數(shù)值不發(fā)送，可獲得新請(qǐng)求碼，即100。

（3）讀寫(xiě)器發(fā)送請(qǐng)求碼（100），電子標(biāo)簽收到請(qǐng)求碼后將自身序列號(hào)對(duì)應(yīng)請(qǐng)求碼的最高三位與請(qǐng)求碼（100）進(jìn)行比較，序列號(hào)不大于請(qǐng)求碼的標(biāo)簽會(huì)進(jìn)行應(yīng)答，此次只有標(biāo)簽4應(yīng)答。讀寫(xiě)器將給標(biāo)簽4發(fā)送指令使其進(jìn)入休眠狀態(tài)，不再響應(yīng)。同時(shí)算法返回父節(jié)點(diǎn)，由此可獲得新的請(qǐng)求碼，即10。

（4）讀寫(xiě)器發(fā)送請(qǐng)求碼（10），電子標(biāo)簽收到請(qǐng)求碼后會(huì)將自身序列號(hào)對(duì)應(yīng)請(qǐng)求碼的最高兩位與請(qǐng)求碼（10）進(jìn)行比較，序列號(hào)不大于請(qǐng)求碼的標(biāo)簽會(huì)應(yīng)答，此次只有標(biāo)簽3應(yīng)答。讀寫(xiě)器給標(biāo)簽3發(fā)送指令使其進(jìn)入休眠狀態(tài)，不再響應(yīng)。同時(shí)算法返回根節(jié)點(diǎn)，新的請(qǐng)求碼為最大序列號(hào)，即11111111。

（5）讀寫(xiě)器發(fā)送請(qǐng)求碼（11111111），所有在其廣播范圍內(nèi)的標(biāo)簽都會(huì)回應(yīng)此請(qǐng)求碼。收到請(qǐng)求碼的標(biāo)簽1和標(biāo)簽2應(yīng)答。由曼徹斯特編碼可知，上述兩個(gè)標(biāo)簽的序列號(hào)會(huì)在第3位、第5位、第6位發(fā)生碰撞。由此讀寫(xiě)器會(huì)將碰撞最高位，即第6位的數(shù)值設(shè)為0，高于第6位的數(shù)值保持不變，低于第6位的數(shù)值不發(fā)送，由此得到新的請(qǐng)求碼，即110。

（6）讀寫(xiě)器發(fā)送請(qǐng)求碼（110），電子標(biāo)簽收到請(qǐng)求碼后將自身序列號(hào)對(duì)應(yīng)請(qǐng)求碼的最高三位與請(qǐng)求碼（110）進(jìn)行比較，序列號(hào)不大于請(qǐng)求碼的標(biāo)簽會(huì)應(yīng)答，此次只有標(biāo)簽1應(yīng)答。讀寫(xiě)器給標(biāo)簽1發(fā)送指令使其進(jìn)入休眠狀態(tài)，不再響應(yīng)。同時(shí)算法返回根節(jié)點(diǎn)，新的請(qǐng)求碼為最大序列號(hào)，即11111111。

（7）讀寫(xiě)器發(fā)送請(qǐng)求碼（11111111），所有在其廣播范圍內(nèi)的標(biāo)簽都會(huì)回應(yīng)此請(qǐng)求碼。此次只有標(biāo)簽2會(huì)應(yīng)答。讀寫(xiě)器將給標(biāo)簽2發(fā)送指令使其進(jìn)入休眠狀態(tài)，不再響應(yīng)。由此所有標(biāo)簽識(shí)別完成。

3 算法分析與實(shí)驗(yàn)比較

通常評(píng)估無(wú)線射頻識(shí)別標(biāo)簽防碰撞算法的性能，主要從讀寫(xiě)器向標(biāo)簽發(fā)送請(qǐng)求碼的次數(shù)和讀寫(xiě)器向標(biāo)簽發(fā)送請(qǐng)求碼的總位數(shù)這兩方面入手。

本次實(shí)驗(yàn)主要針對(duì)讀寫(xiě)器發(fā)送的二進(jìn)制請(qǐng)求碼數(shù)據(jù)的總數(shù)位，對(duì)后退二進(jìn)制樹(shù)防碰撞算法與基本二進(jìn)制樹(shù)防碰撞算法進(jìn)行比較。由于實(shí)際應(yīng)用中難以存在標(biāo)準(zhǔn)的數(shù)據(jù)，因此只能選擇隨機(jī)生成的方式來(lái)產(chǎn)生防碰撞算法所需的數(shù)據(jù)。

當(dāng)同時(shí)有20個(gè)標(biāo)簽時(shí)，基本二進(jìn)制樹(shù)防碰撞算法需發(fā)送的請(qǐng)求碼為2 944位，而后退二進(jìn)制樹(shù)防碰撞算法需發(fā)送的請(qǐng)求碼為1 664位，少于基本二進(jìn)制樹(shù)防碰撞算法所發(fā)請(qǐng)求碼位數(shù)的一半。當(dāng)標(biāo)簽個(gè)數(shù)持續(xù)增多時(shí)，兩種算法的性能都有所下降。但當(dāng)標(biāo)簽個(gè)數(shù)為最大值100時(shí)，基本二進(jìn)制樹(shù)防碰撞算法需發(fā)送的請(qǐng)求碼為51 200位，后退二進(jìn)制樹(shù)防碰撞算法只需發(fā)送請(qǐng)求碼30 720位。充分證明后退二進(jìn)制樹(shù)防碰撞算法在識(shí)別標(biāo)簽時(shí)發(fā)送的請(qǐng)求碼位數(shù)更少。發(fā)送二進(jìn)制請(qǐng)求碼總位數(shù)比較如圖4所示。

與基本二進(jìn)制樹(shù)防碰撞算法相比，后退二進(jìn)制樹(shù)防碰撞算法能夠更快地識(shí)別出全部標(biāo)簽。但為了保證所有標(biāo)簽都能被準(zhǔn)確識(shí)別，后退二進(jìn)制樹(shù)防碰撞算法也會(huì)存在一定數(shù)量的冗余請(qǐng)求碼，發(fā)送的二進(jìn)制請(qǐng)求碼位數(shù)明顯少于基本二進(jìn)制樹(shù)防碰撞算法。且后退二進(jìn)制樹(shù)防碰撞算法減少了發(fā)送的請(qǐng)求碼位數(shù)，降低了碰撞位數(shù)量的概率，將在一定程度上減少標(biāo)簽的識(shí)別時(shí)間。

4 結(jié) 語(yǔ)

本文主要介紹了兩種無(wú)線射頻識(shí)別標(biāo)簽防碰撞算法。首先對(duì)產(chǎn)生標(biāo)簽碰撞的原因進(jìn)行了詳細(xì)分析，介紹了現(xiàn)在主要使用的標(biāo)簽防碰撞算法，詳細(xì)描述了基本二進(jìn)制樹(shù)防碰撞算法和后退二進(jìn)制樹(shù)防碰撞算法的思路和步驟。通過(guò)對(duì)算法實(shí)驗(yàn)的結(jié)果進(jìn)行分析、比較，發(fā)現(xiàn)后退二進(jìn)制樹(shù)防碰撞算法可以有效避免大量重復(fù)的檢測(cè)步驟，解決無(wú)效數(shù)據(jù)等問(wèn)題。

參考文獻(xiàn)

[1]吳可，張萌，馮菁.無(wú)線射頻識(shí)別防碰撞算法的研究[J].硅谷，2011（10）：102-103.

[2]田晶.基于二進(jìn)制樹(shù)的無(wú)線射頻識(shí)別系統(tǒng)開(kāi)發(fā)防碰撞算法研究[J].信息通信，2014（2）：50-51.

[3]楊威.基于無(wú)線射頻識(shí)別系統(tǒng)二進(jìn)制樹(shù)防碰撞算法的研究[D]. 武漢：武漢理工大學(xué)， 2011.

[4]向垂益.無(wú)線射頻識(shí)別二進(jìn)制樹(shù)防碰撞算法的研究與實(shí)現(xiàn)[D].長(zhǎng)沙：湖南大學(xué)， 2009.

[5]游戰(zhàn)清，李蘇劍，張益強(qiáng)，等.無(wú)線射頻識(shí)別技術(shù)（RFID理論與應(yīng)用）[M].北京：電子工業(yè)出版社，2006：3-18.

[6] S Ahuja，P Potti.An introduction to RFID technology（Radio Frequency Identification）[J].Pervasive Computing IEEE，2006，5 （l）：25-35.

[7]梁彪，胡愛(ài)群，秦中元.一種新的RFID防碰撞算法設(shè)計(jì)[J].電子與信息學(xué)報(bào)，2007，29（9）：21 58-2160.

[8]王曉東，戎蒙恬.基于Q一選擇的RFID防碰撞算法的研究[J].計(jì)算機(jī)仿真，2008，25（6）：124-126.

[9]夏冬雪，楊斌，陽(yáng)樹(shù)洪.一種基于射頻識(shí)別系統(tǒng)的二進(jìn)制防碰撞算法[J].科協(xié)論壇，2008 （6）：53-54.