RFID裝備管理系統(tǒng)的防碰撞算法

楊成龍

(重慶大學，重慶 400044)

RFID 技術在裝備管理信息系統(tǒng)中的應用，必然會有多目標的識別，多目標的識別在此系統(tǒng)的延伸問題就是多標簽的識別，這是很重要的一個問題。在該管理信息系統(tǒng)中，當工作范圍內(nèi)同時出現(xiàn)了多個讀寫器和射頻標簽時，讀寫器和標簽兩種設備的任意組合產(chǎn)生的干擾，就是沖突，也稱碰撞。稱之為RFID 系統(tǒng)有了碰撞(collision)［1］。如何有效的解決RFID系統(tǒng)的碰撞這一關鍵問題?根據(jù)現(xiàn)有的研究成果，防碰撞算法是一個不錯的選擇。據(jù)通信原理可知，直接提高數(shù)據(jù)傳輸效率的方法是增大頻率帶寬，可是這個是非常有限的，所以我們只有從降低碰撞的概率入手，來提高對目標的識別。

1 碰撞算法相關理論

1.1 防碰撞

RFID 系統(tǒng)可以采用不同的算法來減少沖突。在RFID技術越來越普及的當代，很多應用場合都遭遇到碰撞問題，防碰撞技術已經(jīng)成為RFID 系統(tǒng)應用必須面臨和解決的關鍵問題。碰撞的預防就是選擇合適的射頻標簽，特別是在眾多的標簽之中準確的、快速的進行通信，不斷的選出，直至數(shù)據(jù)交流結(jié)束。

防碰撞問題主要解決的是如何快速和準確地從多個標簽中選出一個與讀寫器進行數(shù)據(jù)交流，而其他的標簽同樣可以從接下來的防碰撞循環(huán)中選出與讀寫器進行通信。

1.2 射頻識別系統(tǒng)中常見的碰撞

在射頻識別系統(tǒng)中，常見3 種碰撞形式，如圖1 所示。其中，標簽干擾和讀寫器干擾歸類于讀寫器碰撞范疇，是讀寫器相互的溝通問題。本文主要針對標簽之間的碰撞問題進行討論。

如前所述，該裝備管理系統(tǒng)中的數(shù)據(jù)碰撞問題以通信的角度理解為多路存取問題。常利用FDMA、SDMA、CDMA 以及TDMA 這4 種方法應對。建設成本的昂貴和使用環(huán)境的復雜不得不使我們更多的選擇TDMA 的方法。信道資源的高效合理利用，具體講就是通道容量和時間以及用戶間的分配問題。這也是實現(xiàn)RFID 系統(tǒng)的防碰撞的常用機制，是應用最多的一種。將TDMA 法解決標簽碰撞問題根據(jù)提供能量的不同可分為以下幾種情況(如圖2)。

圖1 RFID 系統(tǒng)中的3 種碰撞問題

圖2 時分多路標簽防碰撞算法分類

針對該平臺，選擇靈活的較為成熟的二進制搜索算法(BS)，因為標簽基本都是確定性的［2］。

2 二進制樹形搜索算法(BS)

在RFID 系統(tǒng)的ISO/IEC 標準中，在ISO 14443 標準中，TYPEA 和ISO 18000-6 標準中，TYPEB 中都可使用的是二進制樹搜索算法［3-4］。二進制樹形搜索算法(Binary Search)，以逐級的辦法將每一次沖突產(chǎn)生隔離，生2 個支脈，這屬于時間域多重訪問中的一種算法。這些支脈會越來越具體和細致，直到最后的支脈下面僅有一個單位的信息量或是沒有。這個流程是按照“First-in，Last-out”的原則［5］。算法的實現(xiàn)，必然需要相應的請求、選擇、讀數(shù)命令，在實際系統(tǒng)中，還有鑒別或?qū)懭搿⑷∠A定等命令。

BS 算法會將碰撞標簽的每一位逐步識別出來，在這之前需要讓讀寫器使用曼徹斯特編碼判斷到?jīng)_突的準確位置，見圖3。

圖4 中，閱讀器識別范圍內(nèi)有標簽1 和標簽2，標簽接受到命令后將自己的識別碼傳輸給閱讀器。圖3 中的虛線線框就是標簽沖突的位置。

下面3 個式子分別表示上述BS 算法的識別出一個目標的迭代次數(shù)為f(n)

目標全部被識別的總迭代次數(shù)為

若定義r 為非零自然數(shù)，定會有2r-1 ＜n≤2，通過式(1)、式(2)便可得出想要的總的次數(shù)

圖3 二進制樹型搜索算法示意圖

圖4 Manchester 編碼發(fā)現(xiàn)碰撞原理

為了從大量收發(fā)器中檢測出單個收發(fā)器所需要的輪回平均數(shù)為L，取決于在讀寫器檢測區(qū)中的收發(fā)器總數(shù)N，可以容易計算出

UID 有著越多的位數(shù)，顯然傳輸?shù)臅r間隨即增大，是因為傳輸時間就會增長。如每次都傳輸完整的UID，每次時間為T，則用于傳輸UID 的時間為

這也就是說交互范圍內(nèi)的電子標簽數(shù)和UID 位數(shù)是成正比的，傳輸時間的長短和防沖突運算時間也是成正比的，這也是BS 算法的傳輸時延。

3 動態(tài)二進制搜索算法(DBS)

在DBS 算法中，就像是按需分配原則。閱讀器需要的識別碼才被發(fā)送，這也是搜索的條件。而目標上的射頻標簽只呈現(xiàn)為被識別的SN。在該算法中讀寫器發(fā)生沖突后，將一樣比特碼的識別模塊回饋其互補的序列號，而后只發(fā)送合適的NVB 和相應的SNR 比特編碼。

從而，這種動態(tài)的算法極高的提高了管理的執(zhí)行效率。最主要的原因是它減少了用在序列號在系統(tǒng)中的傳送時間［7］。

4 改進的二進制算法

4.1 算法原理

首先從數(shù)學角度理解標簽的識別。設標簽UID 長度為L(標簽UID 以二進制的形式表示)。標簽j 的SN 為Ij，標簽量為n(n2≥2L)，起始指令時間為T0，休眠指令時間為T1，信道傳送周期的幀長度是T，掃描輪回的時隙數(shù)為(n2≥2L)。在時隙i 內(nèi)會有Pi個標簽能夠與讀寫器產(chǎn)生數(shù)據(jù)量:標簽j在掃描輪回內(nèi)的收發(fā)時隙為Sj，發(fā)送位為Dj，標簽UID 對M的商為Qj，標簽j 在整個數(shù)據(jù)收發(fā)輪回中的發(fā)送順序Tj，則

系統(tǒng)的性能S 為

算法主要步驟為:

1)以8 位二進制碼標簽為例，讀寫器收發(fā)REQUEST(null，8)命令，全部標簽對此命令作出應答，這些響應了的標簽將自身UID 碼傳輸;

2)當讀寫器無信號，則表示工作范圍無射頻標簽，繼續(xù)對REQUEST(null，8)命令做出應答，否則對回應信號做出判斷;

3)接著步驟2 中的閱讀器有信號的情況，通過回應信號產(chǎn)生的譯碼來判斷是否碰撞，并且經(jīng)過曼徹斯特編碼譯碼得到碰撞最高位。

4)讀寫器根據(jù)步驟3 中的判斷結(jié)果分析出沖突在哪些比特位上，讀寫器把這些沖突的比特位置顯示為“1”，無信號沖突的部分是“0”。

5)射頻標簽接受到讀寫器的REQUEST 指令，將另外幾位作為回應傳給讀寫器。若讀寫器發(fā)送SELECT 和READDATE 指令則表明沒有沖突發(fā)生，之后按圖示往下執(zhí)行。否則在進行上面的循環(huán)識別，通過不斷的譯碼，判斷出準確的比特位置，顯示高地位再次執(zhí)行REQUEST(UID)命令。

6)全部的目標被識別，識別任務完成，見圖5。

圖5 改進的二進制搜索算法流程

4.2 分析

作為一個基本的參數(shù)了解，我們需要知道單個射頻標簽的被識別的平均搜索次數(shù)［8］，以及全部目標被識別的次數(shù)分別為

設識別n 個目標標簽，讀寫器所需要的搜索次數(shù)便有S(n)，將沖突次數(shù)定為C(n)，這樣會有以下2 種情況，通過數(shù)學歸納法易證明［9-10］。

5 結(jié)束語

本文在分析BS 算法、DBS 算法的基礎上提出了一種改進的二進制搜索防碰撞算法，經(jīng)仿真實驗得知，如圖6 所示，黃色線表示的改進算法對于相同的n 值來說顯然比綠色線表示的BS 算法和DBS 算法需要的搜索次數(shù)少很對，這樣體現(xiàn)在數(shù)據(jù)傳輸效率效率上面是非?？捎^的。如果進一步規(guī)定碰撞發(fā)生的比特位數(shù)的取值分別為log2n、log2n+k/2、k 三個值，能夠更深入的得到它們的傳輸時延，以及跟隨目標個數(shù)的關系變化［9］。綜述可得下面的結(jié)論:在上述規(guī)定的條件下，從搜索識別目標的效率上來講，改進的BS 算法和DBS算法以及BS 算法是逐步降低的過程。顯而易見，搜索次數(shù)是一個很直觀的判斷，就我們想要了解的傳輸效率而言，它和傳輸時延表達改進的二進制算法、DBS 算法、BS 算法之間的關系是一致的。

圖6 搜所次數(shù)仿真

［1］游戰(zhàn)清，李蘇劍.無線射頻識別技術（RFID） 理論與應用［M］.北京:電子工業(yè)出版社，2004:105-116.

［2］譚民，曾雋芳.RFID 系統(tǒng)技術工程及應用指南［M］.北京:機械工業(yè)出版社，2007.

［3］FDIS 1443，International Standard ISO/IEC［S］.

［4］FDIS 18000-6，International Standard ISO/IEC［S］.

［5］Dekel E，Sahni S.Binary Trees and Parallel Scheduling Algorithms［J］. Computer IEEE Transactions on，1983（C-32）:307-315.

［6］薛雷，李德華，關景火.基于分布式動態(tài)優(yōu)先權隊列實時可調(diào)的MAC 協(xié)議［J］.通信學報，2003，24（5）:65-71.

［7］LEONG K S，NG M L，COLE P H. The reader collision problem in RFID systems［C］//In Proceedings of IEEE MAPE.Beijing:［s.n.］，2005（1）:658-661.

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

［9］姚勇，虞陽.RFID 防碰撞算法研究與仿真［D］.長沙:湖南大學，2010.

［10］Chriser Ericson.實時碰撞檢測算法技術［M］. 劉天慧，譯.北京:清華大學出版社，2010.