基于隨機時隙的RFID讀寫器防沖突方法

張光山 張 爍 張有光

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

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

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

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

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

1 多讀寫器防沖突方法

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

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

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

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

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

則讀寫器ri隨機選擇范圍內的時隙值，其中%為求模運算，其中■·」和「·■分別為下取整數和上取整數.

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

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

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

6）當周期時間到，所有讀寫器停止讀寫標簽，中央計算機根據當前網絡的拓撲結構和規(guī)模選擇新的時隙數并開始下一周期的操作.

2 性能分析

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

讀寫器ri在時隙mi若滿足以下兩個條件就可以讀寫標簽：

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

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

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

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

則

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

其中Q（V，r，mi）為1.則讀寫器ri在該時隙讀寫標簽的概率為

則讀寫器ri每輪回的讀寫標簽概率為

當l≠1和n≠1，讀寫器的讀寫概率不僅與鄰近讀寫器有關，還和利用率相關.設具有利用率為li的讀寫器ri有Vli個鄰近讀寫器，則讀寫器具有最低利用率li＝0時對應的讀寫概率為

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

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

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

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

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

平均鄰近讀寫器為

對于第M個時隙指令，則有

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

3 仿真結果分析

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

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

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

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

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

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

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

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

圖3 讀寫概率仿真

圖4 發(fā)送信標讀寫器的個數的仿真

4 結 束 語

本文提出了一種基于隨機時隙并通過讀寫器協(xié)調的讀寫器防沖突方法.該方法結合了分布式和集中式防沖突方法的優(yōu)缺點，中央計算機負責同步和協(xié)調各讀寫器時隙，讀寫器之間不需要同步，減少了讀寫器的負擔；讀寫器根據當然利用率隨機選擇時隙，若讀寫器沒有接收到忙信號且沒收到鄰近讀寫器的信標則在當前時隙工作，否則可在額外時隙發(fā)送二次信標，仿真結果表明該方法是可行的和可靠的.與現有的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，Ferrero 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，Ferrero 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，Filippo 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