一種改進的后退式二進制搜索RFID多標簽防碰撞算法

張文欣， 昂志敏， 尹夕振

（合肥工業(yè)大學計算機與信息學院，安徽合肥 230009）

射頻識別（Radio Frequency Identification，簡稱RFID）技術(shù)［1］是一種非接觸的自動識別技術(shù)，它一般通過無線射頻技術(shù)對目標進行自動識別并獲取相關(guān)的數(shù)據(jù)［2］。當讀寫器的作用范圍內(nèi)存在多個標簽，并且有2個或者2個以上的標簽同時發(fā)送數(shù)據(jù)至讀寫器時就會產(chǎn)生信息之間的相互干擾，導致讀寫器無法正常識別出每個標簽的數(shù)據(jù)，這就是標簽碰撞問題。為了解決這個問題，必須采用有效的防碰撞算法［3］。

RFID系統(tǒng)中標簽防碰撞算法一般有頻分多路（FDMA）、空分多路（SDMA）、碼分多路（CDMA）和時分多路（TDMA）?？紤]到RFID系統(tǒng)中通信形式、功耗、系統(tǒng)的復雜性及成本等因素，目前廣泛采用基于TDMA的防碰撞算法，主要有ALOHA算法［4］和二進制搜索算法［5］。ALOHA算法的所有電子標簽的數(shù)據(jù)都是隨機發(fā)送的，操作簡單，便于實際應用，但是當系統(tǒng)中標簽數(shù)量大量增加時，性能會急劇惡化。二進制搜索算法電路實現(xiàn)比ALOHA算法復雜，但算法識別率和系統(tǒng)吞吐率都比較高。本文在二進制搜索防碰撞算法的基礎(chǔ)上，提出一種改進的防碰撞算法。

1 算法的幾點約定

1.1 Manchester編碼

采用Manchester編碼來辨認出讀寫器中數(shù)據(jù)碰撞的比特位的準確位置，該編碼通過電平的改變來表示數(shù)值位，用邏輯“0”表示上升沿跳變，用邏輯“1”表示下降沿跳變。如果沒有狀態(tài)跳變，就被視為非法數(shù)據(jù)，作為錯誤被識別。當2個或多個標簽同時返回的數(shù)位有不同值時，將會出現(xiàn)上升沿與下降沿互相抵消，以至于無狀態(tài)跳變，讀寫器便知道該位出現(xiàn)碰撞，產(chǎn)生錯誤，因而會進一步搜索［6］。假設(shè)有2個RFID標簽，其ID為8位，利用Manchester編碼能按位識別出碰撞位，如圖1所示。

圖1 采用Manchester編碼按位識別碰撞位

讀寫器檢測出D1、D4位出現(xiàn)碰撞，可知區(qū)域內(nèi)存在多個RFID標簽。

1.2 引入4種命令描述算法

（1）Request。請求命令，請求發(fā)送一序列號作為參數(shù)給區(qū)域里的標簽。標簽將自己的序列號與接收到的序列號相比較，如果小于或者等于，則回送此標簽的序列號給讀寫器。

（2）Select。選擇命令，用某個事先確定的序列號作為參數(shù)發(fā)送給標簽，具有相同序列號的標簽被激活，并以此作為執(zhí)行其他命令（例如讀出和寫入）的切入開關(guān)，即選擇了這個標簽。

（3）Read－data。讀出數(shù)據(jù)，選中的標簽將存儲的數(shù)據(jù)發(fā)送給讀寫器。

（4）Unselect。去選擇，取消事先選中的標簽，使該標簽進入“無聲”狀態(tài)。在此狀態(tài)下，標簽不會對Request命令做出應答。只有將標簽遠離讀寫器的作用范圍即沒有能量供應后復位，才能重新激活標簽。

2 算法原理

2.1 后退式二進制搜索算法

算法特點是發(fā)生碰撞時，根據(jù)碰撞的最高位，跳躍式向前搜索；無碰撞時，采取后退策略，實現(xiàn)標簽的有序讀取。當讀寫器識別出一個標簽后不是從根節(jié)點開始重新查詢，而是退到它的上一層節(jié)點，也就是父親節(jié)點［7］。此算法實現(xiàn)過程如下。

（1）讀寫器發(fā)出Request（11111111），讀寫器作用區(qū)域內(nèi)所有標簽都應答。

（2）檢查是否有碰撞發(fā)生，如果無碰撞則直接識別標簽；如果有碰撞，找到碰撞的最高位。

（3）有碰撞時，將發(fā)生碰撞的最高位置“0”，低于該位的所有位全部置“1”，高于該位的不變，獲得下次Request命令的尋呼參數(shù)。

（4）無碰撞時則直接識別出一個單獨的標簽，然后采用后退策略，從上一次的參數(shù)的父親節(jié)點處獲取下一次Request命令的尋呼參數(shù)。

（5）重復進行上述步驟，直到把所有的標簽全部識別出來。

2.2 改進算法

（1）只標識發(fā)生碰撞的比特位，且只在被標識的比特位上進行防碰撞處理。未發(fā)生碰撞的比特位對于讀寫器來說是已知的，故當讀寫器與標簽通信時，不需要再傳輸已知的比特位，只需在未知的比特位上進行防碰撞處理，這樣能減少發(fā)送的指令長度及能量消耗。

（2）當有碰撞發(fā)生時，先通過碰撞位中“1”的個數(shù)來識別標簽，直接識別出碰撞位全為“1”和全為“0”的標簽。

（3）由于電子標簽的ID是采用曼徹斯特編碼的，每個比特位的取值不是0就是1，是互斥的，因此當讀寫器檢測到只有1個比特位發(fā)生碰撞時，讀寫器就不需要發(fā)送請求命令，而能夠直接識別出這2個標簽。

（4）本算法引入命令Request（UID，1）。UID表示的是讀寫器第1次發(fā)送Request指令后，根據(jù)其譯碼結(jié)果得到下一次Request指令所需的參數(shù)。UID取值有如下約定：當標簽數(shù)據(jù)傳輸發(fā)生碰撞時，讀寫器先判斷出在哪幾位發(fā)生了碰撞，然后將碰撞位置“1”，未碰撞位置“0”，組成新的Request指令。當電子標簽接到讀寫器發(fā)出的Request指令后，標簽將自己的ID與此指令內(nèi)容進行比較，其中與UID中的值為“1”所對應的比特位將被標識出來。這樣在之后的防碰撞處理中，只有被標識的比特位參與數(shù)據(jù)發(fā)送和比較。所有標簽中被標識的比特位中最高位為“1”的標簽，將自己的ID返回給讀寫器。

2.3 算法實現(xiàn)

假設(shè)標簽的ID為8位，在讀寫器作用區(qū)域內(nèi)有8個標簽，分別為：標簽1，00010111；標簽2，00110101；標簽3，00011111；標簽4，00111001；標簽5，00111111；標簽6，00010101；標簽7，00011011；標簽8，00110111。具體實現(xiàn)過程如下。

（1）讀寫器發(fā)送Request（11111111），讀寫器作用區(qū)域內(nèi)所有標簽都應答，讀寫器譯碼得到數(shù)據(jù)為00？1？？？1，可得到下一次尋呼指令為Request（00101110，1），第D5、D3、D2和D1位數(shù)據(jù)發(fā)生碰撞，根據(jù)算法直接識別碰撞位“1”的個數(shù)為0和4的標簽，即標簽5：00111111。

識別標簽后，對已識別的標簽5進行Select激活，再通過Read指令讀取被激活的標簽，最后用Quiet指令對標簽進行去選擇操作，使其進入“無聲”狀態(tài)，屏蔽標簽5。

（2）讀寫器發(fā)送Request（00101110，1），所有標簽ID的D5、D3、D2和D1位被標識，其新的ID為0011、1010、0111、1100、0010、0101、1011，標簽5已被識別并屏蔽，此時最高位為1的標簽2、4、8回送自己新的ID給讀寫器，讀寫器譯碼結(jié)果為1？？？，得到下一次尋呼指令為Request（0111，1）。

（3）讀寫器發(fā)送Request（0111，1），標簽2、4、8應答，其ID的D2、D1和D0位被標識，得到新的ID：010、100、011。新ID中最高位為1的標簽4回送其新的ID給讀寫器，讀寫器選中標簽4并進行讀取操作，最后對標簽4進行去選擇操作，使其進入“無聲”狀態(tài)，屏蔽標簽4。此時算法采用后退策略，回到該節(jié)點的父親節(jié)點，獲得下一次尋呼指令Request（111）。

（4）讀寫器發(fā)送Request（111），標簽2、8應答，譯碼結(jié)果為01？，此時只有一位發(fā)生了碰撞，因此可以直接識別出來，讀寫器直接選中標簽2和8并進行讀取操作，最后對標簽2和8進行去選擇操作，使其進入“無聲”狀態(tài)，屏蔽標簽2和8。算法再次采用后退策略，回到該節(jié)點的父親節(jié)點，獲得下一次尋呼指令Request（1111）。

（5）讀寫器發(fā)送Request（1111），標簽1、3、6和7應答，讀寫器譯碼結(jié)果為0？？？，根據(jù)算法直接識別碰撞位“1”的個數(shù)為0和3的標簽，即標簽3：0111。讀寫器選中標簽3并進行讀取操作，最后對標簽3進行去選擇操作，使其進入“無聲”狀態(tài)，屏蔽標簽3。根據(jù)讀寫器譯碼結(jié)果得到下一次尋呼指令Request（0111，1）。

（6）讀寫器發(fā)送Request（0111，1），標簽1、6、7應答，其序列號的D2、D1和D0位被標識，得到新的ID：011、010、101。標簽7回送其新的ID給讀寫器，讀寫器選中標簽7并進行讀取操作，最后對標簽7進行去選擇操作，使其進入“無聲”狀態(tài)，屏蔽標簽7。

此時算法采用后退策略，回到該節(jié)點的父親節(jié)點，獲得下一次尋呼指令Request（111）。

（7）讀寫器發(fā)送Request（111），標簽1、6應答，譯碼結(jié)果為：01？。此時只有一位發(fā)生了碰撞，因此可以直接識別出來，讀寫器直接選中標簽1和6，并進行讀取操作，最后對標簽1和6，進行去選擇操作，使其進入“無聲”狀態(tài)，屏蔽標簽1和6。

查詢過程如圖2所示。由圖2可知，本算法識別出8個標簽只需要發(fā)送7次指令，而后退式二進制搜索算法［7－8］需要2×8－1＝15次?？梢姳疚牡母倪M算法不僅在工作效率上而且在發(fā)送指令的長度上都有了很大改進，能較快地進行識別。

圖2 算法搜索過程

3 算法性能分析

用后退式二進制搜索算法進行識別時，一個根節(jié)點下面有若干個子節(jié)點，父子節(jié)點之間可以雙向搜索。因此對n個標簽進行識別時，搜索次數(shù)為S（n）＝1＋（n－1）×2＝2n－1。由于本文算法是在基于后退式二進制搜索算法基礎(chǔ)上進行的改進，故即使在最不理想的情況下，也可以保持搜索次數(shù)為2n－1。

當讀寫器作用區(qū)域內(nèi)標簽數(shù)量n較大時，發(fā)生多位碰撞的概率增大。本文算法中，先通過碰撞位中“1”的個數(shù)識別標簽，而且只有碰撞位才被標識并參與以后的防碰撞處理，因此大大減少了搜索次數(shù)，有效地減少了發(fā)送和接收的信息量，縮短了傳輸時間，提高了識別的效率。

將本算法與后退式二進制搜索算法的搜索次數(shù)進行比較，假設(shè)標簽ID為16位，通過Matlab［8］仿真得到結(jié)果，如圖3所示。

圖3 算法的性能比較

由圖3可知，當標簽數(shù)量不是很多時，本算法相比于后退式二進制搜索算法的優(yōu)勢并不明顯，而當標簽數(shù)量明顯增多時，本算法優(yōu)勢逐漸明顯，搜索次數(shù)明顯減少，并且由于發(fā)送信息量減少，效率明顯高于后退式二進制搜索算法。

4 結(jié)束語

防碰撞問題一直以來都是RFID技術(shù)的關(guān)鍵問題。本文在研究了后退式二進制搜索算法的基礎(chǔ)上，提出了改進算法，本算法改變了發(fā)送指令的長度，減少了發(fā)送信息的信息量和讀寫器的搜索次數(shù)，提高了標簽識別效率。通過仿真分析驗證了本算法能更快地識別出碰撞的標簽，相比于后退式二進制搜索算法具有更高的效率，因此具有良好的應用前景。

［1］ 康 東，石喜勤，李勇鵬，等.射頻識別（RFID）核心技術(shù)與應用開發(fā)案例［M］.北京：人民郵電出版社，2008：165－178.

［2］ Yang C N，He J Y.An effective 16－bit random number aided query tree algorithm for RFID tag anti－collision［J］.Communications Letters，IEEE，2011，5（15）：539－541.

［3］ 單承贛，孫 明.基于后退策略的位傳輸二進制搜索算法［J］.合肥工業(yè)大學學報：自然科學版，2010，33（1）：68－71，80.

［4］ 趙曉霞，昂志敏，郭 治.一種新的時隙ALOHA算法［J］.合肥工業(yè)大學學報：自然科學版，2010，33（6）：855－858.

［5］ 馮東旭，夏哲雷，凌訪華.一種改進的RFID防碰撞算法［J］.杭州電子科技大學學報，2010，30（5）：109－112.

［6］ 孫文勝，馬建波.基于二進制搜索算法的RFID系統(tǒng)防碰撞算法［J］.計算機應用與軟件，2010，27（12）：268－269，287.

［7］ 余松森，詹宜巨，彭衛(wèi)東，等.基于后退式索引的二進制樹形搜索反碰撞算法及其實現(xiàn)［J］.計算機工程與應用，2004，40（16）：26－28.

［8］ 趙 謙.通信系統(tǒng)中Matlab基礎(chǔ)與仿真［M］.西安：西安電子科技大學出版社，2010：55－129.