0引言

近年來，很多學者嘗試把安全機制和防碰撞算法結合在一起。張暉等最早提出了新型安全機制下的RFID防沖突算法［1］，將物理方法和密碼機制相結合，通過將Hash鎖放入閱讀器中使用來節省門電路。丁治國等提出的基于碼分多址和防碰撞功能的RFID安全認證協議［2］，利用碼分多址技術的保密性、抗干擾性和多址通信能力，結合認證密鑰和Hash函數［3］，設計了一種具有防碰撞功能的安全認證協議;余松森等提出了融合安全與反碰撞的RFID處理機制［4］，采用的方法是將輕量級的隨機密鑰雙向認證和動態時隙ALOHA協議進行融合。然而這些機制都是簡單地將安全協議與防碰撞算法結合在一起，效率較低，隨著標簽的增加，信道占用率較高，吞吐率變低;數據在傳輸的過程中容易被竊聽ID，隱私被刺探，安全性不高;而且防碰撞效果差，花費時間較長，不宜大規模使用;同時又由于安全性達不到實用級別，需要另外的安全協議來加以保護，這樣增加了成本，極大地降低了RFID系統運行的質量。

本文提出了一種新的輕量級高安全性防碰撞策略，該方法將自適應二叉樹遍歷算法與布爾運算雙向認證協議相融合，得到一種新的防碰撞策略，該算法在解決了標簽碰撞問題的同時，具有較高的安全性。對于在圖書館、流水線、快遞服務、散貨堆場等應用場合，已能提供足夠的安全級別，適用于大數量、高效率、低成本的物聯網系統。

1.1自適應二叉樹遍歷機制

在系統讀寫識別之前，該機制相當于在碰撞標簽堆中利用遍歷規則整理出一個有序的隊列，從而使標簽擁擠狀態變成有序狀態。自適應二叉樹遍歷機制［5-6］的搜索過程是根據先序遍歷規則，在收集到的所有碰撞標簽中，根據碰撞位特征采取向前搜索策略，直到遇到一個可以識別的標簽為止;同時再采取后退方式，返回上一查詢指令節點，繼續搜索直至識別完閱讀器工作區域內所有碰撞標簽。主要步驟如下：

1）閱讀器根據曼徹斯特編碼方法得到所有識別標簽的碰撞位，得到一個查詢指令棧。

2）查詢指令棧取出棧頂指令Query（X，N）命令（X為碰撞位查詢碼，N為標簽碰撞的最高位），檢測所有標簽的碰撞位。

3）檢測有無碰撞位編碼符合條件的標簽，若有兩個以上響應，在符合條件的標簽中重新執行曼徹斯特編碼檢測，根據是否連續位調整碰撞位查詢碼，并修改N值，得到下一次查詢命令Query所需的參數，繼續搜索直到出現一個碰撞位或者無碰撞位。

4）若有一個碰撞位，可以根據約定直接先后識別兩個標簽（二進制位上取值具有互斥性，非0即1）;若無碰撞，則直接識別單個標簽，處理完后回跳到父節點，得到下一次查詢命令Query所需的參數。

5）重復進行請求與檢測過程，直到查詢棧中無查詢命令時結束。

算法充分利用返回式搜索［7］和自適應二進制搜索的優點，并根據檢測碰撞位是否連續動態生成多分支進行分治，只查詢碰撞位的方法，減少了冗余，提高了系統效率。

1.2基于布爾運算的雙向認證安全協議

布爾運算是計算機最簡單、最擅長、最快速的運算，具有無可媲美的優勢，布爾運算貫穿該策略。

1）標簽收到閱讀器發出的命令數據，與ID編碼進行布爾運算，命令數據與標簽生成的隨機數進行布爾運算［8］。

2）在閱讀器中根據先建立好的Hash函數的索引，然后解碼在后臺數據驗證，采用索引布爾運算的思想查找ID，可提高驗證速度。

3）后臺數據庫采用布爾運算的結果更新響應標簽的記錄。

現有協議標簽中門電路較多，成本過高;而且動態ID機制中標簽與數據庫更新不同步造成了安全隱患。本文利用布爾運算，提出一種新的認證協議——基于布爾運算的低成本雙向認證機制（如圖1所示）。將Hash模塊放在閱讀器中，標簽上無需集成Hash函數模塊，只需要異或門電路和隨機數生成器，通過布爾異或運算加密保證RFID系統通信安全［9-10］，簡單可行，適宜于低成本電子標簽。

2內嵌安全機制的防碰撞策略

2.1策略的基本思想

RFID技術利用無線射頻方式在閱讀器和標簽之間進行非接觸雙向數據傳輸來達到目標識別與數據交換的目的，電子標簽的二進制唯一標識的ID可以構成一棵完全二叉樹。而在閱讀器作用范圍內同步響應閱讀器信號的標簽的ID構成一棵不完全二叉樹。閱讀器根據信號沖突的情況反復對二叉樹的分枝進行裁剪，快捷安全地找出這棵二叉樹的結構，最終完成信息交換。

1）在修剪二叉樹過程中，只需要根據碰撞位的不同來進行識別，省去了非碰撞位的遍歷，縮減查詢范圍，減少冗余。

2）綜合運用曼徹斯特編碼、棧隊列技術、二叉樹先序遍歷、后退式算法經典部分及采用獨立分治并行處理思想，實現標簽的有序識別。

3）動態自適應策略，根據碰撞位前綴是否連續，動態選擇，碰撞前綴中出現連續n個碰撞位時采取2n叉樹分裂的策略（n為大于等于2的正整數）。

4）短暫鎖定機制，閱讀器接收到標簽所發的信息后，會暫時鎖定，不再發出和接收任何標簽命令。標簽成功發送完信息后進入暫時休眠狀態不再重復發送，閱讀器開始進行內部的防碰撞處理，處理完后會逐步將結果發送到已識別的標簽。

2.2策略準備工作

傳統的都是通過來回多次請求命令實現交互通信的做法，在源頭上將閱讀器與標簽之間的通信信道暴露出來，本文則將加密的ID編譯出來之后，直接在閱讀器中完成處理，最終只需要返回結果即可，減少來回請求次數。這種設計有利于標簽簡單化，低成本化，把重心放在閱讀器上，便于后續的維護升級，使系統生存能力增強。

1）請求命令Request（Null，m1）：閱讀器發出同步廣播請求信號命令作用范圍內的所有標簽（m1為隨機數）。

2）查詢命令Query（X，N）：X為曼徹斯特編碼檢測到的碰撞位前綴，參數N為沖突的最高位，在讀寫器的內部，查詢命令不斷按照先序規則搜索碰撞位生成的二叉樹，直到檢測至無碰撞或只有一個碰撞位為止;否則不斷根據曼徹斯特編碼調整X和N值，繼續搜索。

3）應答命令Answer（Data）（Data是標簽內部經布爾運算加密之后的數據）：其作用是收到請求命令的標簽對閱讀器作出應答，將數據信息返回給閱讀器。

4）鎖定命令Lock（）：閱讀器收到作用范圍內的標簽響應后，會自動進入到鎖定狀態，暫時不接收外界任何消息。

5）h（x）、fk（x）：分別表示標簽能夠運行的Hash函數和帶密鑰的Hash函數［11］。

6）在標準穩定環境中內存記錄安全，閱讀器與后臺服務器之間信道安全，閱讀器與標簽之間信道不安全。

3策略分析

3.1特點分析

本文所提出的策略主要有以下特點：

1）重閱讀器輕標簽。傳統的防碰撞算法都是通過來回多次Request請求命令實現閱讀器標簽間的交互通信，這樣不僅使得標簽的成本很高，而且在源頭上將通信信道暴露出來，不太合理。本文做法是將閱讀器收集到的數據進行解密，得到ID標識號，直接在閱讀器中完成有序列隊處理，最終只需要一次將結果返回即可，不需要來回多次請求應答，使通道處于較安全狀態，即只需Request、Answer兩個命令的傳送。這種設計有利于標簽簡單化，成本降低，把處理重心放在閱讀器和后臺上，便于后續的維護的升級，利于超大批量的標簽系統運作，生存能力加強。

2）內嵌安全機制。通過布爾運算加密的方式將安全機制融合在防碰撞處理之前，一方面先行過濾掉攻擊和假冒的無用標簽，減輕碰撞處理的壓力;另一方面提高標簽的生存能力，通過加密的隨機數和布爾運算打亂前后的信息邏輯，使得無法推測通信以前的信息，保證通信的安全性。并且通過雙向認證的方式來驗證消息的可靠性，確保標簽、閱讀器合法，不被修改。表3給出了該策略與幾種其他的協議安全性能對比。

3）高性價比。在輕量級的RFID解決方案中，利用較簡單的標簽結構，能為整個系統節省非常可觀的費用，同時也能兼顧較高的安全系數。不同策略下的標簽成本。

仿真結果表明，當標簽數目較少時，本文策略防碰撞效果并不明顯，當數目不斷增加時，搜索效果只是比后退機制好一些，但是傳輸比特位會比較顯著。這是因為二叉樹先序遍歷機制采用的是只在碰撞位中遍歷，并且有回退機制避免了搜索路徑的重復，自適應多叉樹策略對碰撞位前綴搜索做了優化，同時利用搜索索引采用布爾運算來匹配，提高了查找的運算速度。

當有巨量標簽、標簽的長度增大時，本文策略傳輸的比特位就會非常有優勢。以后還可以通過閱讀器升級，增加并行分組識別，效果將會更好。

4結語

本文提出了一種輕量級的內嵌安全機制的RFID防碰撞策略，該方案巧妙地將經典動態自適應機制、先序遍歷算法和布爾雙向認證機制融合在一起，提高了防碰撞效率，降低了系統成本，具有一定的防重傳、防纂改、防跟蹤、防阻斷的安全特性，簡單高效，可靠實用。實驗結果表明該處理策略能夠減少碰撞時隙，提高吞吐量和防碰撞質量，在處理大量標簽、較長ID標簽環境中優勢更為突出，具有良好的發展基礎和應用前景。后續，在防碰撞過濾和識別處理等方面需要進一步的優化探索，采用基于PUF的物理不可克隆功能模塊也是RFID系統發展的方向，以不斷提高識別系統的安全性水平。

責任編輯：Ct