基于连续时隙预测的帧时隙Aloha防碰撞算法

付 钰,钱志鸿,孟 婕,王 雪

(1．吉林大学通信工程学院,吉林长春 130012;2．中国电信股份有限公司北京分公司,北京100010)



基于连续时隙预测的帧时隙Aloha防碰撞算法

付 钰1,钱志鸿1,孟 婕2,王 雪1

(1．吉林大学通信工程学院,吉林长春 130012;2．中国电信股份有限公司北京分公司,北京100010)

在射频识别(Radio Frequency Identification,RFID)系统中,针对EPC C1G2协议的Q算法中Q值调整的不灵活性及对空闲时隙和碰撞时隙处理上的缺点,提出了一种基于连续时隙预测的帧时隙Aloha防碰撞算法.通过马尔可夫时隙状态模型,分析不同连续时隙状态下帧长与标签数的关系,提出连续时隙预测机制和自适应散列方案.有效地减少了无效时隙的出现,实现了读取阶段的时隙多数为成功时隙.仿真结果表明,本文提出的算法能够灵活地调整帧长,有效提高吞吐率,降低传输延时和开销,为物联网(Internet of Things,IoT)的海量数据信息完整性问题提供了合理的解决方案.

射频识别;防碰撞算法;Aloha;时隙预测

1 引言

物联网是一种新兴网络技术,是信息化时代的重要发展阶段,RFID(Radio Frequency Identification)作为物联网底层网络的关键技术之一,对物联网的发展起着至关重要的作用[1].RFID是一种新型的非接触式自动识别技术,由于其具有低功耗、低成本、数据存储容量大、多目标识别等优点,已经被广泛地应用于供应链管理、工业控制、卫生保健服务、智能交通、防伪等领域[2～5].

近些年来,RFID标签防碰撞问题引起了大量研究人员的关注.现有的防碰撞算法通常分为两类:基于树的确定性算法[6～9]和基于Aloha的概率性算法[10].基于树的确定性算法包括查询树算法[11]、二进制树算法[12]、搜索树算法[13]和碰撞树算法[14,15]等.但基于树的确定性算法需要识别查询区域内的所有标签,复杂度高且延时较长.而Aloha概率性算法不易受到标签ID位数的影响,更适用于如今的物联网大数据信息采集应用.典型的Aloha算法有纯ALOHA(Pure Aloha,PA)算法、时隙ALOHA(Slotted Aloha,SA)算法、帧时隙Aloha (Framed-Slotted Aloha,FSA)算法和动态帧时隙Aloha(Dynamic Framed-Slotted Aloha,DFSA)算法.PA算法[16]中标签将自身ID随机发送给读写器,然后等待响应,如果标签在发送信息的过程中其他的标签也在发送,那么可能导致部分碰撞或完全碰撞,系统吞吐率较低;为避免部分碰撞,SA算法将时间分成多个离散时隙,使标签在每个离散时隙的起始处同时传送ID;FSA算法[17]在SA算法的基础上,将多个时隙划分为一帧,每个标签只在每一帧中响应一次,若在当前帧中发生碰撞,则在下一帧中重新选择一个时隙,避免了标签频繁发生碰撞;DFSA算法[18]是对FSA算法的改进,使帧长尽可能地等于待读标签数.考虑到大量碰撞时隙和空闲时隙对系统效率的影响,研究人员还提出了不等长的DFSA算法,通过时隙内部机制,减少无效碰撞时隙和空闲时隙数,使系统性能得到显著改善,如EPC C1G2的Q算法[19].Q算法通过时隙内的预测机制调整Q值,进而达到调整帧长的目的,但仍存在较多的碰撞时隙和空闲时隙.且每个时隙结束后都需要计算Q值和参数C,在大量标签的情况下会严重加剧读写器运算负担,并不适用于物联网中的大数据环境.

针对上述不足,在现有的研究成果基础上,提出了一种基于连续时隙预测的帧时隙Aloha防碰撞算法,通过对连续空闲时隙和连续碰撞时隙的预测可加快跳过无效时隙.算法在大规模标签的情况下,仍保持较高的吞吐率,可稳定在65%左右,与已有算法相比,本文所提算法在系统吞吐率、传输开销和传输时延都具有一定的优越性.

2 改进算法分析

2.1 帧长调整方案

2.1.1 马尔可夫时隙状态模型

假设标签数为N,帧长L=2Q.根据二项式分布定理,第r个时隙中有m个标签的概率为

(1)

r为空闲时隙的概率

(2)

r为成功时隙的概率

(3)

r为碰撞时隙的概率

PC=1-PI-PS

(4)

通过帧内的成功、碰撞和空闲时隙数能动态估计L与N的关系.如果出现多个碰撞时隙,说明L较小.同理,如果有多个空闲时隙,则说明L远大于N,时隙因为“空闲”产生了浪费.在连续多个时隙碰撞或空闲的情况下需要调整帧长,其系统模型可用马尔可夫链分析,如图1所示.

设一帧中的第r个时隙,其中r∈[1,L],由于时隙状态仅与状态概率有关,因此可用(2i+1)×1的矩阵A(r)表示时隙r的状态,

(5)

其中

(6)

AS表示成功时隙的概率;ACn表示当前时隙为第n个连续碰撞时隙的概率,n∈[1,i];AIn表示当前时隙为第n个连续空闲时隙的概率.根据当前状态与前一状态概率和转移概率有关,因此得到时隙r+1的状态A(r+1)

A(r+1)=TA(r)

(7)

其中T是一个(2i+1)×(2i+1)的转移矩阵

(8)

2.1.2 时隙预测机制

为了动态地分析多个连续时隙状态,马尔可夫时隙状态模型中需要预测当前时隙之后的时隙状态,为此引入时隙预测机制.设时隙r中的标签数为m,可分为以下两种情况:

当m=1时,标签被成功识别,读写器发送Queryrep命令,标签置SC=SC-1.

当m≠1时,预测时隙r+1的状态,若时隙r+1与时隙r的状态相同(碰撞或空闲),则继续预测时隙r+2的状态,直到时隙状态不同则预测结束.假设时隙r,r+1,…,r+n-1的状态相同,即连续n个碰撞(或空闲)时隙,可表示为n-collision-slot(或n-idle-slot).

连续时隙预测机制中,n个时隙状态标签响应数据格式如下:

[RN16|SC=0]16+[RN16|SC=1]k+…+[RN16|SC=n]k

(9)

SC为0的标签响应当前时隙,返回完整的RN16,SC∈[1,n]的标签返回RN16前kbit.当n>0时,若预测结束,则读写器发送Queryrep指令,标签置SC=SC-n.若识别帧的预测结束,那么无效时隙被跳过,在附加帧识别碰撞标签.

2.1.3 帧长调整方案

通过预测识别帧连续时隙的状态,即n-collision-slot或n-idle-slot,当n值较小时,说明帧长合理;当n较大时,则需要调整帧长.通过马尔可夫时隙状态模型分析不同帧长与连续碰撞时隙和连续空闲时隙的关系.

不同帧长与连续碰撞时隙概率关系如表1,当L=0.75N时3-collision-slot发生的概率是0.0574,为小概率事件,在此认为不可能发生事件;当L=0.5N时,3-collision-slot发生的概率是0.2125,该情况出现较为合理.因此预测到3-collision-slot时,帧长扩大1倍.

不同帧长与连续空闲时隙概率关系如表2,当L=1.5N时4-idle-slot发生的概率是0.0650,属于小概率事件;L分别为1.75N和2N时,4-idle-slot发生的概率相应为0.1017和0.1353,因此预测到4-idle-slot时,帧长减半.

表1 不同帧长下连续碰撞时隙概率分布表

表2 不同帧长下连续空闲时隙概率分布表

2.2 碰撞时隙处理

算法规定在每一帧结束后增加附加帧,帧长与碰撞标签数相等.在附加帧中,读写器通过自适应散列方案对识别帧内的标签进一步识别,分配时隙,调整标签的SC值.

通常,调整帧长时应尽量接近待读标签数量,由表1可知超过连续2个时隙发生碰撞的概率比较低,因此只考虑n-collision-slot (n=1或2)的情况.设时隙r为第q个碰撞时隙,q=q1+q2,其中qn表示识别帧内直至时隙r出现时n-collision-slot的个数.通过Schoute算法[20]对碰撞标签进行估计,由碰撞标签数等于2.39倍的碰撞时隙数,得到碰撞标签数CT与qn关系如下:

(10)

在附加帧中,时隙r的碰撞标签分配时隙,加载SC值

(11)

其中remainingslot=2Q-r表示该帧的剩余时隙数.

如果附加帧中再次发生碰撞,将采用二进制散列机制.即碰撞标签的SC值随机置“0”或“1”,待读标签SC值加1.调整方式如下:

(12)

2.3 算法流程

为判断时隙状态,用m表示一个时隙内响应标签数.若m=0,没有标签响应,该时隙为空闲时隙;若m=1,只有一个标签响应,该时隙为成功时隙,标签被识别后置为静默状态,不再参与查询;若m>1,超过1个标签响应,该时隙为碰撞时隙.成功时隙为有效时隙,相应地,碰撞时隙和空闲时隙统称为无效时隙.

本文所提算法描述如下:

算法1 基于连续时隙预测的帧时隙Aloha防碰撞算法

①初始化,令Q=4.

②读写器发送Query(Q)指令,向所有标签发送Q值,各标签加载SC值,SC∈[0,2Q-1].

③判断该识别帧是否结束,若结束则转向⑦,否则,SC为0的标签响应,按式(9)向读写器返回相应数据.读写器根据响应标签判断时隙状态.若该时隙发生碰撞或空闲,则顺序执行④;若该时隙为成功时隙,则标签识别后置为静默状态,其余标签置SC=SC-1,返回③.

④判断该识别帧是否结束,若结束则转向⑦,否则,SC为1的标签响应,按式(9)返回相应数据.然后读写器判断时隙状态.若至该时隙只出现1-collision-slot,根据自适应散列机制加载SC值,碰撞标签将在附加帧中进一步识别,其余标签置SC=SC-1,返回③;若至该时隙只出现1-idle-slot,标签置SC=SC-1,返回③;若至该时隙出现2-collision-slot或2-idle-slot,则顺序执行⑤.

⑤判断该识别帧是否结束,若结束则转向⑦,否则,SC为2的标签响应,按式(9)返回相应数据.然后读写器判断时隙状态.若至该时隙只出现2-collision-slot,根据自适应散列方案加载SC值,碰撞标签将在附加帧中进一步识别,其余标签置SC=SC-2,返回③;若至该时隙只出现2-idle-slot,标签置SC=SC-2,返回③;若至该时隙出现3-collision-slot,则Q++,读写器执行QueryAdjust指令,返回②;若至该时隙出现3-idle-slot,则顺序执行⑥.

⑥识别帧是否结束,若结束则转向⑦,否则,SC为3的标签响应,按式(9)返回相应数据.若至该时隙出现3-idle-slot,其余标签置SC=SC-3;返回③;若至该时隙出现4-idle-slot,则Q--,读写器执行QueryAdjust指令,返回②.

⑦若附加帧没有标签需要识别,则算法结束.否则,顺序识别附加帧内的标签,SC为0的标签响应并发送[RN16|SC=0]16,当m=0或1时,其余标签置SC=SC-1,返回⑦;当m>1时,标签采用二进制散列机制重新加载SC,返回⑦.

3 仿真实验

3.1 帧长调整

为提高系统识别效率,帧长L应尽量接近待读标签数.当标签数在[100,3000]内变化,分别用连续时隙预测机制和经验C机制(C=0.8/Q)对帧长进行调整.

设Q的初值为4,图2为最佳Q值大于Q时,两种机制调整到最优帧长的碰撞时隙.由于标签数在一定区间内的最佳Q值相同,随着标签数量的增多,出现碰撞时隙的概率增大,空闲时隙的概率减小.新出现的空闲时隙会使Q值增加的速度减慢,从而需要更多的碰撞时隙才能调整到最佳Q值.因此在最佳Q值变化的临界值处,所需的碰撞时隙数会迅速变化,导致图7中的曲线呈折线形.显然,本文所提的机制比经验C机制所需的碰撞时隙数少,且帧长调整速度快.

设Q的初值为13,图3为最佳Q值小于Q时,两种机制调整到最优帧长所需的空闲时隙.图3的曲线也呈折线形,原理与图2相同,但趋势截然相反,在对应相同的最佳Q值区间内,标签数量越多,出现空闲时隙的概率越小,碰撞时隙的概率越大.因此,随着标签数量的增多,最佳Q值减小,空闲时隙减少.本文所提的机制比经验C机制调整帧长到最优时所需的空闲时隙更少.对于相同的最佳Q值,标签数越多,所需的空闲时隙数越少.

在大规模标签情况下,采取经验C机制调整帧长需要多次累加参数C,导致浪费多个无效时隙,系统效率降低.而本文的连续时隙预测机制,可以加速跳过无效时隙,本文所提算法在帧长调整方式方面性能更优.

3.2 传输开销

设标签数量在区间[100,3000]内变化,将本文算法和EPC标准中算法的传输开销进行比较.如图4所示,当N=3000时读写器开销比标准算法下降了11.6%.这是由于预测机制可以对连续碰撞时隙和连续空闲时隙加速跳过,减少了读写器开销.同时附加帧内的标签散列比识别帧的散列更为均匀,读写器成功识别标签的概率更大.随着标签数量的逐渐增多,本文的算法优势更加明显.

如图5所示,当N=3000时,本文提出的算法在k=1时,比标准中算法降低了63.27%.这是因为使用连续时隙预测机制,读写器并未增加额外的传输开销,而是随着总时隙数的递减使发送的比特数减少.进行预测时标签返回RN16的前kbit,k每增加1bit,标签的总传输开销会增加,因此标签开销随k的增加呈上升趋势.当k分别等于2、3和4时,标签的传输开销相应为76446.4bit、82762.5bit、89750.8bit.

3.3 传输时延与吞吐率

标签数量从[100,3000]内变化,将本文提出的算法的传输时延和吞吐率与几种经典ALOHA算法相比,初始帧长512.FSA算法帧长分别取512和1024,本文算法和FSA-DS算法中初值Q=4.

图6所示为几种算法识别标签的传输时延比较.随着标签数量的增加,FSA算法性能急剧下降,传输时延最大;FSA-DS算法[21]根据标签数能有效的调整帧长,但仍需要较多的时隙;而本文所提算法通过连续时隙预测机制,进一步减少了无效时隙的分配,因此所用时隙最少.当N=3000时FSA-DS算法所用时隙达5275,而本文所提算法只需4614,相比FSA-DS算法降低了12.53%.

图7所示,FSA算法在标签数与帧长相等时,吞吐率最高,达到36.8%.DFSA算法在标签数小于512时,多数标签在预估计阶段可以被成功识别,因此与FSA算法吞吐率基本一致;在标签数大于512时,由于帧长调整机制发挥作用,使理想情况下的吞吐率约为36.8%左右.FSA-DS算法具有较高的吞吐率,稳定地保持在53.1%以上.以FSA-DS算法为基础,本文所提算法进一步减少了无效时隙数,并加入了自适应散列,使得系统吞吐率性能最优,保持在60%以上.

4 结论

本文以协议EPC C1G2为基础,针对协议中原始算法Q值调整不灵活、标签散列随机性大等不足,提出了一种基于连续时隙预测的帧时隙ALOHA防碰撞算法.结合马尔可夫时隙状态模型,分析不同连续时隙状态下帧长与标签数的关系,提出连续时隙预测机制和自适应散列方案,对空闲和碰撞时隙加速跳过,有效地减少了无效时隙的出现.仿真结果显示,本文提出的算法降低了传输时延,具有较高的系统吞吐率,为物联网中海量数据的信息完整性问题提供了有效保障.

[1]钱志鸿,王义君.物联网技术与应用研究[J].电子学报,2012,40(5):1023-1029.

QIAN Zhi-hong,WANG Yi-jun.IoT technology and application[J].Acta Electronica Sinica,2012,40(5):1023-1029.(in Chinese)

[2]Zhu W,Cao J,Chan H,et al.Mobile RFID with a high identification rate[J].IEEE Transactions on Computers,2014,63(7):1778-1792.

[3]Vahedi E,Ward R K,Blake I F.Performance analysis of RFID protocols:CDMA versus the standard EPC Gen-2[J].IEEE Transactions on Automation Science and Engineering,2014,11(4):1250-1261.

[4]宋建华,郭亚军,韩兰胜,等.自调整混合树RFID多标签防碰撞算法[J].电子学报,2013,42(4):685-689.

SONG Jian-hua,GUO Ya-jun,HAN Lan-sheng,et al.An adjustive hybrid tree anti-collision algorithm for RFID multi-tag identification[J].Acta Electronica Sinica,2013,42(4):685-689.(in Chinese)

[5]Zhihong Q,Xue W.An overview of anti-collision protocols for radio frequency identification devices[J].China Communications,2014,11(11):44-59.

[6]王雪,钱志鸿,胡正超,等.基于二叉树的RFID防碰撞算法的研究[J].通信学报,2010,31(6):49-57.

WANG Xue,QIAN Zhi-hong,HU Zheng-chao.Research on RFID anti-collision algorithms based on binary tree[J].Journal on Communications,2010,31(6):49-57.(in Chinese)

[7]张学军,蔡文琦,王锁萍.改进型自适应多叉树防碰撞算法研究[J].电子学报,2012,40(1):193-198.

ZHANG Xue-jun,CAI Wen-qi,WANG Suo-ping.One anti-collision algorithm based on improved adaptive multi-tree search[J].Acta Electronica Sinica,2012,40(1):193-198.(in Chinese)

[8]Lai Y C,Hsiao L Y,Chen H J,et al.A novel query tree protocol with bit tracking in RFID tag identification[J].IEEE Transactions on Mobile Computing,2013,12(10):2063-2075.

[9]Liu X,Qian Z,Zhao Y,et al.An adaptive tag anti-collision protocol in RFID wireless systems[J].China Communications,2014,11(7):117-127.

[10]陈毅红,冯全源.按需时隙分配RFID防碰撞协议研究[J].电子学报,2014,42(2):377-382.

CHEN Yi-hong,FENG Quan-yuan.An on-demand slot assignment anti-collision protocol for RFID system[J].Acta Electronica Sinica,2014,42(2):377-382.(in Chinese)

[11]Hush D R,Wood C.Analysis of tree algorithms for RFID arbitration[A].Proceedings of 1998 IEEE International Symposium on Information Theory[C].Cambridge,USA:IEEE,1998.107-107.

[12]Law C,Lee K,Siu K Y.Efficient memoryless protocol for tag identification[A].Proceedings of 4th International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications[C].New York,USA:ACM,2000.75-84.

[13]Klaus F.RFID Handbook:Fundamentals and Applications in Contactless Smart Cards and Identification[M].New York:John Wiley & Sons Ltd,2003.

[14]Jia X,Feng Q,Ma C.An efficient anti-collision protocol for RFID tag identification[J].IEEE Communications Letters,2010,14(11):1014-1016.

[15]Jia X,Feng Q,Yu L.Stability analysis of an efficient anti-collision protocol for RFID tag identification[J].IEEE Transactions on Communications,2012,60(8):2285-2294.

[16]Abramson N.The ALOHA system:another alternative for computer communications[A].Proceedings of Joint Computer Conference[C].New York,USA:ACM,1970.281-285.

[17]Kim S C,Cho J S,Kim S K.Performance improvement of hybrid tag anti-collision protocol for radio frequency identification systems[J].International Journal of Communication Systems,2013,26(6):705-719.

[18]Eom J B,Lee T J.Accurate tag estimation for dynamic framed-slotted ALOHA in RFID systems[J].IEEE Communications Letters,2010,14(1):60-62.

[19]张小红,张留洋.RFID防碰撞时隙应变协处理算法研究[J].电子学报,2014,42(6):1139-1146.

ZHANG Xiao-hong,ZHANG Liu-yang.Research on RFID anti-collision algorithm of slot responding in real-time and co-processing[J].Acta Electronica Sinica,2014,42(6):1139-1146.(in Chinese)

[20]Schoute F C.Dynamic frame length ALOHA[J].IEEE Transactions on Communications,1983,31(4):565-568.

[21]李萌,钱志鸿,张旭,等.基于时隙预测的RFID防碰撞 ALOHA 算法[J].通信学报,2012,32(12):43-50.

LI Meng,QIAN Zhi-hong,ZHANG Xu,et al.Slot-predicting based ALOHA algorithm for RFID anti-collision[J].Journal on Communications,2012,32(12):43-50.(in Chinese)

付 钰 女,1990年生于吉林省吉林市.现为吉林大学通信工程学院博士研究生.主要研究方向为RFID和物联网.

E-mail:fuyu-only@163.com

钱志鸿(通信作者) 男,1957年生于吉林长春.现为吉林大学教授、博士生导师.主要研究方向为物联网、RFID、WIFI、无线传感器网络和无线定位等.

E-mail:dr.qzh@163.com

FSA Anti-collision Algorithm Based on Continuous Slot Prediction

FU Yu1,QIAN Zhi-hong1,MENG Jie2,WANG Xue1

(1.CollegeofCommunicationEngineering,JilinUniversity,Changchun,Jilin130012,China;2.ChinaTelecomCoBeijingBranch,Beijing100010,China)

In the RFID (Radio Frequency Identification,RFID) system,due to inflexibility ofQvalue adjustment and weaknesses of the idle slots and collision slots processing withinQalgorithm of EPC C1G2 protocol,this paper proposes FSA(Framed-Slotted Aloha,FSA) anti-collision algorithm based on continuous slot prediction.The proposed algorithm analyzes the relationship between frame length and the number of tags in different continuous slots status based on Markov slot status model.Continuous slot prediction mechanism and adaptive hashing scheme are proposed to implement that the time slots in read phase are mostly success slots,which effectively reducing invalid slots occur.Simulation results show that the proposed algorithm can flexibly adjust the frame size,improve throughput and reduce transmission delay and overhead,which provides a reasonable solution to integrity problems of massive data in the IoT (Internet of Things,IoT).

radio frequency identification (RFID);anti-collision algorithm;Aloha;slot prediction

2015-01-22;

2015-04-25;责任编辑:覃怀银

国家自然科学基金(No. 61371092)；吉林省和长春市科技攻关项目(No. 20140204019GX, No. 20150101050JC, No. 2014026, No. 16SS02) ; 吉林大学研究生创新基金资助项目(No. 2016091)

TN92

A

0372-2112 (2016)09-2081-06

��学报URL:http://www.ejournal.org.cn

10.3969/j.issn.0372-2112.2016.09.009