基于標簽信息分組的射頻識別防碰撞算法*

李波

(華南理工大學電子與信息學院，廣東廣州510640)

射頻識別(RFID)技術作為一種新的自動識別技術，以其快速、實時、準確采集的特點在眾多領域得到廣泛應用［1-2］.RFID系統(tǒng)主要由閱讀器、標簽和數(shù)據處理3部分組成，其中閱讀器和標簽之間采用非接觸工作方式交互信息.在RFID系統(tǒng)中標簽有3種類型:主動、被動和半主動［3-5］.文中主要討論被動類型的標簽.被動標簽本身是無源的，其工作所需的能量是靠閱讀器傳輸給它的［2］，且標簽之間不能交互，多個標簽同時發(fā)送數(shù)據會導致閱讀器讀取數(shù)據沖突.防碰撞算法就是用來避免這種情況的發(fā)生、協(xié)調標簽之間順序工作的.目前主要有兩種防碰撞算法:二叉樹算法和ALOHA算法［6-7］.

ALOHA算法是標簽在每個時隙開始時競爭信道，競爭到信道的標簽發(fā)送數(shù)據，沒有競爭到的會隨機地等待一段時間后再次競爭信道［5，8］.Deng等［9］提出一種可以自適應調整時隙的算法，該算法能夠根據未識別的標簽數(shù)量調整時隙的數(shù)量，使得識別吞吐量達到最大值.二叉樹算法中，閱讀器通過要求標簽不斷地選擇0和1來使標簽有序地發(fā)送數(shù)據.這兩種算法雖然能解決標簽的沖突問題，但交互過程過多，且隨機性很強，當標簽數(shù)量較多時，識別效率會嚴重下降［1，5，8，10-11］.鄧輝舫等［12］對二叉樹算法進行了改進，使算法保持后退式二進制樹形搜索算法的后退機理，實現(xiàn)標簽的有序讀取.在這兩種算法的基礎上，Wang等［13］提出了一種基于ALOHA的分組識別算法.該算法先利用循環(huán)過程來預識別所有的標簽，然后將所要識別的標簽進行分組，分組結束后再利用ALOHA算法識別各組中的標簽.

為減少可讀取標簽的數(shù)量并自適應地改變標簽應答時隙的數(shù)量以提高系統(tǒng)的識別效率，文中依據概率統(tǒng)計理論和代數(shù)理論提出了基于標簽信息分組的防碰撞算法.

1 算法描述

電子標簽是識別對象的數(shù)據承載體，存儲識別對象和標簽的信息，并在數(shù)據寫入標簽后對這些數(shù)據序列生成一個循環(huán)冗余校驗(CRC)碼，用于在數(shù)據通信中校驗序列［14］.分組識別算法就是以標簽的CRC碼作為分組依據.算法中利用這些已生成的CRC碼再生成更低位的CRC碼值作為每個標簽的組號，而每個組中的標簽以自身的標簽序號作為隨機算法的種子，生成隨機數(shù)并作為它占用的時隙序號，其中每個組的時隙總數(shù)為2l，l為標簽序號的位數(shù).然后，閱讀器按照分組順序依次識別這些標簽，在組內按照標簽所選擇的時隙號依次讀取數(shù)據.

1.1 標簽狀態(tài)的遷移

標簽在識別的過程中處于不同的狀態(tài)，根據閱讀器的請求命令從一個狀態(tài)遷移到另一個狀態(tài).文中算法定義了標簽在識別過程中的5種狀態(tài):

(1)激活狀態(tài)標簽選擇了一個時隙，正在與閱讀器進行交互.

(2)休眠狀態(tài)標簽已選擇了時隙，在等待閱讀器的喚醒請求.

(3)已識別狀態(tài)標簽已被成功讀取，處于該狀態(tài)的標簽不再響應任何閱讀器命令.

(4)等待狀態(tài)處于該狀態(tài)的標簽表示該標簽所在的組還沒有被閱讀器選中并進行識別，在等待閱讀器的REQ-Start請求.

(5)沖突狀態(tài)當標簽所選擇的時隙與其它標簽相同時所具有的狀態(tài).

標簽狀態(tài)遷移過程如圖1所示.所有的標簽在識別開始時全部處于激活狀態(tài)，分組結束后，沒有被選擇識別的組遷移到等待狀態(tài)，而被選中的標簽組則保持激活狀態(tài)，完成時隙選擇后遷移到休眠狀態(tài)，直到閱讀器喚醒標簽開始識別.所有沖突的標簽在一次輪詢識別結束后響應閱讀器的請求返回激活狀態(tài)，重新開始選擇時隙，直到被成功讀取，響應REQ_Kill請求遷移到已識別狀態(tài).其它保持等待狀態(tài)的標簽要在被識別的組中的所有標簽都遷移到已識別狀態(tài)后，才會被閱讀器喚醒.

圖1 標簽狀態(tài)遷移示意圖Fig.1 Schematic diagram of state transition of tag

1.2 標簽分組與時隙選擇

現(xiàn)有的RFID標準中一般采用16位的CRC碼作為校驗碼，故文中以16位CRC為例進行討論.當閱讀器檢測到有新標簽進入其射頻場后，先鎖定標簽，并在后續(xù)識別過程中只識別這些鎖定的標簽，防止有新的標簽進入時擾亂正在進行的識別過程.標簽收到開始識別的請求后，提取自身的16位CRC碼值，采用模2除法去除4位CRC碼，生成多項式G(x)=x4+x+1［15］，并求得4位CRC碼，這樣每個標簽所在組即被唯一確定.4位CRC碼值可表示的范圍是0～15，所以所有的標簽被分配到16個組中.

在識別過程中每個組有2n(2≤n≤l/2)個時隙供標簽進行選擇，其中n的值取決于每次輪詢結束后沖突時隙、空時隙和成功讀取時隙的統(tǒng)計結果.標簽采用偽隨機數(shù)生成(PRNG)算法生成一個隨機數(shù)作為該標簽選擇的時隙號碼.但要求RNG生成的隨機數(shù)序列是均勻分布的，以保證標簽不會過度集中地選擇某個時隙.線性同余算法是一種簡單可行的隨機數(shù)生成算法，在參數(shù)正確設置的前提下，它所產生的隨機序列分布均勻，其形式如下:

式中:r為隨機數(shù);I為隨機算法的種子;λ為整數(shù)乘子;c為整數(shù)常量;m為每次輪詢的時隙總數(shù)，m=2n.由文獻［16-19］可知，式(1)中的參數(shù)按如下設置時所產生的隨機序列具有很好的分布性:(a)λ和m互為質數(shù);(b)如果λ-1是質數(shù)p的倍數(shù)，那么p是λ-1和m的公約數(shù).

由于標簽采用線性同余的方法產生一個隨機數(shù)作為時隙號碼，而不是產生一個序列，因此種子I決定了每組中標簽選擇時隙的分布情況.從式(1)可知，當兩個標簽選擇的種子相同時，生成的時隙號碼是相同的.文中采用標簽序號作為隨機算法的種子源，其中s表示種子位數(shù)，s等于本次輪詢時隙總數(shù)2n的冪，則取種子步驟如下:

1)第1次輪詢時，直接取標簽序號的后s位作為種子;

2)在第k次輪詢時，按順序從后向前取k串s位的子串，將這k串子串的異或值作為種子;

3)若k-1，則按第1次輪詢時的方法取種子.

1.3 輪詢識別過程

閱讀器中設置3個計數(shù)器，分別記錄沒有被選中的時隙(es計數(shù)器)、成功讀取的時隙(ss計數(shù)器)、發(fā)生沖突的時隙(cs計數(shù)器).在輪詢之前，3個計數(shù)器均初始化為0，當一次輪詢結束后，閱讀器可以根據這3個計數(shù)器的情況判斷是否將當前組內的標簽讀取完畢，以及是否調整下一輪輪詢中標簽的可選擇時隙范圍.

在標簽選擇完時隙后，閱讀器開始對這一組的2n個時隙進行輪詢識別.當有標簽選擇的時隙與其它標簽相同時，碰撞就會發(fā)生，此時閱讀器不作處理，繼續(xù)識別后面的時隙.所有2n個時隙識別完畢后，若有碰撞發(fā)生，則請求標簽重新計算種子，然后開始下一次輪詢.一次輪詢算法的步驟如下:

1)發(fā)送REQ_Query請求，其中包括閱讀器所要讀取的時隙號碼.

2)如果收到ACK_Query響應且沒有沖突發(fā)生，則讀取成功，轉步驟3);如果收到ACK_Query響應且有沖突發(fā)生，則轉步驟4);如果沒有任何響應，表明該時隙沒有標簽被選中，則es計數(shù)器(空時隙計數(shù)器)加1，轉步驟5).

3)發(fā)送REQ_Kill請求，將被成功讀取的標簽鎖死，ss計數(shù)器(獨占時隙計數(shù)器)加1，轉步驟5).

4)cs計數(shù)器(沖突時隙計數(shù)器)加1.

5)閱讀器中時隙計數(shù)器加1，準備讀取下一個時隙，返回步驟1).

一次輪詢識別結束后，閱讀器根據3個計數(shù)器的結果進行估計判定，調整時隙總數(shù)，然后讀取該組剩下的標簽，判定準則如下:

1)如果cs計數(shù)器為0，則表示當前這一組所有標簽讀取完畢，準備讀取下一組標簽.

2)如果cs計數(shù)器不為0，有以下2種情況，其中r表示上一次輪詢的時隙總數(shù).

(a)當es=0時，若cs＞ss，則表明沖突嚴重，若n=32則時隙總數(shù)保持不變，否則在下一次輪詢時時隙總數(shù)設為2n+1;若cs≤r/2，則時隙總數(shù)保持不變.

(b)當es≠0時，若cs＞es+ss，則時隙總數(shù)保持不變;若cs≤r/2且n=2，則時隙總數(shù)保持不變，否則時隙總數(shù)設為2n-1.

算法分組過程如圖2所示.兩種準則分別根據碰撞情況調整時隙總數(shù)，從而提高系統(tǒng)的識別效率.

圖2 分組示意圖Fig.2 Schematic diagram of splitting

2 算法分析

文中算法最關鍵的兩個步驟是標簽分組和時隙選擇，因為算法是基于標簽自身攜帶的信息進行劃分的，而所有的信息是不可預知的，那么所有的標簽是否可以利用CRC碼進行分組?在每個小組中標簽是采用線性同余法選擇時隙，是否會出現(xiàn)某個時隙無限重復被選的情況?文中分別討論這兩個問題.

2.1 分組效率問題

文中討論分組識別算法時，以標簽中攜帶16位CRC碼為例，利用生成多項式G(x)=x4+x+1產生4位CRC碼.

隨機均勻地產生t個標簽，令X1，X2，…，Xt分別表示它們所攜帶的16位CRC碼，則Xi∈{0，1，…，216-1}，i=1，2，…，t，且Xi以等概率取值.令RXi表示Xi對G(x)求模取得的余數(shù)，則RXi∈{0，1，…，24-1}，且以等概率取值.在算法中，RXi是各個標簽的分組號，因此各個標簽被分配到16個組中，且被分配到其中一個組的概率相同.可見文中算法可以將所要識別的標簽相對均勻地分配到16個組中.

分組過程是在標簽接收到閱讀器的分組命令后開始的.所有的標簽接收到閱讀器的分組命令后，同時開始進行除法運算產生分組號，因此所有標簽的分組過程所消耗的時間等于一個標簽進行除法運算的時間，即分組過程的算法復雜度相當于一次除法運算的算法復雜度.求取CRC的移位除法運算的復雜度為O(d)，即分組過程的復雜度為O(d)［15］，其中d為被除數(shù)的位數(shù)，在分組過程中用16位CRC產生4位CRC碼，因此d為16.

2.2 時隙分配問題

由式(1)可知，若參數(shù)確定，線性同余算法產生的隨機數(shù)是由種子I確定的，并且若I是周期m內的一個整數(shù)，那么產生的隨機數(shù)是由種子唯一確定的.也就是說，假如一個標簽采用的種子與其它標簽不同，則該標簽占用的時隙也與其它標簽不同.假設第k次輪詢時種子位數(shù)為s位，那么第k次輪詢的種子是標簽序號中從后向前取k個s位長的子串的異或值.

設X1和X2分別表示同一組中任意兩個標簽的l位長的序號(由0、1組成的混合序列)，且X1≠X2，S1和S2分別是它們的種子，位數(shù)為s.設這兩個標簽的序號具有以下形式:

其中“×”表示一個s位子串，共有?l/s」個子串.X1中第i-1和i個子串分別是a和b，X2中第i-1和i個子串分別是c和d.若在前i次輪詢中這兩個標簽產生的種子一樣，由式(2)可知，X1和X2的前i個s位子串必是式(3)-(6)所示的4種形式之一，其中設兩個標簽的后l-si位任意取值，令和分別表示兩個標簽的第j個s位子串表示對子串求反，P(i)表示第i(i=1，2，3，4)種情況的概率.

當i=n/l時，第2種情況中X1=X2，由于序號的唯一性，所以第2種情況不會導致兩個標簽無限地產生同樣的種子;在第3和第4種情況中，由于只有當i為偶數(shù)時才有，當i為奇數(shù)時兩個標簽不會沖突，所以也不會導致兩個標簽始終產生同樣的種子.

對于第1種情況，當i=l時，標簽的兩個序號且X1≠X2.由于第1次輪詢是直接取序號的后s位作為種子，若第1次輪詢時這兩個標簽均不能被識別，則由式(2)可以知道在后續(xù)的輪詢中這兩個標簽產生的種子是一樣的，出現(xiàn)無限選擇同一時隙的情況，那么對于任意兩個標簽序號其不能被識別的概率為

文中是假設標簽序號為32位進行討論的，則PX1=ˉX2=2-32.在現(xiàn)有的RFID標準中標簽大多采用64位或更高的序號，因此不能被識別的概率更低.可以通過減少有效射頻范圍內標簽數(shù)量的方法來避免標簽無法被識別的情況發(fā)生.

3 仿真實驗

是否可以識別所有的標簽和識別的快慢是判斷算法好壞的兩個關鍵指標.由于仿真環(huán)境與真實的識別環(huán)境有區(qū)別，所以文中將識別過程中閱讀器與標簽之間發(fā)送、接收的命令數(shù)量作為判斷算法識別效率的依據.文中算法利用16位的CRC碼進行分組識別，因此在仿真過程中主要是利用隨機算法產生均勻分布的16位數(shù)據來模擬標簽中的16位CRC碼.仿真用14組標簽數(shù)據，標簽數(shù)量逐步增加，每組標簽數(shù)量為100k'，k'為組號.王鋮岑［5］和江岸等［7］已對ALOHA算法和二叉樹算法的性能進行了比較，結果表明二叉樹算法優(yōu)于ALOHA算法，因此僅將文中算法與二叉樹算法的性能進行對比.

從1.3節(jié)的算法步驟可知，時隙分配時初始的時隙數(shù)為2n(n與標簽ID有關)，在識別過程中每次輪詢結束后，閱讀器會根據3個計數(shù)器(es，ss，cs)來調整時隙數(shù)，那么在第1次輪詢時的初始時隙數(shù)(即最小時隙)會影響算法的識別效率:若最小時隙設置偏小，則當標簽數(shù)量較多時沖突時隙出現(xiàn)的概率較大，增加輪詢的次數(shù)而消耗更多的時間;若最小時隙設置偏大，則當標簽數(shù)量較少時空置時隙出現(xiàn)的概率較大，降低了算法的識別效率.文中仿真使用的數(shù)據標簽最大達到1400個，若設置很大的初始時隙勢必造成更多的空閑時隙，因此最大初始時隙設為64.文中利用上述14組標簽數(shù)據對最小時隙為4、8、16、32、64時的5種情況分別進行仿真計算，結果如圖3所示.

從圖3中可以看到，當標簽數(shù)量較少時，最小時隙較小的識別過程識別的速度較快，這是因為在標簽數(shù)量較少而最小時隙較大時，空時隙的數(shù)量會比較多，此時算法在空時隙上會花費較多的時間.隨著標簽數(shù)量的增多，碰撞發(fā)生的概率也隨之增加，所以最小時隙較小的識別過程會越來越慢.當標簽數(shù)量增加到一定程度時，最小時隙大的識別過程明顯地比最小時隙小的識別過程要快很多.Deng等［9］也指出了類似的情況，即在時隙數(shù)量較少時，隨著標簽的增加，折線發(fā)散得較快，因此在算法應用中可以根據實際情況設定最小時隙.從圖3中還可以看到，不同的最小時隙需要幾乎相同的命令數(shù)量，如在標簽數(shù)量達到600時，最小時隙4和最小時隙8的命令數(shù)量相當.這可能是標簽在每次輪詢前選擇時隙后空時隙或沖突時隙較多，算法不斷調整時隙總數(shù)，導致命令數(shù)量增加.

圖3 不同最小時隙下文中算法的仿真結果比較Fig.3 Comparison of simulation results obtained by proposed algorithm with differentminimum slots

綜上所述，當需要識別的標簽較多時，可以增大最小時隙;當標簽較少時，可以減小最小時隙以提高識別效率.

以相同的標簽數(shù)據對二叉樹算法和文中算法進行仿真，結果如圖4所示.其中二叉樹算法的實驗結果是多次仿真結果的平均值;文中算法的結果是5種初始時隙實驗中識別效率取得較好時的實驗結果.從圖4中可知，二叉樹算法的識別速率隨著標簽數(shù)量的增加呈近似線性的上升，而在同樣測試數(shù)據的前提下文中算法的識別速率比二叉樹算法快.

圖4 二叉樹算法與文中算法的仿真結果對比Fig.4 Comparison of simulation results between proposed algorithm and binary-tree algorithm

4 結語

文中提出了一種基于標簽信息分組的射頻識別防碰撞算法，將標簽分成多個組，然后按組的順序依次識別這些標簽，以減少同一時刻響應閱讀器請求的標簽數(shù)量，從而降低碰撞發(fā)生的概率.算法中分組和時隙選擇是最關鍵的兩個因素，文中對這兩個因素從理論上進行了證明，結果表明:標簽能夠相對均勻地分到各組中，從而保證了分組效率;標簽在時隙選擇上也相對分散，不會過度集中到其中一些時隙上;算法能夠根據前一輪的輪詢結果自適應地調整可選擇時隙的范圍.仿真實驗結果表明:當標簽總量較少、初始時隙范圍較小時，算法性能較優(yōu)，但隨著標簽數(shù)量的增加，初始時隙的范圍越大越好;文中算法的性能要優(yōu)于二叉樹算法.從仿真結果看，文中算法具有一定的分組識別效率，但不是十分明顯，從算法的結構看還有可以優(yōu)化的空間，即輪詢結束后，如果算法能更好地調整時隙選擇范圍，那么算法的分組識別效率會更優(yōu).今后將采用優(yōu)化理論對算法進行優(yōu)化，進一步分析文中算法的分組效率和識別性能，使其性能能夠達到最優(yōu).

［1］Sarma S，Brock D，Engels D.Radio frequency identification and the electronic product code［J］.IEEE Micro，2001，21(6):50-54.

［2］Jihoon Myung，Lee Wonjun.Adaptive binary splitting:a RFID tag collision arbitration protocol for tag identification［J］.Communications Letters，2006，10(3):144-146.

［3］Waldrop J，Engels D，Sarma S.Colorwave:an anti-collision algorithm for the reader collision problem［C］∥Proceedings of IEEE International Conference on Communications.Anchorage:IEEE，2003:1206-1210.

［4］EPGglobal Inc.EPCTMradio-frequency identification protocols class-1 generation-2 UHF RFID protocol for communications at860MHz-960MHz Version 1.0.9［S］.

［5］王鋮岑.RFID系統(tǒng)防碰撞算法［J］.計算機技術與發(fā)展，2010，20(1):29-32，35.Wang Cheng-cen.Anti-collision algorithm on RFID system［J］.Computer Technology and Development，2010，20(1):29-32，35.

［6］Cha Jae-ryong，Kim Jae-hyun.Dynamic framed slotted ALOHA algorithms using fast tag estimation method for RFID system［C］∥Proceedings of IEEE Consumer Communications and Networking Conference.Las Vegas:IEEE，2006:768-772.

［7］江岸，伍繼雄，黃生葉，等.改進的RFID二進制搜索防碰撞算法［J］.計算機工程與應用，2009，45(5):229-235.Jiang An，Wu Ji-xiong，Huang Sheng-ye，et al.Improved RFID binary search anti-collision algorithm［J］.Computer Engineering and Applications，2009，45(5):229-235.

［8］Hush Don R，Wood Cliff.Analysis of tree algorithms for RFID arbitration［C］∥Proceedings of IEEE International Symposium on Information Theory.Cambridge:IEEE，1998:107.

［9］Deng Huifang，Liu Jinqiao，Deng Chunhui，et al.RFID multi-tags anti-collision algorithm with adaptive Q leading to the maximum throughput［C］∥Proceedings of the Third Pacific-Asia Conference on Web Mining and Webbased Application.Guilin:IEEE，2010:166-169.

［10］萬紅，楊延昭.RFID防碰撞算法研究與改進［J］.微計算機信息，2009，25(2/3):230-232.Wan Hong，Yang Yan-zhao.Research and improvement on anti-collision algorithm for RFID system［J］.Microcomputer Information，2009，25(2/3):230-232.

［11］武強，李宏生，楊宇，等.UHF RFID系統(tǒng)防碰撞算法研究［J］.儀表技術，2008(2):16-18，20.Wu Qiang，Li Hong-sheng，Yang Yu，et al.Research on anti-collision algorithm of UHF RFID system［J］.Instrumentation Technology，2008(2):16-18，20.

［12］鄧輝舫，劉金橋.RFID系統(tǒng)防碰撞中的二進制矩陣搜索［J］.微計算機信息，2009，25(10-2):4-5，3.Deng Hui-fang，Liu Jin-qiao.Binary-matrix search in anticollision of RFID system［J］.Micro-computer Information，2009，25(10-2):4-5，3.

［13］Wang Chun-yi，Lee Chi-chung.A grouping-based dynamic framed slotted ALOHA anti-collision method with fine groups in RFID systems［C］∥Proceedings of the 5th International Conference on Future Information Technology.Busan:IEEE，2010:1-5.

［14］ISO/IEC FDIS 18000-6，Information technology automatic identification and data capture techniques—radio frequency identification for item management air interface—part6:parameters for air interface communications at860-960MHz［S］.

［15］Tanenbaurn A S.計算機網絡［M］.熊桂喜，王小虎，譯.3版.北京:清華大學出版社，1997:137-142.

［16］Rotenberg A.A new pseudo-random number generator［J］.Journal of the ACM，1960，7(1):75-77.

［17］Covyou R R.Serial correlation in the generation of pseudo-random numbers［J］.Journal of the ACM，1960，7(1):72-74.

［18］Gereenberger M.Notes on a new pseudo-random number generator［J］.Journal of the ACM，1961，8(2):163-167.

［19］ITU recommendation G.704，Synchronous frame structures used at primary and secondary hierarchical［S］.