基于標簽序列號擴展分組的防碰撞算法

王博文

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

0 引言

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

防碰撞算法能夠將讀寫器覆蓋區域的標簽ID區分開來，使讀寫器能準確地識別標簽。所以，防碰撞算法也是RFID標簽識別研究的重點。現有的RFID防碰撞算法大致分為以下幾類:美國夏威夷研究計劃高等算術高級學習(advanced learning on higher arithmetic,ALOHA)算法、時隙ALOHA算法、動態時隙ALOHA算法、二進制樹形搜索算法。總體來說，ALOHA算法是一種非確定的方法，由電子標簽控制發送時間[3]。而二進制樹形搜索算法由讀寫器來控制標簽發送時間，是一種確定的方法。

1 現有的防碰撞算法

1.1 ALOHA算法

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

圖1 純ALOHA算法標簽信息沖突示意圖

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

圖2 時隙ALOHA算法標簽信息沖突示意圖

1.2 基于曼徹斯特編碼的二進制樹形搜索算法

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

圖3 曼徹斯特編碼示意圖

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

圖4 基于曼徹斯特編碼的標簽信息碰撞容錯圖

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

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

圖5 基于二叉樹模型的標簽沖突子集圖

1.3 幾種算法的評析

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

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

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

2 基于標簽序列號擴展分組的防碰撞算法

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

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

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

標簽ID連續碰撞位算法舉例如表1所示。

表1 標簽ID連續碰撞位算法舉例

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

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

表2 標簽序列號列表

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

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

標簽序列號轉換碼列表如表3所示。根據表3將轉換碼轉變為原碼，解析出標簽沖突的前2位信息。

表3 標簽序列號轉換碼列表

標簽ID沖突原碼與轉換碼的公式為:

L轉換碼= 2L原碼，L原碼≥2

(1)

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

(2)

式中:N原碼為原碼值；D0為全零的轉換碼。

標簽ID非連續碰撞位算法舉例如表4所示。

表4 標簽ID非連續碰撞位算法舉例

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

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

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

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

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

當前讀寫器發送指令:DM1，后面的1標志當前為沖突位掩碼。

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

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

A=∑dn,n≤L轉換碼

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

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

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

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

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

讀寫器發送指令:DM1HX

⑦標簽收到讀寫器在步驟⑥下發的指令后，立即反饋自身的ID和擴展碼；讀寫器接收到擴展碼后進一步解碼得到沖突位的ID集合A′，重復⑤直到最后一個標簽沒有沖突時結束[12]。

⑨根據擴展碼解析出標簽的ID信息，并與當前的標簽進行信息交換。回到步驟⑤，取出A中的元素進行下一步查詢。

2.3 擴展分組防碰撞算法與現有算法的對比

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

表5 指令交互次數對比

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

3 結論

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