0引言

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

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

1.1自適應二叉樹遍歷機制

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

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

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

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

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

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

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

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

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

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

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

3）后臺數(shù)據(jù)庫采用布爾運算的結(jié)果更新響應標簽的記錄。

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

2內(nèi)嵌安全機制的防碰撞策略

2.1策略的基本思想

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

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

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

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

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

2.2策略準備工作

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

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

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

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

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

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

6）在標準穩(wěn)定環(huán)境中內(nèi)存記錄安全，閱讀器與后臺服務器之間信道安全，閱讀器與標簽之間信道不安全。

3策略分析

3.1特點分析

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

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

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

3）高性價比。在輕量級的RFID解決方案中，利用較簡單的標簽結(jié)構(gòu)，能為整個系統(tǒng)節(jié)省非?？捎^的費用，同時也能兼顧較高的安全系數(shù)。不同策略下的標簽成本。

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

當有巨量標簽、標簽的長度增大時，本文策略傳輸?shù)谋忍匚痪蜁浅Ｓ袃?yōu)勢。以后還可以通過閱讀器升級，增加并行分組識別，效果將會更好。

4結(jié)語

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

責任編輯：Ct