一種改進(jìn)的RFID防碰撞算法

馮東旭,夏哲雷,凌訪華

(中國計(jì)量學(xué)院信息工程學(xué)院,浙江杭州310018)

0 引 言

射頻識(shí)別(Radio Frequency Identification,RFID)技術(shù)是一種非接觸的自動(dòng)識(shí)別技術(shù),其原理是利用射頻信號(hào)的空間耦合或反射的傳輸特性,實(shí)現(xiàn)對(duì)被識(shí)別物體的自動(dòng)識(shí)別[1]。防碰撞算法是RFID系統(tǒng)中的關(guān)鍵技術(shù)之一,當(dāng)閱讀器的作用范圍內(nèi)存在多個(gè)標(biāo)簽,并有兩個(gè)或者兩個(gè)以上的標(biāo)簽同時(shí)響應(yīng)閱讀器時(shí)將會(huì)產(chǎn)生碰撞。解決RFID系統(tǒng)中標(biāo)簽碰撞問題一般有空分多路、頻分多路、碼分多路和時(shí)分多路等方法[2]。但考慮到RFID系統(tǒng)中通信形式、功耗、系統(tǒng)的復(fù)雜性及成本等因素,目前廣泛使用的防碰撞算法都是基于TDMA的,比較經(jīng)典的兩類是：基于ALOHA的防碰撞算法和基于二進(jìn)制搜索的防碰撞算法。本文在二進(jìn)制防碰撞算法的基礎(chǔ)上,提出了一種改進(jìn)的防碰撞算法。

1 RFID系統(tǒng)的構(gòu)成

RFID系統(tǒng)一般由電子標(biāo)簽和讀寫器兩部分構(gòu)成。電子標(biāo)簽(又稱應(yīng)答器)是由耦合天線及芯片構(gòu)成,每個(gè)標(biāo)簽具有唯一的電子產(chǎn)品代碼(EPC),并附著在被標(biāo)識(shí)的物體或?qū)ο笊稀Ｗx寫器(又稱閱讀器)是讀取或擦寫標(biāo)簽信息的設(shè)備,用于發(fā)送和接收射頻信號(hào)。讀寫器和標(biāo)簽之間采用非接觸雙向通信,已達(dá)到交換數(shù)據(jù)并識(shí)別的目的。RFID系統(tǒng)的結(jié)構(gòu)組成如圖1所示：

圖1 RFID系統(tǒng)結(jié)構(gòu)圖

2 二進(jìn)制防碰撞算法

二進(jìn)制防碰撞算法的基本思想是將處于碰撞的標(biāo)簽分成左右兩個(gè)子集0和1,先查詢子集0,若沒有碰撞,則正確識(shí)別標(biāo)簽,若有碰撞則再分裂,把子集0分成00和01兩個(gè)子集。依次類推,直到識(shí)別出子集0中的所有標(biāo)簽,再按此步驟查詢子集1[1]。

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

二進(jìn)制搜索算法采用曼徹斯特編碼,能夠準(zhǔn)確檢測(cè)出碰撞位的位置。為了實(shí)現(xiàn)這個(gè)算法,引入以下4種命令。

(1)REQUEST--請(qǐng)求命令：發(fā)送一序列號(hào)作為參數(shù)給區(qū)域內(nèi)的標(biāo)簽。標(biāo)簽把自己的序列號(hào)與接收的相比較,若小于或者等于,則此標(biāo)簽回送其序列號(hào)給閱讀器;

(2)SELECT--選擇命令：用某個(gè)(事先確定的)序列號(hào)作為參數(shù)發(fā)送給標(biāo)簽。具有相同序列號(hào)的應(yīng)答器將以此作為執(zhí)行其他命令(讀出和寫入)的切入開關(guān),即選擇了標(biāo)簽;

(3)READ-DATA--讀出數(shù)據(jù)：選中的標(biāo)簽將存儲(chǔ)的數(shù)據(jù)發(fā)送給閱讀器;

(4)UNSELECT--去選擇：取消一個(gè)事先選中的標(biāo)簽,使其進(jìn)入無聲狀態(tài),這樣標(biāo)簽對(duì)QEQUEST命令不再作應(yīng)答。

假設(shè)閱讀器范圍內(nèi)有 4個(gè)標(biāo)簽,即標(biāo)簽 1：10100111;標(biāo)簽 2：10110101;標(biāo)簽 3：10101111;標(biāo)簽4：10111101。二進(jìn)制搜索算法的工作流程如下：

(1)閱讀器發(fā)送REQUEST(11111111)命令,要求區(qū)域內(nèi)所有標(biāo)簽應(yīng)答。根據(jù)曼徹斯特編碼,閱讀器譯碼結(jié)果為101XX1X1,D1、D3、D4位發(fā)生碰撞,算法做如下處理：將碰撞最高位D4置“0”,高于D4位的數(shù)位不變,低于D4位的置“1”,可得到下一次REQUEST命令所需的參數(shù),即10101111;

(2)閱讀器發(fā)送REQUEST(10101111)命令,標(biāo)簽1和3應(yīng)答。閱讀器譯碼結(jié)果為1010X111,D3位發(fā)生碰撞,將D3位置“0”,低于D3位置“1”,得到下一次REQUEST命令所需參數(shù),即10100111;

(3)閱讀器發(fā)送REQUEST(10100111)命令,只有標(biāo)簽1應(yīng)答。沒有碰撞發(fā)生,閱讀器對(duì)標(biāo)簽1進(jìn)行讀取操作后,執(zhí)行UNSELECT命令使得標(biāo)簽1進(jìn)入無聲狀態(tài);

(4)算法從第一步重復(fù)上述過程直到所有的標(biāo)簽都被識(shí)別出來為止。

由二進(jìn)制搜索算法的工作流程可知,標(biāo)簽的數(shù)量越多,防碰撞執(zhí)行的時(shí)間將越長。此算法識(shí)別一個(gè)標(biāo)簽平均的搜索次數(shù)可用式N=logn2+1來計(jì)算,其中n為電子標(biāo)簽的個(gè)數(shù)[2]。

2.2 基于后退式索引的二級(jí)制搜索算法

此算法是在二進(jìn)制搜索算法的基礎(chǔ)上改進(jìn)而來,與二進(jìn)制算法不同的是該算法在閱讀器識(shí)別出一個(gè)標(biāo)簽后不是從根節(jié)點(diǎn)開始重新查詢,而是退到它的上一層節(jié)點(diǎn),即父親節(jié)點(diǎn)。

仍以4個(gè)標(biāo)簽為例,來說明此算法的實(shí)現(xiàn)過程。

(1)閱讀器發(fā)送REQUEST(11111111)命令,標(biāo)簽1、2、3、4均應(yīng)答。閱讀器譯碼結(jié)果為101XX1X1,D1、D3、D4位發(fā)生碰撞,算法做如下處理：將碰撞最高位D4置“0”,高于D4位的數(shù)位不變,低于D4位的置“1”,可得到下一次REQUEST命令所需的參數(shù),即10101111;

(2)閱讀器發(fā)送REQUEST(10101111)命令,標(biāo)簽1和3應(yīng)答。譯碼結(jié)果為1010X111,D3位發(fā)生碰撞,同上可得到下一次REQUEST命令所需的參數(shù),即10100111;

(3)閱讀器發(fā)送REQUEST(10100111)命令,只有標(biāo)簽1應(yīng)答。沒有碰撞發(fā)生,閱讀器對(duì)標(biāo)簽1進(jìn)行閱讀操作后,執(zhí)行UNSELECT命令使得標(biāo)簽1進(jìn)入無聲狀態(tài)。算法采用后退策略,從該節(jié)點(diǎn)的父親節(jié)點(diǎn)獲得下一次REQEST命令的參數(shù)即10101111;

(4)閱讀器發(fā)送REQUEST(10101111)命令,標(biāo)簽3應(yīng)答,無碰撞。閱讀器對(duì)標(biāo)簽3進(jìn)行閱讀操作后使其進(jìn)入無聲狀態(tài)。算法再采用后退策略,得到下一次的尋呼命令REQUEST(11111111);

(5)閱讀器發(fā)送REQUEST(11111111)命令,標(biāo)簽2和4應(yīng)答,譯碼結(jié)果為1011X101,D3位發(fā)送碰撞,同樣可得到下一次的尋呼命令參數(shù)REQUEST(10110111);

(6)閱讀器發(fā)送REQUEST(10110111)命令,只有標(biāo)簽2應(yīng)答,將標(biāo)簽2處理完畢后返回到父親節(jié)點(diǎn)得到下次的尋呼命令參數(shù)REQUEST(11111111);

(7)閱讀器發(fā)送REQUEST(11111111)命令,標(biāo)簽4應(yīng)答,識(shí)別過程結(jié)束。

該算法的特點(diǎn)是：碰撞發(fā)生時(shí),根據(jù)碰撞的最高位跳躍式向前搜索;無碰撞時(shí),采取后退策略。這樣能夠有效地減少時(shí)間復(fù)雜度,更快速的識(shí)別所有標(biāo)簽[3]。

3 改進(jìn)的防碰撞算法

3.1 算法的改進(jìn)思路

與上述防碰撞算法相比,本文提出的算法主要有兩點(diǎn)改進(jìn)：(1)采用標(biāo)識(shí)碰撞位的方法,把發(fā)生碰撞的比特位標(biāo)識(shí)出來,只在被標(biāo)識(shí)的比特位上進(jìn)行防碰撞處理。因?yàn)槿绻喿x器譯碼有K個(gè)位置發(fā)生碰撞,說明只有這K個(gè)比特位對(duì)于閱讀器來說是未知的,其他比特位對(duì)閱讀器來說已經(jīng)是已知的。因此在閱讀器與電子標(biāo)簽的通信中可以不再傳輸這些已知的比特位,只在未知的比特位上作防碰撞處理,以減少傳輸時(shí)延和能耗;(2)采用曼徹斯特編碼的電子標(biāo)簽的序列號(hào)每個(gè)比特位的取值不是1就是0,具有相互排斥的特性。所以如果閱讀器檢測(cè)到只有一個(gè)比特位發(fā)生碰撞時(shí),則閱讀器可以不需要發(fā)送請(qǐng)求命令而能夠直接識(shí)別這兩個(gè)標(biāo)簽。該算法在大量標(biāo)簽存在的情況下會(huì)大大縮短識(shí)別的時(shí)間、提高識(shí)別的效率。

本改進(jìn)算法需要引入一條命令,即REQUEST(UID,0)。UID表示閱讀器第一次尋呼之后,根據(jù)譯碼結(jié)果所得到的下一次的尋呼指令。UID的取值約定為：閱讀器在判斷出數(shù)據(jù)發(fā)生碰撞的準(zhǔn)確比特位之后,將碰撞位置“1”,未發(fā)生碰撞的位置“0”,組成新的尋呼指令。閱讀器發(fā)出這個(gè)尋呼指令之后,電子標(biāo)簽的響應(yīng)為：標(biāo)簽接到這個(gè)命令之后將自己的序列號(hào)與之相比較,與UID中值為“1”所對(duì)應(yīng)的比特位將被標(biāo)識(shí)出來。在以后的防碰撞處理中,參與數(shù)據(jù)發(fā)送和比較的僅僅是這幾個(gè)被標(biāo)識(shí)的比特位。碰撞位被標(biāo)識(shí)以后所有電子標(biāo)簽被標(biāo)識(shí)的比特位中最高位為“0”的回送自己的ID給閱讀器。下面以上述的4個(gè)標(biāo)簽和另外4個(gè)標(biāo)簽為例來說明這一過程,8個(gè)示范標(biāo)簽如表1所示：

表1 8個(gè)示范標(biāo)簽

3.2 算法的實(shí)現(xiàn)過程

(1)閱讀器發(fā)送REQUEST(11111111)命令,區(qū)域內(nèi)所有電子標(biāo)簽都應(yīng)答。閱讀器譯碼結(jié)果為：101XXXX1?？傻玫较乱淮蔚膶ず糁噶顬镽EQUEST(00011110,0);

(2)閱讀器發(fā)送REQUEST(00011110,0)命令,所有標(biāo)簽序列號(hào)的D4、D3、D2和D1位被標(biāo)識(shí),得到他們新的 ID：0011、1010、0111、1110、1111、0010、0101 和 1011,同時(shí)標(biāo)簽 1、3、6、7 回送自己新的 ID 給閱讀器,閱讀器譯碼為0XXX。得到下一次的尋呼指令REQUEST(0111,0);

(3)閱讀器發(fā)送REQUEST(0111,0)命令,標(biāo)簽1、3、6、7應(yīng)答其序列號(hào)的D2、D1、D0位被標(biāo)識(shí),得到他們新的ID：011、111、010、101,同時(shí)標(biāo)簽1和6回送自己新的ID號(hào)給閱讀器。閱讀器譯碼結(jié)果為01X,因?yàn)橹挥幸粋€(gè)比特位發(fā)生碰撞,閱讀器直接選擇標(biāo)簽1和6。然后對(duì)這兩個(gè)標(biāo)簽進(jìn)行讀寫處理,最后讀寫器運(yùn)行“去選擇”命令使標(biāo)簽1和6進(jìn)入“無聲”狀態(tài)。算法采用后退策略,從該節(jié)點(diǎn)的父親節(jié)點(diǎn)獲得下一次命令的參數(shù)REQUEST(111);

(4)閱讀器發(fā)送REQUEST(111)命令,標(biāo)簽3和7應(yīng)答,譯碼結(jié)果為1X1。因?yàn)橹挥幸粋€(gè)比特位發(fā)生碰撞,閱讀器直接選擇標(biāo)簽3和7。然后對(duì)這兩個(gè)標(biāo)簽進(jìn)行讀寫處理,最后讀寫器運(yùn)行“去選擇”命令使標(biāo)簽3和7進(jìn)入“無聲”狀態(tài)。算法再采用后退策略,從該節(jié)點(diǎn)的父親節(jié)點(diǎn)獲得下一次命令的參數(shù)REQUEST(1111);

(5)閱讀器發(fā)送REQUEST(1111)命令,標(biāo)簽2、4、5、8應(yīng)答,閱讀器譯碼結(jié)果為1XXX。得到下一次的尋呼指令為REQUEST(1000,1);

(6)閱讀器發(fā)送REQUEST(1000,1)命令,標(biāo)簽2、4、5、8應(yīng)答其序列號(hào)的D2、D1、D0位被標(biāo)識(shí),得到他們新的ID：010、110、111、011,同時(shí)標(biāo)簽2和8回送自己新的ID號(hào)給閱讀器。閱讀器譯碼結(jié)果為01X,因?yàn)橹挥幸粋€(gè)比特位發(fā)生碰撞,閱讀器直接選擇標(biāo)簽2和8,然后對(duì)這兩個(gè)標(biāo)簽進(jìn)行讀寫處理,最后讀寫器運(yùn)行“去選擇”命令使標(biāo)簽2和8進(jìn)入“無聲”狀態(tài)。算法采用后退策略,從該節(jié)點(diǎn)的父親節(jié)點(diǎn)獲得下一次的命令參數(shù)REQUEST(111);

(7)閱讀器發(fā)送REQUEST(111)命令,標(biāo)簽4和5應(yīng)答,譯碼結(jié)果為11X。因?yàn)橹挥幸粋€(gè)比特位發(fā)生碰撞,閱讀器直接選擇標(biāo)簽4和5。然后對(duì)這兩個(gè)標(biāo)簽進(jìn)行讀寫處理,最后讀寫器運(yùn)行“去選擇”命令使標(biāo)簽4和5進(jìn)入“無聲”狀態(tài)。所有標(biāo)簽都被識(shí)別出來,識(shí)別過程結(jié)束。該實(shí)例防碰撞處理過程的樹型結(jié)構(gòu)圖如圖2示。

圖2 算法實(shí)例的樹型結(jié)構(gòu)圖

4 結(jié)束語

從圖2可知改進(jìn)算法識(shí)別8個(gè)標(biāo)簽的搜索次數(shù)為7次,而二進(jìn)制搜索算法識(shí)別4個(gè)標(biāo)簽的搜索次數(shù)為12次,后退式索引搜索算法的搜索次數(shù)為7次。比較發(fā)現(xiàn)改進(jìn)算法的搜索次數(shù)明顯低于其他算法,可以通過數(shù)學(xué)歸納法證明,如果被標(biāo)識(shí)的比特位中有n個(gè)參與以后的防碰撞處理,則識(shí)別2n個(gè)標(biāo)簽所用搜索的次數(shù)為2n-1-1次。另外,標(biāo)簽?zāi)芎牡拇笮∪Q于閱讀器尋呼次數(shù)以及標(biāo)簽接收和發(fā)送的比特長度。本改進(jìn)算法采用標(biāo)識(shí)碰撞位的方法僅讓碰撞位參與防碰撞處理,使系統(tǒng)的傳輸數(shù)據(jù)量、搜索次數(shù)以及傳輸時(shí)間大大縮短,有效減少標(biāo)簽?zāi)芎?節(jié)省了傳輸信道提高識(shí)別效率。隨著電子標(biāo)簽數(shù)目增加以及標(biāo)簽序列號(hào)比特位數(shù)變長,該改進(jìn)算法的優(yōu)勢(shì)將會(huì)越來越明顯。

[1]康東,石喜勤,李勇鵬,等.射頻識(shí)別(RFID)核心技術(shù)與典型應(yīng)用開發(fā)案例[M].北京：人民郵電出版社,2008：168-179.

[2]Klaus Finkenzellr.吳曉峰,陳大才,譯.射頻識(shí)別技術(shù)([第三版])[M].北京：電子工業(yè)出版社,2006：160-169.

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

[4]陳沖,徐志,何明華.一種新的 RFID防碰撞算法的研究[J].福州大學(xué)學(xué)報(bào)(自然科學(xué)版),2009,37(3)：367-371.

[5]Jia-linMa,XuWei.An Improved Anti-collision Algorithm In RFID System[J].Hybrid IntelligentSystems,2009,3(9)：138-141.