王永華，楊 健，詹宜巨，萬(wàn) 頻

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

RFID網(wǎng)絡(luò)中讀寫器沖突指由一個(gè)讀寫器檢測(cè)到的、由另一個(gè)讀寫器引起的干擾，包含兩種情況。讀寫器-讀寫器沖突頻率沖突和讀寫器-標(biāo)簽沖突[1]。讀寫器頻率沖突發(fā)生在兩個(gè)或兩個(gè)以上讀寫器同時(shí)使用相同的頻率與標(biāo)簽通信時(shí)；讀寫器-標(biāo)簽沖突是指兩個(gè)或更多讀寫器同時(shí)與一個(gè)標(biāo)簽通信時(shí)發(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ù)約方式，使讀寫器在異步方式時(shí)靈活、有效地在多個(gè)時(shí)段和頻段工作。

1 RCA協(xié)議

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

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

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

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

圖1 RTS幀和COL幀格式

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

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

1.1 讀寫器接入過(guò)程

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

圖2 讀寫器接入過(guò)程

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

2 協(xié)議模型

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

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

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

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

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

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

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

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

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

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

3 結(jié)果分析

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

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

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

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

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

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

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

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

3.4 與其他算法對(duì)比

圖6 輸出對(duì)比

4 結(jié) 論

為解決異步的分布式讀寫器網(wǎng)絡(luò)中的讀寫器沖突，本文提出了一種自適應(yīng)多信道讀寫器沖突避免多址接入?yún)f(xié)議。該協(xié)議為異步協(xié)議，基于預(yù)約和多信道思想，可以有效解決讀寫器沖突問(wèn)題。讀寫器和標(biāo)簽建立通信前先發(fā)送RTS，若無(wú)沖突狀態(tài)則選擇一個(gè)業(yè)務(wù)信道開(kāi)始與標(biāo)簽通信，否則進(jìn)行退避。該協(xié)議避免了相鄰讀寫器同時(shí)與標(biāo)簽通信，解決了讀寫器-標(biāo)簽干擾。同時(shí)，多個(gè)信道的通信機(jī)制以及頻率的可空分復(fù)用避免了讀寫器頻率干擾的發(fā)生。對(duì)該協(xié)議分析表明，在RTS數(shù)據(jù)長(zhǎng)度較短、讀寫器平均通信時(shí)間較長(zhǎng)、泊松參數(shù)λ較小時(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ú)線網(wǎng)絡(luò)環(huán)境下自適應(yīng)獲取沖突避免的多址接入?yún)f(xié)議[J]. 計(jì)算機(jī)學(xué)報(bào), 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ú)線網(wǎng)絡(luò)的多址接入?yún)f(xié)議及其性能分析[J]. 計(jì)算機(jī)學(xué)報(bào), 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.

編 輯 漆 蓉