目的 解決現階段包裝箱管理過程中 RFID 標簽沖突的問題。方法 在分析已有的解決標簽沖突算法的基礎上，采用多線程技術、后退式二進制防沖突算法和優化的數據結構等方法，設計并實現一種新 的防沖突算法。RFID 讀寫器發送一個三元組命令，RFID 標簽應答沖突位的信息，減少數據傳輸量;采 用堆棧存儲 RFID 讀寫器發送的命令，減少識別沖突的次數;利用多線程處理思想，對標簽進行分類處 理，縮短沖突處理的時間。

結果 經過仿真分析，這種并發執行的后退式二進制 RFID 防沖突算法效率 可提高約 51%。

結論 該算法解決了 RFID 標簽沖突，提高了多標簽情況下的讀寫效率，很好地解決了包裝箱管理系統中 RFID 標簽的功能和性能的問題。

在現代物流運輸中，射頻識別技術（RFID）被廣泛應用于包裝箱管理。RFID 技術的使用可以對包裝箱的裝箱、運輸、入庫和儲存等各個物流環節進 行跟蹤，實現包裝箱的實時監控和管理。RFID 可 以無接觸采集數據，是一種自動識別的通信技術。 這種技術可以通過電磁波雙向傳輸數據實現數據的 通信。RFID 標簽、RFID 讀寫器和中央信息處理器組 成了 RFID 系統，其中 RFID 標簽可以粘貼在包裝箱上，可存儲包裝箱的具體信息，RFID 標簽具有唯一 的編碼，該編碼可以作為包裝箱的唯一標識;RFID 讀寫器可以對包裝箱上的 RFID 標簽進行更改、寫入 和讀取，將讀取的 RFID 標簽存儲信息傳輸到中央處 理器;中央處理器可以對讀取的 RFID 標簽信息進行 分析處理，實現對包裝箱的管理。

RFID 包裝箱技術存在多個 RFID 標簽信息沖突 的問題。RFID 讀寫器向有效范圍的 RFID 標簽發出通信請求信號，所有包裝箱上的 RFID 標簽會同時返 回標簽信息至 RFID 讀寫器。RFID 標簽的通信使用 共享的通信信道，因此多個 RFID 標簽信息在同一信 道中產生沖突。如何在避免沖突的條件下快速、正確 地讀出 RFID 標簽信息，并高效地利用通信信道，是 RFID 應用在包裝系統中主要需要研究和解決的問題 之一。

對于 RFID 系統中的信息沖突問題，一般采用時 分多址（TDMA）的技術來解決。基于樹的算法和基 于 ALOHA 的算法是時分多址的兩類主要算法［7—10］。 基于 ALOHA 算法的主要思想是發現沖突后，重新產 生識別標簽。當標簽數量增加，沖突則呈線性增長， 系統性能急劇下降。基于樹的算法是一類確定性算 法，例如查詢樹算法（QTA），二進制搜索算法（BAS） 等［11—14］。QTA 算法需傳輸并檢驗標簽前綴，信息處 理速度較慢。BAS 算法的主要思想是將讀入的信息生 成 2 個不相交的子集，循環處理，直到子集中只有唯 一可識別的標簽。當標簽數量增大，也會產生大量標 簽的沖突，使系統效率降低。后退式二進制算法以 BAS 算法為基礎，采用棧和后退原則減少冗余，提高 系統的工作效率。以上 2 種算法雖然可以解決多個包 裝箱 RFID 標簽的傳輸沖突問題，但隨著同時讀取包 裝箱數量的增多，傳輸和處理的數據量也隨之大量增 加。為了解決沖突和效率的問題，這里將提出并發執 行的后退式二進制 RFID 防沖突算法。

算法基礎

1.1 曼徹斯特編碼

多個同時讀取的 RFID 標簽信息在共享信道中產 生沖突，首先應找到沖突產生的位置，曼徹斯特編碼則 是確定沖突位置的基礎編碼方式。曼徹斯特編碼采用在 一位傳輸周期中的電平跳變規則，正跳變為 0，負跳變 為 1。例如有 2 個 RFID 標簽（8 bit），信息分別為 10010111（標簽 TagB）和 10110011（標簽 TagA）。這 2 個標簽在共享信道中同時被 RFID 讀寫器讀出，則讀 出的信息為 10X10X11（其中 X 為無電平）。由于 TagA 和 TagB 的第 2 位和第 5 位相反，上升和下降電平相互 抵消，可以說明第 2 位和第 5 位產生沖突，見圖 1。

1.2 后退式二進制 RFID 防沖突算法

后退式二進制 RFID 防沖突算法識別 RFID 標簽 的步驟如下所述。

1）RFID 讀寫器廣播發送同步信號及請求命令， 將此命令入棧，便于下次命令的確定。各標簽響應請 求，并判斷自己的 ID 是否小于等于 S，S 為 RFID 讀 寫器的參數，表示該讀寫器能夠讀取的 RFID 標簽的 最大長度。如果小于等于 S，則返回自身 ID。

2）讀寫器根據讀回的信息，判斷是否有標簽產 生沖突，如果沒有沖突，轉到步驟 3）;如果有沖突， 將讀回的序列的最高沖突位置“0”，其余沖突位置 “1”，不沖突位保持讀回序列的原狀態。將修改后的 序列賦值給 S，返回步驟 1）。

3）如沒有沖突，證明已識別出一個 RFID 標簽 的 ID，可對此標簽執行操作。從棧中取出請求命令， 確定下次命令的參數，返回步驟 1）。

1.3 并發執行

并發執行主要采用多線程技術實現，多線程技術 可以同步運行多個獨立的程序片段，這種并行可以提 高系統的效率。RFID 中央處理器可以采用多核處理 器，采用多線程的編程方法，對 BAS 算法中生成的 2 個不相交的自己進行同步處理，既解決了沖突問題， 又解決了效率問題。

1.4 定義命令

為方便對算法進行描述，在不改變原 RFID 系統 命令的前提下，定義請求命令 Request（D，m，T） 和應答命令 Response（s）。其中 Request 命令中的 D 參數為沖突最高位的編號（設 RFID 為 8 位 ID，D 為 3 位二進制數，如 110 表示沖突的最高位為 D6 位）， m 為沖突位的參數（0/1），T 為線程編號（4 線程，2 位二進制表示 00，01，10，11 這 4 個線程的編號）。

算法流程

假設 RFID 標簽編碼為 16 位二進制數，現有 20 個待識別的標簽，見表 1。改進算法采用 4 個線程處 理該算法，樹中結點表示根據最高沖突位發出的不同 請求命令。

算法的流程如下所述。

1）RFID 讀寫器向可讀標簽發送同步信號，標簽 返回自身 ID。RFID 讀回 1？？1？0？？的二進制序列，判 斷 D6，D5，D3，D1，D0 發生沖突。RFID 讀寫器將 產生沖突的位置發送給 RFID 標簽。

2）根據最高沖突位和次高沖突位進行分類， RFID 標簽根據自身 ID 的序列和產生沖突的位置，判 斷應進入哪個分類，由哪個線程進行處理。例如，可 用最高沖突位 D6 與次高沖突位 D5 對標簽進行分類， 共分為 4 類，每類對應進入相應的線程中進行下一步 處理，詳細分類情況見表 2。下面以線程 1 的流程說 明算法的整個流程。

3）RFID 讀寫器發送 Request（011，0，00）。其 中，參數“011”表示標簽的最高沖突位為 D3 位;參數 “0”表示將最高沖突位置“0”;參數“00”表示上述標簽 所屬線程的標號為“00”，即線程 1。滿足上述條件的 RFID 標簽（Tag1，Tag11）返回信息，發送命令 Response（D1D0），D1D0 為其余沖突位的標簽信息，即 Tag1 發送 Response（01），Tag11 發送 Response （10）。RFID 讀寫器就收到 Tag1 與 Tag11 返回的疊 加后的信息“？？”，說明仍在 D1 與 D0 位存在沖突。 將 Request（011，0，00）命令入棧。

4）RFID 讀寫器發送 Request（001，0，00），此 時滿足其條件的標簽只有 Tag1，該標簽發送命令 Response（1）。RFID 讀寫器收到“1”的信息，表示此 時無沖突，表示識別了一個標簽（Tag1）。Request （001，0，00）命令入棧。

5）執行出棧，出棧的命令為 Request（001，0， 00），將第 2 個參數“0”改為“1”。RFID 讀寫器發送 Request（001，1，00），此時滿足其條件的標簽只有 Tag11，該標簽發送命令 Response（0）。RFID 讀寫器 收到“0”的信息，表示此時無沖突，并識別了一個標 簽（Tag11）。

6）執行出棧，出棧的命令為 Request（011，0， 00），將第 2 個參數“0”改為“1”。RFID 讀寫器發送 Request（011，1，00），此時滿足其條件的標簽有 Tag4， Tag6 和 Tag8，標簽分別發送命令 Response（01）， Response（00）和 Response（10）。RFID 讀寫器收到 “？？”的信息，表示 D1 和 D0 存在沖突。

7）RFID 讀寫器發送 Request（010，0，00），此 時滿足其條件的標簽有 Tag4，Tag6，標簽分別發送 命令 Response（1）和 Response（0）。RFID 讀寫器 收到“？”，表示 D0 位存在沖突。此時只有一位沖突， 表示 D0 位可有 2 種取值，識別了 2 個標簽（Tag4， Tag6）。Request（010，0，00）命令入棧。

8）執行出棧，出棧的命令為 Request（010，0， 00），將第 2 個參數“0”改為“1”。RFID 讀寫器發送 Request（010，1，00），此時滿足其條件的標簽有 Tag8， 標簽發送命令 Response（0）。RFID 讀寫器收到“0” 的信息，表示此時無沖突，識別了一個標簽（Tag8）。

9）棧為空，該線程結束。 線程 2、線程 3、線程 4 也采取同樣的處理方式。

算法相關問題說明

1）Request 命令入命令棧。由于算法中對樹的操作是從左至右，所以按照命令中的 m 參數值確定是 否命令入棧，m 為“0”入棧，為“1”不入棧。

2）出命令棧。由算法中的后退原則，識別出標 簽后，應后退查找樹的結點。此時可執行出棧操作， 并將出棧命令中的 m 由“0”置“1”，再執行下次搜索。

3）多線程處理。如果 RFID 讀寫器是多頻的， 并且 CPU 是多核處理器，則該多線程為“并行處理”; 如 RFID 是單頻的，則需增加一個命令隊列，暫時存 儲同時發出的 Request 命令，此時為“多線程處理”， 可利用 RFID 讀寫器在處理信息的同時，讀寫 RFID標簽內容。這 2 種方式都可提高系統的效率。

性能分析

4.1 BAS、后退式 BAS 和并發式 BAS 算法比較

評估 RFID 系統防沖突算法的好壞，要看算法搜索 完所有標簽需要的查詢次數和識別的時間。設 RFID 標 簽數量為 N，RFID 標簽的編碼長度為 L，則 BAS 算法 中 RFID 標簽的編碼長度為 L;后退式 BAS 算法中， RFID 標簽的編碼長度為 log2 L+1;在該算法 Request 命令中，D 的長度與編碼長度有關，為 log2 L，m 為 1 位，T 與線程的數目（NT）有關，為 log2 NT。在該算法 中發送的二進制編碼長度為 log2 L+1+log2 NT。

BAS 算法中，需循環搜索 RFID 標簽，因此識別 數量為 N 的標簽查詢次數為 N（N+1）/2;后退式 BAS 算法識別數量為 N 的標簽需要的查詢次數為 2N?1; 文中算法采用并發執行后退式 BAS，每個線程平均查 詢次數為（2N?1）/NT。

BAS、后退式 BAS、并發處理 BAS 算法的傳輸 二進制數據長度分別為 N（N+1）/2 L， （ 2N? 1 ） × （log2 L+1），［（2N?1）/NT］×（log2 L+1+NT）。

以表 1 的 20 個標簽為樣本，比較 BAS、后退式 BAS 和并發執行 BAS 算法的性能，比較指標見表 3。 隨著標簽數量、編碼位數以及并發數的增加，文中算 法的優勢將越來越明顯。對后退式 BAS 和并發執行 BAS 算法進行 Matlab 仿真，對 RFID 標簽的編碼為 8 位、64 位，線程數為 4 和 8 的 2 種算法的吞吐量進 行了比較，見圖 2。

可以看出，新算法發送命令次數和數據量都大幅 度減少，分析其原因應有以下兩點：后退方式減少了 命令的發送;命令的參數不是 RFID 標簽的全部 ID， 而是沖突的位置及數值。當標簽的 ID 位數越多，會 越明顯。

各算法的執行時間比較見表 4。其中 RFID 讀寫 器發送 1 bit 數據時間為 t1，RFID 標簽應答 1 bit 數據 時間為 t2，RFID 進行沖突處理 1 bit 數據時間為 t3。 由表 4 可以看出，改進算法在速度上也得到了提高， 分析其原因應有以下 3 點：并發執行處理，使沖突處理時間減少;命令傳輸的數據減少，識別數據的時間 減少;處理沖突可與命令傳輸多線程處理，提高了運 行的速度。

4.2 并發執行 BAS 算法與其他算法的效率比較

算法的系統效率是比較算法好壞的標準之一，因 此對 ALOHA 算法、QTA 算法和 BAS 算法進行系統 效率的比較。ALOHA 算法的思想是發現沖突后，重 新產生識別標簽，當標簽數量增加，沖突則呈線性增 長，系統性能急劇下降。QTA 算法需傳輸并檢驗標 簽前綴，信息處理速度較慢。BAS 算法的思想是將讀 入的信息生成 2 個不相交的子集，循環處理，直到子集中只有唯一可識別的標簽。

算法的系統效率定義如下：系統效率=（發送成 功的標簽信號/發送總標簽信號）×100%。

這幾種算法的效率比較曲線見圖 3。可以看出， ALOHA 算法的效率最低，隨著閱讀器數目的增多，沖突也隨之增加，當閱讀器數量達到 64 時，ALOHA 算 法的系統效率幾乎為 0;QTA 算法雖然很好地避免了節 點的沖突，但由于需要檢查標簽的前綴，當閱讀器數目 達到 64 時，系統效率約為 40%;BAS 算法將讀入的信 息分成 2 個不相交的子集，但單線程會造成系統空閑， 當閱讀器數目達到 64 時，系統效率約為 67%;文中算法是在 BAS 算法的基礎上，引入多線程后退式技術， 使系統效率一直保持在 90%左右。

結語

提出了并發執行的后退式防沖突算法，減少了命令傳輸數據的數量，縮短了讀寫器的識別時間，提高了包裝系統的處理速度。并發執行的后退式防沖突算法融合了BAS 算法思想，將讀入的信息生成 2 個不相交的子集，循環處理，直到子集中只有唯一可識別的標簽;進一步采用了多線程并發技術，對BAS 算法中系統空閑時間進行有效的利用，提高了系統的工作效率。性能分析表明，該算法優于 BAS 算法和后退式 BAS 算法，更適用于包裝標簽 ID 長、標簽數量大的情況。

責任編輯：ct