基于CSMA/CD改進的混合RFID防碰撞算法

姜志峰，云中華，朱利娟，陳夫桂

(西藏大學，西藏 拉薩 850012)

0 引 言

計算機通信除了傳送數據外，它還進行數據交換、實時監測和數據處理等。但主要是以數據傳輸為基礎，并與計算機相關技術緊密聯系。而“射頻識別技術”(radio frequency identification,RFID)是一種依賴于計算機技術的非接觸式自動識別以及讀取相關數據的技術，主要通過無線電信號識別特定目標并讀寫相關數據。它具有耐高溫、使用壽命久、讀寫性能優越、存儲數據容量大和存儲信息易更改等優點。RFID系統主要由三部分組成：電子標簽、讀寫器和系統高層。其中讀寫器不僅要對電子標簽做出應答響應，還要實時處理數據信息。數據處理主要由系統高層解決，也就是計算機網絡系統。讀寫器通過標準接口與計算機網絡連接，再由計算機網絡完成數據處理、傳輸和通信的功能。

RFID系統廣泛應用在眾多領域，如家禽養殖業、加工零售業和交通運輸業等[1]。但在實際應用中，當多個電子標簽同時響應讀寫器的應答命令時，它們之間建立的共享信道可能會發生沖突即標簽碰撞，形成無效傳輸。若碰撞次數過多，會大大降低信道的利用率，而且影響RFID系統整體的工作效率。目前解決標簽碰撞的算法有二進制確定性算法、ALOHA概率性算法和它們的混合改進算法[2-5]。文獻[4]中列舉了基本的防碰撞協議，而文中基于數據鏈路層中的TBEB和CSMA/CD[6]協議提出了一種改進算法，提高了首次未識別標簽被成功識別的概率。

1 CSMA/CD和截斷二進制指數退避算法

“載波偵聽多路訪問/沖突檢測(carrier sense multiple access/collision detection，CSMA/CD)”協議[7-9]是一種分布式介質訪問控制協議。CSMA/CD應用在OS17層里的數據鏈路層，基本工作原理：在發送數據包之前監聽共享信道是否處于空閑狀態，只有介質處于空閑狀態時，才可以被允許發送數據幀。此時，如果有兩個或兩個以上的站同時監聽到介質處于空閑狀態且發送幀時，則會產生數據沖突現象，那么發送的數據幀就變為一個無效幀，發送失敗。如果檢測到站發生沖突，應該立即停止發送，避免造成因傳送無效幀而使得介質帶寬浪費的現象。隨后延時一段時間，再重新爭用介質，重新發送數據幀。這樣就會有效提高數據傳輸效率，從而大大減小失傳率。

算法流程如下：

(1)待傳送幀排隊等待；

(2)進行信道監聽。如處于空閑狀態，立即發送數據并返回(1)；

(3)若信道處于“忙”，繼續監聽信道，直到信道處于空閑狀態時再次傳送數據。

把上述協議應用在RFID標簽通信中時，需增加發射干擾信號的硬件裝置，也就是產生脈沖信號等。以便在監聽階段，同時監聽到多個標簽時，可以發射干擾信號，強化標簽碰撞，有效縮短標簽排隊等待被識別的時間。完成上述識別過程后，仍會有部分標簽無法成功識別，這時不再發送數據包，而是將標簽隨機退避一個時間段來降低二次重傳時發生沖突的概率，即“截斷二進制指數退避算法(truncated binary exponential backoff，TBEB)”[10-13]。二次重傳時間由TBEB算法來確定，算法流程如下：

(1)碰撞發生后，退避時間規定為2σ。

(2)從整數集[0,1,…,(2k-1)]中隨機選取一個整數作為退避時間，記為r，后續重傳時間是r的倍數。其中k=min[b,10]，b為重傳次數，重傳次數不超過10。例如，第二次重傳時，k=2,隨機數r從整數[0,1,2]中選擇一個，其重傳時間為從0,2σ,4σ和6σ中隨機選擇一個。

(3)當重傳次數達到16次時，發送仍無法成功識別，則放棄。

上述協議在有線以太網中應用廣泛，具有較強的穩定性和可靠性。可以把上述協議的思想借鑒于射頻識別技術，只是需要在硬件電路中增加額外的硬件裝置來產生電子標簽碰撞的干擾信號，這樣就可以有效縮短標簽排隊等待所消耗的時間。

2 ALOHA算法

ALOHA是在“時分多址(time division multiple access,TDMA)”的基礎上衍生出來的，用于解決標簽識別中多標簽碰撞問題的算法。改進算法包括純ALOHA算法、時隙ALOHA算法、幀時隙ALOHA算法和動態幀時隙ALOHA算法等[14-15]，它們在識別時間和識別效率上都有提升。

2.1 純ALOHA算法

純ALOHA算法是最基本的防碰撞算法，當多個標簽進入讀寫器感應范圍內且在不同的時間內發送數據包時，會發生如圖1所示的部分碰撞和完全碰撞。

圖1 純ALOHA算法碰撞示意圖

由于識別過程中，單位時間內標簽應答數服從泊松分布，故在時間t內隨機發送數據幀時，有n個標簽應答的概率為：

(1)

其中，λ表示單位時間內標簽出現的次數；G=λt表示識別過程中的數據包交換量。

那么在碰撞周期2T內無其他標簽應答響應的概率為：

p(n=0)|t=2T=e-2G

(2)

由式(2)可得純ALOHA算法的吞吐率為：

S=G·[p(n=0)|t=2T]=G·e-2G

(3)

當G=0.5時，識別效率達到18.4%，如圖2所示，識別效率相對較低。

圖2 純ALOHA算法數據交換量和

2.2 時隙ALOHA算法

時隙ALOHA算法在純ALOHA算法的基礎上把時間長度劃分為離散的時隙間隔，而碰撞周期縮短為T，這樣每個時隙間隔中將會出現碰撞、成功識別和空閑三種情況。由式(2)可得，時隙ALOHA算法的吞吐率為：

S=G·[p(n=0)|t=T]=G·e-G

(4)

其中，當G=1時，識別效率達到36.8%。

圖3為兩種算法平均數據包交換量與吞吐率的變化曲線，相對于純ALOHA算法的識別效率(18.4%)有明顯提高，但需要時鐘同步且對時隙長度的劃分更加精細。

圖3 兩種算法數據交換量與吞吐率的關系曲線

2.3 幀時隙ALOHA算法

在時隙ALOHA算法的基礎上，把多個時隙劃分組合成一幀，每一幀中隨機接受標簽發送的數據包即幀時隙ALOHA算法。假設時隙ALOHA算法中幀長數目和標簽的數目分別為F和n，由于一個標簽占用某個時隙的概率服從二項分布，那么m個標簽選擇同一個時隙的概率為：

(5)

由式(5)可得，一幀中分布有m個標簽的時隙數的期望值為：

(6)

當m=1時，表示時隙中只有一個標簽處于應答狀態，則成功時隙數的期望值為：

(7)

當m=0時，表示時隙處于空閑狀態，則空閑時隙數的期望值為：

(8)

當m>1時發生碰撞，則發生碰撞時隙數的期望值為：

(9)

由式(7)可得成功識別的概率為：

(10)

對上式進行微分計算可得：

(11)

由式(11)可得，當F=n時，即標簽數等于幀長數，讀寫器的吞吐效率達到最優。

(12)

由式(12)可知，幀時隙ALOHA算法的識別效率達到36.8%。

圖4為不同幀長下對應的標簽數目與吞吐率的關系曲線，五條曲線分別對應的幀長數為256、128、64、32和16，其中曲線的最高點均是在標簽數量和幀長數目近似相等的條件下達到的。此時，系統的識別效率達到最佳。

圖4 時隙ALOHA標簽數目與吞吐率的關系曲線

要使RFID系統的識別效率達到最大，幀長度必須和等待被識別的標簽數目近似相等。各種改進算法中對標簽數目的估計提出了一些有效的改進措施，文獻[16-17]中介紹了一種估計標簽數的方法，可以比較準確地估計出標簽數目。近似估計標簽數目的表達式如下所示：

Ntags=2.39*Ck

(13)

其中，Ntags表示待估計標簽的數目；Ck表示在一幀中發生碰撞的總時隙數。

3 改進新型混合算法

改進的混合算法中首先判斷標簽數目是否大于256，若大于256，則需要對標簽數進行分組處理，使得標簽數量和幀長數近似相等，達到系統可識別的最大識別度。然后通過時隙ALOHA算法完成首次識別，減少電子標簽發生沖突的次數。此時，仍有不確定數量的未成功識別標簽。通過載波監聽/沖突檢測機制，即邊發送邊監聽信道來縮短碰撞時間，使電子標簽有充足的退避時間，更合理地執行截斷二進制指數退避算法，循環上述過程直到所有標簽被識別。

算法主要步驟為：

(1)判斷標簽數目是否大于256，若大于256，標簽進行預處理分組，否則執行步驟(2)；

(2)標簽開始向讀寫器發送消息，進行識別，稱之為多路存取，完成首次識別；

(3)經過一輪查詢后，將統計成功識別的時隙數目記為ω；

(4)根據ω/F≥ε(0.5<ε<1)進行判斷，如果ε介于0.5和1之間，說明成功識別的標簽數目較多，此時執行截斷二進制指數退避算法進行二次識別，否則執行步驟(5)；

(5)進行信道檢測，如果信道處于空閑狀態，立即發送標簽；

(6)反之加強信道干擾，提前結束碰撞，進入TBEB進行二次識別；

(7)直到剩余標簽通過CSMA/CD和TBEB完全識別，結束算法，否則執行步驟(2)。經過時隙ALOHA算法完成首次識別，剩余標簽由CSMA/CD和TBEB聯合進行二次識別，標簽即可在最短的時間內完成識別。

混合算法流程圖如圖5所示。

4 仿真結果與分析

改進的混合RFID防碰撞算法中，首先判斷標簽的數目，在標簽數目小于指定數量時，通過時隙ALOHA算法完成首次識別，否則進行分組處理。之后未識別的標簽通過載波監聽/沖突檢測機制來增強碰撞干擾，縮短碰撞時間。在載波監聽/沖突檢測和截斷二進制指數退避作用下大大縮短了碰撞時間。

圖6為改進混合算法和時隙ALOHA算法的標簽數和吞吐率的性能比較，在最大分組幀長數256處對應的標簽數大約為256，即就是標簽數和幀長數相等，重傳效率達到39.1%，相比時隙ALOHA算法的吞吐率(36.8%)有所改進。

圖5 混合算法流程

圖6 兩種算法中標簽數和吞吐率的關系曲線

時隙ALOHA算法中只是對未識別頑固標簽進行重復識別。改進算法的初始階段,由時隙ALOHA算法完成，在后續識別階段，改進算法在載波監聽/沖突檢測和截斷二進制指數退避算法的作用下降低了重傳次數。同時，當兩種算法處于相同的吞吐率情況下，改進算法所需的識別時間明顯小于時隙ALOHA算法的識別時間。

5 結束語

在時隙ALOHA算法的思想上，結合載波監聽/沖突檢測和截斷二進制指數退避算法機制，提出了一種基于CSMA/CD的混合RFID防碰撞算法，引入二次重傳機制。相比時隙ALOHA算法，標簽信息吞吐率較高。后續可以根據標簽數目變化動態地改變幀長，進一步縮短截斷二進制指數退避時所消耗的時間。

此外，RFID新的防碰撞算法可能將會深入到RFID網絡物理層(頻率、信號調制和數據加密)和數據鏈路層的特性。在無線協同網絡層可以實現信息編碼，由此可以更好地實現分集性能，有效提高信息的傳輸速率，同時具有較低的硬件損耗。而在數據鏈路層中可以將數據信息自適應組合，并調節發送速率使得與接收端相匹配，使得防碰撞算法結合計算機協議思想得到更好的改進，充分提高RFID系統的工作效率。

[1] ULLAH S,ALSALIH W,ALSEHAIM A,et al.A review of tags anti-collision and localization protocols in RFID newworks[J].Journal of Medical Systems,2012,36(6):4037-4050.

[2] 李 晶.一種改進的RFID防碰撞時隙ALOHA算法[D].長春:吉林大學,2009.

[3] 王 勇,李 婷.改進的基于ALOHA的RFID防碰撞算法[J].電信科學,2016,32(8):77-81.

[4] DEMIRKOL I,ERSOY C,ALAGOZ F.MAC protocols for wireless sensor networks[J].IEEE Communications Magazine,2006,44(4):115-121.

[5] KLAIR D K,CHIN K W,RAAD R.A survey and tutorial of RFID anti-collision protocols[J].IEEE Communication Surveys and Tutorials,2010,12(3):400-421.

[6] GALLAGER R G. A perspective on multiaccess channels[J].IEEE Transactions on Information Theory,1985,31(2):124-142.

[7] 李寶山,喬 聰.基于P-堅持CSMA提高RFID系統吞吐率的改進算法[J].計算機測量與控制,2013,21(12):3322-3324.

[8] 馬 純,尹小燕,房鼎益,等.退避算法多負載狀況下的退避窗口最優設定[J].計算機應用研究,2015,32(1):175-178.

[9] CHEN Xiaoming,HONG Geok-Soon.A simuliation study of the predictive p-persistent CSMA protocol[C]//Proceedings of the35th annual simulation symposium.Washington,DC,USA:IEEE Computer Society,2002.

[10] 蔣子峰,陸建德.IEEE802.15.4動態自適應CSMA/CA算法設計與仿真[J].計算機技術與發展,2010,20(9):69-73.

[11] 黃 仁,郜 輝,任軍華.非時隙CSMA/CA性能分析與研究[J].計算機工程與應用,2009,45(7):108-110.

[12] 何 偉,南敬昌,潘 峰.改進的動態p-堅持CSMA協議[J].計算機工程,2010,36(21):118-120.

[13] 蘇恒陽,譚英麗.改進的RFID動態幀時隙ALOHA算法[J].計算機仿真,2011,28(8):148-152.

[14] 錢東昊,張 琨,張 磊.基于標簽識別碼分組的防碰撞算法研究[J].計算機應用與軟件,2015,32(7):252-254.

[15] 高金輝,鄭曉彥.新型的RFID混合防碰撞算法[J].電子技術應用,2011,37(12):130-132.

[16] SCHOUTE F C．Dynamic frame length ALOHA[J]．IEEE Transactions on Communication，1983，31:565-568．

[17] CHA J Y，KIM J Y．Novel anti-collision algorithms for fast object identification in RFID system[C]//Proceedings of the11th international conference on parallel and distributed systems．Washington,DC,USA:IEEE Computer Society,2005:604-609．