推荐星级：
- 1
- 2
- 3
- 4
- 5
可并行识别的分组动态帧时隙ALOHA标签防碰撞算法
资料介绍
该文针对现有动态帧时隙ALOHA标签防碰撞算法的系统吞吐率低、算法效率低等问题,提出一种可并行识别的分组动态帧时隙ALOHA(PIGDFSA)标签防碰撞算法。该文以实验为基础,探索了待识别标签数、标签分组数、帧长对系统吞吐率与标签碰撞率的影响,研究了提升系统吞吐率与降低标签碰撞率的策略与方法。结合射频识别(RFID)的多天线系统,引入FastICA技术,从而实现碰撞时隙重新定义,并以此为基础,利用未识别标签数目自适应确定分组数与帧长。仿真结果表明:PIGDFSA算法在标签数达到2000时,算法吞吐率仍能稳定在92%以上,与FSA-256,GDFSA,BSDBG等算法相比具有更高的算法吞吐率,更少的空隙时隙,更高的算法效率。
部分文件列表
| 文件名 | 大小 |
| 可并行识别的分组动态帧时隙ALOHA标签防碰撞算法.pdf | 690K |
部分页面预览
（完整内容请下载后查看）第 40 卷第 4 期
2018 年 4 月
电
子
与
信
息
学
报
Vol.40No.4
Apr. 2018
Journal of Electronics & Information Technology
可并行识别的分组动态帧时隙 ALOHA 标签防碰撞算法
①
①
②
①
袁莉芬*①
①
杜余庆
何怡刚
吕
密
程
珍
(合肥工业大学电气与自动化工程学院 合肥 230009)
②
(德州农工大学 美国德克萨斯州卡城 TX77843)
摘
要：该文针对现有动态帧时隙 ALOHA 标签防碰撞算法的系统吞吐率低、算法效率低等问题，提出一种可并
行识别的分组动态帧时隙 ALOHA(PIGDFSA)标签防碰撞算法。该文以实验为基础，探索了待识别标签数、标签
分组数、帧长对系统吞吐率与标签碰撞率的影响，研究了提升系统吞吐率与降低标签碰撞率的策略与方法。结合射
频识别(RFID)的多天线系统，引入 FastICA 技术，从而实现碰撞时隙重新定义，并以此为基础，利用未识别标签
数目自适应确定分组数与帧长。仿真结果表明：PIGDFSA 算法在标签数达到 2000 时，算法吞吐率仍能稳定在 92%
以上，与 FSA-256, GDFSA, BSDBG 等算法相比具有更高的算法吞吐率，更少的空隙时隙，更高的算法效率。
关键词：射频识别；ALOHA 算法；FastICA；分组；动态帧时隙
中图分类号： TP391.45
文献标识码： A
文章编号：1009-5896(2018)04-0944-07
DOI: 10.11999/JEIT170654
Grouped Dynamic Frame Slotted ALOHA Tag Anti-collision
Algorithm Based on Parallelizable Identification
①
①
①
②
①
YUAN Lifen
DU Yuqing
HE Yigang
LÜ Mi
CHENG Zhen
①
(School of Electrical Engineering and Automation, Hefei University of Technology, Hefei 230009, China)
②
(Texas A&M University, College Station, TEXAS, TX77843, USA)
Abstract: In order to solve the problem of low throughput rate and efficiency of the current dynamic frame slot
ALOHA collision algorithms, a grouped dynamic frame slotted ALOHA tag anti-collision algorithm based on
Parallelizable identification (PIGDFSA) is proposed. Based on the experiments, the method and strategy of
increasing the system throughput rate and lowering the tag collision rate are presented by exploring effects of the
number of the tags and its groups, the frame length on the system throughout and tag collision rate. Combining the
multi-antenna of the RFID system and FastICA technology, the collision slot can be redefined, and the number of
the unrecognized tags can be used to set the number of groups and frame length adaptively. The simulation results
show that the PIGDFSA algorithm can stabilize the throughput rate more than 92% when the number of tags
reaches 2000, and it has higher throughput rate, lesser idle slot and higher algorithm efficiency compared with the
FSA-256, GDFSA, and BSDBG algorithm.
Key words: Radio Frequency IDentification (RFID); ALOHA algorithm; FastICA; Group; Dynamic frame slot
1 引言
RFID)系统中读写器和标签之间进行通信过程中会
产生标签碰撞问题，导致标签的识别准确度、速度
和效率等性能变差，标签防碰撞算法成为了当前
射 频 识 别 (Radio Frequency IDentification,
RFID 系统亟待突破的关键技术之一[1,2]
。
收稿日期：2017-07-05；改回日期：2017-12-06；网络出版：2018-01-23
*通信作者：袁莉芬
基 金 项 目 ： 国 家 重 点 研 发 计 划 “ 重 大 科 学 仪 器 设 备 开 发 ”
(2016YFF0102200)，国家自然科学基金(61102035, 51577046)，国
家自然科学基金重点项目(51637004)，中国博士后特别资助项目
(2015T80651)，中国博士后面上项目(2014M5517)
目前标签防碰撞算法主要有基于时分多路的
ALOHA 算法[3-7] 和树形算法[8-10] 。树形算法识别率
高，但计算复杂，且当标签数多的时候，时间延迟
大
[11]，不适用于密集标签环境下的实时识别。
Foundation Items: The National Key Research and Development
Program “Major Scientific Equipment Development” (2016YFF
0102200), The National Natural Science Foundation of China
(61102035, 51577046), The National Natural Science Fund Project
(51637004), China Postdoctoral Special Project (2015T80651),
Chinese Postdoctoral on the Project (2014M5517)
ALOHA 算 法 主 要 包 括 时 隙 ALOHA(Slotted
ALOHA, SA) 算 法 [12] 、 帧 时 隙 ALOHA(Frame
Slotted ALOHA, FSA)算法[13]、动态帧时隙 ALOHA
(Dynamic Frame Slotted ALOHA, DFSA)算法[14]
第 4 期
袁莉芬等：可并行识别的分组动态帧时隙 ALOHA 标签防碰撞算法
945
dP
n(n -L)æ
1ön-2
等等。其中 SA 与 FSA 标签识别算法的时隙利用率
低，而 DFSA 算法在标签数量很大时吞吐率快速下
降。文献[15]提出将标签分组策略用于 DFSA，使 得
吞吐率能稳定在 34.6%~36.8%之间，但是该算法在
一个时隙中只能识别一个标签，算法效率依然较低。
据此，文献[16]引入了盲源分离技术，可在一个时隙
中识别多个标签，使标签识别效率有了较大的提高。
然而该算法的帧长不符合 ISO/IEC 18000-6 国际标
1
dL
÷
÷
÷
ç
ç
=
1-
(4)
L3
L
ç
è
ø
dP
1
dL
当
= 0 时，L = n ，此时系统吞吐率S = P
1
取得最大值 36.8%，故动态帧时隙 ALOHA 算法取
得最大吞吐率的理想状态就是帧长 L 始终等于标签
数 n。此时空闲时隙和成功时隙各占总时隙数的
36.8%，碰撞时隙为 26.4%。可以看出，理想动态帧
时隙 ALOHA 算法的吞吐率依然很低，特别是随着
标签数目的激增，空闲时隙与碰撞时隙总数快速增
加。
准
[17]。此外，文献[18]引入了马尔可夫链模型加速跳
过无效时隙，其过程较为复杂且需要进行时隙预测。
文献[19]提出了一种动态位隙分组策略，每个标签需
要利用一个 128 bit 的二进制数进行位隙分组，加大
了阅读器的运算负担。
3 基于动态帧时隙 ALOHA 的改进算法
3.1 同时隙多标签并行识别
针对标签防碰撞算法存在吞吐率低、识别效率
低等问题，本文通过对现有标签防碰撞算法进行实
验与理论分析，发现：(1)如果能解决单时隙内多标
签信号识别问题，可大大减少碰撞时隙数目，提升
标签识别率；(2)系统帧长的自适应设置可提升系统
吞吐率；(3)标签分组数的自适应设置可提升系统吞
吐率。为此，本文提出了一种可并行识别的分组动
态帧时隙 ALOHA(PIGDFSA)标签防碰撞算法。该
算法引入 FastICA 技术实现多个标签在单一时隙内
的并行识别，可实现碰撞时隙的重新定义。同时，
在符合 ISO/IEC 18000-6 国际标准相关规定的前提
下，研究动态帧长调整策略以及标签分组策略，以
提升系统的吞吐率与识别效率。
基于独立成分分析的 FastICA 算法是一种盲多
源信号识别算法[20]，将其引入动态帧时隙 ALOHA
算法，可实现同一时隙内多标签的并行识别，从而
将碰撞时隙转化为可辨识时隙。FastICA 能很好地
将源信号从混合信号中分离出来。碰撞时隙信号由
不同标签信号组成，不同标签信号之间相互独立，
信号能量分布为非高斯分布，满足 FastICA 的应用
要求。此外，FastICA 算法具有收敛速度快、形式
简单等优点[21]，可以满足多标签碰撞时隙识别的实
时性要求。
假设某个时隙内有 N(2 £ N £ M )个标签向带
有 M 个天线的阅读器返回其 EPC 编码信号S0 =
S ,S ,,S T ，各天线接收到的多标签混合信号为
[
]
1
2
N
2 动态帧时隙 ALOHA 算法
X = X ,X ,,X T ，经 过 FastICA 算法处理得到
[
]
0
1
2
M
动态帧时隙 ALOHA 算法将时间分成多个相等
的时隙，然后将这些时隙打包成一个帧，每帧包含
的时隙个数称为帧长，阅读器会根据未识别的标签
数，动态地调整下一帧的帧长。假设某个识别帧的
帧长为 L，在阅读器的识别范围内有 n 个标签。假
设某一时隙内，向阅读器返回信号的标签数N = 0 ，
则这个时隙称为空闲时隙；如果 N = 1 ，则这个时
隙称为单标签时隙；如果N ³ 2 ，则称这个时隙为
T
的标签 EPC 编码估计信号为Y = Y ,Y ,,Y
则存在：
，
0
1
2
N
X0 = AS0
Y0 =WX0
(5)
(6)
其中，A 是M ´N 维的混合矩阵，具体形式由信道
特 征 决 定 。W 是 N ´M 维 的 解 混 矩 阵 。 利 用
FastICA 算法可求出解混矩阵W ，进而估计出N 个
标签 EPC 编码信号S0 的估计信号Y0 。其步骤如下：
(1)采集多标签混合信号 X0 的观测信号 X ,
碰撞时隙。所以，空闲时隙P0 ，单标签时隙P ，碰
1
撞时隙P 的概率可分别表示为[14]
f
1ön
X = X ,X ,,X T 由M 个连续信号组成，X =
æ
(
)
÷
÷
÷
0
1
2
M
ç
P0 = 1-
(1)
ç
ç
è
ø
L
T
x ,x ,,x
， 其 中 M 为 天 线 个 数 ， xi =
1
2
M
1 æ
1ön-1
P = Cn1
1-
(2)
(3)
÷
ç
÷
÷
1
ç
ç
x ,x ,x ,,x 为 第 i 个 天 线 的 采 样 值 (其 中
è
ø
i1 i2
i3
il
L
L
1£ i £ M ), l 为采样数据长度。
P = 1-P0 - P
f
1
(2)对观测信号X 进行去均值和白化处理，对观
测信号 X 去均值得 X' :X' = X - E(X) , E(X)为
采集的观测信号的均值。
RFID 系统的吞吐率是指阅读器在一个识别帧
长的时间内可以成功传输信息的时隙数目所占的比
例
[15]，可以用P 表示。将P 求关于L 的导数得
1
1
全部评论(0)