造价通

反馈
取消

热门搜词

造价通

取消 发送 反馈意见

防碰撞算法Q值算法及其改进算法

2022/07/1687 作者:佚名
导读:DFSA算法可采用各种方法预测待识别的标签数量,然后动态调整最优帧长,与FSA相比,系统效率有明显改善,接近36.8%。但是,当标签数量较多(特别是标签数量大于500)时,采用由预测标签数量设置最优帧长的方案会使系统效率急剧下降。因此,在标签数量较多的情况下,为了使系统效率得到提高,EPCClass1Gen2标准中采用了Q值算法,该算法可以实时自适应地调整帧长 。 Q值算法 在Q值算法中,阅读器首

DFSA算法可采用各种方法预测待识别的标签数量,然后动态调整最优帧长,与FSA相比,系统效率有明显改善,接近36.8%。但是,当标签数量较多(特别是标签数量大于500)时,采用由预测标签数量设置最优帧长的方案会使系统效率急剧下降。因此,在标签数量较多的情况下,为了使系统效率得到提高,EPCClass1Gen2标准中采用了Q值算法,该算法可以实时自适应地调整帧长 。

Q值算法

在Q值算法中,阅读器首先发送Query命令,该命令中含有一个参数Q(取值范围0~15),接收到命令的标签可在[0,2Q-1]范围内(称为帧长)随机选择时隙,并将选择的值存入标签的时隙计数器中,只有计数器为0的标签才能响应,其余标签保持沉默状态。当标签接收到阅读器发送的QueryRep命令时,将其时隙计数器减1,若减为0,则给阅读器发送一个应答信号。标签被成功识别后,退出这轮盘存。当有两个以上标签的计数器都为0时,它们会同时对阅读器进行应答,造成碰撞。阅读器检测到碰撞后,发出指令将产生碰撞的标签时隙计数器设为最大值(2Q-1),继续留在这一轮盘存周期中,系统继续盘存直到所有标签都被查询过,然后阅读器发送重置命令,使碰撞过的标签生成新的随机数 。

根据上一轮识别的情况,阅读器发送Query-Adjust命令来调整Q的值,当标签接收到Query-Adjust命令时,先更新Q值,然后在[0,2Q-1]范围内选择随机值。EPCClass1Gen2标准中提供了一种参考算法来确定Q值的范围.其中:Qfp为浮点数,其初值一般设为4.0,对Qfp四舍五入取整后得到的值即为Q;C为调整步长,其典型取值范围是0.1

该算法在参数C的辅助下对Q值进行动态调整,但是C太大会造成Q值变化过于频繁,导致帧长调整过于频繁,C太小又不能快速地实现最优帧长的选择。因此,研究者们对Q值的调整进行了各种优化 。

基于最大吞吐量调整Q值的算法

文献提出一种基于最大吞吐量对Q值进行调整的算法,其中定义了以下变量:Nt为已识别的标签个数;N为识别标签所需的总时隙数;NC为冲突时隙的个数;nu为上一轮未识别的标签个数;e为冲突时隙中的平均标签个数;PC为冲突时隙所占的比例 。

这些参数之间的关系为PC=NC/N,e=nu/Nc,吞吐量=Nt/N。由于Aloha类算法的最大吞吐量为0.368(e-1)[5],该算法以此作为调整Q值的依据。当系统吞吐量达到或接近0.368时,阅读器仅需调用2Q-1次QueryRep命令,而不需要在接下来的盘存周期中调整Q值。当吞吐量小于0.368时,根据未识别的标签个数nu来调整Q值 .

基于分组的位隙Aloha算法

文献提出一种基于分组的位隙Aloha算法,该算法采用位隙Aloha算法中的128位预定序列,代表128个位隙。若某个标签选择了第i个位隙,则将第i位置1,其余各位都置0。当标签数量为15时,位隙Aloha算法可获得最大吞吐率88.38%,但随着标签数量的增加,算法性能急剧下降 。

因此,基于分组的位隙Aloha算法通过对标签进行分组来提高算法的性能。该算法在查询命令中设置了一个位隙计数器的参数Q(Q为整数,且0≤Q≤15),当标签收到阅读器发送的查询命令后,在[0,2Q-1]范围内生成一个随机数,即代表选择了相应的位隙,只有选择了0的标签才会立即响应。同时,该算法根据冲突位隙数动态地对Q值进行调整:当冲突位隙数小于11时,Q减1且最小为0;当冲突位隙数在11~20之间时,Q保持不变;当冲突位隙数大于20时,Q加1且最大不超过15 。

综上所述,基于Aloha的防碰撞算法原理简单、容易实现,对新到达的标签具有较好的适应性,尤其对于标签持续到达的情况有较好的解决方案,但该类算法存在几个明显的缺点:①响应时间不确定,即同一批标签在不同时刻进行识别所需要消耗的时间相差很大;②个别标签可能永远无法被识别;③Aloha算法达到最佳吞吐率的条件是其帧长等于标签数量,当需要识别的标签数量较多或选择的帧长与实际待识别标签数量不符时,系统性能将明显下降。而基于树的算法则很好地解决了这些问题 。

*文章为作者独立观点,不代表造价通立场,除来源是“造价通”外。
关注微信公众号造价通(zjtcn_Largedata),获取建设行业第一手资讯

热门推荐

相关阅读