張文欣， 昂志敏， 尹夕振

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

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

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

1 算法的幾點(diǎn)約定

1.1 Manchester編碼

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

圖1 采用Manchester編碼按位識(shí)別碰撞位

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

1.2 引入4種命令描述算法

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

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

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

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

2 算法原理

2.1 后退式二進(jìn)制搜索算法

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

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

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

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

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

（5）重復(fù)進(jìn)行上述步驟，直到把所有的標(biāo)簽全部識(shí)別出來。

2.2 改進(jìn)算法

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

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

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

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

2.3 算法實(shí)現(xiàn)

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

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

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

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

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

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

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

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

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

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

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

圖2 算法搜索過程

3 算法性能分析

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

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

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

圖3 算法的性能比較

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

4 結(jié)束語

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

［1］ 康 東，石喜勤，李勇鵬，等.射頻識(shí)別（RFID）核心技術(shù)與應(yīng)用開發(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ìn)制搜索算法［J］.合肥工業(yè)大學(xué)學(xué)報(bào)：自然科學(xué)版，2010，33（1）：68－71，80.

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

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

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

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

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