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

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

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

0 引 言

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

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

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

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

算法流程如下：

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

(2)進行信道監(jiān)聽。如處于空閑狀態(tài)，立即發(fā)送數(shù)據(jù)并返回(1)；

(3)若信道處于“忙”，繼續(xù)監(jiān)聽信道，直到信道處于空閑狀態(tài)時再次傳送數(shù)據(jù)。

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

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

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

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

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

2 ALOHA算法

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

2.1 純ALOHA算法

純ALOHA算法是最基本的防碰撞算法，當(dāng)多個標(biāo)簽進入讀寫器感應(yīng)范圍內(nèi)且在不同的時間內(nèi)發(fā)送數(shù)據(jù)包時，會發(fā)生如圖1所示的部分碰撞和完全碰撞。

圖1 純ALOHA算法碰撞示意圖

由于識別過程中，單位時間內(nèi)標(biāo)簽應(yīng)答數(shù)服從泊松分布，故在時間t內(nèi)隨機發(fā)送數(shù)據(jù)幀時，有n個標(biāo)簽應(yīng)答的概率為：

(1)

其中，λ表示單位時間內(nèi)標(biāo)簽出現(xiàn)的次數(shù)；G=λt表示識別過程中的數(shù)據(jù)包交換量。

那么在碰撞周期2T內(nèi)無其他標(biāo)簽應(yīng)答響應(yīng)的概率為：

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

(2)

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

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

(3)

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

圖2 純ALOHA算法數(shù)據(jù)交換量和

2.2 時隙ALOHA算法

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

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

(4)

其中，當(dāng)G=1時，識別效率達到36.8%。

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

圖3 兩種算法數(shù)據(jù)交換量與吞吐率的關(guān)系曲線

2.3 幀時隙ALOHA算法

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

(5)

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

(6)

當(dāng)m=1時，表示時隙中只有一個標(biāo)簽處于應(yīng)答狀態(tài)，則成功時隙數(shù)的期望值為：

(7)

當(dāng)m=0時，表示時隙處于空閑狀態(tài)，則空閑時隙數(shù)的期望值為：

(8)

當(dāng)m>1時發(fā)生碰撞，則發(fā)生碰撞時隙數(shù)的期望值為：

(9)

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

(10)

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

(11)

由式(11)可得，當(dāng)F=n時，即標(biāo)簽數(shù)等于幀長數(shù)，讀寫器的吞吐效率達到最優(yōu)。

(12)

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

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

圖4 時隙ALOHA標(biāo)簽數(shù)目與吞吐率的關(guān)系曲線

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

Ntags=2.39*Ck

(13)

其中，Ntags表示待估計標(biāo)簽的數(shù)目；Ck表示在一幀中發(fā)生碰撞的總時隙數(shù)。

3 改進新型混合算法

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

算法主要步驟為：

(1)判斷標(biāo)簽數(shù)目是否大于256，若大于256，標(biāo)簽進行預(yù)處理分組，否則執(zhí)行步驟(2)；

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

(3)經(jīng)過一輪查詢后，將統(tǒng)計成功識別的時隙數(shù)目記為ω；

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

(5)進行信道檢測，如果信道處于空閑狀態(tài)，立即發(fā)送標(biāo)簽；

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

(7)直到剩余標(biāo)簽通過CSMA/CD和TBEB完全識別，結(jié)束算法，否則執(zhí)行步驟(2)。經(jīng)過時隙ALOHA算法完成首次識別，剩余標(biāo)簽由CSMA/CD和TBEB聯(lián)合進行二次識別，標(biāo)簽即可在最短的時間內(nèi)完成識別。

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

4 仿真結(jié)果與分析

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

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

圖5 混合算法流程

圖6 兩種算法中標(biāo)簽數(shù)和吞吐率的關(guān)系曲線

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

5 結(jié)束語

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

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

[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].長春:吉林大學(xué),2009.

[3] 王 勇,李 婷.改進的基于ALOHA的RFID防碰撞算法[J].電信科學(xué),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系統(tǒng)吞吐率的改進算法[J].計算機測量與控制,2013,21(12):3322-3324.

[8] 馬 純,尹小燕,房鼎益,等.退避算法多負(fù)載狀況下的退避窗口最優(yōu)設(shè)定[J].計算機應(yīng)用研究,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動態(tài)自適應(yīng)CSMA/CA算法設(shè)計與仿真[J].計算機技術(shù)與發(fā)展,2010,20(9):69-73.

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

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

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

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

[15] 高金輝,鄭曉彥.新型的RFID混合防碰撞算法[J].電子技術(shù)應(yīng)用,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．