射頻識別系統的防沖突算法改進與實現
文章出處：http://hz-huyue.com 作者：喻武龍，孟穎 人氣： 發表時間：2011年09月23日
1 引言
射頻識別技術(RFID)是一種非接觸式自動識別技術，它通過無線射頻方式對目標加以識別并交換數據，主要應用于較短時間內在射頻區域中識別一個目標。當多個電子標簽同時到達射頻有效區域時，標簽會同時響應讀寫器指令并發送信號，導致閱讀器不能正確接收數據，也不能正確識別標簽，發生沖突。需要一種可靠的防沖突(Anti-collision)算法，解決在識別多個電子標簽時出現的數據沖突而導致閱讀器無法正確識別標簽的問題。
無源電子標簽數字集成電路結構框圖如圖1所示，主要由通信安全、信息安全、存儲以及控制等4個單元組成。其中防沖突模塊位于通信信息安全單元，用于解決多個標簽與閱讀器進行數據交換所引起的數據沖突問題。
2 ALOHA算法
ALOHA算法足一種簡便的防沖突算法，如圖2所示。它既沒有檢測機制也沒有恢復機制，只是以一定概率確保電子標簽發出的信息準確地被閱讀器接收。ALOHA算法僅用于只讀閱讀器，標簽將數據(序列號)傳輸給閱讀器，并且在一個周期中將數據不斷發送給閱讀器，數據傳輸時間只是重復時間的一小部分，使得在傳輸中產生相當長的間歇，因此，存在一定概率，使兩個應答器可以在不同的時隙傳輸其數據，從而避免沖突。
從圖2可以看到，閱讀器首先發送讀指令，處于射頻區域的多個標簽收到指令，立即在隨后多個時隙中隨機選擇一個將信息上傳給閱讀器，并且標簽在一個周期循環時隙內完成數據上傳。增加時隙數量可降低RF終端發生沖突的概率，但是信道大部分時間將處于空閑狀態，使得防沖突識別速度變慢。反之，減少時隙數量導致射頻終端沖突明顯增加。運用時隙算法的關鍵在于尋找一個有效的折衷方案，使得防沖突的可靠性和速度滿足要求。隨著RFID系統復雜程度的加大，防沖突的可靠性顯著降低，沖突不可避免，所以這種沒有檢測恢復機制的抗沖突算法僅適用于簡單系統。
3 二進制搜索防沖突算法
ALOHA算法由于效率低，實際RFID系統并未采用，而是采用更加高效的二進制搜索算法。二進制搜索算法靈活，不會發生防沖突失敗情況。對于N個應答器發生沖突的情況，最多只需要N-1次防沖突循環就能準確識別出適合的應答器。二進制搜索算法的基本思想是閱讀器判斷出發送應答器的序列號產生數據沖突位置。然后強制命令在沖突位置發送信息為"0"或"1"的應答器退出沖突。當N-1個應答器退出沖突后信道則被剩下的一個應答器完全占有并由閱讀器識別出。
為了防止數據沖突的發生，首先確定發生沖突的數據比特位的具體位置。這里使用Manchester編碼如圖3所示。這種編碼通過電平的上升沿和下降沿表示高、低電平。上升沿為邏輯"1"，下降沿為邏輯"0"，不存在狀態不變的情況。因此數據傳輸過程中檢測到編碼狀態不跳變，則認為在數據傳輸過程中發生了沖突。兩個發生沖突的數據比特位必定有一個為邏輯"0"，另一個為邏輯"1"，這樣Manchester碼的上升沿和下降沿相互抵消，使接收器在持續時間內接收到狀態持續不變的副載波信號，即出現狀態不跳變，這在Manchester編碼中是不允許的，可以肯定該處出現了沖突。因此可以用這種方法按位跟蹤發生沖突的數據比特位的具體位置。
當應答器進入射頻區域時，閱讀器開始針對所有的應答器進行檢測識別。其工作進程主要有如下五個狀態：
POWER OFF(斷電)狀態：應答器尚未獲得能量(未進入閱讀器工作區)，而處于斷電狀態，因此也不能發射副載波：
IDLE(空閑)狀態：應答器進入閱讀器工作區，電磁場激活獲得能量，形成電壓，進入空閑狀態，同時能對已調制的信號解調，并識別來自閱讀器的RE-QUEST命令和WAKE UP命令；
READY(就緒)狀態：當接收到一個有效的REQA或WAKE UP命令時，進入就緒狀態，在該狀態采用防沖突方法，用UID(惟一標識符)從多張IC卡中選擇出一張應答器，此時該張應答器就進入ACTIVE(激活)狀態；
ACTIVE(激活)狀態：在本狀態完成本次應用(一次交易)所要求的全部操作；
HALT(停止)狀態：閱讀器完成一次交易后，處于停止狀態。
應答器各狀態間的轉換圖如圖4所示。
4 改進后的防沖突算法實現步驟
這里采用SEL+NVB方式傳輸。SEL為指令碼，其代碼為93；NVB的前半字節表示字節數，后半字節表示沖突的位置。
改進后的算法具體實現步驟如下：
第1步：閱讀器分配SEL值，選定反沖突類型和級聯級數；
第2步：閱讀器分配給NVB值'20'(定義了閱讀器將發出命令迫使場內所有應答器響應完整的序列號)；
第3步：閱讀器發出SEL和NVB命令；
第4步：場內所有應答器以完整序列號響應；
第5步：假定場內的應答器都有唯一的序列號，
則當多個應答器響應時，就會發生沖突。如果無沖突，第6步到第10步可以跳過。
第6步：閱讀器確認第一個沖突的位置X并記錄下來。
第7步：閱讀器分配NVB值，其中NVB前半字節為該命令的字節數，后半字節為沖突X的位置。
第8步：閱讀器發出SEL和NVB，要求應答器中第X位為'1'的作出響應。
第9步：只有該部分序列號中第X位為'1'的應答器才會發出它們序列號剩余的部分。
第10步：若有沖突發生，第6～9步重復執行。
第11步：若無沖突發生，閱讀器為NVB分配一個值'70'。
第12步：閱讀器發出SEL和NVB，要求應答器傳送完整的序列號。
第13步：應答器傳送完整的序列號、聞讀器收到后完成對該標簽的識別工作。
改進后的防沖突算法流程圖如圖5所示。
5 改進后防沖突算法的仿真與實現
改進后主要實現Manchester碼和防沖突算法。Manchester碼是一種適合傳輸的基帶碼型，是實現防沖突檢測所采用的碼型。Manchester編碼可用兩個不同相位的二進制碼代替一個二進制碼。而防沖突算法則是采用編寫程序進行算法驗證。實驗證明，算法正確。
6 結束語
改進后的二進制防沖突算法能夠將射頻區域內的多個應答器準確地識別出來，并且使系統的傳輸數據量和傳輸時間大大減少，有效節省了傳輸信道，這是其他算法難以達到的。因此，改進后的二進制防沖突算法比其他算法更準確、更高效地解決射頻識別系統中的標簽應答數據沖突問題。
