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

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

0 引 言

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

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

1 CSMA/CD和截?cái)喽M(jìn)制指數(shù)退避算法

“載波偵聽多路訪問/沖突檢測(cè)(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)時(shí)，才可以被允許發(fā)送數(shù)據(jù)幀。此時(shí)，如果有兩個(gè)或兩個(gè)以上的站同時(shí)監(jiān)聽到介質(zhì)處于空閑狀態(tài)且發(fā)送幀時(shí)，則會(huì)產(chǎn)生數(shù)據(jù)沖突現(xiàn)象，那么發(fā)送的數(shù)據(jù)幀就變?yōu)橐粋€(gè)無效幀，發(fā)送失敗。如果檢測(cè)到站發(fā)生沖突，應(yīng)該立即停止發(fā)送，避免造成因傳送無效幀而使得介質(zhì)帶寬浪費(fèi)的現(xiàn)象。隨后延時(shí)一段時(shí)間，再重新爭(zhēng)用介質(zhì)，重新發(fā)送數(shù)據(jù)幀。這樣就會(huì)有效提高數(shù)據(jù)傳輸效率，從而大大減小失傳率。

算法流程如下：

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

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

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

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

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

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

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

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

2 ALOHA算法

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

2.1 純ALOHA算法

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

圖1 純ALOHA算法碰撞示意圖

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

(1)

其中，λ表示單位時(shí)間內(nèi)標(biāo)簽出現(xiàn)的次數(shù)；G=λt表示識(shí)別過程中的數(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時(shí)，識(shí)別效率達(dá)到18.4%，如圖2所示，識(shí)別效率相對(duì)較低。

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

2.2 時(shí)隙ALOHA算法

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

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

(4)

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

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

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

2.3 幀時(shí)隙ALOHA算法

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

(5)

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

(6)

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

(7)

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

(8)

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

(9)

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

(10)

對(duì)上式進(jìn)行微分計(jì)算可得：

(11)

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

(12)

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

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

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

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

Ntags=2.39*Ck

(13)

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

3 改進(jìn)新型混合算法

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

算法主要步驟為：

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

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

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

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

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

(6)反之加強(qiáng)信道干擾，提前結(jié)束碰撞，進(jìn)入TBEB進(jìn)行二次識(shí)別；

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

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

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

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

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

圖5 混合算法流程

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

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

5 結(jié)束語

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

此外，RFID新的防碰撞算法可能將會(huì)深入到RFID網(wǎng)絡(luò)物理層(頻率、信號(hào)調(diào)制和數(shù)據(jù)加密)和數(shù)據(jù)鏈路層的特性。在無線協(xié)同網(wǎng)絡(luò)層可以實(shí)現(xiàn)信息編碼，由此可以更好地實(shí)現(xiàn)分集性能，有效提高信息的傳輸速率，同時(shí)具有較低的硬件損耗。而在數(shù)據(jù)鏈路層中可以將數(shù)據(jù)信息自適應(yīng)組合，并調(diào)節(jié)發(fā)送速率使得與接收端相匹配，使得防碰撞算法結(jié)合計(jì)算機(jī)協(xié)議思想得到更好的改進(jìn)，充分提高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] 李 晶.一種改進(jìn)的RFID防碰撞時(shí)隙ALOHA算法[D].長春:吉林大學(xué),2009.

[3] 王 勇,李 婷.改進(jìn)的基于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-堅(jiān)持CSMA提高RFID系統(tǒng)吞吐率的改進(jìn)算法[J].計(jì)算機(jī)測(cè)量與控制,2013,21(12):3322-3324.

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

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

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

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

[14] 錢東昊,張 琨,張 磊.基于標(biāo)簽識(shí)別碼分組的防碰撞算法研究[J].計(jì)算機(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．