Ｎｅｔｗｏｒｋ Ｗｏｒｌｄ●网络天地 物联网中标签持续到达的ＲＦＩＤ防碰撞算法思路构建 针对目前无线射频识别标签 防碰撞算法中存在的识别效率在 标签持续到达时的下降问题，本 文提供了在给出标签到达与识别 过程模型的前提下、支持标签持 续到达的防碰撞算法的思路。本 思路使用标签到达与识别的过程 模型，所构造出来的算法能够对 阅读器识别区域内的标签数量进 行准确的估算。同时该算法使用 排队论，对标签到达率的最大值 进行了研究，确保了算法运行的 稳定。 【关键词】物联网标签ＲＩＦＤ防碰撞算法思 路 “物联网”一词随着电子信息技术、通 －＿ｊ 一信技术以及智能嵌入技术等的不断进步而频繁 出现在人们的视线中。所谓物联网，即指物物 相连的互联网。总共包含两层含义：一是其基 础及核心依然是互联网。也就是说，物联网是 互联网的扩展及延伸；二是客户端之间的信息 交换延伸至任意的物品与物品之间。 １网联网及ＲＩＦＤ概述 物联网的宗旨是使万物之间的信息传递 更加方便快捷。要实现这一宗旨，要重要的就 是要对物联网中的事物进行有效识别，这也是 物联网的基础。在现今的技术手段下，自动识 空一别技术是将物联网中的物和网进行有效连接的 基本方式。 在物联网众多的自动识别技术中，ＲＦＩＤ 技术是一种实时、准确、快速的非接触式自动 识别技术。ＲＦＩＤ，即指无线射频识别技术。 ＲＦＩＤ利用射频信号以及空间耦合传输的特性， 对目标对象进行自动识别，以此来获取所需的 中 信息。由于ＲＦＩＤ对物联网的需求具有很强的 适应性，因此在物联网的物品自动识别技术中， 它是最重要的识别技术。ＲＦＩＤ具有的最突出 的优势是能够对多目标进行识别及读取，刚好 与物联网的全面感知及海量存储的要求不谋而 合。 ２问题的提出 ＲＩＦＤ系统分别由标签和阅读器两部分组 成。在标签较多时容易发生碰撞，因此降低其 碰撞率是非常必要的，常使用的方法是防碰撞 算法。 文／刘忠群 Ｆｉ Ｆ ｔ 图１：标签到达与识别过程 在ＲＦＩＤ中，系统识别效率的高低与否取 分来决定，一是上一帧没有识别标签的数量， 决于标签防碰撞算法的优劣。标签防碰撞算法 二是新到达标签的数量。该算法能够有效解决 又能对ＲＦＩＤ在现实中的普及程度产生影响。 标签持续到达时系统的效率下降问题。 在学术界，根据长期以来对相关理论及技术的 研究，已经对ＲＦＩＤ中的多目标碰撞识别算法 ３新算法的基本模型 问题形成了系统科学的体系。 在帧时隙ＡＬＯＨＡ系统中，识别周期Ｐ 碰撞协议主要有两种：时隙ＡＬＯＨＡ类协 是由许多帧Ｆ。组成的，而则由多个时隙ｔ， 组 议和树类协议。前一种协议的优势在于实现比 成，Ｆｉ＝ Ｕ＝１，…，ｎ ，｝，其中ｎ。为帧长。 较容易，因此在ＲＦＩＤ系统中的应用比较广泛。 识另０周期Ｐ＝｛Ｆ．ｊｌｃｎｇｔｈ（Ｆ，）＝ｎ。，ｎ。∈Ｚ ｝， 后一种协议的优势在于能够对阅读器识别区域 Ｆ。未识别的标签数量为ｒｉ（ｒｉ＞０，０ ｉ ｕ一１）。 内的所有标签进行识别，但缺陷是延迟的时间 而帧Ｆ，内每个时隙所到达标签的平均值为 较长。 Ｍｏ ＜１）。当 ＝０时，表示识别过程中没 当标签的数量帧内的时隙数一致时，时 有标签到达。现有算法对这种静态环境进行了 隙ＡＬＯＨＡ类协的议识别效率也会达到最高。 研究；本文则是对Ｏ＜ ＜１时的动态环境进行 现有的相关研究也主要是集中于使二者的数值 研究。 相等。但标签数量会在识别过程中发生一定的 帧Ｆ．中的标签数量由两部分组成，一是 变化，因此需要一种动态协议。由此出现了 未开始识别时启动时间Ｔ内到达的标签数量， 与之相适应的动态帧时隙ＡＬＯＨＡ协议，简称 二是新到的标签数量。识别前标签的到达率 ＤＦＳＡ。ＤＦｓＡ在设置时将帧的长度与标签的 为 ，标签数为ｒｏ＝Ｔ￣ｏ；新到标签数为 ｎ。。 数量设为一致，使得即使标签数量发生变化， 因此帧内的标签总数即为ｍ，（ｍ。＞０）即由未 识别效率依然最高。在标签数量不断变化的前 识别的标签数ｌ＇ｉ＿１（１兰ｉ５ｕ）和新到的标签数 提下，准确估计标签数量是保证识别效率最高 组成。识别过程见图１。 的关键。目前的标签估计方法有很多。例如 由上述内容可以得出，帧长取决于前一 Ｓｃｈｏｕｔｅ估计法、Ｃｈａ估计法、ｖｏｇｔ法、Ｗｅｎ． 帧Ｆ 未识别的标签数量和新到标签的到达率 Ｔｚｕ Ｃｈｅｎ估计法等。以Ｃｈａ估计法和为例， 。在帧Ｆ，没有开启的情况下，对 进行估计 估计的标签数量ｎ满足： 是在标签持续到达的前提下，防碰撞算法对标 １ “ 签进行有效识别的核心和关键。在绝大多数情 ｌ一（１一ｊ） （１＋≠ ）。其中ｌ为帧长。而 况下，标签的到达率是不断变化的，如果使用 Ｗｅｎ—Ｔｚｕ Ｃｈｅｎ估计法在所有算法中所产生的 固定的到达率进行标签数量的计算，很明显不 误差最小，平均大约为５％。上述方法均给定 合理。因此进行标签数量估计的基本要求是对 了标签，标签的数量是固定的。也就是说如 标签的到达率进行动态估计。由图１可知，帧 果在识别时有外部标签进入，那么识别的误差 Ｆ 内的标签数量估算值为ｒ．＋ｓ。＝ｒｉ．１＋ ｎ．。进一 就会加大，降低识别效率。换句话说，上述方 步说，如果Ｆ．内的成功识别时隙数为Ｓ，，空闲 法在阅读器无标签持续到达的静态情况下能够 时隙数为ｋｉ，碰撞时的时隙数为 ，那么可以 确定帧长，但如果是在标签持续到达的工厂自 得出，ｎｉ＝ｓ ＋ｌｑ＋ｇ。。 动化生产线上，则无法确定。本次研究针对这 对于识别周期Ｐ的系统效率Ｅｐ，不同文 一问题，构建了一种能够支持标签持续到达的 献有不同记载，本文中所指的是周期Ｐ以内总 ＲＦＩＤ防碰撞算法。在该算法中，帧长由两部 成功时隙数与总时隙数的比值， Ｅｌｅｃｔｒｏｎｉｃ Ｔｅｃｈｎｏｌｏｇｙ＆Ｓｏｆｔｗａｒｅ Ｅｎｇｉｎｅｅｒｉｎｇ电子技术与软件工程·９ ～ 网络天地·Ｎｅｔｗｏｒｋ Ｗｏｒｌｄ ｒｉＥｐ （ ） ∑ｆ＿ｌ ｉ＝１ 。个标签在Ｆ 内的平均到达率为 ＝ ．。／ｎ。。 转为表示标签已经识别成功的静默状态， Ｔａｇ ＝Ｔａｇｉ一｛Ｓ｝。对循环激活状态的标签ｑ与 ｔｒ进行比较，如果二者相等，则向阅读器传送 。 ｕ～十一吞吐率ｔｈｐ： Ｐ ‘，ｓｌｏｔ， 。其中ｔ。 为时隙的时长。Ｆ 的帧效率ｔｌ１ｉ的定义 根据帧Ｆ。未识别标签数的估计值计算公式， 能够得出 一ｌ＝２．３９ｇ＿．１，因此２．３９ｇＨ／ｎ ＋ ＝１。 此外，由Ｆ；阅读器周围标签的平均到达率计 为帧内标签的成功识别时隙数与帧长的比值， ｔｈ，＝Ｓｉ／ｎｉ。假设标签的数量和帧长的数量相 等时碰撞的时隙标签数为２．３９，那么未识别标 签的数量ｒｌ的估计值即为 ＝２．３９ｘｇ 。ｘ个标签 被分配于ｎ个时隙的帧内，帧效率在ｘ＝ｎ的条 件下达到最优，为Ｏ．３６８。 其ＩＤ 值，ｕｑ ｕｑ＋１；与其不相等部分的标签 ｍ｛ｍ∈Ｔａｇ ，ｍ≠ｓＪｔｍ≠ｑ ｌ，ｕ ＝ｕｍ＋１。对 于外部新到的标签部分万，在到达时隙时立刻 算公式可知 丑 由此证明本式的正确性。 定理３：外部新到标签的平均到达率 ＜Ｏ．３６８是保证系统稳定运行的基本条件。 向阅读器传送ＩＤ，那么帧Ｆ。中参与识别过程 证明：标签的识别过程结束后，离开是 读器可以被当做这一排队系统的服务器，标 定理１及其证明过程可以得出，标签的到达 的标签数量就会增加：Ｔａｇ ＝Ｔａｇｆ＋｛万｝， （１０）在订的后半段时，阅读器对标签 得到正确的 那么Ｒ ＝ＩＤｑ，且Ｓ。＝Ｓ。＋１：若 在离散间隙内，形成了离散时间排队系统。阅 标签万转为不断激活状态。 签被当做客户，离去规则为随机离去。根据 是否识别成功进行检查。如果已经识别成功且 ４ ＣＤＦＳＡ算法 根据之前所论述的计算方法，会使帧的 长度小于标签数，从而使系统的效率与最优值 间隔为几何状，到达概率为 ，也就是说标签 相比较小。本文提出的是一种对标签持续到达 的平均到达速度为 。帧效率在时隙ＡＬＯＨＡ 的过程进行分析的ＣＤＦＳＡ算法。 算法中的最大值为０．３６８，也可以认为是在时 ４．１对标签持续到达及识别过程的分析 隙内以Ｏ．３６８的概率对每一个标签进行识别， 也就是说ｒｔ＝０．３６８，同时服务时间的间隔也是 根据上述所提到的效率最优原理，在 几何状的，因此这一离散排队系统为Ｇｅｏｍ／ ＣＤＦＳＡ算法中，确定效率最优时的时长的关 Ｇｅｏｍ／１。根据该系统的稳定条件Ｐ＝ ／ ＜１ 键是对下一帧的标签数量进行估计，也就是说 可知，当 Ｏ．３６８时，ｋ＜０．３６８；Ｌ＞０．３６８时， 要对新到标签的到达率进行估计。本文以定理 ｐ＞ｌ，此时系统不稳定，帧的长度也会不断变长。 的形式将结论呈现出来，同时对其进行证明。 在阅读器的服务效率有限的情况下，会造成标 定理ｌ：帧Ｆ 内的未识别标签在帧Ｆ，中 签的相关信息遗失。这对ＲＦＩＤ系统来说是不 任意选择帧时隙的过程以及新到标签任意到达 能出现的，因此可将这一数据作为对标签速度 帧Ｆ．内的时隙的过程皆可看做泊松到达过程， 进行控制的根据。 且两个过程相互独立。 ４．２具体算法 证明：在帧时隙算法中，帧Ｆ．．．内未识别 的ｒｉ．。个标签在Ｆ；内被识别时是任意选择时隙 本文所提出的ＣＤＦＳＡ算法的基本过程如 的，某一个时隙被选中的概率为１与时隙的比 下： 值。也就是说在１１．时隙内到达的标签数量为 （１）对参数Ｔ及 进行初始化。 ｒｉ．个。而帧内标签一般较多，帧长也较大， （２）将帧Ｆ 的长度设置为Ｔ 。取整数： 那么某一时隙被选中的概率相对而言就会很 ｎｌ＝ｒｏｕｎｄ（ ），而且ｇ０＝ 。 小。根据概率的相关理论可知，时隙被选中的 （３）帧计数器ｉ＝ｌ。 概率很小而到达标签数量较多时，帧Ｆ 内的 （４）阅读器帧ｉ长度的计算： ｔ一 个未识别标签在帧Ｆ．内任意选择时隙ｔｉｉ的 过程与泊松到达过程较为接近。新到标签到达 ｎ：ｉ ｒｏｕｎｄ （ ）ｌ。 ．１ 帧Ｆｊ的过程与这一过程类似，因此也可被认 （５）当ｎ ：Ｏ时结束；ｎ１≠０时继续。 为是泊松到达过程。将单位时隙的平均标签数 （６）阅读器对还没有识别的标签进行防 作为两个过程泊松到达的参数，用五 和 分别 碰撞控制，使其处于不断被激活的状态。所有 表示。根据标签持续到达的过程可以得知，未 标签所构成的集合Ｔａｇｉ形成参与帧Ｆ。识别的 识别标签任意选择时隙的过程与外部标签随机 标签集合。在进行防碰撞控制的同时，还对 到达帧内时隙的过程相互独立。 循环时隙数也就是帧长Ｉ１ｉ进行控制。将时隙 定理２：帧Ｆ．的帧长的计算公式为 计数器ｔｒ设置为１，碰撞时隙计算器ｇｉ＝Ｏ，成 功的时隙计数器Ｓｉ＝０，将记录识别成功标签的 ｎ－一ｒｏｕｎ Ｒ【Ｄ清空。 证明：按照上文中提到的帧效率最优原 （７）对区域内处于不断激活状态的标签 理，Ｆ．中参与识别过程的标签数量与帧长相同， ｋ进行识别，同时对时隙ｔｉｉ进行随机识别，时 也就是说Ｆ 没有识别的标签数ｒｉ一。与Ｆ，内新 隙计数器ｕｋ＝１。 到达识别区域的标签数加起来为 ，帧效率能 （８）阅读器在时隙仃这一位置上发送包 够达到Ｏ．３６８。由此可知，实现帧效率最高的 括ｔｒ目前的数值以及被成功识别标签的Ｒ。。值 条件是Ｆ．中参与识别过程的标签在 个时隙 在内的时隙同步命令ｃ 。 分布的泊松过程的参数为ｌ。参与识别过程的 （９）对处于不断激活状态的标签 标签是由两个泊松过程产生的，且二者互相独 ｓ（ｓ∈Ｔａｇ ｝的ＩＤ 在时隙ｔｒ中是否与Ｃ 中 立。根据泊松叠加原理可知，五 ＋＾ ＝１。Ｆ．．．的 的Ｒ 相等进行比较，如果二者相等，则 １０·电子技术与软件工程Ｅｌｅｃｔｒｏｎｉｃ Ｔｅｃｈｎｏｌｏｇｙ＆Ｓｏｆｔｗａｒｅ Ｅｎｇｉｎｅｅｒｉｎｇ 碰撞，那么ｇｆ＝ｇ。＋ｌ；ｔｒ＝ｔｒ＋１。 （１１）阅读器对仃＝ｎ，进行检查看是否成 立。如果成立，那么转入下一步骤，如果不成 立，则转入步骤８。 （１２）阅读器对本帧外部标签的额到达 率 进行计算，计算公式为 ： ： ～ ！墨！： ： ！ ｎ． 。然后转入步骤４。 ５结束语 针对目前的防碰撞算法中存在的在标签 持续到达时识别效率下降的问题，本文提出了 一种在标签持续到达时能够进行有效识别的 ＣＤＦＳＡ模型及具体算法。该算法具有计算量 小的优势。 参考文献 …１赵曦，张有光．一种新颖的ＲＦＩＤ多标签 防碰撞算法［Ｊ】．北京航空航天大学学 报，２００８，（３）． ［２】刘冬生，邹雪城，李泳生等．射频识别系 统中的防碰撞算法【Ｊ】．华中科技大学学 报（自然科学版），２００６，（９）． ［３］刘子龙，纪金水，刘彩虹等．基于连续碰 撞位探测的防碰撞算法研究［Ｊ］．电子学 报，２Ｏ１ ３，（１１）． ［４】王雪，钱志鸿，胡正超等．基于二叉树的 ＲＦＩＤ防碰撞算法的研究［Ｊ】．通信学报， ２０１０，（０６）． ［５】李志坚，赖顺桥．一种基于碰撞住指示的 射频识别标签防碰撞算法［Ｊ］．电子与信 息学报，２ ０１４，（ｉ２）． 作者简介 刘忠群（１９８１－），男，江苏省丰县人，大学本 科学历。现为江苏省徐州经贸高等职业学校讲 师。研究方向为物联网应用技术、软件技术。 作者单位 江苏省徐州经贸高等职业学校江苏省徐州市 ２２１００４
