改進型RFID自適應標簽識別算法

孫　宇，王玉皞，李　唯，鄧　晟

(南昌大學 信息工程學院，江西 南昌　330031)

?

改進型RFID自適應標簽識別算法

孫宇，王玉皞，李唯，鄧晟

(南昌大學 信息工程學院，江西 南昌330031)

基于碰撞識別算法系列，提出改進型自適應標簽識別算法(Improved Adaptive Collision Tree Algorithm，IACT)。算法通過優化查詢前綴，消除了自適應碰撞標簽識別算法在四叉樹搜索產生的空時隙查詢，從而減少了算法的時間復雜度，提高識別效率。通過理論推導和計算機仿真可知，該算法比自適應標簽識別算法(Adaptive Collision Tree Algorithm，ACT)有著明顯的優化。

RFID；標簽識別；防碰撞

1　射頻識別技術

射頻識別(Radio Frequency Identification，RFID)技術是一項利用射頻進行非接觸式雙向通信的自動識別技術[1-2]。它作為物聯網的核心技術，在國家行業發展中發揮著越來越重要的戰略作用，并影響社會的各領域，其發展顯現出高速化、規模化、泛在化等特點。當多個標簽(tags)在同一信道與閱讀器通信時，就會引發標簽碰撞，為實現多標簽識別，就必須解決多標簽信號碰撞沖突的問題。尤其在大規模的RFID標簽場景下[3]，RFID系統的標簽防碰撞能力直接決定RFID系統的識別效率。

目前，解決RFID系統中的標簽碰撞問題主要采用兩大類標簽防碰撞算法(anti-collision algorithm)[4]，一類是基于時隙隨機分配的Aloha算法[4-6](隨機性防碰撞協議)，主要包括純Aloha(PA)、時隙Aloha(SA)、幀時隙Aloha(FSA)、動態幀時隙Aloha(DFSA)等，適用于數量較少的標簽識別。另一類是基于樹形搜索的防碰撞算法(確定性防碰撞協議)，包括分裂樹(BTS)[7]、二進制搜索(BS)[8]、查詢樹算法(QT)[9]，以及各種改進算法和混合協議[10-11]。這類算法比較復雜，但是適用于RFID標簽較多的場景。文獻[12-14]就提出了一系列碰撞識別算法，這類算法可以利用標簽之間的比特位碰撞，消除了傳統樹形算法中閱讀器必須對接受序列進行逐比特識別的限制，尤其在標簽數量較多的情況，很好的減少了RFID系統的查詢時隙，由此也減少了系統通信復雜度。

文本在基于自適應標簽識別算法(Adaptive Collision Tree Algorithm，ACT)[14]算法的基礎上，提出了一種改進型標簽識別算法(IACT)，本文的算法對ACT算法中的四叉樹搜索進行了前綴優化，消除了ACT算法中四叉樹搜索產生的空時隙，同時也提高了算法識別效率。

2　碰撞識別算法以及相關改進

2.1曼徹斯特碼

RFID系統中，標簽ID為“0”和“1”的二進制。標簽編碼方式有多種，在二進制搜索算法(Binary Search，BS)中，采用的編碼方式是曼徹斯特碼。曼徹斯特碼[15]是利用相位進行編碼。其編碼方式為數據采集的時鐘信號(每個碼元時間的中間位置)處必有跳變，編碼值1為前半部分高電位，后半部分為低電位，即從高電平跳變到低電平(下降沿)，編碼值0為前半部分低電位，后半部分高電位，即從低電平跳變到高電平(上升沿)。這樣的好處是可以檢測到發生標簽ID碰撞時，其碰撞比特的精確位置和標示。本文提出的算法就是采用曼徹斯特碼，在發生碰撞時就能夠準確地知道標簽ID碰撞比特位。利用此特點，改善樹形算法。根據每個前綴下的匹配標簽比特位。可以快速更新前綴，有效減少查詢時隙和通信復雜度。

2.2CT算法以及改進型ICT算法

在文獻[12]，提出碰撞識別算法(Collision Protocol，CT)，其主要是基于查詢樹算法(QT)，在算法中采用了曼徹斯特編碼，標簽在每次的最高碰撞位進行分裂和疊加前綴。所以每一次查詢的查詢碼可能長度都不一定一樣，有效的減少了在RFID標簽識別過程中出現的空時隙。而ICT算法[13]是在CT算法基礎上，根據標簽ID編碼的“二元性”，即每個標簽ID編碼只能是“0”或者“1”，提出了單次查詢，兩次響應。通過兩個標示位“0”和“1”，進行不同子周期的響應，所以一次查詢就可以得到兩個標識位下面的不同標簽。

2.3自適應標簽識別算法

(1)

假設RFID系統中有X個待識別的標簽ID，系統分配的分叉樹是L，那么在深度為1的搜索深度下，標簽ID的識別概率是p(1)=(1-1/L)X-1，那么在搜索深度為m時，那么其識別概率為

p(m)=p(1)[1-p(1)]m-1

(2)

搜索深度均值就為

(3)

將式(2)帶入式(3)得到

(4)

因為1-p(1)必然是小于1的，最后根據等比數列算出搜索深度均值

(5)

已知時隙表達式為

(6)

式中：Tf表示系統識別均時隙。當分叉樹分別是2和4時，系統識別均時隙則為

(7)

(8)

最后將式(7)公式(8)進行比較。可以計算出，當X<3時，T2用時更少。當X≥3時，T4用時更少。通過和碰撞因子的轉換，可以知道η=1-(1/2)3-1=0.75是其臨界。每次檢測碰撞因子時，當碰撞因子η<0.75選擇二叉樹搜索，當η≥0.75，采用四叉樹。

3　改進型自適應標簽識別算法

ACT算法可以合理的在ICT算法基礎上進一步減少碰撞時隙，其通過碰撞因子和待識別標簽數量X之間的轉換，但是還存在一些誤差。因為，在標簽識別的過程中，雖然可以利用曼特斯特編碼知道碰撞位從而得到定義的碰撞因子，但是實際上當前節點的碰撞因子并不是每次都是能夠對應準確的待識別標簽ID數X。比如，碰撞比特是0011和1100這兩個。那么就可以知道其碰撞位為全4位碰撞。那么可見，碰撞因子為η=1滿足了之前的理論η≥0.75，應該采用四叉樹搜索，這樣在選擇四叉樹搜索下就會多產生兩個空時隙。

ACT算法在處理ICT多叉樹自適應問題的選擇上還有改進。為了減少自適應多叉ICT算法可能產生的查詢空時隙，可以通過對閱讀器的前綴進行優化，也就是本文提出的改進型自適應碰撞識別算法(Improved adaptive collision tree algorithm，IACT)。在二叉樹的情況下，不會產生多余空時隙。那么在碰撞因子η<7.5這個判決條件下，還是采用二叉樹ICT算法。而在碰撞因子η≥0.75時，采用四叉樹。但是在發送查詢之前，先要對當前節點碰撞位進行一個判斷處理。

就如上面的標簽，若碰撞的標簽ID是0011和1100。可知其碰撞比特位為XXXX，碰撞因子為4/4=1，采用四叉樹。本文將4個碰撞比特位分別從高位到低位標為X3，X2，X1，X0。閱讀器先發送一個最高兩位碰撞位即為11，其他比特位全為0的指令給標簽。標簽將接收到的指令與自己標簽ID相“與”，即“0”與“0”得0、“0”與“1”得0、“1”與“0”得0、“1”與“1”得1。那么得到ID碼為1100，0000。所以標簽ID的X3，X2位分別是11和00。為了讓閱讀器能夠識別出高兩位的實際標簽ID碼。將得出的高兩位11和00轉換10進制然后返回其對應10進制位置，即返回一個分別是X3和X0位置為1，其他位置為0的ID碼，閱讀器再次收到就可以根據碰撞位判斷出當前存在的高兩位ID碼。通過在發送查詢之前進行判斷處理就可以有效的檢測出當前標簽ID的高兩位，從而減少了發送無用查詢的空時隙情況。圖1是IACT算法的算法流程。

圖1　IACT算法流程

和查詢樹算法一樣，在初始時，前綴堆棧為空。開始時，閱讀器從前綴池里取出空前綴，發送問詢指令，等待標簽響應。所以本文的算法步驟如下：

1)閱讀器向前綴放入空串，將標簽ID置空。

2)閱讀器發送前綴，標簽響應。標簽根據自己標志位在不同響應子周期發送自己的標簽ID。

3)判斷前綴是否為空，為空則識別完成。否則繼續。在有兩個響應周期的閱讀器情況，回復標簽中的剩余ID的最高碰撞位作為標志位。前綴的更新為當前前綴+剩余碰撞ID位的標志位前沒有發生碰撞的比特。在響應周期為S1的周期，標簽發送標志位為“0”的標簽。在響應周期S2，標簽發送標志位為“1”的標簽。來響應閱讀器的請求。

4)判斷是否發生碰撞，計算碰撞因子η，若η<0.75，則采用二叉樹，發送前綴；若η≥0.75，則采用四叉樹，根據判斷處理得出高兩位前綴，發送前綴。

5)將發生碰撞的最高位前的比特與前綴合并，形成新的前綴，放入堆棧。

6)再次看前綴是否為空，直到前綴為空為止。識別完成。

下面為一個識別實例，假設有7個長度為4的ID標簽，分別是A：0001，B：0010，C：0011，D：0100，E：0101，F：1100，G：1110。使用本算法進行識別。識別過程如圖2所示。

圖2　IACT算法識別實例圖

通過圖2可知，本次識別7個標簽使用6次查詢。其中陰影表示識別標簽，虛線表示不需要發送查詢碼。

4　IACT算法分析

(9)

當搜索深度大于m時，采用二叉樹。因為采用子周期的結構，在搜索的過程中二叉樹的查詢次數需要去掉子周期的次數。那么可得采用二叉樹搜索的識別時隙

(10)

式中：T子的個數根據標簽碰撞的情況在0到X/2之間。本文改進了完全四叉樹的查詢，優化查詢前綴，所以這部分的時間復雜度需要加上閱讀器在檢測到碰撞二次發送查詢的時隙和減去空閑的時隙。二次查詢的時隙正好與碰撞時隙相等。假設，在四叉樹的m搜索層，X待識別標簽。那么就有4m個節點，在m層n個標簽響應同一節點的概率服從二項分布

(11)

那么，空時隙即為0個標簽響應，識別時隙即為1個標簽響應，碰撞時隙即為多個標簽響應。概率表達式分別如下

(12)

(13)

P(1/X,m)

(14)

式中：n>1，p=1/4m表示為在4m節點里選擇一個節點的概率，那么可知

P(0/X,m)=(1-1/4m)X

(15)

P(1/X,m)=X·4-m(1-1/4m)X-1

(16)

P(n/X,m)=1-(1-1/4m)X-X·4-m(1-1/4m)X-1

(17)

設αmi/X和δmi/X分別表示在m層第i節點被搜索的概率和在m層第i節點發生碰撞的概率，節點在同一層的搜索和碰撞的概率相同，可知δmi/X=P(k/X,m)，當父節點發生碰撞時，下一節點才能被訪問到，所以當深度大于1時，αmi/X=δ(m-1)i/X。平均查詢總時隙為

(18)

最后得到

(19)

把δmi/X=P(k/X,m)代入得到

X·4-m(1-1/4m)X-1]

(20)

碰撞時隙為

(21)

空閑時隙為總時隙減去碰撞時隙和識別時隙得到

(22)

根據文獻[16]可得大概關系為

(23)

那么，IACT算法的總時隙是

(24)

所以吞吐率為

(25)

根據文獻[13]中對于ICT算法通信復雜度的計算，可以推導IACT算法的通信復雜度為只是在二次查詢時增加一次查詢碼，但是減少了空閑時隙的查詢碼。所以算法的通信復雜度為

(26)

式中：Creader(X)表示為閱讀器通信復雜度；Ctags(X)表示為標簽通信復雜度；lq,i是在i周期發送查詢前綴長；lr,i是在i識別周期發送響應的長度。標簽ID長度lID=lq,i+lr,i，所以得到

(27)

5　IACT仿真以及性能分析

通過以上分析，本文主要仿真RFID標簽識別最重要的兩個性能對比：查詢總時隙和算法吞吐率。將IACT算法與CT，ICT，ACT算法比較。仿真場景設置為標簽ID長度96，標簽數量從0～10 000個，假設所有標簽空間分布均勻，沒有丟失標簽ID。通過仿真如圖3所示。

圖3　IACT算法與QT，CT，ICT，ACT算法的查詢次數仿真對比圖

從仿真結果看得出，IACT優化了ACT在四叉樹時的前綴搜索。極大的減少了空時隙，進而極大的減少了總查詢次數，減少了系統的識別時間復雜度。

圖4　IACT算法與QT，CT，ICT，ACT算法的吞吐率仿真對比圖

由圖4可以看出，新的改進算法吞吐率有了很大的提高。然而，采用了四叉樹的算法在幾個節點上會出現一些跳變，這是因為與算法的搜索深度有關，深度m=?log4(X/3)」表示向下取整，不是一個連續的整數會導致標簽數量在到達一定數量會出現搜索深度的跳變，所以算法查詢次數和吞吐率都會出現一個階段的上升然后有一個跳變。從圖中可以看出QT算法一直維持在0.4左右的吞吐率，CT和ICT分別維持在0.5和1.0的吞吐率左右。ACT的吞吐率也是高于ICT的。由于總查詢時隙的極大的減少，IACT吞吐率也是極大的提高，高于其他算法。

6　結論

本文提出一種新的改進型碰撞識別算法，在自適應碰撞識別算法上有效去除在選擇四叉樹搜索時產生的空時隙。有效減少系統總查詢時隙。在識別性能上也是極大地優化了ACT算法，通過理論和仿真驗證了提出的IACT算法優于ACT，進一步提升了算法的適用性。表明IACT算法可以應用于標簽識別，能高效地解決標簽碰撞問題。

[1]FINKENZELLER K. RFID-handbook fundamengtals and applications in contact less smart cards and identification [M]. 2nd ed. New York：Wiley and Sons，2003.

[2]WANT R. An introduction to RFID technology[J]. Pervasive computing，2006(1)：25-33.

[3]SHAO C，KIM T，YU J，et al. ProTaR： probabilistic tag retardation for missing tag identification in large-scale RFID systems[J]. IEEE transactions on industrial informatics，2015，11(2)：513-522.

[4]KLAIR D K，CHIN K W，RAAD R. A survey and tutorial of RFID anti-collision protocols[J]. Communications surveys & tutorials，2010，12(3)：400-421.

[5]SU W，ALCHAZIDIS N V，HA T T. Multiple RFID tags access algorithm[J]. IEEE transactions on mobile computing，2010，9(2)：174-187.

[6]KAITOVIC J，IMKO M， LANGWIESER R，et al. Channel estimation in tag collision scenarios[C]// 2012 IEEE International Conference on RFID. Orlando，FL：IEEE，2012： 74-80.

[7]HUSH D R，WOOD C. Analysis of tree algorithms for RFID arbitration[C]//IEEE International Symposium on Information Theory. Cambridge， MA：IEEE，1998：107-110.

[8]YU S， ZHAN Y， WANG Z，et al. Anti-collision algorithm based on jumping and dynamic searching and its analysis[J]. Computer engineering，2005，31(9)：19-20.

[9]LAW C，LEE K，SIU K Y. Efficient memoryless protocol for tag identification[C]//Proc. 4th International Workshop on Discrete Algorithms And Methods For Mobile Computing And Communications. New York：ACM，2000：75-84.

[10]BONUCCELLI M A，LONETTI F，MARTELLI F. Tree slotted ALOHA： a new protocol for tag identification in RFID networks[C]//Proc. 2006 International Symposium on World of Wireless，Mobile and Multimedia Networks. Buffalo-Niagara Falls，NY：IEEE，2006：603-608.

[11]RYU J，LEE H，SEOK Y，et al. A hybrid query tree protocol for tag collision arbitration in RFID systems[C]//IEEE International Conference on Communications，2007. Glasgow：IEEE，2007：5981-5986.

[12]JIA X，FENG Q，MA C. An efficient anti-collision protocol for RFID tag identification[J]. Communications letters，2010，14(11)：1014-1016.

[13]JIA X L，FENG Q Y. An improved anti-collision protocol for radio frequency identification tag[J]. International journal of communication systems，2015，28(3)：401-413.

[14]LIU X，QIAN Z，ZHAO Y，et al. An adaptive tag anti-collision protocol in RFID wireless systems[J]. Wireless communication over zigbee for automotive inclination measurement china communications，2014，11(7)：117-127.

[15]FORSTER R. Manchester encoding：opposing definitions resolved[J]. Engineering science & education journal，2000，9(6)：278-280.

[16]張學軍，蔡文琦，王鎖萍.改進型白適應多叉樹防碰撞算法研究[J]. 電子學報，2012，40(1)：193-198.

孫宇(1989— )，碩士生，主研通信系統、RFID防碰撞協議；

王玉皞(1977— )，博士生導師，主要研究方向為無線協作、通信系統、雷達通信一體化、RFID等；

李唯(1991— )，女，碩士生，主研RFID防碰撞協議；

鄧晟(1991— )，碩士生，主研電波傳播、信道參數估計、無源雷達。

責任編輯：時雯

8月24—27日，第二十五屆北京國際廣播電影電視展覽會(BIRTV2016)在北京中國國際展覽中心舉行。展會以“融合媒體 智慧廣電”為主題，匯聚了中外500多家參展商，展覽面積超過5萬平方米。展會同期舉辦了專業論壇超10場，全面展示了廣電領域最新的技術和設備、傳統主流媒體創新業務及融合發展成果，并展望了廣電領域未來的發展方向。

Improved adaptive tag-reading algorithm in RFID system

SUN Yu，WANG Yuhao，LI Wei，DENG Sheng

(CollegeofInformationEngineering，NanchangUniversity，Nanchang330031，China)

A novel improved adaptive collision tree algorithm (IACT) is proposed for RFID tags-reading based on adaptive collision tree algorithm. The improved algorithm reduces idle time slots which occurs in adaptive collision tree algorithm (ACT) by optimizing the prefix-query. So， the proposed algorithm reduces the time complexity and improves the efficiency of recognition in RFID system. By mathematical analysis and simulation， it proves that the improved adaptive collision tree algorithm (IACT) has a better performance than adaptive collision tree algorithm (ACT) for RFID tags-reading.

RFID； tag-reading； anti-collision

TP39

A

10.16280/j.videoe.2016.09.028

2016-01-05

文獻引用格式：孫宇，王玉皞，李唯，等.改進型RFID自適應標簽識別算法 [J].電視技術，2016，40(9)：137-142.

SUN Y，WANG Y H，LI W，et al.Improved adaptive tag-reading algorithm in RFID system[J].Video engineering，2016,40(9)：137-142.