基于身份競爭與協(xié)作的RFID閱讀器防碰撞算法

楊曉明，杜 力，王佳昊，鄧騰彬（.電子科技大學(xué)計算機(jī)科學(xué)與工程學(xué)院 成都 67；2.工業(yè)和信息化部電子第五研究所 廣州 5060；.東莞電子科技大學(xué)電子信息工程研究院 廣東 東莞 52808）

基于身份競爭與協(xié)作的RFID閱讀器防碰撞算法

楊曉明1，2，杜 力1，王佳昊1，鄧騰彬3
（1.電子科技大學(xué)計算機(jī)科學(xué)與工程學(xué)院 成都 611731；2.工業(yè)和信息化部電子第五研究所 廣州 510610；3.東莞電子科技大學(xué)電子信息工程研究院 廣東 東莞 523808）

在多閱讀器環(huán)境中，現(xiàn)有的大多數(shù)閱讀器防碰撞算法在利用各種方式確定某些閱讀器工作的同時，其他閱讀器只能閑置，使得閱讀器資源并未被充分利用。為優(yōu)化碰撞算法和系統(tǒng)效率，提出一種改進(jìn)算法，該算法利用閑置閱讀器協(xié)助其他閱讀器工作，并且引入身份競爭機(jī)制、雙信道機(jī)制和載波監(jiān)聽機(jī)制減少碰撞。通過與Pulse算法和ALOHA算法的仿真對比實(shí)驗(yàn)，可以發(fā)現(xiàn)改進(jìn)算法的系統(tǒng)效率和吞吐量有一定的優(yōu)勢。

載波監(jiān)聽；雙信道；身份競爭；閱讀器防碰撞；射頻識別

無線射頻識別（RFID）技術(shù)被廣泛應(yīng)用于各個行業(yè)，隨著物聯(lián)網(wǎng)技術(shù)的逐漸普及，在可以預(yù)見的未來，RFID技術(shù)還將被更多地應(yīng)用到日常生活和生產(chǎn)中。然而伴隨著RFID技術(shù)的廣泛應(yīng)用，RFID技術(shù)中的碰撞問題也日漸嚴(yán)重。碰撞是RFID中常見的問題，碰撞大致分為標(biāo)簽碰撞和閱讀器碰撞［1-2］。標(biāo)簽碰撞是多個標(biāo)簽的回復(fù)信號相互干擾使閱讀器無法正常識別標(biāo)簽；而閱讀器碰撞是多個閱讀器的信號相互干擾使標(biāo)簽與閱讀器的通信過程無法正常完成。目前市面上使用最多的標(biāo)簽防碰撞算法基于時分復(fù)用（time division multiple access，TDMA）方法，TDMA方法分為ALOHA的不確定性算法和基于二叉樹的確定性算法。平行雙閱讀器算法和主從式雙閱讀器算法是標(biāo)簽碰撞算法中比較有創(chuàng)新的算法［3］?，F(xiàn)有的閱讀器防碰撞算法主要分為基于控制閱讀器發(fā)射功率的方法［4-6］、基于時序的方法［7］、基于載波監(jiān)聽的方法及其他方法［8］。但是這些閱讀器防碰撞算法在確定某些閱讀器工作的同時，另外一些閱讀器則處于閑置狀態(tài)，使得閱讀器資源未被充分利用。本文提出一種改進(jìn)算法，該算法利用閑置閱讀器協(xié)助工作狀態(tài)的閱讀器，從而改進(jìn)系統(tǒng)效率和吞吐量。

1 相關(guān)工作

HiQ算法適用于閱讀器網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)比較穩(wěn)定的情況，類似于無線傳感網(wǎng)絡(luò)中的分簇算法，將閱讀器分3個等級，底層閱讀器、上層R-Server服務(wù)器和頂層Q-Server服務(wù)器，分別相當(dāng)于傳感網(wǎng)絡(luò)中的節(jié)點(diǎn)、簇頭和匯聚節(jié)點(diǎn)［2］。但如果閱讀器網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)變化頻繁，HiQ算法效率會比較低。Pulse算法利用了載波監(jiān)聽機(jī)制和雙信道機(jī)制，其流程如下：初始時，閱讀器A控制信道偵聽，如同時有其他閱讀器在讀寫標(biāo)簽，則閱讀器A在控制信道等待，否則閱讀器A廣播Request信號嘗試占用數(shù)據(jù)信道；若成功占用數(shù)據(jù)信道，則可以在數(shù)據(jù)信道和標(biāo)簽通信［1］，否則執(zhí)行退避算法。新型閱讀器防碰撞算法在Pulse算法基礎(chǔ)上做了改進(jìn)，性能有一定提高［2］。文獻(xiàn)［8-11］利用DCS（distributed color selection）或VDCS（variable-maximum DCS）算法對閱讀器進(jìn)行著色，不同顏色代表不同時隙，使閱讀器網(wǎng)絡(luò)中任意兩個相鄰的閱讀器發(fā)生碰撞的概率達(dá)到最小。除了算法上改進(jìn)，在閱讀器天線陣設(shè)計上［12］同樣能夠有效地減少閱讀器碰撞。另外文獻(xiàn)［13］提出了一個名為NFRA（neighbor friendly reader anti-collision algorithm）的基于全局調(diào)度的閱讀器防碰撞算法，利用一個名為serve的中央處理機(jī)為閱讀器分配工作，算法能夠適用于閱讀器網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)變化頻繁的環(huán)境。文獻(xiàn)［14］中提到的方法也是一種全局調(diào)度算法，先通過閱讀器之間的碰撞情況生成一個存儲碰撞信息的二維數(shù)組，然后在每一個讀寫周期打開相互沒有碰撞的閱讀器，關(guān)閉二維數(shù)組中有碰撞信息的閱讀器，但在閱讀器密集環(huán)境中系統(tǒng)效率有待改進(jìn)。文獻(xiàn)［15］是一種基于時隙的閱讀器防碰撞算法，算法中利用了多信道和競爭機(jī)制，閱讀器競爭信道，如果有多信道可用，閱讀器會根據(jù)每個信道的RSSI（received signal strength indication）值選擇最合適的信道。

2 基于身份競爭與協(xié)作的閱讀器防碰撞算法

圖1 算法應(yīng)用場景

基于身份競爭與協(xié)作的閱讀器防碰撞算法（IC2RA）利用了載波監(jiān)聽機(jī)制、雙信道機(jī)制和身份競爭機(jī)制。相鄰的多個閱讀器在控制信道競爭主閱讀器身份，競爭成功者成為主閱讀器，其余相鄰閱讀器成為從閱讀器，并輔助主閱讀器的工作。主閱讀器可以在數(shù)據(jù)信道讀寫標(biāo)簽。圖1描繪了一個應(yīng)用場景，虛線標(biāo)識出了主閱讀器控制信道的覆蓋范圍。

2.1 算法前提

首先，算法將RFID系統(tǒng)通信信道分為控制信道和數(shù)據(jù)信道。控制信道用于閱讀器間的通信；數(shù)據(jù)信道用于閱讀器和標(biāo)簽之間的通信。控制信道的覆蓋范圍必須保證所有在數(shù)據(jù)信道可能產(chǎn)生相互干擾的閱讀器之間能夠通過控制信道互相通信［2］?？梢酝ㄟ^提高控制信道的發(fā)射功率保證控制信道的通信范圍大于數(shù)據(jù)信道的通信范圍?？刂菩诺朗钦麄€RFID系統(tǒng)頻段的一部分，和數(shù)據(jù)信道相互之間不會產(chǎn)生干擾。

其次，算法對后臺系統(tǒng)有一定要求。要求后臺計算能力相對較強(qiáng)，而閱讀器只是作為后臺系統(tǒng)的前端終端存在。后臺不僅存儲了標(biāo)簽IDTag等信息，還為每個閱讀器分配了一個唯一的IDreader。后臺會對閱讀器發(fā)送來的消息進(jìn)行分析，并根據(jù)分析結(jié)果確定是否接受某個閱讀器的消息，具有一定的安全防御作用。

2.2 算法介紹

閱讀器的有限自動機(jī)如圖2所示。其中，閱讀器可能經(jīng)歷的狀態(tài)有6種，大致可分為3類：休眠狀態(tài)、主閱讀器狀態(tài)、從閱讀器狀態(tài)。從閱讀器狀態(tài)包括偵聽、等待、身份競爭、隨機(jī)延時4個狀態(tài)，而除休眠狀態(tài)以外的狀態(tài)只要收到后臺的Sleep信號，都會進(jìn)入休眠狀態(tài)。下面就以該狀態(tài)轉(zhuǎn)換圖來描述算法流程。

1）初始時，所有閱讀器處在休眠狀態(tài)，如果有數(shù)據(jù)請求來到，閱讀器A開始在控制信道偵聽；否則繼續(xù)休眠。

2）偵聽狀態(tài)的閱讀器A在Tmin［8］時間內(nèi)若聽到Request或Occupy信號，則閱讀器A立即進(jìn)入等待狀態(tài)；若Tmin時間內(nèi)沒偵聽到Request和Occupy，則閱讀器A廣播Request并立即進(jìn)入身份競爭狀態(tài)。

3）若閱讀器A在等待狀態(tài)收到End信號或者等待時間超過Tmin時限，閱讀器A開始隨機(jī)延時，延時算法類似802.11算法中的backoffs［8］，延時結(jié)束閱讀器A進(jìn)入身份競爭狀態(tài)。

圖2 閱讀器有限自動機(jī)

4）若閱讀器A在競爭狀態(tài)廣播Request信號后，收到Occupy信號，則閱讀器A從身份競爭狀態(tài)回到等待狀態(tài)。若在Tmin時間內(nèi)未收到Occupy信號則閱讀器A身份標(biāo)志置Mas，表示閱讀器A現(xiàn)在成為主閱讀器，可以在數(shù)據(jù)信道開始讀寫標(biāo)簽。

5）一個讀寫標(biāo)簽周期結(jié)束，閱讀器A廣播End信號并將身份標(biāo)志位置為Sla，回到偵聽狀態(tài)。

2.3 主閱讀器工作描述

主閱讀器在數(shù)據(jù)信道讀寫標(biāo)簽，在控制信道廣播控制信號避免碰撞。數(shù)據(jù)信道和控制信道的工作流程描述如下（其中，IDreaderA表示主閱讀器ID，IDreaderB表示從閱讀器ID，IDTag表示標(biāo)簽ID，Sk表示標(biāo)簽密鑰，readerA表示主閱讀器，readerB表示從閱讀器）：

在數(shù)據(jù)信道，主閱讀器廣播發(fā)送Query||IDreaderA，收到標(biāo)簽回復(fù)的消息Hash（IDTag⊕Sk||IDreaderA）后，主閱讀器會將此消息轉(zhuǎn)發(fā)給后臺。

在控制信道，主閱讀器如果收到其他閱讀器的Request信號，則進(jìn)行判斷。如果身份標(biāo)志是Mas且還未廣播End信號，則主閱讀器在控制信道廣播發(fā)送Occupy；除此以外，主閱讀器不響應(yīng)Request信號。

2.4 從閱讀器工作描述

從閱讀器在控制信道不斷嘗試競爭成為主閱讀器，工作流程無需再贅述。下面主要介紹從閱讀器在數(shù)據(jù)信道的工作。

當(dāng)從閱讀器收到標(biāo)簽消息Hash（IDTag⊕Sk||IDreaderA）后，便在消息末尾加上IDreaderB，此時標(biāo)簽消息變成Hash（IDTag⊕Sk||IDreaderA||IDreaderB）。與此同時，若從閱讀器處于隨機(jī)延時狀態(tài)便將自身的延時起始時間置0，重新開始隨機(jī)延時。在標(biāo)簽消息中加上從閱讀器的ID讓后臺能分辨標(biāo)簽消息來源于主閱讀器或從閱讀器；更新延時起始時間可盡量減少從閱讀器發(fā)送Request的次數(shù)，也減少了主閱讀器響應(yīng)Occupy的次數(shù)，增加了主閱讀器的有效工作時間，同時減少了閱讀器的能耗開銷。而一旦延時時間內(nèi)沒收到標(biāo)簽消息，延時結(jié)束的從閱讀器就可以開始身份競爭。這樣既保證了主閱讀器的有效工作時間，又保證了每個閱讀器都有機(jī)會競爭成為主閱讀器。

2.5 后臺系統(tǒng)工作描述

后臺系統(tǒng)的工作主要有：

1）發(fā)送Sleep信號和數(shù)據(jù)請求。

后臺系統(tǒng)為每個閱讀器維護(hù)兩個時間戳，一個時間戳記錄該閱讀器最近一次競爭成為主閱讀器的時間，稱為最近主閱讀器時間戳（latest master timestamp，LMT），每次閱讀器競爭成為主閱讀器且在讀寫周期開始前，便向后臺發(fā)送一個消息來更新LMT值；另一個時間戳記錄該閱讀器最近一次作為從閱讀器轉(zhuǎn)發(fā)標(biāo)簽消息的時間，稱為最近從閱讀器時間戳（latest slave timestamp，LST），這個時間戳可以根據(jù)后臺收到的Hash（IDTag⊕Sk||IDreaderA||IDreaderB）更新LST值。這兩個時間戳都是后臺本地時間，不需要進(jìn)行閱讀器和后臺系統(tǒng)的時間同步。根據(jù)這兩個時間戳，可以得到兩個時間差值，定義如下：

DMR=LT?LMT

DSR=LT?LST

式中，LT（local time）為后臺系統(tǒng)本地時間；DMR描述了閱讀器有多長時間沒有成為主閱讀器；DSR描述了閱讀器多長時間沒有作為從閱讀器輔助其他閱讀器工作。根據(jù)這兩個時間差值可以了解每個閱讀器的工作情況，若都大于各自的門限值則表明該閱讀器一段時間內(nèi)沒有實(shí)際有效的工作，后臺系統(tǒng)便向該閱讀器發(fā)送Sleep信號，使其休眠。當(dāng)再次有數(shù)據(jù)請求到達(dá)該閱讀器時，再將該閱讀器打開（如仿真實(shí)驗(yàn)中兩個門限值都設(shè)為10s，每5s計算一次DMR和DSR）。

2）對標(biāo)簽消息進(jìn)行分析，并根據(jù)分析結(jié)果做出響應(yīng)。

①后臺系統(tǒng)根據(jù)消息格式判斷消息來源。如果收到的標(biāo)簽消息格式為 Hash（IDTag⊕Sk||IDreaderA），表明消息來自主閱讀器，則判斷IDreaderA是否合法。如不合法，則廣播通知所有閱讀器此后收到的readerA消息都丟棄；若IDreaderA合法，則判斷IDTag是否合法。如IDTag不合法，閱讀器就不響應(yīng)該標(biāo)簽消息，否則響應(yīng)該標(biāo)簽消息。

②如果收到的標(biāo)簽消息格式為Hash（IDTag⊕Sk||IDreaderA||IDreaderB），表明消息來自從閱讀器，則先判斷IDreaderB是否合法：如IDreaderB不合法，則后臺收到閱讀器ID為IDreaderB的消息都丟棄；如IDreaderB合法，則執(zhí)行步驟①的流程。

3 算法仿真

該算法使用MATLAB進(jìn)行仿真，仿真主要對兩個指標(biāo)進(jìn)行比較：系統(tǒng)吞吐量和系統(tǒng)效率。

3.1 仿真內(nèi)容

Requesti表示第i個閱讀器發(fā)送的Request請求數(shù)，RequestSuci表示第i個閱讀器發(fā)送且被標(biāo)簽正確回復(fù)的Request請求數(shù)，Time表示仿真進(jìn)行的時間。

系統(tǒng)吞吐量定義為：

系統(tǒng)效率定義為：

由于RFID系統(tǒng)的工作模式基本上是閱讀器請求越多，請求最終被成功響應(yīng)的也越多，同時考慮到響應(yīng)同樣數(shù)量的請求有時間和成功率的差異，所以選擇系統(tǒng)吞吐量和系統(tǒng)效率作為測試指標(biāo)。為體現(xiàn)該算法的性能，將該算法與已有的Pulse［1］和ALOHA［2］算法在同等條件下進(jìn)行仿真比較。

3.2 仿真條件及結(jié)果分析

MATLAB仿真條件為：閱讀器數(shù)量分別為10、20、30、40、50、60、70。標(biāo)簽數(shù)量為400，標(biāo)簽分布在10m×10m的范圍內(nèi)。偵聽時間選擇15ms，Tmin等待時間也為15ms，backoffs選擇在0～15ms之間的一個隨機(jī)值，DMR和DSR門限設(shè)為10s，每5s計算一次DMR和DSR，仿真時間Time為300s。圖3給出了3種算法的系統(tǒng)吞吐量的比較曲線。

圖3 系統(tǒng)吞吐量的比較曲線

圖3中，可以看出ALOHA算法在多閱讀器環(huán)境中的吞吐量明顯低于其他兩種算法。ALOHA算法由于每次閱讀器收到請求都會立即讀寫標(biāo)簽，而忽視了其他閱讀器在數(shù)據(jù)信道工作的可能性，碰撞發(fā)生頻繁，吞吐量較低。IC2RA算法隨著閱讀器數(shù)量的增加較Pulse算法體現(xiàn)出明顯優(yōu)勢，這是因?yàn)樵贗C2RA算法中從閱讀器協(xié)助主閱讀器的讀寫工作的緣故。在IC2RA中，當(dāng)從閱讀器將標(biāo)簽信息轉(zhuǎn)發(fā)給后臺系統(tǒng)后，后臺會對信息進(jìn)行處理和判斷，如果信息合法，后臺會立即通知主閱讀器讀寫該標(biāo)簽，從而使主閱讀器在一個讀寫周期能識別多個標(biāo)簽，提高了系統(tǒng)吞吐量。

圖4是系統(tǒng)效率的比較曲線。在系統(tǒng)效率的比較中，ALOHA算法依然明顯低于其他兩種算法。10個閱讀器時效率為9％，70個閱讀器時只有4％。IC2RA算法和Pulse算法相差無幾，兩種算法對閱讀器請求的響應(yīng)成功率都比較高，在10個閱讀器時Pulse算法效率幾乎為100％，IC2RA算法效率為95％。隨著閱讀器數(shù)量的增加，Pulse和IC2RA算法效率相差不大，但是IC2RA算法的效率更為穩(wěn)定，在70個閱讀器環(huán)境中IC2RA算法效率依然有94％。

圖4 系統(tǒng)效率的比較曲線

4 結(jié)束語

本文針對閱讀器防碰撞問題進(jìn)行探討，提出了一種基于載波監(jiān)聽的閱讀器防碰撞算法，該算法采用多閱讀器之間進(jìn)行局部競爭的方法確定工作閱讀器，競爭成功者開始讀寫工作，這相比于全局協(xié)調(diào)的方法效率更高。該算法利用閱讀器網(wǎng)絡(luò)中的閑置閱讀器協(xié)助工作閱讀器的讀寫工作，以提高系統(tǒng)效率。仿真結(jié)果表明該算法的吞吐量和系統(tǒng)效率相比于已有算法有一定的優(yōu)勢。

［1］MBIRARI S，IYER S.PULSE：a MAC protocol for RFID networks［J］.Communications and Mobile Computing，2009（2）：313-316.

［2］魏欣.RFID標(biāo)簽及閱讀器防碰撞算法研究［D］.成都：電子科技大學(xué)，2009.

WEI Xin.Research on anti-collision algorithms for RFID tags and readers［D］.Chengdu：University of Electronic Science and Technology of China，2009.

［3］孫群英.密集環(huán)境中有源RFID防沖撞算法的研究及應(yīng)用［D］.杭州：浙江大學(xué)，2011.

SUN Qun-ying.Research on anti-collision algorithms for dense active RFID systems and applications［D］.Hangzhou：Zhejiang University，2011.

［4］陳穎，張洪福.RFID傳感網(wǎng)絡(luò)中多閱讀器碰撞算法的研究［J］.傳感技術(shù)學(xué)報，2010，23（2）：265-268.

CHEN Ying，ZHANG Hong-fu.Study on reader anti-collision algorithm in RFID sensor networks［J］.Chinese Journal of Sensors and Actuators，2010，23（2）：265-268.

［5］陳穎.一種新的多閱讀器防碰撞算法的研究［J］.杭州電子科技大學(xué)學(xué)報，2012，32（5）：112-115.

CHEN Ying.Research on a novel reader anti-collision algorithm［J］.Journal of Hangzhou Dianzi University，2012，32（5）：112-115.

［6］李雪，陸百川，李政.RFID系統(tǒng)多閱讀器防碰撞問題研究［J］.重慶交通大學(xué)學(xué)報（自然科學(xué)版），2012，31（3）：435-438.

LI Xue，LU Bai-chuan，LI Zheng.Study on reader anti-collision algorithm in RFID system［J］.Journal of Chongqing Jiaotong University（Natural Science），2012，31（3）：435-438.

［7］孫文勝，胡玲敏.基于調(diào)度方式的多閱讀器防碰撞算法［J］.計算機(jī)工程，2012，38（9）：258-261.

SUN Wen-sheng，HU Ling-min.Anti-collision algorithm for multi-reader based on schedule mode［J］.Computer Engineering，2012，38（9）：258-261.

［8］徐雪慧.射頻識別技術(shù)中防沖突算法研究［D］.武漢：華中師范大學(xué)，2006.

XU Xue-hui.Study on the anti-collision algorithm in radio frequency identification technology［D］.Wuhan：Central China Nromal University，2006.

［9］GALIOTTO C，MARCHETTI N，PRAEAD N，et al.Low access delay anti-collision algorithm for readers in passive RFID systems［J］.Wireless Pers Commun，2012，64：169-183.

［10］GANDINO F，F(xiàn)ERRERO R，MONTRUCCHIO B，et al.Probabilistic DCS：an RFID reader-to-reader anti-collision protocol［J］. Journal of Network and Computer Applications，2011，34：821-832.

［11］祁士東.基于圖染色思想的RFID防沖突算法研究［J］.電子測試，2012（9）：28-31.

Qi Shi-dong.Research of RFID anti collision algorithm based on graph coloring［J］.Electronic Test，2012（9）：28-31.

［12］鄧毅華.RFID射頻若干問題研究［D］.廣州：華南理工大學(xué)，2009.

Deng Yi-hua.Rearch on some issues about the RF of RFID［D］.Guangzhou：South China University of Technology，2009.

［13］EOM J B，YIM S B，LEE T J.An efficient reader anticollision algorithm in dense RFID networks with mobile RFID readers［J］.IEEE Transactions on Industrial Electronics，2009，56（7）：2326-2336.

［14］CHEN N K，CHEN J L，LEE C C.Array-based reader anti-collision scheme for highly efficient RFID network applications［J］.Wireless Communications and Mobile Computing.2009（9）：976- 987.

［15］QUAN C H，CHOI J C，CHOI G Y，et al.The slotted-LBT：a RFID reader medium access scheme in dense reader environments［C］//The 2008 IEEE International Conference on RFID.Las Vegas，Nevada，USA：IEEE，2008：16-17.

編輯 漆 蓉

Improved RFID Anti-Collision Algorithm Based on Indentity Competition and Cooperation

YANG Xiao-ming1，2，DU Li1，WANG Jia-hao1，and DENG Teng-bin3
（1.School of Computer Science and Engineering，University of Electronic Science and Technology of China Chengdu 611731；2.The Fifth Research Institute of Ministry of Information Industry Guangzhou 510610；3.Institute of Electronic and Information Engineering in Dongguan， University of Electronic Science and Technology of China Dongguan Guangdong 523808）

In a multiple radio frequency identification（RFID）reader environment，most of the reader anti-collision algorithms use a variety of means to determine reader duty ratio，which leads to the reader resource not be fully exploited.In order to reduce collisions and optimize the system efficiency，this paper presents an improved algorithm which utilizes idled readers to assist those in work while avoiding conflict by introducing identity competition，double channels and carrier sensing.Simulation results show that the algorithm has certain advantage of system efficiency and system throughput in comparison with Pulse and ALOHA.

carrier sensing；double channels；identity competition；reader anti-collision；RFID

TP393

A

10.3969/j.issn.1001-0548.2015.05.021

2014-02-26；

2014-09-25

國家自然科學(xué)基金（61003230）；四川省科技支撐計劃支撐項(xiàng)目（2013GZ0022）

楊曉明（1974-），男，博士生，高級工程師，主要從事信息安全、無線傳感網(wǎng)絡(luò)與RFID方面的研究.