高效的功率可控防碰撞算法

李建雄，邢炳雷，閆必行，劉鵬雪，賈紅玉（天津工業(yè)大學電子與信息工程學院，天津　300387）

?

高效的功率可控防碰撞算法

李建雄，邢炳雷，閆必行，劉鵬雪，賈紅玉
（天津工業(yè)大學電子與信息工程學院，天津300387）

摘要：多標簽防碰撞技術(shù)是射頻識別系統(tǒng)中的關(guān)鍵技術(shù)，針對現(xiàn)有的ALOHA防碰撞算法消耗大量的時隙和能量，提出了一種高效的功率可控防碰撞算法.首先，本算法通過對標簽UUID進行哈希編碼將標簽映射到相應的幀時隙，提高了時隙利用率.然后，利用碰撞檢測機制，每次只允許無碰撞的標簽與閱讀器進行通信，從而大大減少了無效通信的過程.最后，采用功率控制機制將標簽按區(qū)域進行識別，明顯地減少了標簽碰撞并且節(jié)約了通信耗能.通過仿真結(jié)果分析可以看出：該算法的性能比已有的防碰撞算法有明顯提高，基本滿足了RFID系統(tǒng)對標簽防防碰撞算法的要求，提高了系統(tǒng)的穩(wěn)定性.

關(guān)鍵詞：射頻識別；防碰撞算法；ALOHA；哈希編碼；碰撞檢測；功率可控

射頻識別（radio frequency identification，RFID），是一種近年來逐漸成熟的利用無線傳輸?shù)淖R別技術(shù)，其通過無線電波自動識別標簽數(shù)據(jù).與傳統(tǒng)識別技術(shù)相比，無需直接接觸即可完成通信過程，具有識別距離遠、操作簡單等優(yōu)點[1].射頻識別系統(tǒng)表現(xiàn)出良好的發(fā)展趨勢，并在醫(yī)療、自動化、交通運輸管理、定位、產(chǎn)品證件防偽、門禁等眾多領(lǐng)域得到了廣泛的應用.

閱讀器通過天線發(fā)送電磁波，電子標簽接收到足夠的能量后將被激活，將自身信息返回各閱讀器，再轉(zhuǎn)達服務(wù)器進行處理.當識別區(qū)域內(nèi)的多個標簽在同一時刻和閱讀器通信時，閱讀器將不能正確識別標簽，從而降低了通信成功率，因此合理的標簽防碰撞算法是RFID研究的重要內(nèi)容.性能優(yōu)越的防碰撞算法可以提高射頻識別系統(tǒng)的穩(wěn)定性，更利于其推廣.

目前，在國內(nèi)外RFID系統(tǒng)中使用的防碰撞算法以時分多址最為常見.基于時分多址的標簽防碰撞算法主要有兩種：一種是隨機防碰撞算法[2]，如ALOHA系列算法，其要求標簽在通信時隨機選擇發(fā)送時隙；另一種是確定防碰撞算法[3]，如二叉樹系列防碰撞算法，其策略為按照樹形結(jié)構(gòu)逐步查找所需要的標簽.采用標簽防碰撞算法可以避免多標簽同時和閱讀器進行通信，從而保證了整個系統(tǒng)的成功率. ALOHA算法在選擇時隙時的隨機性，可能會導致個別標簽始終無法被成功識別，被稱為標簽“餓死”現(xiàn)象，而基于二叉樹的確定性防碰撞算法雖然可以保證識別成功率，但也存在著算法復雜、識別周期長等問題.

本文根據(jù)已存在的ALOHA防碰撞算法[4-8]，提出一種高效的功率可控防碰撞算法.該算法通過對標簽UUID進行哈希編碼[9]將標簽映射到相應的幀時隙，然后利用碰撞檢測機制，每次只允許無碰撞的標簽與閱讀器進行通信，從而大大避免了閱讀器與標簽間的無效通信過程，提高了時隙利用率，同時采用功率可控機制將標簽按識別區(qū)域進行識別，明顯地減少了標簽碰撞并且減少了通信耗能.

1　新型防碰撞算法

本算法是在分組動態(tài)幀時隙防碰撞算法[5，7]的基礎(chǔ)上提出的，針對多標簽識別時產(chǎn)生的大量碰撞的一種改進算法.該算法很好地提升了時隙利用率，減少了閱讀器多次查詢造成的時隙浪費，不但減少了識別總時間，而且使閱讀器在節(jié)能方面表現(xiàn)出良好的性能.

1.1算法原理

假設(shè)標簽均勻分布在識別區(qū)域內(nèi)，本文算法首先需要閱讀器對標簽進行統(tǒng)計，通過控制閱讀器發(fā)射功率實現(xiàn)對識別區(qū)域的劃分，從而實現(xiàn)了將標簽按距閱讀器的距離分組.功率可控算法的原理如圖1所示.

圖1　功率可控原理示意圖Fig.1 Schematic of power-control

假設(shè)將整個識別區(qū)域劃分為4個子區(qū)域，T0代表在有效識別范圍d0內(nèi)的標簽群，T1代表在識別范圍d1但不包括d0內(nèi)T0的標簽群，T2、T3代表同樣意義的標簽群.當在識別范圍內(nèi)有大量標簽存在時，減少發(fā)射功率，也就減少了參與識別的標簽，從而也就減少了標簽的通信碰撞概率.以圖1所示為例，閱讀器先發(fā)射較小的功率，使有效識別區(qū)域為d0，僅與d0區(qū)域的標簽群T0進行通信；在與T0標簽群通信結(jié)束后，再增加發(fā)射功率至有效識別區(qū)域為d1（包含d0），屏蔽掉T0標簽群而只與T1標簽群通信；在與T1標簽群通信結(jié)束后，再增加發(fā)射功率至有效識別區(qū)域為d2（包括d1），屏蔽掉T0和T1標簽群而只與T2標簽通信；最后，增加發(fā)射功率到最大，也就是最大有效識別區(qū)域d3，屏蔽掉T0、T1和T2標簽群而只與剩下的標簽群進行通信.

在每組標簽的識別過程中，閱讀器首先對標簽發(fā)送一個帶有初始幀長L的查詢命令，激活范圍內(nèi)的標簽收到來自閱讀器的查詢命令后進行簡單的求余運算，用自身的UUID號對幀長L求余，并存儲在標簽的時隙標志位中.然后標簽將時隙標志位信息返回給閱讀器，閱讀器統(tǒng)計每個時隙中標簽的個數(shù).閱讀器生成一個L位的碰撞檢測序列，當時隙i為單標簽占用時，碰撞檢測序列的第i位設(shè)置為1，空閑或多標簽占用時設(shè)置為0，閱讀器將此碰撞檢測序列發(fā)送給激活的標簽.標簽接收到來自閱讀器的碰撞檢測序列后，通過查詢只允許碰撞檢測序列對應位值為1的標簽響應閱讀器的查詢.然后閱讀器采用變幀長ALOHA算法進行標簽識別直到本組標簽全部通信完成，被識別的標簽將被設(shè)置為靜默態(tài)不再參與后續(xù)的識別過程.

1.2算法模型與實現(xiàn)流程

假設(shè)n為識別區(qū)域內(nèi)未識別的標簽數(shù)目，L表示時隙幀長，且每個幀時隙被標簽選中的概率是相等的.根據(jù)概率論原理[4，10-11]，標簽選擇任意時隙的概率為1/L，則有r個標簽選擇同一時隙的概率為：

式中：Pidle表示一個時隙沒被標簽占用的概率；Psucc表示一個時隙只有一個標簽的概率；Pcoll表示一個時隙被多個標簽同時占用而產(chǎn)生標簽碰撞的概率.

對上式（1）求導可得最高的系統(tǒng)效率[5，10]，此時

由公式（4）可以得出，當標簽數(shù)與幀長幾乎相等的時候系統(tǒng)識別率最高，因此盡量將幀長設(shè)置為與未識別標簽數(shù)相等，但是幀長不能隨著標簽數(shù)的增長一直變大.當標簽數(shù)很大時，將標簽分成m組和m+1組（m≥1），這時分組的臨界標簽個數(shù)為[5，12]

然后得到識別范圍內(nèi)未識別的標簽數(shù)與分組數(shù)之間的關(guān)系[5，12]

例如當m = 1時，得到不分組和分成2組的標簽臨界值為n = 354；通過式（1）—式（8），得到表1的分組規(guī)則.

表1　未識別標簽數(shù)與幀長大小和分組數(shù)的關(guān)系Tab.1 Relationship between unrecognized tags，framelength and groups

根據(jù)Friis[1，13]公式，能得到閱讀器發(fā)射功率與識別距離的關(guān)系

式中：d為識別半徑；λ為電磁波波長；Preader為閱讀器發(fā)射功率；Greader= 8 dBi和Gtag= 1.2 dB分別為閱讀器天線增益和標簽天線增益；Preader和Greader均為等效全向輻射功率（EIRP），其在北美地區(qū)限制在4 W內(nèi)；p為閱讀器天線和標簽天線的極化匹配因子（極化完全匹配時，p = 1），ptr= -15 dBm表示無源標簽的最小工作門限；τ為標簽天線和標簽芯片的功率傳輸因子（共軛阻抗匹配時，τ= 1）.

假設(shè)閱讀器的最大識別半徑為dmax= 10 m，并且標簽均勻分布在識別區(qū)域內(nèi)，即標簽密度為ρ= n/πd2max，通過結(jié)合表1中的數(shù)據(jù)能夠到圖1中具體的di值

式中：m表示分組的臨界值，根據(jù)公式（11），能得到di值對應的閱讀器的發(fā)射功率Pi值

在每組標簽的識別過程中，閱讀器采用哈希映射碰撞檢測機制，標簽收到查詢命令后將自身唯一識別碼（UUID）對幀長L求余并存儲在時隙標志位中，即此標簽在幀時隙中對應的時隙號

式中：NUM為時隙標志位值，將NUM返回給閱讀器.閱讀器接收并統(tǒng)計來自標簽發(fā)來的NUM值，以11個標簽（標簽UUID為1～1 000內(nèi)的值），幀長L以8為例，如表2所示.表2中Y表示此時隙有標簽占用，N表示此時隙沒有標簽占用.

表2　幀時隙響應情況Tab.2 Response of time slots

閱讀器統(tǒng)計接收到NUM值，得到數(shù)據(jù)如表3所示.

表3　幀時隙的占用情況Tab.3 Use of time slots

閱讀器端建立了一個碰撞檢測序列[14]，將只有單標簽占用的時隙設(shè)置為1，無標簽或者多標簽占用的時隙設(shè)置為0，則有表4所示碰撞檢測序列.

表4　生成的碰撞檢測序列Tab.4 Generated collision detection sequence

閱讀器將生成的碰撞檢測序列發(fā)送給標簽，標簽通過查詢自己的時隙標志位值對應的碰撞檢測序列值是否為1，如果標簽的NUM值為1，則閱讀器將對該標簽進行無碰撞識別，否則，不對該標簽進行識別.

具體識別過程為：

（1）閱讀器發(fā)射全功率對標簽進行掃描，利用切比雪夫不等式[15]統(tǒng)計出識別范圍內(nèi)的待識別標簽數(shù)，依據(jù)表1的規(guī)則確定閱讀器的功率級Pi（置初始值i = 0）.

（2）閱讀器使用功率級Pi激活di內(nèi)的Ti標簽群，并發(fā)送初始幀長L.

（3）Ti標簽群將自身UUID與接收到的幀長L進行哈希處理得到自身的時隙標志位NUM值，并返回NUM值給閱讀器.

（4）閱讀器接收標簽的NUM值信息，統(tǒng)計整個幀長的時隙占用情況，然后將生成碰撞檢測序列返回給標簽.

（5）標簽接收到碰撞檢測序列后與自身時隙標志位進行對比，如果時隙標志位對應的碰撞檢測序列中的位值為1，則參與此次無碰撞識別過程；若為0，則不參與此次識別過程.

（6）每輪識別過程結(jié)束，識別完成的標簽被設(shè)為靜默態(tài)，閱讀器利用切比雪夫不等式估計未識別標簽數(shù).若未識別標簽數(shù)不為0，調(diào)整幀長L重復步驟（3）—步驟（6）；若未識別標簽數(shù)為0，進入（7）.

（7）調(diào)整閱讀器發(fā)射功率級Pi進行下一組標簽的識別，重復步驟（2）—步驟（6），直到整個識別區(qū)域的標簽數(shù)全部被識別.

2　仿真結(jié)果

本節(jié)將本文提出的算法與BFSA、DFSA、EDFSA進行詳細的比較.通過對比不同標簽個數(shù)時閱讀器成功識別所有標簽所需的總時隙數(shù)，消耗時間和消耗的能量來比較算法的性能.為了保證仿真的效果，假設(shè)為理想實驗環(huán)境：在半徑為10 m的圓形內(nèi)均勻地分布著1 000個標簽，并且每個標簽都能被正確讀取.為了保證實驗精度，取100次仿真結(jié)果的平均值.

比較BFSA、DFSA、EDFSA和本文提出的算法所需的時隙數(shù)如圖2所示.從圖2可以看出，BFSA算法所需的時隙數(shù)成指數(shù)增長.當標簽數(shù)為450以內(nèi)時，DFSA和EDFSA需要的時隙數(shù)差不多，但隨著標簽的增加，EDFSA的優(yōu)勢越來越明顯.從仿真結(jié)果可以看出，本文提出的算法與已有的幾種ALOHA算法相比具有明顯的優(yōu)勢.當標簽數(shù)為1 000時，本文提出的算法比BFSA、DFSA和EDFSA所用的時隙數(shù)分別減少了76.79%、75.93%和55.17%.由于本文提出的算法采用了功率可控機制，減少了同時參與通信的標簽；同時哈希編碼和碰撞檢測機制，有效地減少了無效時隙的參與，仿真結(jié)果與理論預期相符.

圖2　所需時隙數(shù)的比較Fig.2 Comparison of required number of time slots

識別標簽所消耗的時間[2，6]是衡量防碰撞算法性能的另一個重要指標. EDFSA算法因為采用了分組機制，當標簽數(shù)大于500時，在節(jié)省時間上會表現(xiàn)出明顯的優(yōu)勢.縱觀整個識別過程，本文提出的算法雖然在碰撞檢測階段增加了一次訪問標簽的時間，但其極大地減少了標簽通信失敗和無效時隙參與造成的時間損耗，消耗時間情況如圖3所示.由圖3可以看出，當標簽數(shù)為1 000時，本文提出的算法比BFSA、DFSA 和EDFSA所消耗的時間分別減少了78.57%、76.92% 和62.5%，證實本文提出的算法在識別效率上表現(xiàn)出良好的性能.

圖3　消耗時間的比較Fig.3 Comparison of time consumption

基于本文提出的功率可控機制，識別標簽消耗的能量也成為考察算法性能的重要指標.已存在的防碰撞算法均采用最大功率完成識別過程，當大部分標簽距離閱讀器較近時會造成能量的浪費.功率可控機制使閱讀器每次都用盡可能小的功率來識別標簽，而不是一直使用最大功率完成識別過程，消耗能量情況如圖4所示.從圖4中明顯看出，本文提出的算法可以節(jié)約大量的能量，當標簽數(shù)為1 000時，本文提出算法所需的耗能僅為BFSA、DFSA和EDFSA算法的13.33%、15.38%和22.2%，非常符合國家提出的節(jié)能減排規(guī)劃.

圖4　消耗能量的比較Fig.4 Comparison of energy consumption

3　結(jié)論

（1）利用哈希映射時隙機制替代了原來的標簽隨機選擇時隙方法，降低了標簽碰撞的概率.

（2）引入碰撞檢測機制，這樣不但避免碰撞的標簽參與識別過程，而且避免了空閑時隙和碰撞時隙造成的額外開銷.

（3）采用功率可控機制，一方面將同時參與識別的標簽數(shù)減少了，另一方面減少了識別所消耗的能量.

（4）將本文提出的算法與BFSA、DFSA和EDFSA進行詳細比較，結(jié)果表明：本文提出的防碰撞算法在識別過程中消耗的總時隙數(shù)、消耗的時間和耗能方面均有良好的表現(xiàn)，提高了RFID系統(tǒng)的穩(wěn)定性.

參考文獻：

[1]周曉光，王曉華.射頻識別（RFID）技術(shù)原理與應用實例[M].北京：人民郵電出版社，2006. ZHOU X G，WANG X H. The Principle and Application of Radio Frequency Identification（RFID）Technology[M].Beijing：The People′s Posts and Telecommunications Press，2006（in Chinese）.

[2] VOGT H. Multiple object identification with passive RFID tags [C]//2002 IEEE International Conference on Systems. [s.l.]：Man & Cybernetics，2002：98-113.

[3]余松森，詹宜巨，彭衛(wèi)東.基于后退式索引的二進制樹形搜索反碰撞算法及其實現(xiàn)[J].計算機工程與應用，2004，40 （16）：26-28. YU S S，ZHAN Y J，PENG W D. An anti-collision algorithm based on binary -tree searching of regressive index and its practice [J]. Computer Engineering and Applications，2004，40 （16）：26-28（in Chinese）.

[4]程文青，趙夢欣，徐晶.改進的RFID動態(tài)幀時隙ALOHA算法[J].華中科技大學學報：自然科學版，2006，35（6）：14-16. CHENG W Q，ZHAO M X，XU J. Enhanced dynamic frame slotted ALOHA algorithm for anti-collision in RFID systems [J]. Journal of Huazhong University of Science and Technology：Nature Science Edition，2006，35（6）：14-16（in Chinese）.

[5] WANG H，XIAO S L，LIN F Y. Group improved enhanced dynamic frame slotted ALOHA anti-collision algorithm [J]. The Journal of Supercomputing，2014，69（3）：1235-1253.

[6] DENG D J，TSAO H W. Optimal dynamic framed slotted ALOHA based anti-collision algorithm for RFID systems [J]. Wireless Personal Communications，2011，59（1）：109-122.

[7] LEE S R，LEE C W. An enhanced dynamic framed slotted ALOHA algorithm for RFID tag identification[C]//Emerging Directions in Embedded and Ubiquitous Computing Lecture Notes in Computer Science. [s.l.]：[s.n.]，2006：403-412.

[8]吳春華，陳軍.動態(tài)ALOHA法在解決RFID反碰撞問題中的應用[J].電子器件，2003，26（2）：173-176. WU C H，CHEN J. Application of dynamic ALOHA in RFID′s collision [J]. Journal of Electron Devices. 2003，26（2）：173-176（in Chinese）.

[9]王驍，郭網(wǎng)媚，肖鶴玲，等.基于哈希函數(shù)的高效完善安全網(wǎng)絡(luò)編碼算法[J].華中科技大學學報：自然科學版，2013，41（5）：102-104. WANG X，GUO W M，XIAO H L，et al. Efficient perfect secure network coding algorithm using Hash function [J]. Journal of Huazhong University of Science and Technology：Nature Science Edition，2013，41（5）：102-104（in Chinese）.

[10]尹君，何怡剛，李兵.基于分組動態(tài)幀時隙的RFID防碰撞算法[J].計算機工程，2009，35（20）：267-269. YIN J，HE Y G，LI B. RFID anti-collision algorithm based on groupingdynamicframeslotted[J].ComputerEngineering，2009，35（20）：267-269（in Chinese）.

[11] YANG Q，LI J C，WANG H Y. A dynamic framed slotted ALOHA anti -collision algorithm based on tag -grouping for RFID systems [C]//2012 IEEE 11th International Conference. Xi′an：[s.n.]，2012：1-3.

[12]徐圓圓，曾雋芳，劉禹.基于ALOHA算法的幀長及分組數(shù)改進研究[J].計算機應用，2008，28（3）：588-590. XU Y Y，ZENG J F，LIU Y. Research of optimizing frame size and group division in aloha-based algorithms [J]. Computer Applications，2008，28（3）：588-590（in Chinese）.

[13] KIM I，XU S，RAHMAT-SAMII Y. Generalised correction to the friis formula：Quick determination of the coupling in the Fresnel region [J]. IET Microw，Antennas Propage，2013，13 （7）：1092-1101.

[14]李建成.射頻識別系統(tǒng)空中接口通信協(xié)議關(guān)鍵技術(shù)研究與實現(xiàn)[D].長沙：國防科學技術(shù)大學，2011. LI J C. Research and implementation technologies of communication protocol for RFID air interface [D]. Changsha：Graduate School of National University of Defense Technology，2011（in Chinese）.

[15]王萌，陳殿仁. RFID系統(tǒng)多標簽識別防碰撞算法[J].太赫茲科學與電子信息學報，2013，11（4）：601-605. WANG M，CHEN D R. Anti-collision multi-tag identification algorithms for RFID systems[J]. Journal of Terahertz Science and Electronic Information Technology，2013，11（4）：601-605 （in Chinese）.

Efficient anti-collision algorithm based on power-control

LI Jian-xiong，XING Bing-lei，YAN Bi-xing，LIU Peng-xue，JIA Hong-yu
（School of Electronics and Information Engineering，Tianjin Polytechnic University，Tianjin 300387，China）

Abstract：The technology of multi-tag anti-collision is the key in radio frequency identification（RFID）system，in view of the existing problem that ALOHA anti-collision algorithms consume a lot of time solts and energy，an efficient anti-collision algorithm based on power-control is proposed. First，the UUID of tags will be done hash coding and the tags will be mapped to the corresponding slots in this algorithm to improve the utilization rate of slots. Then，collision detection mechanism allows only non-collision tags to communicate with the reader，thereby greatly reduces the ineffective communication process. Finally，the power-control mechanism to identify the tags by region significantly reduces the tag collision and saves the energy consumption of communication. It is found from the analysis of simulation results that the performance of the algorithm has been improved significantly compared with the existing anti-collision algorithms. It can satisfy the RFID system requirement of anti-collision algorithm，which improves the stability of system.

Key words：radio frequency identification（RFID）；anti-collision；ALOHA；Hash code；collision detection；power-control

通信作者：李建雄（1969—），男，副教授，碩士生導師，主要研究方向為射頻識別技術(shù)、微波技術(shù)與天線、電磁場的數(shù)值計算. E-mail：lijianxiong@tjpu.edu.cn

基金項目：國家自然科學基金資助項目（61372011）；天津市應用基礎(chǔ)與前沿技術(shù)研究計劃項目（15JCYBJC16300）

收稿日期：2015-07-17

DOI：10.3969/j.issn.1671-024x.2016.02.014

中圖分類號：TP311

文獻標志碼：A

文章編號：1671－024X（2016）02－0072－05