设计 巾国集成电路 Ｃｈｉｎａ Ｉｎｔｅｇｒａｔｅｄ Ｃｉｒｃｕｉｔ
国标超高频窒口协议防碰撞算法建横
及仿真研究
张学磊，孙云龙
（华大半导体有限公司，北京，１０２２０９）
摘要：超高频国标射频识别（ＲＦＩＤ）空口协议使用动态收缩二叉树防碰撞算法（ＤＤＳ—ＢＴ），ＤＤＳ—ＢＴ效率
直接决定国标协议在多标签应用场景下的防碰撞效率。模拟仿真超高频国标协议下标签全盘点的情形，
寻找不同参量对ＤＤＳ－ＢＴ的影响。统计国标协议在推荐参数下盘点不同标签群使用的指令分布，标签数
量与所需盘点命令成线性增加。对比研究不同参数组合情况下ＤＤＳ－ＢＴ算法与推荐参数的效率。ＤＤＳ—ＢＴ
参数随使用环境而定，统计结果基于多次重复仿真，样本足够大，统计分析结果可以为超高频系统应用
设计者及阅读器防碰撞算法开发者提供参考，同时模型也可以用来检验芯片随机数生成器质量。
关键词：射频识别；超高频协议；动态收缩二叉树防碰撞算法
Ｔｈｅ ｍｏｄｅｌｉｎｇ ａｎｄ ｓｉｍｕｌａｔｉｏｎ ｏｆ ＧＢ ＵＨＦ ａｉｒ ｉｎｔｅｒｆａｃｅ
ｐｒｏｔｏｃｏｌ ａｎｔｉ－ｃｏｌｌｉｓｉｏｎ ａｌｇｏｒｉｔｈｍｓ
ＺＨＡＮＧ Ｘｕｅ－ｌｅｉ，ＳＵＮ Ｙｕｎ－ｌｏｎｇ （ＨＵＡＤＡ ＳＥＭＩＣＯＮＤＵＣＴＯＲ Ｃｏ．，ＬＴＤ，Ｂｅｉｊｉｎｇ １０２２０９，Ｃｈｉｎａ）
Ａｂｓｔｒａｃｔ：Ｄｙｎａｍｉｃ ｄｉｓｐｅｒｓｅ ｓｈｒｉｎｋ ｂｉｎａｒｙ ｔｒｅｅ（ＤＤＳ－ＢＴ）ｈａｖｅ ａｐｐｌｉｃａｔｉｏｎ ｉｎ Ｉｎｆｏｒｍａｔｉｏｎ ｔｅｃｈｎｏｌｏｇｙ—Ｒａｄｉｏ ｆｒｅ—
ｑｕｅｎｃｙ ｉｄｅｎｔｉｆｉｃａｔｉｏｎ－ａｉｒ ｉｎｔｅｒｆａｃｅ ａｔ ８００／９００ＭＨｚ（ＧＢ／Ｔ ２９７６８）ｔｏ ｒｅｓｏｌｖｅ ｃｏｌｌｉｓｉｏｎ ａｔ ｔｈｅ ｗａｖｅｆｏｒｍ ｌｅｖｅ１．Ｔｈｅ
ｑｕａｌｉｔｙ ｏｆ ＤＤＳ—ＢＴ ｄｅｆｉｎｉｔｉｖｅ ｔｈｅ ｅｆｆｉｃｉｅｎｃｙ ｏｆ ＧＢ／Ｔ ２９７６８ ｆｏｒ ａｃｃｅｓｓｉｎｇ ｉｎ ｔａｇ ｐｏｐｕｌａｔｉｏｎ．Ｍｏｄｅｌ ｏｎ ＤＤＳ—ＢＴ ａｎｄ ｃａｌｃｕｌａｔｅ ｄｉｆｆｅｒｅｎｔ ｐａｒａｍｅｔｅｒ ｅｆｆｉｃｉｅｎｃｙ ｏｎ ＤＤＳ－ＢＴ．Ｓｔａｔｉｓｔｉｃａｌ ＧＢｆｆ ２９７６８ ｉｎｖｅｎｔｏｒｙ ｃｏｍｍａｎｄｓ ｄｉｓｔｒｉｂｕｔｉｏｎ ｉｎ ｔｈｅ
ｒｅｃｏｍｍｅｎｄｅｄ ｐａｒａｍｅｔｅｒｓ ｏｆ ｄｉｆｅｒｅｎｔ ｔａｇ ｐｏｐｕｌａｔｉｏｎ，ｉｎ ｗｈｉｃｈ ｔｈｅ ｎｕｍｂｅｒ ｏｆ ｔａｇ ａｎｄ ｔｈｅ ｒｅｑｕｉｒｅｄ ｉｎｖｅｎｔｏｒｙ ｃｏｍｍａｎｄｓ
ｌｉｎｅａｒｌｙ ｉｎｃｒｅａｓｅ ｔｈｅ ｎｕｍｂｅｒ ｏｆ ｔａｇｓ．Ｃｏｍｐａｒｅ ｔｈｅ ｅｆｆｉｃｉｅｎｃｙ ｏｆ ＤＤＳ ａｌｇｏｒｉｔｈｍ ｗｉｔｈ ｒｅｃｏｍｍｅｎｄｅｄ ｐａｒａｍｅｔｅｒｓ ｔｉｎｄｅｒ
ｈｔｔｐ：／／ｗｗｗ．ｃｉｃｍａｇ．
ｃｏｍ ｄｉｆｅｒｅｎｔ ｃｏｍｂｉｎａｔｉｏｎｓ ｏｆ ｐａｒａｍｅｔｅｒｓ．ＤＤＳ ａｌｇｏｒｉｔｈｍ ｐａｒａｍｅｔｅｒｓ ｄｅｐｅｎｄｅｄ ｏｎ ｔｈｅ ｕｓｅ ｏｆ ｔｈｅ ｅｎｖｉｒｏｎｍｅｎｔ．Ｔｈｅ ｓｔａｔｉｓｔｉ— ｃａｌ ｒｅｓｕｌｔｓ ａｒｅ ｂａｓｅｄ ｏｎ ｍｕｌｔｉｐｌｅ ｒｅｐｌｉｃａｔｅ ｓｉｍｕｌａｔｉｏｎｓ ａｎｄ ｌａｒｇｅ ｓａｍｐｌｅｓ．Ｔｈｅ ｒｅｓｕｌｔｓ ｏｆ ｓｔａｔｉｓｔｉｃａｌ ａｎａｌｙｓｉｓ ｃａｎ ｐｒｏｖｉｄｅ
ａ ｒｅｆｅｒｅｎｃｅ ｆｏｒ ｄｅｖｅｌｏｐｅｒｓ ｏｆ ＵＨＦ ｓｙｓｔｅｍ ａｐｐｌｉｃａｔｉｏｎ ｄｅｓｉｇｎｅｒｓ ａｎｄ ｒｅａｄｅｒ ａｎｔｉ—ｃｏｌｌｉｓｉｏｎ ａｌｇｏｒｉｔｈｍｓ，ａｎｄ ｔｈｅ ｍｏｄｅｌ
ｃａｎ ａｌｓｏ ｂｅ ｕｓｅｄ ｔｏ ｖｅｒｉｆｙ ｔｈｅ ｑｕａｌｉｔｙ ｏｆ ｃｈｉｐ ｒａｎｄｏｍ ｎｕｍｂｅｒ ｇｅｎｅｒａｔｏｒ．
Ｋｅｙ ｗｏｒｄｓ：ＲＦＩＤ；ＵＨＦ；ＤＤＳ－ＢＴ
１己ｌ言 Ｉ Ｊ Ｉ口
射频识别【ｌＪ（ＲＦＩＤ）是一种无线通信技术，可
以通过无线电信号识别特定目标并读写相关数据，
而不需要识别系统与特定目标之间建立机械或光
学连接。 无线电的信号是通过对无线频率的磁场／电磁
场进行调制，将信号与数据调制于载波之中，射频接
收端解调出信号并通过再次调制的方式进行应答，
从而完成无线射频通信。
在无线通信过程中，经常出现多个应答器同时
处于阅读器的作用范围，在这样的通信系统中需要
阅读器将每个应答器识别出来，通信系统中需要支
持防碰撞机制【２１。常见的多路存取法／防碰撞法包括 空分多路（ＳＤＭＡ）、时分多路（ＴＤＭＡ）、频分多路
（ＦＤＭＡ）及码分多路（ＣＤＭＡ）。超高频国标采用的
是ＴＤＭＡ防碰撞法［３１。ＴＤＭＡ中常见的防碰撞机制
有ＡＬＯＨＡ法嘲、动态时隙法［５１、静态时隙法嘲、二叉树
搜索法等。在超高频国标协议中采用动态收缩二又
树防碰撞机制（ＤＤＳ—ＢＴ）。 为适应超高频在我国的标准化运用，全国信息
技术标准化技术委员会提出并归口了中国超高频空
口协议，编号ＧＢ／Ｔ ２９７６８—２０１３（国标８００／９００ＭＨｚ
空口协议），ＤＤＳ—ＢＴ作为该标准规定的防碰撞算 法具有唯一性。因此研究ＤＤＳ—ＢＴ算法，对国标超
高频协议的推广具有重要意义。
多数仿真模型采用统计时隙值的方式来评价标
签的防碰撞能力，本文根据国标ＤＤＳ—ＢＴ算法的特
点，直接统计盘点过程使用的单一化指令，这样能为 设计人员设计提供更精准的参考。
２ ＤＤＳ－ＢＴ算法分析
ＤＤＳ—ＢＴ防碰撞算法核心是基于树的动态时隙
搜索算法，主要包括重复查询、分裂、分散、收缩等四 个单一化指令。ＧＢ／Ｔ ２９７６８—２０１３对算法的执行步
骤，跳转方式等规定明确，影响算法效率主要有以下
几个方面。 ●随机数的质量，ＤＤＳ—ＢＴ在分裂、分散指令
下，会调用随机数，随机数的质量直接决定算法的效
率。
●ＣＩＮ（连续空闲阈值），ＣＩＮ是阅读器发送指 令，标签连续无响应次数的阈值，ＣＩＮ值影响阅读器
下一条下发指令。
●ＣＣＮ（连续碰撞阈值），ＣＩＮ是阅读器发送指
令，标签连续碰撞次数的阈值，ＣＩＮ值影响阅读器下
一条下发指令。 ●ＣＥＮ（盘点结束阈值），ＣＩＮ判断是否结束本
次盘点循环的值，受单一化指令的影响。
３系统建模
模型系统主要由阅读器模型，标签模型及计算 模型组成，本系统我们选用ｍａｔｌａｂ工具建立算法模
型；主要因为Ｍａｔｌａｂ在该模型中两个主要优势。第
一，使用函数形式，ｍａｔｌａｂ也能自动保存全局变量，
且查看调用简单方便，有利开发人员查验模型算法
是否正确；第二，ｍａｔｌ
ａｂ绘图能力强大，方便数据后 续处理。如图１是为各个模型编写的主要函数，计
算模型控制阅读器和标签模型的运行方式。阅读器
模型和标签模型共用部分指令函数。
图１仿真模型支持的主要函数
３．１阅读器模型
阅读器模型模拟阅读器发送指令及接收标签的
返回信息，在阅读器一标签模型中属于控制主体。
本模型中阅读器模型主要功能有：（１）建立ＤＤＳ—
ＢＴ判定体系，（２）支持所有单一化指令，（３）实时
记录一些重要参数，如连续空闲值、连续碰撞值、盘 点结束值等。为满足以上需求，为阅读器模型编写
控制函数，用来调用单一化指令；编写碰撞判断函 数，处理碰撞情景；编写正常盘点判断函数，处理盘
点成功情景，以及标签无响应判断函数，处理标签无
响应情景；同时，提供一个统计函数，统计标签时隙
计算器为０的标签数量，用来判断标签群接收命令
后处于碰撞、正常相应、无响应之中的何种状态。建
立阅读器参数矩阵变量，记录阅读器参数。
３．２标签模型
标签模型模拟标签接收指令，并对标签自身做
响应动作，在阅读器一标签模型中属于被动接收。
本模型中，标签模型主要功能有：（１）执行阅读器发
送的单一化指令，（２）记录标签重要参数，比如标签
选择标记、标签盘点标记、标签时隙计数器值、标签
所处的状态等。因此为标签模型编写查询、重复查 询、分裂、分散、收缩、ＡＣＫ等响应函数；建立标签参 数矩阵变量。标签模型需要的随机数调用ｍａｔｌａｂ随
机数生成函数得到，同时预留接口，实际应用中，也
可以调用标签真实生成的随机数系列，对评价标签 随机数生成模块实际运用能力做个参考。
３．３计算模型
ＤＤＳ—ＢＴ算法建立起阅读器在访问标签及标签 群时的盘点方法。国标超高频空口协议防碰撞算法
模型的目的即为检验ＤＤＳ—ＢＴ算法盘点标签的能 力和效率。设计计算模型能够计算出标签盘点出全
部标签的消耗，设计的计算流程如图２。国标协议中
一次Ｑｕｅｒｙ指令开启一轮盘点循环，计算模型中，一 次仿真可能开启多次Ｑｕｅｒｙ循环，当所有标签都被
盘点出仿真才结束，设置盘点结束标记、标签全部盘
点标记两个控制参数。同时，建立系统统计矩阵变
量，记录系统运行中产生的重要参数及结果，比如各
单一化指令次数、总的单一化指令次数、总的Ｑｕｅｒｙ
命令次数。 ： 仿真开始 ：
— Ｑｕｅｒｙ引领一次盘 点循环
一＼、 ‰ ／
Ｉ （ 仿真结束 ） （ａ）单次盘点循环 （ｂ）总流程圈 图２流程图
４仿真及统计分析
４．１仿真
影响国标８００／９００ＭＨｚ空口协议ＤＤＳ—ＢＴ防碰
撞算法效率的主要有ＣＩＮ、ＣＣＮ、ＣＥＮ等几个参数，
国标协议对这几个参数给出了推荐值，其中ＣＩＮ推
荐值为４，ＣＣＮ推荐值为３，ＣＥＮ推荐值为２，在本
文的仿真模型中，模拟系统盘点出所有标签需要的
ｈｔｔｐ：／／ｗｗｗ．ｃｉｃｍａｇ．
ｃｏｍ Ｌ！ｊ Ｃ巾ｈｉｎ国ａ Ｉｎ集ｔｅ成电路 设计— ｇｒａｔｅｄ Ｃｉｒｃｕｉｔ ■—●●－ｌ一· —＿．，－ 一一一。一
单一化命令，这样更符合实际运用要求。在仿真中，
分别取ＣＩＮ、ＣＣＮ、ＣＥＮ不同值组合进行仿真，对各
组合进行编号，编号对于关系如表１。其中加粗组合
为协议推荐参数。
表１参数与编号对应关系
ＣＩＮ ３ ３ ３ ３ ３ ３ ３ ３ ３ ＣＣＮ ２ ２ ２ ３ ３ ３ ４ ４ ５ ＣＥＮ １ ２ ３ １ ２ ３ ｌ ２ ３ 编号 １ ２ ３ ４ ５ ６ ７ ８ ９ ＣＩＮ ４ ４ ４ ４ ４ ４ ４ ４ ４ ＣＣＮ ２ ２ ２ ３ ３ ３ ４ ４ ４ ＣＥＮ １ ２ ３ ｌ ２ ３ ｌ ２ ３ 编号 １０ ｌｌ １２ １３ １４ １５ １６ ｌ７ １８ ＣＩＮ ５ ５ ５ ５ ５ ５ ５ ５ ５ ＣＣＮ ２ ２ ２ ３ ３ ３ ４ ４ ４ ＣＥＮ ｌ ２ ３ ｌ ２ ３ ｌ ２ ３ 编号 １９ ２０ ２１ ２２ ２３ ２４ ２５ ２６ ２７
本文分别模拟了５、１Ｏ、２０、５０、１００张标签群，其 中数量为５、ｌ０、２Ｏ、５０的标签群各仿真ｌ０万次，标
签数量为１００仿真１万次，仿真的结果保存到．ｔｘｔ文
件中。
４．２统计分析
４．２．１国标推荐参数下盘点效率
本文首先统计国标推荐的ＣＩＮ、ＣＣＮ、ＣＥＮ值的
仿真结果，以２０张标签群为例。其使用的总的单一
化指令分布如图３。由图可见，全盘点计算模型下 ＤＤＳ—ＢＴ效率符合正态分布，但其分布较广，最小到
３９，最大到１６０，具有随机眭。在国标协议推荐参数
下，完全盘点出２０张标签，盘点出一张标签平均需
要４条单一化指令。
在国标协议推荐参数下不同标签数量的标签
群，其平均需要的总单一化指令分布如图４，总单一
化指令与标签数量成线性分布，标签数量越多，总单
一化指令数值也大。但对应单个标签，其盘点出一
张标签平均所需要的单一化指令数相近，大约为４
个。芯片设计者可根据仿真结果及芯片的单条单一
化指令耗时，以及阅读器的工作模式，大体估算其设 ３５ＯＯ
３０００
２５ＯＯ
２ＯＯＯ
１５００
１０００
５００
０
咖
１ 均值：８０．２２０２ 标签数量：２０个 仿真总次数：１０万次
ｍ－３＊ｏ ｍ＋３ ｏ ４ ｌ ；
｛ Ｉ Ｊ Ｌ
４０ ６０ ８０ １Ｏ０ １２０ １４０ １６０ 单一化命令总数 图３ ｃ ＪＮ＝４、ＣＮＮ＝３、ＣＥＮ＝２单一化 指令总次数正态概率密度分布
／ ／ ／ ／ ／ ／ ／
／ ／ ／
Ｏ ｌ０ ２０ ３０ ４０ ５０ ６０ ７０ ８０ ９０ １Ｏ０ 标签数量 图４ ＣＩＮ＝４、ＣＮＮ＝３、ＣＥＮ＝２单一 化指令总次数随标签数量变化
计的芯片在不同标签数量下盘点出所有标签需要的
时间。
４．２．２参数对效率的影响 在全盘点计算模型下，合适的参数选取对系统
效率提升非常重要。本文对影响ＤＤＳ—ＢＴ算法效率
的三个重要参数不同组合进行仿真，共有２７个组
合。统计分析每个参数下，盘点不同数量标签群平
均单一化指令。为了与国标推荐参数结果更直观比 较。绘制不同参数下仿真结果与国标推荐参数下仿
真结果比值曲线，如图５，水平线以上，说明需要的
平均单一化指令总数比国标推荐算法的要少，绿色
水平线以下则是要多。得到以下结论：
●ＣＩＮ对全盘点计算模型ＤＤＳ—ＢＴ防碰撞算
法效率影响很小，其值越大，效率缓慢减低。 ●ＣＣＮ对全盘点计算模型ＤＤＳ—ＢＴ防碰撞算 Ｏ Ｏ ０ Ｏ ０ ０ Ｏ ０ ０ ０ 牾∞ ∞ 加
５