1、1第第10章章 射頻識別技術碰撞算法、標射頻識別技術碰撞算法、標準、安全、中間件及解決方案準、安全、中間件及解決方案l射頻識別的一個優點就是多個目標識別。在射頻識別系統工作時，在讀射頻識別的一個優點就是多個目標識別。在射頻識別系統工作時，在讀頭的作用范圍內，可能會有多個應答器同時存在。對于射頻識別系統中頭的作用范圍內，可能會有多個應答器同時存在。對于射頻識別系統中存在的不同通信形式一般有三種。存在的不同通信形式一般有三種。l第一種是第一種是“無線廣播無線廣播式，式，即在一個閱讀器的閱讀范圍內存在多個應答即在一個閱讀器的閱讀范圍內存在多個應答器，閱讀器發出的數據流同時被多個應答器接收。這可以同數

2、百個電子器，閱讀器發出的數據流同時被多個應答器接收。這可以同數百個電子標簽同時接收一個發送信息類似，而信息是由一個閱讀器發射的。標簽同時接收一個發送信息類似，而信息是由一個閱讀器發射的。無線電廣播工作無線電廣播工作2l第二種是在閱讀器的作用范圍有多個應答器同時傳輸數據給閱讀器第二種是在閱讀器的作用范圍有多個應答器同時傳輸數據給閱讀器，這種通信形式稱為這種通信形式稱為多路存取通信。多路存取通信。閱讀器的多路存儲閱讀器的多路存儲5、RFID讀寫器防沖撞實理機理讀寫器防沖撞實理機理 35、RFID讀寫器防沖撞實理機理讀寫器防沖撞實理機理l第三種是多個閱讀器同時給多個應答器發送數據。第三種是多個閱讀器

3、同時給多個應答器發送數據。現在射頻現在射頻識別系統中這種情況很少遇到，我們常常遇到識別系統中這種情況很少遇到，我們常常遇到“多路存取多路存取”這這種通信方式。種通信方式。l每個通信通路有規定的通路容量。這種通路容量是由這個通每個通信通路有規定的通路容量。這種通路容量是由這個通信通路的最大數據率以及供給它使用的時間片確定的。分配信通路的最大數據率以及供給它使用的時間片確定的。分配給每個應答器的通路容量必須滿足：當多個應答器同時把數給每個應答器的通路容量必須滿足：當多個應答器同時把數據傳輸給一個單獨的閱讀器時不能出現互相干擾（碰撞）。據傳輸給一個單獨的閱讀器時不能出現互相干擾（碰撞）。4l無線電通

4、信系統中多路存取方式一般具有以下幾種形式：空分多路法無線電通信系統中多路存取方式一般具有以下幾種形式：空分多路法（SCDMA）、時分多路法（）、時分多路法（TDMA）、頻分多路法（）、頻分多路法（FDMA）和碼分多路法）和碼分多路法（CMDA）。）。l1）空分多路法（）空分多路法（SCDMA）l空分多路法是在空分多路法是在分離的空間范圍內進行多個目標識別的技術分離的空間范圍內進行多個目標識別的技術。一種方式是將讀。一種方式是將讀頭和天線的作用距離按空間區域進行劃分，把多個閱讀器和天線放置在這個陳頭和天線的作用距離按空間區域進行劃分，把多個閱讀器和天線放置在這個陳列中。這樣，當標簽進入不同的閱讀

5、器范圍時，就可以在空間上將標簽區別開列中。這樣，當標簽進入不同的閱讀器范圍時，就可以在空間上將標簽區別開來。來。l另一種方式是在閱讀器上利用一個相陣天線，并使天線的方向性圖對準某個應另一種方式是在閱讀器上利用一個相陣天線，并使天線的方向性圖對準某個應答器。不同應答器可以根據其在閱讀范圍內的角度位置區別開來。答器。不同應答器可以根據其在閱讀范圍內的角度位置區別開來。l該方法的該方法的缺點是復雜的天線系統和相當高的實施費用缺點是復雜的天線系統和相當高的實施費用，因此采用這種技術的系統，因此采用這種技術的系統一般在一些特殊應用場合，如這種方法在大型的馬拉松活動中就獲得了成功。一般在一些特殊應用場合，

6、如這種方法在大型的馬拉松活動中就獲得了成功。5、RFID讀寫器防沖撞實理機理讀寫器防沖撞實理機理55、RFID讀寫器防沖撞實理機理讀寫器防沖撞實理機理l2）頻分多路法（）頻分多路法（FDMA）l而對于上行鏈路（從標簽到讀頭），射頻標簽可以采用不同的、獨立的而對于上行鏈路（從標簽到讀頭），射頻標簽可以采用不同的、獨立的負載頻率進行數據傳輸（如負載頻率進行數據傳輸（如433435kHz頻率范圍內的若干個頻率）。頻率范圍內的若干個頻率）。l該方法的一個該方法的一個缺點是閱讀器的成本高，因為每個接收通路必須有自己缺點是閱讀器的成本高，因為每個接收通路必須有自己的獨立的接收器，射頻標簽的差異更為麻煩。的

7、獨立的接收器，射頻標簽的差異更為麻煩。因此，這種防碰撞方法因此，這種防碰撞方法只限制在少數幾個特殊的應用上。只限制在少數幾個特殊的應用上。l頻分多路法是提供若干個不同載波頻率的傳輸通路同時給通信用戶使頻分多路法是提供若干個不同載波頻率的傳輸通路同時給通信用戶使用的技術。一般情況下，這種射頻識別系統采用的下行鏈路（從讀頭用的技術。一般情況下，這種射頻識別系統采用的下行鏈路（從讀頭到標簽）的頻率是固定的（如到標簽）的頻率是固定的（如125kHz），用于能量供應和命令數據），用于能量供應和命令數據的傳輸。的傳輸。65、RFID讀寫器防沖撞實理機理讀寫器防沖撞實理機理l3）時分多路法（）時分多路法（T

8、DMA）l時分多路法（時分多路法（TDMA）是把整個可供使用的通道容量按時間分配給多個用戶的）是把整個可供使用的通道容量按時間分配給多個用戶的技術。技術。TDMA首先在數字移動系統范圍內推廣使用。對射頻識別系統來說，首先在數字移動系統范圍內推廣使用。對射頻識別系統來說，TDMA構成了防碰撞算法的最大一族。這種方法又可分為構成了防碰撞算法的最大一族。這種方法又可分為標簽控制法和讀頭控標簽控制法和讀頭控制法制法，如下圖所示。，如下圖所示。l標簽控制法的工作標簽控制法的工作是非同步的，因為這里沒有讀頭的數據傳輸控制，例如是非同步的，因為這里沒有讀頭的數據傳輸控制，例如ALOHA法。按照應答器成功完成

9、數據傳輸后是否將通過閱讀器的信號斷開，法。按照應答器成功完成數據傳輸后是否將通過閱讀器的信號斷開，又可區分為又可區分為“開關斷開開關斷開法和法和“非開關非開關法法。l在讀頭控制法中在讀頭控制法中，所有的射頻標簽同時由讀頭進行觀察和控制。通過一種規定，所有的射頻標簽同時由讀頭進行觀察和控制。通過一種規定的算法，在讀頭作用范圍內，首先在選擇的標簽組中選中一個標簽，然后完成的算法，在讀頭作用范圍內，首先在選擇的標簽組中選中一個標簽，然后完成讀頭和標簽之間的通訊（如識別、讀出和寫入數據）。在同一時間只能建立一讀頭和標簽之間的通訊（如識別、讀出和寫入數據）。在同一時間只能建立一個通訊關系，所以如果要選擇

10、另外一個標簽，就應該解除與原來標簽的通訊關個通訊關系，所以如果要選擇另外一個標簽，就應該解除與原來標簽的通訊關系。讀頭控制法可以進一步劃分為系。讀頭控制法可以進一步劃分為輪詢法和二進制搜索法。輪詢法和二進制搜索法。75、RFID讀寫器防沖撞實理機理讀寫器防沖撞實理機理l輪詢法輪詢法需要一個所有可能用到標簽的序列號清單。讀頭依次詢問所需要一個所有可能用到標簽的序列號清單。讀頭依次詢問所有的序列號，直到詢問到某個有相同序列號的射頻標簽響應為止。有的序列號，直到詢問到某個有相同序列號的射頻標簽響應為止。然而，這個過程依賴于標簽的數量，然而，這個過程依賴于標簽的數量，只適用于作用區內僅有幾個已只適用于

11、作用區內僅有幾個已知的射頻標簽的場合。知的射頻標簽的場合。l最靈活的和應用最廣泛的是使用最靈活的和應用最廣泛的是使用二進制搜索法二進制搜索法。對這種方法來說，為。對這種方法來說，為了從一組標簽中選擇其中之一，讀頭要發出一個請求命令。讀頭通過了從一組標簽中選擇其中之一，讀頭要發出一個請求命令。讀頭通過合適的信號編碼，能夠確定發生碰撞的準確的比特位置，從而對電子合適的信號編碼，能夠確定發生碰撞的準確的比特位置，從而對電子標簽返回的數據作出進一步判斷，發出另外的請求命令，最終確定讀標簽返回的數據作出進一步判斷，發出另外的請求命令，最終確定讀頭作用范圍內的所有標簽。頭作用范圍內的所有標簽。l二進制搜索

12、法的二進制搜索法的缺點就是標簽的識別碼的識別速率較低。缺點就是標簽的識別碼的識別速率較低。85、RFID讀寫器防沖撞實理機理讀寫器防沖撞實理機理l目前所有面向目前所有面向RFID系統應用的系統應用的TDMA方式的防碰撞算法研究可以被歸結方式的防碰撞算法研究可以被歸結為兩大類：為兩大類：l一類是隨機性或稱概率性的防碰撞算法，一類是隨機性或稱概率性的防碰撞算法，這類算法大都基于這類算法大都基于ALOHA機機制，例如，純制，例如，純ALOHA，時隙，時隙ALOHA，幀時隙，幀時隙ALOHA，動態幀時隙，動態幀時隙ALOHA算法等；算法等；l另一類是確定性的防碰撞算法另一類是確定性的防碰撞算法，確定性

13、算法是閱讀器根據標簽序列號的，確定性算法是閱讀器根據標簽序列號的惟一性選擇標簽進行通信，確定性的防碰撞算法都屬于二進制搜索算惟一性選擇標簽進行通信，確定性的防碰撞算法都屬于二進制搜索算法，最簡單的確定性算法是二進制樹機制。法，最簡單的確定性算法是二進制樹機制。l現階段，在高頻頻段現階段，在高頻頻段，標簽的防碰撞算法一般采用，標簽的防碰撞算法一般采用ALOHA相關協議。使相關協議。使用用ALOHA協議的標簽，通過選擇經過一個隨機時間向閱讀器傳送信息的協議的標簽，通過選擇經過一個隨機時間向閱讀器傳送信息的方法，來避免沖突，絕大多數高頻閱讀器能同時掃描幾十個電子標簽。方法，來避免沖突，絕大多數高頻閱

14、讀器能同時掃描幾十個電子標簽。l在超高頻頻段在超高頻頻段，現在的主要研究趨向是采用樹分叉搜索算法來防沖突。，現在的主要研究趨向是采用樹分叉搜索算法來防沖突。9l在在RFID無源標簽系統中，目前廣泛使用的防沖突算法大都是無源標簽系統中，目前廣泛使用的防沖突算法大都是TDMA（Time Division Multiple Access），主要分為），主要分為2大類：基于大類：基于Aloha的算法和基于樹的算法和基于樹的算法。的算法。 （1） ALOHA算法算法 l1）純）純Aloha算法算法是一種隨機接入方法，其基本思想是采取是一種隨機接入方法，其基本思想是采取標簽先發言的方標簽先發言的方式式，當

15、標簽進入讀寫器的識別區域內就自動向讀寫器發送其自身的，當標簽進入讀寫器的識別區域內就自動向讀寫器發送其自身的ID號，號，標簽1標簽2信道部分沖突完全沖突標簽3l在標簽發送數據的過程中在標簽發送數據的過程中,若有其他標簽也在發送數若有其他標簽也在發送數據，那么發生信號重疊導致據，那么發生信號重疊導致完全沖突或部分沖突，完全沖突或部分沖突，l讀寫器檢測接收到的信號有無沖突，讀寫器檢測接收到的信號有無沖突，一旦發生沖突，讀寫器就發送命令讓標簽一旦發生沖突，讀寫器就發送命令讓標簽停止發送，隨機等待一段時間后再重新發送以減少沖突停止發送，隨機等待一段時間后再重新發送以減少沖突。Aloha算法模型圖如算法

16、模型圖如圖所示。圖所示。10l純純Aloha算法雖然算法簡單，易于實現，但是存在一個嚴重的問題就算法雖然算法簡單，易于實現，但是存在一個嚴重的問題就是讀寫器對同一個標簽，是讀寫器對同一個標簽，如果連續多次發生沖突，這將導致讀寫器出如果連續多次發生沖突，這將導致讀寫器出現錯誤判斷認為這個標簽不在自己的作用范圍。現錯誤判斷認為這個標簽不在自己的作用范圍。（1） ALOHA算法算法l同時還存在另外一個問題其同時還存在另外一個問題其沖突概率很大沖突概率很大，假設其數據幀為，假設其數據幀為F，則沖突周，則沖突周期為期為2F。針對以上問題有人提出了多種方案來改善。針對以上問題有人提出了多種方案來改善Alo

17、ha算法在算法在RFID系系統其可行性和識別率，統其可行性和識別率，l2） 時隙時隙ALOHA算法算法 l在在Aloha算法中，標簽通過循環序列傳輸數據。標簽數據的傳輸時間僅僅算法中，標簽通過循環序列傳輸數據。標簽數據的傳輸時間僅僅為循環時間的一個小片段。為循環時間的一個小片段。在第一次傳輸數據完成后，標簽將等待一個在第一次傳輸數據完成后，標簽將等待一個相對較長的時間后再次傳輸數據。相對較長的時間后再次傳輸數據。每個標簽的等待時間很小。每個標簽的等待時間很小。 11（1） ALOHA算法算法l按照這種方式，所有的標簽完成全部的數據傳輸給讀寫器后，重復的過程才會按照這種方式，所有的標簽完成全部的

18、數據傳輸給讀寫器后，重復的過程才會結束。分析結束。分析Aloha算法的運行機制，算法的運行機制，不難發現當一個標簽發送數據給讀寫器時，不難發現當一個標簽發送數據給讀寫器時，另外一個標簽也開始發送數據給讀寫器，這時標簽數據碰撞不可避免發生。另外一個標簽也開始發送數據給讀寫器，這時標簽數據碰撞不可避免發生。l鑒于以上缺點，研究人員提出鑒于以上缺點，研究人員提出“時隙時隙Aloha算法算法” 。在該算。在該算法中，法中，標簽僅能在時隙的開始傳標簽僅能在時隙的開始傳輸數據輸數據。l用于傳輸數據的時隙數由讀寫器控制，只有當讀寫器分配所有的時隙后，標用于傳輸數據的時隙數由讀寫器控制，只有當讀寫器分配所有的

19、時隙后，標簽才能利用這些時隙傳輸數據。因此與純簽才能利用這些時隙傳輸數據。因此與純Aloha算法不同，算法不同，時隙時隙Aloha算法算法是隨機的詢問驅動的是隨機的詢問驅動的TDMA防沖撞算法。防沖撞算法。12（1） ALOHA算法算法l因為標簽僅僅在確定的時隙中傳輸數據，因為標簽僅僅在確定的時隙中傳輸數據，所以該算法的沖撞發生的頻率僅僅所以該算法的沖撞發生的頻率僅僅是純是純Aloha算法的一半而且系統的數據吞吐性能卻增加一倍。算法的一半而且系統的數據吞吐性能卻增加一倍。 l增加時隙數量可降低增加時隙數量可降低RF終端發生沖突的概率，但是信道大部分時間將處于終端發生沖突的概率，但是信道大部分時

20、間將處于空閑狀態，空閑狀態，使得防沖突識別速度變慢。使得防沖突識別速度變慢。l反之，減少時隙數量導致射頻終端沖突明顯增加。運用時隙算法的關鍵在于反之，減少時隙數量導致射頻終端沖突明顯增加。運用時隙算法的關鍵在于尋找一個有效的折衷方案，尋找一個有效的折衷方案，使得防沖突的可靠性和速度滿足要求。使得防沖突的可靠性和速度滿足要求。l隨著隨著RFID系統復雜程度的加大，防沖突的可靠性顯著降低，沖突不可避免，系統復雜程度的加大，防沖突的可靠性顯著降低，沖突不可避免，所以所以這種沒有檢測恢復機制的抗沖突算法僅適用于簡單系統。這種沒有檢測恢復機制的抗沖突算法僅適用于簡單系統。 13（1） ALOHA算法算法

21、l3） 幀時隙幀時隙ALOHA算法的基本原理算法的基本原理 l雖然時隙雖然時隙Aloha算法提高系統的吞吐量，但是當大量標簽進入系統算法提高系統的吞吐量，但是當大量標簽進入系統時，該算法的效率并不高，因此幀時隙算法被提出。時，該算法的效率并不高，因此幀時隙算法被提出。l幀時隙幀時隙ALOHA（Framed slotted Aloha，FSA）算法是基于通信領）算法是基于通信領域的域的ALOHA協議提出的。協議提出的。l在在FSA中，中，“幀幀”（Frame）是由讀寫器定義的一段時間長度，其中包含）是由讀寫器定義的一段時間長度，其中包含若干時隙。若干時隙。l標簽在每個幀內隨機選擇一個時隙發送數據

22、。所有標簽應答同步，即只能標簽在每個幀內隨機選擇一個時隙發送數據。所有標簽應答同步，即只能在時隙（在時隙（Slot）開始點向讀寫器發送信息，每個標簽發送的時隙是隨機選）開始點向讀寫器發送信息，每個標簽發送的時隙是隨機選擇的。擇的。14（1） ALOHA算法算法l時隙可以分為三類：空閑時隙、應答時隙和碰撞時隙。在空閑時隙中時隙可以分為三類：空閑時隙、應答時隙和碰撞時隙。在空閑時隙中沒有識別任何標簽，應答時隙中可以正確識別一個標簽。當一個時隙沒有識別任何標簽，應答時隙中可以正確識別一個標簽。當一個時隙中有多個標簽同時發送應答時就會產生碰撞，形成碰撞時隙。碰撞的中有多個標簽同時發送應答時就會產生碰撞

23、，形成碰撞時隙。碰撞的標簽退出當前循環，等待參與新的幀循環。標簽退出當前循環，等待參與新的幀循環。 l通常，在幀時隙通常，在幀時隙Aloha防沖撞算法中，防沖撞算法中，當系統標簽數量變得很大時，系統效當系統標簽數量變得很大時，系統效率就開始降低。率就開始降低。15（1） ALOHA算法算法l4） 動態幀時隙動態幀時隙ALOHA算法算法 l在幀時隙在幀時隙Aloha算法中，算法中，所有的幀具有相同的長度，即每一幀中的時所有的幀具有相同的長度，即每一幀中的時隙數是相同的且是固定的。隙數是相同的且是固定的。l由于讀寫器并不知道標簽數量，由于讀寫器并不知道標簽數量，當標簽數量遠大于幀時隙數時當標簽數量

24、遠大于幀時隙數時，一幀，一幀中的所有時隙都會發生碰撞，讀寫器不能讀取標簽信息；中的所有時隙都會發生碰撞，讀寫器不能讀取標簽信息；l當當標簽數遠小于一幀中時隙數時標簽數遠小于一幀中時隙數時，識別過程中將有許多時隙被浪費掉。，識別過程中將有許多時隙被浪費掉。l動態幀時隙算法動態幀時隙算法通過根據識別標簽的數量來改變幀長度來客服動態幀時通過根據識別標簽的數量來改變幀長度來客服動態幀時隙的不足。隙的不足。 16l為了實現這個功能在通信上所采取的技術是（防沖撞）為了實現這個功能在通信上所采取的技術是（防沖撞）“防碰撞防碰撞”。同。同時讀取復數個標簽是常被人們談及的時讀取復數個標簽是常被人們談及的RFID

25、比條形碼遠為優越的地方比條形碼遠為優越的地方，但，但是如果沒有防碰撞是如果沒有防碰撞 （防沖撞）的功能時，（防沖撞）的功能時，RFID系統只能讀寫一個標簽。系統只能讀寫一個標簽。l在這種情況下如果有兩個以上的標簽同時處于可讀取的范圍內就會導在這種情況下如果有兩個以上的標簽同時處于可讀取的范圍內就會導致讀取的錯誤。致讀取的錯誤。l其次，我們來簡單地說明防碰撞（防沖撞）功能的工作原理。即使是其次，我們來簡單地說明防碰撞（防沖撞）功能的工作原理。即使是具有防碰撞（防沖撞）功能的具有防碰撞（防沖撞）功能的RFID系統，系統，實際上并非同時讀取所有標實際上并非同時讀取所有標簽的內容。簽的內容。l在同時查

26、出有復數個標簽存在的情況下，在同時查出有復數個標簽存在的情況下，檢索信號并防止沖突的功能檢索信號并防止沖突的功能開始動作開始動作。為了進行檢索，首先要確定檢索條件。例如，。為了進行檢索，首先要確定檢索條件。例如，13.56MHz頻頻帶的帶的RFID系統里應用的系統里應用的ALOHA方式的防碰撞功能的工作步驟如下。方式的防碰撞功能的工作步驟如下。 （1） ALOHA算法算法17l1）首先，閱讀器指定電子標簽內存的特定位數（）首先，閱讀器指定電子標簽內存的特定位數（14位左右）為次數批量。位左右）為次數批量。l2）電子標簽根據次數批量，將響應的時機離散化。例如在兩位數的次數批量）電子標簽根據次數批

27、量，將響應的時機離散化。例如在兩位數的次數批量“00、01、10、11”時，讀寫器將以不同的時機對這四種可能性逐一進行響時，讀寫器將以不同的時機對這四種可能性逐一進行響應。應。l3）若在各個時機里同時響應的電子標簽只有一個的場合下才能得到這個電子）若在各個時機里同時響應的電子標簽只有一個的場合下才能得到這個電子標簽的正常數據。信息讀取之后閱讀器對于這個電子標簽發送在一定的時間標簽的正常數據。信息讀取之后閱讀器對于這個電子標簽發送在一定的時間內不再響應的睡眠的指令（內不再響應的睡眠的指令（Sleep/Mute）使之在休眠，避免再次向應。）使之在休眠，避免再次向應。（1） ALOHA算法算法18l

28、4）若在各個時機內同時有幾個電子標簽響應，判別為）若在各個時機內同時有幾個電子標簽響應，判別為“沖突沖突”。在這種情。在這種情況下，內存內的另外兩位數所記錄的次數批量，重復以上從況下，內存內的另外兩位數所記錄的次數批量，重復以上從2）開始的處）開始的處理。理。l5）所有的電子標簽都完成響應之后，閱讀器向他們發送喚醒的指令）所有的電子標簽都完成響應之后，閱讀器向他們發送喚醒的指令（Wake Up），從而完成對所有電子標簽的信息讀取。），從而完成對所有電子標簽的信息讀取。（1） ALOHA算法算法19l在這種搭載有防碰撞（防沖撞）功能的在這種搭載有防碰撞（防沖撞）功能的RFID系統中，為了只讀一個

29、標簽，系統中，為了只讀一個標簽，幾經調整次數批量反復讀取進行檢索。所以，一次性讀取具有一定數量的標幾經調整次數批量反復讀取進行檢索。所以，一次性讀取具有一定數量的標簽的情況下，所有的標簽都被讀到為止其速度是不同的，一次性讀取的標簽簽的情況下，所有的標簽都被讀到為止其速度是不同的，一次性讀取的標簽數目越多，完成讀取所需時間要比單純計算所需的時間越長。數目越多，完成讀取所需時間要比單純計算所需的時間越長。l實現防止抗碰撞（防沖撞）的功能是實現防止抗碰撞（防沖撞）的功能是RFID在物流領域中在物流領域中取代條形碼所必不取代條形碼所必不可少的條件。例如，在超市中，商品是裝在購物車里面進行計價的。為了實

30、可少的條件。例如，在超市中，商品是裝在購物車里面進行計價的。為了實現這種計價方式，抗碰撞現這種計價方式，抗碰撞 （防沖撞）功能必須完備。（防沖撞）功能必須完備。l具有抗碰撞（防沖撞）功能的具有抗碰撞（防沖撞）功能的RFID系統的價格比不具有這種功能的系統的系統的價格比不具有這種功能的系統的要昂貴要昂貴。當個人用戶在制作。當個人用戶在制作RFID系統的時候，如果沒有必要進行復數個系統的時候，如果沒有必要進行復數個ID同時認識時就沒有必要選擇抗碰撞機能的讀寫器。同時認識時就沒有必要選擇抗碰撞機能的讀寫器。l另一方面，在電子貨幣和個人認證方面利用另一方面，在電子貨幣和個人認證方面利用RFID系統時，

31、系統時，同時識別幾個標同時識別幾個標簽是發生差錯的主要原因。簽是發生差錯的主要原因。（1） ALOHA算法算法20l（2） 二進制搜索防沖突算法二進制搜索防沖突算法 （2）二進制搜索算法）二進制搜索算法lALOHA算法由于效率低，實際算法由于效率低，實際RFID系統并未采用，而是采用更加高系統并未采用，而是采用更加高效的二進制搜索算法。效的二進制搜索算法。l二進制搜索算法靈活，不會發生防沖突失敗情況。二進制搜索算法靈活，不會發生防沖突失敗情況。l對于對于N個應答器發生沖突的情況，最多個應答器發生沖突的情況，最多只需要只需要N-1次防沖突循環就能準次防沖突循環就能準確識別出適合的應答器。確識別出

32、適合的應答器。l二進制搜索算法的基本思想二進制搜索算法的基本思想是閱讀器判斷出發送應答器的序列號產是閱讀器判斷出發送應答器的序列號產生數據沖突位置。然后強制命令在沖突位置發送信息為生數據沖突位置。然后強制命令在沖突位置發送信息為0或或1的的應答器退出沖突。當應答器退出沖突。當N-1個應答器退出沖突后信道則被剩下的一個應個應答器退出沖突后信道則被剩下的一個應答器完全占有并由閱讀器識別出。答器完全占有并由閱讀器識別出。 21l為了防止數據沖突的發生，首先確定發生沖突為了防止數據沖突的發生，首先確定發生沖突的數據比特位的具體位置。這里使用的數據比特位的具體位置。這里使用Manchester編碼如圖所

33、示。編碼如圖所示。（2）二進制搜索算法）二進制搜索算法l這種編碼通過電平的上升沿和下降沿表示高、低電這種編碼通過電平的上升沿和下降沿表示高、低電平。上升沿為邏輯平。上升沿為邏輯1，下降沿為邏輯，下降沿為邏輯0，不存在，不存在狀態不變的情況。狀態不變的情況。l因此數據傳輸過程中檢測到編碼狀態不跳變，則認為在數據傳輸過程中發生因此數據傳輸過程中檢測到編碼狀態不跳變，則認為在數據傳輸過程中發生了沖突。了沖突。l兩個發生沖突的數據比特位必定有一個為邏輯兩個發生沖突的數據比特位必定有一個為邏輯“0”，另一個為邏輯，另一個為邏輯“1”，這，這樣曼徹斯特碼（樣曼徹斯特碼（Manchester）的上升沿和下降

34、沿相互抵消，使接收器在持續的上升沿和下降沿相互抵消，使接收器在持續時間內接收到狀態持續不變的副載波信號，即出現狀態不跳變時間內接收到狀態持續不變的副載波信號，即出現狀態不跳變，這在，這在Manchester編碼中是不允許的，可以肯定該處出現了沖突。因此可以用這種編碼中是不允許的，可以肯定該處出現了沖突。因此可以用這種方法按位跟蹤發生沖突的數據比特位的具體位置。方法按位跟蹤發生沖突的數據比特位的具體位置。 22（2）二進制搜索算法）二進制搜索算法l當應答器進入射頻區域時，閱讀器開始針對所有的應答器進行檢測識別。其工當應答器進入射頻區域時，閱讀器開始針對所有的應答器進行檢測識別。其工作進程主要有如

35、下五個狀態：作進程主要有如下五個狀態：lPOWER OFF（斷電）狀態（斷電）狀態：應答器尚未獲得能量（未進入閱讀器工作區），：應答器尚未獲得能量（未進入閱讀器工作區），而處于斷電狀態，因此也不能發射副載波；而處于斷電狀態，因此也不能發射副載波；lIDLE（空閑）狀態（空閑）狀態：應答器進入閱讀器工作區，電磁場激活獲得能量，形成：應答器進入閱讀器工作區，電磁場激活獲得能量，形成電壓，進入空閑狀態，同時能對已調制的信號解調，并識別來自閱讀器的電壓，進入空閑狀態，同時能對已調制的信號解調，并識別來自閱讀器的RE-QUEST命令和命令和WAKE UP命令；命令；lREADY（就緒）狀態（就緒）狀態：

36、當接收到一個有效的：當接收到一個有效的REQA或或WAKE UP命令時，進入命令時，進入就緒狀態，在該狀態采用防沖突方法，用就緒狀態，在該狀態采用防沖突方法，用UID（惟一標識符）從多張（惟一標識符）從多張IC卡中選卡中選擇出一張應答器，此時該張應答器就進入擇出一張應答器，此時該張應答器就進入ACTIVE（激活）狀態；（激活）狀態；lACTIVE（激活）狀態：（激活）狀態：在本狀態完成本次應用所要求的全部操作；在本狀態完成本次應用所要求的全部操作；lHALT（停止）狀態：（停止）狀態：閱讀器完成一次交易后，處于停止狀態。閱讀器完成一次交易后，處于停止狀態。 23l在二進制搜索算法的實現中，起決

37、定作用的是讀寫器所使用的信號編碼在二進制搜索算法的實現中，起決定作用的是讀寫器所使用的信號編碼必須能夠確定碰撞的準確比特位置。必須能夠確定碰撞的準確比特位置。曼徹斯特碼（曼徹斯特碼（Mancherster）可在）可在多卡同時響應時，譯出錯誤碼字，可以按位識別出碰撞。多卡同時響應時，譯出錯誤碼字，可以按位識別出碰撞。這樣可以根據這樣可以根據碰撞的位置，按一定法則重新搜索射頻卡。碰撞的位置，按一定法則重新搜索射頻卡。l防碰撞典型指令規則防碰撞典型指令規則lREQUEST請求（序列號）請求（序列號）。此命令發送一序列號作為參數給射頻卡。此命令發送一序列號作為參數給射頻卡。l應答規則是，射頻卡把自己的

38、序列號與接收到的序列號比較，如果自身應答規則是，射頻卡把自己的序列號與接收到的序列號比較，如果自身序列號小于或等于序列號小于或等于REQUEST指令序列號參數，則此射頻卡回送其序列號指令序列號參數，則此射頻卡回送其序列號給讀寫器。給讀寫器。l這樣可以縮小預選的射頻卡的范圍；如果大于，則不響應。這樣可以縮小預選的射頻卡的范圍；如果大于，則不響應。（2）二進制搜索算法）二進制搜索算法24lSELECT選擇（序列號）。選擇（序列號）。l用某個（事先確定的）序列號作為參數發送給射頻卡。用某個（事先確定的）序列號作為參數發送給射頻卡。具有相同序列號的具有相同序列號的射頻卡將以此作為執行其他命令（例如讀出

39、和寫入數據）的切入開關，即射頻卡將以此作為執行其他命令（例如讀出和寫入數據）的切入開關，即選擇這個射頻卡。選擇這個射頻卡。l具有其他序列號的射頻卡只對具有其他序列號的射頻卡只對REQUEST命令應答。命令應答。lREAD-DATA讀出數據讀出數據。選中的射頻卡將存儲的數據發送給讀寫器。選中的射頻卡將存儲的數據發送給讀寫器。lUNSELECT 去選擇去選擇。l取消一個事先選中的射頻卡，射頻卡進入取消一個事先選中的射頻卡，射頻卡進入“無聲無聲”狀態，在這種狀態下射狀態，在這種狀態下射頻卡完全是非激活的，對收到的頻卡完全是非激活的，對收到的REQUEST命令不作應答。為了重新激活命令不作應答。為了重

40、新激活射頻卡，必須先將射頻卡移出讀寫器的作用范圍再進入，以實行復位。射頻卡，必須先將射頻卡移出讀寫器的作用范圍再進入，以實行復位。（2）二進制搜索算法）二進制搜索算法251）二進制搜索算法）二進制搜索算法l 工作流程工作流程l在二進制搜索算法中，要能夠檢測出多張卡的存在，卡片的返回數據必在二進制搜索算法中，要能夠檢測出多張卡的存在，卡片的返回數據必須具有唯一性，且卡片在傳輸其身份識別標簽時必須準確、同步。這樣須具有唯一性，且卡片在傳輸其身份識別標簽時必須準確、同步。這樣終端才能在位級上檢測出多張卡片的存在，這是防碰撞檢測的關鍵。終端才能在位級上檢測出多張卡片的存在，這是防碰撞檢測的關鍵。l射頻

41、卡工作的特點是射頻卡工作的特點是，當讀到讀寫器發出的序列號大于自身序列號時，當讀到讀寫器發出的序列號大于自身序列號時，則對系統作出響應。根據這一特點，二進制搜索算法的工作流程是：則對系統作出響應。根據這一特點，二進制搜索算法的工作流程是：l射頻卡進入讀寫器的工作范圍，讀寫器發出一個最大序列號讓所有射射頻卡進入讀寫器的工作范圍，讀寫器發出一個最大序列號讓所有射頻卡響應；同一時刻開始傳輸它們的序列號到讀寫器的接收模塊。頻卡響應；同一時刻開始傳輸它們的序列號到讀寫器的接收模塊。26l讀寫器對比射頻卡響應的序列號的相同位數上的數，讀寫器對比射頻卡響應的序列號的相同位數上的數，如果出現不一致如果出現不一

42、致的現象的現象（即有的序列號該位為（即有的序列號該位為0，而有的序列號該位為，而有的序列號該位為1），），則可判斷出則可判斷出有碰撞。有碰撞。l確定有碰撞后，把有不一致位的數從最高位到次低次依次置確定有碰撞后，把有不一致位的數從最高位到次低次依次置0再輸出系再輸出系列號，即依次排除序列號大的數，至讀寫器對比射頻卡響應的序列號的相列號，即依次排除序列號大的數，至讀寫器對比射頻卡響應的序列號的相同位數上的數完全一致時，說明無碰撞。這時就選出序列號最小的數。同位數上的數完全一致時，說明無碰撞。這時就選出序列號最小的數。l選出序列號最小的數后，對該卡進行數據交換，然后使該卡進入選出序列號最小的數后，對

43、該卡進行數據交換，然后使該卡進入“無無聲聲”狀態，則在讀出器范圍也不再響應（移動該范圍后移入可再次響狀態，則在讀出器范圍也不再響應（移動該范圍后移入可再次響應）。應）。l重復流程，選出序列號倒數第二的射頻卡進行數據交換。重復流程，選出序列號倒數第二的射頻卡進行數據交換。l多次循環后可完成所有射頻卡的讀取。多次循環后可完成所有射頻卡的讀取。（2）二進制搜索算法）二進制搜索算法27（2）二進制搜索算法）二進制搜索算法l假設有假設有4個標簽其序列號分別為個標簽其序列號分別為10110010、10100011、10110011、11100011，其二進制搜索算法實現流程如表，其二進制搜索算法實現流程如

44、表1所示：所示：查詢前綴查詢前綴Q第一次查詢第一次查詢11111111第二次查詢第二次查詢10111111第三次查詢第三次查詢10101111標簽響應標簽響應1X1X001X101X001X10100011標簽標簽A1011001010110010標簽標簽B101000111010001110100011標簽標簽C1011001110110011標簽標簽D11100011282）動態二進制搜索算法）動態二進制搜索算法l為減少標簽發送數據所需的時間和所消耗的功率，有人提出了改進的二為減少標簽發送數據所需的時間和所消耗的功率，有人提出了改進的二進制樹搜索算法，進制樹搜索算法，l其改進思路是把數據分

45、成兩部分，其改進思路是把數據分成兩部分，閱讀器和標簽雙方各自傳送其中一部閱讀器和標簽雙方各自傳送其中一部分數據，可把傳輸的數據量減小一半，達到縮短傳送時間的目的。分數據，可把傳輸的數據量減小一半，達到縮短傳送時間的目的。l根據二進制搜索算法的思路進行改良，根據二進制搜索算法的思路進行改良，當標簽當標簽ID與查詢前綴相符時，標與查詢前綴相符時，標簽只發送其余的比特位，簽只發送其余的比特位，可以減少每次傳送的位數，也可縮短傳送的時可以減少每次傳送的位數，也可縮短傳送的時間，從而縮短防碰撞執行時間。間，從而縮短防碰撞執行時間。29l其改進思路是把數據分成兩部分，收發雙方各自傳送其中一部分數據，其改進

46、思路是把數據分成兩部分，收發雙方各自傳送其中一部分數據，可把傳輸的數據量減小到一半，達到縮短傳送時間的目的。可把傳輸的數據量減小到一半，達到縮短傳送時間的目的。l通常序列號的規模在通常序列號的規模在8字節以上。為選擇一個單獨的射頻卡，每次都不得字節以上。為選擇一個單獨的射頻卡，每次都不得不傳輸大量的數據，效率非常低。根據二進制搜索算法的思路進行改不傳輸大量的數據，效率非常低。根據二進制搜索算法的思路進行改良，可以減少每次傳送的位數，也可縮短傳送的時間，從而縮短防碰撞良，可以減少每次傳送的位數，也可縮短傳送的時間，從而縮短防碰撞執行時間。執行時間。l下面分析動態二進制搜索算法的工作過程。在例子中

47、，射頻卡有下面分析動態二進制搜索算法的工作過程。在例子中，射頻卡有3張，序張，序列號分別是：標簽列號分別是：標簽1，11010111；標簽；標簽2，11010101；標簽；標簽3，11111101。2）動態二進制搜索算法）動態二進制搜索算法302）動態二進制搜索算法）動態二進制搜索算法l（1） 動態二進制搜索算法的工作步驟動態二進制搜索算法的工作步驟l 讀寫器第一次發出一個完整的讀寫器第一次發出一個完整的UID位位數碼數碼N，每個位上的碼全為，每個位上的碼全為1，讓所有射，讓所有射頻卡都發回響應。頻卡都發回響應。l 讀寫器判斷有碰撞的最高位數讀寫器判斷有碰撞的最高位數X，把該位置，把該位置0。

48、然后傳輸。然后傳輸N X位的數位的數據后即中斷傳輸。射頻卡接到這些數據后馬上響應，回傳的信號位是據后即中斷傳輸。射頻卡接到這些數據后馬上響應，回傳的信號位是（X-1）1。即讀寫器和射頻卡以最高碰撞位為界分別傳送前后信號。傳。即讀寫器和射頻卡以最高碰撞位為界分別傳送前后信號。傳遞的總數據量可減小一半。遞的總數據量可減小一半。查詢前綴查詢前綴Q第一次查詢第一次查詢11111111標簽響應標簽響應11X1X1X1標簽標簽111010111標簽標簽211010101標簽標簽311111101312）動態二進制搜索算法）動態二進制搜索算法l 讀寫器檢測第二次返回的最高碰撞讀寫器檢測第二次返回的最高碰撞位

49、數位數X是否小于前一次檢測回傳的次高是否小于前一次檢測回傳的次高碰撞位數。碰撞位數。l 重復步驟，多次重復后可完成射頻卡的交換數據工作。重復步驟，多次重復后可完成射頻卡的交換數據工作。查詢前綴查詢前綴Q第一次查詢第一次查詢11011111標簽響應標簽響應110101X1標簽標簽111010111標簽標簽211010101標簽標簽311111101l若不是，則直接把該位置若不是，則直接把該位置“0”；l若是，則要把前一次檢測的次高位也填若是，則要把前一次檢測的次高位也填“0”。l然后向射頻卡發出信號。發出信號的位數為然后向射頻卡發出信號。發出信號的位數為NX，射頻卡接收到信號，如果射，射頻卡接收

50、到信號，如果射頻卡信號小于或等于這一接收信號，馬上響應，回傳的信號只是序列號中最高頻卡信號小于或等于這一接收信號，馬上響應，回傳的信號只是序列號中最高碰撞位后的數，即（碰撞位后的數，即（X-1）1位。位。l若射頻卡返回信號表示無碰撞，則對該序列號的射頻卡進行讀若射頻卡返回信號表示無碰撞，則對該序列號的射頻卡進行讀/寫處理，然后使寫處理，然后使其進入其進入“不響應狀態不響應狀態”。322）動態二進制搜索算法）動態二進制搜索算法l（2） 動態二進制搜索算法與工作步驟相動態二進制搜索算法與工作步驟相對應的示例對應的示例l 例如例如N=8，傳送數據為，傳送數據為11111111b。最高位為第最高位為第

51、8位，最低位為位，最低位為1位。根據響位。根據響應可判斷第應可判斷第6位、第位、第4位、第位、第2位有碰位有碰撞。撞。l X=6，即第，即第6位有碰撞，則傳送數據變為位有碰撞，則傳送數據變為11011111b。傳送時，只傳送前。傳送時，只傳送前面面3位數位數110b。這時標簽。這時標簽1和標簽和標簽2響應，其序列號的前響應，其序列號的前3位與射頻卡相同，位與射頻卡相同，不回傳，只回傳各自的后不回傳，只回傳各自的后5位數據。標簽位數據。標簽1為為10111b，標簽，標簽2為為10101b。可。可判斷第判斷第2位有碰撞。位有碰撞。查詢前綴查詢前綴Q第一次查詢第一次查詢11111111標簽響應標簽響

52、應11X1X1X1標簽標簽111010111標簽標簽211010101標簽標簽311111101332）動態二進制搜索算法）動態二進制搜索算法l X=2，根據要求第，根據要求第4位也要補零，則傳位也要補零，則傳送數據變為送數據變為11010101b，傳送時只傳送，傳送時只傳送1101010b。這時只有標簽。這時只有標簽2響應，并返回響應，并返回1b，表明無碰撞。讀寫器選中標簽，表明無碰撞。讀寫器選中標簽2進行進行數據交換，讀數據交換，讀/寫完畢后標簽寫完畢后標簽2進行進行“休休眠眠”。l 重復步驟，按序可讀重復步驟，按序可讀/寫標簽寫標簽1、標簽、標簽3。l在動態二進制搜索算法的工作過程中，要

53、注意通過附加參數把有效位的在動態二進制搜索算法的工作過程中，要注意通過附加參數把有效位的編號發送到射頻卡，從而保證每次響應的位置是正確的。編號發送到射頻卡，從而保證每次響應的位置是正確的。查詢前綴查詢前綴Q第一次查詢第一次查詢11010101標簽響應標簽響應110101X1標簽標簽111010111標簽標簽211010101346、射頻識別技術標準、射頻識別技術標準l（1）主要技術標準體系）主要技術標準體系 l目前目前RFID存在三個主要的技術標準體系，總部設在美國麻省理工學院存在三個主要的技術標準體系，總部設在美國麻省理工學院（MIT）的）的Auto-ID Center（自動識別中心自動識別

54、中心）、日本的）、日本的Ubiquitous ID Center （泛在（泛在ID中心，中心，UIC）和）和ISO標準體系。標準體系。 356、射頻識別技術標準、射頻識別技術標準l1）EPC Global lEPC Global是由美國統一代碼協會（是由美國統一代碼協會（UCC）和國際物品編碼協會（）和國際物品編碼協會（EAN）于于2003年年9月共同成立的非營利性組織，其前身是月共同成立的非營利性組織，其前身是1999年年10月月1日在美國麻日在美國麻省理工學院成立的非營利性組織省理工學院成立的非營利性組織Auto-ID中心。中心。lAuto-ID中心以創建中心以創建“物聯網物聯網”（Int

55、ernet of Things）為使命，與眾多成員）為使命，與眾多成員企業共同制訂一個統一的開放技術標準。旗下有沃爾瑪集團、英國企業共同制訂一個統一的開放技術標準。旗下有沃爾瑪集團、英國Tesco等等100多家歐美的零售流通企業，同時有多家歐美的零售流通企業，同時有IBM、微軟、飛利浦、微軟、飛利浦、Auto-IDLab等等公司提供技術研究支持。公司提供技術研究支持。l目前目前EPC Global已在加拿大、日本、中國等國建立了分支機構，專門負責已在加拿大、日本、中國等國建立了分支機構，專門負責EPC碼段在這些國家的分配與管理、碼段在這些國家的分配與管理、EPC相關技術標準的制定、相關技術標準

56、的制定、EPC相關相關技術在本國的宣傳普及以及推廣應用等工作。技術在本國的宣傳普及以及推廣應用等工作。366、射頻識別技術標準、射頻識別技術標準lEPC Global“物聯網物聯網”體系架構由體系架構由EPC編碼、編碼、EPC標簽及讀寫器、標簽及讀寫器、EPC中間中間件、件、ONS服務器和服務器和EPCIS服務器等部分構成。服務器等部分構成。lEPC賦予物品惟一的電子編碼，其位長通常為賦予物品惟一的電子編碼，其位長通常為64位或位或96位，也可擴展為位，也可擴展為256位。對不同的應用規定有不同的編碼格式，主要存放企業代碼、商品代碼和位。對不同的應用規定有不同的編碼格式，主要存放企業代碼、商品

57、代碼和序列號等。最新的序列號等。最新的GEN2標準的標準的EPC編碼可兼容多種編碼。編碼可兼容多種編碼。lEPC中間件中間件對讀取到的對讀取到的EPC編碼進行過濾和容錯等處理后，輸入到企業的業編碼進行過濾和容錯等處理后，輸入到企業的業務系統中。它通過定義與讀寫器的通用接口（務系統中。它通過定義與讀寫器的通用接口（API）實現與不同制造商的讀）實現與不同制造商的讀寫器兼容。寫器兼容。lONS服務器服務器根據根據EPC編碼及用戶需求進行解析，以確定與編碼及用戶需求進行解析，以確定與EPC編碼相關的編碼相關的信息存放在哪個信息存放在哪個EPCIS服務器上。服務器上。lEPCIS服務器服務器存儲并提供

58、與存儲并提供與EPC相關的各種信息。這些信息通常以相關的各種信息。這些信息通常以PML的的格式存儲，也可以存放于關系數據庫中。格式存儲，也可以存放于關系數據庫中。376、射頻識別技術標準、射頻識別技術標準l2）Ubiquitous ID l日本在電子標簽方面的發展，始于日本在電子標簽方面的發展，始于20世紀世紀80年代中期的實時嵌入式系統年代中期的實時嵌入式系統TRON。T-Engine是其中核心的體系架構。是其中核心的體系架構。l在在TEngine論壇領導下，泛在論壇領導下，泛在ID中心于中心于2003年年3月成立，并得到日本政月成立，并得到日本政府經產省和總務省以及大企業的支持，目前包括微

59、軟、索尼、三菱、日府經產省和總務省以及大企業的支持，目前包括微軟、索尼、三菱、日立、日電、東芝、夏普、富士通、立、日電、東芝、夏普、富士通、NTT DoCoMo、KDDI、J-Phone、伊、伊藤忠、大日本印刷、凸版印刷、理光等重量級企業。藤忠、大日本印刷、凸版印刷、理光等重量級企業。l泛在泛在ID中心的泛在識別技術體系架構由中心的泛在識別技術體系架構由泛在識別碼（泛在識別碼（uCode）、信息系統）、信息系統服務器、泛在通信器和服務器、泛在通信器和ucode解析服務器等四部分構成解析服務器等四部分構成。 386、射頻識別技術標準、射頻識別技術標準luCode采用采用128位記錄信息，提供了位

60、記錄信息，提供了3401036編碼空間，并可以以編碼空間，并可以以128位為位為單元進一步擴展至單元進一步擴展至256、384或或512位。位。uCode能包容現有編碼體系的元編碼能包容現有編碼體系的元編碼設計，可以兼容多種編碼，包括設計，可以兼容多種編碼，包括JAN、UPC、ISBN、IPv6地址，甚至電話地址，甚至電話號碼。號碼。luCode標簽標簽具有多種形式，包括條碼、射頻標簽、智能卡、有源芯片等。具有多種形式，包括條碼、射頻標簽、智能卡、有源芯片等。泛在泛在ID中心把標簽進行分類，設立了中心把標簽進行分類，設立了9個級別的不同認證標準。個級別的不同認證標準。l信息系統服務器信息系統服