基于能量和距離分簇的主動式RFID防碰撞算法

劉雄飛，周小軍，肖振國

（中南大學 物理與電子學院，湖南 長沙410083）

0 引 言

射頻識別技術 （radio frequency identification，RFID），通過射頻信號自動識別目標對象，可快速地進行物品追蹤和數據交換［1］，根據電子標簽數據調制方式可分為主動式和被動式。目前，對主動式RFID 防碰撞算法的研究相對比較缺乏［2－4］，為消除或減少系統中的碰撞問題，設計出一種防碰撞能力強，識別速度快的主動式標簽防碰撞算法是很有必要的。

目前，主動式RFID 應用系統的防碰撞機制大多基于ALOHA 類防碰撞算法［5，6］，其中 包 括 改 進 型 的ALOHA［7］和時隙ALOHA 算法［8，9］。但是這些協議都較為簡單，數據重傳會經常發生，導致系統的吞吐量低，識別時間較長。文獻 ［10］提出了一種主動式RFID 動態退避算法，并對CSMA／CA 的退避時間進行了研究，該算法降低了主動式標簽功耗和讀取時延，但要求系統對數據碰撞自動檢測。文獻 ［11］在標簽密集環境下提出一種被動式標簽的PDC（power－based distance clustering）防碰撞機制，其機制只能運用在被動式標簽的防碰撞算法中，并不能用來解決主動式標簽的碰撞問題。

本文主要研究主動式RFID 防碰撞算法，針對上述問題，提出一種基于能量和距離分簇的主動式RFID 防碰撞機制，把這個機制稱之為EDC （energy and distance clustering）。本文首先對該機制進行理論分析和流程設計；然后利用提出的EDC 機制融合現有的純ALOHA、時隙ALOHA 和非堅持CSMA 防碰撞算法進行實驗仿真；最后對有無融合EDC 機制的防碰撞算法的吞吐量和平均傳輸時延進行分析與比較。

1 EDC機制理論模型

基于能量和距離分簇 （EDC）機制是一個適用于主動式RFID 系統的防碰撞機制。該機制基本原理是利用閱讀器接收到的主動式標簽的傳輸功率大小，對距離閱讀器周圍的主動式標簽做簇群分類，每個簇群內遠近的標簽是通過調整閱讀器的接收來自于標簽所發出的能量信號強弱進行辨識，而標簽發射功率的強度大小取決于標簽與閱讀器之間的距離。

1.1 能量傳輸分析

主動式RFID 系統在自由空間傳輸模型中，距離主動式標簽發射天線R 處的功率密度為

在閱讀器與主動式標簽最佳對準和正確極化時，閱讀器可接收的最大功率與功率密度S 成正比，則閱讀器的接收功率Pr為

式中：Ae——閱讀器接收天線的有效面積，最佳接收狀態下

因而有

式中：Pt——標簽的發射功率；Gt、Gr——標簽和閱讀器的天線增益；λ——所傳輸信號的波長 （取決于頻率）。

在自由空間傳輸中，電磁波隨著傳輸的距離增大，能量在自然擴散中引起傳輸損耗，則距離R 的自由空間傳輸損耗Lf為

由式 （5）可知，經過自由空間傳輸損耗后，距離主動式標簽R 處的閱讀器接收功率Pr為

則此時的主動式標簽發射功率為

1.2 EDC模型分析

主動式標簽和閱讀器的讀取之間的距離是變化的，因為標簽在不同位置的天線功率是不同的，由式 （6）可知閱讀器接收標簽功率Pr與R 的二次方成反比，距離越遠，閱讀器接收到的信號越弱。因此可根據式 （7）對閱讀器接收的可設定范圍內的標簽發射功率Pt大小進行分簇。通過利用接收功率的變化來進行標簽的距離群簇，極大的減少每次做防碰撞算法的標簽數目，以期達到更有效率的防碰撞。在EDC機制中，當進行防碰撞算法之前，會首先對所有的主動式標簽進行區域分類，然后再逐個簇群的進行防碰撞處理，所以，EDC機制能夠有效減少主動式RFID 系統的整體工作量，并能夠有效的縮短識別時間。

圖1表示EDC機制距離分簇模型。閱讀器對所有標簽按照其功率大小進行距離的排序和分類，用T、T′和T″來表示屬于不同簇群內的標簽，根據閱讀器從標簽那接收到不同的信號，可以分出不同群簇的標簽，而這些群簇也正是代表著距離遠近彼此不同的主動式標簽。圖1所示把每個簇群能量信號 （即主動式標簽發射功率）的區間值設為step 值，閱讀區域可以分為sd、sd－step 和sd－2＊step 標簽群簇區間，因此在任何時候，只有同一個群簇的標簽請求發送數據與閱讀器通信，優先從能量信號強的簇群開始識別。即當第一群簇sd 的標簽經閱讀器識別完畢后，并立即進入休眠模式，然后第二群簇sd′的標簽才能與閱讀器通信，以此類推進行識別。

圖1 閱讀器與標簽之間距離分簇

圖2所示，主動式標簽信號強度也可在同一簇群內進行層級分類，按照閱讀器接收的功率大小把標簽距離為d1＞d2＞d3＞d4＞d5，從而閱讀器對標簽的讀取順序為：T5→T4→T3→T2→T1，如此循環進行逐個讀取標簽信息，極大的減少標簽的碰撞。

2 基于EDC機制的算法流程

EDC機制的運行首先是閱讀器讀取第一個簇群后，所有屬于同一個簇群的主動式標簽都會進入休眠模式，閱讀器則會開始識別下一個簇群內的標簽，這樣一輪一輪的讀取閱讀器所能接收到的最遠的那個簇群為止，就結束了整個流程。

圖2 同一簇群內標簽能量信號強度分類

EDC的流程如圖3所示，首先所有的主動式標簽先對閱讀器發出請求指令，閱讀器接收到所有標簽發出的指令，其中也包含了信號的強度，然后閱讀器按照信號強度找出最大值和最小值，設置sd 為標簽信號的最強功率信號，把這個最強功率信號當作一個區間值step；如果還有任何未讀取的標簽，該標簽的信號強度又大于或等于sd 值，則這些標簽需要執行主動式防碰撞算法來解決碰撞問題；否則，就將sd 值減少一個區間值step；假如sd 小于最小值時，整個流程就結束。

圖3 基于EDC機制的算法流程

在理論上來說，EDC機制與現提出來的主動式算法相兼容，而大多數RFID 系統中，閱讀器都提供了功率控制機制，與EDC機制相結合能夠增強防碰撞能力。EDC 機制同樣也可以解決處在流動密集環境 （如物流倉庫或卸貨碼頭）的標簽碰撞，由于標簽碰撞率較高，識別過程需要較長的時間，則需要通過調整EDC 機制一個重要參數step值。此參數用來確定的標簽簇群的范圍，在一個簇群范圍內，step 值決定簇群內標簽的數量。在密集的環境中，需要有多個簇群，則step 值就調低，反之就調高，避免不必要的讀取次數，來提高識別效率。但本文暫不討論流動環境，因此設step 參數為固定值。

由圖3可知，整個EDC要運行成功，最重要的就是一開始閱讀器必須能夠成功的取得所有標簽的信號，并能夠分辨出最大和最小的信號強度，假如不能夠成功計算出標簽的最大和最小的信號強度時，就不能夠準確的對在場所有標簽根據它們與閱讀器的距離進行分簇，然而要達到這一目的，其中一個最重要的因素就是EDC 機制必須先要解決信號碰撞問題。由于信號在空氣環境下中傳送，閱讀器在接收信號的時候就很可能發生碰撞問題，如果因為碰撞問題導致EDC 在一開始就無法準確的辨識標簽的信息和它的信號強度時，那就整個機制無法順利執行。

前述提到的問題將嚴重影響EDC 的運行，根據ISO／IEC 18000－7主動式標簽收集算法［12］，本文結合時隙ALOHA 協議來解決這個問題，首先閱讀器對整個所有標簽發出請求并提出收集 （collection command）指令來取得所有標簽的信號。而對于主動式標簽來講，主動式標簽有自己的電源，所有一開始閱讀器可以通過喚醒命令 （wake－up）讓所有標簽從休眠中醒來，再進行查詢命令 （query command）獲取所有主動式標簽信號，通過獲取最大值最小值命令 （received max／min）分辨出最大和最小的信號強度，再搭配時隙 （Slot）的選擇，來解決EDC 機制下一開始取得標簽的信息和信號強度碰撞問題，如圖4所示。

圖4 解決EDC機制下取得信號強度最大最小值時閱讀器和標簽之間碰撞

3 仿真與實驗結果

通過上述理論分析，EDC 機制并不是一個一般性單獨存在的機制，相反的它必須搭配現今已被提出的主動式標簽的防碰撞算法來進行的。本文利用EDC 與現有的防碰撞算法相結合，來增強主動式標簽的防碰撞能力。以下實驗在Matlab仿真平臺進行，對EDC機制融合純ALOHA、時隙ALOHA 和非堅持CSMA 算法3種現有的防碰撞算法進行定量分析。通過文獻 ［1］所知衡量防碰撞算法優劣的主要有兩個指標：吞吐量和平均傳輸時延，其中實驗中的吞吐量是單位時間內成功傳輸到接入點的數據包的總和，平均傳輸時延是數據包從終端產生到成功的傳輸到接入點的平均時間間隔。

3.1 吞吐量性能分析

以下實驗對有無融合EDC 機制的純ALOHA、時隙ALOHA 和非堅持CSMA 這3種防碰撞算法進行吞吐量性能比較。從圖5 可以看出，在無搭載EDC 機制時，純ALOHA 算法的最大吞吐量為0.184，仿真結果與理論值吻合的很好。而在存在EDC 機制時，最大吞吐量為0.248，較大的提高了算法的吞吐量。

圖5 EDC機制在純ALOHA 算法中的吞吐量

從圖6和圖7可以看出，有EDC 機制的算法吞吐量提升效果顯著：時隙ALOHA 算法最大吞吐量從原算法的0.368提高到0.465；非堅持CSMA 算法的最大吞吐量提高至0.610。而隨著業務量的增加，融合EDC 機制的算法吞吐量下降更為緩慢，因此在可以證明有EDC 機制的算法都能得到進一步提升，吞吐量明顯優于原算法。

圖6 EDC機制在時隙ALOHA 算法中的吞吐量

3.2 平均傳輸時延分析

主動式RFID 系統在數據傳輸產生碰撞后，需要對發生碰撞的數據進行重傳，因此還需要考慮算法的傳輸時延特性。下面對純ALOHA、時隙ALOHA 和非堅持CSMA這3種算法搭載EDC機制進行平均傳輸時延分析，仿真結果如圖8～圖10所示。

圖7 EDC機制在非堅持CSMA 算法中的吞吐量

圖8 EDC機制在純ALOHA 算法中的平均傳輸時延

圖9 EDC機制在時隙ALOHA算法中的平均傳輸時延

從圖8和圖9的平均傳輸時延曲線可以看出，有EDC機制的延遲隨業務量的增加基本呈線性增加，而無EDC 機制的仿真延遲數據包的曲線隨業務量的增加呈指數增加，系統時延性能變得越來越差。由此可知基于EDC 機制的兩種算法延時都優于原算法。

圖10 EDC機制在非堅持CSMA算法中的平均傳輸時延

從圖10看到，EDC 機制在非堅持CSMA 算法中的平均傳輸時延在業務量較少時，兩者性能上都無差別，傳輸延遲并不顯著。而業務量增加到一定值時，無EDC 機制的原算法延遲曲線急劇上升，性能迅速惡化。因此當系統業務量較大時，基于EDC機制的非堅持CSMA 防碰撞算法的平均傳輸時延遠小于原算法。同時與圖8和圖9比較可知，基于EDC 的非堅持CSMA 算法比有EDC 機制的ALOHA和時隙ALOHA 算法性能更好，提供了相對較低的延遲。

綜合以上3種時延對比圖可以看出，有EDC 機制的算法延時都比原算法的延時要低，隨業務量的增加延時特性更為顯著，因此實驗也證明了EDC 機制也有效的提高了主動式RFID 系統識別速度。

4 結束語

本文針對主動式RFID 防碰撞算法的吞吐量低、識別速度慢的問題，提出一種基于能量和距離分簇 （EDC）主動式防碰撞機制。實驗通過3種基于EDC 機制防碰撞算法進行了分析與比較，可以得出如下結論：

（1）在系統吞吐量上，基于EDC 機制的算法比原算法的吞吐量均得到提高，證明EDC 機制有效的提高RFID 系統的吞吐量性能。

（2）在平均傳輸時延上，業務量較多時，基于EDC 機制的算法有相對有較低的時延，系統延時性能較好，使得提高了系統的識別速率。

（3）綜上，基于EDC 機制的算法增強了主動式RFID系統的防碰撞性能，提高了主動式RFID 在實際項目應用中的實用性。

［1］Karmakar，Nemai Chandra.Handbook of smart antennas for RFID systems［M］.New York：Wiley，2010.

［2］Klair D K，Chin K W，Raad R.A survey and tutorial of RFID anti－collision protocols［J］.Communications Surveys ＆ Tutorials，IEEE，2010，12 （3）：400－421.

［3］LIU Chenchen.Research on three kinds of mechanism of active RFID tag communication protocols［J］.Coal Technology，2012，31 （4）：166－168（in Chinese）.［劉塵塵.有源RFID 標簽通信協議三種機制研究［J］.煤炭技術，2012，31 （4）：166－168.］

［4］SUN Qunying.Research on anti－collision algorithms for dense active RFID system and applications［D］.Hangzhou：Zhejiang University，2011 （in Chinese）.［孫群英.密集環境中有源RFID防沖撞算法的研究及應用［D］.杭州：浙江大學，2011.］

［5］Huang Y H，Huang X，Sun Q.The design of the management system for parking lot based on 2.45GHz active RFID ［C］／／International Conference on Computer Science and Service System.IEEE，2011：850－853.

［6］Ullah S，Alsalih W，Alsehaim A，et al.A review of tags anticollision and localization protocols in RFID networks［J］.Journal of Medical Systems，2012，36 （6）：4037－4050.

［7］SHAN Jianfeng，CHEN Ming，XIE Jianbing.Research on RFID tag anti－collision technology base on aloha algorithm ［J］.Journal of Nanjing University of Posts and Telecommunications （Natural Science），2013，33 （1）：56－61 （in Chinese）. ［單劍鋒，陳明，謝建兵.基于ALOHA算法的RFID防碰撞技術研究［J］.南京郵電大學學報（自然科學版），2013，33 （1）：56－61.］

［8］Wang H，Pei C，Su B.Collision－free arbitration protocol for active RFID systems［J］.Journal of Communications and Networks，2012，14 （1）：34－39.

［9］SHU Yuanzhong，TIAN Lei，ZHANG Li.Time slots ALOHA anti－collision algorithm based on queuing theory［J］.Computer Engineering and Design，2013，34 （7）：2632－2636 （in Chinese）.［舒遠仲，田蕾，張麗.基于排隊理論的時隙ALOHA 防碰撞算法［J］.計算機工程與設計，2013，34 （7）：2632－2636.］

［10］Nilsson B，Bengtsson L，Svensson B.An application dependent medium access protocol for active RFID using dynamic tuning of the back－off algorithm ［C］／／IEEE International Conference on RFID.IEEE，2009：72－79.

［11］Ali K，Hassanein H，Tana A E M.RFID anti－collision protocol for dense passive tag environments［C］／／32nd IEEE Conference on Local Computer Networks.IEEE，2007：819－824.

［12］CHUNG S H，Dong－Chul S.Performance improvement of tag collection in active RFID systems based on ISO／IEC 18000－7［J］.IEICE Transactions on Communications，2011，94 （7）：2062－2073.