基于標(biāo)簽序列號擴展分組的防碰撞算法

王博文

(中煤科工集團(tuán)重慶研究院有限公司,重慶 400039)

0 引言

將射頻識別(radio frequency identification,RFID)讀寫器置于多個標(biāo)簽構(gòu)成的區(qū)域內(nèi)時，讀寫器的線圈會產(chǎn)生磁場，使該區(qū)域的所有標(biāo)簽都開始向讀寫器發(fā)送標(biāo)簽的序列號(下文簡稱ID)等標(biāo)簽信息。當(dāng)兩個以上標(biāo)簽在同一時刻同時向讀寫器發(fā)送數(shù)據(jù)，就會產(chǎn)生通信沖突[1-2]。通信沖突在讀寫器端表現(xiàn)，為接收的幀錯誤，也稱為標(biāo)簽通信碰撞。由于標(biāo)簽之間不能互相通信，并且標(biāo)簽不具備檢測沖突的功能，所以沖突判斷必須由讀寫器完成。

防碰撞算法能夠?qū)⒆x寫器覆蓋區(qū)域的標(biāo)簽ID區(qū)分開來，使讀寫器能準(zhǔn)確地識別標(biāo)簽。所以，防碰撞算法也是RFID標(biāo)簽識別研究的重點。現(xiàn)有的RFID防碰撞算法大致分為以下幾類:美國夏威夷研究計劃高等算術(shù)高級學(xué)習(xí)(advanced learning on higher arithmetic,ALOHA)算法、時隙ALOHA算法、動態(tài)時隙ALOHA算法、二進(jìn)制樹形搜索算法?？傮w來說，ALOHA算法是一種非確定的方法，由電子標(biāo)簽控制發(fā)送時間[3]。而二進(jìn)制樹形搜索算法由讀寫器來控制標(biāo)簽發(fā)送時間，是一種確定的方法。

1 現(xiàn)有的防碰撞算法

1.1 ALOHA算法

ALOHA算法有純ALOHA算法和時隙ALOHA兩種。純ALOHA算法是通過標(biāo)簽隨機發(fā)送ID信息至讀寫器，避免大概率的沖突，對具體的時隙沒有要求。純ALOHA算法標(biāo)簽信息沖突如圖1所示。

圖1 純ALOHA算法標(biāo)簽信息沖突示意圖

時隙ALOHA算法是讓標(biāo)簽在讀寫器分配的時隙內(nèi)隨機發(fā)出ID信息至讀寫器。這種方式避免了純ALOHA算法的部分碰撞問題[4]。時隙ALOHA算法標(biāo)簽信息沖突如圖2所示。

圖2 時隙ALOHA算法標(biāo)簽信息沖突示意圖

1.2 基于曼徹斯特編碼的二進(jìn)制樹形搜索算法

曼徹斯特編碼如圖3所示。

圖3 曼徹斯特編碼示意圖

該算法主要基于曼徹斯特編碼來識別標(biāo)簽ID信息的沖突位[4-5]。如果兩個或者多個標(biāo)簽向讀寫器發(fā)送的比特位有不同值，則讀寫器接收到的多標(biāo)簽ID疊加信息碼中上升沿和下降沿互相抵消。根據(jù)該編碼規(guī)則，就將其判斷為誤碼，從而識別出沖突的比特位?；诼鼜厮固鼐幋a的標(biāo)簽信息碰撞容錯圖如圖4所示。

圖4 基于曼徹斯特編碼的標(biāo)簽信息碰撞容錯圖

二進(jìn)制樹形搜索法的基本思想是將沖突中的標(biāo)簽按照二叉樹形狀劃分為若干個子集。由于每個沖突的位由0和1兩個子集組成，所以通過遍歷整個二叉樹，就可以讓讀寫器依次訪問到每個標(biāo)簽[6]。

基于二叉樹模型的標(biāo)簽沖突子集如圖5所示。

圖5 基于二叉樹模型的標(biāo)簽沖突子集圖

1.3 幾種算法的評析

ALOHA算法原理是當(dāng)標(biāo)簽的信息發(fā)生沖突時，讀寫器控制標(biāo)簽隨機延遲一段時間再次發(fā)送標(biāo)簽ID，直到?jīng)]有沖突為止。這種算法在標(biāo)簽數(shù)量較少時，具有較高的實用價值。但是標(biāo)簽數(shù)量過多會導(dǎo)致標(biāo)簽沖突頻繁，時延劃分過長會導(dǎo)致個別標(biāo)簽響應(yīng)時間過長，使個別標(biāo)簽出現(xiàn)饑餓現(xiàn)象[7]。個別標(biāo)簽響應(yīng)時間過長，會讓讀寫器認(rèn)為當(dāng)前的標(biāo)簽已經(jīng)讀取，從而出現(xiàn)誤判現(xiàn)象。

在二進(jìn)制樹形搜索算法中，讀寫器一次性只能讀取一個標(biāo)簽ID。當(dāng)標(biāo)簽ID過長時，通過樹形遍歷的方式過于繁瑣。該算法和當(dāng)前的標(biāo)簽進(jìn)行信息交互后要立即發(fā)送靜默指令使該標(biāo)簽進(jìn)入休眠狀態(tài)，直到重復(fù)上電(讀寫器重新激活標(biāo)簽區(qū)域的磁場)才能正常工作[8]。

基于以上原因，本文提出了基于標(biāo)簽序列號擴展分組的防碰撞算法。該算法的實現(xiàn)較為復(fù)雜，需要在讀寫器和標(biāo)簽兩端同時實現(xiàn)匹配的功能。但是其可以處理多標(biāo)簽沖突問題，且一次處理可以讀取多個標(biāo)簽。

2 基于標(biāo)簽序列號擴展分組的防碰撞算法

在二進(jìn)制樹形搜索算法的基礎(chǔ)上，本文引入了一種基于標(biāo)簽序列號擴展分組的防碰撞協(xié)議。該防碰撞協(xié)議同樣基于曼徹斯特編碼原理，對讀寫器覆蓋區(qū)域的標(biāo)簽ID所構(gòu)成的集合按照沖突的(binary digit,BIT)(這里稱為窗口大小)進(jìn)行分組。通過分組再分組的遞歸方式，實現(xiàn)標(biāo)簽ID的準(zhǔn)確識別[7]。

2.1 擴展分組的防碰撞算法舉例

讀寫器讀取到多個標(biāo)簽的信息之后，根據(jù)曼徹斯特編碼原理檢查沖突的BIT位。當(dāng)沖突的標(biāo)簽ID信息BIT位確定之后，再根據(jù)沖突的BIT位來劃分標(biāo)簽的子集[10]。在該算法中，讀寫器檢測到標(biāo)簽序列號沖突后，依據(jù)沖突的BIT位按照一定的窗口大小(Wsize≥2)將標(biāo)簽ID劃分為若干子集。然后，讀寫器會將包含了沖突BIT位的掩碼發(fā)送給標(biāo)簽。標(biāo)簽收到后，按照位擴展3～8譯碼器的原理，將原始ID號連同沖突BIT位的轉(zhuǎn)換碼一起發(fā)送給讀寫器。

標(biāo)簽ID連續(xù)碰撞位算法舉例如表1所示。

表1 標(biāo)簽ID連續(xù)碰撞位算法舉例

讀寫器收到轉(zhuǎn)換碼后解析轉(zhuǎn)換碼，同時將窗口向右移動，再次將解析后的沖突BIT位連同下個窗口沖突的BIT位一起發(fā)送給標(biāo)簽；依次迭代，直到所有的沖突BIT位都被解析。至此，讀寫器所覆蓋區(qū)域的標(biāo)簽ID號識別完成。

第三步，標(biāo)簽立即發(fā)送自身的ID+擴展碼，標(biāo)簽序列號列表如表2所示。

表2 標(biāo)簽序列號列表

讀寫器將掩碼+信息碼發(fā)送到標(biāo)簽，目的是為了讓標(biāo)簽接收到讀寫器下發(fā)的指令后，匹配掩碼中對應(yīng)信息碼中比特位為1的ID位。匹配通過后，將ID發(fā)送至讀寫器；否則不發(fā)送。

擴展碼的位數(shù)(窗口大小)根據(jù)標(biāo)簽的ID及標(biāo)簽的個數(shù)確定，窗口太大會導(dǎo)致擴展碼的長度過長，影響通信效率、窗口太小就會導(dǎo)致頻繁分組，造成信道利用率不高。

標(biāo)簽序列號轉(zhuǎn)換碼列表如表3所示。根據(jù)表3將轉(zhuǎn)換碼轉(zhuǎn)變?yōu)樵a，解析出標(biāo)簽沖突的前2位信息。

表3 標(biāo)簽序列號轉(zhuǎn)換碼列表

標(biāo)簽ID沖突原碼與轉(zhuǎn)換碼的公式為:

L轉(zhuǎn)換碼= 2L原碼，L原碼≥2

(1)

D轉(zhuǎn)換碼= (1?N原碼)|D0

(2)

式中:N原碼為原碼值；D0為全零的轉(zhuǎn)換碼。

標(biāo)簽ID非連續(xù)碰撞位算法舉例如表4所示。

表4 標(biāo)簽ID非連續(xù)碰撞位算法舉例

2.2 擴展分組的防碰撞算法描述

①讀寫器置于標(biāo)簽所在的區(qū)域之后，立即發(fā)送索取標(biāo)簽ID命令111…111(長度位標(biāo)簽ID的比特位數(shù))。標(biāo)簽收到相關(guān)命令后，立即發(fā)送自身的ID給讀寫器，讀寫器收到后檢測沖突的BIT位。

②讀寫器從沖突位的高位開始取窗口的Lw的長度，發(fā)送Lw長度的掩碼DM至標(biāo)簽端。其中，Lw≤Lx≤L原碼。Dx沖突碼中前Lw個沖突位x置1，其他BIT位全部置0,得到DM掩碼。

舉例:Dx(100XXX000XXX1000XXXX11111)、D原碼(1001000000011000001111111)

當(dāng)窗口大小Lw為3時:DM(0001110000001000000000000)。

當(dāng)前讀寫器發(fā)送指令:DM1，后面的1標(biāo)志當(dāng)前為沖突位掩碼。

③標(biāo)簽收到讀寫器發(fā)送的掩碼后，立即發(fā)送自身的ID和擴展碼至讀寫器，擴展碼查表2得到。

④讀寫器收到標(biāo)簽發(fā)送的ID和擴展碼之后，判斷擴展碼的沖突碼D′X；D′X經(jīng)過譯碼得到原碼,從而判斷Dx沖突碼中前面Lw長度的碼字集合A。

A=∑dn,n≤L轉(zhuǎn)換碼

集合A中包含了所有Lw長度的標(biāo)簽沖突碼字，其中可能存在不同的標(biāo)簽發(fā)送了同一個碼字dn。

⑤讀寫器將A中碼字取出d0。因為d0是標(biāo)簽T0ID中的碼字，所以將d0最后一個BIT位X3之前的碼字取出，作為信息碼HX發(fā)送至標(biāo)簽，以此檢索標(biāo)簽T0。標(biāo)簽T0可能是一個集合，因為不同標(biāo)簽可能包含相同的頭部HX。擴展分組的防碰撞算法流程如圖6所示。

圖6 擴展分組的防碰撞算法流程圖

讀寫器發(fā)送指令DM0HX0…0。0表示當(dāng)前為信息位掩碼。DM中1的個數(shù)等于HX的長度，Hx后面補0補足ID長度。

⑥標(biāo)簽收到讀寫器在步驟⑤發(fā)送的指令后，立即反饋自己的ID給讀寫器，讀寫器檢查是否再次沖突。如果沒有沖突，直接到步驟⑧；如果再次沖突,讀寫器判斷生成最新的沖突碼序列，按照窗口大小取沖突碼的頭部，將沖突碼的頭部映射為相應(yīng)的掩碼，將掩碼DM和Hx標(biāo)簽頭碼字發(fā)送至沖突的標(biāo)簽[9-11]。

讀寫器發(fā)送指令:DM1HX

⑦標(biāo)簽收到讀寫器在步驟⑥下發(fā)的指令后，立即反饋自身的ID和擴展碼；讀寫器接收到擴展碼后進(jìn)一步解碼得到?jīng)_突位的ID集合A′，重復(fù)⑤直到最后一個標(biāo)簽沒有沖突時結(jié)束[12]。

⑨根據(jù)擴展碼解析出標(biāo)簽的ID信息，并與當(dāng)前的標(biāo)簽進(jìn)行信息交換?；氐讲襟E⑤，取出A中的元素進(jìn)行下一步查詢。

2.3 擴展分組防碰撞算法與現(xiàn)有算法的對比

擴展分組防碰撞算法是利用曼徹斯特編碼對錯誤碼的解析，通過讀寫器、標(biāo)簽兩端的協(xié)議，讓標(biāo)簽對沖突碼進(jìn)行一步步擴展，從而讓讀寫器快速識別出多標(biāo)簽ID的方法。該方法與現(xiàn)有的二進(jìn)制樹形搜索算法相比，完成所有標(biāo)簽識別的指令交互，總次數(shù)得到了明顯的壓縮。指令交互次數(shù)對比如表5所示。

表5 指令交互次數(shù)對比

該算法通過增加指令編碼的復(fù)雜度，擴展了標(biāo)簽的ID位數(shù)。當(dāng)標(biāo)簽ID個數(shù)小于沖突位窗口大小時，僅用2次完成所有標(biāo)簽的識別。當(dāng)標(biāo)簽的ID位數(shù)越長，該算法的效率越優(yōu)，彌補了二進(jìn)制樹形搜索算法由于標(biāo)簽ID過長導(dǎo)致的指令交互次數(shù)過多、時延過長的問題。

3 結(jié)論

該算法通過將多個標(biāo)簽的沖突碼按照一定的窗口大小進(jìn)行解析。解析出來的沖突碼作為分組的集合進(jìn)行分組。對已經(jīng)解析出來的沖突碼作為查詢條件進(jìn)行標(biāo)簽ID的查詢，直到檢索的標(biāo)簽沒有發(fā)生沖突為止。該算法需要在讀寫器和標(biāo)簽兩端同時實現(xiàn)，協(xié)議復(fù)雜但一次查詢可以識別出多個標(biāo)簽的ID，大大降低了讀寫器和標(biāo)簽之間的指令交互次數(shù)，節(jié)省了訪問時間，具有較高的實用價值。