基于分組的多級隨機數RFID標簽并行識別算法

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

(1.太原理工大學 a.信息工程學院,b.計算機科學與技術學院,太原030024;2.弗吉尼亞衛斯理學院,Norfolk,USA)

?

基于分組的多級隨機數RFID標簽并行識別算法

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

(1.太原理工大學 a.信息工程學院,b.計算機科學與技術學院,太原030024;2.弗吉尼亞衛斯理學院,Norfolk,USA)

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

大規模RFID系統;動態幀時隙ALOHA;被動式標簽;多級隨機數;并行識別

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

為了進一步提高標簽的識別率,研究者提出基于多級隨機數的算法。該類算法充分利用了非成功時隙,使識別效率達到45%以上。文獻[12]中標簽生成兩個隨機數并劃分優先級,將部分空閑時隙轉化為成功時隙而將識別效率提高到45.3%。文獻[13]中,提出了多級隨機數選擇的數學模型,計算出第i級的識別率Si，通過將3級隨機數部署在單個標簽上,將部分空閑和碰撞時隙轉化為成功時隙,識別率達到69.35%。然而該算法未充分考慮被動式標簽有限的存儲和計算能力以及閱讀器較強的計算能力。

隨著RFID技術的進步和應用系統規模的擴展,需要研究一種適合于大規模被動式RFID系統使用的輕量、并行、高效識別算法。為此,筆者結合基于分組和多級隨機數標簽識別算法的設計思想,將多級隨機數分別部署在不同組的標簽中,以動態幀時隙ALOHA(DFSA)算法框架為基礎,提出了基于分組的多級隨機數并行識別算法。針對算法中負載不均衡的問題,實現了3種采用不同負載均衡策略的模式,并對其性能進行了理論分析和仿真實驗,驗證了該算法的有效性。

1 算法設計

為了滿足大規模RFID系統中高效識別被動式標簽的需求,本文結合分組和多級隨機數的思想,在大量標簽分組的基礎上,將多級隨機數依次部署在不同的標簽組上,設計了一種在DFSA框架內按多級隨機數適時選擇機制一次處理多個標簽組的并行算法,由于輪詢次序影響了標簽組的識別率,使對應的標簽組內未識別標簽數不盡相同,出現了并行算法的負載不均衡問題。因此,還需要解決標簽組的負載不均衡問題。

本算法由標簽數估計與分組、識別過程和負載均衡3部分組成,算法流程如圖1所示。圖中,T表示所有標簽的集合,G表示所有組的集合,P表示所有并行組的集合。

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

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

(1)

S=∑Si,1≤i≤m (m為隨機數的級數) .

(2)

由圖2可知,從5級開始Si小于1%,并且S的增長逐漸放緩并趨于平穩;考慮到DFSA框架的幀長是以2的整數次冪,所以算法取隨機數的級數m=4 .

1.1 分組與初始化

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

圖2 級數m對應的識別率SiFig.2 The Si for different m-values

1.2 識別過程

通過分組和初始化過程,按照DFSA的框架以P為負載開始一個識別過程,閱讀器確定合適的幀長按時隙對標簽組進行輪詢。首先輪詢p1中的標簽,如果在當前時隙內沒有標簽成功響應則輪詢p2內的標簽并以此類推至p4,直至有一個標簽成功響應或者輪詢完所有標簽組,開始下一個時隙輪詢；當一幀結束后,估計P內當前未讀標簽數后動態確定最優幀長開始下一次盤存周期至P中所有標簽識別完畢。在識別過程中,由于每個時隙中按照固定順序輪詢而造成P中每組未讀標簽數不盡相同,所以當滿足一定條件時需要進行組間負載的調整,開始新一輪的識別過程。識別過程流程圖如圖3所示。

1.3 負載均衡

在識別的過程中,由于輪詢的次序對標簽組的識別率有影響,在m=4級隨機數中各級的識別率依次為36.8%,23.26%,9.29%和2.35%,這使對應的U(j)不盡相同,出現了并行算法的負載不均衡問題。針對P中成功識別1組標簽、2組標簽和4組標簽的情況,提出了3種基于組粒度的負載均衡調整策略。

定義1P中負載均衡

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

Q值所對應的標簽數上界L(Q)、下界R(Q)參考自文獻[14],列于表1。

表1 Q值對應標簽上、下界

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

PMould1intk=1，n；∥n為組內標簽數輸入：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(閱讀器成功識別pj一個標簽)S(j)++；if(S(1)+S(2)>n)p1=gk；輸出：P={pj|j∈[1，4]}

圖3 基于分組的多級隨機數DFSA識別流程Fig.3 The flowchart for proposed algorithm

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

PMould2intk=1，n；∥n為組內標簽數輸入：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(閱讀器成功識別pj一個標簽)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]的大小降序排序,并按更新后的次序開始下一幀的輪詢,直至|U|=?或幀長L≤8(Q≤3)為止。輸出P已識別的標簽(約4組),并從G取4組分別與P內各組剩余的未識別標簽合并,更新后的P作為并行算法的負載,開始下一輪識別。算法如下：

PMould3intk=1，n；∥n為組內標簽數輸入：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(閱讀器成功識別pj一個標簽)S(j)++；SortingpjbyS(j)descendingorderinanewarrayA[]；for(j=1；j<=4；j++)pj=A[5-j]；輸出：P={pj|j∈[1，4]}

1.4 算法性能分析

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

表2 性能分析

通過與單隨機數性能比較,利用4級隨級數后,標簽識別率大幅度提高,識別單個標簽所需的平均時隙個數降低,標簽的響應率提高,時隙利用率提高約1倍。

(3)

(4)

(5)

2 仿真結果分析和比較

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

圖4 識別效率結果Fig.4 The throughput for identification

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

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

表3列出了在標簽總數為273 000的情況下,PMould 1,PMould 2,PMould 3與分組算法[11]和多級隨機數算法[13]在識別效率和花費時間上的比較。總體來說,所提出的算法均超過分組識別算法和多級隨機數識別算法的識別效率。運行時間上,PMould 3花費的時間最短,相比于分組算法可以節省66%左右,PMolud1和PMould2也有相應提高,分別為22%和14%。

表3 識別效率對比

3 結論

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

[1] 梁雪萍,馬存慶,梁穎升.基于幀時隙ALOHA的RFID標簽集合檢測協議框架[J].計算機應用研究,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] 顏元,武岳山,熊立志.一種新型多標簽估算方法[J].計算機應用研究,2012(3):930-932.

[5] 賀洪江,丁曉葉,翟耀緒.一種基于碰撞因子的RFID標簽估算方法[J].計算機應用研究,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] 史長瓊,肖瑞強,吳丹.改進的動態幀時隙ALOHA防碰撞算法[J].計算機工程與設計,2014,35(6):1897-1900,1910.

[13] 杜永興,白文浩,李寶山.RFID系統動態幀時隙ALOHA算法的改進[J].高技術通訊,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

國家自然科學基金資助項目：大型采煤設備異常追蹤檢測與診斷的免疫智能方法研究 (61472271);國家自然科學青年基金資助項目：層次粒化的不確定多態網絡重疊社區發現辦法研究 (61503273)

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

段富，博導，教授，主要從事物聯網、人工智能、計算機網絡等的研究，(E-mail)duanfu@tyut.edu.cn

TP301.6

A

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