劉雄飛，周小軍，肖振國

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

0 引 言

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

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

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

1 EDC機(jī)制理論模型

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

1.1 能量傳輸分析

主動式RFID 系統(tǒng)在自由空間傳輸模型中，距離主動式標(biāo)簽發(fā)射天線R 處的功率密度為

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

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

因而有

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

在自由空間傳輸中，電磁波隨著傳輸?shù)木嚯x增大，能量在自然擴(kuò)散中引起傳輸損耗，則距離R 的自由空間傳輸損耗Lf為

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

則此時的主動式標(biāo)簽發(fā)射功率為

1.2 EDC模型分析

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

圖1表示EDC機(jī)制距離分簇模型。閱讀器對所有標(biāo)簽按照其功率大小進(jìn)行距離的排序和分類，用T、T′和T″來表示屬于不同簇群內(nèi)的標(biāo)簽，根據(jù)閱讀器從標(biāo)簽?zāi)墙邮盏讲煌男盘?，可以分出不同群簇的?biāo)簽，而這些群簇也正是代表著距離遠(yuǎn)近彼此不同的主動式標(biāo)簽。圖1所示把每個簇群能量信號 （即主動式標(biāo)簽發(fā)射功率）的區(qū)間值設(shè)為step 值，閱讀區(qū)域可以分為sd、sd－step 和sd－2＊step 標(biāo)簽群簇區(qū)間，因此在任何時候，只有同一個群簇的標(biāo)簽請求發(fā)送數(shù)據(jù)與閱讀器通信，優(yōu)先從能量信號強(qiáng)的簇群開始識別。即當(dāng)?shù)谝蝗捍豷d 的標(biāo)簽經(jīng)閱讀器識別完畢后，并立即進(jìn)入休眠模式，然后第二群簇sd′的標(biāo)簽才能與閱讀器通信，以此類推進(jìn)行識別。

圖1 閱讀器與標(biāo)簽之間距離分簇

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

2 基于EDC機(jī)制的算法流程

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

圖2 同一簇群內(nèi)標(biāo)簽?zāi)芰啃盘枏?qiáng)度分類

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

圖3 基于EDC機(jī)制的算法流程

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

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

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

圖4 解決EDC機(jī)制下取得信號強(qiáng)度最大最小值時閱讀器和標(biāo)簽之間碰撞

3 仿真與實驗結(jié)果

通過上述理論分析，EDC 機(jī)制并不是一個一般性單獨存在的機(jī)制，相反的它必須搭配現(xiàn)今已被提出的主動式標(biāo)簽的防碰撞算法來進(jìn)行的。本文利用EDC 與現(xiàn)有的防碰撞算法相結(jié)合，來增強(qiáng)主動式標(biāo)簽的防碰撞能力。以下實驗在Matlab仿真平臺進(jìn)行，對EDC機(jī)制融合純ALOHA、時隙ALOHA 和非堅持CSMA 算法3種現(xiàn)有的防碰撞算法進(jìn)行定量分析。通過文獻(xiàn) ［1］所知衡量防碰撞算法優(yōu)劣的主要有兩個指標(biāo)：吞吐量和平均傳輸時延，其中實驗中的吞吐量是單位時間內(nèi)成功傳輸?shù)浇尤朦c的數(shù)據(jù)包的總和，平均傳輸時延是數(shù)據(jù)包從終端產(chǎn)生到成功的傳輸?shù)浇尤朦c的平均時間間隔。

3.1 吞吐量性能分析

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

圖5 EDC機(jī)制在純ALOHA 算法中的吞吐量

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

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

3.2 平均傳輸時延分析

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

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

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

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

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

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

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

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

4 結(jié)束語

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

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

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

（3）綜上，基于EDC 機(jī)制的算法增強(qiáng)了主動式RFID系統(tǒng)的防碰撞性能，提高了主動式RFID 在實際項目應(yīng)用中的實用性。

［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 標(biāo)簽通信協(xié)議三種機(jī)制研究［J］.煤炭技術(shù)，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）.［孫群英.密集環(huán)境中有源RFID防沖撞算法的研究及應(yīng)用［D］.杭州：浙江大學(xué)，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防碰撞技術(shù)研究［J］.南京郵電大學(xué)學(xué)報（自然科學(xué)版），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）.［舒遠(yuǎn)仲，田蕾，張麗.基于排隊理論的時隙ALOHA 防碰撞算法［J］.計算機(jī)工程與設(shè)計，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.