一種改進的RFID標簽防碰撞算法

康維新，吳學文, 2

(1. 哈爾濱工程大學 信息與通信工程學院，哈爾濱 150001; 2. 中國人民解放軍91899部隊，遼寧 葫蘆島 125001)

射頻識別(Radio Frequency Identification，RFID)技術即一種自動識別技術，通過無線射頻方式進行非接觸式雙向數(shù)據通信，對目標加以識別并獲取相關數(shù)據，整個識讀過程不需要人員參與即可完成信息讀寫及相關處理，操作簡單快捷[1].RFID技術在物品的追蹤管理上有很大的優(yōu)勢:非接觸式自動識別技術，數(shù)據存儲容量大、可讀寫、可重復利用、穿透能力強、讀寫距離遠、讀取速度快、環(huán)境適應性好、使用壽命長，可以實現(xiàn)多目標識別的自動識別技術[2].

無線射頻識別技術最大的特點是非接觸式的自動識別，且在閱讀器識別范圍內實現(xiàn)多目標識別，然而多標簽與閱讀器同時通信，必然會在無線共享信道上形成相互干擾，致使閱讀器不能成功接收電子標簽的數(shù)據信息，從而產生了電子標簽碰撞問題.

1 RFID防碰撞算法

目前，已研究出許多種技術來解決標簽防碰撞問題，其中多址技術為標簽防碰撞的常見解決方法.該技術主要為空分多址(SDMA)技術、碼分多址(CDMA)技術、頻分多址(FDMA)技術和時分多址(TDMA)技術.前三種多址技術主要基于硬件的技術，通過改善硬件的條件來解決碰撞問題，但因利用率低、實現(xiàn)成本比較高，所以較少實用[3].目前RFID系統(tǒng)中普遍采用的防碰撞算法主要是基于TDMA思想，TDMA防碰撞算法又可以分為兩大類：一類是基于二進制搜索的確定性標簽防碰撞算法，一類是基于ALOHA的概率性算法[4].

1.1 ALOHA系列防碰撞算法

純ALOHA算法(Pure ALOHA PA算法)是最簡單的基于ALOHA的標簽防碰撞算法，此種算法采取“標簽先發(fā)言”的方式，即標簽一進入閱讀器的工作范圍就自動向閱讀器發(fā)該標簽的ID.這樣，在共享的無線信道內，不同標簽的信息傳輸時間就會有很大概率發(fā)生重疊，導致識別的碰撞，碰撞分為完全碰撞和部分碰撞.一旦發(fā)生碰撞，閱讀器就會命令標簽停止發(fā)送自身ID信息，該標簽會隨機的選擇回退時間進行重新發(fā)送，直到該標簽被閱讀器識別為止.

時隙ALOHA算法(Slot ALOHA SA算法)是對PA算法的改進，即在原始的PA算法基礎上將時間分成若干個時間相等的離散時隙(slot)，并且每個時隙的的長度大于標簽與閱讀器數(shù)據交換的時間長度.系統(tǒng)時鐘控制時隙長度，并要求各控制單元與系統(tǒng)時鐘同步，同時，每個標簽必須在時隙起始時刻發(fā)送數(shù)據信息，因此，標簽只會完全接收和完全碰撞兩種狀態(tài).

幀時隙ALOHA算法(Frame Slot ALOHA FSA算法)是對SA算法的改進，在SA算法的基礎之上引入幀的概念，把L個時隙組成一幀，標簽在每一幀值范圍內隨機選擇一時隙發(fā)送ID數(shù)據給閱讀器.

動態(tài)幀時隙ALOHA算法(Dynamic Frame Slot ALOHA DFSA算法)是對FSA算法的改進.在FSA算法中，幀長L為固定值，當標簽逐漸被識別后，未被標簽數(shù)逐漸變少，或進入識別范圍的標簽逐漸變多時，上一幀結束后，下一幀中空閑時隙或碰撞時隙必然會增多，這些將嚴重降低系統(tǒng)的識別效率.DFSA算法為解決此問題，將幀值L的大小根據標簽數(shù)量的變化進行動態(tài)的調整.

由于基于ALOHA的概率性算法采取“標簽先發(fā)言” 的模式，并且多標簽“發(fā)言”具有很大的隨機性，導致某一標簽可能在相當長的一段時間內無法識別，而且在應用中，隨著標簽數(shù)量的擴大，性能將會急劇惡化，出現(xiàn)吞吐量偏低、“餓死”、識別速度緩慢、能量消耗大等缺點[5].

1.2 二進制樹系列防碰撞算法

二進制搜索系列算法的實現(xiàn)防碰撞的基礎條件為對碰撞比特位得準確定位.由曼徹斯特(Manchester)編碼原理可知，信號的上升沿代表邏輯“0”，下降沿代表邏輯“1”，若信號未發(fā)生跳變，則認為是該位沒有數(shù)據，確認該位出現(xiàn)了碰撞[6].因此，Manchester編譯碼是二進制搜索系列算法的主要編碼方式，其監(jiān)測碰撞位過程如圖1所示.

圖1 曼徹斯特編碼檢測碰撞位

二進制搜索算法(Binary Search BS算法)是基于輪詢方式，無記憶查詢，由多個周期閱讀器查詢和電子標簽應答實現(xiàn)電子標簽篩選識別.在每個查詢與應答周期內，閱讀器發(fā)出帶比特前綴的查詢命令，電子比標簽將自身的ID與查詢命令進行比較并進行應答.其應答約定為：ID序列小于或者等于查詢命令的電子標簽進行應答，若識別區(qū)域內有兩個以上電子標簽同時滿足應答條件，閱讀器判斷為標簽碰撞.接著閱讀器根據發(fā)生碰撞的最高比特位，將此位置“0”，該位以后的比特位都置“1”，產生新的查詢命令，再進行尋呼，識別出一個電子標簽后，閱讀器從頭開始發(fā)送Request(1111……1111)指令，按照上述方式來識別其它的電子標簽，直到工作區(qū)域內所有的電子標簽都被識別出來.二進制搜索算法的命令序列格式：Request(請求命令)—Select(選擇命令)—Read_Data(讀寫數(shù)據命令)—Unselect(退出命令)[7].搜索算法本質上就是二叉樹的一種遍歷形式.假設標簽平均每次傳送的二進制碼的長度為L，int(·)為向上取整，成功識別一個標簽的搜索次數(shù)為：

S(N)=log2N+1

(1)

總搜索次數(shù)S(N)為：

S(N)=int(log2N!+N)

(2)

總通信量LBS為：

LBS=S(N)×L=int(log2N!+N)×L

(3)

動態(tài)二進制搜索算法(Dynamic Binary Search DBS算法)是一種改進的BS算法[8].在BS算法中，閱讀器尋呼與標簽響應的都是傳輸完整的標簽ID號，如果標簽ID號很長，所傳輸?shù)臄?shù)據量就會非常大，這樣就增加了搜索時間和出錯頻率.實際上，閱讀器發(fā)送的請求命令中，最高碰撞位以后各位不包含給電子標簽的補充信息，因為這些位總是被置“1”，只要事先預定好，這些信息可不必發(fā)送.電子標簽響應的ID號的 最高碰撞位以前各位不包含給閱讀器的補充信息，因為這些位是已知且給定的.若把這些冗余信息剪掉，系統(tǒng)的傳輸效率會大大提高.因此，DBS算法的每次搜索，閱讀器只發(fā)送碰撞位之前的比特位信息及碰撞位比特碼，標簽只回送給閱讀器碰撞位之后的比特位，一次搜索傳輸?shù)男畔⒘空脼橐粋€完整標簽的比特位長度L.

總搜索次數(shù)S(N)為：

S(N)=int(log2N!+N)

(4)

平均每次傳輸?shù)谋忍財?shù)為：

(5)

總通信量LDBS為：

(6)

后退式二進制搜索算法(Retreat Binary Search RBS算法)是從減少搜索次數(shù)上對BS算法的改進.BS算法與DBS算法每成功識別一個標簽之后，都會回到根節(jié)點，發(fā)送全“1”的最大Request命令.而RBS算法則不同于二者，它成功識別一個標簽之后，并不返回根節(jié)點，而是返回上次碰撞節(jié)點，即父節(jié)點[9].

RBS算法的總搜索次數(shù)S(N)為：

S(N)=2N-1

(7)

總通信量LRBS為：

LRB=S(N)×L=(2N-1)×L

(8)

BS算法雖然能解決ALOHA算法中的“餓死”問題，但卻由于過大的搜索次數(shù)及總通信量，使系統(tǒng)識別速度降低，能耗變大，系統(tǒng)的吞吐率最大為左右；DBS算法是在減少通信量的基礎上對BS算法的改進，其通信量只有BS算法的，總搜索次數(shù)與BS算法相同.RBS算法是在減少總搜索次數(shù)基礎上對BS算法的改進，其搜索次數(shù)較BS、DBS算法有了較大減少，系統(tǒng)的吞吐量維持在左右[10].

2 一種改進的RFID防碰撞算法

2.1 改進算法原理

通過上節(jié)對各算法的研究分析，可以看出，要提高防碰撞算法的性能可以從兩個方面進行改進，一是減少閱讀器與標簽的通信次數(shù)，即減少搜索次數(shù)；二是減少數(shù)據傳輸量，即減少通信的比特長度.本節(jié)以二進制搜索算法為基礎，采用曼徹斯特編解碼機制，結合動態(tài)二進制搜索算法和后退二進制算法的優(yōu)點，提出了一種改進算法.

改進算法命令組：Request (SN)：請求(序列號)，此命令要求閱讀器向進場標簽發(fā)送一尋呼序列，標簽接到命令后將自身序列號與之比對，如果電子標簽的ID中包含此前綴序列號，則此電子標簽回送其序列號給閱讀器.Request (SN，0)：鎖位查詢命令，該命令根據標簽查詢結果，進行曼徹斯特譯碼，確定碰撞位后根據取值約定，生成下一輪的尋呼序列號.它的取值約定為：對解碼的后的標簽序列號進行碰撞位判斷，對閱讀解碼系列的碰撞位置“1”，其余非碰撞位置“0”，從而得到鎖定碰撞位的查詢命令.閱讀器在發(fā)送鎖位查詢命令后，電子標簽按位將自身的ID與查詢命令中與邏輯“1”對應的比特位鎖定提取，生成新的標簽ID，以后的查詢與應答均是以此ID作為依據.并且此查詢命令發(fā)送后，只有鎖定的最高碰撞位為邏輯“0”的電子標簽進行應答，回送值為除了最高鎖定位的新ID.Request (SN，1)：“1”分支尋呼.針對Request (SN，0)命令，“0”分支識別結束，返回父節(jié)點進行尋呼命令.Select(選擇命令)、Read_Data(讀寫數(shù)據命令)、Unselect(退出命令)與之前的二進制搜索算法命令一致.

2.2 改進算法流程及實例分析

改進算法的流程如圖2所示.

下面以標簽A(10110011)、標簽B(10100010)、標簽C(10110010)、標簽D(11100010)進行實例演示分析,具體過程如圖3.

2.3 改進的防碰撞算法仿真結果分析

在理想信道條件下，不計控制、前后綴和校驗冗余等開銷，參考ISO18000-6 標準，進行仿真.標簽數(shù)量在0～100動態(tài)變化，標簽ID長度為16位，比特率為100 Kb/s，通過20次仿真取均值，對讀寫器識別所有標簽所用總搜索次數(shù)、系統(tǒng)總通信量以及吞吐率等性能指標進行分析，與BS算法、DBS算法、RBS算法進行比較.

圖4為閱讀器在不同標簽下各算法的總搜索次數(shù)比較，由于改進算法使用后退二進制搜索算法的返回策略，同時改進算法由于對碰撞位進行鎖位處理，這樣減少了搜索次數(shù)，經過仿真分析，改進算法總搜索次數(shù)較其他算法有很大改進；圖5為各算法的總通信量比較，由于改進算法采取對碰撞位的鎖位處理，每次傳輸?shù)臄?shù)據只是對碰撞位進行處理，這樣就減少了傳輸?shù)男畔⒘?，通過對比分析，改進算法的總通信量的顯著減少，提高了識別的速度；圖6為各算法的吞吐率分析，通過仿真分析，改進算法的吞吐率在50%～60%，略高于后退式二進制搜索法，并且隨著標簽數(shù)的增加有顯著增大趨勢.

圖2 改進的防碰撞算法流程圖

圖3 改進的防碰撞算法操作實例

圖4 總搜索次數(shù)比較圖

圖5 總通信量比較

圖6 吞吐率比較

3 結 語

本文分析了當前的防碰撞算法，結合實際應用提出了一種改進的防碰撞算法，該算法以減少搜索次數(shù)與減少信息傳輸量為改進思路，采用了曼徹斯特編解碼識別機制，碰撞位鎖定機制，后退式二進制搜索算法的后退機制，跳躍二進制搜索算法的碰撞位傳輸機制四種機制有效的結合，經過仿真分析，驗證了算法的可行性，降低了系統(tǒng)的能耗，同時對標簽的硬件要求較低，更利于實踐應用.

參考文獻：

[1] 李全圣, 劉忠立, 吳里江. 特高射頻識別技術及應用[M]. 北京: 國防工業(yè)出版社, 2010. 275-277.

[2] 徐 卓. 基于RFID的軍用物流管理系統(tǒng)的研究與設計[D]. 哈爾濱: 哈爾濱工程大學, 2011. 1-3.

[3] 胡正超. 基于二進制樹的RFID防碰撞算法的研究[D].長春: 吉林大學, 2009. 26-28.

[4] 馮 娜, 潘偉杰, 李少波, 等. 基于新穎跳躍式動態(tài)搜索的RFID防碰撞算法[J]. 計算機應用, 2012, 32(1): 288 -291.

[5] 王 雪, 錢志鴻, 胡正超, 等. 基于二叉樹的 RFID 防碰撞算法的研究[J]．通信學報, 2010, 31(6): 49-57．

[6] KLAIR D K, CHIN K W, RAAD R. A survey and tutorial of RFID anti-collision protocols [J]. IEEE Communications Surveys & Tutorials, 2010, 12(3): 400-421.

[7] ZHANG Yan, YANG L T, CHEN Ji-ming. RFID與傳感器網絡：架構、協(xié)議、安全與集成[M]. 北京: 機械工業(yè)出版社, 2012. 1-45.

[8] 楊成龍. RFID裝備管理系統(tǒng)的防碰撞算法[J]．四川兵工學報, 2013, 34(6): 75-78.

[9] 王 玨. RFID防碰撞算法的研究[D]. 南京: 南京郵電大學, 2011. 23-30.

[10] 張文欣，昂志敏，尹夕振. 一種改進的后退式二進制搜索RFID多標簽防碰撞算法[J]．合肥工業(yè)大學學報:自然科學版, 2012, 35(7): 199-221.