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

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

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

1 RCA協(xié)議

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

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

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

網(wǎng)絡(luò)內(nèi)的讀寫器可以充分利用多個業(yè)務(wù)信道避免頻率干擾，此外業(yè)務(wù)信道的空分復(fù)用機(jī)制還大大提高了信道利用率。

圖1 RTS幀和COL幀格式

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

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

1.1 讀寫器接入過程

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

圖2 讀寫器接入過程

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

2 協(xié)議模型

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

定義相鄰性參數(shù)為：

發(fā)生RTS沖突的情況是當(dāng)一個讀寫器發(fā)送一個RTS后，在Y時間內(nèi)一個或者多個相鄰讀寫器也發(fā)送RTS，其中0

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

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

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

可得到成功發(fā)送RTS的概率為：

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

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

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

3 結(jié)果分析

3.1 RTS分組長度變化時的系統(tǒng)輸出

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

圖3 RTS分組長度變化時的系統(tǒng)輸出

3.2 通信時間變化時的系統(tǒng)輸出

圖4 通信時間變化時的系統(tǒng)輸出

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

3.3 相鄰讀寫器數(shù)量變化時的系統(tǒng)輸出

圖5 相鄰讀寫器數(shù)量變化時的系統(tǒng)輸出

3.4 與其他算法對比

圖6 輸出對比

4 結(jié) 論

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

[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] 劉凱, 李建東, 周亞建. 多跳分布式無線網(wǎng)絡(luò)環(huán)境下自適應(yīng)獲取沖突避免的多址接入?yún)f(xié)議[J]. 計算機(jī)學(xué)報, 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] 劉凱, 李建東, 張文柱. 一種用于多跳分布式無線網(wǎng)絡(luò)的多址接入?yún)f(xié)議及其性能分析[J]. 計算機(jī)學(xué)報, 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.

編 輯 漆 蓉