基于能量和距離分簇的主動(dòng)式RFID防碰撞算法

劉雄飛，周小軍，肖振國(guó)

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

0 引 言

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

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

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

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

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

1.1 能量傳輸分析

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

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

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

因而有

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

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

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

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

1.2 EDC模型分析

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

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

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

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

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

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

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

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

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

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

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

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

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

3 仿真與實(shí)驗(yàn)結(jié)果

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

3.1 吞吐量性能分析

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

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

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

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

3.2 平均傳輸時(shí)延分析

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

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

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

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

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

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

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

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

4 結(jié)束語(yǔ)

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

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

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

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

［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é)報(bào)（自然科學(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)仲，田蕾，張麗.基于排隊(duì)理論的時(shí)隙ALOHA 防碰撞算法［J］.計(jì)算機(jī)工程與設(shè)計(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.