何申炎，楊恒新，張 昀

(南京郵電大學(xué) 電子科學(xué)與工程學(xué)院，江蘇 南京 210003)

基于映射序列碼的多叉樹防碰撞算法

何申炎，楊恒新，張 昀

(南京郵電大學(xué) 電子科學(xué)與工程學(xué)院，江蘇 南京 210003)

隨著物聯(lián)網(wǎng)技術(shù)的發(fā)展，射頻識(shí)別(RFID)技術(shù)得到了廣泛應(yīng)用。標(biāo)簽碰撞問題嚴(yán)重影響RFID系統(tǒng)的識(shí)別效率，因此多標(biāo)簽防碰撞算法成為了研究RFID技術(shù)的關(guān)鍵。為此，提出了一種基于映射序列碼的多叉樹標(biāo)簽防碰撞算法，其主要思想是在多叉樹的基礎(chǔ)上，將閱讀器識(shí)別范圍內(nèi)的標(biāo)簽識(shí)別碼進(jìn)行分組，根據(jù)唯一的映射關(guān)系確定存在的查詢前綴，消除了多叉樹的空閑時(shí)隙，減少了碰撞時(shí)隙；同時(shí)標(biāo)簽在響應(yīng)閱讀器時(shí)，只需要發(fā)送其與查詢前綴相匹配后的剩余部分，減少了信息的傳輸量，降低了系統(tǒng)能耗。Matlab仿真結(jié)果表明，所提出的算法有效減少了標(biāo)簽識(shí)別的總時(shí)隙數(shù)，系統(tǒng)的識(shí)別效率可以達(dá)到71%左右，系統(tǒng)性能有了明顯的提升，當(dāng)標(biāo)簽識(shí)別碼位數(shù)長，標(biāo)簽數(shù)量多時(shí)，算法性能的提升尤為顯著。

射頻識(shí)別；標(biāo)簽防碰撞；多叉樹；映射關(guān)系

0 引 言

物聯(lián)網(wǎng)是新一代信息技術(shù)的重要組成部分，即通過射頻識(shí)別(RFID)、紅外感應(yīng)器、全球定位系統(tǒng)、激光掃描器、氣體感應(yīng)器等信息傳感設(shè)備，按約定協(xié)議，把任何物品與互聯(lián)網(wǎng)連接起來，進(jìn)行信息交換和通訊，以實(shí)現(xiàn)智能化識(shí)別、定位、跟蹤、監(jiān)控和管理的一種網(wǎng)絡(luò)。RFID技術(shù)、傳感器技術(shù)、納米技術(shù)、智能嵌入技術(shù)是實(shí)現(xiàn)物聯(lián)網(wǎng)的四大核心技術(shù)。隨著物聯(lián)網(wǎng)技術(shù)和應(yīng)用的不斷深入，RFID技術(shù)已成為當(dāng)前研究的熱點(diǎn)[1]。

無線射頻識(shí)別(Radio Frequency IDentification,RFID)技術(shù)是一種以空間電磁波為傳輸媒介的非接觸式自動(dòng)數(shù)據(jù)采集技術(shù)，系統(tǒng)間通過發(fā)送無線射頻信號(hào)實(shí)現(xiàn)數(shù)據(jù)信息的自動(dòng)識(shí)別和雙向通信。典型的RFID系統(tǒng)主要由閱讀器、電子標(biāo)簽和中央處理系統(tǒng)三大部分組成。當(dāng)閱讀器的作用范圍內(nèi)存在多個(gè)標(biāo)簽，并有一個(gè)以上的標(biāo)簽同時(shí)響應(yīng)閱讀器時(shí)將會(huì)產(chǎn)生碰撞，這種碰撞稱為標(biāo)簽碰撞[2]。這種碰撞會(huì)導(dǎo)致閱讀器不能成功識(shí)別標(biāo)簽，嚴(yán)重影響RFID系統(tǒng)的識(shí)別效率。

RFID防碰撞算法一般有基于空分多址(Space Division Multiple Access，SDMA)、頻分多址(Frequency Division Multiple Access，F(xiàn)DMA)、碼分多址(Code Division Multiple Access，CDMA)、時(shí)分多址(Time Division Multiple Access，TDMA)[3]等四種方式。其中TDMA應(yīng)用最廣泛?，F(xiàn)有的防碰撞算法主要分為基于ALOHA的隨機(jī)性算法和基于樹的確定性算法?；贏LOHA的防碰撞算法[4]主要包括三種：純ALOHA算法、幀時(shí)隙ALOHA算法和動(dòng)態(tài)幀時(shí)隙ALOHA算法。基于樹的防碰撞算法[5-6]主要包括二進(jìn)制樹(BT)算法和查詢樹(QT)算法，以及基于BT和QT進(jìn)行改進(jìn)的算法。

基于ALOHA的防碰撞算法需要一個(gè)時(shí)鐘電路來解決同步問題，且存在一個(gè)致命缺點(diǎn)：由于標(biāo)簽長時(shí)間無法被閱讀器識(shí)別而導(dǎo)致標(biāo)簽“餓死”?；跇涞姆琅鲎菜惴ú恍枰剑⑶医鉀Q了標(biāo)簽“餓死”問題，但仍存在識(shí)別周期長、標(biāo)簽?zāi)芎拇蟮葐栴}。

針對(duì)上述問題，提出了一種基于映射序列碼的多叉樹標(biāo)簽防碰撞算法。主要思想是在多叉樹的基礎(chǔ)上，將閱讀器識(shí)別范圍內(nèi)的標(biāo)簽識(shí)別碼進(jìn)行分組，根據(jù)唯一的映射關(guān)系確定存在的查詢前綴，消除多叉樹的空閑時(shí)隙，減少碰撞時(shí)隙；同時(shí)標(biāo)簽在響應(yīng)閱讀器時(shí)，只需要發(fā)送其與查詢前綴相匹配后的剩余部分，減少了信息的傳輸量，降低了系統(tǒng)能耗。

1 查詢樹算法

QT算法是一種無記憶算法，對(duì)標(biāo)簽計(jì)算能力的唯一要求就是將它的識(shí)別碼與查詢命令中的二進(jìn)制序列進(jìn)行比較[7]，只有當(dāng)二者一致時(shí)，標(biāo)簽才進(jìn)行響應(yīng)。當(dāng)只有一個(gè)標(biāo)簽響應(yīng)閱讀器時(shí)，標(biāo)簽被成功識(shí)別；當(dāng)有一個(gè)以上標(biāo)簽同時(shí)響應(yīng)閱讀器時(shí)，通過在原查詢前綴的基礎(chǔ)上加上一位1或0生成新的查詢前綴，繼續(xù)查詢，直到成功識(shí)別所有的標(biāo)簽[8]。

QT算法的基本識(shí)別過程如下：閱讀器初始化查詢前綴堆棧為0和1，當(dāng)堆棧不為空時(shí)，閱讀器發(fā)送查詢命令，堆棧中的查詢前綴出棧并更新堆棧。若只有一個(gè)標(biāo)簽響應(yīng)，則識(shí)別該標(biāo)簽；若有一個(gè)以上標(biāo)簽響應(yīng)，則表明發(fā)生碰撞，分別在原查詢前綴后加0和1作為新的查詢前綴，并壓入堆棧中；若沒有標(biāo)簽響應(yīng)，則不進(jìn)行任何操作。重復(fù)以上操作，直到堆棧為空。當(dāng)標(biāo)簽接收到閱讀器的查詢命令，判斷自身的ID號(hào)和查詢前綴是否一致，若一致則發(fā)送ID的剩余部分給閱讀器，若不一致，則標(biāo)簽不響應(yīng)。假設(shè)有四個(gè)標(biāo)簽A、B、C、D，它們的ID分別為0010、1010、1011、0101。則它們的識(shí)別過程如表1所示。

表1 查詢樹算法識(shí)別過程

從表1可以看出，成功識(shí)別四個(gè)ID長度為4的標(biāo)簽，需要9次查詢，其中產(chǎn)生了過多的碰撞時(shí)隙，算法的運(yùn)行時(shí)間較長，導(dǎo)致識(shí)別效率過低。為此，對(duì)QT算法進(jìn)行了各種改進(jìn)。Law C等提出了shortcuttingQT算法[9]，若在閱讀器查詢前綴q時(shí)發(fā)生了碰撞，則在q后加上0和1繼續(xù)查詢。如果閱讀器先查詢q0，沒有標(biāo)簽響應(yīng)，則前綴為q1的標(biāo)簽至少為2個(gè)，肯定會(huì)發(fā)生碰撞，因此可以跳過前綴q1，直接查詢前綴q10和q11，所以shortcuttingQT算法在一定程度上減少了查詢次數(shù)，縮短了算法的運(yùn)行時(shí)間。Jia等提出了一種CT算法[6]，它的查詢過程只針對(duì)碰撞位，使用查詢前綴查詢碰撞位，和QT算法相比，避免了對(duì)ID號(hào)相同部分的查詢，減少了碰撞周期和空閑周期，提高了識(shí)別效率。另外，最壞的情況下，就是出現(xiàn)大量標(biāo)簽導(dǎo)致所有位都發(fā)生碰撞，這種情況下，CT算法的性能和QT算法相同。

2 基于多叉樹的改進(jìn)型防碰撞算法

2.1 算法描述

目前在查詢樹算法的基礎(chǔ)上，提出了很多改進(jìn)算法。文獻(xiàn)[10]提出了一種基于分組碼的改進(jìn)型防碰撞算法，其主要思想是：首先采用分組碼將標(biāo)簽識(shí)別碼進(jìn)行分組，根據(jù)碰撞位置可以確定存在的分組碼，在八叉樹的基礎(chǔ)上，去除了空閑時(shí)隙，提高了識(shí)別效率。但是，在識(shí)別過程中，由于引入了分組碼，產(chǎn)生了二次發(fā)送，增加了八叉樹的時(shí)隙數(shù)。提出了基于多叉樹的防碰撞算法，減少碰撞時(shí)隙的同時(shí)，引入了映射序列碼，消除了空閑時(shí)隙，提高了算法的識(shí)別效率，同時(shí)減少了數(shù)據(jù)的通信量。

該算法包含分組操作和映射識(shí)別操作兩個(gè)部分。

(1)分組操作。

所有標(biāo)簽先對(duì)識(shí)別碼進(jìn)行分組，每3比特標(biāo)簽識(shí)別碼為一組，若最后剩余的標(biāo)簽識(shí)別碼不足3比特時(shí)，剩余比特識(shí)別碼為一組。假設(shè)長度為n的標(biāo)簽識(shí)別碼為P1P2…Pn，則P1P2P3為第1組標(biāo)簽識(shí)別碼，P4P5P6為第2組標(biāo)簽識(shí)別碼，依次類推，若n=3k，則第k組為Pn-2Pn-1Pn，若n=3k-1，則第k組為Pn-1Pn，若n=3k-2，則第k組為Pn。

(2)映射識(shí)別操作。

閱讀器發(fā)送Query(k)指令，第一次發(fā)送時(shí)k=1，標(biāo)簽將第1組3比特標(biāo)簽識(shí)別碼的映射序列碼發(fā)送給閱讀器，映射關(guān)系如表2和表3所示。

閱讀器對(duì)接收到的信息進(jìn)行譯碼，得到初始查詢前綴并壓入堆棧。這里，閱讀器利用曼徹斯特編碼識(shí)別出具體碰撞位。假設(shè)三個(gè)標(biāo)簽分別為a：101，b：001，c：100，由映射關(guān)系表得到，它們的映射序列碼分別為：a：00100000，b：00000010，c：00010000，閱讀器得到譯碼結(jié)果為00XX00X0，可得存在101、100、001三種查詢前綴。

表2 映射關(guān)系表(1)

表3 映射關(guān)系表(2)

2.2 算法流程

(1)初始化查詢前綴堆棧Q，閱讀器發(fā)送Request(NULL)通信請(qǐng)求命令，使工作范圍內(nèi)的所有標(biāo)簽進(jìn)行響應(yīng)。

(2)閱讀器發(fā)送Query(k)指令，將標(biāo)簽ID號(hào)的第k組標(biāo)簽識(shí)別碼的映射序列碼發(fā)送給閱讀器，第一次發(fā)送時(shí)k=1，這個(gè)映射序列碼準(zhǔn)確地反映了標(biāo)簽的碰撞信息。閱讀器收到映射序列碼并進(jìn)行譯碼，根據(jù)碰撞位置判斷存在的查詢前綴，然后依次壓入查詢前綴堆棧Q中。若k不等于1，則在原查詢前綴PRE后加上第k組標(biāo)簽序列碼得到新的查詢前綴，并依次壓入堆棧Q中。若第k組標(biāo)簽識(shí)別碼為2bit，由映射序列碼得到標(biāo)簽識(shí)別碼，并依次壓入堆棧。若第k組標(biāo)簽識(shí)別碼為1bit，則直接識(shí)別兩個(gè)標(biāo)簽。

(3)閱讀器發(fā)送Request(PRE)命令，PRE取值為堆棧中的查詢前綴，與查詢前綴匹配的標(biāo)簽響應(yīng)，檢測是否發(fā)生碰撞，若沒有發(fā)生碰撞，則發(fā)送標(biāo)簽ID的剩余部分給閱讀器，成功識(shí)別標(biāo)簽；如果判斷出有碰撞，則使k=k+1，發(fā)生碰撞的標(biāo)簽發(fā)送下一組標(biāo)簽ID的映射序列碼給閱讀器，跳回步驟2，直到標(biāo)簽被成功識(shí)別。

(4)判斷堆棧Q是否為空，若不為空，則轉(zhuǎn)回步驟3，若為空，則識(shí)別結(jié)束。

算法流程如圖1所示。

圖1 算法流程圖

2.3 算法識(shí)別過程舉例

假設(shè)有8個(gè)標(biāo)簽A、B、C、D、E、F、G、H在閱讀器的工作域，標(biāo)簽ID號(hào)分別為：10110101，11100011，10100111，11011011，10000011，11010011，10010101，10011111。

算法查詢過程如表4所示。

由表4可知，識(shí)別這8個(gè)標(biāo)簽一共查詢了12次，其中產(chǎn)生3次碰撞，并去除了多叉樹中的所有空閑時(shí)隙。與QT算法相比，減少了查詢次數(shù)，提高了識(shí)別效率。

表4 算法查詢過程

3 仿真分析

為了更好地驗(yàn)證改進(jìn)算法的性能，通過Matlab仿真工具對(duì)該改進(jìn)算法、shortcuttingQT算法、CT算法、四叉樹算法、八叉樹算法的各方面性能進(jìn)行對(duì)比。

由文獻(xiàn)[6]可知，CT算法識(shí)別n個(gè)標(biāo)簽所用的總時(shí)隙為：

T(n)=2n-1

(1)

算法識(shí)別效率為：

(2)

文獻(xiàn)[11]對(duì)于多叉樹的性能分析中，利用式(3)來計(jì)算總時(shí)隙數(shù)：

(3)

由式(4)得到算法的識(shí)別效率：

(4)

其中，B為叉數(shù)；L為當(dāng)前所在的層數(shù)；m為標(biāo)簽總數(shù)。

將分別取B=4(四叉樹)和B=8(八叉樹)進(jìn)行仿真。圖2中對(duì)提出的改進(jìn)算法以及shortcuttingQT算法、CT算法、四叉樹算法、八叉樹算法識(shí)別標(biāo)簽的總時(shí)隙進(jìn)行了比較。

由圖2可以看出，與其他四種算法相比，該改進(jìn)算法需要的總時(shí)隙明顯要少。當(dāng)標(biāo)簽數(shù)量達(dá)到1 000時(shí)，該改進(jìn)算法需要消耗1 390個(gè)總時(shí)隙，比QT算法少用了30.5%的時(shí)隙,比shortcuttingQT算法少用了接近40%的時(shí)隙，比四叉樹算法少用了51.9%的時(shí)隙，和消耗總時(shí)隙最多的八叉樹算法相比，節(jié)省了64.7%的時(shí)隙。該改進(jìn)算法通過使用映射序列碼，消除了空閑時(shí)隙，避免了無效查詢，同時(shí)減少了查詢所需的總時(shí)隙。所以，相比其他四種算法，使用了最少的識(shí)別總時(shí)隙，大大提高了算法的總體性能。

圖2 五種算法總時(shí)隙性能比較

圖3對(duì)所提出的改進(jìn)算法以及shortcuttingQT算法、CT算法、四叉樹算法、八叉樹算法的識(shí)別效率(吞吐率)進(jìn)行了比較。

圖3 五種算法識(shí)別效率比較

從圖3可以看出，八叉樹算法的識(shí)別效率最低，在25%～27%；而四叉樹算法和shortcuttingQT算法的識(shí)別效率也都低于50%；CT算法的識(shí)別效率達(dá)到了50%；而改進(jìn)算法的效率能達(dá)到71%左右，性能明顯優(yōu)于其他四種算法。

4 結(jié)束語

傳統(tǒng)QT算法雖然解決了標(biāo)簽“餓死”問題，但是存在識(shí)別周期長、系統(tǒng)能耗大等缺點(diǎn)。為此，提出了一種基于映射序列碼的RFID標(biāo)簽防碰撞算法，將標(biāo)簽識(shí)別碼進(jìn)行分組，再根據(jù)唯一的映射關(guān)系確定存在的查詢前綴，消除了多叉樹的空閑時(shí)隙，減少了碰撞時(shí)隙，提高了系統(tǒng)的識(shí)別效率。同時(shí)，標(biāo)簽在響應(yīng)閱讀器時(shí)，只需要發(fā)送匹配前綴后的剩余部分，降低了系統(tǒng)能耗，尤其是在標(biāo)簽識(shí)別碼位數(shù)長，標(biāo)簽數(shù)量多時(shí)，算法性能達(dá)到最優(yōu)。但是，在閱讀器工作范圍內(nèi)，標(biāo)簽分布密度較小時(shí)，算法的識(shí)別效率出現(xiàn)不穩(wěn)定。在后續(xù)工作中，可以結(jié)合碰撞跟蹤技術(shù)[12-14]，進(jìn)一步提高算法的識(shí)別效率和總體性能。

[1] 寧煥生,徐群玉.全球物聯(lián)網(wǎng)發(fā)展及中國物聯(lián)網(wǎng)建設(shè)若干思考[J].電子學(xué)報(bào),2010,38(11):2590-2599.

[2]AliK,HassaneinH,TahaAEM.RFIDanti-collisionprotocolfordensepassivetagenvironments[C]//32ndIEEEconferenceonlocalcomputernetworks.[s.l.]:IEEE,2007:819-824.

[3] 朱 軍,張 元,盧小冬,等.基于分段搜索的多RFID標(biāo)簽抗沖突方法[J].計(jì)算機(jī)應(yīng)用研究,2011,28(3):1031-1033.

[4] 程文青,趙夢欣,徐 晶.改進(jìn)的RFID動(dòng)態(tài)幀時(shí)隙ALOHA算法[J].華中科技大學(xué)學(xué)報(bào):自然科學(xué)版,2007,35(6):14-16.

[5] 王 雪,錢志鴻,胡正超,等.基于二叉樹的RFID防碰撞算法的研究[J].通信學(xué)報(bào),2010,31(6):49-57.

[6]JiaX,FengQ,MaC.Anefficientanti-collisionprotocolforRFIDtagidentification[J].IEEECommunicationsLetters,2010,14(11):1014-1016.

[7] 蘇 健,文光俊,韓佳利.一種基于ISO18000-6B標(biāo)準(zhǔn)的RFID防碰撞算法[J].電子學(xué)報(bào),2014,42(12):2515-2519.

[8] 劉 淼.基于RFID的物聯(lián)網(wǎng)感知層查詢樹防碰撞算法研究[D].長春:吉林大學(xué),2013.

[9]LawC,LeeK,SiuKY.Efficientmemorylessprotocolfortagidentification[C]//Proceedingsofthe4thinternationalworkshopondiscretealgorithmsandmethodsformobilecomputingandcommunications.[s.l.]:ACM,2000:75-84.

[10] 張學(xué)軍,王緒海,蔡文琦.基于分組碼的改進(jìn)型防碰撞算法研究[J].計(jì)算機(jī)應(yīng)用研究,2012,29(11):4265-4268.

[11] 丁治國,郭 立,朱學(xué)永,等.基于二叉樹分解的自適應(yīng)防碰撞算法[J].電子與信息學(xué)報(bào),2009,31(6):1395-1399.

[12]LaiYC,HsiaoLY,ChenHJ,etal.AnovelquerytreeprotocolwithbittrackinginRFIDtagidentification[J].IEEETransactionsonMobileComputing,2013,12(10):2063-2075.

[13]WangG,PengY,ZhuZ.Anti-collisionalgorithmforRFIDtagidentificationusingfastquerytree[C]//InternationalsymposiumonITinmedicineandeducation.[s.l.]:IEEE,2011:396-399.

[14]ChenWC,HorngSJ,FanP.Anenhancedanti-collisionalgorithminRFIDbasedoncounterandstack[C]//2007secondinternationalconferenceonsystemsandnetworkscommunications.[s.l.]:IEEE,2007:21.

Multi-tree Anti-collision Algorithm Based on Mapping Sequence Code

HE Shen-yan,YANG Heng-xin,ZHANG Yun

(College of Electronic Science and Engineering,Nanjing University of Posts and Telecommunications,Nanjing 210003,China)

With the development of Internet of Things,Radio Frequency Identification (RFID) has been widely used.Tag collision problems seriously affect the efficiency of RFID identification systems.As a result,multi-tag anti-collision algorithm becomes a key point in investigation of RFID technology.A multi-tree anti-collision algorithm based on mapping sequence code has been presented.With the main idea of multi-tree,tag identifiers within the range of reader have been grouped.According to the unique mapping relationship,existing query prefixes has been determined;idle slots of multi-tree have been eliminated and collision slots of multi-tree have been reduced.At the same time,tags only need to send the rest parts matching with the query prefix when responding to the reader.Thus,the amount of information transmission and energy consumption has been reduced.The results of Matlab simulation show that the proposed algorithm has effectively reduced the total slots of tag identification and significantly improved system performance,and that efficiency of identification reaches about 71%,which means this algorithm can achieve optimal performance especially since the length of tag identifier is long and the number of tags is large.

RFID;tag anti-collision;multi-tree;mapping relationship

2016-06-21

2016-09-28 網(wǎng)絡(luò)出版時(shí)間：2017-03-13

國家自然科學(xué)基金青年科學(xué)基金項(xiàng)目(61302155)

何申炎(1992-)，女，碩士研究生，研究方向?yàn)橹悄苄畔⑻幚?；楊恒新，副教授，研究方向?yàn)闊o線射頻識(shí)別技術(shù)；張 昀，碩士生導(dǎo)師，研究方向?yàn)橥ㄐ判盘?hào)盲檢測、神經(jīng)網(wǎng)絡(luò)和無線傳感器網(wǎng)絡(luò)等。

http://kns.cnki.net/kcms/detail/61.1450.tp.20170313.1547.086.html

TP301.6

A

1673-629X(2017)05-0054-05

10.3969/j.issn.1673-629X.2017.05.012