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

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

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

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

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

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

算法基礎(chǔ)

1.1 曼徹斯特編碼

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

1.2 后退式二進(jìn)制 RFID 防沖突算法

后退式二進(jìn)制 RFID 防沖突算法識別 RFID 標(biāo)簽 的步驟如下所述。

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

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

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

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

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

1.4 定義命令

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

算法流程

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

算法的流程如下所述。

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

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

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

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

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

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

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

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

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

算法相關(guān)問題說明

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

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

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

性能分析

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

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

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

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

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

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

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

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

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

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

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

結(jié)語

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

責(zé)任編輯：ct