RFID二进制树防碰撞算法的总结

2021年1月29日发(作者：mimir)

南

阳

理

工

学

院

本科生毕业设计（论文）

学院（系）

：计算机与信息工程学院

专

业：

通信工程

学

生：

乔军惠

指导教师：

路新华

完成日期

2012

年

4

月

1

南

阳

理

工

学

院

本

科

毕

业

设

计（论文）

RFID

二进制树防碰撞算法设计

学

院（系）

：

计算机与信息工程学院

专

业：

通信工程

学

生

姓

名：

乔军惠

学

号：

1

指

导

教

师（职称）

：

路新华（讲师）

评

阅

教

师：

完

成

日

期：

2012

年

4

月

南阳理工学院

Nanyang Institute of Technology

2

RFID

二进制树防碰撞算法设计

< /p>

【

摘要

】

射频识 别技术

RFID

是目前正快速发展的一项新技术，它通过射频信

号进行非接触式的双向数据通信，从而达到自动识别的目的。随着

RFID

技术的

发展，如何实现同时与多个目标之间的正确的 数据交换，即解决

RFID

系统中多

个 读写器和应答器之间的数据碰撞，成为了限制

RFID

技术发展 的难题，采用合

理的算法来有效的解决该问题，

称为

< p>
RFID

系统的防碰撞算法。

在各种算法当中，< /p>

二进制树算法因为它识别应答器的确定性，

成为了应用最广泛的一 种，

多个国际

标准均对其进行了规定，

这推动了防碰撞算法的发展，

但是也带来了解决思路不

统一的矛 盾。在传统思路中，一般是通过单片机来进行算法处理，随着

RFID

< br>技

术的发展，未来的一个重要方向是现场可编程门阵列

F PGA

，做为一种现场可编

程的专用集成电路，

FPGA

拥有高速度，可编程等多个适应于算法处理的优点，

< br>从而为

RFID

防碰撞算法问题开辟了新的有效途径根据 上述分析，

全文针对

RFID

系统二进 制树防碰撞算法，进行了理论与实践方面的探讨，主要分为三个方面，

首先是二进制树算 法的理论研究，

将现有的二进制树算法进行了归纳，

汇总为基< /p>

本算法，动态算法，退避式算法三类，阐述了各个算法的思路，对其进行了性能

< p>
评价；

其次，

在现有的三类防碰撞算法的基础上，

提出了一种新的改进型二进制

树算法，该算法识别速度快，执行 效率高，极大的改进了识别效果。

【关键词】

：

射频识别；防碰撞算法；读写器；应答器；现场可编程门阵列

Abstract

RFID is anewly developedtechnologywhich communicates through the

—

contact RF signal

，

so

asto

achieve

objective

automatic

identification

．

Along

with

the

development

of

RFID

technology

，

how

to

realize

Data

Exchange

accurately

amongMultiple

Targets

at

the

same

time

becomes the key problem of RFID technology

．

RFID anti-collision algorithm is the solution to the

above

mentioned

problems

．

In

all

the

algorithms

，

binary

algorithm

is

most

widely

used

as

an

international standard fbr its exactness ofidentincation

．

< p>
International standards have put forward

manyregulations

on

binary

algorithm

．

It

not

onlypromotes

the

development

of

anti

．

coUision

algorithm

，

but

also

b“ngs

the

conflict

to

a

unilFied

solution

．

Traditionalideas

in

general

are

handled byMCU

．

Along with the development ofRFID technology

，

an imponant direction in the

f

．

uture

is

the

field

programmable

gates

arrayFPGA

．

As

kindof

integrated

circuitsthatcanbe

programmed in the field

，

FPGA is fast and programmable

．

All these adVantagesopenup anewef

active way ofRF IDanti

．

collisionarithmetic

．

In viewof the above problems

，

this paperprobes into

the

RFID

systembinary

prevent

collisionf

．

rom

the

perspectives

ofboth

theory

and

practice

．

It

canbediVided into three aspects

< br>：

6rstly

，

theore tical researchon binary algorithm

．

It sums up all

thebinary algorithms in being and gather to three categorys suchas Basic algorithm

，

Dynamic

algorithm and Backoff algorithm

．

MoreoVer

，

it Expounds the idea of the various algorithms and

evalues their perf6rmance

；

secondary

，

it introduces an improved version of algorithm onthe basis

of specinc standard

．

This algorithm has f

．

ast recognition

，

high efnciency and greatly improved

the identification results

．

Key Words

：

RFID

；

Anticollision

；

< p>
Read

／

Write DeVices

；

Transponders

；

FPGA

3

目

录

1

引言

. .................................................. .........

6

1

．

1

RFID

技术简介

< br>............................................... ...

6

1

．

2

RFID

系统

................................................. .....

6

1

< br>．

2

．

1 RFID

< p>
系统组成

............................. ...............

6

1

．

2

．

2 RFID

系统分类

.................... ........................

7

< /p>

1

．

2

．

3 RFID

系统工作原理

........ ................................

8

1

．

3

RFID

技术现状及其发展

..........................................

8

1

．

3

．

1

RFID

技术应用

< br>...............................................

8

1

．

3

．

2 RFID

标准统一化

.................................. ........

9

1

< p>
．

3

．

3 RFID

防碰撞算法

......................... .................

9

< br>1

．

4

课题提出的背景及其意义

........................... ..............

9

1

．

5

本文的主要工作

.................................. ..............

1

0

2

现有

RFID

二进制树防碰撞算法

....................................

11

2

．

1

RFID

防碰撞算法概述

< p>
...........................................

1

1

2

．

2

RFID

二进制树防碰撞算法概述

...................................

1

1

2

．< /p>

2

．

1

基本概念

....................................... .........

1

1

2

．

2

．

2

< p>
性能指标

............................. ...................

1

2

< p>
2

．

2

．

3

算法分类

................... .............................

1

3

2

．< /p>

3

基本二进制树防碰撞算法

< p>
........................................

1

4

2

．< /p>

3

．

1

算法思路

....................................... .........

1

4

2

．

3

．

2

< p>
实例演示

............................. ...................

1

5

< p>
2

．

3

．

3

性能评价

................... .............................

1

7

2

．< /p>

4

动态二进制树防碰撞算法

< p>
........................................

1

9

2

．< /p>

4

．

1

算法思路

....................................... .........

1

9

2

．

4

．

2

< p>
实例演示

............................. ...................

2

1

< p>
2

．

4

．

3

性能评价

................... .............................

2

2

2

．< /p>

5

退避式二进制树防碰撞算法

......................................

2

2

2

．< /p>

5

．

1

算法思路

....................................... .........

2

2

2

．

5

．

2

< p>
实例演示

............................. ...................

2

4

< p>
2

．

5

．

3

性能评价

................... .............................

2

5

2

．< /p>

6

本章小结

. .................................................. ...

2

5

3

改进型二进制树防碰撞算法

.......................................

25

3

．< /p>

1

涉及二进制树算法的国际标准

....................................

2

5

3

．< /p>

1

．

1 IS0 15693

........................................... ...

2

5

3

．

1

．

2 IS014443 < /p>

........................................ .......

2

6

3

．

2

IS014443

标准二进制树防碰撞算法

...............................

2

7

3

．< /p>

2

．

1

基本概念

....................................... .........

2

7

3

．

2

．

2

< p>
算法思路

............................. ...................

2

8

< p>
3

．

3

改进型二进制树防 碰撞算法

......................................

3

2

3

．< /p>

3

．

1

改进方向

....................................... .........

3

2

3

．

3

．

2

< p>
基本概念

............................. ...................

3

2

4

3

．< /p>

3

．

4

实例演示

....................................... .........

3

7

3

．

4

本章小结

......................................... .............

3

9

4 FPGA

实现改进型二进制树防碰撞算法

...............................

40

4

．

1

FPGA

技术

................................................. ....

4

0

4

< br>．

1

．

1 FPGA

< p>
简介

............................... ................

4

0

< br>4

．

1

．

2 FPGA

设计流程

................. ..........................

4

0

4

．< /p>

1

．

3 FPGA

设计工具

.................................. .........

4

2

4

．

1

．

4 FPGA

设计语言

........................ ...................

4

5

< p>
4

．

1

．

5 TestBench

验证平台

......... .............................

4

5

4

．

2

RFID

系统中的防碰撞模块

.......................................

4

6

4

．

3

FPGA

实现算法流程

.............................................

4

6

4

．< /p>

4

曼彻斯特解码模块

< br>..............................................

4

7

4

．< /p>

5

命令处理模块

................................................. .

5

0

4

．

5

．

1

请求 命令处理

................................... .........

5

0

4

．

5

．

2

< p>
防碰撞命令处理

.......................... ................

5

1

< br>4

．

5

．

3

选择命令处理

.................... ........................

5

3

4

．

5

．

4

去选择命令处理

........... ...............................

5

3

4

．< /p>

6

命令选择模块

................................................. .

5

3

4

．

7

数据存储模块

< br>............................................... ...

5

5

4

．

8

密勒编码模块

............................................. .....

5

6

4

．

9

模块连接

............................................. .........

5

7

4

．

10

本章小结

............ .........................................

5

8

结论

....................................... ......................

58

致谢

.............. ...............................................

62

5

1

引言

1

．

1 RFID

技术简介

自动设备识别技术 是目前国际上发展很快的一项新技术，英文名称为

Automatic Equipment Identif ication

，简称

AEI

，它通过一些先进的技术手

段，实现人们对各种设备在不 同状态下的自动识别和管理【

ll

】

。

目前，应用最广泛的自动识别技术大致可以分为光学技术和无 线电技术两

种，

其中光学技术普遍应用于条形码和摄像两大类，

而无线电技术在自动识别领

域

的

应

用

更

具

< p>
体

的

名

称

为

射

频

识

别

，

英

文

名

为

Radio

Frequency

Identification

，

简写 为

RFIDI21

。

RFID

技术通过射频方式进行非接触的双向通

信，

达到 自动识别的目的，

它源起于上世纪四五十年代，

最初是基于雷达 与微波

理论的发展，自从上世纪九十年代以来，

RFID

技术快速发展，得到了广泛的应

用，进入新世纪后，各个国家，组织还 有企业都加大了对

RFID

技术的投入，生

产了大批相应的产品，在多个领域有了成功的应用案例。

RFID

< br>被誉为二十一世

纪的十大战略性产业之一，

可以预想，< /p>

未来

RFID

技术的发展空间是无限广阔 的。

1

．

2 RFID

系统

1

．

2

．

1 RFID

系统组成

根据实际应用环境 ，

RFID

系统结构有多种不同分法，一般来说，一个典型

RFID

系统包括三个部分：前端信息载体，数据交换环节，后端应 用环境【

3

】

。

在具体应用中，前端信息载体有多个名称，如标签

(Tag)

，智能标签

(Smart

Labels)

，射频卡

(RF Ca rd)

等，本文建议采用应答器

(Transponder)< /p>

这种更具普

遍意义的说法。在

RFID< /p>

系统中，应答器放置在待识别的物体上，它内部存储的

信息表征着 该物品的独一性。通常来说，应答器由耦合元件和微电子芯片组成，

主要电气性能为工作 频率，读写能力，数据传输率，信息数据存储量，防碰撞能

力，

信息安全性能等，

应答器的分类也是以这些性能为依据的，

例如 根据存储器

可将应答器分为

EEPROM

，

FROM(

铁电存储器

)

，

SRAM(

静态随机存储器

< br>)

，根据信

息注入方式可分为集成电路固化，

< p>
现场线改写，

现场无线改写，

根据电源供给方

式分为无源，半无源，有源。一般来说，应用最广泛的是无源

+

集成电路固化

+

静态随机存储的应答器。由 于在

RFID

系统中，应答器是大规模生产的。应答器

的典型产品有

TI

公司的

6000

系列，

Philips

公司 的

I

·

CODE

等。数据交换环节

即

RFID

系统中 的读出写入设备，它是系统的核心部件，是后端应用环境和前端

信息载体的数据通道，在 实际应用中，往往被称为查询器，扫描器，阅读器，编

程器等，本文建议采用读写器

(Read

／

Write Device)

这种更具普遍意义的说法，

这样既包括了从应答器中读出信息，

同时也包括了向应答器中写入信息。

根据天

线与读写器模块的分离与否，

读写器可以分为分离式和集成式，

但无论哪种读写

器，其基本结构都是类似的，从硬件部分来说，典型的读写器由三块 组成：射频

通道模块，

控制处理模块，

天线。

后端应用环境主要完成数据信息的存储及处理，

6

它实质上就是一个数据管理系统，也是一个全局控制系统， 一般由

PC

机或者工

作站组成，

同时也包括了应用软件在内，

整个后端应用环境负责接收来自读写器< /p>

的数据，

并进行存储以及相应的处理，

协 同调节多个读写器的工作，

该部分在应

用中常称为中间件

(Savant)

，它扩展了

RFID

系统的应用范围和应用能力，是未

来

RFID

系统智能化，

大型化发展的有力技术支撑，

是

RFID

技术发展的重要方式。

微软公司近年来也介入了

RFID

技 术领域，所瞄准的就是

RFID

系统后端应用的相关软件和服务 。

综上所述，一个典型的

RFID< /p>

系统的组成如图所示：

图

1.1 RFID

系统组成

1

．

2

．

2 RFID

系统分类

RFID

系统依据不同的标准，可以分为很多类别，各个不同的

RFID

系统，在

工作方式和应用范围上，

有着各自不同 的特点，

在应用时要根据实际需要来选择。

几种典型的分类方式 如下所示：

根据作用距离的远近，

R FID

系统可以分为如下三个方面：

(1)

密耦合：典型的作用范围为

0

～

lcm

。

( 2)

遥耦合：典型的作用范围为

lcm

～

1m

。

( 3)

远距离系统：典型的作用范围为

l

～

10m

。

根据工作频率的大小，

RFID

系统可以分为如下四个方面：< /p>

(1)

低频：

30

～

300KHz

，典型应用为

134KHz

。

(2)

高频：

3

～

30MHz

，典型应用为

13

．< /p>

56MHz

．

(3)

超高频：

300MHz~5

．< /p>

8GHz

，典型应用为

2

．

4G

。

< br>(4)

混频：多个频率的混合使用，典型应用为

134K Hz+430MHz

。

根据应答器供 电方式，

RFID

系统可以分为三个方面：

(1)

无源系统：由读写器负责给应答器供电。

(2)

半无源系统：应答器内的电池仅做辅助 作用。

(3)

有源系统：应答器内置 电池负责供给工作电压。

7

1

．

2

．

3 RFID

系统工作原理

< br>RFID

是一门多学科综合技术，涉及到电磁场理论，数字电路，模拟电路，

无线电广播，通信原理等多方面知识

RFlD

系统中，读写器将要发送的信号调制

到载波上，

经由射频通道 ，

通过天线发送出去，

应答器上的电压根据载波的变化

而变化，

将该电压信号进行整流和滤波后，

得到 解调后的数据，

这是下行链路的

过程，

应答器传输的数据的变化控制应答器天线上负载电阻的通断，

从而促使读

写器天线上电压的变化，

从而实现了数据的上行链路传输。

在数据的双向传输过

程中，

是通过电磁场的相互感应来实现 的，

该过程也可以用变压器的模型来予以

参考。同时，根据

RFID

系统的不同，在供电方式上有无源或者有源，调制方式

上有幅度调制或者相位调制，数据读取上有电感耦合或者反向散射等区别【

< br>5

】

。

1

．

3 RFID

技术现状及其发展

1

．

3

．

1 RFID

技术应用

做为一种新兴的自 动识别技术，

RFID

近年来发展很快，在国内国外都取得

了广泛的应用，主要体现在以下几个领域【

6

】

。

(1)

物流管理

．

物流管理是

RFID

技术最具应用前景的领域，近年来提出了一个物联网的概

念，

意在将全球所有的物品信息都用唯一的电子代码来表示，

从而将这些物品都

联系在一起，可以随时随地的识别，追踪，管理这些物品，最终在产 品，用户，

企业和政府之间建立但是该应用涉及到的方面太广，

技术难度很大，

目前还在研

究当中。

(2)

身份识别

利用

RFID

技术，将应答器嵌入到身份证，护照等各种证 件当中，甚至植入

动物皮毛，

用来跟踪和识别目标。

< p>
这方面应用的典型例子是我国目前实行的二代

身份证，它基于

ISO

／

IEC14443

标准定义的

TYPE

B

类型卡。

RFID

在身份识别方

面的主要问题是频段 的局限性，

一般使用的是

l35KHz

和

13

．

56MHz

< br>的工作频率，

这是因为过高的频段容易带来对人体有害的电磁辐射。

(3)

防伪应用

应答器在防伪应用中有识别快速，

伪造难，

成 本低等优点，

再加上安全认证

和加密功能，就可以大大提高伪造 的难度和成本，同时，在识别的时刻，可以通

过读写器的快速阅读功能，

在瞬间得出所有物品的信息，

并加以记录和处理。

目< /p>

前在日本和欧洲已经有了类似的应用。

(4)

交通管理

交通管理是

RFID

最先应用的领域，目前已经拥有了成熟 的技术，它利用了

应答器便捷快速识别，

可靠性高，

< p>
安全性强的特点，

目前主要应用范围是电子车

票， 高速公路收费等方面，在我国深圳，基于

RFID

技术的高速公 路收费系统已

经得到了成功的应用。

RFID

< br>技术的应用远不止以上提及的四个方面，它在诸如

生产线自动化管理，

< p>
门禁系统，

新生婴儿防错管理，

地理信息标识等多 个方面都

有着广泛应用，可以毫不夸张的说，

RFID

技术有着良好的发展前景，它孕育的

8

经济效益将是超乎想像的。

1

．

3

．

2 RFID

标准统一化

RFID

最初是各个厂家在各自的独立标准下开发出来的，缺乏统一的规范，

因 此制约了该项技术在大规模系统中的应用，随着

RFID

技术的 发展，参与到其

中的国家，组织，企业也越来越多，目前形成了国际标准化组织

ISO

，泛在

ID

中心

UID

，

全球电子产品代码管理中心< /p>

EPC

三大标准体系，

这些标准涉及到< /p>

RFID

系统的物理结构，

通信协议，< /p>

防碰撞算法，

应用系统接口协议等等多个方面的内

容，

它们针对不同的频率，

基于不同的工作原理，

甚至在同样的应用背景下也有

着巨大的协议上的区别。而要建立一个 全球互联的

RFID

产品网络，实现

R FID

技术的飞跃发展，就必须解决标准不统一的难题，近年来，随着

< br>RFID

技术的应

用越发广泛 ，

有识之士都意识到并着手解决这个问题，

目前主要有两种思路 ，

一

是生产出适应于不同标准，多制式兼容的

< br>RFID

产品，二是制定一个统一的

RFID

< p>
硕十学位论技术标准。但是

RFID

本身的技术难 度，以及标准带来的经济利益的

冲突，

使得该目标实施起来非常 困难。

由此可见，

标准统一化问题的重要性与困

难性是并存的，这将是一个任重而道远的过程。

1< /p>

．

3

．

3 RFID

防碰撞算法

随着

< p>
RFID

技术的发展，多目标识别成为了一个很重要的应用方向，特别在< /p>

目标跟踪，物品识别，访问控制等操作中，利用

RFID

技术，对附着在不同目标

上的应答器快速可靠的进行识别，

从而大大提高了定位的精确度，

管理的自动化

促进了 整个产业链的发展。

因此，

如何保证迅速快捷，

又安全可靠的同时识别多

个目标，

就成为了

< p>
RFID

技术发展的关键性技术。

在

RFID

系统中，

当工作范围内

同时出现了多个读写器和多个应答器时，

读写器与读写器之间，

应答器与应答器

之间的相互干扰，

称

RFID

系统发生了碰撞

【

7

】

，

从而导致数据不能正确的传输，

信息无法得到正确的读取，

一方面影响了产品的识别，

< br>另一方面还可能导致信息

的泄露。在全球信息安全意识广泛普及的背景下，可靠的 安全机制成为了

RFID

技术发展的关键性制约因素，如何有效 的解决

RFID

系统的碰撞问题，成为了技

术的关键，

对此就需要采用一定的防碰撞算法来对其进行处理。

目前关于防碰撞

算法的研究还在进行当中，

理论成果已经得 出了很多，

许多国际标准也对一些成

熟的算法进行了规定，

但是无论在理论效率还是实际应用上，

都还存在很大的改

< p>
进空间。

1

．

4

课题提出的背景及其意义

< br>早期的

RFID

技术很少涉及到防碰撞问题，

< p>
而在近年来，

随着

RFID

技术的发

展，应用范围的扩大，使得防碰撞问题日益成为制约

RFID

发展的关键技术，原

因有两个，首先，早期的

RFID

一般是近距离感应耦合式系统，其操作频率功率

普遍较低，

读取的速度慢，

范围小，

< br>所以也较少有发生碰撞的可能，

而目前

RFID

应用中多目标识别成为了主流方向，

这就要求实现在多个物品中正确的识 别出单

个目标；

其次，

早期的

RFID

应用没有统一的规范，

各个厂家的

RFID

产品也仅是

9

应用在单个的系统当中，不存在碰撞的可能，而近年来

RFID

应用迅速发展，各

个不同

RFID

制造商的产品之间的不兼容，也带来了碰撞问题。总之，由于多 目

标识别应用的需要，

RFID

系统防 碰撞问题成为了关键技术，为了解决碰撞，可

以从硬件和软件两方面着手，由于

RFID

系统的大规模应用限制了成本，所以，

硬件实现是不实际的，

因此就需要采用一定的防碰撞算法来予以解决。

< br>依前所述，

RFID

系统碰撞主要有两种情况，读写器碰 撞和应答器碰撞，读写器碰撞是一个

应答器同时收到不同读写器发出的命令，

< p>
应答器碰撞是一个读写器同时给不同应

答器发送命令。在实际的应用当中， 应答器由于其低成本的优越

,

从而得到大量

的生产，

而读写器往往是固定在系统的某处，

来识别多个应 答器，

所以碰撞的主

要情况是应答器碰撞，

即一个读写器的工作范围内同时出现了多个应答器，

并且

对 该读写器发出的命令同时予以响应，

从而导致读写器无法正确的识别出一个应

< p>
答器，

称该现象为发生了应答器碰撞。

解决碰撞的 过程相应的被称为防碰撞，

如

前所述，该防碰撞过程主要从软件 的角度来予以解决，称为防碰撞算法【

8

】

。

在上述前提下，

基于应答器的 确定型二进制树防碰撞算法是目前最好的一种

选择，对其进行研究，是最有实际应用价值 的，所以，本文将对其进行理论分析

与具体实现，在研究过程中，注重与新一代智能

RFID

系统的结合，应用拥有强

大功能的

FPGA(FieldProgrammable

GateA rray)

做为算法运行的微处理器，这种思路将是未来

RFI D

技术发展的重要

方向，

RFID

技术中的关键算法与先进的电子技术

FPGA

的结合，将为

RFID

技术

的应用拓 开广阔的前景。

1

．

5

本文的主要工作

本文将在

RFID

技术的前提下，结合当前数字电路设计的主流思路，重 点研

究

RFID

的关键技术防碰撞算法 ，并主要着眼于其中基于应答器的确定性算法，

即二进制树防碰撞算法，

在理论分析的基础上，

对其进行具体实现。

基于上述考

虑，论文将分四章来予以讲述，文章结构与内容安排如下：

< /p>

第

1

章：

绪论。

系统的介绍了

RFID

技术，

描述了典型

RFID

系统的结构组成，

提出了

RFID

系统的分类思想，讲述了

RFID

系统的工作原理，以及其应用范围，

重点强调了

RFID

技术的现状和所面临的主要问题，

由此体现了研究

RFID

关键技

术防碰撞算法的意义，明确了本文的主要研究内容。

第

2

章：

现有

RFID

二进制树防碰撞算法。

概要性的描述了

RFID

防碰撞算法，

对其进行了分类，

重点介绍其中的二进制树防碰撞算法，

研究了三种最基本的二

进制树算法，对其进行了原理阐述，性能分析，以及实例演示。

第

3

章：

改进型二进制树防 碰撞算法。

二进制树防碰撞算法在多个国际标准

中均有规定，基 于

IS014443

标准的

TYPEA

是其中的一个典型例子，本章首先介

绍了涉及到二进制树防碰撞 算法的几个标准，其次详细研究了

ISOl4443

标准对

二进制树防碰撞算法的规定，

最后提出了在此基础上的改进算法，< /p>

这也是本章的

重点。

< br>第

4

章：

FPGA

实现改进型二进制树防碰撞算法。

FPGA

技术是目 前数字电路

设计的主流思路，

利用

FP GA

做主处理器，

是

RFID

技术发展的方向，

本章探讨了

这一想法，介绍了

FPGA

技术的相关要点，并应用

FP GA

，实现了改进型二进制树

防碰撞算法。

10

2

< br>现有

RFID

二进制树防碰撞算法

2

．

1 RFID

防碰撞算法概述

RFID< /p>

系统的数据通信双方是读写器和应答器，在实际的

RFID

系统工作时，

可能会出现同时多个读写器和多个应答器共存的情况，< /p>

毫无疑问，

此时系统的数

据交换就会出现 信道与时序上的重叠，

也就是发生了碰撞，

在多个读写器与多个

应答器的射频识别系统中，

存在着两种形式的冲突方式，

一种是同一应答器同时

收到不同读写器发出的命令，

< br>另一种是同一个读写器同时收到多个不同应答器返

回的数据，前者我们称为读写器 碰撞，后者称为应答器碰撞【

9

】

，在 实际应用当

中，

一般是读写器做为主设备，

来识别多个应答器，

所以发生读写器碰撞的应用

场合是不多 的，因此下文将着重研究应答器碰撞。

在上述前提下，

有两种类型的通信方式，

一种是读写器发送的数据同时被多

< p>
个应答器接收，称为“无线广播”

，另一种是多个应答器的数据同时传送给 读写

器，称为“多路存取”

，两者都是无线电技术中长期面临的 难题，同时也发展出

一系列相应的解决思路，

一般来说分为四种 ，

即空分多路

(SDMA)

，

码分多路

(CDMA),

频分多路

(FDMA)

，时分多路

(TDMA)

，从

RFID

系统的通信形式、功耗、系统复杂

性以及成本多方面综合考虑，时分多路法是最有实际应用价值的，它也是目前

RFID

防碰撞算法应用中最广泛的一类，时分多路法的基本思想是把整个可供 使

用的通路容量按时间分配给多个用户，从而达到在不同时隙将各个应答器一

< p>

一识别出来的目的【

11

】

。时分多路法按照能量的供给者可以分为两大类，

一类是应 答器驱动型，另一类是读写器驱动型，这也正是对应了第一章中

RFID

系统分类思路中的有源系统和无源系统，

根据实际应用情况，

< br>无源系统是应用最

广泛的一类，

所以下文重点研究读写器 驱动型的时分多路法。

在该类读写器驱动

型时分多路法中，

目前最常用的防碰撞算法有两种，

一类是基于时隙

< br>ALOHA

的统

计型算法，

另一 类是基于二进制树的确定型算法，

统计型算法的意义是在一定的

时隙范围内，

系统有可能识别出所有应答器，

确定型算法的最大 优点是，

在一定

的时隙范围内，系统一定可以将所有的应答器一 一识别出来【

13

】

。从应用的角

度来说，

正确有效的识别是实际所需要的，

因此下文将着重于二进制树防碰撞算

法的研究。

2

．

2 RFID

二进制树防碰撞算法概述

2

．

2

．

1

基本概念

在

RF ID

防碰撞算法中，二进制树算法是目前应用最广泛的一种，之所以称

< br>为“二进制树”

，是因为在算法执行过程中，读写器要多次发送命令给应答器，< /p>

每次命令都把应答器分成两组，

多次分组后最终得到唯一的一个应 答器，

在这个

分组过程中，

将对应的命 令参数以节点的形式存储起来，

就可以得到一个数据的

分叉树，

而所有的这些数据节点又是以二进制的形式出现的，

所以称为< /p>

“二进制

树”

。

11

为了便于描述算法，声明一些 基本概念如下：首先，在

RFID

系统当中，每个应

< p>
答器都是独一无二的，

它们的独立性通过唯一的自身序列号来体现，

该序列号在

不同的标准中有不同的名称，如

E PC

标准中称其为电子产品代码

EPC

，即英文

ElectronicProduct Code

的缩 写，

IS014443

标准中称其为唯一标识码

UID

，即

英文

Unique Identmer

的缩写【

15

】

。事实上，这些都是对应答器序列号的名称

描述，

< br>因为下文涉及到的防碰撞算法是普遍意义上的，

既包括了

EPC

标准中的规

定，

也包括了

ISO

标准中的规定，

因此在本文对普遍意义 上的防碰撞算法的描述

过程中，统一用序列号

SN(Seria lNumber)

来描述上述概念，同时，序列号的长

度，格式 ，以及编码方式也是各个标准各自差异的，为了说明的便利，统一定义

为

8

位长度的

二进制码。如图

2

．

1

所示。

图

2

．

1

应答器序列号数据格式

读写器与应答 器之间进行数据交换时，往往要传输序列号的部分或者全部

位，此时的传输顺序定义为： 先发送低位，再发送高位。在读写器或者应答器内

部，对数据进行比较时，遵循这样的原 则，即按位依次比较，先比较低位，再比

较高位，约定

0<1< /p>

，根据这个比较顺序，在判断大小时，低位数据优先，即两数

A< /p>

，

B

相比较，从低位开始的第一个不相等 位的大小决定了两数的大小，只有当

两个数的全部位均相等时，两数才相等。

< p>

2

．

2

．

2

性能指标

定义碰撞解决时期

CRI

，即

Collision

Resolution

Interv al

【

16

】

，即解决

一个读写器工作范围内碰撞所需要的时隙数，

对二进制 树算法的评价，

一些常用

的性能指标如下所示【

17

】

：

< br>首先是算法执行效率

，定义如下：在算法执行过程，一共

个时隙，识别

了

n

个应答器，则

=n/

表示算法的执行效率。

分析如下：

n=l

，显而易见，在第一个时隙内不发 生碰撞，可以成功识别该

应答器，

=1

。

n

≥

2< /p>

，

由于应答器序列号的唯一性，

将有碰撞 发生，

在一个时隙内发生碰撞

的概率

p

是一个随机事件，在

n

个应答器信息包 中

i

个发生碰撞的概率为：

给出

i

个碰 撞，则

CRI

的长度为：

其中

1

是< /p>

n

个信息包最初的一个时隙，

是

i

个碰撞的顺利传输的时隙，

12

是

n-i

个无碰撞传输的时隙。

由上式可知，

是逐渐递归的，通过递归可得：

根据式

(2.3)

，上式可化为：

由此可见，

是关于

< br>p

的函数，则

=n/

也是关于< /p>

p

的函数，一般情况下，

可以参考二项分 布，将

p

取为

1

／

2

。

算 法的第二个重要的性能指标是稳定性，显然，基于

TDMA

的二 进制树防碰

撞算法是沿着时间轴线来执行协议的，有一系列的碰撞解决时期

CRI

，定义一个

随机变量

，表示第

k

个

CRI

< br>的长度，这些

…………形成一个马

尔可夫链

(Markovchain)

，

因为第

个

CRI

的长度由它开始的第一个时隙传输的

信息，

也就是在

k

个

CRI

区间内到达的信息包决定的，

所 以，

如果马尔可夫链满

足遍历性分布，那么这个系统就可以说是 稳定的。

马尔可夫链遍历性分布要满足下列两个条件【

18

】

：

这里有：

也就是

n

个 信息包从发生碰撞开始传输的

CRI

区间长度的数学期望，

是

在一个时隙内到达这个系统信息包的期 望值，该过程属于泊松过程【

l9

】

。 一般

来说，

在二进制树防碰撞算法中 ，系统都能够满足马尔可夫链的两个遍历性分布条件，

即作为一种确定型的算法，

二进制树防碰撞算法是稳定的。

算法的第三个重要性

< br>能是系统通信复杂度，

显而易见，

系统的通信双方是读写 器与应答器，

则通信复

杂度也应该从这两方面着手考虑，即读写 器与应答器各自发送的数据位的位数。

该指标的评价标准是基于能量消耗的角度的，

即发送的数据信息量越少，

则整个

系统消耗 的能量也越少，这显然是一个理想的效果。

2

．

2

．

3

算法分类

在基本的二进制树搜索算法的基础上，

有多种形式的二进制树搜索算法，

它

13

们之间主要的区别在于命令的数据形式，主要有两点。

(1)

命令参数是

1bit

< br>数据，还是多

bit

数据。

< /p>

(2)

命令参数长度是固定的，还是变化的。

图

2

．

2

是一个二进制树搜索算法的分类图，在基本二进制树的基础上，按

照命令参数分为

1bit

和多

bi t

，根据传输的命令参数的长度分为定长二进制树

和动态二进制 树两种，

根据二进制树遍历时是一轮前进到底的还是退避返回的分

为前进二进制树和退避二进制树两种。

需要说明的是，

这只是 一个大略的分类法，

主要目的在于说明二进制树分类的基本原则。

事实上，

分类所得的这些算法中也

有互相重合的，

< p>
如动态二进制树算法既可以采用前进思路，

也可以采用退避思路。

另外，在具体应用时，可能还存在多种不同的说法，如

lbit

长二进制树中还有

修正二进制树

MBBT

，加强二进制树

EBBT

等区别【

< p>
20

】

。

图

2

．

2

二进制树算法分类

2

．

3

基本二进制树防碰撞算法< /p>

2

．

3

．

1

算法思路

定义两个具有普遍意义的命令来描述算法：

< br>(1)

请求命令

Request(SN)

：

该命令携带一个参数

SN

，

应答器接收到该命令，

将自身的

SN< /p>

与接收到的

SN

比较，若小于或者等于， 则该应答器回送其

SN

给读

写器。注：

Request(SN)

初始值设为

R equest(11111111)

。

(2)

休眠命令

Sleep(SN)

：该命令携带一个参数

SN

，应答器接收到该命令，

< p>
将自身的

SN

与接收到的

SN

比较，若等于，则该应答器被选中，进入休眠状态，

也即是 不再响应

Request

命令，

除非该 应答器通过先离开读写器工作范围再进入

的方式重新上电，才可以再次响应

Request

命令。

基 本二进制树算法的流程图如图

2

．

3< /p>

所示：

14

图

2

．

3

基本二进制树算法流程

基本二进制树算法的步骤如下：

(1)

应答器进入读写器工作范围，

读写器发出一个最大序列号，

所有应答器

的序列号均小于该最大 序列号，所以在同一时刻将自身序列号返回给读写器。

(2)

由于应答器序列号的唯一性，

当应答器数目不小于两个 时，

必然发

生碰撞．发生碰撞时，将最大序列号中对应的碰撞起 始位设置为

O

，低于该位者

不变，高于 该位者设置为

l

。

(3)

读写器将处理后的序列号发送给应答器，

应答器序列号与该值比较，

小

于或等于该值者，将自 身序列号返回给读写器。

(4)

循 环这个过程，

就可以选出一个最小序列号的应答器，

与该应答器 进行

正常通信后，

发出命令使该应答器进入休眠状态，

即除非重新上电，

否则不再响

应读写器请求命令 。

也就是说，

下一次读写器再发最大序列号时，

该应答器不再

响应。

(5)

重复上述过程，即可按序列号从小到大依次识别出各个应答器。

注：

第五步时，

从步骤

1

开始重复，

也就是说，

读写 器识别完一个应答器后，

将重新发送原始的最大序列号。

2

．

3

．

2

实例演示

根据上述 分析，

下面给出一个基本二进制树搜索算法的实例演示，

如图< /p>

2

．

4

所示。

假设

RFID

系统中有一个读写器

R

，四个 应答器

Tl(10100101)

，

T 2

15

(10l01101)< /p>

，

T3(11010101)

，

T4(11101101)

，在某一时刻，四个应答器

< br>

同时进入读写器的工作范围之内，

读写器发出命令，< /p>

四个应答器同时响应，

由于

< p>
其序列号

SN

的唯一性，将发生应答器碰撞，从而 启动防碰撞循环，分析如下：

图

2.4

基本二进制树算法实例

注：

图中共有四轮循环，

依次识别出四个应答器，

分 别以不同格式的线条表

示，并加有循环轮次的数字标识。

( 1)

启动第一轮循环，读写器发送

Request(1lll1 111)

命令，所有应答器响

应该命令，将自身序列号与该

SN(1l1l1111)

比较，均小于该值，于是所有应答

器均返回自身序列号给读写器，

因为序列号的唯一性，

应答器返回的序列号在读

写器接收端发生碰撞，读写器检测到返回数据为

lXXXXl0l

，其中

X

< br>表示该位发

生了碰撞，读写器做如下处理：将碰撞起始位

D4

位置

0

，低于该位者不变，高

于该位者置

l

，得到

11ll0l01

，作为下一次

Request

命令携带的参数值，即

Request(11110l01)

。

(2)

读写器发送

Request(11110101)

命令，所有应答器响应该命令， 将自身

序列号与该

SN(11110l01)

< br>比较，其中

T1(10l00101)

，

T3(1l010101)

的序列号小

于该值，则

Tl

，

T3

返回自 身序列号给读写器，在读写器接收端发生碰撞，读写

器检测到返回数据为

1XXX0l01

，读写器做如下处理：将碰撞起始位

D5

位置

0

，

低于该位者不变，

高于该位者置

l

，< /p>

得到

11l00l01

，

作为下一次

Request

命令携

带的参数值，即

Request(11100101)

。< /p>

(3)

读写器发送

Request(11100101)

命令，所有应答器响应该命令，将自身

序列号与该

SN(111 00l01)

比较 ，其中

Tl(10100l01)

的序列号小于该值，则

Tl

返回自身序列号给读写器，

在读写器接收 端不发生碰撞，

读写器检测到返回数据

为

10100101

，读写器做如下处理：将该数值作为下一次

Sleep

命令携带的参数

值，即

Sl eep(10100101)

。

(4 )

读写器发送

Sleep(10100101)

命令，所有应答器响应该命令，将自身序

列号与该

SN (10l00111)

比较，

其中

T1 (10l00101)

的序列号等于该值，

则

< br>T1

执行

该命令，进入休眠状态，即除非重新上电，否则 不再响应

Request

命令。

16

(5)

启动第二轮循环，读写器发送

Request(111l1111)

< br>命令，除

T1

外所有应

答器响应 该命令，将自身序列号与该

SN(11111l11)

比较，均 小于该值，于是所

有应答器均返回自身序列号给读写器，

因为序 列号的唯一性，

应答器返回的序列

号在读写器接收端发生碰撞， 读写器检测到返回数据为

1XXXXl01

，其中

X

表示

该位发生了碰撞，读写器做如下处理：将碰撞 起始位

D4

位置

0

，低于该位者不

变，高于该位者置

1

，得到

11110101

，作为下一次

Request

命令携带的参数值，

即

Request(11110101)

。

< br>(6)

读写器发送

Request(11110101)

命令，

．

除

T l

外所有应答器响应该命令，

将自身序列号与该

SN(11l10101)

比较，其中

T3(1l01 0l01)

的序列号小于该值，

则

T3

返回自身序列号给读写器，在读写器接收端不发生碰撞，读写器检测到返

回数据为

110l0101

，读写器做如下处理：将该 数值作为下一次

Sleep

命令携带

的 参数值，即

Sleep(11010101)

。

(7)

读写器发送

Slee p(1l010101)

命令，所有应答器响应该命令，将自身序

列号与该

SN(110l

0101)

比较，其中

T3(11010101)

的序列号等于该值，则

T3

执行该命令，进

入休眠状态，即除 非重新上电，否则不再响应

Request

命令。

(8)

启动第三轮循环，读写器发送

Request(11111111)

命令，除

T1

，

T3

外所

有 应答器响应该命令，将自身序列号与该

SN(1111ll11)

比较，均小于该值，于

是所有应答器均返回自身序列号给读写器，

因为序列号的唯一性，

应答器返回的

序列号在读写器接收端 发生碰撞，读写器检测到返回数据为

1X101101

，其中< /p>

x

表示该位发生了碰撞，读写器做如下处理：将碰撞起始位

D7

位置

0

，低于该 位

者不变，

高于该位者置

1

< p>
，

得到

10101101

，

作为下一次

Request

命令携带 的参数

值，即

Request(10101101)

< p>
。

(9)

读写器发送< /p>

Request(10101101)

命令，除

< br>Tl

，

T3

外所有应答器响应该 命

令，将自身序列号与该

SN(10101101)

< p>
比较，其中

T2(10101101)

的序列号等 于该

值，则

T2

返回自身序列号给读写 器，在读写器接收端不发生碰撞，读写器检测

到返回数据为

l0 101101

，读写器做如下处理：将该数值作为下一次

Sle ep

命令

携带的参数值，即

Sleep (10101101)

。

(10)< /p>

读写器发送

Sleep(10101101)

命令，所有应答器响应，将自身序列号与

该

SN(1010 1101)

比较，

其中

T2(1010 1101)

的序列号等于该值，

则

T2

执行该命令，

进入休眠状态，即除非重新上电，否则不再响应< /p>

Request

命令。

(11)

启动第四轮循环，读写器发送

Request (1l111111)

命令，除

Tl

，

T3

，

T2

外 所有应答器响应该命令，将自身序列号与该

SN(11l1l111)

< br>比较，均小于该值，

则所有应答器均返回自身序列号给读写器，因为只有应答器< /p>

T4

返回数据，所以

在读写器接收端不发 生碰撞，读写器检测到返回数据为

11101101

，读写器做 如

下处理：将该数值作为下一次

Sleep

命令携带的参数值，即

Sleep(1l1

01101)

。

(12)

读写器发送

Sleep(1ll 01101)< /p>

命令，所有应答器响应，将自身序列号

与该

SN(11101l01)

比较，其中

T4(1l1 011 01)

的序列号等于该值，则

T4

执行 该

命令，进入休眠状态，即除非重新上电，否则不再响应

Req uest

命令。

2

< br>．

3

．

3

性能评价

假设工作范围内有

N

个应答器存在，

通过基本二进制树搜索算法进行防碰撞

操作，依次识别出所有应答器。循环次数

定义为在整个防碰撞循环过程中的循

17

环轮次，

也即是二进制树的遍历次数。

根据前面的分析可知，

做为一 种确定性的

算法，

基本二进制树一轮循环总能识别出一个应答器 ，

所以在

n

个应答器的前提

< p>
下，经过

n

次循环可以识别出

N

个应答器，所以整个过程中的循环次数为

n

．

搜索次数

定义为算法执 行命令的次数。

也即是二进制树的节点数目。

该值

可以用式子

来表示【

21

】

，其中

Integ

表示取整。

通信时间

t

定义为数 据交换的时间，

也即是命令执行的时间。

假设有

n

个应

答器，从读写器到应答器的传输时间为

tl

，反之为

t2

．总 时间为

t

，则传输的

总时间

< p>
t

可以用式

2.8

来表示 【

22

】

：

数学归纳法证明如下：

< p>
假设只有一个应答器，则读写器发送命令，应答器响应，无碰撞，识别出应

答器。

假设有两个应答器，则读写 器发送命令，两个应答器响应，发生碰撞，为第

一次过程，该时间为：

< br>

读写器修改命令参数，发出命令，仅一个应答器响应 ，则识别出该应答器，

这一次过程时间与前一次一致，

读写器再发送命令，

最后一个应答器响应，

得 到

识别，时间也是一样的，则总时间为：

当有

n

个应 答器时，假设识别总时间为：

则当

n+1

个应答器时，读写器首先发送命令，应答器全体响应，发 生碰撞，

这个过程时间为：

读写器修改命令参数，

发出命令，

k

个应答器响应，

余下

p

个不响应，

k+p=n+l

，

则识别出 该

k

个应答器需要时间为：

再识别余下

p

个需要时间为：

则这两者时间之和为：

< p>
加上前一次的．

t1+t2

，总时间为：

18

得证。

因为基本二进制树算法中每次 传输的序列号

SN

长度相同，

，所以有 ：

基本二进制树搜索算法是所有二 进制树算法的基础，

分析基本二进制树搜索

算法的性能可知，< /p>

对于固定数目的应答器，

二进制树算法的性能主要取决于二进

制树的节点数目和单次传输命令参数的时间，

事实上，

二进制树的节点数目与应

答器分组的思路是直接相关的，

而单次传输命令参数的时间则取决于该命令包含

的数据位数。所以，要改善二进制树 算法的性能，就必须从这两点着手，现有的

二进制树搜索算法有很多种，

它们都是在基本二进制树搜索算法的基础上加以改

进得来的，根据前述分析，主 要的改进思路有两个：

(1)

减少每 次通信过程中的数据传输位数。

(2)

减少应答器分组的询问次数。

本文中，定义根据第一个思路得来的算法为动态二进制树，它的一个典型应

用为

ISOl4443

TYPE-A

二进制树搜索算法。

定义根据第二个思路得来的算法为退

避式二进制树，它的一个典型应用为

EPC

二进制树搜索算 法。

2

．

4

动态二进制树防碰撞算法

2

．

4

．

1

算法思路

定义两个具有普遍意义的命令来描述算法：

< br>(1)

请

求

命

< br>令

Request(

)

，

该

命

令

携

< p>
带

一

个

参

数

SN

，

长

< br>度

为

，应答器接收到该命令，将自身的

< br>SN

中的前

1

～

x

位与接收到的

比较，若两者相等，则该答器返回其< /p>

SN

的剩余位给读写器。注：

Reque st(

)

初始值设为

Request( 1l111111)

，约定当参数值为全

1

时，应答

器返回完整序列号。

( 2)

休眠命令

Sleep(SN)

，该 命令携带一个参数

SN

，应答器接收到该命令，

将自身的

SN

与接收到的

SN

比较，若等于，则该应答器被选中，进入休眠状态，

也即是不再 响应

Request

命令，

除非该应答 器通过先离开读写器工作范围再进入

的方式重新上电，

才可以再 次响应

Request

命令。

动态二进 制树算法的流程与基

本二进制树算法是一致的，

它们的区别在于 ：

基本二进制树算法中，

应答器返回

完 整序列号，而动态二进制树算法中，应答器只返回序列号的有效部分；同样，

基本二进制 树算法中，

读写器生成新

Request

命令时，

其命令参数长度是固定为

8

位的，而动态二进制树算法中，该命令参数长度是根据应答器返回的序列号来

动态变化的 。

动态二进制树算法的流程如图

2< /p>

．

5

所示：

19

图

2

．

5

动态二 进制树算法流程

事实上，

动态二进制 树对基本二进制树的改进是基于如下考虑的，

在基本二

进制树的 分析过程中可见，

算法的核心部分即新命令参数的生成，

是根据 是否发

生碰撞，

以及碰撞位来决定的，

特别是新

Request

命令参数的生成是由碰撞的起

始位来确定的，

而碰撞的起始位的得到只需要应答器序列号中包括碰撞起 始位在

内的部分位即可，

把这些位称为序列号的有效位，

同样，

新

Request

命令参数也

为包括碰撞起始位

(

设 为

0)

在内的部分位，综合如下：若选择高位加碰撞起始位

(

设为

0)

，则算 法为应答器序列号对应位小于这些位的数值者，返回剩余低位，

若选择碰撞起始位

(

设为

0)

加低位，

则算法为应答器序列号对应位等于这些位的

数值者，

< p>
返回剩余高位，

从而读写器的新

Request< /p>

命令参数与应答器返回的序列

号有效部分组合起来，

可以得到一个完整的应答器序列号。

这两种选择方式并没

有本质区别，在本文中，采取其中的一种，即：读写器检测到碰撞后，将碰撞起

始位 置

0

，低位不变，从而将碰撞起始位

(

置为

O)

加低位作为新

Request

命令参

数，应答器响应，从低位开始比 较，若对应位等于该参数，则返回剩余位给读写

器，如果只有

_

个应答器响应，读写器检测到无碰撞发生，则将上一次发出的

R equest

命令参数与应答器返回的剩余位组合起来，作为新的

Sleep

命令参，该

参数也即是刚刚做出响应的这个应答器 的序列号。

注：如果上一次发出的

R equest

为全

l

，则表明读写器工 作范围内只有一个

应答器，此时应答器返回数据为完整序列号，以该序列号作为

Sleep

命令参数。

动态二进制树算法的步骤如下：

(1)

应答器进入读写器工作范围，

读写器发出一个最大序列号，

约定此时所

有应答器均返回完整序 列号，则同一时刻应答器将自身序列号发回给读写器。

(2)

由于应答器序列号的唯一性，

当应答器数目不小于两个时，

必然发生碰

20

撞。发生碰撞时，将最大序列号中对应的碰撞起始位置为

0

。 低于该位者不变。

(3)

读写器将 处理后的碰撞起始位与低位发送给应答器，

应答器序列号与该

值 比较，等于该值者，将自身序列号中剩余位发回．

(4) < /p>

循环这个过程，

就可以选出一个最小序列号的应答器，

< p>
与该应答器进行

正常通信后，

发出命令使该应答器 进入休眠状态，

即除非重新上电，

否则不对读

< br>写器请求命令起响应。

(5)

重复上述过程，即可按序列号从小到大依次识别出各个应答器．

2

．

4

．

2

实例演示

动态 二进制树算法的实例演示如图

2

．

6< /p>

所示，基本设置同基本二进制树算

法：

图

2

．

6

动态二进制树算法实例

(1)

启动第一轮循环，读写器发送

Request( 11111111)

命令，所有应答器响

应该命令，

< p>
按照约定，

命令参数为全

1

时，

所有应答器均返回自身序列号给读写

器，

因为序列号的唯一性，

应答器返回的序列号在读写器接收端发生碰撞，

读写

器检测到返回数据为

1XXXXl01

，其中

X

表示该位发生了碰撞，读写器做如 下处

理：将碰撞起始位

D4

位置

0

，低于该位者不变，得到

0101

，则下一次

Request

命令携带的参数值， 即

Request(0101)

。

< /p>

(2)

读写器发送

Request(0l 01)

命令，所有应答器响应，将自身序列号与该

SN(010 1)

比较，其中

Tl(10l00101)

，

T3(110l0l01)

的序列号低四位等于该值，< /p>

则

T1

，

T3< /p>

返回剩余位给读写器，在读写器接收端发生碰撞，读写器检测到返回

数据为

lXXX

，读写器做如下处理：将碰撞起始位

D5

位置

0

，低于该位 者不变，

得到

0010l

，作为下一次

Request

命令参数值，即

Req uest(00l01)

。

(3)< /p>

读写器发送

Request(00l01)

命令，所有应答器响应，将自身序列号与该

SN(00101)

比较，其中

Tl(10100101)

的序列号对应位等于该 值，则

Tl

返回剩余

序列号给读写器， 在读写器接收端不发生碰撞，读写器检测到返回数据为

l0l

，

读写器做如下处理：将上一次

Request(00l01)< /p>

命令参数

00101

与返回数据

101

组合起来，作为下一次

Sleep

命令携带的参数值，即

Sleep(10100101)

。

(4)

读写器发送

Sleep(10100101)

命令，所有应答器响应该命令，将 自身序列

21

号与该

SN(10100101)

比较，

其中

T1(10100101)

的序列号等于该值，

则< /p>

Tl

执行该

命令，进入休眠状态，即除非 重新上电，否则不再响应

Request

命令。

(5)

启动新一轮循环，

重 复上述步骤，

总计

12

步后，

依次识别出

T1

，

T3

，

T2

，

T4

，参数变化过程见图

2

．

6

中标示，具体内容不再详述。

< br>2

．

4

．

3

性能评价

与

3

．

3

．

2

基本二进制树实例图比较可知，

动态二进制树算法的识别过程 中，

节点数目，

循环轮次都是一样的，

但是每次循环过程中，

读写器命令与应答器指

令所携带的参数都 是在动态改变长度的，

所以动态算法的优势主要体现在两个方

面 ，

一是算法执行过程中数据传输时间；

二是算法执行过程中数据 信息量。

根据

分析，

算法执行过程中，

读写器与应答器传送的数据主体是应答器的序列号，

为

了便于分析，假定数据交换过程中，双方只传送序列号

SN

，则在基本算法中，

读写器与应答器均传送了序列号全部长度，

而在动态算法中，

读写器传送序列号

的部分位，应答 器再传送剩余位，两者组合起来才得到全部的序列号，显然，虽

然每次传送时动态算法的 数据长度不同，

但是在整个算法执行过程中，

基本算法

传送了两倍序列号，

动态算法则只传送了一倍数据量，

< br>从而可知，

动态算法传送

的信息量是基本算法的

50

％，

从而数据传输时间也是原基本算法的< /p>

50

在本例中，

由于假定了应答器的序列 号为

8

位长度二进制数，

所以这个动态 变化的优势并不

明显，然而，事实上在实际应用中，应答器序列号长度往往是极大的，比 如说常

见的是

96

位，在这样的情况下 ，动态算法的优势就体现出来了。

2

．

5

退避式二进制树防碰撞算法

2

．

5

．

1

算法思路

退避式二 进制树搜索算法是对基本二进制树搜索算法的一种改进，根据

2

．

3

基本二进制树算法的分析可知，

每 识别一个应答器后，

读写器恢复

Request

命令

参数的初始值，

重新从二进制树的根部开始执行，

对此可以采取退避的思想，

即

每次识别 出一个应答器后，

算法返回其上一个父节点，

而不返回整棵树的 根节点。

定义两个具有普遍意义的命令来描述算法：

< br>(1)

请求命令

Request(SN)

：

该命令携带一个参数

SN

，

应答器接收到该命令，

将自身的

SN< /p>

与接收到的

SN

比较，若小于或者等于， 则该应答器回送其

SN

给读

写器。注：

Request(SN)

初始值设为

R equest(11ll1111)

。

(2)

休眠命令

Sleep(SN)

：该命令携带一个参数

SN

，应答器接收到该命令，

< p>
将自身的

SN

与接收到的

SN

比较，若等于，则该应答器被选中，进入休眠状态，

即除非 重新上电，

否则不再响应

Request

命令。

退避式二进制树算法的流程见图

2

．

7

，基本设置可参考基本二进制树算法：

22

图

2

．

7

退避式二进制树算法流程

如图所示，

退避式二进制树算法的流程与基本算法的区别在于：

基本算法中，

< br>一个应答器被识别后，

重新启动新循环时，

读写器返回整 棵树的根节点，

获取原

始

Reques t

命令参数，

而退避式算法中，

读写器 返回上一次发生碰撞节点，

获取

Request

命令参数。事实上，退避式算法的改进是基于如下考虑的，在基本二进

制树的分 析过程中可见，

算法之所以称为二进制树，

是因为每次碰撞后，

均以碰

撞起始位为界，

将应答器分为两 个部分，

形象的看，

如同一棵树在进行从根部到

主干到树枝的一个不断的分叉过程，

所以，

分叉也即是 分组的理念是二进制树算

法的本质所在，

根据这一点，

算法每次分叉到达末端之后，

不再返回根部重新开

始分叉，

而是返回上一次分叉的节点即可重新开始新的树干 ，

该节点也即是上一

次发生碰撞的节点。

采用该返回思路的二进制树算法，

称为退避式二进制树算法。

退避式二进制树算法的步骤如下：

(1)

应答器进入读写器工作范围，

读写器发出一个最大序列号，

所有应答器

的序列号均小于该最大 序列号，所以在同一时刻将自身序列号发回给读写器。

(2)

由于应答器序列号的唯一性，若应答器数目不小于两个，必发生碰撞。

< br>此时将最大序列号中对应碰撞起始位置为

O

。

< p>
低于该位者不变，

高于该位者置

1

。

(3)

读写器将处理后的 最大序列号发送给应答器，

应答器序列号与该值比较，

小于或等 于该值者，将自身序列号发回．

(4)

循环这个过程，选出一个最小序列号的应答器，与之正常通信后，命令

该应答器进入休 眠状态，即除非重新上电，否则不再响应读写器请求命令。

( 5)

返回上一个发生碰撞的节点，获取该节点对应的最大序列号，重复上述

过程，即可按序列号从小到大依次识别出各个应答器．

23

2

．

5

．

2

实例演 示

退避式二进制树算法实例演示如图

2

．

8

所示，其设置参考基本二进制树 算

法：

图

2

．

8

退避式 二进制树算法实例

(1)

启动第一轮 循环，读写器发送

Request(11111111)

命令， 所有应答器响

应，将自身序列号与该

SN(11111111)

比较，均小于该值，则所有应答器均返回

自身序列号给读写器，

因为序列号的唯一性，

应答器返回的序列号在读写器接收

端发生碰撞，读写器检测到返回数据为

lXXXXl0l

，其中

X

表示该位发生了碰撞，

读写器做如下处理：

将碰撞起始位

D4

位置

0

，

低于该位者不变，

高于该位者置

1

，

得 到

1l110l01

，作为下一次

Re quest

命令参数，即

Request(1l1

l 0l01)

。

< br>(2)

读写器发送

Request(1l110101)

命令，所有应答器响应，将自身序列号

与该

SN(111l0l01)

比较，

其中

T1(10100101)

，

T3(110l0101)< /p>

的序列号小于该值，

则

Tl

，

T3

返回自身序列号给读写器，

< br>在读写器接收端发生碰撞，

读

RFID

< br>二进制

树防碰掩算法的研究与实现写器检测到返回数据为

1XXX0101

，读写器做如下处

理：

将碰撞起始位

D5

位置

0

< p>
，

低于该位者不变，

高于该位者置

1

，

得到

11l

< p>
00101

，

作为下一次

Request

命令携带的参数值，即

Request(1l1 00101)

。

(3)

读写器发送

Request(11100101)

命 令，所有应答器响应，将自身序列号

与

SN(1ll

00101)

比较，其中

T1(1010010 1)

序列号小于该值，则

Tl

返回序列 号，

在读写器接收端不发生碰撞，读写器检测到返回数据为

10 100l01

，做如下处理：

将该值作为下一次

Sleep

命令参数值，即

Sleep(101001 01)

。

(4)

读写器发送

Sleep(10l00l01)

命令，所有应 答器响应，将自身序列号与该

SN(10100ll1)

比较， 其中

T1(10100l01)

的序列号等于该值，则

Tl

执行该命令，

进入休眠状态，即除非重新上 电，否则不再对

Request

命令做出响应。

(5)

启动新一轮循环，

重 复上述步骤，

总计

12

步后，

依次识别出

T1

，

T3

，

T2

，

T4

，参数变化过程见图

2

．

8

中标示，具体内容不再详述。

24

2

．

5

．

3

性能评 价

与基本二进制树比较可知，

退避式 算法每次传送的数据信息量与基本算法是

一样的，

区别在于，< /p>

退避式算法的传送次数，

也即是所遍历的节点数目比之基本

算法大大减少，

假设读写器工作范围内有

n< /p>

个应答器，

则所需节点数目为而，

则

可用式子

2

．

19

来表示：

数学归纳法证明如下：

当读写器工作范围内只有一个应答器时，显然有：

假设

n

个应 答器时，有：

则当系统中有

n+1

个应答器时，由于新增加的这个应答器与原来

< br>n

个应答

器的序列号均不相同 ，

为了将其与某个匹配度最高的应答器区分开来，

需要在原

来二进制树中增加一个节点，

由于节点之 间仅存在父子关系，

且仅通过两条边相

连，所以有：

得证。

2

．

6

本章小结

本章归纳了现有的二进制树防碰撞算法，

将其分为三个基本类别，

分别讲述

了其实现思路，进行了实例演示，并且对其做了性能分析，结果表明，动态算 法

和退避式算法是对基本算法的两个改进思路，具有各自的优势。

3

改进型二进制树防碰撞算法

3

．

1

涉及二 进制树算法的国际标准

3

．

1

．

1 IS0 15693

ISO l5693

【

23

< p>
】

，短距离智能卡

(Vicinity coupling smart cards)

标准，

读取距离 可高达一分米，使用的频率为

l3

．

5 6MHz

，它设计简单，生产成本比

IS014443

低，大都用来做出入控制、出勤考核等，现在很多企业使用的门禁卡

大都 使用这一类的标准。符合

IS015693

标准的信号接口部分 的性能如下：

工作场强：工作场的最小值为

< br>O

．

15A

／

< br>m

，最大场为

5A

／

< p>
m

。

工作频率：工作频 率为

13

．

56MKz

士

7KHz

25

调制：

用

2

种幅值调 制方式，

即

l0

％和

< br>l00

％调制方式。

读写器应能确定用

< br>哪种方式。

100

％幅值调制

10

％的幅值调制

数据编码

数据编码采用脉冲位置调制 。两种数据编码模式：

256

选

1

模式和

4

选

1

模

式。

数率：有高和低两种数率。

表

3

．

1IS015693

数率

3

．

1

．

2 IS014443

ISO

是英文

International OrganizationForStandardization

的简写，

< p>
即国

际标准化组织，

IEC

是

InternationalElectromechanical

< p>
Commission

的简写，

即国际电子科技化 委员会，

JTC(JointTechCommittee)

是

ISO

和

IEC

组成的一个

联合技术委员会，负责

ISO

／

IEC

国际标准的起草、讨论、修正、制定、表决和

公布等具体事宜，

JTC

分为各个子委员会

SC(Subcommittee)

，

子委员会又分为各

个工作组

WG(WorkGroup)

，

其中子委员会

SCl7

下的

WG8

负责

ISOl4443

、

ISOl5693

以及

ISOl5693

非接触式智能卡标准具体起草、

讨 论修正、

制定、

表决和最终

ISO

国际标准的公布【

24

】

< br>。

ISO

／

IECl4443< /p>

标准开始于

1995

年，单个系统于

1999

年进入市场，而其完成在

2000

年以后，迄今为止，

ISO

／

IECl4443

标准中的非

接触式智能卡的类 型可以分为

TypeA

和

TypeB< /p>

。

TypeC

—

G

目前已经暂时被列入

IS014443

标准，等待复议。

下面简要介绍一下

ISO

／

IECl

4443

标准中各个不同类型的非接触式智能卡。

T ypeA

由

Philips

半导体公司 首次开发和使用，在亚洲等地区，

TypeA

技术

和产品占据了很大的市场份额。

TypeA

技术设计 简单扼要，应用项目的开发周期

可以很短，同时又能起到足够的保密作用，可以适用于非 常多的应用场合。

TypeB

是一个 开放式的非接触式智能卡标准，

所有的读写操作可以由应用系

统 开发者定义，因此被世界上众多的智能卡厂家所广泛接受。

T ypeC

由日本索尼公司研制。

有两个主要特点，

一是独特的天线结构和技术，

使其读写距离可以稳定地达到

< br>10cm

以上，

同时其天线结构中镶嵌的特殊材料

(

铁

氧体等材料

)< /p>

使其天线电磁场的读写距离非常均匀，没有“死区”现象出现，二

是

SONY

非接触智能卡数据写操作失败时的数据恢复功能。< /p>

TypeD

由

Cubic

公司研制，该系统的非接触方式读卡／认证速度非常快速，

< br>

约为

70ms

左右，并且实现 了数据加密技术，开创了交通系统中“刷卡”的

先例。并且，

C ubic

将一些人体的生物特性，例如指纹、面部图案识别等融入于

非接触智能卡技术中，开创了非接触智能卡生物识别的新领域。

< br>TypeE

由以色列

oTI

公司 研制，应用市场主要在欧洲和美国等地。

OTI

独创

< p>

26

的一些非接触智能卡技术，

可以使一个接触式智能卡提升成为一个非接触式智能

卡，另外，

OTI

研究开发的单芯片解决方案和双模块解决方案支持接触式和非接

触式

(13

．

56M Hz)

两种接口应用，并自动识别和转换。

< br>TypeF

由欧洲

LEGIC

公 司研制，其保密系统的产品在欧洲市场占有率达到

60

％以上。

LEGIC

保密模块包括

SM05(- S)

、

SMlOO(-S)

、

SM300

／

400(-S)

< br>等。

TypeG

由中国制定， 在应用层面，

TypeG

体现出了足够的技术先进性，但是

在非接触智能卡核心技术的研发和掌握上、

微电子工业基础设施和设 备上，

还有

一段漫长的路要走。

3

．

2 IS014443

标准二进制树防碰撞算法

< br>3

．

2

．

1

基本概念

ISO

／

IECl4443

标准主要规定了

< br>TYEP A

和

TYPEB

两种 类型的非接触式智能

卡，

以

13

．

56MHz

交变信号为载波频率，

读写距离为

0

～

l0c m

，

通信速率均为

l06kb

／

s(9

．

4us perbit)

。

TYPEA

和

TYPEB

的不同主要在于载波的调制深度 和位编码方式，

TYPEA

采用

l00

％

ASK

调制、同步时序以及改进的米 勒

(Miller)

编码方式，使用的是间断式

调制方式，即当表示信息“

l

”时，表示有信号到卡， 当表示信息“

0

“时，没有

信号到卡。

这种方式的优点是信息区别明显，

受到干扰的机会少，

不容易误操作，

缺点是需要能量持续到卡；

T YPEB

采用采用

10

％

ASK

调制、非同步时序和不归

零

< br>(NRz)

编码方式，使用了一种调幅的调制方式，信息“

l

”和“

0

”的区别是在

< p>
于信号的强弱，这一点容易受到外界干扰，需要采用冗余校验来解决。

< /p>

由上面的比较可以看出，

两种技术各有优劣，

这也是

lSO

组织确定了两种标

准 的原因之一。

然而，

在应用层面上

A< /p>

类有着比

B

类更多的厂商支持，

是市场上

的主流应用技术，

其后续支持较好。< /p>

在价格上由于

A

类的广泛性和芯片本身的 低

端设计性，

A

类有更大的优势。

ISO

／

IEC l4443

标准由以下四个部分组成：

Part1

：

Physical ch aracteristics(

物理特性

)

；

Part2

：

Radiofrequencypowerandsignal interface(

频谱功率和信号接口

)

㈣；

Part3

：

Initializat ion andanti

．

collision(

初始化和防碰撞算法

)

例；

Part4

：

Transmissio nprotocols(

传输协议

)

。

表

3

．

2

读写器和应答器的中英文名称及其缩写

注：这

里的近距离耦合器

< p>
(PCD

，

ProximityCoupling Device)

和近耦合卡

(PICC

，

ProximityCard)

即前文的读写器和应答器，为 尊重原

IS014443

标准，这里保留该说法。

表

3

．

< br>3Type A

的通信信号接口

27

I SOl4443

标准在第三部分

:

“初 始化和防碰撞算法”中，对防碰撞算法进行

了规定，定义了

PI CC

进入

PCD

时的轮询，通信初始化 阶段，从多卡中选取其中

的一张的方法等。

< br>3

．

2

．

2

算法思路

PCD

的初始化，防碰撞，以及数据交换的流程如图

3

．

1

所示：

图

3

．

1ISOl 4443

标准

TYPE A

类型

PCD

通信全过程

28

如图所示，分为这么几个部分：

1< /p>

．

PCD

与

PI CC

进行符合

lSO

／

IECl4443

．

2

的初始 化通信。

(1)PCD

不断发送请求 命令

Req

，检测工作范围内的

PlC C

。

(2)PICC

接收到请求命令

Req

，返回一个请求命令应答

Atq

。

(3)P CD

接收到来自

PICC

的请求命令应 答

Atq

，表明有

PICC

< p>
存在。

(4)PCD

对 该

Atq

进行检测，决定下一步动作。

此时若

Atq

携带信息显示，

PICC

符合

ISOl4443

—

3

，

则启动位帧防碰撞循环 ，

否则启动专用的防碰撞循环。

2< /p>

．

PCD

与

PI CC

进行符合

ISO

／

IECl4443

—

3

的位帧 防碰撞循环。

(1)PCD

选择级联 层

l

，发送防碰撞命令

Anti

．

collision

。

(2)PICC

响应防碰撞命令

Anti

．

collision

，返回 其

UID

的部分或者全部。

(3)PCD

根据

PICC

的响应，检测到碰撞，修改

Anti

．

collision

命令参数，

发送防碰撞命令

< p>
Anti

．

collision

< br>。

(4)PICC

响应防碰撞 命令

Anti

．

collision< /p>

，返回其

UID

的部分或者全部。

(5)

循环

3)< /p>

～

4)

步。

< /p>

(6)PCD

根据

PICC

的响应，若检测不到碰撞，则发送

Select

选择 命令。

(7)PICC

接收到

Select

选择命令，发送选择应答

SAK

作为响应。

(8)PCD

< p>
对该

SAK

进行检测，决定下一步动作。

若

SAK

携带信息显 示：

PICC

返回的

UID

< p>
不完整，且未清除级联层数，则应

增加级联层数，继续位帧防碰撞循环，即 循环

2)

～

7)

步。若

SAK

携带信息显示：

PIC C

返回的

UID

完整，

且清除级联层数，

但是不符合

IS014443

—

4

，

则

< p>
PCD

发送

停止命令

Ha lt

，令

PICC

进

< br>

入停止状态

Halt

。若

SAK

携带信息显示：

PICC

< p>
返回的

UID

完整，且清除级

联层数，并且符合

IS014443

—

4

，则启动数据操作，即下一个环节

3

。

3

．

PCD

与

PICC

进行符合

< p>
ISO

／

IECl4443

．

4

的数据操作。

(1)PCD

发送请求选择应答

RAts

。

(2)PICC

接收到 请求选择应答

RAts

，返回一个选择应答

Ats

。

(3)PCD

接收到来自

PICC

的选择应答

Ats

。

(4)PCD

对该

Ats

进行检测，决定下一步动作。< /p>

若

Ats

携带 信息显示：

PICC

支持协议和参数选择

PPS

，

则根据实际情况，

判

断是否需要进行参数修改。如果不需要进行参数修改，则执行步骤

5)

，如果需

要进行参数修改，则执行下列操作。

< br>

(1)PcD

发送协议和参数选择请求

PPSReq

。

(2)PI CC

接收该命令，修改相关参数。

RFID_

< br>二进制树防碰掩算法的研究‘

j

实现

(3)PICC

返回协议和参数选择应答

PPSResp

。若

Ats

携 带信息显示：

PICC

不

支持协议和参 数选择

PPS

，则直接进行数据交换，即步骤

< br>5)

。

(5)PCD

与

PICC

进行数据交换。

(6)PCD

发送去选择请求命令

DeselectReq

，表示不再选择该

PICC

。

(7)PICC

接 收该命令，

去除选择，

返回去选择应答命令

DeselectResp

，

表示

已经去除了选择，进入

HALT

状态，除非重新唤醒，否则将不 再响应其它命令。

(8)PCD

接收 去选择应答命令

DeselectResp

。

< br>

总结：

PCD

与

PICC

之间的通信包括上述初始化，防碰撞和数据操作三个环

节，

每个环节包括多个步骤，

各个步骤下还可能有多 个可能的分支操作，

理想的

29

操作流程为按各个步骤从上而下的执行。

图

3

．

2Isol4443

标准

TYPE A

类型

PIcc

状态转移图

< br>

图中各个状态及其转移关系说明如下：

(1)

掉电状态

(PowerOff )

：

PICC

未进入

< br>PCD

工作范围，没获得能量。

(2)

空闲状态

(Idle)

：

PICC

进入

PC D

工作范围，获得能量，

PICC

由掉 电状

态进入空闲状态，要注意的是，这里的复位

Reset

指的是

PICC

进入

PCD

工作场

的操作过程，并非是一个具体的指令。

(3)

准备状态

( Ready)

：空闲状态的

PICC

接 收到请求命令

Req

，或停止状态

的< /p>

PICC

接收到唤醒命令

Halt

，进入准备状态，在该状态中，完成防碰撞循环，

从多张卡中选择出一 张

PICC

。

(4)

激活状态

(Active)

：

PICC

被识别后，

PCD

发送选择命令

Select

来选中

该卡，

PICC

接收到该命令，进入激活状态，在该 状态中，完成数据操作。

(5)

停 止状态

(Halt)

：处于激活状态的

PICC

完成数据操作后，接收到来自

PCD

< br>的停止命令

Halt

，从而进入停止状态。

PCD

与

PICC

通信过程中，

防碰撞循环是最关键的一个环节，

如图

3

．

3

所示：

步骤

l

：

PCD

为选择的防冲突类型和串联级别分配了带有编码的< /p>

SEL

。

步骤

2

：

PCD

分 配了带有值为

‘

20

’

的

NVB

。

该值定义了

PCD

将不发送

UIDCLn

的任何部分，从而迫使工作场内的所有

PICC

以其完 整的

UIDCLn

表示响应。

步骤

3

：

PCD

发送

SEL

和

Nv B

。

步骤

4

：工作场内的所有

PICC

应使用它们 的完整的

UIDCLn

响应。

步骤

5

：假设场内的

PICC

拥有唯一序列号，那么，如果一个以上的

PICC

响

应，则冲突发生。如果没有冲突发生，则步骤

6

到步骤

10

被跳过。

< p>

步骤

6

：

PCD

识别出第一个冲突的位置。

步骤

7

：

PCD

分配

NVB

，

该值规定了< /p>

UIDCLn

有效比特数。

这些有效位应 是

PCD

30

所决定的冲突发生之前被接收到的

UIDCLn

的一部分再 加上

(O)b

或

(1)b

。

步骤

8

：

PCD

发送

SEL

和

NVB

，后随有效位本身。

< br>

步骤

9

：只有

PICC

的

UIDCLn

中的 一部分等于

PCD

所发送的有效位时，

PICC

才应发送其

UIDCLn

的其 余部分。

步骤

10

< br>：

如果出现进一步的冲突，

则重复步骤

< br>6

～

9

。

最大的重复数目是

32

。

步骤

1l

：如果不出现进一步的冲突，则

PCD

分配带有值为‘

70

< br>’的

NVB

。

注：该值定义了

PCD

将发送完整的

< br>UIDCLn

。

步骤

12

：

PCD

发送

SEL

和

NVB

， 后随

UIDCLn

的所有

40

个位。

步骤

13

：它的

UIDCLn

与

40

个比特匹配，则该

PlCC

以 其

SAK

表示响应。

步骤

14

：如果

UID

完整，则

PICC

应发送带有清空串联级别位 的

SAK

，并从

READY

< p>
状态转换到

ACTIVE

状态。

< br>

步骤

15

：

< br>PCD

应检验

SAK

的串联比特 是否被设置，

以决定带有递增串联级别

的进一步防冲突环是否应 继续进行。

31