楊斐+黃軍+陸垂偉

摘 要：針對(duì)卷煙物流管理系統(tǒng)中多標(biāo)簽密集產(chǎn)生的數(shù)據(jù)碰撞問題，基于二進(jìn)制樹搜索的確定性算法思想，提出一種改進(jìn)的防碰撞算法。通過減少RFID標(biāo)簽識(shí)別過程中的通信量以及遍歷節(jié)點(diǎn)的數(shù)目，提高標(biāo)簽的識(shí)別效率，從而保證了卷煙倉庫中件煙托盤的信息讀寫速度，進(jìn)一步提高了卷煙倉儲(chǔ)物流、過程監(jiān)管的技術(shù)水平。

關(guān)鍵詞：卷煙物流;RFID技術(shù);托盤標(biāo)簽;防碰撞

中圖分類號(hào)：TP301 ? ? ? ? ? ? ? ? ? ? ? ?文獻(xiàn)標(biāo)識(shí)碼：A ? ? ? ? ? 文章編號(hào)：2095-1302（2015）01-00-03

0 ?引 ?言

隨著行業(yè)流通體制改革的不斷深化和物流體系建設(shè)的快速推進(jìn)，行業(yè)物聯(lián)網(wǎng)技術(shù)的應(yīng)用取得了較大進(jìn)步和發(fā)展。國(guó)家煙草專賣局先后組織開發(fā)了行業(yè)卷煙生產(chǎn)經(jīng)營(yíng)決策管理系統(tǒng)一期二期工程、煙草商業(yè)企業(yè)數(shù)字倉儲(chǔ)管理系統(tǒng)、工商卷煙物流在途信息系統(tǒng)、煙草商業(yè)企業(yè)倉儲(chǔ)監(jiān)控系統(tǒng)等物流信息系統(tǒng)，在這些系統(tǒng)中，射頻識(shí)別技術(shù)（RFID）、全球定位系統(tǒng)（GPS）、地理信息系統(tǒng)（GIS）等物聯(lián)網(wǎng)技術(shù)得到了廣泛的運(yùn)用， 文獻(xiàn)[1]中分析了RFID技術(shù)在武漢卷煙集團(tuán)一號(hào)成品倉庫中的應(yīng)用，闡述了該倉庫的掃碼組盤和讀托盤出庫的功能。文獻(xiàn)[2]中，研究設(shè)計(jì)了漳州市煙草卷煙物流配送監(jiān)控系統(tǒng)，本著“全面感知，全程監(jiān)控”的現(xiàn)代物流建設(shè)目標(biāo)，利用RFID技術(shù)實(shí)現(xiàn)了對(duì)卷煙配送過程中人、車、物的全程監(jiān)控和智能管理?？梢?，作為物聯(lián)網(wǎng)的核心技術(shù)，RFID技術(shù)已經(jīng)廣泛應(yīng)用于我國(guó)卷煙物流管理體系中，降低了物流工作人員的勞動(dòng)強(qiáng)度，提高了企業(yè)的管理效率和運(yùn)作效率，達(dá)到了卷煙配送過程信息化、網(wǎng)絡(luò)化和可視化。

然而近年來，隨著煙草行業(yè)的蓬勃發(fā)展，卷煙市場(chǎng)也在不斷地?cái)U(kuò)大，使得卷煙倉庫進(jìn)出量大大提高，必須部署大量的讀寫器和標(biāo)簽，多個(gè)標(biāo)簽同時(shí)響應(yīng)讀寫器的查詢時(shí)會(huì)相互干擾，即數(shù)據(jù)產(chǎn)生了碰撞，導(dǎo)致讀寫器無法正確讀出標(biāo)簽數(shù)據(jù)，大大降低了物流管理系統(tǒng)的效率和穩(wěn)定性。因此，用于解決密集型 RFID 系統(tǒng)中多標(biāo)簽識(shí)別問題的防碰撞算法已成為該領(lǐng)域研究的熱點(diǎn)。

1 ?超高頻RFID技術(shù)

RFID技術(shù)是一種非接觸式自動(dòng)識(shí)別的技術(shù)，利用射頻信號(hào)和空間耦合的傳輸特性，無需機(jī)械或光學(xué)接觸即可通過無線電信號(hào)識(shí)別特定目標(biāo)并讀寫相關(guān)數(shù)據(jù)。按工作頻率可分為低頻、高頻、超高頻、微波等，由于超高頻RFID技術(shù)具有批量讀取、穿透性強(qiáng)、數(shù)據(jù)記憶容量大、抗干擾能力性強(qiáng)等優(yōu)點(diǎn)，被廣泛應(yīng)用于行業(yè)物流管理系統(tǒng)。一套完整的超高頻RFID系統(tǒng)由以下三部分組成：標(biāo)簽、閱讀器和應(yīng)用軟件[3-4]。

（l）標(biāo)簽： 是帶有線圈、天線、存儲(chǔ)器與控制系統(tǒng)的低電集成電路，其內(nèi)部存有唯一標(biāo)識(shí)編碼，貼在被識(shí)別物上，用來存儲(chǔ)物品信息并能把存儲(chǔ)的信息發(fā)射出去。

（2）閱讀器：一般包含射頻模塊、控制單元和天線。閱讀器通過天線與 RFID 標(biāo)簽進(jìn)行無線通信，可實(shí)現(xiàn)對(duì)標(biāo)簽識(shí)別碼和內(nèi)存數(shù)據(jù)的讀取和寫入，具有相當(dāng)復(fù)雜的狀態(tài)控制、奇偶校驗(yàn)與更正等功能。

（3）應(yīng)用軟件：確保閱讀器和標(biāo)簽通信的有效性和安全性，對(duì)讀取的信息進(jìn)行數(shù)據(jù)處理。

2 ?RFID數(shù)據(jù)碰撞

在卷煙物流管理系統(tǒng)中，一般采用的是體積小、功耗低的無源RFID標(biāo)簽，以托盤為單位貼簽，通過閱讀器將托盤上的件煙信息和RFID標(biāo)簽ID號(hào)綁定在一起，每個(gè)卷煙成品倉庫的托盤數(shù)量較多，標(biāo)簽密度大，且進(jìn)出庫工作頻繁，標(biāo)簽識(shí)別過程中會(huì)出現(xiàn)數(shù)據(jù)碰撞從而導(dǎo)致系統(tǒng)穩(wěn)定性下降。

2.1 ?閱讀器碰撞

當(dāng)一個(gè)有限范圍內(nèi)部署多個(gè)閱讀器時(shí)，由于閱讀器工作區(qū)域的相互重疊或者多個(gè)閱讀器使用了相同的工作頻率，會(huì)產(chǎn)生干擾從而形成了數(shù)據(jù)沖撞，稱為閱讀器碰撞。多個(gè)閱讀器之間往往可以互相通信，這種碰撞問題相對(duì)容易解決。

2.2 ?標(biāo)簽碰撞

標(biāo)簽碰撞是指多個(gè)標(biāo)簽同時(shí)發(fā)射無線信號(hào)所產(chǎn)生的信號(hào)沖突，會(huì)導(dǎo)致閱讀器無法準(zhǔn)確識(shí)別標(biāo)簽。根據(jù)標(biāo)簽類型不同，標(biāo)簽沖撞又分為有源RFID碰撞和無源RFID碰撞[5]。由于有源RFID系統(tǒng)受到了有源標(biāo)簽的成本、體積及功耗的制約，不適合應(yīng)用于物流管理中，因此無源標(biāo)簽的防碰撞問題成為了研究重點(diǎn)。

標(biāo)簽本身功能較簡(jiǎn)單、計(jì)算能力有限且不能互相通信，因此防碰撞技術(shù)主要涉及到無線電通信中的多路存取問題，一般有以下幾種[6]：

空分多路法：在分離的空間范圍內(nèi)進(jìn)行多個(gè)目標(biāo)的識(shí)別。這種方法是以犧牲硬件成本為代價(jià)的。

頻分多路法：把傳輸信道分解成若干個(gè)不同載波頻率的子信道，各子信道之間有隔離區(qū)域，使得各路信號(hào)不會(huì)互相干擾。其缺點(diǎn)是各子信道必須有單獨(dú)的接收模塊，浪費(fèi)頻譜資源，成本較高。

時(shí)分多路法：將整個(gè)信道傳輸?shù)男畔澐譃槿舾蓵r(shí)隙，其特點(diǎn)是時(shí)隙分配固定，適用于數(shù)字信息的傳輸。

碼分多路法：采用不分頻段傳輸，用編碼區(qū)分同時(shí)傳送的多路信息，能將不需要的無用信號(hào)丟棄，提取需要的有用信號(hào)。

3 ?防碰撞算法

目前，無源RFID防碰撞的研究主要是基于時(shí)分多址的，分為概率性算法和確定性算法兩大類，概率性算法中具有代表性的是動(dòng)態(tài)幀時(shí)隙ALOHA算法，確定性算法主要是二進(jìn)制樹搜索算法。國(guó)內(nèi)學(xué)者對(duì)這兩類算法進(jìn)行了一定的改進(jìn)研究，文獻(xiàn)[7]中郭志濤針對(duì)動(dòng)態(tài)幀時(shí)隙ALOHA算法提出了改進(jìn)方案，結(jié)合hash函數(shù)和三維估計(jì)方法將標(biāo)簽分配到不同的時(shí)隙，估計(jì)標(biāo)簽數(shù)并調(diào)整幀長(zhǎng)為標(biāo)簽數(shù)的1.7倍，以獲得最好的識(shí)別效果;文獻(xiàn)[8]中袁正午等人提出了一種基于堆棧存儲(chǔ)的改進(jìn)二進(jìn)制搜索算法，通過對(duì)標(biāo)簽進(jìn)行預(yù)處理以及在閱讀器中設(shè)置堆棧，有效地減少碰撞算法中的識(shí)別次數(shù)和傳輸冗余信息;文獻(xiàn)[9]中高金輝通過設(shè)置堆棧和設(shè)置標(biāo)簽內(nèi)部休眠計(jì)數(shù)器來有效地提高RFID標(biāo)簽識(shí)別效率。

根據(jù)分析得知，ALOHA算法簡(jiǎn)單，但識(shí)別碰撞的穩(wěn)定性相對(duì)較差，最高信道利用率不到50%，可以應(yīng)用在對(duì)實(shí)時(shí)性要求不高、標(biāo)簽數(shù)量較少的場(chǎng)合。二進(jìn)制樹搜索算法相對(duì)較復(fù)雜，但標(biāo)簽識(shí)別正確率較高，穩(wěn)定性強(qiáng)，在卷煙倉庫中標(biāo)簽數(shù)量較多的情況下應(yīng)優(yōu)先考慮這種算法，且算法實(shí)現(xiàn)目標(biāo)主要是縮短標(biāo)簽識(shí)別延遲時(shí)間和降低標(biāo)簽碰撞率。

3.1 ?算法改進(jìn)思想

3.1.1 ?盡可能減少標(biāo)簽識(shí)別過程中的查詢次數(shù)。

傳統(tǒng)二進(jìn)制防碰撞算法中，閱讀器每次讀取一個(gè)電子標(biāo)簽后，都會(huì)從根節(jié)點(diǎn)開始重新操作，即讀取標(biāo)簽平均查詢次數(shù)與閱讀器范圍內(nèi)電子標(biāo)簽的數(shù)量有線性關(guān)系。為了盡可能減少查詢次數(shù)，可以使閱讀器返回父節(jié)點(diǎn)進(jìn)行查詢，一定程度上可減少查詢次數(shù)。

3.1.2 ?盡可能減少通信過程中傳輸?shù)男畔⒘俊?/p>

閱讀器在發(fā)出REQUEST命令后，有效范圍內(nèi)所有的標(biāo)簽都要做出應(yīng)答。假設(shè)閱讀器在譯碼后得知有n位發(fā)生碰撞，即無法識(shí)別n個(gè)比特位信息，由于最高碰撞位之前的若干比特位總是固定的，下一次閱讀器發(fā)出REQUEST命令時(shí)只需發(fā)送最高碰撞位之前的信息以及發(fā)生的碰撞位置，電子標(biāo)簽再次響應(yīng)時(shí)也只需發(fā)送最高碰撞位后面的幾位信息，顯然可以有效減少閱讀器與標(biāo)簽的通信量，提高識(shí)別速度。

3.2 ?算法實(shí)現(xiàn)流程

改進(jìn)后的二進(jìn)制防碰撞算法的流程圖如圖1所示。

下面通過一個(gè)具體的例子來說明改進(jìn)算法識(shí)別一組標(biāo)簽的過程。

假設(shè)某讀寫器有效作用范圍內(nèi)有6個(gè)件煙托盤，每個(gè)托盤上有一個(gè)RFID標(biāo)簽，標(biāo)簽ID號(hào)分別為：11000001、11010011、11001001、11010001、11000011、11011001。閱讀器發(fā)送請(qǐng)求指令REQUEST（11111111），要求6個(gè)標(biāo)簽都作出響應(yīng)，具體步驟如下：

（l）標(biāo)簽1～6均響應(yīng)閱讀器發(fā)出的請(qǐng)求指令REQUEST（11111111），將自身的ID號(hào)發(fā)送給閱讀器。經(jīng)過曼徹斯特編碼譯碼得到110XX0X1，可以得到下一步的請(qǐng)求指令為REQUEST（00011010，0）。

（2）閱讀器發(fā)出REQUEST（00011010，0）指令，標(biāo)簽鎖定自身ID號(hào)的第1、3、4位。鎖定位中最高位為0的標(biāo)簽響應(yīng)該指令，即標(biāo)簽1、3、5響應(yīng)，返回鎖定位中的剩余位：00、10、01，閱讀器解碼結(jié)果為OXX，得到下一步的請(qǐng)求指令為REQUEST（00）。

（3）閱讀器發(fā)出REQUEST（00）指令，標(biāo)簽1、5響應(yīng)，分別返回自身的ID號(hào)為O和1，閱讀器解碼結(jié)果為00X，于是得到下一步的請(qǐng)求指令為REQUEST（000）。

（4）閱讀器發(fā)出REQUEST（000）指令，標(biāo)簽1作出響應(yīng)，無碰撞發(fā)生，閱讀器發(fā)出SELECT和READ指令對(duì)標(biāo)簽1進(jìn)行讀寫操作，接著執(zhí)行SLEEP指令，使標(biāo)簽1休眠。為減少查詢次數(shù)，采用后退策略從該節(jié)點(diǎn)的父節(jié)點(diǎn)得到下一步的請(qǐng)求指令為REQUEST（001）。

（5）閱讀器發(fā)出REQUEST（001）指令，標(biāo)簽5作出響應(yīng)，無碰撞發(fā)生，閱讀器完成對(duì)標(biāo)簽5的讀寫后，同樣執(zhí)行SLEEP命令，使之休眠。接著采用后退策略得到下一步的請(qǐng)求指令為REQUEST（01）。

（6）閱讀器發(fā)出REQUEST（01）指令，標(biāo)簽3作出響應(yīng)，無碰撞發(fā)生，同理，該標(biāo)簽完成讀寫后進(jìn)入休眠狀態(tài)，并得到下一步的請(qǐng)求指令為REQUEST（1）。

（7）閱讀器發(fā)出REQUEST（1）指令后，標(biāo)簽2、4、6作出響應(yīng)，產(chǎn)生了碰撞。同上方法將該分支內(nèi)所有產(chǎn)生碰撞的標(biāo)簽都識(shí)別出來，識(shí)別先后順序?yàn)闃?biāo)簽4、標(biāo)簽2、標(biāo)簽6，至此，整個(gè)識(shí)別過程結(jié)束。

3.3 ?算法分析

（1）假設(shè)讀寫器有效范圍內(nèi)有N個(gè)標(biāo)簽，采用傳統(tǒng)的二進(jìn)制搜索算法，從N個(gè)標(biāo)簽中識(shí)別出一個(gè)標(biāo)簽所需要的平均查詢次數(shù)S為[10]：

S（N）=log2N+1

顯然如果有兩個(gè)以上甚至更多的標(biāo)簽發(fā)生碰撞，則閱讀器重復(fù)詢問的次數(shù)將會(huì)增加很快，算法的性能也急劇下降。對(duì)于改進(jìn)的二進(jìn)制搜索算法，每次正確識(shí)別一個(gè)標(biāo)簽后可得到下一次的REQUEST指令，大大地減少了識(shí)別過程中遍歷節(jié)點(diǎn)的數(shù)目，即減少了總的查詢次數(shù)，因此平均搜索次數(shù)S'為：

S'（N）=2N-1

由公式得知，改進(jìn)的二進(jìn)制防碰撞算法中，識(shí)別單個(gè)標(biāo)簽平均只需要不到2次的查詢次數(shù)，利用后退思想降低了算法的時(shí)間復(fù)雜度，算法性能得到了很大的提高。

（2）假設(shè)標(biāo)簽ID的長(zhǎng)度為M，在傳統(tǒng)二進(jìn)制搜索算法中，REQUEST請(qǐng)求命令必須發(fā)送標(biāo)簽完整的序列號(hào)，即發(fā)送的二進(jìn)制編碼長(zhǎng)度L=M;在改進(jìn)算法中，REQUEST命令中的參數(shù)是最高碰撞位，即每次發(fā)出的二進(jìn)制編碼長(zhǎng)度L'=log2M+1，顯然減少了閱讀器與標(biāo)簽之間的通信量。

綜上分析，改進(jìn)后的二進(jìn)制防碰撞算法在多標(biāo)簽的密集環(huán)境下具有較高的識(shí)別效率，尤其適用于卷煙倉庫的物流管理系統(tǒng)，可大大提高件煙托盤的信息讀寫效率，最終有效提高卷煙倉儲(chǔ)物流、過程監(jiān)管的技術(shù)服務(wù)水平。

4 ?結(jié) ?語

本文分析了卷煙物流管理系統(tǒng)中的射頻識(shí)別技術(shù)，研究了RFID系統(tǒng)中數(shù)據(jù)碰撞問題及其解決方法。為了得到更高的標(biāo)簽識(shí)別效率，在原有二進(jìn)制搜索算法的基礎(chǔ)上提出了一種改進(jìn)算法，有效地減少了閱讀器與標(biāo)簽之間的通信量，同時(shí)減少了閱讀器的查詢次數(shù)和時(shí)間延遲。在卷煙倉庫中多標(biāo)簽密集的環(huán)境下，可大大提高件煙托盤的信息讀寫速度，使倉儲(chǔ)物流系統(tǒng)具有更強(qiáng)的穩(wěn)定性。

參考文獻(xiàn)

[1]米志強(qiáng).射頻識(shí)別技術(shù)與應(yīng)用[M].北京：電子工業(yè)出版社，2011.

[2]黃恒博.基于物聯(lián)網(wǎng)的配送監(jiān)控系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[D].廈門：廈門大學(xué)，2013.

[3] FINKEN ZELLERK. RFID Handbook[M].2nd.NewYork： Wiley，2003.

[4] WANG B S， ZHANG Q S. Study of anti-collision performance in parallelizable identification UHF RFID system[J].Journal on Communications，2009，30（6）：108-113.

[5]侯曉波，孫玲玲，錢忺.RFID二進(jìn)制防碰撞算法研究與改進(jìn)[J].杭州電子科技大學(xué)學(xué)報(bào)，2009，29（3）： 16-19.

[6] JIA X，F(xiàn)ENG Q. An efficient anti-collision protocol for RFID tag identification[J]. IEEE Communications letters，2010，14（11）：1014-1016

[7]郭志濤，程林林，周艷聰，等.動(dòng)態(tài)幀時(shí)隙ALOHA算法的改進(jìn)[J].計(jì)算機(jī)應(yīng)用研究，2012，29（3）：907-909

[8]袁正午，段莉丹.改進(jìn)的基于堆棧存儲(chǔ)的二進(jìn)制搜索算法[J].計(jì)算機(jī)應(yīng)用，2012，32（11）： 3089-3091

[9]高金輝，鄭曉彥.RFID系統(tǒng)中二進(jìn)制搜索防碰撞改進(jìn)算法[J].計(jì)算機(jī)測(cè)量與控制，2012，20（10）：2754-2756

[10]周曉光，王曉華.射頻識(shí)別（RFID）技術(shù)原理與應(yīng)用實(shí)例[M].北京：人民郵電出版社，2006.