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

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

?

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

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

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

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

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

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

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

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

1　新型防碰撞算法

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

1.1算法原理

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

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

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

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

1.2算法模型與實現流程

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

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

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

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

然后得到識別范圍內未識別的標簽數與分組數之間的關系[5，12]

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

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

根據Friis[1，13]公式，能得到閱讀器發射功率與識別距離的關系

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

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

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

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

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

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

閱讀器統計接收到NUM值，得到數據如表3所示.

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

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

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

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

具體識別過程為：

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

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

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

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

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

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

（7）調整閱讀器發射功率級Pi進行下一組標簽的識別，重復步驟（2）—步驟（6），直到整個識別區域的標簽數全部被識別.

2　仿真結果

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

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

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

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

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

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

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

3　結論

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

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

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

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

參考文獻：

[1]周曉光，王曉華.射頻識別（RFID）技術原理與應用實例[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]余松森，詹宜巨，彭衛東.基于后退式索引的二進制樹形搜索反碰撞算法及其實現[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動態幀時隙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]吳春華，陳軍.動態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]王驍，郭網媚，肖鶴玲，等.基于哈希函數的高效完善安全網絡編碼算法[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]尹君，何怡剛，李兵.基于分組動態幀時隙的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算法的幀長及分組數改進研究[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]李建成.射頻識別系統空中接口通信協議關鍵技術研究與實現[D].長沙：國防科學技術大學，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系統多標簽識別防碰撞算法[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—），男，副教授，碩士生導師，主要研究方向為射頻識別技術、微波技術與天線、電磁場的數值計算. E-mail：lijianxiong@tjpu.edu.cn

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

收稿日期：2015-07-17

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

中圖分類號：TP311

文獻標志碼：A

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