段力畑,王子中,2,段 富

(1.太原理工大學(xué) a.信息工程學(xué)院,b.計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,太原030024;2.弗吉尼亞衛(wèi)斯理學(xué)院,Norfolk,USA)

?

基于分組的多級(jí)隨機(jī)數(shù)RFID標(biāo)簽并行識(shí)別算法

段力畑1a,王子中1a,2,段 富1b

(1.太原理工大學(xué) a.信息工程學(xué)院,b.計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,太原030024;2.弗吉尼亞衛(wèi)斯理學(xué)院,Norfolk,USA)

為了提高大規(guī)模RFID系統(tǒng)中的被動(dòng)標(biāo)簽識(shí)別率,在分析已有基于幀時(shí)隙ALOHA標(biāo)簽識(shí)別算法的基礎(chǔ)上,結(jié)合分組算法和多級(jí)隨機(jī)數(shù)算法的思想,將多級(jí)隨機(jī)數(shù)分別部署在不同組的標(biāo)簽中,使用動(dòng)態(tài)幀時(shí)隙ALOHA算法框架,提出基于分組的多級(jí)隨機(jī)數(shù)并行識(shí)別算法框架,推導(dǎo)出多級(jí)隨機(jī)數(shù)適時(shí)選擇機(jī)制的計(jì)算公式。針對(duì)并行識(shí)別過(guò)程中的負(fù)載不均衡問(wèn)題,提出了3種負(fù)載均衡策略及其形式化描述,設(shè)計(jì)了與之相應(yīng)的3種算法并進(jìn)行了性能分析和仿真。結(jié)果表明,所提算法可以有效地將部分非成功時(shí)隙轉(zhuǎn)化為成功時(shí)隙,提高了標(biāo)簽識(shí)別率、標(biāo)簽識(shí)別速度和時(shí)隙利用率:平均識(shí)別率均在70%以上,最高可達(dá)76.77%;標(biāo)簽識(shí)別速度較單隨機(jī)數(shù)的算法提高了66%;時(shí)隙利用率達(dá)51.02%,約為單隨機(jī)數(shù)算法的2倍。所提算法具有并行、高效、輕量等特點(diǎn),適用于大規(guī)模被動(dòng)式RFID系統(tǒng)的應(yīng)用場(chǎng)合。

大規(guī)模RFID系統(tǒng);動(dòng)態(tài)幀時(shí)隙ALOHA;被動(dòng)式標(biāo)簽;多級(jí)隨機(jī)數(shù);并行識(shí)別

無(wú)線射頻識(shí)別技術(shù)(Radio Frequency Identification, RFID)是一種非接觸式自動(dòng)識(shí)別技術(shù),它能夠利用射頻信號(hào)進(jìn)行空間耦合而實(shí)現(xiàn)信息交互[1],識(shí)別過(guò)程也無(wú)需人工干預(yù),因此在供應(yīng)鏈管理、倉(cāng)庫(kù)管理和訪問(wèn)控制等領(lǐng)域應(yīng)用廣泛,出現(xiàn)了相應(yīng)的大規(guī)模RFID應(yīng)用系統(tǒng)。該系統(tǒng)主要由大量的標(biāo)簽、多閱讀器和系統(tǒng)服務(wù)(如數(shù)據(jù)庫(kù))組成,閱讀器與標(biāo)簽之間使用EPC global Class-1 Gen-2協(xié)議[2],并通過(guò)基于幀時(shí)隙ALOHA的算法(FSA)識(shí)別被動(dòng)式標(biāo)簽。針對(duì)FSA中幀長(zhǎng)度固定的問(wèn)題,研究人員又提出了根據(jù)估算當(dāng)前未讀標(biāo)簽數(shù)而動(dòng)態(tài)確定幀長(zhǎng)的動(dòng)態(tài)幀時(shí)隙ALOHA(DFSA)及其改進(jìn)算法。估算的方法除了比較經(jīng)典的最小值方法[3]、泊松分布方法[4]、碰撞因子方法[5]外,也出現(xiàn)了適用于標(biāo)簽量較大的采樣和復(fù)合估算方法:文獻(xiàn)[6]提出的基于采樣的線性標(biāo)簽數(shù)估算方法,通過(guò)i個(gè)時(shí)隙的估算值等比地計(jì)算出實(shí)際未讀標(biāo)簽數(shù);文獻(xiàn)[7]提出了時(shí)隙結(jié)果采樣統(tǒng)計(jì)的分情況標(biāo)簽數(shù)估算方法,通過(guò)采樣結(jié)果中空閑、碰撞和成功時(shí)隙之間關(guān)系的不同而采用不同的估算方法；文獻(xiàn)[8]提出的一種時(shí)隙數(shù)選擇方法能夠基于碰撞時(shí)隙的個(gè)數(shù)動(dòng)態(tài)調(diào)整當(dāng)前幀長(zhǎng);文獻(xiàn)[9]中總結(jié)并列出不同幀長(zhǎng)時(shí)理想的標(biāo)簽數(shù)范圍,通過(guò)查表的方式動(dòng)態(tài)調(diào)整當(dāng)前幀長(zhǎng);文獻(xiàn)[10-11]以354作為標(biāo)簽數(shù)分組的門限值并對(duì)應(yīng)幀長(zhǎng)256。上述所有算法的識(shí)別率均未突破FSA類算法識(shí)別率36.8%的瓶頸。

為了進(jìn)一步提高標(biāo)簽的識(shí)別率,研究者提出基于多級(jí)隨機(jī)數(shù)的算法。該類算法充分利用了非成功時(shí)隙,使識(shí)別效率達(dá)到45%以上。文獻(xiàn)[12]中標(biāo)簽生成兩個(gè)隨機(jī)數(shù)并劃分優(yōu)先級(jí),將部分空閑時(shí)隙轉(zhuǎn)化為成功時(shí)隙而將識(shí)別效率提高到45.3%。文獻(xiàn)[13]中,提出了多級(jí)隨機(jī)數(shù)選擇的數(shù)學(xué)模型,計(jì)算出第i級(jí)的識(shí)別率Si，通過(guò)將3級(jí)隨機(jī)數(shù)部署在單個(gè)標(biāo)簽上,將部分空閑和碰撞時(shí)隙轉(zhuǎn)化為成功時(shí)隙,識(shí)別率達(dá)到69.35%。然而該算法未充分考慮被動(dòng)式標(biāo)簽有限的存儲(chǔ)和計(jì)算能力以及閱讀器較強(qiáng)的計(jì)算能力。

隨著RFID技術(shù)的進(jìn)步和應(yīng)用系統(tǒng)規(guī)模的擴(kuò)展,需要研究一種適合于大規(guī)模被動(dòng)式RFID系統(tǒng)使用的輕量、并行、高效識(shí)別算法。為此,筆者結(jié)合基于分組和多級(jí)隨機(jī)數(shù)標(biāo)簽識(shí)別算法的設(shè)計(jì)思想,將多級(jí)隨機(jī)數(shù)分別部署在不同組的標(biāo)簽中,以動(dòng)態(tài)幀時(shí)隙ALOHA(DFSA)算法框架為基礎(chǔ),提出了基于分組的多級(jí)隨機(jī)數(shù)并行識(shí)別算法。針對(duì)算法中負(fù)載不均衡的問(wèn)題,實(shí)現(xiàn)了3種采用不同負(fù)載均衡策略的模式,并對(duì)其性能進(jìn)行了理論分析和仿真實(shí)驗(yàn),驗(yàn)證了該算法的有效性。

1 算法設(shè)計(jì)

為了滿足大規(guī)模RFID系統(tǒng)中高效識(shí)別被動(dòng)式標(biāo)簽的需求,本文結(jié)合分組和多級(jí)隨機(jī)數(shù)的思想,在大量標(biāo)簽分組的基礎(chǔ)上,將多級(jí)隨機(jī)數(shù)依次部署在不同的標(biāo)簽組上,設(shè)計(jì)了一種在DFSA框架內(nèi)按多級(jí)隨機(jī)數(shù)適時(shí)選擇機(jī)制一次處理多個(gè)標(biāo)簽組的并行算法,由于輪詢次序影響了標(biāo)簽組的識(shí)別率,使對(duì)應(yīng)的標(biāo)簽組內(nèi)未識(shí)別標(biāo)簽數(shù)不盡相同,出現(xiàn)了并行算法的負(fù)載不均衡問(wèn)題。因此,還需要解決標(biāo)簽組的負(fù)載不均衡問(wèn)題。

本算法由標(biāo)簽數(shù)估計(jì)與分組、識(shí)別過(guò)程和負(fù)載均衡3部分組成,算法流程如圖1所示。圖中,T表示所有標(biāo)簽的集合,G表示所有組的集合,P表示所有并行組的集合。

圖1 基于分組的多級(jí)隨機(jī)數(shù)并行識(shí)別算法框架Fig.1 The frame of Parallel Identification Algorithm for RFID tags with Group-based Multiple-random Numbers

由于閱讀器在一個(gè)幀時(shí)隙內(nèi)按多級(jí)隨機(jī)數(shù)的級(jí)次對(duì)相應(yīng)的標(biāo)簽組進(jìn)行輪詢,直到有一個(gè)標(biāo)簽被成功識(shí)別或輪詢完所有相應(yīng)的標(biāo)簽組。那么,對(duì)第i級(jí)隨機(jī)數(shù)的輪詢,是在前i-1個(gè)隨機(jī)數(shù)的輪詢沒(méi)有成功識(shí)別標(biāo)簽的條件下發(fā)生的,其成功識(shí)別一個(gè)標(biāo)簽的概率。第i級(jí)隨機(jī)數(shù)的識(shí)別率Si可用條件概率計(jì)算,由此推出計(jì)算Si公式(1);相應(yīng)的總識(shí)別率S可通過(guò)公式(2)計(jì)算。由公式(1)，公式(2)計(jì)算5級(jí)隨機(jī)數(shù)的Si及相應(yīng)級(jí)別的總識(shí)別率S,結(jié)果如圖2所示。

(1)

S=∑Si,1≤i≤m (m為隨機(jī)數(shù)的級(jí)數(shù)) .

(2)

由圖2可知,從5級(jí)開(kāi)始Si小于1%,并且S的增長(zhǎng)逐漸放緩并趨于平穩(wěn);考慮到DFSA框架的幀長(zhǎng)是以2的整數(shù)次冪,所以算法取隨機(jī)數(shù)的級(jí)數(shù)m=4 .

1.1 分組與初始化

在閱讀器感知到其覆蓋范圍內(nèi)的標(biāo)簽集合定義為T,使用文獻(xiàn)[7]中的算法估算出標(biāo)簽數(shù)量nt并分為大小相等的ng組,得到分組標(biāo)簽集合G={gi|i∈[1, ng]},其中|gi|=?nt/ng」+1, ng為m的整數(shù)倍；從G取出前m個(gè)放入P={pj| j∈[1, m]}；初始化P內(nèi)各組內(nèi)已讀標(biāo)簽的數(shù)目集合為S={sj| j∈[1, m]}=?,未讀標(biāo)簽的數(shù)目集合為U={uj| j∈[1, m]}=|P| .

圖2 級(jí)數(shù)m對(duì)應(yīng)的識(shí)別率SiFig.2 The Si for different m-values

1.2 識(shí)別過(guò)程

通過(guò)分組和初始化過(guò)程,按照DFSA的框架以P為負(fù)載開(kāi)始一個(gè)識(shí)別過(guò)程,閱讀器確定合適的幀長(zhǎng)按時(shí)隙對(duì)標(biāo)簽組進(jìn)行輪詢。首先輪詢p1中的標(biāo)簽,如果在當(dāng)前時(shí)隙內(nèi)沒(méi)有標(biāo)簽成功響應(yīng)則輪詢p2內(nèi)的標(biāo)簽并以此類推至p4,直至有一個(gè)標(biāo)簽成功響應(yīng)或者輪詢完所有標(biāo)簽組,開(kāi)始下一個(gè)時(shí)隙輪詢；當(dāng)一幀結(jié)束后,估計(jì)P內(nèi)當(dāng)前未讀標(biāo)簽數(shù)后動(dòng)態(tài)確定最優(yōu)幀長(zhǎng)開(kāi)始下一次盤存周期至P中所有標(biāo)簽識(shí)別完畢。在識(shí)別過(guò)程中,由于每個(gè)時(shí)隙中按照固定順序輪詢而造成P中每組未讀標(biāo)簽數(shù)不盡相同,所以當(dāng)滿足一定條件時(shí)需要進(jìn)行組間負(fù)載的調(diào)整,開(kāi)始新一輪的識(shí)別過(guò)程。識(shí)別過(guò)程流程圖如圖3所示。

1.3 負(fù)載均衡

在識(shí)別的過(guò)程中,由于輪詢的次序?qū)?biāo)簽組的識(shí)別率有影響,在m=4級(jí)隨機(jī)數(shù)中各級(jí)的識(shí)別率依次為36.8%,23.26%,9.29%和2.35%,這使對(duì)應(yīng)的U(j)不盡相同,出現(xiàn)了并行算法的負(fù)載不均衡問(wèn)題。針對(duì)P中成功識(shí)別1組標(biāo)簽、2組標(biāo)簽和4組標(biāo)簽的情況,提出了3種基于組粒度的負(fù)載均衡調(diào)整策略。

定義1P中負(fù)載均衡

若并行集中標(biāo)簽組的個(gè)數(shù)等于4,即P={pj|j∈[1,4]},且第j個(gè)標(biāo)簽組的未讀標(biāo)簽數(shù)U(j)與當(dāng)前Q所對(duì)應(yīng)的標(biāo)簽數(shù)上界L(Q)、下界R(Q)之間滿足關(guān)系:L(Q)≤U(j)≤R(Q),其中Q∈[2,8],j∈[1,4]。那么,P被認(rèn)為在當(dāng)前Q下是負(fù)載均衡的。

Q值所對(duì)應(yīng)的標(biāo)簽數(shù)上界L(Q)、下界R(Q)參考自文獻(xiàn)[14],列于表1。

表1 Q值對(duì)應(yīng)標(biāo)簽上、下界

策略1(PMould 1) 若s1和s2之和大于一個(gè)組所包含的數(shù)量時(shí),則輸出p1和p2中已識(shí)別的標(biāo)簽(約1組),并將p1中未識(shí)別的標(biāo)簽合并至p2,然后從G={gi|i∈[1,ng]}中取出新的1組補(bǔ)充到P中作為p1,將更新后的P作為并行算法的負(fù)載,開(kāi)始下一輪識(shí)別過(guò)程。算法如下：

PMould1intk=1，n；∥n為組內(nèi)標(biāo)簽數(shù)輸入：G={gi|i∈[1，ng]}intm=4；for(j=1；j<=m；j++)pj=gk；k++；輸出：P={pj|j∈[1，4]}輸入：P={pj|j∈[1，4]}for(j=1；j<=4；j++)if(閱讀器成功識(shí)別pj一個(gè)標(biāo)簽)S(j)++；if(S(1)+S(2)>n)p1=gk；輸出：P={pj|j∈[1，4]}

圖3 基于分組的多級(jí)隨機(jī)數(shù)DFSA識(shí)別流程Fig.3 The flowchart for proposed algorithm

策略2( PMould2 ) 當(dāng)|S|大于兩個(gè)組所包含的數(shù)量時(shí),輸出P已識(shí)別的標(biāo)簽(約2組),將p1中未識(shí)別的標(biāo)簽合并至p4,將p2中未識(shí)別的標(biāo)簽合并至p3,然后從G={gi|i∈[1,ng]}中取出新的2組補(bǔ)充到P中作為新p1和p2,將更新后的P作為并行算法的負(fù)載,開(kāi)始下一輪識(shí)別。算法如下：

PMould2intk=1，n；∥n為組內(nèi)標(biāo)簽數(shù)輸入：G={gi|i∈[1，ng]}intm=4；for(j=1；j<=m；j++)pj=gk；k++；輸出：P={pj|j∈[1，4]}輸入：P={pj|j∈[1，4]}for(j=1；j<=4；j++)if(閱讀器成功識(shí)別pj一個(gè)標(biāo)簽)S(j)++；if(S(1)+S(4)>n&&S(2)+S(3)>n)pj=gk；k++；pj=gk；k++；輸出：P={pj|j∈[1，4]}

策略3(PMould 3) 在閱讀器輪詢完每一幀之后,按照S(j),j∈[1, 4]的大小降序排序,并按更新后的次序開(kāi)始下一幀的輪詢,直至|U|=?或幀長(zhǎng)L≤8(Q≤3)為止。輸出P已識(shí)別的標(biāo)簽(約4組),并從G取4組分別與P內(nèi)各組剩余的未識(shí)別標(biāo)簽合并,更新后的P作為并行算法的負(fù)載,開(kāi)始下一輪識(shí)別。算法如下：

PMould3intk=1，n；∥n為組內(nèi)標(biāo)簽數(shù)輸入：G={gi|i∈[1，ng]}intm=4；for(j=1；j<=m；j++)pj=gk；k++；輸出：P={pj|j∈[1，4]}輸入：P={pj|j∈[1，4]}for(j=1；j<=4；j++)if(閱讀器成功識(shí)別pj一個(gè)標(biāo)簽)S(j)++；SortingpjbyS(j)descendingorderinanewarrayA[]；for(j=1；j<=4；j++)pj=A[5-j]；輸出：P={pj|j∈[1，4]}

1.4 算法性能分析

本節(jié)從標(biāo)簽識(shí)別率、時(shí)隙碰撞率、時(shí)隙利用率等指標(biāo)對(duì)所提算法進(jìn)行算法性能分析,結(jié)果如表2所示。由于多級(jí)隨機(jī)數(shù)的識(shí)別率服從條件概率的計(jì)算條件,因此標(biāo)簽識(shí)別率S可通過(guò)公式(2)計(jì)算,相應(yīng)的可計(jì)算出時(shí)隙碰撞率。識(shí)別標(biāo)簽所需平均時(shí)隙(Aslot)可通過(guò)公式(3)計(jì)算,標(biāo)簽響應(yīng)的平均時(shí)隙數(shù)(Tslot)由公式(4)計(jì)算,時(shí)隙利用率(Eslot)由公式(5)得出。

表2 性能分析

通過(guò)與單隨機(jī)數(shù)性能比較,利用4級(jí)隨級(jí)數(shù)后,標(biāo)簽識(shí)別率大幅度提高,識(shí)別單個(gè)標(biāo)簽所需的平均時(shí)隙個(gè)數(shù)降低,標(biāo)簽的響應(yīng)率提高,時(shí)隙利用率提高約1倍。

(3)

(4)

(5)

2 仿真結(jié)果分析和比較

在MATLAB環(huán)境中,標(biāo)簽規(guī)模從6 000到12 000間隔200,對(duì)所提出的算法(PMould1,PMould2,PMould3以及沒(méi)有負(fù)載均衡的算法)進(jìn)行了仿真,其中分組估計(jì)采用和文獻(xiàn)[7]中相同的程序。重復(fù)仿真5次后取平均值,圖4為識(shí)別效率的比較曲線,圖5為算法在分組數(shù)(圖5(a))、組合并次數(shù)(圖5(b))和幀調(diào)整次數(shù)(圖5(c))的比較曲線。

圖4 識(shí)別效率結(jié)果Fig.4 The throughput for identification

從圖中可以看出,PMould1,PMould2和PMould3的平均識(shí)別效率在72%以上,均高于沒(méi)有負(fù)載均衡的算法(70.6%),PMould3平均效率最高(76.7%)。其中,PMould1和PMould2需要PGT內(nèi)的組間合并保持其識(shí)別效率,而PMould3需要頻繁調(diào)整Q值保持其識(shí)別效率。因此可根據(jù)不同的工作環(huán)境選擇不同的算法。

圖5 基本算法與負(fù)載均衡調(diào)整方法Fig.5 The comparison results in (a) Grouping numbers; (b) Merging times; (c) Frame adjusting times

表3列出了在標(biāo)簽總數(shù)為273 000的情況下,PMould 1,PMould 2,PMould 3與分組算法[11]和多級(jí)隨機(jī)數(shù)算法[13]在識(shí)別效率和花費(fèi)時(shí)間上的比較。總體來(lái)說(shuō),所提出的算法均超過(guò)分組識(shí)別算法和多級(jí)隨機(jī)數(shù)識(shí)別算法的識(shí)別效率。運(yùn)行時(shí)間上,PMould 3花費(fèi)的時(shí)間最短,相比于分組算法可以節(jié)省66%左右,PMolud1和PMould2也有相應(yīng)提高,分別為22%和14%。

表3 識(shí)別效率對(duì)比

3 結(jié)論

本文以動(dòng)態(tài)幀時(shí)隙ALOHA(DFSA)為基礎(chǔ),提出了一種基于分組的多級(jí)隨機(jī)數(shù)并行識(shí)別算法框架。根據(jù)并行識(shí)別過(guò)程中組間負(fù)載不均衡的問(wèn)題,設(shè)計(jì)了3種采用不同負(fù)載均衡策略的算法,并對(duì)其性能進(jìn)行了理論分析和仿真實(shí)驗(yàn)。結(jié)果表明,平均識(shí)別率在70.65%以上,其中使用負(fù)載均衡策略調(diào)整的算法平均識(shí)別率在72%以上并最高可達(dá)到76.77%。本文算法的識(shí)別速度均高于分組算法。其中基于次序調(diào)整的組粒度負(fù)載均衡策略的算法識(shí)別率最高,速度最快,適用于大規(guī)模被動(dòng)式RFID系統(tǒng)使用。今后的工作將繼續(xù)針對(duì)更細(xì)粒度的識(shí)別算法進(jìn)行研究。

[1] 梁雪萍,馬存慶,梁穎升.基于幀時(shí)隙ALOHA的RFID標(biāo)簽集合檢測(cè)協(xié)議框架[J].計(jì)算機(jī)應(yīng)用研究,2015(3):1-6.

[2] EPC Radio-Frequency Identity Protocols,Class-1 Generation-2 UHF RFID Protocol for Communications at 860 MHz—960 MHz, Version 2.0.0[S].USA:Springer,2013.

[3] VOGT H.Efficient object dentification with passive RFID tags[C]∥IEEE.First International Conference on Pervasive Computing Pervasive 2002,Zurich,Switzerland,2002:26-28.

[4] 顏元,武岳山,熊立志.一種新型多標(biāo)簽估算方法[J].計(jì)算機(jī)應(yīng)用研究,2012(3):930-932.

[5] 賀洪江,丁曉葉,翟耀緒.一種基于碰撞因子的RFID標(biāo)簽估算方法[J].計(jì)算機(jī)應(yīng)用研究,2011(11):4131-4133.

[6] CHEN W.A feasible and easy-to-implement anticollision algorithm for the EPCglobal UHF class-1 generation-2 RFID protocol[J].IEEE Transactions on Automation Science and Engineering,2014,11(2):485-491.

[7] DUAN Litian,WANG Zizhong,JOHN,et al.An identification algorithm in grouping and paralleling for data-intensive RFID systems[C]∥Springer.First International Conference on Big Data Computing and Communications 2015,Taiyuan,China,2015:1-3.

[8] DANESHMAND M,WANG C,SOHRABY K.A new slot-count selection algorithm for RFID protocol[C]∥IEEE.The Second International Conference on Communications and Networking in China,Shanghai,China,2007:22-24.

[9] MYUNG J,LEE W J, SRIVASTAVA J.Adaptive binary splitting for efficient RFID tag anti-collision[J].IEEE Communications Letters,2006(10):144-146.

[10] LEE S R,JOO S D,LEE C W.An enhanced dynamic framed slotted ALOHA algorithm for RFID tag identification[C]∥IEEE Computer Society. Proceedings of 2nd Annual International Conference on Mobile and Ubiquitous Systems:Networking and Services,Washington D C,USA,2005:166-174.

[11] WANG Hui,XIAO Shengliang.Group improved enhanced dynamicframe slotted ALOHA anti-collision algorithm[J].The Journal of Supercomputer,2014,69(3):1235-1253.

[12] 史長(zhǎng)瓊,肖瑞強(qiáng),吳丹.改進(jìn)的動(dòng)態(tài)幀時(shí)隙ALOHA防碰撞算法[J].計(jì)算機(jī)工程與設(shè)計(jì),2014,35(6):1897-1900,1910.

[13] 杜永興,白文浩,李寶山.RFID系統(tǒng)動(dòng)態(tài)幀時(shí)隙ALOHA算法的改進(jìn)[J].高技術(shù)通訊,2015,25(3):313-318.

[14] DUAN Litian,PANG Wenwen,Duan Fu.An enhanced posterior probability anti-collision algorithm based on dynamic frame slotted ALOHA for EPCglobal Class1 Gen2[J].Journal of Communications,2013,9(10):798-804.

(編輯：賈麗紅)

A Parallel Identification Algorithm for RFID tags with Group-based Multiple-random Numbers

DUAN Litian1a,WANG Zizhong1a,2,DUAN Fu1b

(1a.College of Information Engineering,b.College of Computer Science and Technology,TaiyuanUniversityofTechnology,Taiyuan030024;2.VirginiaWesleyanCollege,Norfolk,USA)

To enhance the efficiency for identifying passive tags in large-scale RFID systems, a parallel identification framework based on group algorithms and multiple-random numbers algorithms is proposed, which is implemented by putting multiple-random numbers into different groups,The calculation formula for multiple-random numbers is also provided in this paper. This parallel identification framework is under the dynamic frame slotted ALOHA framework. Additionally, there are three adjustment strategies to keep the load balance during parallel identification process. As a result, the proposed algorithms can efficiently transfer part of collision or empty slots into successful slots to improve the utilization.Simulation results present that the average efficiency of identification is over 70% and maximizes to 76.77%, the identification speed is increased by 66%, and the utilization for slots is 51.02% which is approximate 2 times that of single random number algorithm.The proposed algorithms are suitable for large-scale RFID systems with the characters of parallel, high efficiency and lightweight in computation and storage cost.

large-scale RFID System;dynamic frame slotted ALOHA;passive tags;multiple-random numbers;parallel identification

1007-9432(2016)04-0495-06

2016-03-19

國(guó)家自然科學(xué)基金資助項(xiàng)目：大型采煤設(shè)備異常追蹤檢測(cè)與診斷的免疫智能方法研究 (61472271);國(guó)家自然科學(xué)青年基金資助項(xiàng)目：層次?；牟淮_定多態(tài)網(wǎng)絡(luò)重疊社區(qū)發(fā)現(xiàn)辦法研究 (61503273)

段力畑(1989-)，男，太原人，博士生，主要從事RFID識(shí)別技術(shù)研究，(E-mail)dylann@yeah.net

段富，博導(dǎo)，教授，主要從事物聯(lián)網(wǎng)、人工智能、計(jì)算機(jī)網(wǎng)絡(luò)等的研究，(E-mail)duanfu@tyut.edu.cn

TP301.6

A

10.16355/j.cnki.issn1007-9432tyut.2016.04.012