《防碰撞機制分析與實現》

一、教學內容的引入二、產生碰撞的原因三、防碰撞機制的實現主要內容四、讀寫器防碰撞機制的實現一、教學內容的引入

澳洲RECALL公司，稽查文件，多個文件箱同時通過閘門讀寫器，如何正確識別？二、產生碰撞的原因在RFID系統應用中，因為多個讀寫器或多個標簽，造成的讀寫器之間或標簽之間的相互干擾，統稱為碰撞。1什么是碰撞1、讀寫器碰撞2、標簽碰撞2碰撞的類型Data1Data5Data4Data3Data5Data4Data3Data2Data2Data1RFID數據碰撞示意圖二、產生碰撞的原因TimeTime完全碰撞Time讀寫器TagATagBtag1閱讀器tag2tag3tag4tag5多標簽碰撞二、產生碰撞的原因一個讀寫器的讀寫范圍內有多個標簽存在，發生通信沖突。二、產生碰撞的原因R1RrRrReader2Reader1讀寫器-讀寫器頻率干擾

R1為Reader1的干擾范圍

Rr為Reader1和Reader2的讀取范圍

從標簽T反射到讀寫器Reader2的信號很容易被從Reader1發出的信號干擾。Tag二、產生碰撞的原因Tag3Tag2Tag1Reader1Reader2多讀寫器一標簽干擾

標簽1接收到的信息為兩個讀寫器發射信號的矢量和,是一個未知信號。

如何解決碰撞的問題呢？三、防碰撞機制的實現三、防碰撞機制的實現讀寫器Tag3Tag5Tag2Tag6Tag4Tag7Tag11、空分多址SDMA法1、空間分割多重存取ReaderTagTagTag三、防碰撞機制的實現

分離的空間范圍內重新使用確定的資源（通信容量）1、自適應SDMA，電子控制定向天線，天線的方向直接對準某個標簽2、減少單個讀寫器的作用范圍三、防碰撞機制的實現讀寫器Tag1Tag3Tag5Tag4Tag2閱讀器廣播命令閱讀器讀寫區域f1f2f3f4f52、頻分多址FDMA法2、頻率分割多重存取ReaderTagTagTagabcabc三、防碰撞機制的實現

把若干個使用不同載波頻率的傳輸通路同時供給通信用戶使用。3、時間分割TDMAa’b’c’abcReaderTag1Tag2Tag3a’ab’bc’c三、防碰撞機制的實現TDMA是把整個可供使用的信道容量按時間分配給多個同戶的技術。(1).純-ALOHA(PureALOHA)法即標簽只要有數據發送請求就立即發送出去，而不管無線信道中是否已有數據在傳輸。它是無線網絡中最早采用的多址技術，也是最為簡單的一種方法。在RFID系統中，這種方法僅適用于只讀標簽(Readonlytag)。ALOHA系統所采用的多址方式基于TDMA，是一種無規則的時分多址，或者叫隨機多址。用于實時性不高的場合。1防碰撞的基本算法ALOHA基本思想很簡單：當用戶想要發送數據幀時，它就可以在任何時候發送。有可能發生沖突。沖突導致傳輸不成功。得不到確認或者本身偵聽到錯誤。等待隨機長時間重發。通信量越大，碰撞的可能性也越大。主要特點是各個標簽發射時間不需要同步，是完全隨機的，實現起來比較簡單。當標簽不多時它可以很好的工作。缺點就是數據幀發送過程中碰撞發生的概率很大。經過分析，ALOHA法的最大吞吐率只有18.4％，80％以上的信道容量沒有被利用。對于較小的數據包量，無線信道的大部分時間沒有被利用，而隨著數據包量的增加，標簽碰撞的概率又會明顯增加。（2）．時隙ALOHA法為了提高接入系統的吞吐量，可將時間劃分為一段段等長的時隙，記為T0。規定數據幀只能在時隙的開始才能發送出去。如果一個時隙內只有一個站點到達，則該分組會傳輸成功；如果有多于一個的分組到達，將會發生碰撞。和純ALOHA一樣，發生碰撞后，各標簽仍是經過隨機時延后分散重發的。如果有許多標簽處于閱讀器的作用范圍內，在最不利的情況下，經過多次搜索也可能沒有發現序列號，因為沒有唯一的標簽能單獨處于一個時隙之中而發送成功。因此，需要準備足夠大量的時隙，這樣做法降低了防碰撞算法的性能。算法

ISO18000-6協議中使用的是一種二進制樹形防碰撞算法，通過標簽內隨機產生0、1及內置計數器實現標簽的防碰撞。2防碰撞的基本算法——二進制碰撞算法三、防碰撞機制的實現樹分叉算法沖突節點非沖突節點011011100101樹分叉算法三、防碰撞機制的實現基本思想是：將處于碰撞的標簽分成左右兩個子集0和1，先查詢子集0，若沒有碰撞，則正確識別標簽，若仍有碰撞則分裂，把1子集分成10和11兩個子集，直到識別子集1中所有標簽?；诼鼜厮固鼐幋a信號的Manchester編碼可以讓讀寫器準確地判斷出數據碰撞的比特位置，2防碰撞的基本算法——二進制搜索算法（1）REQUEST——請求(序列號)。此命令發送一序列號作為參數給射頻卡。應答規則是，射頻卡把自己的序列號與接收到的序列號比較，如果自身序列號小于或等于REQUEST指令序列號參數，則此射頻卡回送其序列號給讀寫器。這樣可以縮小預選的射頻卡的范圍；如果大于，則不響應。當進入“識別”有多個標簽----防碰撞指令規則

三、防碰撞機制的實現

所有接收到FAIL指令且內部計數器不等于0的標簽計數器加1。所有接收到FAIL指令且內部計數器等0的標簽將產生一個1或者0的隨機數，如果是1，則標簽計數器加1，如果是0，則標簽計數器保持不變，并再次發送其識別碼。

(2)SELECT——選擇(序列號)。用某個(事先確定的)序列號作為參數發送給射頻卡。具有相同序列號的射頻卡將以此作為執行其他命令(例如讀出和寫入數據)的切入開關，即選擇這個射頻卡。具有其他序列號的射頻卡只對REQUEST命令應答。

（3）READ-DATA——讀出數據。選中的射頻卡將存儲的數據發送給讀寫器。

當進入“識別”有多個標簽----防碰撞指令規則

三、防碰撞機制的實現

(4)UNSELECT

——取消選擇。取消一個事先選中的射頻卡，射頻卡進入"無聲"狀態，在這種狀態下射頻卡完全是非激活的，對收到的REQUEST命令不作應答。為了重新話化射頻卡，必須先將射頻卡移出讀寫器的作用范圍再進入，以實行復位。

射頻卡進入讀寫器的工作范圍，讀寫器發出一個最大序列號讓所有射頻卡響應；同一時刻開始傳輸它們的序列號到讀寫器的接收模塊。讀寫器對比射頻卡響應的序列號的相同位數上的數。出現不一致的現象即有的序列號該位為0，而有的序列號該位為1把有不一致位的數從最高位到低位依次置O再輸出系列號，即依次排除序列號大的數，至讀寫器對比射頻卡響應的序列號的相同位數上的數完全一致時，說明無碰撞。選出序列號最小的數后，對該標簽進行數據交換，然后使該卡進入“無聲”狀態。YN三、防碰撞機制的實現二進制搜索算法的工作流程是：101100001110??????射頻卡1射頻卡2讀寫器譯碼三、防碰撞機制的實現

在二進制搜索算法的實現中，起決定作用的是讀寫器所使用的信號編碼必須能夠確定碰撞的準確比特位置。曼徹斯特碼(Mancherster)可在多卡同時響應時，譯出錯誤碼字，可以按位識別出碰撞。這樣可以根據碰撞的位置，按一定法則重新搜索射頻卡。范例：二元搜尋算法A:10100111B:10110101C:10101111D:10111101R:11111111R:11111111送REQUEST（11111111）命令，要求區域內所有標簽應答，根據曼徹斯特編碼，解碼數據為101??1?1,發生碰撞，算法做下如下，將碰撞的最高置0，其它碰撞位置1。得下次的REQUEST(10101111)???R表示閱讀器三、防碰撞機制的實現范例：二元搜尋算法搜尋標簽過程A:10100111C:10101111R:10101111R:10101111送REQUEST（10101111）命令，標簽A和C應答。解碼數據為1010?111,發生碰撞，算法做下如下，將碰撞的最高置0，其它碰撞位置1。得10100111?R表示閱讀器三、防碰撞機制的實現范例：二元搜尋算法A:10100111C:10101111R:10100111R:10100111送REQUEST（10100111）命令，只有標簽A應答。沒有發生碰撞，閱讀器對標簽A進行閱讀操作。R表示閱讀器可以識別A三、防碰撞機制的實現ImprovedAnti-collisionAlgorithm搜尋過程第一次搜尋第二次搜尋第三次搜尋第四次搜尋第五次搜尋發送序號接收序號TagATagBTagCTagD三、防碰撞機制的實現1010011110110101101011111011110111111111101??1?11010111110100111101011111010?1111010011110100111識別TagA10110101101011111011110111111111101??1?11010111110101111識別TagCImprovedAnti-collisionAlgorithm搜尋過程第六次搜尋第七次搜尋第八次搜尋第九次搜尋第十次搜尋發送序號接收序號TagATagBTagC

TagD三、防碰撞機制的實現1011010110111101111111111011?10110110101101101011011110110111101識別TagB識別TagD采用二進制樹形搜索算法的RFID系統特點是：具有較高的穩定性，屬于TDMA方式，易于用軟件實現，吞吐率最高可達36．4％。但ID不能太長，ID越長所需要的時間就越長，當時間超過一定限度時，這種算法將不再適用。動態二進制樹搜索算法標簽的ID達到幾個字節以上時，不但不能在有效的時間內正確識別出標簽，還會增加系統的負擔，考慮采用動態二進制算法。一般說來，ID總有相同的高位，假設20個ID中有5個的最高三位是相同的，REQUEST先發送這相同的高三位就可以先處理這五個ID，再處理其他的ID，這種已知部分ID動態查詢ID的方法就是動態二進制算法。采用動態二進制樹搜索算法的RFID系統特點是：隨機性小，準確率高，吞吐率大，穩定性好。1、RFID讀寫器沖突及解決途徑

密集讀寫器環境中的讀寫器沖突四、讀寫器防碰撞機制的實現密集讀寫器環境就是指在RFID系統應用中，在預定區域內部署多個RFID讀寫器，以滿足對區域內的所有標簽進行完全的、高可靠的讀取要求。系統網絡中包含多個讀寫器和一個中央計算機，讀寫器與中央計算機之間一般采用局域網（LAN）或無線局域網（WLAN）方式進行通信連接。密集讀寫器網絡拓樸結構分時傳輸解決讀寫器沖突

網絡中的每個讀寫器通常具有不同范圍的識讀區域，各讀寫器的識讀區域可能有交集，即識讀區域有相互重疊的部分。為了便于說明，用圖7-17近似地描繪了密集讀寫器環境下的讀寫器沖突。每個圓圈代表一個讀寫器的識讀區域（實際應用中的識讀區域可能為不規則形狀），圓點代表相應的讀寫器。如果兩個讀寫器的識讀區域有相互重疊，如圖7-17中的R1和R2，則當R1、R2同時工作時，如果不采取防沖突措施，就會產生讀寫器沖突，甚至使整個RFID系統無法正常工作。

四、讀寫器防碰撞機制的實現密集環境下讀寫器沖突示意圖解決讀寫器沖突

Colorwave算法：

該算法是一種分布式的TDMA算法，通過給閱讀器分配不同的時隙來避免閱讀器之間的碰撞。該算法需要所有閱讀器之間時間同步，還要求所有閱讀器都可以檢測RFID系統中的碰撞。四、讀寫器防碰撞機制的實現Q．Learing算法：——Q．Learing算法是一個分等級的，在線學習算法?！喿x器發送碰撞信息給閱讀器等級服務器(R—sever)。一個獨立的R—server給閱讀器分配資源，用這個方法使閱讀器的通信之間