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

楊斐+黃軍+陸垂偉

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

關鍵詞：卷煙物流;RFID技術;托盤標簽;防碰撞

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

0 ?引 ?言

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

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

1 ?超高頻RFID技術

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

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

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

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

2 ?RFID數據碰撞

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

2.1 ?閱讀器碰撞

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

2.2 ?標簽碰撞

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

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

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

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

時分多路法：將整個信道傳輸的信息劃分為若干時隙，其特點是時隙分配固定，適用于數字信息的傳輸。

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

3 ?防碰撞算法

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

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

3.1 ?算法改進思想

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

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

3.1.2 ?盡可能減少通信過程中傳輸的信息量。

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

3.2 ?算法實現流程

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

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

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

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

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

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

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

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

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

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

3.3 ?算法分析

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

S（N）=log2N+1

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

S'（N）=2N-1

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

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

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

4 ?結 ?語

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

參考文獻

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

[2]黃恒博.基于物聯網的配送監控系統的設計與實現[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，FENG Q. An efficient anti-collision protocol for RFID tag identification[J]. IEEE Communications letters，2010，14（11）：1014-1016

[7]郭志濤，程林林，周艷聰，等.動態幀時隙ALOHA算法的改進[J].計算機應用研究，2012，29（3）：907-909

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

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

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