rfid防碰撞演算法

『壹』 aloha提升下載速度

aloha演算法可以提升下載速度。
Aloha演算法是一種非常簡單的TDMA演算法，該演算法被廣泛應用在RFID系統中。這種演算法多採取標簽先發言的方式，即標簽一進入讀寫器的閱讀區域就自動向讀寫器發送其自身的ID，隨即標簽和讀寫器間開始通信。
ALOHA演算法是隨機接入演算法的一種，當標簽要發送數據信息時，它可以在任意時間段隨機發送，把它稱為純ALOHA演算法。為了解決標簽碰撞問題，RFID系統採取兩種類型的防碰撞演算法，一種是確定性防碰撞演算法，如二進制搜索演算法、動態二進制搜索演算法、跳躍式動態樹型演算法、查詢樹演算法、動態查詢樹演算法、後退索引搜索演算法等。確定性防碰撞演算法在整個識別過程不存在隨機性，提高了信號傳輸速率，信道的利用率比較高，性能穩定，但是演算法存在復雜度大、系統識別時延大等缺點，當標簽數過多時，系統效率降低。

『貳』 如何解決rfid系統的防碰撞問題

RFID射頻識別技術近年來廣受關注，被應用於眾多領域，其中UHF(超高頻)頻段RFID應用最為廣泛。UHF RFID國際標准有ISO/IEC 180006 Type A、Type B、Type C三類，Type C類標準是最新制定的，在數據速率、調制方式等方面都要優於其他兩種。本文針對Type C類標准中的防沖突演算法進行研究，分析該標准採用的防沖突演算法在面對快速運動標簽群時的處理情況。

本文基於特定背景，快速運動的電子標簽群源源不斷地筆直經過UHF RFID讀卡器的識別范圍，如圖1所示。

圖1 快速運動的UHF RFID標簽群

在正常情況下，當RFID電子標簽讀卡器范圍內存在大量靜止電子標簽，RFID電子標簽讀卡器可通過防沖突演算法，完成所有電子標簽的識別工作;但當電子標簽群運動起來，並達到一定的速度時，是否可以在有限時間內完成電子標簽的讀取工作是一個問題，其關鍵因素是防沖突演算法。

能否有效地完成快速移動電子標簽群的讀取工作，直接影響系統的穩定性以及可靠性。未來用於快速運動標簽群的UHF RFID自動識別系統將越來越多，因此本課題的研究具有一定的前瞻性以及現實意義。

1 UHF RFID介紹

射頻識別(Radio Frequency Identification，RFID)是一種無線射頻識別技術，它利用射頻信號通過空間耦合(交變磁場或電磁場)實現無接觸信息傳遞，並通過傳遞的信息識別目標。RFID的工作頻段分為低頻(LF)、高頻(HF)、超高頻(UHF)和微波(MW)，其中UHF RFID(860~960 MHz)具有讀寫速度快、識別距離遠、抗干擾能力強、標簽小等優點，被廣泛應用。

1.1 協議標准

國際上主要有3個RFID技術標准體系組織：全球產品電子編碼中心(EPC Global)、ISO/IEC和日本Ubiquitous ID Center(UID)。ISO/IEC 18000是基於物品管理的RFID的國際標准，按頻率不同分為7個部分，其中ISO/IEC 180006規定UHF頻段，針對860~930 MHz的無線接觸通信空氣介面參數。ISO/IEC 180006系列標准包括Type A、Type B、Type C三類標准，其主要區別在於標簽識別中的編碼方式以及防沖突演算法等。

1.2 防沖突演算法

防沖突演算法是射頻識別系統中的多路存取法，它是射頻識別系統實現標簽快速識別的關鍵。RFID系統識別多標簽時，當有2個或者2個以上標簽同時發送數據就會產生數據的干擾，這種干擾稱為標簽沖突。因此，在RFID系統中必須建立有效的仲裁機制來避免沖突的發生。

目前在RFID系統中使用最廣泛的防沖突演算法大多基於時分多址(TDMA),每個標簽在某個時隙佔用信道與讀卡器通信，當產生沖突則暫時退避，重新選擇時隙再次與讀卡器通信，從而實現系統的防沖突工作。

1.3 研究背景

本文的研究基於快速運動標簽群不間斷地經過讀卡器識別范圍的特定背景。如果運動標簽群速度過慢，讀卡器在新標簽到來之前已經完成了場內所有標簽的識別工作，不會出現漏讀現象，但是在這種情況下，系統識別效率就會大大降低;而當運動標簽群達到一定速度時，讀卡器將進行標簽的防沖突處理，因為新標簽的加入會產生部分標簽一段時間內不被識別到，隨著標簽移動離開射頻范圍，就會出現漏讀現象。

在現實生活中，滿載貨物的貨車在通過讀卡器識別范圍時，要求系統快速有效地讀取貨車上所有貨物的物品信息。貨車通過讀卡器的速度直接影響系統的工作效率，快速通過能節約大量時間和成本。

所以，如果要提高系統效率並且保證系統可靠性，移動標簽群必須達到一個適中的速度，並且防沖突演算法一定要對此種情況進行有效處理。本文研究ISO/IEC 180006 Type C的防沖突處理演算法，分析其對快速運動標簽群是否有可靠的對策和處理方式。

2 Type C防沖突演算法

2.1 Aloha演算法

常用的防沖突演算法大多是基於Aloha演算法——一種無規則的時分多址(TDMA)演算法。Aloha演算法規定標簽周期性地發送數據給讀卡器，數據傳輸時間只是周期時間的一小部分，標簽傳輸中有很長時間的停歇，因此有一定概率使兩個標簽在不同時隙傳輸數據，以避免沖突。

基於Aloha演算法出現了很多改進演算法：時隙Aloha演算法、幀時隙Aloha演算法、動態幀時隙Aloha演算法等。Type C採用的防沖突演算法是隨機時隙防沖突演算法，其本質跟幀時隙Aloha機制一樣。

2.2 隨機時隙防沖突演算法(SR)

隨機時隙防沖突演算法本質上與幀時隙Aloha機制類似，其幀長度為2Q,並且該機制根據標簽應答情況來調整Q值，改變下一個識別周期的時隙數，讓未識別標簽重新選擇。當一幀中出現過多的沖突時隙時，讀卡器會提前結束該幀，並選擇一個更大的Q值發送給標簽群;當一個幀中出現過多的空閑時隙時，讀卡器會提前結束該幀，並選擇一個比較小的Q值發送給標簽群。

隨機時隙防沖突演算法命令包括Query、QueryAdjust、Query Rep等,主要參數為時隙計數參數Q。協議中的Q值決定了防沖突時所用的時隙數,讀卡器通過給標簽發送相應命令改變標簽狀態，完成防沖突工作。協議規定標簽有3個狀態，如圖2所示。

圖2 電子標簽狀態圖


當系統上電或信道空閑時，讀卡器發送Query命令，啟動清點周期，初始化一個識別周期，並決定哪些電子標簽參與本輪識別周期。Query命令包含時隙計數參數Q，當接收到Quary命令時，RFID電子標簽讀卡器在識別區域內隨機選擇進入識別周期的標簽，所有參與電子標簽在(0，2Q-1)范圍內選擇一個隨機數，並置入它們的時隙計數器。選到0值的電子標簽變為應答狀態，並響應讀卡器，回答一個16機制隨機數(RN16)給讀卡器;沒有選到0值的標簽變為仲裁狀態，等待下一條Query Adjust或Query Rep命令;沒有進入本輪識別周期的電子標簽保持休眠狀態。

處於仲裁狀態的電子標簽每接收到一條Query Rep命令，它們的時隙計數器減一次，當時隙計數器減到0000h時，標簽轉變為應答狀態，響應讀卡器。當時隙計數器值為0000h，並且已經應答，但沒有得到確認時，標簽變為仲裁狀態，當接收到下一條QueryRep命令時，簽時隙計數器減一變為7FFFh，防止隨後應答，直到標簽接收到Query Adjust命令或者進入下一個識別周期。在2Q-1條QueryRep命令中，所有標簽至少應答一次。

當電子標簽時隙計數器同時達到0000h，並同時應答，會產生沖突;當標簽時隙計數器都不等於0000h,讀卡器接收不到響應。面對這兩種情況，讀卡器可能需要重新選定Q值，讀卡器根據的自適應Q演算法如圖3所示。

圖3 自適應Q演算法

由自適應Q演算法可知，當某一時隙出現沖突或者無響應的情況，Qfp的值會增大或減小，然後對Qfp四捨五入得到新的Q值。如果Q值發生變化，讀卡器發送Query命令更新Q值，並使標簽重新選擇時隙計數器;否則繼續發送QueryRep命令，讓所有標簽時隙計數器減一。自適應Q演算法通過根據標簽沖突以及無響應情況動態地改變Q值，從而改變時隙數，實現自適應防沖突。

3 存在的問題及解決方案

3.1存在的問題

本文的背景是快速運動標簽群通過讀卡器射頻區域，該種情況必須注意的是，讀卡器范圍內的標簽是動態變化的，隨時都有新標簽加入讀卡器的識別范圍，從而影響系統的防沖突處理。通過對ISO180006 Type C防沖突演算法過程的研究，發現該演算法在面對快速標簽群時並未做有效的處理。

根據演算法的工作過程，當UR6258電子標簽讀卡器開始電子標簽的識別工作，首先發送Query命令開啟一個清點周期，高速運動標簽群進入讀卡器識別范圍，上電進入休眠狀態。讀卡器在識別范圍內選擇部分標簽進入清點周期，部分標簽沒有被選擇而保持休眠狀態，等待下一個清點周期的到來。當上一個清點周期結束，讀卡器會發送Query命令開啟新的清點周期，這時候讀卡器識別范圍內會有新加入的標簽，讀卡器會從所有標簽中再次隨機選擇部分標簽進入清點周期。新標簽的加入導致部分標簽可能始終無法進入清點周期，無法被識別到，然後離開讀卡器識別范圍。

另外一種情況是，電子標簽進入清點周期後，在電子標簽應答發生沖突或者未收到回復的情況下，時隙計數器由0000H減1變為FFFFH，避免隨後應答。這時候會有兩種情況：一種是由於碰撞或者無響應的情況導致Q值發生變化，這時允許所有標簽重新隨機選擇一個值放入時隙計數器，在清點周期內獲得再一次被識別的機會;如果沖突以及無響應現象沒有導致Q值發生變化，那麼在本輪清點周期結束後，它會同新進標簽一起爭取下一次進入清點周期的機會，所以會有幾率無法進入清點周期，直到離開讀卡器的識別范圍。

假設運動標簽群的運動速度為v,標簽在讀卡器識別范圍內運動距離為d,那標簽在識別范圍內的時間t=v/d。假設讀卡器進行一輪標簽讀取的時間為T，而標簽被識別所需的周期為n(n為正整數)，那麼當n·Tv/d，則會出現標簽不被識別的情況。

以上兩種情況的發生都可能會導致標簽群中部分標簽一段時間不被識別，通過讀卡器的識別范圍，從而造成系統的不可靠，出現漏讀。

3.2 解決方案

針對快速運動標簽群的識別，主要問題是新標簽與舊標簽爭搶進入清點周期的機會，而舊標簽在讀卡器識別范圍的時間有限。面對這種情況，解決問題切入點是讓舊標簽比新標簽擁有更多的機會進入清點周期，或者直接不允許新標簽與舊標簽競爭，而是等待舊標簽完成識別才開始新標簽的識別工作。擬採用兩種方法解決該問題。

第一種是基於標簽到場時間的解決方案。標簽進入射頻范圍內上電，標簽內到場計時器開始計時，計時值為t，讀卡器選定一個適當的計時值T，發送Query命令開始清點周期的同時發送T，標簽把自己的計時值與讀卡器所要求的T大小作比較：如果t

第二種是基於標簽到場點名的辦法。當某一時刻系統啟動，讀卡器開始發送Query命令進入清點周期之前發送點名命令，讓識別范圍內的標簽由休眠狀態進入到場狀態。之後只選擇到場狀態的標簽進入清點周期，待所有到場標簽完成識別再進行新一輪點名。這種方案可以完全解決新舊標簽的競爭問題。

結語

針對快速運動標簽群的特殊背景，研究了ISO180006 Type C類標準的隨機時隙防沖突演算法(SR)，研究得知該演算法並沒有針對該種情況進行有效的處理，會出現漏讀現象。在不改變原有演算法本質的前提下提出了基於到場時間以及基於到場點名兩種解決方案。
參考：http://www.rfidhb.com/rfid/knowledge/446.html

『叄』 關於RFID防碰撞演算法中的Q值演算法

Q=S/G,CN=1/Q,so C=G/(S*N)

『肆』 求解釋RFID的防碰撞演算法中的查詢樹QT演算法麻煩詳細說一下演算法原理，如何防碰撞的謝謝~

查詢樹QT（QueryTree）是一種典型的樹結構演算法，其演算法原理：讀寫器發送長度為k的prefix（前置代碼，一般為置於一組號碼前的數字或字母，表示所屬區域等）；標簽ID中前kbit與prefix匹配的tag反饋第(k+1)bit至最後1bit。如果讀寫器收到的標簽ID碰撞，再分別將prefix加「1」和「0」，作為新的prefix發送出去。如果沒有碰撞，就表明一個標簽被識別了。

舉例：設有三個標簽ID分別為「010」，「011」，「100」，讀寫器的查詢序列首先置為「0」、「1」，讀寫器先發送序列「0」進行查詢，發生碰撞，此時將序列置為「00」、「01」，再次分別發送，序列「00」沒有響應，序列「01」發生碰撞，將序列置為「010」、「011」，成功識別。回溯到序列「1」，只有標簽「100」響應，成功識別。如圖所示