基于RFID的二進(jìn)制防碰撞算法的改進(jìn)

王道強(qiáng)，李志鵬

(東北林業(yè)大學(xué)交通學(xué)院，哈爾濱150040)

1 RFID系統(tǒng)中的二進(jìn)制防碰撞算法

二進(jìn)制防碰撞算法是基于二進(jìn)制樹(shù)理論，是把產(chǎn)生碰撞的標(biāo)簽分裂成兩個(gè)結(jié)點(diǎn)0和1，若結(jié)點(diǎn)1中的標(biāo)簽繼續(xù)發(fā)生碰撞，則再次分裂分成10和11兩個(gè)結(jié)點(diǎn)［1］。依此類推，直到識(shí)別出結(jié)點(diǎn)1中的所有標(biāo)簽。如圖1所示。

圖1 二進(jìn)制防碰撞算法模型Fig.1 Binary anti－collision algorithm model

2 二進(jìn)制搜索 (Binary Search)算法

在二進(jìn)制防碰撞算法的基礎(chǔ)上提出了二進(jìn)制搜索算法，這是一種無(wú)記憶的算法，為了在一組電子標(biāo)簽中選擇任意一個(gè)，閱讀器發(fā)出一個(gè)請(qǐng)求命令，有意識(shí)地將電子標(biāo)簽傳輸時(shí)的數(shù)據(jù)碰撞引導(dǎo)到閱讀器上。閱讀器的命令查詢的是一個(gè)比特前綴，只有序列號(hào)與閱讀器查詢命令前綴相符的標(biāo)簽才能響應(yīng)閱讀器，并回送其序列號(hào)，當(dāng)有多個(gè)標(biāo)簽同時(shí)響應(yīng)的時(shí)候，閱讀器把下一次發(fā)送的查詢命令的前綴增加一個(gè)比特0，通過(guò)不斷的增加命令前綴，使閱讀器能夠識(shí)別所有的標(biāo)簽［2］。

2.1 算法的命令

(1)REQUEST:請(qǐng)求命令，該命令發(fā)送一組序列號(hào)作為參數(shù)給電子標(biāo)簽。若電子標(biāo)簽的序列號(hào)小于或等于閱讀器發(fā)送的序列號(hào)，則將自身的序列號(hào)回送給閱讀器。

(2)SELECT:選擇命令，用某個(gè)事先確定好的序列號(hào)作為參數(shù)發(fā)送給電子標(biāo)簽。具有相同的序列號(hào)的標(biāo)簽將此作為執(zhí)行其他的命令 (例如讀出和寫(xiě)入)的切入開(kāi)關(guān)，即選擇了標(biāo)簽。

(3)READDATE:讀出數(shù)據(jù)命令，選中的電子標(biāo)簽將其存儲(chǔ)的數(shù)據(jù)發(fā)送給閱讀器。

(4)UNSELECT:去選擇命令，取消一個(gè)選中的標(biāo)簽，標(biāo)簽進(jìn)入無(wú)聲狀態(tài)，這種狀態(tài)中的電子標(biāo)簽完全是非激活的，對(duì)收到的REQUEST命令不作應(yīng)答［3］。

2.2 算法的原理和執(zhí)行過(guò)程

假設(shè)閱讀器周圍存在著四個(gè)電子標(biāo)簽T1、T2、T3、T4，并 且 它 們 的 ID分 別 為 10111101、10101111、10110101、10100111。

第1步，閱讀器在其工作區(qū)域內(nèi)發(fā)送命令REQUEST(11111111)，標(biāo)簽序列號(hào)小于或等于閱讀器命令的與閱讀器進(jìn)行通信。閱讀器對(duì)應(yīng)答的標(biāo)簽進(jìn)行譯碼，得到解碼數(shù)據(jù)101XX1X1，判斷出發(fā)生碰撞的比特位D4、D3、D1［4］，進(jìn)行如下處理:將D4位置“0”，高于D4位的不變化，低于D4位的置“1”，得到下一次命令所需要的序列號(hào)10101111。

第2步，閱讀器發(fā)送命令 REQUEST(10101111)，標(biāo)簽T2和T4應(yīng)答，對(duì)標(biāo)簽進(jìn)行解碼，得到解碼數(shù)據(jù)為1010X111，將最高碰撞位D3置“0”，得到下一次命令所需要的序列號(hào)10100111。

第3步，閱讀器發(fā)送命令 REQUEST(10100111)，只有標(biāo)簽T4應(yīng)答。無(wú)碰撞產(chǎn)生，閱讀器處理完標(biāo)簽T4后，使其進(jìn)入無(wú)聲狀態(tài)，接著重復(fù)上述過(guò)程直到識(shí)別所有的標(biāo)簽為止。識(shí)別過(guò)程見(jiàn)表1。

表1 二進(jìn)制搜索算法的實(shí)現(xiàn)過(guò)程Tab.1 Realization of binary search algorithm

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

二進(jìn)制搜索算法有著明顯的缺陷，閱讀器發(fā)給每個(gè)標(biāo)簽的比較序列，其中有用的信息只包含在高于上次碰撞碰撞位X比特的高位之中，而且每一次識(shí)別標(biāo)簽之后都要從頭開(kāi)始查詢，算法執(zhí)行時(shí)間較長(zhǎng)，為了解決這些缺陷，本文提出了改進(jìn)的算法。

3.1 算法編碼原理

為了能夠在算法中準(zhǔn)確的辨認(rèn)出數(shù)據(jù)碰撞的比特位，改進(jìn)的算法采用Manchester編碼［5］。該編碼也叫做相位編碼 (PE)，是一個(gè)同步時(shí)鐘編碼技術(shù)，是用電平的跳變 (上升沿/下降沿)來(lái)表示數(shù)值位。這里，虛線所在位置由高電平跳變到低電平，編碼為邏輯“1”;由低電平跳變到高電平，編碼為邏輯“0”，若不產(chǎn)生跳變，則視為非法數(shù)據(jù)，當(dāng)作錯(cuò)誤數(shù)據(jù)識(shí)別。當(dāng)兩個(gè)或兩個(gè)以上標(biāo)簽同時(shí)返回的數(shù)位出現(xiàn)不同值時(shí)，則上升沿與下降沿相互抵消，導(dǎo)致無(wú)狀態(tài)跳變，可知閱讀器的數(shù)據(jù)出現(xiàn)碰撞，出現(xiàn)了錯(cuò)誤，應(yīng)當(dāng)進(jìn)一步搜索，如圖2所示。

3.2 算法的原理和執(zhí)行過(guò)程

在二進(jìn)制搜索算法命令的基礎(chǔ)上，新增兩個(gè)命令。

(1)新增命令REQUEST(ID，1):這里的ID的取值表示的是閱讀器第一次與標(biāo)簽進(jìn)行通訊之后，對(duì)標(biāo)簽的序列號(hào)進(jìn)行譯碼，判斷出產(chǎn)生碰撞的比特位，我們規(guī)定把產(chǎn)生碰撞的比特位置“1”，沒(méi)有產(chǎn)生碰撞的比特位置“0”，從而得到的下一次尋呼的序列號(hào)。

1表示的是先處理鎖定的標(biāo)簽碰撞位中最高位為1的標(biāo)簽組。

圖2 Manchester編碼得到的沖突位Fig.2 The conflict bit in Manchester coding

(2)新增命令REQUEST(ID):

這里的ID的取值表示的是閱讀器在進(jìn)行REQUEST(ID，1)命令之后，如果標(biāo)簽繼續(xù)產(chǎn)生碰撞，同樣我們規(guī)定把產(chǎn)生碰撞的比特位置1，沒(méi)有產(chǎn)生碰撞的比特位置0，則標(biāo)簽鎖定閱讀器第一次發(fā)出的ID中值為1的比特位，在接下來(lái)的防碰撞處理過(guò)程中，參與數(shù)據(jù)發(fā)送的僅僅是鎖定的幾個(gè)產(chǎn)生標(biāo)簽碰撞的比特位，然后通過(guò)對(duì)標(biāo)簽的譯碼所得到的下一次尋呼的鎖定序列號(hào)［6］。這里產(chǎn)生碰撞的標(biāo)簽中，首先將鎖定的所有比特位中的最高位的值為1的標(biāo)簽回送自己的序列號(hào)給閱讀器，并且返回鎖定位除最高位以外的其他鎖定位。

改進(jìn)的二進(jìn)制算法的工作流程圖如圖3所示。

圖3 改進(jìn)的二進(jìn)制防碰撞算法的工作流程圖Fig.3 Work flowchart of the improved binary anti－collision algorithm

改進(jìn)的二進(jìn)制算法的主要工作步驟為:

第1步，閱讀器在其工作區(qū)域內(nèi)發(fā)送 REQUEST(全“1”序列)，標(biāo)簽ID小于或等于閱讀器命令的與閱讀器進(jìn)行通信。

第2步，閱讀器對(duì)應(yīng)答的標(biāo)簽進(jìn)行譯碼，若無(wú)碰撞產(chǎn)生則識(shí)別標(biāo)簽，使其進(jìn)入無(wú)聲狀態(tài)。

第3步，若有碰撞產(chǎn)生，則對(duì)標(biāo)簽進(jìn)行譯碼，將產(chǎn)生碰撞的比特位置“1”，未產(chǎn)生碰撞的比特位置“0”，得到新增命令REQUEST(ID，1)。

第4步，閱讀器發(fā)送REQUEST(ID，1)，標(biāo)簽再接收到該命令后，將閱讀器的命令I(lǐng)D與自己的序列號(hào)進(jìn)行比較，鎖定產(chǎn)生碰撞的比特位，鎖定位中比特位最高位為1的標(biāo)簽優(yōu)先進(jìn)行作答，并將除鎖定位以外的剩下幾位回送給閱讀器［7］。

第5步，閱讀器判斷回送的標(biāo)簽序列號(hào)是否產(chǎn)生碰撞，若無(wú)碰撞產(chǎn)生則識(shí)別標(biāo)簽，使其進(jìn)入無(wú)聲狀態(tài)，若有碰撞產(chǎn)生，閱讀器對(duì)回送的標(biāo)簽序列號(hào)繼續(xù)進(jìn)行譯碼，判斷產(chǎn)生碰撞的比特位，將發(fā)生碰撞的最高比特位置1，高于該碰撞位的不變。低于該碰撞位的舍去，得到新增命令REQUEST(ID)。

第6步，閱讀器發(fā)送REQUEST(ID)，繼續(xù)判斷有無(wú)碰撞，每當(dāng)順利的識(shí)別標(biāo)簽之后，都將采用后退策略，返回上一次產(chǎn)生碰撞的結(jié)點(diǎn)，識(shí)別結(jié)點(diǎn)的另一個(gè)分支，直到把鎖定碰撞位的最高位為1的標(biāo)簽組全部識(shí)別完。

第7步，閱讀器在識(shí)別完鎖定碰撞位最高位為1的標(biāo)簽組之后，發(fā)送命令REQUEST(0)，識(shí)別鎖定碰撞位最高位為0的標(biāo)簽組，過(guò)程原理同第5步和第6步。直到識(shí)別所有標(biāo)簽結(jié)束。

下面舉例介紹改進(jìn)算法工作的具體實(shí)現(xiàn)過(guò)程:

假設(shè)閱讀器周圍存在著四個(gè)電子標(biāo)簽T1、T2、T3、T4，并 且 它 們 的 ID分 別 為 11100010、11110011、11100011、10100011。識(shí)別標(biāo)簽 T2的具體操作流程如圖4所示。

圖4 改進(jìn)的二進(jìn)制搜索算法的實(shí)例操作流程Fig.4 Procedures of the example based on improved binary search algorithm

4 MATLAB 仿真分析

通過(guò)matlab仿真比較分析了在不同的情況下，改進(jìn)的算法相比于二進(jìn)制搜索算法的優(yōu)勢(shì)。

(1)通信次數(shù)。二進(jìn)制搜索算法識(shí)別n個(gè)標(biāo)簽所需要的尋呼次數(shù)為QBS=n· ［integ(log2n)+1］，integ()表示向上取整函數(shù)［8］。而改進(jìn)的算法的通訊次數(shù)Q改=2n－1，如圖5所示。

從圖可以看出，改進(jìn)的二進(jìn)制算法在閱讀器的尋呼次數(shù)上明顯低于二進(jìn)制搜索算法，而且隨著n值的增大，改進(jìn)的二進(jìn)制算法優(yōu)勢(shì)越明顯。

(2)傳輸時(shí)延。傳輸時(shí)延就是閱讀器從開(kāi)始發(fā)送數(shù)據(jù)到數(shù)據(jù)全部發(fā)送完畢所需要的時(shí)間［9］，二進(jìn)制搜索算法和改進(jìn)的二進(jìn)制算法的傳輸時(shí)延分別為:

圖5 改進(jìn)的算法與二進(jìn)制搜索算法的通信次數(shù)比較Fig.5 Comparison on the communication frequency of improved algorithm and binary search algorithm

其中x的取值范圍為 ［integ(log2n)，k］。

假設(shè)標(biāo)簽ID的長(zhǎng)度k的取值為64 bit，傳輸速率為100K bit/s，，產(chǎn)生碰撞的比特位數(shù)x取k時(shí)，得到算發(fā)法的傳輸時(shí)延隨標(biāo)簽個(gè)數(shù)n的變化關(guān)系如圖6所示。

圖6 改進(jìn)的算法與二進(jìn)制搜索算法的傳輸時(shí)延比較Fig.6 Comparison on the transmission delay of improved algorithm and binary search algorithm

從圖6中可以看到即使x取最大值k，改進(jìn)的二進(jìn)制算法的傳輸時(shí)延都要小于二進(jìn)制搜索算法。

(3)吞吐量。吞吐量代表有效傳輸?shù)膶?shí)際總效率［10］，二進(jìn)制搜索算法和改進(jìn)的算法的吞吐量分別為:

改進(jìn)的算法和二進(jìn)制搜索算法在吞吐量上的比較，從圖中可以看出在吞吐量上改進(jìn)的算法的明顯優(yōu)于二進(jìn)制搜索算法，隨著n的增大，改進(jìn)的二進(jìn)制算法吞吐量趨近于50%如圖7所示。

5 結(jié)論

圖7 改進(jìn)的算法與二進(jìn)制搜索算法的吞吐量的比較Fig.7 Comparison on the transaction capacity of improved algorithm and binary search algorithm

在實(shí)際的情況下，RFID系統(tǒng)一般都使用較長(zhǎng)的ID碼進(jìn)行數(shù)據(jù)的傳輸，二進(jìn)制搜索算法在每一次識(shí)別標(biāo)簽之后都要從頭開(kāi)始查詢，耗費(fèi)大量的算法執(zhí)行時(shí)間。通過(guò)matlab仿真對(duì)比分析，改進(jìn)的二進(jìn)制算法不僅節(jié)省了數(shù)據(jù)傳輸?shù)臅r(shí)間，減少了通訊次數(shù)，而且在傳輸?shù)男噬弦裁黠@高于二進(jìn)制搜索算法。

［1］康 東，石喜勤，李勇鵬.射頻識(shí)別核心技術(shù)與典型應(yīng)用開(kāi)發(fā)案例［M］.北京:人民郵政出版社，2008.

［2］李興鶴，胡詠梅，王華蓮，等.基于動(dòng)態(tài)二進(jìn)制的二叉樹(shù)搜索結(jié)構(gòu) RFID 反碰撞算法［J］.山東科學(xué)，2006，19(2):51－55.

［3］ Wang T P.Enhanced binary search with cut－through operation for anti－ Collision in RFID systems［J］.IEEE Communications Letters，2006，10(4):236 －238.

［4］吳偉陵，牛 凱.移動(dòng)通信原理［M］.北京:電子工業(yè)出版社，2005.

［5］傅祖蕓.信息論—基礎(chǔ)理論與應(yīng)用［M］.北京:電子工業(yè)出版社，2001.

［6］王 雪，錢志鴻，胡正超，等.基于二叉樹(shù)的RFID防碰撞算法的研究［J］.通信學(xué)報(bào)，2010，31(6):48 －57.

［7］ Shih D H，Sun P L，Yen D.Taxonomy and survey of RFID anticollision protocols［J］.Computer Communications，2006，29(11):2150－2166.

［8］單承贛，余春梅，王聰聰.改進(jìn)的二進(jìn)制查詢樹(shù)的RFID標(biāo)簽防碰撞算法［J］.合肥工業(yè)大學(xué)學(xué)報(bào)，2008，31(11)，1801 －1804.

［9］ Choi J H.Query tree－based reservation for efficient RFID tag anticollision［J］.IEEE Communications Letters，2007，11(1):85 －87.

［10］李 瑾.無(wú)線射頻識(shí)別(RFID)防碰撞算法的研究和仿真［D］.北京:北京交通大學(xué)，2007.