推荐星级：
- 1
- 2
- 3
- 4
- 5
位屏蔽多叉树搜索射频识别防碰撞算法
资料介绍
针对RFID树型防碰撞算法中时隙数多、数据通行量大等问题,提出了一种改进的多叉树防碰撞算法,阅读器准确检测碰撞位并向标签反馈碰撞位信息,标签对阅读器已知的ID位进行屏蔽,把ID号转换成连续碰撞的序列号.阅读器利用屏蔽位信息和标签返回的碰撞位编码信息,对标签进行分层分类搜索.通过对标签ID进行屏蔽,阅读器和标签间仅发送对方不知道的碰撞位信息.该算法减少了碰撞时隙和识别时隙,避免了空闲时隙,减少了阅读器和标签间的数据通信量.理论分析和仿真结果表明,该算法减少了系统的时隙总数和数据通信量,提高了阅读器的识别效率.
部分文件列表
| 文件名 | 大小 |
| 位屏蔽多叉树搜索射频识别防碰撞算法.pdf | 1M |
部分页面预览
（完整内容请下载后查看）5
Vol． 46 No． 5
May 2018
第
期
电
子
学
报
2018
5
ACTA ELECTRONICA SINICA
年
月
位屏蔽多叉树搜索射频识别防碰撞算法
， ，
莫 磊 陈 伟 任 菊
( 1．
，
成都航空职业技术学院信息工程学院 四川成都
610100; 2．
“ ” ，
四川省高校校企联合 航空电子技术 应用技术创新基地 四川成都
610100)
:
RFID
、 ，
树型防碰撞算法中时隙数多 数据通行量大等问题 提出了一种改进的多叉树防碰撞算法
，
摘
要
针对
，
阅读器准确检测碰撞位并向标签反馈碰撞位信息 标签对阅读器已知的
ID ， ID
位进行屏蔽 把
号转换成连续碰撞的序
ID
． ， ．
列号 阅读器利用屏蔽位信息和标签返回的碰撞位编码信息 对标签进行分层分类搜索 通过对标签
，
进行屏蔽 阅
． ， ，
读器和标签间仅发送对方不知道的碰撞位信息 该算法减少了碰撞时隙和识别时隙 避免了空闲时隙 减少了阅读器
． ， ，
和标签间的数据通信量 理论分析和仿真结果表明 该算法减少了系统的时隙总数和数据通信量 提高了阅读器的识
．
别效率
关键词
中图分类号
URL: http: / /www． ejournal． org． cn
:
;
;
;
;
位屏蔽 射频识别 防碰撞 多叉树 预查询
:
TP301. 6
:
A
: 0372-2112 ( 2018) 05-1200-07
DOI: 10． 3969 /j． issn． 0372-2112． 2018． 05． 027
文献标识码
文章编号
电子学报
A RFID Anti-collision Algorithm Based on
Bit-shield and Multi-tree Search
MO Lei，CHEN Wei，REN Jü
( 1． Chengdu Aeronautic Polytechnic，Chengdu，Sichuan 610100，China;
2． The Innovation Base of School － Enterprise Cooperation Aviation Electronic Technology in Sichuan，Chengdu，Sichuan 610100，China)
Abstract: Focusing on the problem of multi slots and large amount of data traffic in RFID tree anti-collision algo-
rithm，an improved anti-collision algorithm based on multi-tree is proposed． The reader can detect the collision accurately and
send feedback to the tags regarding the collision bits information． The tag shields the known ID bits of the reader and con-
verts the ID number into the serial number of consecutive collisions． The reader makes use of shield bits information and the
collision bits coding information returned by the tags in order to search the tags in a hierarchical classified manner． By shiel-
ding the tag ID，the reader and the tag only sends the collision bits information which the other party unknown． The algo-
rithm reduces the collision time slots and the recognition time slots，avoids the idle time slots，and reduces the communication
data between the reader and the tags． Theoretical analysis and simulation results show that the algorithm reduces the total
slots and data traffic，and improves the recognition efficiency of reader．
Key words: bit-shield; RFID; anti-collision; multi-tree; pre query
［2］
．
， ，
大多数标签为无源标签 能量来自阅读器 处
方法
理能力弱 不具备载波侦测能力 很多传统的防碰撞方
RFID
1
引言
，
，
( Radio frequency identification，RFID)
射频识别
技
，
法不能用于
系统 现阶段的防碰撞方法主要是基
，
术是物联网的核心技术之一 是一种非接触的自动识
， :
于时分多路的方法 主要有 基于
ALOHA
的不确定性
ALOHA
的算
［3］
，
别技术 典型的射频识别系统一般由电子标签和阅读
．
算法和基于搜索树的确定性算法
基于
，
法相对较简单 易于实现 但由于其时隙是随机分配的
［1］
，
器组成
射频识别技术中最关键的问题是多标签识
，
，
， ，
别问题 由于多个标签共用一个信道 当多个标签同时
“ ”
存在某一标签在长期内不能被识别而导致的 饥饿 问
［4］
， ，
向阅读器发送数据时 就会引起数据冲突或碰撞 导致
， ，
题 而且随着标签数量的增加 其性能急剧恶化
．
基
RFID
，
系统不能正常工作 解决冲突的方法就是防碰撞
100%
，
的标签识别率 但存在搜索
于搜索树的算法具有
: 2017-02-04;
: 2018-01-02;
:
责任编辑 马兰英
收稿日期
修回日期
:
基金项目 四川省安全生产科技项目
( No． scaqjgjc_stp_2015004) ;
( No． 15ZA0341)
四川省教育厅科研项目
1201
5
:
磊 位屏蔽多叉树搜索射频识别防碰撞算法
第
期
莫
［5］
，
次数多 识别时间长等问题
．
，
一一对应 与屏蔽寄存器
S
‘0’ ID
的 对应的标签 位为
:
常用的搜索树算法有 基本二进制搜索树
( Binary
，
屏蔽位 与屏蔽寄存器
S
‘1’ ID
的 对应的标签 位为非
［6］
Search，BS)
，
( Dynamic Binary
，
屏蔽位 由标签
ID
算法
动态二进制搜索树
的非屏蔽位组成的序列号称为非屏
［7］
Search，DBS)
，
( Jumping and
．
算法
跳跃式动态搜索树
蔽序列号
［8］
Dynamic searching，JDS)
，
算 法 等 其 中
DBS
算 法 为
， ，
增加屏蔽寄存器 在提高系统性能的同时 也对标
ISO/IEC1443A
， ，
标准推荐的算法 但在实际应用中 这些
，
签性能提出了更高的要求 但屏蔽寄存器占用存储空
，
算法难以完全满足要求 为了提高搜索树算法的识别
，
，
．
间小 计算量不大 以较小的代价获得了较高的性能
2． 1． 2
为了准确的检测标签最高两个碰撞位的数据信
， ， ［9］
效率 很多学者对此展开了研究 文献 中提出一种
编码和译码
， ，
四叉树搜索算法 根据碰撞位信息进行四叉树搜索 相
， ， ，
对二叉树搜索 减少了搜索时隙 但增加了空闲时隙 文
，
息 需要对标签最高两个碰撞位进行编码和译码
．
［10］
献 中提出了一种基于多叉树搜索的防碰撞算法
，
BMS
，
算法中 非屏蔽位就是相应子集标签的碰
在
根据碰撞位的不同来动态选择二叉树搜索或四叉树搜
， ，
撞位 因此 最高两个碰撞位就是最高两个非屏蔽位
．
， ， ［11］
索 但仍有很多空闲时隙 文献 提出
IAMS
，
算法 通
A A ，
0
设标 签 最 高 两 个 碰 撞 位 为
对 应 编 码 为
1
，
过碰撞因子来动态选择二叉树或四叉树搜索 并对四
B B B B ，
1
1
则编码方法如表 所示
．
3
2
0
1
表
编码对应表
， ，
叉树的查询前缀进行优化 以避免空闲时隙 文献
［12］
IAMS
指出
碰撞时隙机会等问题 并提出了
碰撞位进行探索查询和多叉树搜索 但是当遇到非连
算法存在碰撞因子减少了利用四叉树减少
A A
1 0
00
01
10
11
，
CCBD
，
算法 利用连续
B B B B
0
0001
0010
0100
1000
3
2
1
，
，
阅读器接收编码数据 由碰撞位信息就可知道最
，
续碰撞位时 这种方法无能为力
．
， ， :
高两个碰撞位信息 这一过程就是译码 例如 假设接收
，
针对这些方法存在的缺陷 本文提出一种新的算
0XXX，
: “00”、“01”、“10”．
数据为
2． 1． 3
为了描述算法方便 定义了以下几个阅读器请求
则译码为
:
法 位屏蔽多叉树搜索射频识别防碰撞算法
( A RFID
阅读器命令
anti-collision algorithm based on bit-shield and multi-tree
，
search，BMS) ， ，
该算法利用屏蔽寄存器 把阅读器已知的
．
命令
，
标签信息进行屏蔽 把阅读器未知的标签位组成一个
( 1) REQUEST1( NULL) :
，
首次搜索命令 阅读器作
，
从最低位到最高位都连续碰撞的新序列号 并从最高
．
用范围内所有标签响应命令
，
两个碰撞位开始进行预查询和四叉树搜索 避免了空
( 2) REQUEST2( P) :
，
屏蔽预查询命令 屏蔽寄存器
，
闲时隙 提高了搜索效率
．
S
‘1’
P ，
的个数和 的长度相等的标签响应命令 分三
中
2
位屏蔽多叉树防碰撞算法
:
步进行
( a)
S:
P S
的各位取代 的对应
更新屏蔽寄存器
用
BMS
: ，
算法的指导思想是 尽量减少碰撞时隙 完全
‘1’ ．
位
，
避免空闲时隙 尽量减少阅读器和标签 间 的数据 通
( b)
:
编码 对最高两个非屏蔽位进行编码
．
．
信量
( c)
．
标签返回编码给阅读器
，
标签采用曼彻斯特编码 以便阅读器能够准确的
( 3) REQUEST3( Q，L) :
，Q
标签搜索命令
为两位二
．
检测碰撞位
， Q L
进制 非屏蔽位最高两位为 且非屏蔽位长度为 的
， ，
为了减少碰撞时隙 在标签中设置屏蔽寄存器 把
，
标签响应命令 分两步进行
:
，
阅读器已知的非碰撞位屏蔽起来 把剩下的阅读器未
( a)
S:
更新屏蔽寄存器 非屏蔽位最高两位转为屏
ID
，
位组成一个完全连续碰撞的新序列号 并采用
知的
( S ‘1’ ) ．
蔽位 即 最高两个 清零
; ，
后退式四叉树进行搜索 为了避免空闲时隙 对最高两
( b)
．
，
个碰撞位进行预查询 以获知标签最高两个碰撞位的
发送非屏蔽序列号给阅读器
算法步骤
．
阅读器设置堆栈 按先进后出的规则存取数据
; ， ，
准确信息 为了减少数据通信量 通过屏蔽寄存器 标签
2． 2
，
只发送阅读器不知道的碰撞位信息 阅读器在屏蔽某
，
，
层标签后 只发送该层标签的非屏蔽位个数信息
．
，
阅读器设 深 度 寄 存 器 以 区 分 不 同 搜 索 深 度 的
．
2． 1
标签
算法命令
Step1:
，
2． 1． 1
阅读器初始化堆栈为空 阅读器发送请求命
REQUEST1( NULL) ．
令
屏蔽寄存器
，
为了实现本算法 在标签中设置屏蔽寄存器
S，
其
ID
， S
的长度 屏蔽寄存器 的数据和标签
ID
Step2:
ID
，
数据
长度同标签
阅读器作用范围内所有标签返回
全部评论(0)