一種基于ALOHA的RFID標(biāo)簽多址接入算法

楊靈　劉磊安

摘要：多址接入問(wèn)題是多節(jié)點(diǎn)信號(hào)共享一個(gè)無(wú)線信道產(chǎn)生的信號(hào)沖突問(wèn)題，是RFID系統(tǒng)的主要問(wèn)題之一。目前，解決該問(wèn)題的方法有4個(gè)：空分多路法、頻分多路法、碼分多路法和時(shí)分多路法，而RFID系統(tǒng)中常用的TDMA算法是ALOHA算法。對(duì)ALOHA算法的過(guò)程及效率進(jìn)行了分析，在幀長(zhǎng)和標(biāo)簽數(shù)目相同的條件下，求出系統(tǒng)吞吐率最大值。在此基礎(chǔ)上提出一種標(biāo)簽估算算法，并對(duì)其估算誤差率進(jìn)行了分析。計(jì)算機(jī)仿真實(shí)驗(yàn)證明，隨著幀長(zhǎng)和標(biāo)簽數(shù)增加，該算法可以有效降低誤差率，解決RFID標(biāo)簽多址接入問(wèn)題。

關(guān)鍵詞關(guān)鍵詞：多址接入；RFID；ALOHA

DOIDOI：10.11907/rjdk.143877

中圖分類號(hào)：TP312

文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)文章編號(hào)：16727800（2015）002006602

基金項(xiàng)目基金項(xiàng)目：廣東省自然科學(xué)基金項(xiàng)目（S2012010010329）；廣東省科技攻關(guān)項(xiàng)目（2012B010100034）

作者簡(jiǎn)介作者簡(jiǎn)介：楊靈（1980-） ，男，江西崇仁人，碩士 ，仲愷農(nóng)業(yè)工程學(xué)院信息科學(xué)與技術(shù)學(xué)院副研究員，研究方向?yàn)镽FID、網(wǎng)絡(luò)安全、食品安全溯源；劉磊安（1979-） ，男，河南封丘人，博士，仲愷農(nóng)業(yè)工程學(xué)院信息科學(xué)與技術(shù)學(xué)院副教授，研究方向?yàn)镽FID、網(wǎng)絡(luò)安全。

0引言

由于RFID系統(tǒng)是通過(guò)射頻場(chǎng)來(lái)完成標(biāo)簽和閱讀器之間的信息交換，而射頻場(chǎng)屬于共享的無(wú)線廣播信道，因此必然涉及多址接入問(wèn)題[1]。在傳統(tǒng)的無(wú)線通信網(wǎng)絡(luò)中，由于有很多的節(jié)點(diǎn)共享一個(gè)無(wú)線信道，所以必須使用相應(yīng)的機(jī)制，才能使這些節(jié)點(diǎn)共用信道，避免相互之間的沖突，主要方法有：空分多路法（SDMA）、頻分多路法（FDMA）、碼分多路法（CDMA）和時(shí)分多路法（TDMA）。

空分多路法是指物理上多條線路共享一條線纜，但RFID系統(tǒng)是無(wú)線傳輸，天線系統(tǒng)設(shè)計(jì)比較復(fù)雜，實(shí)施成本高，且必須當(dāng)頻率大于1GHz以上才能使用，因此SDMA使用面比較窄；頻分多路法是指多條不同頻帶的信道共享一條載波帶寬的多路復(fù)用技術(shù)，該方案對(duì)RFID閱讀器要求較高，每條信道都必須有自己的接收器，因此使用較少；碼分多路法是一種既共享信道頻率又共享時(shí)間的多路復(fù)用技術(shù)，其將比特時(shí)間分成若干個(gè)碼片，每個(gè)不同頻帶的信道使用指定的碼片。該方案效率較高，主要在移動(dòng)互聯(lián)網(wǎng)使用，對(duì)終端設(shè)備要求高，但RFID標(biāo)簽結(jié)構(gòu)簡(jiǎn)單、功耗低，碼片捕獲時(shí)間和選擇時(shí)間較長(zhǎng)，不能滿足RFID對(duì)效率的要求；TDMA應(yīng)用簡(jiǎn)單，可以很好地解決多址接入問(wèn)題，是目前RFID系統(tǒng)中多址接入控制機(jī)制的主要方法。RFID系統(tǒng)中常用的TDMA算法是ALOHA算法。ALOHA算法是一種基于概率的算法，共分為3種：純ALOHA算法、時(shí)隙ALOHA算法和動(dòng)態(tài)時(shí)隙ALOHA算法。本文對(duì)3種ALOHA算法的過(guò)程及效率進(jìn)行了分析，在幀長(zhǎng)和標(biāo)簽數(shù)目相同的條件下，求出系統(tǒng)吞吐率最大值。在此基礎(chǔ)上提出一種標(biāo)簽估算算法，對(duì)估算誤差率進(jìn)行了分析。仿真實(shí)驗(yàn)證明，隨著幀長(zhǎng)和標(biāo)簽數(shù)增加，該方法可以有效降低誤差率，解決RFID標(biāo)簽多址接入問(wèn)題。

1ALOHA算法

純ALOHA算法是指標(biāo)簽進(jìn)入閱讀器范圍后，自主選擇發(fā)送數(shù)據(jù)時(shí)間[2]。閱讀器選擇一個(gè)標(biāo)簽與其通信，在通信的過(guò)程中，標(biāo)簽可以將閱讀器反饋的信息與緩存區(qū)中的數(shù)據(jù)進(jìn)行比較，若一致則表示發(fā)送成功，若不一致，則表示發(fā)生沖突，該標(biāo)簽停止發(fā)送數(shù)據(jù)，等待一段隨機(jī)時(shí)間后再次發(fā)送數(shù)據(jù)。同理，其它標(biāo)簽通信時(shí)也按照上述過(guò)程進(jìn)行，這樣標(biāo)簽就可以在發(fā)送過(guò)程中及時(shí)檢測(cè)是否發(fā)生沖突。由于在純ALOHA算法中，沖突檢測(cè)是由數(shù)據(jù)發(fā)送方負(fù)責(zé)，所以比較適合標(biāo)簽負(fù)責(zé)發(fā)送數(shù)據(jù)、閱讀器負(fù)責(zé)接收數(shù)據(jù)的情況。

幀時(shí)隙ALOHA算法是在純ALOHA算法的基礎(chǔ)上把時(shí)間離散分解成多個(gè)時(shí)間幀，一個(gè)標(biāo)簽在一個(gè)時(shí)間幀中只能發(fā)送數(shù)據(jù)一次。同時(shí)，將幀分解成若干個(gè)時(shí)隙，每個(gè)時(shí)隙的長(zhǎng)度要能夠完成一次數(shù)據(jù)傳輸，每個(gè)標(biāo)簽的傳輸必須在一個(gè)時(shí)隙內(nèi)完成，這樣每個(gè)標(biāo)簽的傳輸都局限在一個(gè)時(shí)隙中，避免了2個(gè)標(biāo)簽傳輸頭尾碰撞的概率，并盡量保證一個(gè)標(biāo)簽在一個(gè)數(shù)據(jù)幀中能夠完成一次通信。其缺點(diǎn)是當(dāng)標(biāo)簽數(shù)量很多時(shí)，數(shù)據(jù)幀設(shè)置必須要足夠長(zhǎng)，否則標(biāo)簽沖突情況會(huì)大幅增加，導(dǎo)致數(shù)據(jù)傳輸速率很慢。

標(biāo)簽到達(dá)數(shù)量是隨著時(shí)間的變化而變化的，因而幀時(shí)隙ALOHA算法中的數(shù)據(jù)幀長(zhǎng)度無(wú)法固定。動(dòng)態(tài)幀時(shí)隙ALOHA算法通過(guò)動(dòng)態(tài)調(diào)整數(shù)據(jù)幀的長(zhǎng)度來(lái)有效提高系統(tǒng)吞吐量。由于標(biāo)簽到達(dá)數(shù)目是按照泊松分布變化的，所以幀的時(shí)隙數(shù)也要相應(yīng)地變化，以減少時(shí)隙的浪費(fèi)。動(dòng)態(tài)幀時(shí)隙ALOHA算法基于TDMA算法，實(shí)現(xiàn)比較簡(jiǎn)單，并且能夠動(dòng)態(tài)調(diào)整幀的長(zhǎng)度，匹配標(biāo)簽數(shù)量變化，是目前RFID系統(tǒng)常用的防沖突算法。

2ALOHA算法分析

為方便對(duì)動(dòng)態(tài)幀時(shí)隙ALOHA算法效率進(jìn)行分析，首先定義：

S：T0時(shí)內(nèi)成功完成數(shù)據(jù)通信的平均標(biāo)簽數(shù)量，即成功傳輸?shù)目倲?shù)據(jù)率；λ： T0時(shí)間內(nèi)RFID標(biāo)簽到達(dá)的次數(shù)；Pe：成功完成數(shù)據(jù)通信的標(biāo)簽概率；n：到達(dá)讀寫器范圍的標(biāo)簽數(shù)量；l：標(biāo)簽數(shù)據(jù)幀的長(zhǎng)度；t：標(biāo)簽成功傳輸?shù)臄?shù)量。

由概率論可知，每秒發(fā)送數(shù)據(jù)幀的數(shù)量服從泊松分布，當(dāng)n趨于無(wú)窮，成功的概率P趨于零，且滿足np=λ時(shí)，泊松分布可由二項(xiàng)分布的極限得到。二項(xiàng)頻率函數(shù)是：P（t）=n！t?。╪-t）！pt（1-p）n-t（1）設(shè)np=λ，則：P（t）=n！t！（n-t）?。é薾）t（1-λn）n-tP（t）=λtt！n?。╪-t）！1nt（1-λn）n（1-λn）-t當(dāng)n→∞時(shí)，可得以下結(jié)論：λn→0n?。╪-t）！nt→1（1-λn）n→e-λ（1-λn）-t→1綜上可得：p（t）→λte-λt！（2）

這樣，在一個(gè)時(shí)隙內(nèi)沒(méi)有其它標(biāo)簽發(fā)送信息的概率為：Pe=e-λ因此，時(shí)隙ALOHA算法的吞吐率為：

S=λPe=λe-λ（3）

由圖1可知：當(dāng)nl，即λ>1時(shí)，則碰撞時(shí)隙的數(shù)目會(huì)逐漸增加，成功傳輸?shù)臅r(shí)隙逐漸減少，導(dǎo)致標(biāo)簽有效傳輸概率減少，標(biāo)簽讀取時(shí)間增加；當(dāng)n=l，即λ=1時(shí)，標(biāo)簽成功傳輸?shù)母怕剩赐掏侣剩┻_(dá)到最大，其值為0.368；根據(jù)公式[35]可得到吞吐率S與總數(shù)據(jù)率λ的關(guān)系如圖1所示，時(shí)隙數(shù)、標(biāo)簽及吞吐率之間的關(guān)系如圖2所示。

3誤差率分析

為了標(biāo)簽可以比較均衡地在幀中不同時(shí)隙發(fā)送數(shù)據(jù)，我們根據(jù)標(biāo)簽ID的唯一性，在ALOHA算法中使用了標(biāo)簽ID作為內(nèi)部偽隨機(jī)數(shù)發(fā)生器的輸入，將內(nèi)部偽隨機(jī)數(shù)發(fā)生器的輸出作為選擇標(biāo)簽發(fā)送的時(shí)隙，這樣，就可以比較均衡地選擇不同的時(shí)隙，降低誤差率。誤差率分析如下：由于n'=n-n（1-1l）n-t， 則誤差率

Std（|（n′-n）/n|）=nt（1-1l）n-t（1l）t（4）

從上述公式可以看出，標(biāo)簽數(shù)一定，誤差率與幀長(zhǎng)成反比，若要減少誤差率就必須增加幀長(zhǎng)。