王道強，李志鵬

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

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

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

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

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

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

2.1 算法的命令

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

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

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

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

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

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

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

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

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

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

3 改進的二進制防碰撞算法

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

3.1 算法編碼原理

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

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

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

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

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

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

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

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

改進的二進制算法的工作流程圖如圖3所示。

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

改進的二進制算法的主要工作步驟為:

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

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

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

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

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

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

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

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

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

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

4 MATLAB 仿真分析

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

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

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

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

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

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

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

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

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

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

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

5 結(jié)論

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

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

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

［2］李興鶴，胡詠梅，王華蓮，等.基于動態(tài)二進制的二叉樹搜索結(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］吳偉陵，牛 凱.移動通信原理［M］.北京:電子工業(yè)出版社，2005.

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

［6］王 雪，錢志鴻，胡正超，等.基于二叉樹的RFID防碰撞算法的研究［J］.通信學(xué)報，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］單承贛，余春梅，王聰聰.改進的二進制查詢樹的RFID標(biāo)簽防碰撞算法［J］.合肥工業(yè)大學(xué)學(xué)報，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］李 瑾.無線射頻識別(RFID)防碰撞算法的研究和仿真［D］.北京:北京交通大學(xué)，2007.