RFID包裝系統(tǒng)怎樣防止沖突

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

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

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

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

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

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

算法基礎

1.1 曼徹斯特編碼

多個同時讀取的 RFID 標簽信息在共享信道中產 生沖突，首先應找到沖突產生的位置，曼徹斯特編碼則 是確定沖突位置的基礎編碼方式。曼徹斯特編碼采用在 一位傳輸周期中的電平跳變規(guī)則，正跳變?yōu)?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 讀寫器廣播發(fā)送同步信號及請求命令， 將此命令入棧，便于下次命令的確定。各標簽響應請 求，并判斷自己的 ID 是否小于等于 S，S 為 RFID 讀 寫器的參數(shù)，表示該讀寫器能夠讀取的 RFID 標簽的 最大長度。如果小于等于 S，則返回自身 ID。

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

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

1.3 并發(fā)執(zhí)行

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

1.4 定義命令

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

算法流程

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

算法的流程如下所述。

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

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

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

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

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

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

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

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

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

算法相關問題說明

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

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

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

性能分析

4.1 BAS、后退式 BAS 和并發(fā)式 BAS 算法比較

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

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

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

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

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

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

4.2 并發(fā)執(zhí)行 BAS 算法與其他算法的效率比較

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

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

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

結語

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

責任編輯：ct