卷煙物流管理中超高頻RFID防碰撞技術(shù)研究

楊斐+黃軍+陸垂偉

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

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

中圖分類號：TP301 ? ? ? ? ? ? ? ? ? ? ? ?文獻標識碼：A ? ? ? ? ? 文章編號：2095-1302（2015）01-00-03

0 ?引 ?言

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

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

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

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

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

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

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

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

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

2.1 ?閱讀器碰撞

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

2.2 ?標簽碰撞

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

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

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

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

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

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

3 ?防碰撞算法

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

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

3.1 ?算法改進思想

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

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

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

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

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

改進后的二進制防碰撞算法的流程圖如圖1所示。

下面通過一個具體的例子來說明改進算法識別一組標簽的過程。

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

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

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

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

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

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

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

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

3.3 ?算法分析

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

S（N）=log2N+1

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

S'（N）=2N-1

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

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

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

4 ?結(jié) ?語

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

參考文獻

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

[2]黃恒博.基于物聯(lián)網(wǎng)的配送監(jiān)控系統(tǒng)的設計與實現(xiàn)[D].廈門：廈門大學，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].杭州電子科技大學學報，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]郭志濤，程林林，周艷聰，等.動態(tài)幀時隙ALOHA算法的改進[J].計算機應用研究，2012，29（3）：907-909

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

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

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