RFID防碰撞協(xié)議原理分析

1、RFID防碰撞協(xié)議原理分析姓名： _張強強_學(xué)號： 院系： _計算機學(xué)院_專業(yè)： _網(wǎng)絡(luò)工程_指導(dǎo)教師：_范波_目錄摘要3Abstract31.RFID系統(tǒng)中防碰撞協(xié)議41.1 二進(jìn)制防碰撞協(xié)議51.2 查詢樹防碰撞協(xié)議52.RFID中防碰撞算法62.1基于Aloha的算法62.1.1純Aloha62.1.2時隙Aloha72.1.3 FSA82.1.4 DFSA82.2基于二進(jìn)制樹的算法92.2.1 二進(jìn)制搜索算法92.2.2 動態(tài)二進(jìn)制搜索算法92.2.3后退式二進(jìn)制搜索算法9結(jié)束語10參考文獻(xiàn)11摘要RFID是一種非接觸式的自動識別技術(shù)，碰撞問題是影響RFID系

2、統(tǒng)讀取效率的關(guān)鍵問題。導(dǎo)致標(biāo)簽識別效率的降低和資源的浪費。本文介紹了兩種防碰撞協(xié)議的性能。指出其優(yōu)缺點和研究進(jìn)展情況。關(guān)鍵詞：RFID ; 防碰撞協(xié)議AbstractRFID is a non-contact automatic identification technology, which is the key problem of the RFID system. Reduce the efficiency of label identification and the waste of resources. In this paper, the performances of thre

3、e kinds of anti-collision protocols are compared. Points out their advantages and disadvantages and the research progress.Keyword: RFID ; Anti-collision protocol1. RFID系統(tǒng)中防碰撞算法為了解決碰撞問題，產(chǎn)生了很多的防碰撞算法，目的就是把眾多的標(biāo)簽按照某種方式分隔開進(jìn)行逐個讀取，主要有頻分多路法(FDMA)、空分多路法(SDMA)、時分多路法(TDMA)和碼分多路法(CDMA)四種方法。防碰撞算法結(jié)構(gòu)圖如圖所示防碰撞算法二進(jìn)制樹Q

4、算法查詢樹分裂法輪詢法Aloha閱讀器驅(qū)動標(biāo)簽驅(qū)動CDMAFDMA TDMASDMA空分多路法由于其復(fù)雜的天線系統(tǒng)的高費用使得應(yīng)用不是很廣泛，頻分多路法由于其閱讀器的費用比較高，應(yīng)用也受到了限制。碼分多路法的多路方式軟件設(shè)計困難，讀寫器每一路都需要相應(yīng)的硬件或軟件支持，非常復(fù)雜，所以不適合RFID系統(tǒng)。因此，TDMA成為反碰撞算法最廣泛的選擇，該方法又分為標(biāo)簽驅(qū)動法和閱讀器驅(qū)動法，標(biāo)簽驅(qū)動法中具有代表性的算法是Aloha算法。閱讀器驅(qū)動法需要準(zhǔn)確的同步進(jìn)而無錯誤的檢測出碰撞位，它再劃分為“輪詢法”和“分裂法”。由于Aloha算法不能有效地解決標(biāo)簽餓死的問題，所以本文的研究主要在分裂法的基礎(chǔ)上進(jìn)

5、行。1.1 二進(jìn)制防碰撞協(xié)議二進(jìn)制防碰撞協(xié)議中，閱讀器應(yīng)用二進(jìn)制搜索算法能夠成功地讀取它范圍內(nèi)的所有標(biāo)簽。標(biāo)簽含有唯一的ID序列號(由一些二進(jìn)制碼構(gòu)成)，閱讀器在每次查詢過程中只發(fā)送一位0或1，標(biāo)簽中與接收的位相同的才會發(fā)生應(yīng)答，并發(fā)送自己的下一位直至所有ID序列號傳完。標(biāo)簽中與接收到的位不相同的就會轉(zhuǎn)到待機狀態(tài)，直到某個標(biāo)簽被識別剩余的標(biāo)簽重置。在一個識別過程中，如果閱讀器發(fā)現(xiàn)沖突就會發(fā)0，否則發(fā)送從標(biāo)簽接收的那一位作為下一個查詢位。1.2 查詢樹防碰撞協(xié)議查詢樹算法是一種無記憶標(biāo)簽防碰撞算法。讀寫器發(fā)送一個前綴查詢信息，與這個前綴相匹配的標(biāo)簽做出響應(yīng)。讀寫器發(fā)出的前綴決定了碰撞的標(biāo)簽如何分

6、裂。標(biāo)簽除了其自身的ID號以外無需記憶其他額外的信息。一旦一個標(biāo)簽被成功識別，讀寫器就開始新一輪的讀取操作。協(xié)議原理：讀寫器發(fā)送長度為k的前綴；ID中前k bit和前綴匹配的標(biāo)簽反饋第(k+1)bit至最后1 bit。如果閱讀器收到的ID碰撞，再先后將前綴加“0”或 “1”，作為新的前綴發(fā)送出去。如果沒有發(fā)生碰撞，就表明有一個標(biāo)簽被識別了。2.RFID中防碰撞算法本文主要研究基于時分多址技術(shù)的防碰撞協(xié)議，這些協(xié)議根據(jù)是由閱讀器驅(qū)動還是標(biāo)簽驅(qū)動可以分為閱讀器先發(fā)言(reader-talk-first，RTF)和標(biāo)簽先發(fā)言(tag-talk-first，TTF)，其中用得最廣泛的是RTF，而基于R

7、TF有兩種防碰撞算法，即Aloha算法和基于二進(jìn)制樹的算法。2.1基于Aloha的算法2.1.1純AlohaAloha算法是一種隨機接入方法，其基本思想是采取標(biāo)簽先發(fā)言的方式，當(dāng)標(biāo)簽進(jìn)入閱讀器的識別區(qū)域時自動向讀寫器發(fā)送其自身的ID號，在標(biāo)簽數(shù)據(jù)的過程中，若有其他標(biāo)簽也在發(fā)送數(shù)據(jù)，那么發(fā)生信號重疊導(dǎo)致完全沖突或部分沖突，讀寫器檢測接收到的信號是否發(fā)生沖突，一旦發(fā)生沖突，讀寫器就發(fā)送命令讓標(biāo)簽停止發(fā)送，隨機等待一段時間后再重新發(fā)送以減少沖突。在純Aloha算法中，存在部分碰撞和完全碰撞的問題。它有如下3種工作狀態(tài)關(guān)斷。在協(xié)議中用Muting命令時，成功識別一個標(biāo)簽就會讓在閱讀器識別范圍標(biāo)簽總數(shù)目

8、減，減少閱讀器的負(fù)載。當(dāng)兩個標(biāo)簽同時發(fā)送數(shù)據(jù)時就會發(fā)生碰撞，隨機等待一段時間再重新發(fā)送。當(dāng)系統(tǒng)成功識別后，閱讀器發(fā)送Muting命令讓標(biāo)簽處于“沉默”狀態(tài)。減慢標(biāo)簽信息發(fā)送速度。在這種工作模式下，主要降低數(shù)據(jù)的傳輸速率，這樣能減少碰撞的幾率。載波監(jiān)聽。當(dāng)閱讀器偵測到一個標(biāo)簽開始傳送數(shù)據(jù)時，會發(fā)送一個“Silence”命令。目的是阻止其他標(biāo)簽傳送數(shù)據(jù)，直到閱讀器發(fā)送“ACK”或標(biāo)簽等待時間到時，標(biāo)簽重新傳送數(shù)據(jù)。其他結(jié)合Fast Mode和Muting、PA with and Fast Mode和Slow Down各自的特性組成另外兩種工作模式。由于純Aloha算法存在著部分碰撞現(xiàn)象，因此其碰撞

9、概率很大，適用于閱讀器只負(fù)責(zé)接收標(biāo)簽發(fā)射的信號，而標(biāo)簽只負(fù)責(zé)向閱讀器發(fā)射信號的情況。2.1.2時隙Aloha在時隙Aloha算法中，標(biāo)簽數(shù)據(jù)傳輸只在每個時隙的起始，因此它只會發(fā)生，不會發(fā)生部分碰撞。時隙Aloha算法有如下幾種工作狀態(tài)。Muting/Slow Down。作用相似于在純Aloha算法中的作用，只是運行在單個時隙中.Early End。當(dāng)在這個時隙沒有檢測到有數(shù)據(jù)傳送時，閱讀器馬上關(guān)閉該時。在這個工作模式中，有兩個命令應(yīng)用：第一，Start-of-Frame(SOF)開始一個閱讀循環(huán)；第二，End of-Frame(EOF)關(guān)閉一個空閑的時隙。Early End and Mutin

10、g。成功識別標(biāo)簽后，閱讀器發(fā)送Mute命令減少需要識反之，在一個短暫時間內(nèi)偵測到?jīng)]有數(shù)據(jù)傳輸，閱讀器就發(fā)出EOF命令終止這個。Slow Down and Early End。提前結(jié)束狀態(tài)時間?？偟膩碚f，F(xiàn)ast Mode僅用于與純Aloha結(jié)合，Early End用在時隙算法中，目的是減少對已經(jīng)終止的時隙的檢測，Muting和Slow Down能有效地減少閱讀器的負(fù)載。在時隙算法中，完全Aloha算法中的部分碰撞，提高了信道的利用率。但是這種算法需要一個時鐘使閱讀器閱讀區(qū)域內(nèi)的所有標(biāo)簽時隙同步，這相應(yīng)地提高了設(shè)備的成本，并且標(biāo)簽數(shù)目遠(yuǎn)遠(yuǎn)大于時隙時，標(biāo)簽碰撞機率就會大大增加，造成標(biāo)簽識別時延。2

11、.1.3 FSA幀時隙 Aloha (framed slotted Aloha，F(xiàn)SA)算法是在時隙Aloha算法的基礎(chǔ)上，把N個時隙組成一幀，標(biāo)簽在每個幀內(nèi)隨機選擇一個時隙發(fā)送數(shù)據(jù)，適用于傳輸信息量較大的場合，與時隙Aloha算法相同，其也需要一個同步開銷，但只需要每個幀同步就可以了，相對于時隙Aloha算法，其同步開銷更少。基于RFID的PA和SA有很快的響應(yīng)速度，隨之帶來的也是很高的碰撞幾率，因為在一個時隙中，多個標(biāo)簽都可以在每個時隙開始的時候傳輸數(shù)據(jù)。在FSA算法中，只在每個幀開始時傳送一次數(shù)據(jù)，這會大大降低標(biāo)簽碰撞的幾率.2.1.4 DFSADFSA動態(tài)幀時隙Aloha(DFSA)算

12、法是FSA算法的一種改進(jìn)算法，也是在RFID應(yīng)用中防碰撞算法應(yīng)用得最多的算法之一。在DFSA算法中，每幀中的時隙數(shù)都是動態(tài)的，因此解決了FSA算法的時隙浪費和不足問題，與FSA算法的不同之處在于其每次循環(huán)都會利用一個標(biāo)簽估計函數(shù)來修改幀的大小。動態(tài)幀時隙Aloha算法中的標(biāo)簽估計函數(shù)是基于閱讀器反饋的空時隙數(shù)(c0)、成功時隙數(shù)(c1)和碰撞時隙數(shù)(ck)計算下個識別循環(huán)需要的時隙數(shù)。理論上，當(dāng)估計的時隙數(shù)等于標(biāo)簽的數(shù)目時，標(biāo)簽識別的效率最高。2.2基于二進(jìn)制樹的算法2.2.1 二進(jìn)制搜索算法基本思想是將處于碰撞的標(biāo)簽分成左右兩個子集0和1，先查詢子集0，若沒有碰撞，則正確識別標(biāo)簽，若還碰撞則

13、再次分裂，直到識別完所有標(biāo)簽；同理，查詢子集1。在RFID系統(tǒng)中，要實現(xiàn)這種防碰撞算法，需要一系列的命令Request ； Select ； Read Data ； Unselect；2.2.2 動態(tài)二進(jìn)制搜索算法在實踐中標(biāo)簽的序列號不像上例中那樣僅由1byte組成，而是按系統(tǒng)的規(guī)?？赡荛L達(dá)10byte，以致不得不傳輸大量的數(shù)據(jù)，而僅僅是選擇一個單獨的標(biāo)簽。傳輸?shù)男蛄刑柕母髯曰パa的部分是多余的，也是不必傳輸?shù)摹Ｓ纱说贸鲆环N最佳的算法：代替序列號在兩個方向上完整地傳輸，序列號或搜索的范圍標(biāo)準(zhǔn)的傳輸現(xiàn)在簡單地改變?yōu)椴糠治唬╔）。閱讀器在Request（請求）命令中只發(fā)送要搜索的序列號的已知部分NX

14、作為搜索的依據(jù)，然后中斷傳輸。所有在NX位中的序列號與搜索依據(jù)相符的標(biāo)簽，則傳輸?shù)男蛄刑柕氖Ｓ喔魑患磝-1位為應(yīng)答。在Request命令中的附加參數(shù)（有效位的編號）將余下各位的數(shù)量通知標(biāo)簽。2.2.3后退式二進(jìn)制搜索算法這個算法的策略是不斷縮小搜索的范圍來識別標(biāo)簽。相對于前面兩種算法減少了時間的復(fù)雜度，即識別N個標(biāo)簽，閱讀器共需要問詢2N-1次，平均問詢次數(shù)為2次。實現(xiàn)方法：碰撞發(fā)生時，根據(jù)碰撞的最高位，跳躍式向前搜索；無碰撞時，采取后退策略，能夠快速地識別所有標(biāo)簽22,23，減少標(biāo)簽識別的循環(huán)次數(shù)，但標(biāo)簽ID傳輸時間和二進(jìn)制傳輸時間是一樣的。從上面幾種算法可以看出，二進(jìn)制算法及基于二進(jìn)制改進(jìn)的算法都可以減少標(biāo)簽數(shù)據(jù)和搜索循環(huán)次數(shù)，以此來減少識別時延。結(jié)束語從上面的分析可知，當(dāng)標(biāo)簽數(shù)目不是很多且對實時性要求不是很高時，可以采用Aloha算法和由它改進(jìn)的算法，因為這種算法實現(xiàn)簡單，成本較低；當(dāng)標(biāo)簽數(shù)量很多時，Aloha算法的信道利用率迅速降低，這時就可以采用二進(jìn)制算法及由它改進(jìn)的一些算法。從上面的比較可知，這幾種算法暴露信息很多，安全性很差，因此未來的防碰撞算法應(yīng)該在不增加成本的基礎(chǔ)上，提高標(biāo)簽識別的效率和數(shù)據(jù)信息的安全性。參考文獻(xiàn)1.Rfidinfo.中國RFID市場首次突破120億規(guī)模.2 譚民，劉禹，曾雋芳,等.RFID技術(shù)系統(tǒng)工程及應(yīng)用指南M.北京:機械工業(yè)出版社，