楊靈　劉磊安

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

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

DOIDOI：10.11907/rjdk.143877

中圖分類號：TP312

文獻標識碼：A文章編號文章編號：16727800（2015）002006602

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

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

0引言

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

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

1ALOHA算法

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

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

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

2ALOHA算法分析

為方便對動態(tài)幀時隙ALOHA算法效率進行分析，首先定義：

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

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

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

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

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

3誤差率分析

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

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

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