鄭曉彥 王玉慶

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

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

鄭曉彥 王玉慶

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

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

射頻識(shí)別；碰撞；二進(jìn)制搜索算法

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

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

1 兩種典型的二進(jìn)制防碰撞算法

1.1 二進(jìn)制搜索算法

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

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

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

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

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

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

1.2 動(dòng)態(tài)二進(jìn)制搜索算法

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

2 改進(jìn)的二進(jìn)制算法

2.1 算法的原理

通過(guò)分析二進(jìn)制搜索算法的缺點(diǎn)，本文提出了一種改進(jìn)的二進(jìn)制算法，算法約定如下：其一，電子標(biāo)簽序列號(hào)上的比特值不是“0”就是“1”，因此如果讀寫(xiě)器檢測(cè)出電子標(biāo)簽的碰撞為只有一位的情況下，不用發(fā)出讀寫(xiě)命令就直接可以將2個(gè)電子標(biāo)簽識(shí)別出來(lái)。其二，當(dāng)讀寫(xiě)器檢測(cè)出電子標(biāo)簽中有N個(gè)碰撞位的話(huà)，說(shuō)明除了這N個(gè)碰撞為是未知的，在其余比特位上的二進(jìn)制數(shù)都是已知的，所以只需要針對(duì)這N個(gè)碰撞為發(fā)送適當(dāng)?shù)恼?qǐng)求命令就可以將電子標(biāo)簽識(shí)別出來(lái)，這樣就極大地減少了二進(jìn)制搜索算法中的重復(fù)檢測(cè)過(guò)程，從而減少識(shí)別所用消耗的時(shí)間。

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

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

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

具體過(guò)程如下：

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

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

第三，讀寫(xiě)器發(fā)送unselect命令使標(biāo)簽1進(jìn)入到“無(wú)聲”狀態(tài)。

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

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

第六，讀寫(xiě)器發(fā)送unselect命令，標(biāo)簽5進(jìn)入到“無(wú)聲”狀態(tài)。

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

第8，讀寫(xiě)器發(fā)送unselect命令，標(biāo)簽7進(jìn)入到“無(wú)聲”狀態(tài)。

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

第10，讀寫(xiě)器發(fā)送unselect命令，標(biāo)簽2和標(biāo)簽6進(jìn)入到“無(wú)聲”狀態(tài)。

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

第十二，讀寫(xiě)器發(fā)送unselect命令，標(biāo)簽8進(jìn)入到“無(wú)聲”狀態(tài)。

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

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

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

2.2 算法性能的比較

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

動(dòng)態(tài)二進(jìn)制搜索算法的搜尋次數(shù)：

而對(duì)于改進(jìn)后的防碰撞算法來(lái)說(shuō)，當(dāng)有N電子標(biāo)簽在讀寫(xiě)器的作用范圍下，而發(fā)生碰撞的次數(shù)為n（N=2n），則當(dāng)有兩個(gè)電子標(biāo)簽探測(cè)到發(fā)生碰撞的位數(shù)只有1位的碰撞的時(shí)候，查詢(xún)次數(shù)：

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

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

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

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

3 結(jié)語(yǔ)

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

[1]夏志國(guó)，何怡剛，侯周?chē)?guó).一種二進(jìn)制樹(shù)位檢測(cè)的標(biāo)簽防碰撞算法[J].計(jì)算機(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]鞠偉成，俞承芳.一種基于動(dòng)態(tài)二進(jìn)制的RFID抗沖突算法[J].復(fù)旦學(xué)報(bào)（自然科學(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]余松森，詹宜巨.基于修剪枝的二進(jìn)制樹(shù)形搜索反碰撞算法與實(shí)現(xiàn)[J].計(jì)算機(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ù)。