论文研究-一种动态分组RFID防碰撞搜索树算法研究与实现 .pdf

所需积分/C币:7 2019-08-16 13:27:49 244KB .PDF

一种动态分组RFID防碰撞搜索树算法研究与实现,吕国宁,胡明生,多标签冲突碰撞问题是RFID技术中存在的主要问题,是目前该领域研究的热点和难点之一。在分析现有的基于二进制的防碰撞算法基础上��
国武技论文在线 非目标标签同读写器的不断通信,干扰系统的正常工作;第三,读写器发送的以标签序列号 为依据的请求指令,易被外界设备所截获,造成信息泄露和安全问题。针对上述存仁的 主要问题,本文给出一种动态分组查询的进制搜索算法 动态分组查询树防碰撞算法 木文提出的算法主要思想是通过对大量标签进行子集划分缩小识别范围,然后再用上文 提到的二进制搜索算法思想,确定读写器发送冲突位置并发送查询数据指令,有序地识别标 签,然后对发送指令长度进行动态调整,以实现信道使用的髙效性。 算法描述 在描述算法流程之前,先定义相关的防碰撞命令: 、请求命令 ,:其中参数表小为二进制的比特位数,表小为系统检测 的有冲突的最高比特位。读写器向每一个待接收标签发送此命令。接收标签将所得位处的 编码与值比较,若成功匹配则返回冲突位和相关信息:;否则将停止匹配而进入休眠状态, 并将计数器重置为“”。休眠状态的标签则计数器继续罴加 激活命令 :该命令将激活处于休眠状态的标签。并对休眠标签的程序计数器 进行递减操作。当休眠计数器减到时,标签状态转变为待命,能再接收 命令请求。 、去选择命令 该命令作用是取消已选择的标签,将标签状态置为“无声”, 此时不能接收 命令。当标签离开可读区域并重新进入可读区域时,才能重浙接收 命令。 只体的实现过程课描述如下,改定读写器作用范围内有四个标签,每个标签长度位, 各自为 和 首先,读写器发送 命令, 表小为结束符,将标签划分两个子集 和最高位为的标签先进行命令响应,最高位为的标签先进入休眠状态。详细执行过 程如下: 读写器向标签 发送 (,)命令;四个设定的标签对比接 收命令的最高位和査询位,然后标签和标签返回下一位,标签和标签则进入休眠 状态直到其他标签被识别或重置操作。 读写器以返回值作为查询值,发送命令 ,。标签和标签返回 各自下一位 位发送冲突时,读写器将无法得到标签响应。此时,算法做如下处 理:读写器记录冲突位置和,并将作为下一位查询值 读写尜发送 ,)命令;标签指针所指位数值与查询值不同,标 签进入休眠状态。标签则返回最后位。读写器最终识别出标签并将其进行处 读写器发送 (,,)命令;标签査询位置并将指针指向位。 如果与査询位匹配则返回其最后一位。最终实现对标签的识别 读写器发送 )命令;重新激活标签和标签,比较各自最高位 和査询位的值。如果兀配则返回下一位,表示存在冲突,冲突位为。读写器保存冲突 位置和并将下一步查询参数置。 、读写尜发送 ,)命令:只有标签进行响应返回其下一位 读写器发送 (,)命令;标签返回最后一位,读写器识别出标签 ,将其置于“哑巴”状态,屏蔽该标签。、读写器发送 ,)余令 国武技论文在线 在读写区内的标签中,只有标签进行应答,返回到读写器。 读写器发送 (,)命令;标签返回最后一位:读写器可判决标签, 算法完成。 以上步骤的流栏图如下: 开始 将读写器作用域内标签分0和 两个子集 是 测了集内是否发生碰名一 记录冲突位置,搦冲突 位置和0作为查询数据 否 将返回数据作为查询据 否 检测数据是香结束 结束 图算法流程图 性能分析 上述算法测试了对四个标签的识别过程,即当根节点下有四个子节点时,父节点和子节 点双向搜索的过程。因此在识别中,子节点搜索是双向存在的。总的搜索次数为 结论:若要对个标签利用该算法进行识别,所需总的搜索次数为 对此结论利用数学归纳法进行证明: 时,搜索次数显然为: 时,因为标签的编码不会产生重复,所以 读写器发送 命令吋,冲突位至少为,设检测到的最高冲突位为其中, ,标签编码长度为,按照流程,读写器下·次将发送请求命令 那么其中一个标签应答,从而对应答标签实现识别。之后通过回跳策略对另一个标签实 现识别。当时,标签编码都是唯一的,不会重复,因此当读写器发送 命令时,冲突位至少是,若检测到的冲突位最高为其中,∈,,…, 标签 编码长,则读写器下一次发送请求命令 时,其中一个标签响应,从而实现了 对应答标签的识别。然后运行回跳策略去识别下一个标签。所以, 。结论成立 假设 个标签时,搜索次数 成立。 、当标签数为时,由于编码只有唯一性,新标签编似不会和原有的个标签重复 在识别过程中,原二进制搜索树需要新增一个节点,根据父子节点闾的双向搜索特性,可以 得出, ,结论成立。 对ˆ标签利用遍厉循环搜索的动态二进制搜索算法,则所需总的搜索次数为: 国武技论文在线 n(n+1) 2 假设标签的编码长度为位,在二进制搜索算法中,请求命令 每次发送标签编 码的序列号,其编码长度为。动态二进制算法每次发送的平均二进制编码长度为 而木文的算法的发送命令长度取决J冲突位置,其平均编码长度为log2 由此,得到本文动态二进制搜索算法在识别个标签时,所需传输的二进制数据总长为: M+1n(n+1) 改进后的算法为 仿真结果 本文基于 平台设计仿真实验以对本文算法进行性能测试。实验内容为:在深 度优先搜索的前提下,首先产生位比特的随机标签,对本文所提算法和动态二进制搜 索算法的查询次数进行对比。实验结果如图所示: 800 600 进制算法 -+ -1÷--- UU 2 00 图识别标签所需搜索次数图 轴表示为读写器中标签的数量,轴表示为识别标签的查询次数。可知,随着标签数 量的嶒多,所需査询次数怛在快速増长。而本文提出的改进搜索算法要同传统动态二进制算 法相比,有效降低了査询次数,且标签薮量越多优势越明显。 结语 本文对传统的动态二进制搜索算法进行了改进,利用子集分组的方式对标签进行处理。 实验结果表明,该算法减少识别标签时间和系统通信传输的数据量,能忺速识別标签,降低 了所需的査询次数,提高了系统的效率。为解决多标签碰撞问题提供了一种有效方式。 参考文献 王雪,钱志鸿基于二叉树的防碰撞算法的研究,通信学报 马昌社向隐私安全的低成木认证协议,计算机学报: 左磊,何怡刚无源超高频系统识别区域分析及优化,物理学报: 刘永,熊兴中,李晓花防碰撞技术的研究,电信科学, () 张忠,徐秋亮物联网环境下安全的组证明协议.计算机学报, 徐海峰,姜晖,刘振一种新的混合防碰揎算法,计算机工程与应用 国武技论文在线

...展开详情
img

关注 私信 TA的资源

上传资源赚积分,得勋章
相关内容推荐