改進型MBI防碰撞算法研究*

李 唯，王玉皞，孫 宇，曾 艦

（南昌大學信息工程學院，南昌330031）

改進型MBI防碰撞算法研究*

李 唯，王玉皞*，孫 宇，曾 艦

（南昌大學信息工程學院，南昌330031）

在深入研究多比特識別算法MB（IMulti-Bit Identification Protocol）的基礎上，從概率的角度對MBI機制進行分析建模，完善了MBI的理論基礎。并且針對MBI算法通信開銷較大問題，提出一種改進型多比特識別算法IMBI（Improved Multi-Bit Identification Protocol）。該算法在不增加原算法時間復雜度的前提下，通過引入滑動窗及部分碰撞比特恢復機制，解決了MBI算法中常規時隙標簽冗余響應以及反演時隙下空閑分組造成的時延浪費問題，提升了系統識別性能。仿真結果表明，文章建立的模型對MBI算法有良好的逼近性能。此外，所提出的IMBI算法在標簽平均消耗和系統時延上性能有大幅提升，進而提升了系統處理海量標簽信息的能力。

射頻識別；多比特識別；理論分析；滑動窗；部分比特碰撞機制

射頻識別技術RFID（Radio Frequency Identifi?cation）是一種通過射頻信號對帶有信息的標簽進行無線數據傳輸，實現非接觸通信的自動識別技術，是物聯網的重要組成部分。作為一種快速、實時、準確地采集與處理信息技術，RFID已經廣泛應用于各個領域和行業，并且深度地影響到社會經濟的發展。然而，RFID傳感網絡中閱讀器與標簽間的隱私保護、定位和標簽碰撞等問題嚴重制約著RFID的發展，其中核心的就是標簽碰撞問題［1-5］。

目前研究的防碰撞算法主要包括ALOHA防碰撞算法及樹形防碰撞算法。其ALOHA算法包括純ALOHA算法PA（Pure ALOHA）、幀時隙ALOHA算法FSA（Framed Slotted ALOHA）、動態幀時隙ALOHA算法DFSA（Dynamic Framed Slotted ALOHA）［6-9］等。這類算法主要特點是，算法結構簡單，容易實現，但標簽的接入存在不可預見性的問題，且識別效率相對較低。樹形防碰撞算法主要包括查詢樹算法QT（Query Tree）、二進制樹算法BT（Binary Tree）、碰撞樹算法CT（Collision Tree）［10-14］等。樹形防碰撞算法基于數據結構設計，不斷將產生碰撞的標簽分成多個子集逐個識別。標簽數目較多時識別延時較長。文獻［15-16］提出了MBI算法，將MQT防碰撞算法與純碰撞反演理論相結合，去除所有空時隙，實現了多比特識別，提高了系統的識別效率。然而，MBI算法仍然存在以下不足：（1）算法分析僅停留于給定仿真環境下的整體性能仿真，沒有針對算法進行完備的理論分析和建模；（2）算法在碰撞比特數大于1時不論標簽數量多少均開啟反演時隙，標簽數量較少時，標簽端分組小于閱讀器端預留分組，存在延時浪費問題，通信復雜度仍有提升空間；（3）標簽響應冗余度較大，即常規時隙中，閱讀器發送查詢前綴，匹配標簽不論碰撞與否都將回復除前綴外的所有ID信息，然而真正有用的信息只存在于第一個包含碰撞的識別段。

本文從概率的角度對MBI進行深入分析，完善其理論基礎。此外，針對MBI算法常規時隙標簽冗余響應以及反演時隙下空閑分組造成的時延浪費問題，引入滑動窗及部分碰撞比特恢復機制［17］，設計了改進多比特識別防碰撞算法（IMBI）。通過滑動窗智能地截取系統有用信息，阻止標簽無效數據的發送。對于系統空閑分組問題，通過部分比特恢復機制在標簽碰撞比特不大于反演長度M的對數時，直接恢復碰撞位數據信息，反之依照MBI算法開啟反演時隙。仿真結果表明，本文提出的理論模型對MBI算法有良好的逼近性能，通過與MBI算法以及傳統防碰撞算法的性能對比，不難發現IMBI算法有效的解決了MBI算法遺留的系列問題，系統的識別速度和吞吐率得到了極大的提升，并且能有效的降低系統能耗。

1 MBI算法簡介

文獻［15］結合標簽碰撞信息與集群特點提出MBI防碰撞算法，該算法通過陪集定理［18］對標簽進行分組實現多比特識別，去除了算法所有的空時隙，提高了系統的識別效率。并且碰撞越多，算法帶來的效益越大，是當前系統性能最高的樹形防碰撞算法之一。

1.1 碰撞反演條件

圖1 碰撞反演約束條件

1.2 MBI識別機制

MBI算法將純碰撞反演機制與傳統MQT算法結合，閱讀器以M比特為單位發送查詢前綴，標簽接收到查詢命令后與自身ID進行比對，匹配則發送標簽后面ID信息。閱讀器端接收狀態包括：空時隙、識別時隙、單比特碰撞時隙和多比特碰撞時隙。

閱讀器依照傳統QT算法對空時隙和識別時隙進行處理。對于單比特識別時隙，假設標簽碰撞為‘X101’，閱讀器則根據標簽ID的二元性直接在碰撞位分別給定比特‘0’和‘1’識別出‘0101’和‘1101’。MBI算法中包括常規時隙和反演時隙，當閱讀器端狀態反饋為空時隙、識別時隙、單比特碰撞時隙時，按照常規時隙操作，即上述步驟。當檢測到多個比特碰撞時開啟反演時隙，滿足條件的標簽首先遍歷事先存儲好的分組信息，確定自己分組后選擇相應的時隙發送查詢碼后M位標簽數據。閱讀器按分組順序將接收到的比特信息與參考碼字異或，即可得到當前反演長度下所有發送標簽的M位數據信息。

2 MBI算法理論分析與完善

MBI算法分析僅停留于仿真環境下的整體性能仿真，沒有針對算法進行完備的理論分析和建模。本章將從概率的角度分別對算法性能重要評價因子進行深入分析，完善MBI算法的理論基礎。模型如圖2所示。

2.1 時隙分析

假設系統內有N0個待識別標簽，系統初始分配叉樹為L0(L0=2M)，標簽ID長度為1且隨機均勻分布。N0個標簽隨機地從L0個分支中選取一個分支來發送自身ID數據。為考慮普適性，隨機抽取任意一個識別深度進行分析。假設當前識別深度為第k層，待識別標簽為N。

任意一個分支沒有標簽響應的概率可表示如下：

某個分支有且僅有一個標簽響應（識別時隙）的概率為：

當多個標簽同時選擇一個分支響應，且響應ID中只有一位比特產生碰撞，則稱該時隙為單比特識別時隙，概率可表示為：

多比特碰撞時隙產生于一個分支下有多個標簽回復且碰撞比特數大于1的情況，為以上各時隙集合的補集，故概率應為：

根據式（1）～式（4）易得當前搜索深度下各時隙數：

因而在該深度下分段碰撞反演所花總時隙應為：

2.2 平均延時分析

對某識別深度下所需通信延時進行分析，由于每個比特所需傳輸時間一定。為簡化分析，本模型中以傳輸的比特數代替延時。模型分別從反演時隙和常規時隙兩個角度討論。

常規時隙中，不論標簽數量是多少，總的延時可表示為：

其中，1為閱讀器為區分常規時隙和反演時隙增加的一位區分比特。

反演時隙中，延時不僅與標簽發送比特數M有關，還與分組數量有關。反演時隙總延時為：

則當前深度下總的識別延時為：

圖2 碰撞反演模型

2.3 平均標簽消耗分析

平均標簽消耗是RFID防碰撞算法性能的另一個重要指標，其表示識別過程中每個標簽平均發送的比特數。與延時分析類似，對平均標簽消耗的討論也從常規時隙及反演時隙兩方面進行，不同的是平均標簽消耗對標簽數量的變化更為敏感。同樣，針對某個識別深度探討標簽的平均消耗問題。通常情況，樹型結構的每個分支節點回復的標簽數量不定，難以分別計算。但每個識別深度其包含的標簽數量確定，通過對每層整體計算標簽消耗能極大的簡化分析。第k層識別深度下，常規時隙標簽消耗為：

在常規時隙過程中，部分標簽被識別而不再參與接下來的反演時隙響應，故反演時隙標簽消耗可表示如下：

則當前識別深度下總的標簽消耗為：

由于每個識別深度下的識別機制一致，只有標簽數量和分支節點數量不斷變化。故只需在識別過程中不斷更新標簽數量N及分支叉樹L即可得到系統每個識別深度的具體信息。整體建模表示如下：

3 改進型MBI防碰撞算法

本章將對改進型MBI防碰撞算法（IMBI）進行詳細介紹，該算法引入滑動窗和部分比特恢復機制，通過滑動窗逐段接收標簽響應序列，檢測到碰撞則提取出當前識別段并通知標簽停止ID數據的發送。系統使用曼切斯特編碼定位碰撞。為保證MBI時間復雜度不變，IMBI算法設定在碰撞比特數n滿足1＜n≤log2(M)時開啟部分比特恢復機制，閱讀器發送當前前綴及碰撞位的位置信息給標簽，匹配標簽提取碰撞對應位置ID數據轉化為十進制并將M位全0序列對應位置‘1’后發送給閱讀器。閱讀器通過檢測到的碰撞信息解析出當前識別段數據。IMBI算法針對性地解決MBI算法中標簽消耗冗余及反演時隙下標簽數量較少場景時的延時浪費問題，能有效的減小系統的時間復雜度及系統能耗。

圖3 IMBI防碰撞算法流程

IMBI防碰撞算法流程如圖3所示，其具體步驟為：

（1）閱讀器檢查前綴堆棧，不為空則取出前綴發送常規時隙查詢命令并等待標簽的響應。

（2）標簽收到查詢命令后首先與自身ID進行比對，前綴匹配的標簽回復除前綴外的所有ID。

（3）閱讀器以長度為M的滑動窗對接收到的標簽響應逐段識別，確定出窗內標簽響應碰撞的位置及碰撞比特數量n。

①若沒有碰撞，則將該識別段與查詢前綴合并作為新的前綴存入前綴堆棧，識別滑動窗往后滑動M位比特的距離，開始識別下一個響應段；②若只有一個比特碰撞，通知標簽停止發送后面ID，將碰撞位分別置‘0’和‘1’，與查詢前綴合并存入前綴堆棧；③若碰撞比特數n≤log2(M)，通知標簽停止發送后面ID，閱讀器重新發送本輪查詢前綴信息及前log2(M)位碰撞比特的位置信息，開啟部分比特識別機制，執行步驟（4）；④若碰撞比特數n＞log2(M)，閱讀器重新發送本輪查詢前綴信息后面加上反演時隙標識碼‘1’，開啟反演時隙識別模式，執行步驟（6）、步驟（7）。

（4）前綴匹配的標簽取出碰撞位所對應比特數據轉化為十進制，生成長度為M的全0序列并將其對應位置比特置‘1’后重新響應。

（5）閱讀器重新接收標簽數據，根據碰撞信息解讀出上輪查詢時隙響應標簽碰撞位傳輸比特數據，替換掉碰撞比特后與查詢前綴合并存入前綴堆棧。

（6）前綴匹配的標簽首先遍歷事先存儲好的分組信息，確定自身分組后選擇相應的時隙發送查詢前綴后M位標簽數據。

（7）閱讀器按分組順序將接收到的比特信息與參考碼字異或，得到當前反演長度下所有發送標簽的M位數據信息，與查詢前綴合并存于前綴堆棧。

下面通過一個實例講解當反演長度M=4時IMBI防碰撞算法的具體工作流程，假設閱讀器通信范圍內存在8個ID長度為16的標簽tag1～tag8，如表1所示。

表1 實例標簽ID信息

IMBI算法實例步驟如下：

（1）由于初始前綴為空，閱讀器發送查詢命令(ε,0)，tag1～tag8均滿足條件回復。閱讀器以長度為4的滑動窗對標簽響應進行逐段識別，檢測到第一個識別段為‘00X0’，有一個比特的碰撞，則立即通知標簽停止后面ID的發送，閱讀器將碰撞位分別置‘0’和‘1’得‘0000’和‘0010’并將其壓入前綴堆棧；

（2）閱讀器從前綴堆棧取出前綴發送查詢命令（0000，0），tag1、tag2和tag4前綴匹配回復后面12 bit ID信息。閱讀器檢測到第一個識別段為‘X1X0’，存在碰撞，通知標簽停止繼續發送后面8 bit ID。因為碰撞比特數為2≤log2(4)，開啟部分比特恢復機制；

（3）閱讀器發送查詢命令（0000.X1X0，0）通知標簽碰撞位置為bite0和bite3。tag1、tag2和tag4分別提取出對應位置的ID信息組成新的序列‘00’、‘10’和‘11’并轉化為十進制‘0001’、‘0100’和‘1000’重新發送。閱讀器接收到響應信息‘XX0X’，通過碰撞的位置得到標簽在碰撞位的ID序列分別為‘00’、‘10’和‘11’，分別替換0000.X1X0中的碰撞位置比特得到最終恢復序列0000.0100、0000.1100和0000.1110并存于前綴堆棧。

（4）閱讀器分別發送（0000.0100，0）、（0000.1100，0）和（0000.1110，0）三個查詢碼，標簽端tag1、tag2和tag4分別對應響應，閱讀器未檢測到碰撞，為識別時隙，故tag1、tag2和tag4直接識別。

（5）閱讀器從前綴堆棧中取出（0010，0）開始發送，tag3、tag5～tag8均滿足條件響應，滑動窗截取前4位比特‘XXXX’，由于碰撞數n＞log2() 4，閱讀器開啟反演時隙發送反演前綴（0010，1）進行查詢。

（6）tag3、tag5～tag8分別查閱事先存儲的分組方案確定自身ID發送時隙并發送‘0010’后4位ID信息，tag3和tag5為第1組，tag6第2組，tag8、tag7分別為第3組和第4組。閱讀器端接收到‘0XX0.0011.0101.1011’，第1組中第2位、第3位比特產生碰撞，閱讀器分別將參考碼字‘0000’的第2位、第3位取反得‘'0100’、‘0010’。其余3組沒有碰撞產生，閱讀器直接識別。將‘0100’、‘0010’、‘0011’、‘0101’和‘1011’分別與查詢前綴‘0010’合并存入前綴堆棧。

（7）閱讀器分別查詢（0010.0010，0）、（0010.0100，0）、（0010.0011，0）、（0010.1011，0）和（0010.0101，0），tag3、tag5、tag6、tag7和tag8分別回復，無碰撞產生，為識別時隙。

（8）閱讀器檢測到前綴堆棧為空，識別結束。

具體識別流程如圖4所示。

圖4 IMBI算法識別實例圖

4 模型驗證及仿真結果分析

4.1 MBI模型驗證分析

為驗證該模型的正確性，文中對此算法涉及的三項性能指標進行理論逼近。設定標簽ID長度為64 bit，標簽分布為均勻分布，標簽數量變化范圍為1～1 024，每個標簽循環次數為50次。圖5為系統3項基本性能指標的理論模型分析與實際情況的仿真對比。不難發現，不論是系統總時隙、平均標簽消耗還是系統平均時延，該模型都有良好的逼近性能。模型與實際結果存在較小誤差的原因在于模型是通過統計理論建立，概率分析與實際情況必然存在一定誤差，當仿真次數達到一定數量時誤差會隨之減小。通過以上對比分析可以證明模型對算法具有較好的逼近能力，同時證明了模型建立的正確性。

圖5 模型驗證結果分析

4.2 改進MBI防碰撞算法仿真分析

對提出的改進型MBI防碰撞算法（IMBI）進行仿真，仿真條件與上述模型驗證一致。圖6（a）～6（c）分別為IMBI算法與MBI，QT，JDS，NEAA算法所需總時隙、標簽平均消耗、系統平均延時的比較。

圖6 改進MBI算法仿真分析

圖6（a）為系統總時隙分析，可以看出，與傳統樹形算法相比，IMBI算法與MBI算法的系統識別時隙性能最佳，這是因為MBI類型算法采用碰撞反演識別機制，充分利用碰撞信息去除空閑時隙實現了多比特識別。MBI（4）與IMBI（4）、MBI（8）與IMBI（8）曲線重合是由于IMBI算法只針對性地解決系統標簽消耗冗余及延時浪費問題，并沒有對系統時隙進行改進。

圖6（b）是標簽平均消耗的仿真對比，由圖可知IMBI算法在標簽平均消耗上同樣具有最佳性能。IMBI引入滑動窗及部分比特識別機制能極大地提升系統性能，M=4時標簽消耗相對于MBI算法減少了近19.7%，相對于QT算法減少了32.5%。M=8時標簽消耗相對于MBI算法減少了近13.9%，相對于QT算法減少近32.4%。M=8的性能提升優于M=4是由于M=4時的碰撞時隙數多于M=8，M=4的樹形結構對比于M=8為縱向擴展，識別深度大于M=8，標簽重復響應次數較多，故加入滑動窗后性能提升較大。

圖6（c）為系統平均延時分析，與傳統的QT，JDS，NEAA算法相比，MBI（4）系統延時最小，為QT的50%。MBI（8）由于存在反演時隙標簽空閑分組問題，在標簽數量較少時，隨著標簽數的增加而急劇增長。但當標簽數量增大到500左右時，系統延時隨標簽增長呈下降趨勢。IMBI算法在MBI的基礎上進行改進，有效地降低了MBI（4）及MBI（8）的系統延時。M=4與M=8性能提升幅度相近在于除了滑動窗帶來的系統效益外，部分比特恢復機制有效的消除了空閑分組帶來的時延浪費，進一步減小了系統時間復雜度，且該機制給系統帶來的效益隨著M的增大而增大。

5 結語

本文從概率的角度出發，構建了MBI防碰撞算法的理論分析模型，完善了算法的理論體系。通過該模型，我們只需得知閱讀器識別范圍內標簽數量，即可快速有效地對系統識別性能進行分析。同時，該模型逐層描述了分段碰撞反演算法的識別機制，有助于進一步的對此算法進行深入研究。此外，本文針對MBI防碰撞算法標簽響應冗余及反演時隙中空閑分組延時浪費問題，引入滑動窗以及部分比特恢復機制，在不增大系統實現復雜度的基礎上，大幅度提升了系統的性能，具有一定的創新性和實用性。

［1］Hugo L，Asier P，Enrique O，et al.An Energy and Identification Time Decreasing Procedure for Memory-Less RFID Tag Anti-Col?lision Protocols［J］.IEEE Transactions on Wireless Communica?tions，2016（99）：1.

［2］Zhang D，Wang X，Song X，et al.A Novel Approach to Mapped Correlation of ID for RFID Anti-Collision［J］.IEEE Transactions on Services Computing，2014，7（4）：741-748.

［3］劉明生，王艷，趙新生.基于Hash函數的RFID安全認證協議的研究［J］.傳感技術學報2011，24（9）：1317-1321.

［4］周治平，張惠根.一種更具實用性的移動RFID認證協議［J］.傳感技術學報，2016，29（2）：271-277.

［5］李勃，毛陸虹，張世林，等.集成于無源UHF RFID標簽的寬溫測范圍CMOS溫度傳感器［J］.傳感技術學報，2014，27（5）：581-586.

［6］Dheeraj K K，Kwan-Wu C，Raad R.A Survey and Tutorial of RFID Anti-Collision Protocols［J］.IEEE Communications Surveys &Tutorials，2010，12（3）：400-421.

［7］Zhu L.A Theory of RFID Anti-Collision Mechanisms［M］.The Chi?nese University of Hong Kong（People’s Republic of China），2010.

［8］Li X.A Study of Anti-Collision Multi-Tag Identification Algorithms for Passive RFID Systems［D］.University of North Texas，2010.

［9］Shao Chenglong，Kim Taekyung，Yu Jieun，et al.ProTaR：Probabi?listic Tag Retardation for Missing Tag Identification in Large-Scale RFID Systems［J］IEEE Transactions on Industrial Informat?ics，2015，11（2）：513-522.

［10］Myung J，Lee W，Shih T K.An Adaptive Memoryless Protocol for RFID Tag Collision Arbitration［J］.IEEE Transactions on Multi?media，2006，8（5）：1096-1101.

［11］Chen Y H，Horng S J，Run R S，et al.A Novel Anti-Collision Algo?rithm in RFID Systems for Identifying Passive Tags［J］.IEEE Transactions on Industrial Informatics，2010，6（1）：105-121.

［12］Jihoon Myung，Wonjun Lee，Jaideep Srivastava，et al.Adaptive Bi?nary Splitting for Efficient RFID Tag Anti-Collision［J］.IEEE Communications Letters，2006，10（3）：144-146.

［13］Landaluce H，Perallos A，Bengtsson L，et al.Simplified Computa?tion in Memoryless Anti-Collision RFID Identification Protocols［J］.Electronics Letters，2014，50（17）：1250-1252.

［14］Su J，Sheng Z，Hong D，et al.An Effective Frame Breaking Policy for Dynamic Framed Slotted Aloha in RFID［J］.IEEE Communi?cations Letters，2016，20（4）：692-695.

［15］Wang Y，Liu Y，Leung H，et al.A Multi-Bit Identification Protocol for RFID Tag Reading［J］.IEEE Sensors Journal，2013，13（10）：3527-3536.

［16］Wang Y，Liu Y，Leung H，et al.A Segment Collision Inversion Protocol for RFID Tag Reading［J］.IEEE Communications Let?ters，2013，17（10）：2008-2011.

［17］Landaluce H，Perallos A，Zuazola I J G，et al.A Fast RFID Identifi cation Protocol With Low Tag Complexity［J］.IEEE Communica?tions Letters，2013，17（9）：1704-1706.

［18］耿素云，屈婉玲，王捍貧.離散數學教程［M］.北京：北京大學出版社，2002.

［19］劉祎.基于多比特識別的RFID標簽防碰撞算法［D］.南昌：南昌大學，2013.

李 唯（1991-），女，南昌大學信息工程學院碩士研究生，主要研究方向為RFID防碰撞協議及無線通信，1522151783@ qq.com；

王玉皞（1977-），男，南昌大學博士生導師，主要研究方向為寬帶無線通信，雷達通信一體化，RFID等，wangyuhao@ncu.edu.cn；

孫 宇（1989-），男，南昌大學信息工程學院碩士研究生，主要研究方向為RFID防碰撞協議及無線通信，1043360657@ qq.com。

An Improved MBI Anti-Collision Algorithm for Identification of RFID Tag*

LI Wei，WANG Yuhao*，SUN Yu，ZENG Jian
（College of Information Engineering，Nanchang University，Nanchang 330031，China）

Based on the in-depth study of MBI，a model for perfecting the theory of MBI is established from the view?point of probability in this paper.Furthermore，a improved Multi-Bit Identification Protocol（IMBI）is proposed to re?duce the communication overhead of the conventional MBI algorithm.By means of introducing sliding window and partial bits recovery mechanism，the proposed algorithm can solve the problems of tag response redundancy in regu?lar slot and idle groups in inversion slot simultaneously.In addition，it improves the efficiency of recognition in RFID system without increasing any time complexity.The simulations reveal that the model established has good ap?proximation performance.And the proposed algorithm has a better performance on tag average consumption and sys?tem delay，thus it improves the ability to deal with massive tag data.

RFID；MBI；Theoretical Analysis；sliding window；partial bits recovery mechanism

TP393

A

1004-1699（2016）11-1711-07

EEACC：6150P；6110；6140 10.3969/j.issn.1004-1699.2016.11.014

項目來源：面向動態本地無線環境的電波傳播特征認知方法研究項目（61261010）；寬帶無線通信與雷達感知融合系統關鍵技術研究項目（20142BCB23001）

2016-05-10 修改日期：2016-07-04