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

何申炎，楊恒新，張 昀

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

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

何申炎，楊恒新，張 昀

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

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

射頻識別；標簽防碰撞；多叉樹；映射關系

0 引 言

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

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

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

基于ALOHA的防碰撞算法需要一個時鐘電路來解決同步問題，且存在一個致命缺點：由于標簽長時間無法被閱讀器識別而導致標簽“餓死”?；跇涞姆琅鲎菜惴ú恍枰?，并且解決了標簽“餓死”問題，但仍存在識別周期長、標簽能耗大等問題。

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

1 查詢樹算法

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

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

表1 查詢樹算法識別過程

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

2 基于多叉樹的改進型防碰撞算法

2.1 算法描述

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

該算法包含分組操作和映射識別操作兩個部分。

(1)分組操作。

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

(2)映射識別操作。

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

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

表2 映射關系表(1)

表3 映射關系表(2)

2.2 算法流程

(1)初始化查詢前綴堆棧Q，閱讀器發(fā)送Request(NULL)通信請求命令，使工作范圍內的所有標簽進行響應。

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

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

(4)判斷堆棧Q是否為空，若不為空，則轉回步驟3，若為空，則識別結束。

算法流程如圖1所示。

圖1 算法流程圖

2.3 算法識別過程舉例

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

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

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

表4 算法查詢過程

3 仿真分析

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

由文獻[6]可知，CT算法識別n個標簽所用的總時隙為：

T(n)=2n-1

(1)

算法識別效率為：

(2)

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

(3)

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

(4)

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

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

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

圖2 五種算法總時隙性能比較

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

圖3 五種算法識別效率比較

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

4 結束語

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

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

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

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

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

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

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

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

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

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

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

[11] 丁治國,郭 立,朱學永,等.基于二叉樹分解的自適應防碰撞算法[J].電子與信息學報,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 網絡出版時間：2017-03-13

國家自然科學基金青年科學基金項目(61302155)

何申炎(1992-)，女，碩士研究生，研究方向為智能信息處理；楊恒新，副教授，研究方向為無線射頻識別技術；張 昀，碩士生導師，研究方向為通信信號盲檢測、神經網絡和無線傳感器網絡等。

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