基于隨機(jī)時(shí)隙的RFID讀寫器防沖突方法

張光山 張 爍 張有光

（北京航空航天大學(xué) 電子信息工程學(xué)院，北京100191）

無線射頻識別系統(tǒng)中讀寫器和標(biāo)簽通信具有空間受限的特性.由于 RFID（Radio Frequency I－dentification）讀寫器的覆蓋范圍有限，在很多RFID系統(tǒng)應(yīng)用中，需要RFID讀寫器能在一個(gè)大的范圍內(nèi)的任何地方都能讀寫標(biāo)簽，因此必須在整個(gè)范圍內(nèi)配置很多讀寫器，不可避免地存在讀寫器沖突問題.

隨著RFID的廣泛應(yīng)用，讀寫器沖突問題得到重視并做了一些研究.文獻(xiàn)［1］最早提出了RFID讀寫器沖突問題，并指出讀寫器沖突是一種類似于簡單圖著色問題.隨后文獻(xiàn)［2］提出了一種Colorwave讀寫器防沖突算法.Colorwave是一種基于時(shí)分多址原理的分布式防沖突算法，當(dāng)網(wǎng)絡(luò)中讀寫器的數(shù)量比較小時(shí)該方法是有效和可行的.文獻(xiàn)［3］提出一種分布式顏色選擇算法（DCS，Distributed Colour Selection），該算法的時(shí)隙數(shù)是固定的并且容易實(shí)現(xiàn)，然而當(dāng)時(shí)隙數(shù)與讀寫器數(shù)不匹配時(shí)，算法性能將大大降低.文獻(xiàn)［4］提出一種增強(qiáng)型PDCS（Probability DCS）算法，當(dāng)讀寫器發(fā)生碰撞時(shí)則依據(jù)預(yù)先設(shè)定的概率閾值選擇新的顏色，可降低碰撞概率，但概率閾值的選擇會(huì)影響系統(tǒng)性能［5］.歐洲電信標(biāo)準(zhǔn)協(xié)會(huì)發(fā)布的EN 302 208標(biāo)準(zhǔn)［6］采用一種基于載波偵聽多路訪問（CSMA，Carrier Sense Multi－Access）原理的先偵聽后發(fā)言的方法來減少讀寫器沖突情況.該方法盡管實(shí)現(xiàn)簡單，但是可能導(dǎo)致某些讀寫器長時(shí)間無法獲得信道.EPC Class I Gen2標(biāo)準(zhǔn)［7］闡述了采用頻分多址原理來避免讀寫器沖突的算法，但是由于大部分的標(biāo)簽不具備頻率分辨能力，因此仍然存在讀寫器沖突情況.Pulse算法［8］將讀寫器的通信信道分為控制信道和數(shù)據(jù)信道，由于該算法采用競爭檢測機(jī)制，當(dāng)有大量讀寫器同時(shí)競爭信道時(shí)，算法的訪問延遲性能將大大降低.

傳統(tǒng)基于時(shí)隙分配的防沖突方法可分為分布式與集中式時(shí)隙控制兩種.第一種方法以Colorwave［2］等算法為代表，時(shí)隙分配過程以網(wǎng)絡(luò)中的每個(gè)讀寫器為中心，各讀寫器之間相互反復(fù)通信協(xié)商來確定各自的工作時(shí)隙，發(fā)生沖突時(shí)往往通過增加新的時(shí)隙來解決，結(jié)果是時(shí)隙分配過程較長且需要的總時(shí)隙數(shù)目增多；第二種方法通過中央計(jì)算機(jī)運(yùn)行優(yōu)化算法來進(jìn)行時(shí)隙分配求解，幾乎不占用讀寫器資源，不過該方法的性能取決于所選擇的優(yōu)化算法的復(fù)雜度.

為了解決RFID網(wǎng)絡(luò)中的協(xié)議沖突，本文在結(jié)合分布式和集中式時(shí)隙控制方法的基礎(chǔ)上提出一種基于隨機(jī)時(shí)隙并通過中央計(jì)算機(jī)協(xié)調(diào)的讀寫器防沖突方法.提出讀寫器根據(jù)當(dāng)前利用率隨機(jī)選擇時(shí)隙，提高了各讀寫器讀寫的公平性；增加額外時(shí)隙使得讀寫器有更多機(jī)會(huì)讀寫標(biāo)簽，提升RFID系統(tǒng)的吞吐量.中央計(jì)算機(jī)負(fù)責(zé)同步和協(xié)調(diào)各讀寫器時(shí)隙，讀寫器根據(jù)鄰近讀寫器工作和碰撞情況選擇時(shí)隙執(zhí)行讀寫操作，從而消除讀寫器之間的沖突情況.

1 多讀寫器防沖突方法

密集讀寫器環(huán)境是指在RFID系統(tǒng)中，在預(yù)定區(qū)域內(nèi)部署多個(gè)RFID讀寫器，以滿足對區(qū)域內(nèi)的所有標(biāo)簽進(jìn)行完全的高可靠的讀寫.

讀寫器網(wǎng)絡(luò)通常包含多個(gè)讀寫器和一個(gè)中央計(jì)算機(jī)，讀寫器與中央計(jì)算機(jī)一般采用局域網(wǎng)或者無線局域網(wǎng)方式進(jìn)行通訊連接.網(wǎng)絡(luò)中每個(gè)讀寫器可能具有不同范圍的讀寫區(qū)域，各讀寫器的讀寫區(qū)域可能有交集，即讀寫區(qū)域有相互重疊地方.另外由于RFID系統(tǒng)的非對稱性，標(biāo)簽反射到讀寫器的信號能量很低，因此在一個(gè)很大的范圍內(nèi)都可能存在讀寫器到讀寫器的干擾即干擾范圍遠(yuǎn)大于讀寫范圍.

假定RFID系統(tǒng)中各讀寫器使用相同信道，讀寫器信標(biāo)和忙信號的通信范圍為讀寫器的干擾范圍，中央計(jì)算機(jī)負(fù)責(zé)同步和協(xié)調(diào)各讀寫器.本文防沖突方法主要結(jié)合了分布式和集中式時(shí)隙分配的優(yōu)缺點(diǎn)，具體流程如下：

1）中央計(jì)算機(jī)發(fā)送每輪回起始命令，并根據(jù)整個(gè)讀寫器網(wǎng)絡(luò)規(guī)模，選擇合適的總時(shí)隙數(shù)M并通知各個(gè)讀寫器.

2）讀寫器根據(jù)接收到的M值和各自的利用率隨機(jī)選擇合適的時(shí)隙.將M 個(gè)時(shí)隙n等分，其中n＜M，低利用率的讀寫器可以選擇低時(shí)隙進(jìn)行工作，提高了各讀寫器之間的公平性.設(shè)讀寫器ri工作次數(shù)為wi，輪回間隔為u和當(dāng)前輪回間隔數(shù)為m，定義利用率li為

則讀寫器ri隨機(jī)選擇范圍內(nèi)的時(shí)隙值，其中%為求模運(yùn)算，其中■·」和「·■分別為下取整數(shù)和上取整數(shù).

3）中央計(jì)算機(jī)開始間隔發(fā)送M個(gè)時(shí)隙指令，時(shí)隙指令的時(shí)隙參數(shù)值是從0開始到M－1，協(xié)調(diào)同步各讀寫器.

4）讀寫器接收到的時(shí)隙參數(shù)值若等于自身隨機(jī)選擇的時(shí)隙值，則開始在該時(shí)隙進(jìn)行操作.若之前收到其它鄰近讀寫器發(fā)送的忙信號，則在該輪回不工作，否則發(fā)送信標(biāo)并偵聽.若讀寫器接收到鄰近讀寫器發(fā)送的信標(biāo)，則該讀寫器在該時(shí)隙停止工作，否則發(fā)送忙信號給鄰近讀寫器并開始讀寫標(biāo)簽.

5）當(dāng)中央計(jì)算機(jī)發(fā)送完M 個(gè)時(shí)隙指令，則開始發(fā)送額外時(shí)隙指令.若RFID系統(tǒng)中讀寫器都在讀寫標(biāo)簽或者不工作的讀寫器都接收到忙信號，則該時(shí)隙沒有讀寫器工作.若存在空閑和沒有接收到忙信號的讀寫器，則該讀寫器發(fā)送二次信標(biāo)并偵聽，若接收到鄰近讀寫器的信標(biāo)則該時(shí)隙不工作，否則開始讀寫標(biāo)簽.

6）當(dāng)周期時(shí)間到，所有讀寫器停止讀寫標(biāo)簽，中央計(jì)算機(jī)根據(jù)當(dāng)前網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)和規(guī)模選擇新的時(shí)隙數(shù)并開始下一周期的操作.

2 性能分析

本節(jié)分析讀寫器的讀寫概率和在額外時(shí)隙發(fā)送二次信標(biāo)的讀寫器個(gè)數(shù).假設(shè)讀寫器ri有V個(gè)鄰近讀寫器，選擇第mi個(gè)時(shí)隙.令Pm（V，M，l，n）為讀寫器在第m個(gè)時(shí)隙有V個(gè)鄰近讀寫器時(shí)讀寫標(biāo)簽的概率.對于任一時(shí)隙k（0≤k≤M－1），讀寫器存在3種情況：①?zèng)]有鄰近讀寫器選擇該時(shí)隙；②至少有兩個(gè)鄰近讀寫器選擇該時(shí)隙；③只有唯一個(gè)鄰近讀寫器選擇該時(shí)隙.

讀寫器ri在時(shí)隙mi若滿足以下兩個(gè)條件就可以讀寫標(biāo)簽：

1）對于k＝mi，滿足情況①，設(shè)概率為P1；

2）對于?k，0≤k≤mi－1，至少需要滿足情況①或②，設(shè)概率為P2.

首先分析l＝1，n＝1的情況，設(shè)讀寫器等概率地選擇M個(gè)時(shí)隙，則

當(dāng)mi＝1，由于不可能收到其它讀寫器的忙信號，則讀寫器一定滿足條件2）.另外由于讀寫器隨機(jī)選擇時(shí)隙，則讀寫器選擇相同時(shí)隙的概率服從二項(xiàng)分布，則概率密度函數(shù)為

則

當(dāng)mi＞2時(shí)，P2主要取決于前面時(shí)隙鄰近讀寫器的讀寫情況.定義遞推函數(shù)Q（V，r，mi）：對于?k（0≤k≤mi－r－1）滿足條件2），同時(shí)對于?k（mi－r－1＜k＜mi－1）也滿足條件2），而且對于k＝mi滿足條件1），因此 P2＝Q（V，1，mi），則

其中Q（V，r，mi）為1.則讀寫器ri在該時(shí)隙讀寫標(biāo)簽的概率為

則讀寫器ri每輪回的讀寫標(biāo)簽概率為

當(dāng)l≠1和n≠1，讀寫器的讀寫概率不僅與鄰近讀寫器有關(guān)，還和利用率相關(guān).設(shè)具有利用率為li的讀寫器ri有Vli個(gè)鄰近讀寫器，則讀寫器具有最低利用率li＝0時(shí)對應(yīng)的讀寫概率為

利用率為li＝1的讀寫器只有當(dāng)最低利用率的讀寫器發(fā)生相互碰撞時(shí)才能讀寫標(biāo)簽，概率為

則利用率為l的讀寫器每輪回讀寫概率為

假設(shè)RFID系統(tǒng)中N個(gè)讀寫器，讀寫器ri在當(dāng)前輪回讀寫標(biāo)簽的個(gè)數(shù)為ui，則每輪回RFID系統(tǒng)的吞吐量即所有讀寫器每輪回讀寫標(biāo)簽的總數(shù)為

從式（9）可知，最低利用率的讀寫器具有最高讀寫概率，并且隨著利用率增加，讀寫概率急劇下降.下面分析每輪在額外時(shí)隙發(fā)送二次信標(biāo)的讀寫器個(gè)數(shù).

設(shè)每個(gè)讀寫器平均有V個(gè)鄰近讀寫器，系統(tǒng)在時(shí)隙i空閑讀寫器個(gè)數(shù)為Ni和平均的空閑鄰近讀寫器個(gè)數(shù)為Vi，并假設(shè)每時(shí)隙平均有個(gè)讀寫器發(fā)送信標(biāo).顯然在時(shí)隙指令0時(shí)刻，N0＝N，V0＝V.由于每個(gè)讀寫器有N0－V0－1個(gè)讀寫器不在自己的干擾范圍內(nèi)，則時(shí)隙0讀寫器發(fā)送信標(biāo)且沒有受到鄰近讀寫器干擾的概率為

平均鄰近讀寫器為

對于第M個(gè)時(shí)隙指令，則有

可以看出在額外時(shí)隙有NM個(gè)讀寫器可以發(fā)送二次信標(biāo)，因此添加額外時(shí)隙可以使得那些沒有接收到忙信號和空閑的讀寫器有機(jī)會(huì)讀寫標(biāo)簽，進(jìn)一步提高系統(tǒng)的吞吐量以及公平性．

3 仿真結(jié)果分析

對提出的防沖突方法進(jìn)行仿真，并與傳統(tǒng)的PDCS，Colorwave和Pulse算法進(jìn)行比較．仿真參數(shù)設(shè)置：讀寫器的讀寫范圍為2m和干擾范圍8m［9］，讀寫器數(shù)量從10到50個(gè)或者500個(gè)，讀寫器部署范圍為40m×40m到100m×100m，根據(jù)文獻(xiàn)［10］，讀寫器在讀寫距離為2m的條件下在0．46s內(nèi)可以讀寫7個(gè)標(biāo)簽．PDCS和Colorwave算法中交互信號的時(shí)間為1ms［10］，因此時(shí)隙長分別為0．461s，0．462s．對于Pulse算法，信標(biāo)指令時(shí)間為5ms［8］．本文方法起始命令時(shí)間2．83ms，時(shí)隙指令時(shí)間為1ms，工作忙和信標(biāo)信號時(shí)間為0．3ms［10］．根據(jù)文獻(xiàn)［11］，Jain公平指數(shù)定義為

其中N為讀寫器數(shù)量和xi為第i個(gè)讀寫器的吞吐量，用于衡量各防沖突方法的公平性．

圖1給出了不同的防沖突方法對應(yīng)的吞吐量．吞吐量定義為RFID系統(tǒng)中所有讀寫器每秒鐘讀寫標(biāo)簽的總數(shù)，好的防沖突方法可以保證讀寫器讀寫更多的標(biāo)簽即高的吞吐量．PDCS算法仿真時(shí)采用最優(yōu)顏色數(shù)［3］，若不采用最優(yōu)顏色值，系統(tǒng)性能將下降，概率值取為0．7．由圖可知，本文的防沖突方法的吞吐量明顯優(yōu)于PDCS和Colorwave方法，并且逼近Pulse方法和理論值．

圖1 不同防沖突方法的吞吐量對比仿真

圖2為不同防沖突方法的Jain公平指數(shù)．Jain公平指數(shù)越高，說明該防沖突方法使得各讀寫器有更公平的機(jī)會(huì)讀寫標(biāo)簽．由圖可知，本文的防沖突方法的公平性指數(shù)明顯優(yōu)于Colorwave和Pulse方法，不過低于PDCS算法．PDCS算法的性能取決于初始配置值，若不采用最優(yōu)顏色值，系統(tǒng)公平性將下降．

圖2 不同防沖突方法的Jain公平指數(shù)對比仿真

圖3分析對比了不同利用率對應(yīng)讀寫概率的仿真和理論曲線．仿真情況分兩種：讀寫器個(gè)數(shù)N＝10和時(shí)隙數(shù)M＝14；N＝30和M＝32．由圖可知，越低利用率的讀寫器讀寫標(biāo)簽的概率越高，而越高利用率的讀寫器讀寫標(biāo)簽的概率就很低，保證了各讀寫器之間的公平性．

圖4分析對比了不同時(shí)隙下發(fā)送信標(biāo)讀寫器的個(gè)數(shù)的仿真和理論曲線．從圖中可以看出，隨著時(shí)隙增加，發(fā)送信標(biāo)的讀寫器在不斷減少，但在額外時(shí)隙，發(fā)送信標(biāo)的讀寫器明顯增加，說明有較多的讀寫器沒有接收到工作忙信號，可以發(fā)送二次信標(biāo)信號，因此增加額外時(shí)隙可提高系統(tǒng)的吞吐量.

圖3 讀寫概率仿真

圖4 發(fā)送信標(biāo)讀寫器的個(gè)數(shù)的仿真

4 結(jié) 束 語

本文提出了一種基于隨機(jī)時(shí)隙并通過讀寫器協(xié)調(diào)的讀寫器防沖突方法.該方法結(jié)合了分布式和集中式防沖突方法的優(yōu)缺點(diǎn)，中央計(jì)算機(jī)負(fù)責(zé)同步和協(xié)調(diào)各讀寫器時(shí)隙，讀寫器之間不需要同步，減少了讀寫器的負(fù)擔(dān)；讀寫器根據(jù)當(dāng)然利用率隨機(jī)選擇時(shí)隙，若讀寫器沒有接收到忙信號且沒收到鄰近讀寫器的信標(biāo)則在當(dāng)前時(shí)隙工作，否則可在額外時(shí)隙發(fā)送二次信標(biāo)，仿真結(jié)果表明該方法是可行的和可靠的.與現(xiàn)有的PDCS，Colorwave和Pulse算法相比較，本文提出的方法具有較好的吞吐量和公平性.

（

）

［1］Engels D W，Sarma S E.The reader collision problem［C］／／Proceedings of IEEE International Conference on Sysmtems Man and Cybernetics.Hammamet，Tunisia：IEEE ICSMC，2002：6－9

［2］Waldrop J，Engels D W，Sarma S E.Colorwave：an anticollision algortihm for the reader collision problem［C］／／Proceeding of 2003IEEE International Conference on Communication.Anchorage Alaska，USA：IEEE ICC，2003：1206－1210

［3］Waldrop J，Engels D W，Sarma S E.Colorwave：a MAC for RFID reader networks［C］／／Proceedings of IEEE Wireless Communic－ation and Networking Conference.New Orleans，Louisiana，USA：IEEE WCNC，2003：1701－1704

［4］Gandino F，F(xiàn)errero R，Montrucchio B.Probabilitic DCS：an RFID reader－to－reader anti－collision protocol［J］.Journal of Network Computing Applications，2011，34（3）：821－832

［5］Gandino F，F(xiàn)errero R，Montrucchio B.Introducing probability in RFID reader－to－reader anti－collsision［C］／／8th IEEE Internati－onal Symposium on Network Computing and Application.Cambridge，Massachusetts：IEEE ISNCA，2009：250－257

［6］ETSI EN 302 208.Electromagnetic ompatibility and radio spectrum matters［EB／OL］.Brussels：ETSI，2005［2008－6－8］.http：／／www.etsi.org

［7］EPCglobal.EPC radio－frequency identity protocols class－1 generation－2UHF RFID protocol for communications at 860MHz－960MHz［EB／OL］.Brussels：EPCglobal Inc，2005［2007－1－12］.http：／／www.epcglobalinc.org

［8］Birari S，Iyer S.Mitigating the reader collision problem in RFID networks with mobile readers［C］／／13th IEEE International Conference on Networks.Bombay，India：IEEE ICN，2005：463－468

［9］Eom J B，Yim S B，Lee T J.An efficient reader anticollision algorithm in dense RFID networks with mobile RFID readers［J］.IEEE Trans Ind Electron，2009，56（7）：2326－2336

［10］Buettner M，Werherall D.An empirical study of UHF RFID performance［C］／／Proceeding of ACM International Conference on Mobile Computing and Networking.New York，USA：ACM ICMCN，2008：223－234

［11］Renato Ferrero，F(xiàn)ilippo Gandino.A fair and high throughput reader－to reader anticollision protocol in dense RFID networks［J］.IEEE Transactions on Industrial Informatics，2011，99（1）：1－9