RFID中解決無線信道爭用問題的防碰撞算法研究

摘要：RFID技術(shù)中的防碰撞算法分為閱讀器的防碰撞以及標(biāo)簽的防碰撞兩種。文章通過對(duì)RFID中各種主流防碰撞方法的思想、實(shí)現(xiàn)及算法的研究，在現(xiàn)有的二進(jìn)制搜索算法的基礎(chǔ)之上，提出了一種改進(jìn)算法，并對(duì)改進(jìn)算法的實(shí)現(xiàn)進(jìn)行了Matlab仿真。結(jié)果證實(shí)：改進(jìn)后的算法相較其他算法在標(biāo)簽長度較短的情況下，可以表現(xiàn)出極其優(yōu)越的性能。
關(guān)鍵詞：RFID；防碰撞；二進(jìn)制搜索算法；改進(jìn)算法

0 引言
RFID系統(tǒng)主要由讀寫器和射頻卡兩部分組成，它們之間可以通過無線方式進(jìn)行通信。其中，射頻卡中存儲(chǔ)了需要識(shí)別、交互的數(shù)據(jù)，并且可以實(shí)時(shí)寫入或擦除。RFID系統(tǒng)工作時(shí)，若有多個(gè)電子標(biāo)簽同時(shí)在同一個(gè)閱讀器的作用范圍內(nèi)向閱讀器發(fā)送數(shù)據(jù)，則往往會(huì)出現(xiàn)信號(hào)的干擾，這個(gè)干擾就被稱為碰撞，其結(jié)果將會(huì)導(dǎo)致此次數(shù)據(jù)傳輸?shù)氖?，因而必須采用適當(dāng)?shù)募夹g(shù)防止碰撞。最近，有人提出了動(dòng)態(tài)二進(jìn)制搜索法、跳躍式類二進(jìn)制搜索法等二進(jìn)制防碰撞算法的改進(jìn)算法。國際上廣泛應(yīng)用的防碰撞算法是ALOHO法和二進(jìn)制搜索法及對(duì)這兩種算法的改進(jìn)方法，如時(shí)隙ALOHO法、動(dòng)態(tài)二進(jìn)制搜索法、后退式二進(jìn)制法搜索等。其中，動(dòng)態(tài)二進(jìn)制法是國際標(biāo)準(zhǔn)所推薦的防碰撞方法。就此，本文提出了一種二進(jìn)制搜索法的改進(jìn)型算法。

1 二進(jìn)制搜索算法
1．1 二進(jìn)制搜索算法(BS)原理
二進(jìn)制搜索算法又稱為二叉樹搜索算法。由于它要求能夠在閱讀器中確定數(shù)據(jù)碰撞位的準(zhǔn)確位置，因此，必須要有合適的位編碼法。曼徹斯特碼用上升沿表示0，用下降沿表示1，在數(shù)據(jù)傳輸過程中不允許“沒有改變”的狀態(tài)。如果采用ASK調(diào)制方式，當(dāng)多個(gè)電子標(biāo)簽同時(shí)發(fā)送的數(shù)據(jù)位值不同時(shí)，則對(duì)應(yīng)的曼徹斯特碼的上升沿和下降沿相互抵消，造成一種錯(cuò)誤的狀態(tài)，從而可以確定碰撞位置。假設(shè)有兩個(gè)編碼為8位的電子標(biāo)簽，利用曼徹斯特編碼識(shí)別碰撞位的原理如圖1所示。閱讀器檢出的碰撞位為D6位和D5位。

一般情況下，二進(jìn)制搜索算法必須先能辨認(rèn)出閱讀器中數(shù)據(jù)沖突的確切位置，這一點(diǎn)是下面算法的基礎(chǔ)。這里主要對(duì)以下幾個(gè)命令以及原理流程進(jìn)行簡述：
REQUEST(某序列號(hào)Q)：如果標(biāo)簽序列號(hào)小于或等于Q，則該標(biāo)簽進(jìn)入識(shí)別狀態(tài)，將發(fā)自己的序列號(hào)給閱讀器，否則處于等待狀態(tài)；
SELECT(某序列號(hào)Q)：如果標(biāo)簽序列號(hào)等于Q，則該標(biāo)簽進(jìn)入選中狀態(tài)，否則繼續(xù)等待識(shí)別；
READ：選中的標(biāo)簽與閱讀器進(jìn)行數(shù)據(jù)通信；
UNSELECT：取消前選中標(biāo)簽，該標(biāo)簽進(jìn)入靜默狀態(tài)，待所有標(biāo)簽完成通信或者該標(biāo)簽重新入場后，才能進(jìn)入等待狀態(tài)。
1．2 二進(jìn)制搜索算法的深入分析
閱讀器和標(biāo)簽之間的通信次數(shù)決定了識(shí)別速度。從眾多標(biāo)簽中識(shí)別出一個(gè)標(biāo)簽的平均通信次數(shù)為L。在二進(jìn)制搜索算法中，我們知道：
L=log2N+1 (1)
由于二進(jìn)制搜索算法的識(shí)別獨(dú)立性，N個(gè)標(biāo)簽的全部識(shí)別平均通信次數(shù)為：

當(dāng)標(biāo)簽數(shù)目很多的時(shí)候，由于每次獨(dú)立識(shí)別浪費(fèi)了大量通信次數(shù)，算法總的通信次數(shù)必然會(huì)增長很快。二進(jìn)制搜索算法還有一個(gè)很明顯的弱點(diǎn)：閱讀器發(fā)送給每個(gè)標(biāo)簽的比較序列，其實(shí)有用的信息只包含在高于上次碰撞位X的高位之中，低于碰撞位的通信產(chǎn)生冗余。

2 動(dòng)態(tài)二進(jìn)制搜索算法
2．1 動(dòng)態(tài)二進(jìn)制搜索算法原理
前面所述的二進(jìn)制搜索算法，每次搜索都需要完整的傳輸標(biāo)簽的序列號(hào)ID。但在實(shí)際應(yīng)用中，標(biāo)簽的序列號(hào)長度不再像前所述那樣為8位，而可能是長達(dá)10個(gè)字節(jié)甚至更大的規(guī)模。這樣采用BS算法，RFID系統(tǒng)標(biāo)簽的傳輸量將大增，為此動(dòng)態(tài)二進(jìn)制搜索(DBS)算法應(yīng)運(yùn)而生。D BS算法是IS014443A這一國際標(biāo)準(zhǔn)所推薦的防碰撞算法。序列號(hào)ID中的全部信息對(duì)于成功識(shí)別出標(biāo)簽不是不可或缺的。根據(jù)編碼規(guī)律可以去掉序列號(hào)中的冗余信息，留下有用的信息傳輸。通過觀察上面BS算法實(shí)例中標(biāo)簽的識(shí)別過程可知：命令中的碰撞位及其低位因?yàn)榭偸潜恢梦粸?，不包含有用的信息，這樣就不要傳輸；標(biāo)簽應(yīng)答的序列號(hào)最高位至碰撞位是已知的前綴信息，不包括補(bǔ)充信息，也不需要傳輸。由上面的分析可知，序列號(hào)ID中的冗余部分是不需要傳輸?shù)?。可以將DBS算法由雙向的完整傳輸加以改進(jìn)，只傳輸部分有用信息。Request命令中，讀寫器只需以要搜索的序列號(hào)ID的碰撞位至最高位部分為參數(shù)。所有相應(yīng)位與此命令中參數(shù)相符的標(biāo)簽，則傳輸序列號(hào)的碰撞位以下部分作為應(yīng)答。
2．2 DBS算法的命令
與BS算法的命令相比，DBS算法的命令做了一些改進(jìn)：主要是DBS算法把第一個(gè)命令改成Request(IDn-x，X)。讀寫器發(fā)送參數(shù)IDn-x(ID的N-X位)給作用范圍內(nèi)的所有標(biāo)簽，相應(yīng)位與IDn-x符合的標(biāo)簽做出響應(yīng)，返回剩余的位信息。其余三條命令與前面所述BS算法一致。
2．3 DBS算法的性能分析
DBS算法與BS算法的規(guī)則相同，所以兩者重復(fù)操作的過程也相同。因此，DBS算法的總搜索次數(shù)為：

DBS算法在識(shí)別過程開始時(shí)，即算法的第一步，工作范圍內(nèi)的標(biāo)簽是需要傳輸整個(gè)序列號(hào)的；在這之后的識(shí)別過程中，標(biāo)簽只需要傳輸ID的有用部分位。整個(gè)識(shí)別過程平均下來，DBS的信息量只有BS算法的一半。DBS算法中，標(biāo)簽要傳輸?shù)臄?shù)據(jù)量和所需時(shí)間比起B(yǎng)S算法減少了近50％。