推荐星级：
- 1
- 2
- 3
- 4
- 5
基于查询树的防碰撞算法性能分析与研究
资料介绍
多标签碰撞问题严重影响射频识别系统的性能.基于查询树的防碰撞算法作为一种确定性算法被广泛的应用于各类射频识别场景中.本文分析了主流查询树防碰撞算法的性能与不足,并基于查询树方法提出了一种时间有效的防碰撞算法.该算法基于传统查询树识别模型,实施了一种双查询前缀匹配方法,可以消除传统查询树方法中的空闲时隙.此外,提出的算法可以充分利用碰撞时隙来提高识别效率.理论分析和仿真结果表明该算法优于现有的查询树防碰撞算法.
部分文件列表
| 文件名 | 大小 |
| 基于查询树的防碰撞算法性能分析与研究.pdf | 2M |
部分页面预览
（完整内容请下载后查看）11
Vol． 46 No． 11
Nov． 2018
第
期
电
子
学
报
2018
11
ACTA ELECTRONICA SINICA
年
月
基于查询树的防碰撞算法性能分析与研究
1，5
2，4
3
4
5
， ， ， ，
李 川 苏 健 刘克雄 韩 雨 赵红军
( 1.
，
绵阳职业技术学院信息工程系 四川绵阳
621000; 2.
，
南京信息工程大学计算机与软件学院 江苏南京
210044;
3. ， 100083; 4.
北京林业大学工学院 北京
，
电子科技大学通信与信息工程学院 四川成都
611731;
5.
，
西南科技大学信息工程学院 四川绵阳
621010)
:
．
多标签碰撞问题严重影响射频识别系统的性能 基于查询树的防碰撞算法作为一种确定性算法被广泛
摘
要
． ，
的应用于各类射频识别场景中 本文分析了主流查询树防碰撞算法的性能与不足 并基于查询树方法提出了一种时间
． ， ，
有效的防碰撞算法 该算法基于传统查询树识别模型 实施了一种双查询前缀匹配方法 可以消除传统查询树方法中
． ， ．
的空闲时隙 此外 提出的算法可以充分利用碰撞时隙来提高识别效率 理论分析和仿真结果表明该算法优于现有的
．
查询树防碰撞算法
:
;
;
;
关键词
中图分类号
URL: http: / /www． ejournal． org． cn
射频识别 防碰撞 查询树方法 时间效率
:
TP391. 4
:
A
: 0372-2112 ( 2018) 11-2671-08
DOI: 10． 3969 /j． issn． 0372-2112． 2018． 11． 014
文献标识码
文章编号
电子学报
Performance Analysis and Research of
Anti-collision Algorithms Based on Query Tree
1，5
2，4
3
4
5
LI Chuan ，SU Jian ，LIU Ke-xiong ，HAN Yu ，ZHAO Hong-jun
( 1. Department of Information Engineering，Mianyang Polytechnic，Mianyang，Sichuan 621000，China;
2. School of Computer and Software，Nanjing University of Information Science and Technology，Nanjing，Jiangsu 210044，China;
3. School of Engineering，Beijing Forestry University，Beijing 100083，China;
4. School of Communication and Information Science，University of Electronic Science and Technology of China，Chengdu，Sichuan 611731，China;
5. School of Information Engineering，Southwest University of Science and Technology，Mianyang，Sichuan 621010，China)
Abstract: Multiple tags collision problem severely impairs identification performance of RFID systems． Anti-collision
algorithms based on query tree have been widely applied in various RFID scenarios． In this paper，we analyze the perform-
ance and deficiency of mainstream query tree based algorithms． And then，a time efficient anti-collision algorithm based on
query tree is proposed to enhance the identification efficiency． Specifically，the dual prefixes matching method is implemen-
ted based on the conventional query tree identification model，which can significantly remove idle slots． Moreover，the pro-
posed method can also make extensive use of collision slots to improve the identification efficiency． Both theoretical and
simulation results indicate that the proposed algorithm outperforms the existing query tree based algorithms．
Key words: radio frequency identification( RFID) ; anti-collision; query tree( QT) ; time efficiency
［1］
．
签从而实现目标物体的自动识别
当多个标签同时
1
引言
ID
“ ” ，
数据时会产生 多标签碰撞 问题 这
向读写器返回
( Radio frequency identification，RFID)
射频识别
是
．
会导致读写器无法成功识别标签 为了解决这一问题
，
．
一种用于目标自动识别的无线通信技术 一个典型的
，
读写器必须运行相应的防碰撞算法来识别多标签 特
RFID
系统由一个读写器和多个低成本和体积小的标签
， ( unique identifier，
组成 每个标签对应唯一的标识符
RFID
．
别是标签数量密集的
环境
RFID
现有的
多标签防碰撞算法主要可以分为三
UID)
，
并贴在某个物体上 读写器通过双向通信识别标
: 2017-09-19;
: 2018-04-26;
:
责任编辑 蓝红杰
收稿日期
修回日期
:
基金项目 四川省科技计划面上项目
( No． 2018JY0337) ;
( No． 17KJB510036)
江苏省高等学校自然科学研究面上项目
2672
2018
年
电
子
学
报
［2，3］
［4 ～ 6］
， :
类 即 概率性算法
，
确 定 性算 法
和 混 合 型 算
思想 应用最普遍的是动
Aloha( Dynamic framed slotted Aloha，DFSA)
［7，8］
．
Aloha
，
法
概率性算法基于
态帧时隙
． DFSA
算
，
算法的原理是 读写器在每轮识别周期指定
法
F( ) ，
帧长 帧长度大小等于时隙个数 然后向其工作域内
，
的标签广播查询命令 接收到查询命令的标签在
1-F
间
ID
随机选择一个时隙来响应读写器并返回自身的
数
．
据 读写器检测标签响应并统计不同状态下的时隙个
． ，
数 当一帧结束后 读写器根据此轮识别周期的统计结
．
器可以在接收端解码并检测出接收信号的比特信息
，
果来估计剩余标签数并调整相应的帧长 直到所有的
2
．
所示为曼彻斯特编码的一个示例 两个标签的
ID
图
． ‘ ’ ，
标签被成功识别 因为遭受 标签饥饿 问题 概率性算
‘0101’ ‘0011’．
分为别 和
2
当
个标签采用曼彻斯特编
ID
100%
．
的识别率 确定性算法又叫做查询
法并不能确保
( query tree，QT)
树
，
数据时 读写器会
码方式同时向读写器发送它们的
， ，
算法 对于这类算法而言 比特追踪
‘0xx1’， ‘x’ ．
接收到数据 其中 表示碰撞比特 从这个例
［6，7］
ID
，
数据碰撞的具体位置 因
技术
能够使读写器识别
2 3 ．
子中可以看出碰撞比特的位置为第 和第 位 读写器
QT
，
防碰撞算法 诸如碰撞树
( colli-
此被广泛的应用于
检测到的碰撞信息有助于将碰撞的标签分组并更快的
［4］
sion tree，CT) ， ( consecu-
tive collision bit mapping algorithm，CCMA) ，Q
算法 连续碰撞比特映射算法
．
识别它们
［5］
进制搜
，
查询窗树形
［9］
( q-ary search scheme，QAS)
索方法
( Query window tree，QwT)
QT
算法
算法以及它的进化算法
算法相比 上述算法可以实现更好的性
ID
［10，11］
．
，
与传统的
．
，
能 然而 它们的性能高度取决于标签的
分布和碰撞
．
比特位置 混合防碰撞算法融合概率性算法和
QT
算法
，
来实现更好的性能 代价是复杂的读写 器 和 标 签 设
［12］
． QT
，
防碰撞算法的特点是设计简单 无需估计标
计
，
签数 可以保证所有的标签都被成功识别
．
QT
，
防碰撞算法 阐述了已有工作的
本文主要讨论
， ，
原理和性能 分析了目前存在的问题和不足 提出了一
( dual-prefix probe scheme，DPPS)
种双前缀探测方法
RFID
来
2. 2 CT
算法
． DPPS，
系统的识别效率 基于 多个标签可以
提高
［4］
CT
:
读写器检测接收到的数
算法的基本原理是
．
1
QT
在同一时隙内被成功识别 图 所示为传统
算法和
算法的系统传输模型 本质上 读写器可以利用单
，DPPS
，
据的最高碰撞位 并将其分别置为
0
1，
产生新的查
和
DPPS
．
，
，
询前缀并在下一个时隙发送新的查询命令 接收到查
．
次查询命令在同一个时隙探测两个标签 因此
算
ID
询命令的标签只需要返回与前缀匹配后的剩余
QT ，CT
算法消除了查询过程中的
数
． ，
法能够节省总的识别时间 除此之外 不同于已有的多
［5，10］
．
据 同传统
算法相比
空闲时隙 并减少了时隙内的数据传输量 假设当前读
( A，B，C，D，E) ， ID
，DPPS
比特碰撞仲裁机制
来识别标签并彻底消除了多进制查询产生的空闲时
DPPS
能够充分利用碰撞时隙
，
．
5
写器工作域内存在 个标签
其
分别
．
，
隙 理论分析和仿真结果表明 我们提出的
算法
‘00001011’，‘00110110’，‘10011000’，‘11001101’
为
、
在识别效率 通信复杂和系统效率上均优于主流
QT
‘01100100’，
QT
，
算法识别 其识别过程如表
1
和
采用
．
算法
．
所示
2
相关工作
1
从表 中可以看出
CT
5
算法识别 个标签共需要
9
． QT
个时隙
类防碰撞算法的识别过程类似一颗二进制
2. 1
比特追踪技术
［5］
［4，5，10 ～ 13］
，
遍历树 每个标签都可以通过对树的遍历而被探测
，
，
它
比特追踪技术通常基于曼彻斯特编码
ID
树中的根节点到叶子节点的路径对应标签
的每个比
． 0 ‘ -
将单比特数据编码为电平跳变 数据 被编码为 正 负
， ， ．
特 且每个节点具有空闲 成功和碰撞三种状态 由于
’， 1 ‘ - ’， ．
跳变 数据 被编码为 负 正跳变 反之亦然 由于
CT QT ， CT
算法在 算法的基础上消除了空闲节点 所以
‘ ’ ，
曼彻斯特编码中不存在 无跳变 状态 因此读写器可
(
算法所对应的二进制遍历树仅包含碰撞节点 中间节
． ，
以识别并追踪某个碰撞比特 通过这种编码方式 读写
更多>>
最新上传
- 打赏
- 30日榜单
-
21ic小能手 打赏10.00元 1天前
-
21ic小能手 打赏20.00元 1天前
-
21ic小能手 打赏20.00元 1天前
-
注册1 打赏0.01元 2天前
-
注册1 打赏0.01元 2天前
用户：xlhtracy
-
注册1 打赏0.01元 2天前
用户：xlhtracy
-
注册1 打赏0.01元 2天前
用户：xlhtracy
-
注册1 打赏0.01元 2天前
用户：xlhtracy
-
注册1 打赏0.01元 2天前
用户：xlhtracy
-
注册1 打赏0.01元 2天前
用户：xlhtracy
-
注册1 打赏0.01元 2天前
用户：xlhtracy
-
注册1 打赏0.01元 2天前
用户：xlhtracy
-
注册1 打赏0.05元 2天前
用户：xlhtracy
-
注册1 打赏0.01元 2天前
用户：xlhtracy
-
注册1 打赏0.01元 2天前
-
注册1 打赏0.01元 2天前
用户：21ic下载
-
注册1 打赏0.01元 2天前
用户：21ic下载
-
21ic小能手 打赏0.03元 2天前
用户：21ic下载
-
21ic小能手 打赏0.01元 2天前
用户：21ic下载
-
21ic小能手 打赏0.01元 2天前
用户：21ic下载
-
21ic小能手 打赏0.02元 2天前
全部评论(0)