一種新型RFID樹形碰撞位識別防碰撞算法研究

錢琨　潘洋　冉全

摘要摘要：多標簽防碰撞算法在射頻識別系統應用中發揮著重要作用。目前比較有代表性的樹形防碰撞算法都存在識別周期過長、空閑時隙、碰撞時隙過多的問題。針對上述問題，提出了一種根據碰撞位分布特征，調整碰撞節點分叉數的防碰撞算法。仿真及實驗結果表明，該方法能減少空閑時隙和碰撞時隙數量，提高查詢效率及時隙吞吐量，滿足實際需求。

關鍵詞關鍵詞：射頻識別；防碰撞算法；碰撞位識別

DOIDOI：10.11907/rjdk.162854

中圖分類號：TP312

文獻標識碼：A文章編號文章編號：16727800（2017）005004403

0引言

射頻識別（Radio frequency identification，RFID）是一種通過射頻信號識別目標對象的非接觸式自動識別技術，識別過程無需人為干預，在較為惡劣的條件（灰塵、水漬、油漬）下仍能正常工作[1]。最基本的RFID系統由閱讀器和電子標簽構成[2]。其中，電子標簽是射頻識別系統中儲存物體信息的介質，各個電子標簽內部都有唯一產品識別碼來區分不同目標對象。

RFID系統應用時，由于閱讀器只有一個共享信道，在有效范圍內出現較多電子標簽同時進行信息傳輸的情況下會產生通信碰撞[3]。為了閱讀器能夠正常讀取信息，需要以某種方法令電子標簽重復發送信息以避開碰撞[4]，這樣就不可避免地產生了通信開銷以及傳輸延時，影響系統效率[5]。

防碰撞算法一般分為兩個類別：基于時隙分配的ALOHA算法[6]和基于二進制的樹形查詢算法。基于時隙分配的ALOHA算法是將時間離散化，使之變為若干時隙，當發生碰撞時，標簽必須等待下一個時隙才能重新發送信息。其缺點顯而易見：標簽數量較多時碰撞概率會增加，有些情況下某些標簽發生多次碰撞時可能長時間無法識別，出現所謂“標簽饑餓”現象。基于二進制的樹形查詢算法根據深度優先思想，指定產生碰撞節點處查詢的比特位數，將碰撞節點逐漸分裂為更小的碰撞子集，逐步縮小查詢范圍，最終達到識別所有標簽的目的。

1典型樹形查詢算法

典型樹形查詢算法是將標簽內存所攜帶的識別碼ID與閱讀器發送前綴查詢進行比較、判斷。首先閱讀器發送查詢指令，根據標簽返回攜帶的識別碼ID是否包含該前綴判斷有無標簽應答。若只有唯一標簽應答，則將該前綴所代表的標簽標記為已確認標簽。若該前綴查詢同時有多個標簽應答，則進一步在原前綴后加入若干個比特位組成新的前綴。重復上述過程，直至最終實現所有標簽都正確識別。圖1是樹形查詢算法查詢流程。

2新型碰撞位識別防碰撞算法（CBRA）

樹形查詢算法中，假設總時隙期望為T0（n），碰撞時隙期望為C0（n），空閑時隙期望為I0（n），系統內符合查詢條件的標簽數量有n個，由此可得：

T0（n）=C0（n）+I0（n）+n（1）

樹形查詢方法在L層分枝有標簽的概率P=B-L，B為樹的分叉數，L層中k個標簽出現在同一時隙的概率為

P（k/n，L）=Cknpk（1-p）n-k（2）

根據公式（2）得出分枝狀態分別為空閑時隙、確認時隙、碰撞時隙的概率：

P（0/n）=（1-p）n（3）

P（1/n，L）=n（1-p）n-1（4）

P（k>1/n，L）=1-（1-p）n-n（1-p）n-1（5）

設歷遍到s層第i個分枝的概率為P（s/i，n），由于每次查詢開始的概率P（s/i，n）=1，由此可得P（s/i，n）=1P（k>1/n，L） L=1L>1 （6）

根據公式（6）可得總時隙期望為T0（n）=1+B∑∞l=0BlP（k>1/n，L）（7）

同理可得碰撞時隙期望為

C0（n）=∑∞l=0BlP（k>1/n，L）=1B（T0（n）-1）（8）

代入式（1）則空閑時隙I0（n）為

I0（n）=B-1BT0（n）+1B-n（9）

當分叉數B=3時，總時隙T0（n）為最小值，標簽識別效果最佳。樹形查詢結構依托于二進制，不能使用三叉樹進行標簽識別，因此本文對基于二進制的樹形查詢算法作適當改進，根據碰撞位信息判斷混合使用叉樹類型，而不是單一使用某種叉樹，在減少碰撞時隙數量的同時避免產生大量空閑時隙，提高系統效率。

假設當前分枝符合查詢條件的待識別標簽為m個，任意位不發生碰撞概率為（12）m-1，則采用二叉樹概率為

P（B=2）=[1-（12）m-1]（12）m-1（10）

采用四叉樹概率為

P（B=4）=[1-（12）m-1]2（11）

當m=2時，二叉樹以及四叉樹采用的概率是相等的。即可將m=2作為臨界條件，當m≤2時使用二叉樹查詢算法，m>2時使用四叉樹查詢算法。

如圖2所示，以0000、0001、0010、0011、1100、1101、1110、1111八個標簽為例，對比兩種樹形查詢算法，可以發現二叉樹查詢算法查詢深度較大而且碰撞時隙較多。四叉樹查詢算法雖然減少了查詢深度和碰撞時隙，但會出現較多空閑時隙。

如圖3所示，經過改進后的碰撞位識別防碰撞算法（Collision Bit Recognition Algorithm），根據碰撞位待識別標簽數量合理使用二叉樹或四叉樹查詢，避免空閑時隙的產生并能減少碰撞時隙和總時隙數量。

3仿真與實驗結果分析

純二叉樹查詢算法中，除葉節點度為0之外其余節點度均為2。假設其余節點數為m1，葉節點（待識別標簽）數為m2，則總時隙數M=m1+m2。此外，根據二叉樹性質可得總時隙數為各節點樹之和加1，因此可得M=2m1+1，m1=m2-1。可得總時隙數和待識別數之間關系為：

M=2m2-1 （12）四叉樹查詢算法中，除葉節點樹為0之外，其余節點樹均為4。總時隙M=4m1+1，可得m2=3m1+1。將葉節點數按確認時隙和空閑時隙分別設為j1和j2，則j1+j2=3m1+1。由于存在兩位連續碰撞位，因此一個碰撞時隙最多產生空閑時隙0～2個，產生2個空閑時隙時j2=2m1，可得m1=j1-1。則最大總時隙：Mmax=j1+j2+m1=2j1-3（13）當產生0個空閑時隙時，葉節點數與確認時隙數相等，即j1=3m1+1，m1=（j1-1）/3，則最小總時隙Mmin=j1+j2=（4j1-1）/3=（4m2-1）/3（14）將式（13）和（14）取均值可得：

=（5m2-5）/3（15）將式（12）與式（15）所得總時隙取均值可得碰撞位識別查詢算法總時隙為：

=（11m2-8）/6（16）

通過Matlab將公式（12）、（15）、（16）進行仿真比較，得到3種算法總時隙對照圖（見圖4）。待識別標簽數在0-500區間采樣時，CBRA總時隙數始終少于純二叉樹和純四叉樹算法。

系統傳輸率為確認時隙與總時隙之比，待識別標簽數即為確認時隙數，可得系統傳輸率β為：β=確認時隙確認時隙+碰撞時隙+空閑時隙=m2M（17）

同樣，對比三者系統傳輸率，CBRA在系統傳輸率上也始終好于其它兩種算法，如圖5所示。

4結語

基于二進制的樹形防碰撞算法無法達到在減少碰撞時隙的同時消除空閑時隙的目的。本文在分析二叉樹、四叉樹結構查詢方法的基礎上，吸收了兩者的優點，形成一種根據當前分枝待識別標簽數量，選擇性地使用二叉樹和四叉樹進行標簽查詢的方法。根據仿真結果可知，該新型算法可以減少總時隙數量并提高系統傳輸率，具有一定的實際應用仿值。

參考文獻參考文獻：

[1]夏小勤，胡佳佳.基于動態樹形RFID防碰撞算法的研究[J].科技廣場，2014（3）：7984.

[2]江城，黃立波.基于二進制搜索的RFID標簽防碰撞算法的研究[J].計算機與數字工程，2011（4）：2933.

[3]宋建華，郭亞軍，韓蘭勝，等.自調整混合樹RFID多標簽防碰撞算法[J].電子學報，2014（4）：685689.

[4]施衛東.一種改進的RFID防碰撞算法[J].科技通報，2015（4）：121123.

[5]呂敬祥，劉清，過繼紅.基于碰撞樹的自適應多叉樹RFID防碰撞算法[J].井岡山學院學報：自然科學版，2014（2）：3944.

[6]馬琰，蔡麗霞，任曉娜.一種自適應幀長RFID標簽防碰撞算法[J].計算機與現代化，2014（11）：113121.

責任編輯（責任編輯：杜能鋼）