改進(jìn)型MBI防碰撞算法研究*

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

（南昌大學(xué)信息工程學(xué)院，南昌330031）

改進(jìn)型MBI防碰撞算法研究*

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

（南昌大學(xué)信息工程學(xué)院，南昌330031）

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

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

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

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

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

1 MBI算法簡介

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

1.1 碰撞反演條件

圖1 碰撞反演約束條件

1.2 MBI識別機制

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

閱讀器依照傳統(tǒng)QT算法對空時隙和識別時隙進(jìn)行處理。對于單比特識別時隙，假設(shè)標(biāo)簽碰撞為‘X101’，閱讀器則根據(jù)標(biāo)簽ID的二元性直接在碰撞位分別給定比特‘0’和‘1’識別出‘0101’和‘1101’。MBI算法中包括常規(guī)時隙和反演時隙，當(dāng)閱讀器端狀態(tài)反饋為空時隙、識別時隙、單比特碰撞時隙時，按照常規(guī)時隙操作，即上述步驟。當(dāng)檢測到多個比特碰撞時開啟反演時隙，滿足條件的標(biāo)簽首先遍歷事先存儲好的分組信息，確定自己分組后選擇相應(yīng)的時隙發(fā)送查詢碼后M位標(biāo)簽數(shù)據(jù)。閱讀器按分組順序?qū)⒔邮盏降谋忍匦畔⑴c參考碼字異或，即可得到當(dāng)前反演長度下所有發(fā)送標(biāo)簽的M位數(shù)據(jù)信息。

2 MBI算法理論分析與完善

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

2.1 時隙分析

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

任意一個分支沒有標(biāo)簽響應(yīng)的概率可表示如下：

某個分支有且僅有一個標(biāo)簽響應(yīng)（識別時隙）的概率為：

當(dāng)多個標(biāo)簽同時選擇一個分支響應(yīng)，且響應(yīng)ID中只有一位比特產(chǎn)生碰撞，則稱該時隙為單比特識別時隙，概率可表示為：

多比特碰撞時隙產(chǎn)生于一個分支下有多個標(biāo)簽回復(fù)且碰撞比特數(shù)大于1的情況，為以上各時隙集合的補集，故概率應(yīng)為：

根據(jù)式（1）～式（4）易得當(dāng)前搜索深度下各時隙數(shù)：

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

2.2 平均延時分析

對某識別深度下所需通信延時進(jìn)行分析，由于每個比特所需傳輸時間一定。為簡化分析，本模型中以傳輸?shù)谋忍財?shù)代替延時。模型分別從反演時隙和常規(guī)時隙兩個角度討論。

常規(guī)時隙中，不論標(biāo)簽數(shù)量是多少，總的延時可表示為：

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

反演時隙中，延時不僅與標(biāo)簽發(fā)送比特數(shù)M有關(guān)，還與分組數(shù)量有關(guān)。反演時隙總延時為：

則當(dāng)前深度下總的識別延時為：

圖2 碰撞反演模型

2.3 平均標(biāo)簽消耗分析

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

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

則當(dāng)前識別深度下總的標(biāo)簽消耗為：

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

3 改進(jìn)型MBI防碰撞算法

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

圖3 IMBI防碰撞算法流程

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

（1）閱讀器檢查前綴堆棧，不為空則取出前綴發(fā)送常規(guī)時隙查詢命令并等待標(biāo)簽的響應(yīng)。

（2）標(biāo)簽收到查詢命令后首先與自身ID進(jìn)行比對，前綴匹配的標(biāo)簽回復(fù)除前綴外的所有ID。

（3）閱讀器以長度為M的滑動窗對接收到的標(biāo)簽響應(yīng)逐段識別，確定出窗內(nèi)標(biāo)簽響應(yīng)碰撞的位置及碰撞比特數(shù)量n。

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

（4）前綴匹配的標(biāo)簽取出碰撞位所對應(yīng)比特數(shù)據(jù)轉(zhuǎn)化為十進(jìn)制，生成長度為M的全0序列并將其對應(yīng)位置比特置‘1’后重新響應(yīng)。

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

（6）前綴匹配的標(biāo)簽首先遍歷事先存儲好的分組信息，確定自身分組后選擇相應(yīng)的時隙發(fā)送查詢前綴后M位標(biāo)簽數(shù)據(jù)。

（7）閱讀器按分組順序?qū)⒔邮盏降谋忍匦畔⑴c參考碼字異或，得到當(dāng)前反演長度下所有發(fā)送標(biāo)簽的M位數(shù)據(jù)信息，與查詢前綴合并存于前綴堆棧。

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

表1 實例標(biāo)簽ID信息

IMBI算法實例步驟如下：

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

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

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

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

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

（6）tag3、tag5～tag8分別查閱事先存儲的分組方案確定自身ID發(fā)送時隙并發(fā)送‘0010’后4位ID信息，tag3和tag5為第1組，tag6第2組，tag8、tag7分別為第3組和第4組。閱讀器端接收到‘0XX0.0011.0101.1011’，第1組中第2位、第3位比特產(chǎn)生碰撞，閱讀器分別將參考碼字‘0000’的第2位、第3位取反得‘'0100’、‘0010’。其余3組沒有碰撞產(chǎn)生，閱讀器直接識別。將‘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分別回復(fù)，無碰撞產(chǎn)生，為識別時隙。

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

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

圖4 IMBI算法識別實例圖

4 模型驗證及仿真結(jié)果分析

4.1 MBI模型驗證分析

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

圖5 模型驗證結(jié)果分析

4.2 改進(jìn)MBI防碰撞算法仿真分析

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

圖6 改進(jìn)MBI算法仿真分析

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

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

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

5 結(jié)語

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

［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函數(shù)的RFID安全認(rèn)證協(xié)議的研究［J］.傳感技術(shù)學(xué)報2011，24（9）：1317-1321.

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

［5］李勃，毛陸虹，張世林，等.集成于無源UHF RFID標(biāo)簽的寬溫測范圍CMOS溫度傳感器［J］.傳感技術(shù)學(xué)報，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］耿素云，屈婉玲，王捍貧.離散數(shù)學(xué)教程［M］.北京：北京大學(xué)出版社，2002.

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

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

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

孫 宇（1989-），男，南昌大學(xué)信息工程學(xué)院碩士研究生，主要研究方向為RFID防碰撞協(xié)議及無線通信，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

項目來源：面向動態(tài)本地?zé)o線環(huán)境的電波傳播特征認(rèn)知方法研究項目（61261010）；寬帶無線通信與雷達(dá)感知融合系統(tǒng)關(guān)鍵技術(shù)研究項目（20142BCB23001）

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