趙曉霞, 昂志敏, 郭 治

(合肥工業(yè)大學(xué)計(jì)算機(jī)與信息學(xué)院,安徽合肥 230009)

無(wú)線射頻技術(shù)(radio frequency identification,簡(jiǎn)稱RFID)因具有識(shí)別距離遠(yuǎn)、穿透力強(qiáng)、多物體識(shí)別及抗污染等優(yōu)點(diǎn),近年來(lái)得到不斷的發(fā)展和進(jìn)步,現(xiàn)已廣泛應(yīng)用于工業(yè)自動(dòng)化、商業(yè)自動(dòng)化、交通運(yùn)輸控制管理、門禁保安及防盜等眾多領(lǐng)域,成為當(dāng)前IT行業(yè)研究的熱點(diǎn)技術(shù)之一。

射頻識(shí)別系統(tǒng)一般由閱讀器(Reader)、標(biāo)簽(Tag)和后端數(shù)字處理系統(tǒng)構(gòu)成。因?yàn)樗械臉?biāo)簽工作在同一個(gè)頻率,當(dāng)有多個(gè)標(biāo)簽同時(shí)回復(fù)閱讀器時(shí)就會(huì)發(fā)生數(shù)據(jù)碰撞,造成數(shù)據(jù)傳輸錯(cuò)誤,因此需要制定相應(yīng)的防碰撞算法來(lái)解決沖突問(wèn)題。目前用于解決沖突問(wèn)題算法的多址技術(shù)都是基于時(shí)分多址(TDMA)的,其中包括二進(jìn)制樹算法和ALOHA算法,以及對(duì)這2種算法的改進(jìn)算法,但還是不能很好地解決大量標(biāo)簽存在時(shí)產(chǎn)生的沖突問(wèn)題。

基于以上原因,本文提出了一種基于碼分多址技術(shù)(CDMA)的二維時(shí)隙 ALO(C-S-ALOHA)[1]的防碰撞算法,并采用m序列作為擴(kuò)頻碼。作為一種二維算法,它有效地改善了多標(biāo)簽的沖突問(wèn)題,提高了吞吐量。文中還給出了數(shù)學(xué)分析和仿真結(jié)果。

1 C-S-ALOHA算法描述

1.1 CDMA技術(shù)

CDMA技術(shù)是通過(guò)不同的擴(kuò)頻序列碼來(lái)識(shí)別不同的用戶,即各用戶可以在同一工作頻段選用不同擴(kuò)頻碼來(lái)發(fā)送信息而互不干擾。具有抗干擾性好、帶寬動(dòng)態(tài)分配、保密性和可擴(kuò)展性好等優(yōu)點(diǎn)。其中,擴(kuò)頻序列碼是CDMA技術(shù)的關(guān)鍵,常用的擴(kuò)頻碼有m序列、gold序列和walsh碼等,其中m序列是擴(kuò)頻系統(tǒng)中應(yīng)用最廣的擴(kuò)頻碼,具有編碼簡(jiǎn)單、易于產(chǎn)生的優(yōu)點(diǎn)。

文獻(xiàn)[2,3]選用的walsh碼作為RFID系統(tǒng)中的擴(kuò)頻碼,但當(dāng)擴(kuò)頻碼長(zhǎng)較大時(shí),若選用walsh序列,會(huì)有較長(zhǎng)的連0連1,這對(duì)系統(tǒng)的位同步是不利的。正交擴(kuò)頻系統(tǒng)若采用特性優(yōu)良的m序列做擴(kuò)頻碼,不但編碼簡(jiǎn)單,而且可以增加系統(tǒng)抗突發(fā)錯(cuò)誤的能力,日益受到業(yè)界的推崇,因此本文選用了m序列。

m序列(又稱最大長(zhǎng)度線性移位寄存器序列)具有良好的偽隨機(jī)特性,常用作擴(kuò)頻通信系統(tǒng)的擴(kuò)頻碼字,由于生成多項(xiàng)式相同的不同m序列是彼此正交的,具有處處約為0的互相關(guān)特性和尖銳的自相關(guān)特性,故亦可構(gòu)成正交碼擴(kuò)頻系統(tǒng)中的正交碼集。

m序列的產(chǎn)生方法：n級(jí)線性移位寄存器,經(jīng)過(guò)適當(dāng)?shù)某轭^反饋和模2加法器,能產(chǎn)生序列的最大可能周期是p=2n-1的序列[4]。

1.2 S-ALOHA技術(shù)

時(shí)隙ALOHA算法[5]是在ALOHA算法的基礎(chǔ)上把時(shí)間分成多個(gè)離散時(shí)隙,每個(gè)時(shí)隙長(zhǎng)度T等于標(biāo)簽的數(shù)據(jù)幀長(zhǎng)度,標(biāo)簽只能在每個(gè)時(shí)隙的分界處才能發(fā)送數(shù)據(jù)。每個(gè)時(shí)隙存在以下3種情況：

多機(jī)器人協(xié)同系統(tǒng)在汽車焊接生產(chǎn)線中的應(yīng) 用 …………………………………………… 鐘 平，李華雄（31）

(1)無(wú)響應(yīng)時(shí)隙：在此時(shí)隙內(nèi)沒有標(biāo)簽發(fā)送。

(2)識(shí)別時(shí)隙：在此時(shí)隙內(nèi)只有1個(gè)標(biāo)簽發(fā)送,標(biāo)簽被正確識(shí)別。

(3)沖突時(shí)隙：在此時(shí)隙內(nèi)多個(gè)標(biāo)簽發(fā)送,產(chǎn)生沖突。這樣標(biāo)簽或成功發(fā)送或完全沖突,避免了原ALOHA算法中的部分沖突,使沖突期減少1/2,提高了信道的利用率。但是這種方法需要一個(gè)同步時(shí)鐘以使讀寫器閱讀區(qū)域內(nèi)的所有標(biāo)簽的時(shí)隙同步。

設(shè)T為單個(gè)標(biāo)簽完成發(fā)送自身ID號(hào)的時(shí)間,負(fù)載G為T時(shí)間內(nèi)某個(gè)閱讀器認(rèn)識(shí)范圍內(nèi)標(biāo)簽平均到達(dá)數(shù)量,吞吐量S為T時(shí)間內(nèi)某讀寫器成功完成通信的標(biāo)簽數(shù)量。則時(shí)隙ALOHA算法的吞吐量計(jì)算公式為：

當(dāng)G=1時(shí),吞吐量達(dá)到最大值,max(S)=e-1=0.368;當(dāng)G ＞1時(shí),系統(tǒng)處于不穩(wěn)定狀態(tài),當(dāng)大量標(biāo)簽存在時(shí)則不滿足需要。

1.3 碼分時(shí)隙ALOHA算法(C-S-ALOHA)

基于CDMA時(shí)隙ALOHA算法是在CDMA信道上使用時(shí)隙ALOHA技術(shù),而傳送的信息可以在時(shí)域和碼域上進(jìn)行二維檢測(cè),如圖1所示。

圖1 二維數(shù)據(jù)傳輸模型

在C-S-ALOHA算法中,若每個(gè)發(fā)送用戶有唯一的擴(kuò)頻碼字,不同的發(fā)送方使用不同的擴(kuò)頻碼字以時(shí)隙ALOHA方式發(fā)送信息,則稱為基于發(fā)送方的擴(kuò)頻傳輸協(xié)議(T-SSA),它的特點(diǎn)是沒有碼字選擇的沖突;若系統(tǒng)中的碼字總數(shù)受限于接收方的解調(diào)器,各個(gè)發(fā)送方需競(jìng)爭(zhēng)碼字傳送信息,則稱為基于接收方的擴(kuò)頻傳輸協(xié)議(R-SSA),它的特點(diǎn)是可以節(jié)省碼字?jǐn)?shù),減少碼字的同步時(shí)間,但有可能出現(xiàn)碼字競(jìng)爭(zhēng)沖突[6]。在RFID系統(tǒng)中基于對(duì)硬件電路復(fù)雜度的考慮,選取基于接收方的擴(kuò)頻傳輸協(xié)議。即在讀寫器中存儲(chǔ)有限數(shù)量的正交碼組,在每個(gè)標(biāo)簽中存儲(chǔ)2組數(shù)據(jù)：自身的ID號(hào)和隨機(jī)寫入的一組正交碼。

由于擴(kuò)頻碼的數(shù)量有限,必然會(huì)有不同的標(biāo)簽選用相同正交碼,在所有標(biāo)簽取得同步的基礎(chǔ)上,標(biāo)簽同時(shí)發(fā)送 ID號(hào)時(shí)必然會(huì)發(fā)生碰撞(見圖1)。

圖1中,在第3個(gè)時(shí)隙,有3個(gè)標(biāo)簽同時(shí)選用了碼字4,則發(fā)生碰撞,這時(shí)仍然采用S-ALOHA算法中的隨機(jī)退避機(jī)制達(dá)到識(shí)別目的,但只要選用不同的碼字就可以在1個(gè)時(shí)隙傳輸2個(gè)以上標(biāo)簽,圖1在時(shí)隙1和時(shí)隙5讀寫器接收到這些重疊的信號(hào)也能完整地分離出各個(gè)標(biāo)簽的ID號(hào),有效地改善了系統(tǒng)的吞吐量。系統(tǒng)的實(shí)現(xiàn)也較簡(jiǎn)單,僅需要在標(biāo)簽中增加1組正交碼和相應(yīng)的擴(kuò)頻電路,在讀寫器中存儲(chǔ)有限數(shù)量的正交碼組。在基于S-ALOHA算法的電路上變動(dòng)不大,具有實(shí)際意義。

2 C-S-CDMA算法的數(shù)學(xué)分析

由于所有標(biāo)簽的ID號(hào)是互異的,當(dāng)其選用不同的擴(kuò)頻碼發(fā)送ID號(hào),或者選用相同的擴(kuò)頻碼在不同的時(shí)隙發(fā)送,才可以成功地被讀寫器經(jīng)解擴(kuò)獲得,而不同的標(biāo)簽選用了相同的擴(kuò)頻碼且在同一時(shí)隙發(fā)送仍將會(huì)導(dǎo)致標(biāo)簽碰撞[7]。

假設(shè)CDMA時(shí)隙ALOHA接入系統(tǒng)每次可分配的擴(kuò)頻序列碼為N個(gè),以0,1,…,N-1標(biāo)識(shí)這些擴(kuò)頻序列碼。假設(shè)某時(shí)隙內(nèi)第i個(gè)標(biāo)簽使用第Rn個(gè)擴(kuò)頻碼(Rn是一個(gè)隨機(jī)整數(shù)0≤Rn≤N-1)發(fā)送自身ID號(hào)。而當(dāng)這一時(shí)隙中有其它標(biāo)簽使用同一個(gè)擴(kuò)頻碼發(fā)送ID號(hào)時(shí),就會(huì)產(chǎn)生沖突,信息就不可能被正確接收。因?yàn)闃?biāo)簽發(fā)送自身ID號(hào)所用的擴(kuò)頻碼可以看成均勻分布在[0,N-1]之間(即假設(shè)一個(gè)閱讀器范圍內(nèi)的標(biāo)簽是均勻分布的),則一個(gè)標(biāo)簽在該時(shí)隙中使用某個(gè)擴(kuò)頻碼發(fā)送的概率為：

如果在時(shí)隙 T內(nèi)有K+1個(gè)標(biāo)簽發(fā)送自身ID號(hào),則另外K個(gè)標(biāo)簽與第i個(gè)標(biāo)簽沒有使用同一個(gè)擴(kuò)頻碼的概率[8]為：

根據(jù)假設(shè)條件,一個(gè)閱讀器區(qū)域內(nèi)標(biāo)簽數(shù)目足夠多,可以把初始接入信息到達(dá)過(guò)程看作是Poisson過(guò)程,則在一個(gè)時(shí)隙內(nèi)有K個(gè)標(biāo)簽信息到達(dá)的概率為：

在每個(gè)時(shí)隙的開始處,假設(shè)一個(gè)閱讀器區(qū)域內(nèi)欲發(fā)送的接入信息有K+1個(gè),且至少有N個(gè)接入信息能被閱讀器接收到。對(duì)某個(gè)標(biāo)簽發(fā)送的信息,另外K個(gè)標(biāo)簽被看作為干擾。設(shè)Pc(K)是在K個(gè)干擾下一個(gè)標(biāo)簽的信息被成功捕獲和恢復(fù)的概率,平均信道吞吐量S是每個(gè)時(shí)隙內(nèi)成功發(fā)送被閱讀器成功收到的平均信息數(shù)目,它可以表示為：

在CDMA時(shí)隙ALOHA系統(tǒng)中,假設(shè)不考慮多址干擾和忽略高斯白噪聲,則 Pc(K)=P(K),同時(shí)在C-S-ALOHA接入系統(tǒng)中,不同的擴(kuò)頻碼序列總有一個(gè)接收機(jī)在前端控制器中,則S(G)又可以表示為：

對(duì)(6)式求導(dǎo)數(shù),并令其導(dǎo)數(shù)為零。即令?S/?G=0,當(dāng) G=N,吞吐量取最大 值,即max(S)=N/e=G/e,可見C-S-ALOHA算法的吞吐量是與擴(kuò)頻碼階數(shù)成正比的,是S-ALOHA算法的最大吞吐量0.36的 N倍。由于受硬件電路的影響,擴(kuò)頻碼階數(shù)是有限的,并不能通過(guò)無(wú)限增大擴(kuò)頻碼階數(shù)來(lái)提高系統(tǒng)的吞吐量。

3 計(jì)算機(jī)仿真結(jié)果及分析

為了驗(yàn)證本文提出的算法,在Matlab環(huán)境下進(jìn)行了仿真[9],仿真條件是標(biāo)簽分布服從Poisson分布。分別仿真了 N=1的C-S-ALOHA算法吞吐量,即S-ALOHA算法理論所能達(dá)到的最大吞吐量,驗(yàn)證了算法的最大吞吐量約為0.36,如圖2所示。

圖2 N=1時(shí)C-S-A LOHA算法的吞吐量

對(duì)不同階數(shù)的擴(kuò)頻碼的吞吐量進(jìn)行對(duì)比,如圖3所示,實(shí)驗(yàn)表明：

(1)當(dāng)N＜G時(shí),標(biāo)簽的吞吐量S與負(fù)載G成正比。

(2)當(dāng)N=G時(shí),標(biāo)簽的負(fù)載G達(dá)到極值。

(3)當(dāng)N＞G時(shí),標(biāo)簽的吞吐量S與負(fù)載G成反比,同時(shí)也表明階數(shù)越大對(duì)于G＞N時(shí)所引起的吞吐量的衰減影響越小,此結(jié)果與理論分析相符。

S-ALOHA和C-S-ALOHA(N=4)2種算法的吞吐量,如圖 4所示。實(shí)驗(yàn)結(jié)果表明,C-SALOHA算法的吞吐量明顯優(yōu)于S-ALOHA算法。

圖3 不同階擴(kuò)頻碼的吞吐量比較

圖4 2種算法的比較

4 結(jié)束語(yǔ)

本文提出了一種利用m序列作為擴(kuò)頻碼的C-S-ALOHA算法,把碼分多址技術(shù)和時(shí)隙ALOHA算法相結(jié)合,可以進(jìn)行時(shí)域和碼域的二維碰撞檢測(cè)。理論和實(shí)驗(yàn)結(jié)果表明：C-S-ALOHA算法的吞吐量明顯優(yōu)于S-ALOHA算法;而且用于傳送信息分組的擴(kuò)頻序列碼階數(shù)越多,系統(tǒng)的吞吐量越大,當(dāng)擴(kuò)頻碼階數(shù)大于負(fù)載時(shí),對(duì)于吞吐量衰減影響不大。但由于受硬件電路限制,擴(kuò)頻碼階數(shù)不能無(wú)限制的增加。與目前流行的S-ALOHA算法相比較,新算法極大地提高了系統(tǒng)的吞吐量,并且采用m序列編譯碼簡(jiǎn)單,硬件電路更改不大,具有很好的應(yīng)用前景。但本文未對(duì)時(shí)延作出分析,這將是后期研究的方向。

[1]王建偉,趙玉萍,Korhonen T.RFID系統(tǒng)防碰撞協(xié)議研究：設(shè)計(jì)與優(yōu)化[J].電子與信息學(xué)報(bào),2009,31(2)：1-4.

[2]梁 彪,胡愛群,秦中元.一種新的 RFID防碰撞算法設(shè)計(jì)[J].電子與信息學(xué)報(bào),2007,29(9)：2158-2160.

[3]曹小華,陶德馨,李文鋒.時(shí)隙A LOHA防沖突算法的馬爾可夫鏈模型研究[J].武漢理工大學(xué)學(xué)報(bào)：交通科學(xué)與工程版,2007,31(5)：796-799.

[4]邱 慶,張水蓮,陳海燕.m序列在雙正交碼擴(kuò)頻系統(tǒng)中的應(yīng)用[J].無(wú)線電工程,2004,34(8)：58-62.

[5]陳 香,薛小平,張思東.標(biāo)簽防沖突算法的研究[J].現(xiàn)代電子技術(shù)通信與信息技術(shù),2006,(5)：13-15.

[6]謝 磊,陳慧芳,仇佩亮.HFC網(wǎng)絡(luò)CDM A時(shí)隙A LOHA接入系統(tǒng)性能分析[J].電路與系統(tǒng)學(xué)報(bào),2000,5(3)：6-8.

[7]Liang B,Hu A Q,Qin Z Y.T rends and brief comments on anti-collision techniques in RFID[C]//Proc of the 6th Int Conf on ITS Telecomm,Chengdu,China,2006：241-245.

[8]程 楠,劉志敏,王繼新.Ad hoc網(wǎng)絡(luò) TDMA分布式動(dòng)態(tài)時(shí)隙算法[J].計(jì)算機(jī)應(yīng)用研究,2005,(1)：222-225.

[9]劉拓晟,何怡剛,侯再平,等.超高頻射頻識(shí)別的防碰撞算法設(shè)計(jì)[J].計(jì)算機(jī)工程,2008,44(36)：87-89.