王佩瑋

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

關鍵詞：無線射頻識別；讀寫器；基本二進制樹防碰撞算法；后退二進制樹防碰撞算法

中圖分類號：TP391 文獻標識碼：A 文章編號：2095-1302（2017）04-00-04

0 引 言

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

1 基本二進制樹防碰撞算法

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

基本二進制樹防碰撞算法識別標簽時，讀寫器需要多次發(fā)送電子標簽的標簽序列號。這時定義數(shù)據(jù)傳送的順序為由低位到高位依次發(fā)送。在讀寫器或電子標簽內(nèi)部比較數(shù)據(jù)時也遵循這一原則。按照標簽序列號由低位再到高位的順序比較，約定0<1。根據(jù)該順序，判斷數(shù)據(jù)的大小時從最低位開始。即兩個數(shù)A，B相比，從最右邊的低位開始，直到遇到不相等數(shù)位。當兩個數(shù)的所有數(shù)位都相同時，這兩個數(shù)就是相等的。

基本二進制樹防碰撞算法的步驟如圖1所示。

因為每個電子標簽的序列號都不相同，所以當多于兩個的電子標簽同時給讀寫器發(fā)送數(shù)據(jù)時，就不可避免地發(fā)生碰撞。當碰撞發(fā)生后，請求碼中相應碰撞最高位的數(shù)值將被設定為0，低于碰撞位的數(shù)值保持不變，高于碰撞位的數(shù)值設定為1，生成新請求碼。讀寫器將更新后的請求碼傳遞給電子標簽，電子標簽會繼續(xù)用自己的序列號與新請求碼進行比較。如果序列號不大于請求碼，則會返回自身的序列號給讀寫器。

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

循環(huán)全部步驟，最終將所有電子標簽按序列號由小到大的順序識別出來。但需注意的是，循環(huán)全部步驟應從算法的最開始重復，即讀寫器確定一個電子標簽后，將重新發(fā)送最大序列號的請求碼。

以四個標簽同時進入讀寫器的廣播范圍為例。標簽1的序列號為（11011001），標簽2的序列號為（11101101），標簽3的序列號為（10111001），標簽4的序列號為（10001001）?；径M制樹防碰撞算法識別標簽過程如圖2所示。

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

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

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

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

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

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

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

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

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

2 后退二進制樹防碰撞算法

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

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

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

（1）當讀寫器檢測到有電子標簽進入其廣播范圍內(nèi)時，就會發(fā)送一個最大序列號的請求碼，命令所有電子標簽都將自身完整的序列號返回給讀寫器。

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

（3）讀寫器將新請求碼發(fā)送給電子標簽，電子標簽收到后會將自己對應請求碼的最高幾位序列號與請求碼進行比較，序列號不大于請求碼的標簽會應答，并將自身剩余的序列號位返回讀寫器。

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

（5）反復執(zhí)行以上步驟，當發(fā)出最大序列號的請求碼也無碰撞發(fā)生，成功識別出最后一個標簽后結束。

繼續(xù)使用上例所使用的四個標簽，運用后退二進制樹防碰撞算法識別標簽的過程如圖3所示。

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

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

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

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

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

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

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

3 算法分析與實驗比較

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

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

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

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

4 結 語

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

參考文獻

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

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

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

[4]向垂益.無線射頻識別二進制樹防碰撞算法的研究與實現(xiàn)[D].長沙：湖南大學， 2009.

[5]游戰(zhàn)清，李蘇劍，張益強，等.無線射頻識別技術（RFID理論與應用）[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]梁彪，胡愛群，秦中元.一種新的RFID防碰撞算法設計[J].電子與信息學報，2007，29（9）：21 58-2160.

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

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