康維新，吳學(xué)文, 2

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

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

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

1 RFID防碰撞算法

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

1.1 ALOHA系列防碰撞算法

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

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

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

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

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

1.2 二進(jìn)制樹系列防碰撞算法

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

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

二進(jìn)制搜索算法(Binary Search BS算法)是基于輪詢方式，無記憶查詢，由多個周期閱讀器查詢和電子標(biāo)簽應(yīng)答實現(xiàn)電子標(biāo)簽篩選識別.在每個查詢與應(yīng)答周期內(nèi)，閱讀器發(fā)出帶比特前綴的查詢命令，電子比標(biāo)簽將自身的ID與查詢命令進(jìn)行比較并進(jìn)行應(yīng)答.其應(yīng)答約定為：ID序列小于或者等于查詢命令的電子標(biāo)簽進(jìn)行應(yīng)答，若識別區(qū)域內(nèi)有兩個以上電子標(biāo)簽同時滿足應(yīng)答條件，閱讀器判斷為標(biāo)簽碰撞.接著閱讀器根據(jù)發(fā)生碰撞的最高比特位，將此位置“0”，該位以后的比特位都置“1”，產(chǎn)生新的查詢命令，再進(jìn)行尋呼，識別出一個電子標(biāo)簽后，閱讀器從頭開始發(fā)送Request(1111……1111)指令，按照上述方式來識別其它的電子標(biāo)簽，直到工作區(qū)域內(nèi)所有的電子標(biāo)簽都被識別出來.二進(jìn)制搜索算法的命令序列格式：Request(請求命令)—Select(選擇命令)—Read_Data(讀寫數(shù)據(jù)命令)—Unselect(退出命令)[7].搜索算法本質(zhì)上就是二叉樹的一種遍歷形式.假設(shè)標(biāo)簽平均每次傳送的二進(jìn)制碼的長度為L，int(·)為向上取整，成功識別一個標(biāo)簽的搜索次數(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)二進(jìn)制搜索算法(Dynamic Binary Search DBS算法)是一種改進(jìn)的BS算法[8].在BS算法中，閱讀器尋呼與標(biāo)簽響應(yīng)的都是傳輸完整的標(biāo)簽ID號，如果標(biāo)簽ID號很長，所傳輸?shù)臄?shù)據(jù)量就會非常大，這樣就增加了搜索時間和出錯頻率.實際上，閱讀器發(fā)送的請求命令中，最高碰撞位以后各位不包含給電子標(biāo)簽的補(bǔ)充信息，因為這些位總是被置“1”，只要事先預(yù)定好，這些信息可不必發(fā)送.電子標(biāo)簽響應(yīng)的ID號的 最高碰撞位以前各位不包含給閱讀器的補(bǔ)充信息，因為這些位是已知且給定的.若把這些冗余信息剪掉，系統(tǒng)的傳輸效率會大大提高.因此，DBS算法的每次搜索，閱讀器只發(fā)送碰撞位之前的比特位信息及碰撞位比特碼，標(biāo)簽只回送給閱讀器碰撞位之后的比特位，一次搜索傳輸?shù)男畔⒘空脼橐粋€完整標(biāo)簽的比特位長度L.

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

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

(4)

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

(5)

總通信量LDBS為：

(6)

后退式二進(jìn)制搜索算法(Retreat Binary Search RBS算法)是從減少搜索次數(shù)上對BS算法的改進(jìn).BS算法與DBS算法每成功識別一個標(biāo)簽之后，都會回到根節(jié)點，發(fā)送全“1”的最大Request命令.而RBS算法則不同于二者，它成功識別一個標(biāo)簽之后，并不返回根節(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算法是在減少通信量的基礎(chǔ)上對BS算法的改進(jìn)，其通信量只有BS算法的，總搜索次數(shù)與BS算法相同.RBS算法是在減少總搜索次數(shù)基礎(chǔ)上對BS算法的改進(jìn)，其搜索次數(shù)較BS、DBS算法有了較大減少，系統(tǒng)的吞吐量維持在左右[10].

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

2.1 改進(jìn)算法原理

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

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

2.2 改進(jìn)算法流程及實例分析

改進(jìn)算法的流程如圖2所示.

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

2.3 改進(jìn)的防碰撞算法仿真結(jié)果分析

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

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

圖2 改進(jìn)的防碰撞算法流程圖

圖3 改進(jìn)的防碰撞算法操作實例

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

圖5 總通信量比較

圖6 吞吐率比較

3 結(jié) 語

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

參考文獻(xiàn)：

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

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

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

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

[5] 王 雪, 錢志鴻, 胡正超, 等. 基于二叉樹的 RFID 防碰撞算法的研究[J]．通信學(xué)報, 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與傳感器網(wǎng)絡(luò)：架構(gòu)、協(xié)議、安全與集成[M]. 北京: 機(jī)械工業(yè)出版社, 2012. 1-45.

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

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

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