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

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

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

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

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

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

算法基礎(chǔ)

1.1 曼徹斯特編碼

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

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

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

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

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

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

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

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

1.4 定義命令

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

算法流程

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

算法的流程如下所述。

1）RFID 讀寫器向可讀標(biāo)簽發(fā)送同步信號(hào)，標(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)入哪個(gè)分類，由哪個(gè)線程進(jìn)行處理。例如，可 用最高沖突位 D6 與次高沖突位 D5 對(duì)標(biāo)簽進(jìn)行分類， 共分為 4 類，每類對(duì)應(yīng)進(jìn)入相應(yīng)的線程中進(jìn)行下一步 處理，詳細(xì)分類情況見(jiàn)表 2。下面以線程 1 的流程說(shuō) 明算法的整個(gè)流程。

3）RFID 讀寫器發(fā)送 Request（011，0，00）。其 中，參數(shù)“011”表示標(biāo)簽的最高沖突位為 D3 位;參數(shù) “0”表示將最高沖突位置“0”;參數(shù)“00”表示上述標(biāo)簽 所屬線程的標(biāo)號(hà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 返回的疊 加后的信息“？？”，說(shuō)明仍在 D1 與 D0 位存在沖突。 將 Request（011，0，00）命令入棧。

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

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

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

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

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

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

算法相關(guān)問(wèn)題說(shuō)明

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

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

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

性能分析

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

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

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

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

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

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

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

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

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

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

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

結(jié)語(yǔ)

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

責(zé)任編輯：ct