RFID網絡讀寫器沖突避免MAC協議

王永華，楊 健，詹宜巨，萬 頻

(1. 廣東工業大學自動化學院 廣州 510006；2. 中山大學工學院 廣州 510006)

RFID網絡中讀寫器沖突指由一個讀寫器檢測到的、由另一個讀寫器引起的干擾，包含兩種情況。讀寫器-讀寫器沖突頻率沖突和讀寫器-標簽沖突[1]。讀寫器頻率沖突發生在兩個或兩個以上讀寫器同時使用相同的頻率與標簽通信時；讀寫器-標簽沖突是指兩個或更多讀寫器同時與一個標簽通信時發生的沖突。目前解決讀寫器沖突的方法主要有EPC CLASS-1 Gen-2標準[2]、ETSI EN 302 208標準[3]、PULSE[4]、Colorwave算法[5]、DiCa算法[6]等，但均未徹底避免讀寫器沖突。為了解決RFID網絡中的讀寫器沖突，本文在參考自組織網絡中的多址接入協議[7-9]基礎上提出了一種RFID系統中自適應多信道讀寫器沖突避免MAC(RCA)協議。其主要思想為：讀寫器選取各自業務信道并向其他讀寫器聲明該結果，而不是等待其他讀寫器給它分配業務信道，采用資源預約方式，使讀寫器在異步方式時靈活、有效地在多個時段和頻段工作。

1 RCA協議

假定系統中各讀寫器均有一個互不相同的ID號，分別為1，2，，N，其中，N為系統中的讀寫器總數。將可用的頻率資源等分成2M－1份，其中的一個頻率作為控制信道，用于各讀寫器發送預約分組，從而完成它的信道獲取和通信接入過程，其余2M個信道作為業務信道。讀寫器用其中的偶數信道，標簽用相應的奇數信道通信。假定讀寫器的控制信道的通信距離大于數據信道的2倍，可以有效避免RFID網絡中的隱藏終端問題[6]。

鄰讀寫器指2個讀寫器有覆蓋區域重疊并且能相互通信。在RCA協議中，所有讀寫器共用控制信道，并且每個讀寫器用一個信道使用表記錄業務信道的狀態(忙閑)和必要的參數。假設讀寫器能夠通過控制信道交換控制信息，逐個發現自己的鄰居讀寫器并建立連接，每個讀寫器維護一個鄰居讀寫器表和非相鄰讀寫器列表。

鄰居讀寫器表內記錄與該讀寫器能發生沖突的相鄰讀寫器，非相鄰讀寫器表則記錄不會與其發生沖突的讀寫器。每個讀寫器預先監測記錄鄰居讀寫器的通信及信道使用情況，從而自適應地為自己選擇發送數據的信道及時刻，并且利用在控制信道上發送的RTS數據通知其他讀寫器，從而實現無沖突的通信。

網絡內的讀寫器可以充分利用多個業務信道避免頻率干擾，此外業務信道的空分復用機制還大大提高了信道利用率。

圖1 RTS幀和COL幀格式

RTS和COL幀格式如圖1所示。其中，讀寫器編號指發送信息的讀寫器編號。

RAC協議的優點是只有控制信息才有可能發生碰撞，請求通信的讀寫器一旦成功發送了RTS，并且未出現碰撞，則開始與標簽通信，之后它將不會干擾其他讀寫器或被其他讀寫器所打斷。

1.1 讀寫器接入過程

當一個讀寫器需要與標簽通信時，它監測控制信道，并在控制信道空閑一段時間后準備接入信道。為了避免多個讀寫器的分組碰撞，讀寫器還會按照某種退避算法再隨機延遲一段時間，若控制信道仍然空閑，此時該讀寫器發送RTS請求，通知相鄰讀寫器將使用的信道，并繼續偵聽控制信道一段時間(為一個往返時間+其他讀寫器發送COL信號所需的時間)。在沒有RTS沖突，并且未收到COL信號的情況下，讀寫器進入與標簽通信狀態，然后相鄰讀寫器進入延遲狀態并監測控制信道。如果有沖突或相鄰讀寫器處于通信狀態, 則會收到相鄰讀寫器發送的沖突信號，并立即隨機延遲，嘗試選擇其他未用信道并廣播，直至沒有沖突發生為止，如圖2所示。

圖2 讀寫器接入過程

最后，各讀寫器交換并存儲整個系統內讀寫器信道使用情況表。讀寫器的移動可能導致占用相同發送信道的兩個讀寫器變成相鄰，其公共鄰讀寫器或它們本身會通過監測控制信道發現這種情況，先發現者告知ID號更大的讀寫器延遲，然后重新接入。在這期間兩個讀寫器的數據通信有可能造成沖突，但是從上述過程中可以看出，這段時間非常短暫。

2 協議模型

設RTS的發送時間為 ，讀寫器與標簽的通信時間的平均長度為δ>1，γ<δ<∞；信道上的傳播時延為 ，τ<γ。各讀寫器通信需求符合參數為 的泊松過程。定義系統輸出S為讀寫器利用率。

定義相鄰性參數為：

發生RTS沖突的情況是當一個讀寫器發送一個RTS后，在Y時間內一個或者多個相鄰讀寫器也發送RTS，其中0

由于算法中的讀寫器在成功發送RTS后可以保證無沖突通信。由圖2可知成功發送期時間長度為：

另一種發送失敗的情況是有鄰居讀寫器在通信，此時一個讀寫器發送RTS后，將收到COL信號。所以發送失敗期2的時間長度為：

考慮讀寫器i在時刻t開始與標簽通信，首先發送RTS，易知成功發送RTS的條件為：1) 與讀寫器i相鄰的讀寫器均處于未通信狀態。2) 讀寫器i相鄰的讀寫器在持續 時間內都不在公共信道上發送RTS。因為讀寫器i發出RTS信息經傳播時延τ后，其他讀寫器也會收到該RTS信息，此時即使有通信需求也不再發送RTS，而是選擇退避。3) 讀寫器有空閑的業務信道可選擇，即不會與相鄰的讀寫器信道沖突。由于該協議中，相鄰讀寫器不能同時通信，所以讀寫器有空閑信道可選擇的概率為1。

可得到成功發送RTS的概率為：

讀寫器處于忙的狀態為兩種情況：一種是成功與標簽通信，另一種是發送RTS失敗。所以平均忙碌期為：

有效的讀寫器利用是指讀寫器成功與標簽通信的時間，即:

協議中，讀寫器在成功通信完畢后或者發送RTS失敗后均需要退避。在成功通信后，等待時間是γ，發送RTS失敗后等待時間是2。所以平均空閑期為：

3 結果分析

3.1 RTS分組長度變化時的系統輸出

圖3給出了每個讀寫器均有5個相鄰讀寫器，讀寫器與標簽的通信時間平均長度δ=1.5，給定不同的RTS分組時間長度γ時，系統輸出S隨泊松參數的變化情況。從圖中可以看出，隨著RTS分組時間長度γ的增大，協議的輸出將會減少。這是由于RTS分組時間長度γ的增大會使讀寫器接入時間增加，進而導致系統輸出S減少。

圖3 RTS分組長度變化時的系統輸出

3.2 通信時間變化時的系統輸出

圖4 通信時間變化時的系統輸出

在每個讀寫器周圍均有5個相鄰讀寫器、RTS分組時間長度γ=0.1的情況下，給定不同的讀寫器與標簽的通信時間γ時，系統輸出S隨泊松參數γ的變化情況如圖4所示。隨著讀寫器與標簽的平均通信時間δ的增大，系統輸出S將會增大，這是因為讀寫器在成功接入后可以保證無沖突的通信，減少由沖突引起的系統開銷，增加讀寫器的利用率。

3.3 相鄰讀寫器數量變化時的系統輸出

圖5 相鄰讀寫器數量變化時的系統輸出

3.4 與其他算法對比

圖6 輸出對比

4 結 論

為解決異步的分布式讀寫器網絡中的讀寫器沖突，本文提出了一種自適應多信道讀寫器沖突避免多址接入協議。該協議為異步協議，基于預約和多信道思想，可以有效解決讀寫器沖突問題。讀寫器和標簽建立通信前先發送RTS，若無沖突狀態則選擇一個業務信道開始與標簽通信，否則進行退避。該協議避免了相鄰讀寫器同時與標簽通信，解決了讀寫器-標簽干擾。同時，多個信道的通信機制以及頻率的可空分復用避免了讀寫器頻率干擾的發生。對該協議分析表明，在RTS數據長度較短、讀寫器平均通信時間較長、泊松參數λ較小時，讀寫器利用率較高。

[1] ENGELS D W, SARMA S E. The reader collision problem[C]//Proceedings of IEEE International Conference on Systems, Man and Cybernetics. Hammamet, Tunisia:IEEE, 2002: 6-9.

[2] EPCGlobal. EPC radio-frequency identity protocols class-1 generation-2 UHF RFID protocol for communications at 860-960 MHz version 1.0.9[EB/OL]. [2005-03-10].http://www.epcglobalinc.org/Standards.2005.

[3] ETSI. ETSI EN 302 208-1 V1.1.1[EB/OL]. [2004-05-22].http://www.esti.org.2004.

[4] BIRARI S M, IYER S. PULSE: a MAC protocol for RFID networks[C]//1st International Workshop on RFID and Ubiquitous Sensor Networks (USN). Nagasaki, Japan: [s.n.],2005: 1036-1046.

[5] WALDROP J, ENGELS D W, SARMA S E. Colorwave: an anti-collision algorithm for the reader collision problem[C]//IEEE Wireless Communications and Networking Conference (WCNC). New Orleans, Louisiana,USA: IEEE, 2003: 1701-1704.

[6] HWANG K, KIM K, EOM D. DiCa: Distributed tag access w ith collision-avoidance among mobile RFID readers[C]//Conferenceon: Embedded and Ubiquitous Computing– EUC.[S.l.]: IEEE, 2006: 413-422.

[7] 劉凱, 李建東, 周亞建. 多跳分布式無線網絡環境下自適應獲取沖突避免的多址接入協議[J]. 計算機學報, 2002,25(10): 1046-1051.

LIU Kai, LI Jian-dong, ZHOU Ya-jian. Multiple access protocol for adaptive acquisition collision avoidance in multihop w ireless Ad hoc networks[J]. Chinese Journal of Computers, 2002, 25(10): 1046-1051.

[8] 劉凱, 李建東, 張文柱. 一種用于多跳分布式無線網絡的多址接入協議及其性能分析[J]. 計算機學報, 2003, 26(8):925-933.

LIU Kai, LI Jian-dong, ZHANG Wen-zhu. A novel multiple access protocol for multihop w ireless Ad hoc networks[J].Chinese Journal of Computers, 2003, 26(8): 925-933.

編 輯 漆 蓉