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

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

2、統(tǒng)讀取效率的關鍵問題。導致標簽識別效率的降低和資源的浪費。本文介紹了兩種防碰撞協(xié)議的性能。指出其優(yōu)缺點和研究進展情況。關鍵詞：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)中防碰撞算法為了解決碰撞問題，產生了很多的防碰撞算法，目的就是把眾多的標簽按照某種方式分隔開進行逐個讀取，主要有頻分多路法(FDMA)、空分多路法(SDMA)、時分多路法(TDMA)和碼分多路法(CDMA)四種方法。防碰撞算法結構圖如圖所示防碰撞算法二進制樹Q

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

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

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

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

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

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

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

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

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

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

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