RFID技術中防碰撞算法的改進

鄭曉彥 王玉慶

（鄭州信息科技職業學院，河南 鄭州 450046）

RFID技術中防碰撞算法的改進

鄭曉彥 王玉慶

（鄭州信息科技職業學院，河南 鄭州 450046）

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

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

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

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

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

1.1 二進制搜索算法

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

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

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

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

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

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

1.2 動態二進制搜索算法

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

2 改進的二進制算法

2.1 算法的原理

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

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

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

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

具體過程如下：

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

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

第三，讀寫器發送unselect命令使標簽1進入到“無聲”狀態。

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

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

第六，讀寫器發送unselect命令，標簽5進入到“無聲”狀態。

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

第8，讀寫器發送unselect命令，標簽7進入到“無聲”狀態。

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

第10，讀寫器發送unselect命令，標簽2和標簽6進入到“無聲”狀態。

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

第十二，讀寫器發送unselect命令，標簽8進入到“無聲”狀態。

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

第十四，讀寫器發送unselect命令，標簽3竟如到“無聲”狀態。

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

2.2 算法性能的比較

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

動態二進制搜索算法的搜尋次數：

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

當有4個電子標簽，發生的碰撞有2位的時候，查詢次數為：

根據數學歸納法可知當有N電子標簽在讀寫器的作用范圍下，而發生碰撞的次數為n（N=2n），總的查詢次數為：

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

圖1 查詢次數的比較

3 結語

本文主要是對傳統的二進制算法進行了分析和研究，并在此基礎上提出了一種基于二進制算法的改進算法。該算法能夠大大減少搜尋次數和傳輸的數據量，也體現出了該算法的優越性。

[1]夏志國，何怡剛，侯周國.一種二進制樹位檢測的標簽防碰撞算法[J].計算機工程與應用，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]鞠偉成，俞承芳.一種基于動態二進制的RFID抗沖突算法[J].復旦學報（自然科學版），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]余松森，詹宜巨.基于修剪枝的二進制樹形搜索反碰撞算法與實現[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-），女，碩士研究生，助教，研究方向：電子電器技術。