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

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

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

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

1 RFID防碰撞算法

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

1.1 ALOHA系列防碰撞算法

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

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

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

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

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

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

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

圖1 曼徹斯特編碼檢測(cè)碰撞位

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

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

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

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

(4)

平均每次傳輸?shù)谋忍財(cái)?shù)為：

(5)

總通信量LDBS為：

(6)

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

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

S(N)=2N-1

(7)

總通信量LRBS為：

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

(8)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

圖5 總通信量比較

圖6 吞吐率比較

3 結(jié) 語(yǔ)

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

參考文獻(xiàn)：

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

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

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

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

[5] 王 雪, 錢(qián)志鴻, 胡正超, 等. 基于二叉樹(shù)的 RFID 防碰撞算法的研究[J]．通信學(xué)報(bào), 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é)報(bào), 2013, 34(6): 75-78.

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

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