鄭曉彥 王玉慶

（鄭州信息科技職業(yè)學(xué)院，河南 鄭州 450046）

RFID技術(shù)中防碰撞算法的改進

鄭曉彥 王玉慶

（鄭州信息科技職業(yè)學(xué)院，河南 鄭州 450046）

在射頻識別系統(tǒng)中，如果多個電子標簽同時出現(xiàn)在讀寫器的作用范圍內(nèi)，就會出現(xiàn)多個電子標簽在數(shù)據(jù)上的碰撞問題，如果標簽的碰撞位過多，用二進制搜索防碰撞算法處理起來就會顯得繁瑣，本文提出了一種基于二進制搜索算法的改進算法，原理是當(dāng)碰撞位數(shù)過多時，就將碰撞位每兩個來處理，通過設(shè)置它們的比特位來發(fā)送查詢命令，理論和仿真軟件證明了該算法比二進制搜索算法和動態(tài)算法更具優(yōu)勢。

射頻識別；碰撞；二進制搜索算法

射頻識別技術(shù)是一種非接觸的自動識別技術(shù)，主要是由電子標簽和讀寫器組成，通過無線傳輸技術(shù)對電子標簽內(nèi)部的數(shù)據(jù)進行讀取或修改操作，當(dāng)在讀寫器的作用范圍內(nèi)存在多個電子標簽時，所有的電子標簽就會同一時間將標簽內(nèi)部數(shù)據(jù)發(fā)送給讀寫器，在傳輸?shù)倪^程中就會造成數(shù)據(jù)間的相互干擾，即碰撞。這樣讀寫器就不能正常的讀取出電子標簽的內(nèi)部數(shù)據(jù)，從而影響射頻識別系統(tǒng)的正常工作。這也就是多路存取問題，因此，保證射頻識別系統(tǒng)的正常運行的首要工作就是解決好電子標簽的碰撞問題。而解決電子標簽碰撞問題的方法就是設(shè)計出行之有效的防碰撞算法。

現(xiàn)有的射頻識別系統(tǒng)的防碰撞算法都是基于TDMA[1]的，并且可以劃分為基于二進制樹搜索（Binary search，BS）算法和Aloha防碰撞算法。Aloha算法的特點是：算法比較簡單，容易實現(xiàn)，成本低。但該算法的時隙是隨機分配的，當(dāng)有大量電子標簽并存的時候，幀沖突嚴重，存在“tag starvation”問題[2-3]。而基于二進制搜索（BS）算法雖然識別率高，但是相應(yīng)的算法復(fù)雜，識別需要較長的時間[4]，本文是基于二進制搜索算法提出了一種改進的防碰撞算法。

1 兩種典型的二進制防碰撞算法

1.1 二進制搜索算法

能夠在讀寫器中準確辨認出發(fā)生碰撞的比特位是實現(xiàn)二進制搜索算法的前提條件，因此必須選擇適合的編碼，曼徹斯特編碼能夠按位識別出碰撞位，這樣就可以根據(jù)發(fā)生碰撞的位置，讀寫器就可以按一定的規(guī)則重新發(fā)出讀取命令來搜索電子標簽，因此曼徹斯特編碼的使用是實現(xiàn)二進制搜索防碰撞算法的必要前提。它的工作流程如下：

1.1.1 電子標簽進入到讀寫器的信號范圍下，讀寫器便會向電子標簽發(fā)送REQUEST（≤11111111）的命令，所有滿足該條件的電子標簽都會發(fā)生響應(yīng)，并向讀寫器發(fā)送自己的EPC號。

1.1.2 讀寫器對比所有電子標簽相同位置上的二進制數(shù)，如果發(fā)現(xiàn)有不一致的情況，就可以判定出該位置上發(fā)生碰撞。

1.1.3 當(dāng)確定發(fā)生碰撞時，就將發(fā)生碰撞的最高比特位上的二進制數(shù)置為0，發(fā)生碰撞最高比特位之前的數(shù)保持不變，之后的數(shù)均置為1，并將此二進制數(shù)作為下次的REQUEST命令，從而逐步排除序列號較大的電子標簽，直至發(fā)送的命令與電子標簽所響應(yīng)的序列號完全一致時，就說明了再無碰撞發(fā)生，使用選擇命令（SELECT）選出這個唯一的標簽。

1.1.4 選出唯一的標簽以后，使用（UNSELECT）命令，使這個點子標簽進入到“無聲”狀態(tài)，不再對讀寫器發(fā)出的命令進行相應(yīng)，當(dāng)該標簽移出讀寫器的作用范圍以外再進入時，可重新發(fā)生響應(yīng)，進行復(fù)位操作可以重新激活該電子標簽

1.1.5 重復(fù)上述的4個步驟，直至完成對所有電子標簽數(shù)據(jù)的讀取操作

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

在二進制搜索算法中，從讀寫器和單個電子標簽進行數(shù)據(jù)轉(zhuǎn)換的過程中可以看出：讀寫器發(fā)出請求命令中，把最高碰撞位之后的比特位都置為1，這對于標簽的識別不能提供任何信息，而標簽返回過來的數(shù)據(jù)，最高碰撞位和最高碰撞位之前的比特位也不包含任何補充的信息，屬于重復(fù)多余的信息，正因為如此，人們提出了動態(tài)二進制算法[5]，當(dāng)讀寫器檢測到有碰撞發(fā)生的時候，下一次讀寫器在請求命令中只發(fā)送搜索序列號中的最高位與最高碰撞位之間的二進制數(shù)位搜索的依據(jù)，然后中斷傳輸，所有與最高位和最高碰撞位之間二進制數(shù)相同的電子標簽發(fā)生響應(yīng)，并將剩余的序列號傳輸給讀寫器。這樣就避免了序列號中多余二進制數(shù)的傳輸，這樣就能縮短識別的時間，動態(tài)二進制數(shù)相對于二進制搜索算法來說，在傳輸數(shù)據(jù)量和傳輸時間上可以減少達50%。時間上可以減少達50%。

2 改進的二進制算法

2.1 算法的原理

通過分析二進制搜索算法的缺點，本文提出了一種改進的二進制算法，算法約定如下：其一，電子標簽序列號上的比特值不是“0”就是“1”，因此如果讀寫器檢測出電子標簽的碰撞為只有一位的情況下，不用發(fā)出讀寫命令就直接可以將2個電子標簽識別出來。其二，當(dāng)讀寫器檢測出電子標簽中有N個碰撞位的話，說明除了這N個碰撞為是未知的，在其余比特位上的二進制數(shù)都是已知的，所以只需要針對這N個碰撞為發(fā)送適當(dāng)?shù)恼埱竺罹涂梢詫㈦娮訕撕炞R別出來，這樣就極大地減少了二進制搜索算法中的重復(fù)檢測過程，從而減少識別所用消耗的時間。

為了便于描述該改進算法，給出以下的防碰撞命令。

2.1.1 該算法主要是對碰撞位進行0，1的二進制數(shù)賦值，與碰撞位上的二進制數(shù)具有相同序列號的電子標簽將被識別出來，如果碰撞位數(shù)過多，賦值的過程也比較麻煩，因此采用每兩位碰撞位進行賦值的方法，查詢命令REQUEST（Dx1，Mx；Dx2，Mx1），REQUEST（Dx3，Mx3；Dx4，Mx4），參數(shù)Dx1為檢測到的最高碰撞位，Dx2為碰撞次高位，Dx3為碰撞位的第三高位，Dx4為碰撞為的第四高位，例如檢測1？？1？？0？，那么讀寫器首先發(fā)送request（D6，0；D5，0），符合條件的電子標簽進行相應(yīng)，然后響應(yīng)的標簽進入到待命的狀態(tài)，然后在發(fā)送request（D4，0；D3，0）命令，從待命狀態(tài)下的電子標簽選出符合條件的電子標簽，完成數(shù)據(jù)讀取后，將讀取過的電子標簽進入“無聲”狀態(tài)，即非激活狀態(tài)。同理讀寫器依次發(fā)送（D4，0；D3，1）（D4，1；D3，0），（D4，1；D3，1）命令將處于相應(yīng)待命狀態(tài)的電子標簽全部識別出來，并將其進入非激活狀態(tài)，然后再發(fā)送request（D6，0；D5，1）命令，重復(fù)上述過程直至將電子標簽全部識別出來。

2.1.2 退出選擇命令unselect：取消事先選中的電子標簽，使標簽進入到“無聲”的狀態(tài)，即非激活狀態(tài)，對于讀寫器所下達的任何命令都不予以響應(yīng)。如果想要重新激活標簽，需要先移除讀寫器的范圍，并再次進入到讀寫器的范圍。下面以8個具體的電子標簽為例，電子標簽的編碼為8位，它們的編碼分別如下：標簽1：00001000，標簽2：01010100，標簽3：10011010，標簽4：11000000，標 簽 5：01000010，標 簽 6：01010000，標 簽 7：01001010，標簽8：01011000.

具體過程如下：

第一，發(fā)送request≤11111111命令，處在讀寫器范圍內(nèi)的所有電子標簽均發(fā)生相應(yīng)，并向讀寫器發(fā)送各自的序列號，讀寫器檢測出的結(jié)果為：？？0？？？？0碰撞位為D7，D6，D4，D3，D2，D1。最高碰撞位是D7，次高碰撞位為D6，第三高碰撞位為D4，第四高碰撞位為D3。因此下次發(fā)送的查詢命令為（D7，0；D6，0）。

第二，讀寫器發(fā)送查詢命令（D7，0；D6，0），標簽通過比較自己相應(yīng)位上的二進制數(shù)，與之相同的電子標簽將內(nèi)部的信息發(fā)送給讀寫器，通過比較得發(fā)生相應(yīng)的只有標簽1，這樣標簽1就被順利識別出。

第三，讀寫器發(fā)送unselect命令使標簽1進入到“無聲”狀態(tài)。

第四，讀寫器發(fā)送查詢命令requset（D7，0；D6，1），發(fā)生響應(yīng)的電子標簽為：標簽2，標簽5，標簽6，標簽7，標簽8，然后將這些響應(yīng)的標簽進入到待命狀態(tài)。

第五，讀寫器發(fā)送命令request（D4，0；D3，0），碰撞位上二進制數(shù)與之相同的電子標簽為標簽5，因此讀寫器從這些待命的電子標簽中識別出標簽5。

第六，讀寫器發(fā)送unselect命令，標簽5進入到“無聲”狀態(tài)。

第七，讀寫器發(fā)送命令request（D4，0；D3，1），碰撞位上二進制數(shù)與之相同的電子標簽是標簽7，因此讀寫器從這些待命的電子標簽中識別出標簽7。

第8，讀寫器發(fā)送unselect命令，標簽7進入到“無聲”狀態(tài)。

其9，讀寫器發(fā)送命令request（D4，1；D3，0），碰撞位上二進制數(shù)與之相同的電子標簽為標簽2和標簽6。處于待命中的標簽2和標簽6發(fā)生響應(yīng)，讀寫器檢測出這兩個電子標簽只有一個碰撞位，因此可以直接識別出待命狀態(tài)的標簽2和標簽6。

第10，讀寫器發(fā)送unselect命令，標簽2和標簽6進入到“無聲”狀態(tài)。

第十一，讀寫器發(fā)送命令request（D4，1；D3，1），碰撞位上二進制數(shù)與之相同的電子標簽為標簽8，因此讀寫器識別出待命狀態(tài)中的標簽8。

第十二，讀寫器發(fā)送unselect命令，標簽8進入到“無聲”狀態(tài)。

第十三，此時讀寫器已經(jīng)處于待命狀態(tài)的電子標簽全部識別完。讀寫器再次發(fā)送命令request（D7，1；D6，0），碰撞位上二進制數(shù)與之相同的電子標簽為標簽3，因此讀寫器識別出標簽3。

第十四，讀寫器發(fā)送unselect命令，標簽3竟如到“無聲”狀態(tài)。

第十五，讀寫器發(fā)送命令request（D7，1；D6，1），碰撞位上二進制數(shù)與之相同的電子標簽是標簽4，因此讀寫器識別出標簽4。至此，處于讀寫器范圍內(nèi)的電子標簽全部被正確識別出來。

2.2 算法性能的比較

設(shè)在讀寫器作用范圍內(nèi)的電子標簽數(shù)有N個，防碰撞算法完成所有電子標簽識別所需要的搜尋命令次數(shù)為S（N），那么基于二進制搜索防碰撞算法的搜尋次數(shù)：

動態(tài)二進制搜索算法的搜尋次數(shù)：

而對于改進后的防碰撞算法來說，當(dāng)有N電子標簽在讀寫器的作用范圍下，而發(fā)生碰撞的次數(shù)為n（N=2n），則當(dāng)有兩個電子標簽探測到發(fā)生碰撞的位數(shù)只有1位的碰撞的時候，查詢次數(shù)：

當(dāng)有4個電子標簽，發(fā)生的碰撞有2位的時候，查詢次數(shù)為：

根據(jù)數(shù)學(xué)歸納法可知當(dāng)有N電子標簽在讀寫器的作用范圍下，而發(fā)生碰撞的次數(shù)為n（N=2n），總的查詢次數(shù)為：

根據(jù)MATLAB仿真結(jié)果如圖1：可以看出改進后的防碰撞算法比之傳統(tǒng)的算法具有兩個明顯的優(yōu)勢：一是搜尋的次數(shù)大大減少，從而減少讀寫器識別標簽的時間。二是傳輸?shù)臄?shù)據(jù)量減少，相應(yīng)的識別時間也大大減小，從而提高識別的效率。

圖1 查詢次數(shù)的比較

3 結(jié)語

本文主要是對傳統(tǒng)的二進制算法進行了分析和研究，并在此基礎(chǔ)上提出了一種基于二進制算法的改進算法。該算法能夠大大減少搜尋次數(shù)和傳輸?shù)臄?shù)據(jù)量，也體現(xiàn)出了該算法的優(yōu)越性。

[1]夏志國，何怡剛，侯周國.一種二進制樹位檢測的標簽防碰撞算法[J].計算機工程與應(yīng)用，2010，46（20）：245-248.

Xia ZG，He Y G，Hou Z G.A binary tree tag anti-collision algorithm for detecting [J]. Computer Engineering and Applications，2010，46（20）：245-248.

[2]Harald Vogt．Efficient object identification with Passive RFID tags，in：Proceedings International Conference on Pervasive Computing，April，2002：98-113.

[3]Harald Vogt.Multiple object identification with Passive RFID tags，in：Proceedings of IEEE International Conference on Systems，Manand Cybernetics，vol.3，Hammamet，Tunisia，October，2002：114-124.

[4]鞠偉成，俞承芳.一種基于動態(tài)二進制的RFID抗沖突算法[J].復(fù)旦學(xué)報（自然科學(xué)版），2005，44（1）：46-50.

Ju W C，Yu C F.A dynamic binary anti-collision algorithm based on RFID [J]，Journal of Fudan University（Natural Science），2005，44（1）：46-50.

[5]余松森，詹宜巨.基于修剪枝的二進制樹形搜索反碰撞算法與實現(xiàn)[J].計算機工程，200，31（16）：217-218.

Yu S S，Zhan Y J.Pruning branches based on a binary search tree anti-collision algorithm and implementation[J]. Computer Engineering，200，31（16）：217-218.

TP301

A

1671-0037（2014）08-81-2.5

鄭曉彥（1986-），女，碩士研究生，助教，研究方向：電子電器技術(shù)。