錢琨　潘洋　冉全

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

關(guān)鍵詞關(guān)鍵詞：射頻識別；防碰撞算法；碰撞位識別

DOIDOI：10.11907/rjdk.162854

中圖分類號：TP312

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

0引言

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

RFID系統(tǒng)應用時，由于閱讀器只有一個共享信道，在有效范圍內(nèi)出現(xiàn)較多電子標簽同時進行信息傳輸?shù)那闆r下會產(chǎn)生通信碰撞[3]。為了閱讀器能夠正常讀取信息，需要以某種方法令電子標簽重復發(fā)送信息以避開碰撞[4]，這樣就不可避免地產(chǎn)生了通信開銷以及傳輸延時，影響系統(tǒng)效率[5]。

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

1典型樹形查詢算法

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

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

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

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

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

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

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

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）

根據(jù)公式（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）

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

假設當前分枝符合查詢條件的待識別標簽為m個，任意位不發(fā)生碰撞概率為（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八個標簽為例，對比兩種樹形查詢算法，可以發(fā)現(xiàn)二叉樹查詢算法查詢深度較大而且碰撞時隙較多。四叉樹查詢算法雖然減少了查詢深度和碰撞時隙，但會出現(xiàn)較多空閑時隙。

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

3仿真與實驗結(jié)果分析

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

M=2m2-1 （12）四叉樹查詢算法中，除葉節(jié)點樹為0之外，其余節(jié)點樹均為4?？倳r隙M=4m1+1，可得m2=3m1+1。將葉節(jié)點數(shù)按確認時隙和空閑時隙分別設為j1和j2，則j1+j2=3m1+1。由于存在兩位連續(xù)碰撞位，因此一個碰撞時隙最多產(chǎn)生空閑時隙0～2個，產(chǎn)生2個空閑時隙時j2=2m1，可得m1=j1-1。則最大總時隙：Mmax=j1+j2+m1=2j1-3（13）當產(chǎn)生0個空閑時隙時，葉節(jié)點數(shù)與確認時隙數(shù)相等，即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）。待識別標簽數(shù)在0-500區(qū)間采樣時，CBRA總時隙數(shù)始終少于純二叉樹和純四叉樹算法。

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

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

4結(jié)語

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

參考文獻參考文獻：

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

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

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

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

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

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

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