登录
注册
RFID 无线通信迂回式随机树形防冲突算法
作者：刘云
来源：RFID世界网
日期：2010-01-12 11:28:42
摘要：RFID 系统主要由三部分组成， 即电子标签（tag）、读写器（reader） 以及天线（antenna）， 是一种非接触式的自动识别系统。随着RFID系统的不断增多， 多个电子标签同时将信号送入一个读写器的读写通道必然会产生信道争用问题， 如何减少数据碰撞从而快速有效的在规定时间内读取出所有电子标签的信息成为一个难点。
射频识别RFID （RadioFrequencyIdentification） 技术相对于传统的磁卡及IC 卡技术具有非接触、阅读速度快、无磨损等特点， 在最近几年里得到快速发展。RFID 系统主要由三部分组成， 即电子标签（tag）、读写器（reader） 以及天线（antenna）， 是一种非接触式的自动识别系统。随着RFID系统的不断增多， 多个电子标签同时将信号送入一个读写器的读写通道必然会产生信道争用问题， 如何减少数据碰撞从而快速有效的在规定时间内读取出所有电子标签的信息成为一个难点。
解决碰撞问题的算法有ALOHA算法、分隙ALOHA算法和二进制树形搜索算法， 但这几种算法都有一个共同的缺陷： 信道利用率比较低。本文提出了一种新的反碰撞算法， 这种算法是在传统的二进制树算法基础上， 通过迂回式反碰撞算法， 利用二进制位取值的互异（即非0 即1）的特性， 以及连续两位发生冲突（即00， 01， 10， 11）， 可同时识别出1~4 个标签， 进而提高阅读器识别标签的效率， 在信道利用率上远远优于其它算法。
1 射频识别系统的工作原理
射频识别系统的工作频段有低频， 中频， 高频， 超高频及微波之分， 而在工业中通常采用13.56MHz 的频率。对于从阅读器与电子标签间数据传递， 通常采用振幅键控ASK （AmplitudeShiftKeying）、频移键控FSK(FrequencyShiftKeying)和相移键控PSK （PHASEShiftKeying）。ASK 和PSK 常被使用， 因为它们特别容易解调， 其原理参见图1。由图1 中可知， 当有多于1个的标签在阅读器的作用范围内时， 且传递的数据0/1 交错时， 将会出现1个标签谐振， 1个标签失谐的情况。这时就阅读器则很难通过判断输出端的高低电位来读出标签的内部信息， 这就是我们要解决的碰撞问题。
二进制搜索算法， 是以一个独特的序列号(UID)来识别标签为基础的， 为了能辨认出阅读器中数据碰撞比特位的准确位置， 传统采用曼彻斯特编码。该编码采用电平的上升沿和下降沿来表示数值位。本文中假设上升沿编码为逻辑“0”， 下降沿编码为逻辑“1”， 若状态跳变， 视为无效数据且作为错误码被识别。如在多标签的环境中当同时有上升沿和下降沿同时存在是， 则会互相抵消从而无状态跳变， 以此阅读器判断发生碰撞的准确位数而再次搜索。假设有6 个RFID 标签， 其相应EPC代码为8 位， 利用曼彻斯特编码能准确识别出碰撞位的示意图如图2 所示， 图中用红色部分为碰撞位。
本文约定在阅读器作用范围内的所有标签能在同一时刻同步传送响应数据， 以便准确地监测碰撞位的发生。为了便于表述算法， 还需要引入4 种命令：
1） REQUEST： 表示阅读器发送一个呼叫参数给区域内标签， 所有标签的EPC 与之进行“与运算”， 结果全为0 的标签将各自的EPC返回至阅读器。在第1 次询问时， 呼叫参数应全为0， 即Request 命令为： Request(00000000)， 这样区域内所有标签都会应答。
2） SELECT： 用某个（事先确定的） EPC 作为参数发送给标签。具有相同EPC 的标签将以此作为执行其他命令（例如读出和写入数据）的切入开关， 即选择这个标签。
3） READ/DATA： 选中的标签将存储的数据发送给阅读器）。
4） UNSELECT： 取消一个事先选中的标签， 标签进入“休眠”状态。在该状态下标签对收到的REQUEST 命令不作应答。为了重新激活标签， 须将标签移出阅读器的作用范围再进入， 以实行复位。
3 算法原理
假设阅读器作用范围内有6 个标签， 阅读器在本文约定的环境中识别这些标签， 最初阅读器对区域内标签处于未知状态， 发送Request（00000000） 命令， 此时阅读器周边区域内所有的标签则同步应答。详细数据处理过程如下：
Step1： 阅读器发送Request （00000000） 命令。区域内所有标签的与运算结果全为0， 即所有的标签返回自身8 位的EPC 代码应答。根据曼彻斯特编码原理， 可解码得EPC 数据为： “$$1$$$10”， 即D2， D3， D4， D6， D7 位发生碰撞。算法作以下的处理： 从5 个碰撞位随机选择一位， 如D7； 然后将上一次Request命令中的参数00000000 的D7 位取反， 得下一次Request 命令所需的参数： 10000000。
Step2： 阅读器发送Request （10000000） 命令。则此时区域内D7位是0 的标签应答， 即标签1 不相应， 标签2~ 标签6 应答， 同理可解码得EPC 数据为： “0$1$$$10”， 碰撞位有： D2， D3， D4， D6， 位。算法作以下的处理： 从4 个碰撞位随机选择一个， 如D3； 然后将上一次Request 命令中的参数10000000 的D3 位取反， 得下一次Request命令所需的参数： 10001000。
Step3： 阅读器发送Request （10001000） 命令。区域内的D3 和D7 都是0 的标签应答， 此时只有标签4 应答， 其他标签不响应， 在这种情况下没有碰撞位， 阅读器可以直接将收到的EPC 值用SELECT 命令发给标签4 并进行读写操作， 处理完成后执行Unselect 命令， 屏蔽掉标签4， 使它处于“休闲” 状态。算法再采用回溯策略， 从该节点的父节点获得下一次Request 命令所需的参数： 10000000。
Step4： 阅读器发送Request ( 1000 0000) 命令。区域内D7 位是0 的标签应答， 即标签2， 标签3， 标签5， 标签6 应答， 同理可解码得EPC 数据为： 0$101$10， 碰撞位有： D2， D6， 位， 此时只有两个碰撞位， 则读写器可依次通过SELECT 命令发送“00101010”，“00101110”， “01101010”， “01101110”， 从而完成标签5， 标签2， 标签6 的读写操作， 最后通过UNSELECT 命令将些三个标签置于“休闲” 状态。算法再采用回溯策略， 从该节点的父节点获得下一次Request 命令所需的参数： 00000000。
Step5： 阅读器发送Request(00000000)命令。区域内所有处于非“哑吧” 状态的标签应答， 即标签1 与标签3 应答， 同理可解码得EPC数据为： $0101010， 此时碰撞位只有D7 位。则读写器可依次通过SELECT命令发送00101010， 10101010， 从而完成标签3 和标签1 的读写操作， 最后通过UNSELECT 命令将标签3 和标签1 置于“休闲” 状态。算法再采用回溯策略， 从该节点的父节点获得下一次Request 命令所需的参数， 由于已到树根无父节点， 因此识别过程结束。图3 为识别读写全部标签的流程图：
1） 阅读器发Request （00000000） 命令， 要求区域内所有标签应答。
2） 检测有无碰撞发生。若无碰撞时， 可识别出一个单独的标签。标签值为应答时返回的EPC 值。处理完后， 再屏蔽掉它。
3） 若有碰撞， 可分两种情况， 如碰撞位>2， 则可从碰撞位中随机选择一位， 并由选中的那一位和上一次REQUEST 中的参数共同决定下一次Request 命令所需的参数， 具体如下： 在上一次REQUEST 命令中参数的基础上再对所选中的那一位取反， 即可得下一次REQUEST命令的参数。
4） 若碰撞位<=2 时， 可通过改变相应两位的数值即00， 01， 10， 11 的值以同时识别出4 个标签， 另外下一次Request 命令所需参数， 采用回溯策略， 从其父节点获得， 通过迂回方式直到执行Request(00000000)命令返回值碰撞位小于2 时读写结束。
4 系统的软件实现
以下程序为实现读写过程的子程序：
Push(EPC)： 将EPC 值入栈；
Pop()： 将栈顶元素弹出；
GetTop()： 返回栈顶元素；
StackEmpty()： 栈空返回true， 不空返回false；
Request(EPC)： 阅读器将EPC 发送给标签；
GetCollisionBitsCount_(EPC)： 返回EPC 值中碰撞位的数目；
RandomSelectCollisionBit(EPC)： 返回从EPC 中随机选择的一个碰撞位的下标；
ReverseBit(EPC， n)： 将EPC 的第n 位取反， 并返回取反后的EPC 值；
SetCollision(EPC， bit)： 将EPC 的碰撞位置bit 值， 而其他位不变， 并返回。
阅读器算法描述：
Push(00000000);
while(!stackEmpty())
{
Request(GetTop()); // 获得返回的EPC 值;
if(GetCollisionBitsCount(EPC)>2)
Push(ReverseBit(GetTop()， RandomSelectCollisionBit(EPC)));
else
{
pop();
Switch(GetCollisionBitsCount(EPC))
Case0:
Select(EPC);
ReadData(EPC);
Unselect(EPC);
break;
Case1:
EPC0=SetCollision(EPC， 0);
Select(EPC0);
ReadData(EPC0);
Unselect(EPC0);
EPC0=SetCollision(EPC,1);
Select(EPC0);
ReadData(EPC0);
Unselect(EPC0);
break;
Case2:
for(i=0;i<4， i++)
{
EPC0=SetCollision(EPC,i);
Select(EPC0);
ReadData(EPC0);
Unselect(EPC0);
}
break;
}
}
5 算法复杂度和通信信道分析
本文这种迂回式算法受到标签数量以及碰撞对数的限制， 假设n 个标签中这样无重叠的理想碰撞标签对(任意两组标签对中无相同的标签)有m （m≤n/2） 组， 则在最理想的情况下(这个要由好的随机算法提供)算法的总的询问次数为： R （n， m） =2 （n-m） -3。在本文基于迂回式的算法发送REQUEST 命令的次数为5 次（R （6， 2））， 而参考文献[5]中提出的算法的询问次数为7 次， 读写速度提高28%， 对于标签较多的环境中将会高效完成读写动作。
6 结语
通过本文对标签的处理过程可以看出读写过程实际上是请求与检测的过程重复进行， 当碰撞位小于等于2 时可以快速高效的识别出标签， 而当碰撞位大于2 时则通过屏蔽位的方式继续发送请求命令直到碰撞位小于等于2， 正是通过反复迂回的方式从而大大减小了请求次数，提高了读写的速度， 从而实现了高效率的控制。
解决碰撞问题的算法有ALOHA算法、分隙ALOHA算法和二进制树形搜索算法， 但这几种算法都有一个共同的缺陷： 信道利用率比较低。本文提出了一种新的反碰撞算法， 这种算法是在传统的二进制树算法基础上， 通过迂回式反碰撞算法， 利用二进制位取值的互异（即非0 即1）的特性， 以及连续两位发生冲突（即00， 01， 10， 11）， 可同时识别出1~4 个标签， 进而提高阅读器识别标签的效率， 在信道利用率上远远优于其它算法。
1 射频识别系统的工作原理
射频识别系统的工作频段有低频， 中频， 高频， 超高频及微波之分， 而在工业中通常采用13.56MHz 的频率。对于从阅读器与电子标签间数据传递， 通常采用振幅键控ASK （AmplitudeShiftKeying）、频移键控FSK(FrequencyShiftKeying)和相移键控PSK （PHASEShiftKeying）。ASK 和PSK 常被使用， 因为它们特别容易解调， 其原理参见图1。由图1 中可知， 当有多于1个的标签在阅读器的作用范围内时， 且传递的数据0/1 交错时， 将会出现1个标签谐振， 1个标签失谐的情况。这时就阅读器则很难通过判断输出端的高低电位来读出标签的内部信息， 这就是我们要解决的碰撞问题。
二进制搜索算法， 是以一个独特的序列号(UID)来识别标签为基础的， 为了能辨认出阅读器中数据碰撞比特位的准确位置， 传统采用曼彻斯特编码。该编码采用电平的上升沿和下降沿来表示数值位。本文中假设上升沿编码为逻辑“0”， 下降沿编码为逻辑“1”， 若状态跳变， 视为无效数据且作为错误码被识别。如在多标签的环境中当同时有上升沿和下降沿同时存在是， 则会互相抵消从而无状态跳变， 以此阅读器判断发生碰撞的准确位数而再次搜索。假设有6 个RFID 标签， 其相应EPC代码为8 位， 利用曼彻斯特编码能准确识别出碰撞位的示意图如图2 所示， 图中用红色部分为碰撞位。
本文约定在阅读器作用范围内的所有标签能在同一时刻同步传送响应数据， 以便准确地监测碰撞位的发生。为了便于表述算法， 还需要引入4 种命令：
1） REQUEST： 表示阅读器发送一个呼叫参数给区域内标签， 所有标签的EPC 与之进行“与运算”， 结果全为0 的标签将各自的EPC返回至阅读器。在第1 次询问时， 呼叫参数应全为0， 即Request 命令为： Request(00000000)， 这样区域内所有标签都会应答。
2） SELECT： 用某个（事先确定的） EPC 作为参数发送给标签。具有相同EPC 的标签将以此作为执行其他命令（例如读出和写入数据）的切入开关， 即选择这个标签。
3） READ/DATA： 选中的标签将存储的数据发送给阅读器）。
4） UNSELECT： 取消一个事先选中的标签， 标签进入“休眠”状态。在该状态下标签对收到的REQUEST 命令不作应答。为了重新激活标签， 须将标签移出阅读器的作用范围再进入， 以实行复位。
3 算法原理
假设阅读器作用范围内有6 个标签， 阅读器在本文约定的环境中识别这些标签， 最初阅读器对区域内标签处于未知状态， 发送Request（00000000） 命令， 此时阅读器周边区域内所有的标签则同步应答。详细数据处理过程如下：
Step1： 阅读器发送Request （00000000） 命令。区域内所有标签的与运算结果全为0， 即所有的标签返回自身8 位的EPC 代码应答。根据曼彻斯特编码原理， 可解码得EPC 数据为： “$$1$$$10”， 即D2， D3， D4， D6， D7 位发生碰撞。算法作以下的处理： 从5 个碰撞位随机选择一位， 如D7； 然后将上一次Request命令中的参数00000000 的D7 位取反， 得下一次Request 命令所需的参数： 10000000。
Step2： 阅读器发送Request （10000000） 命令。则此时区域内D7位是0 的标签应答， 即标签1 不相应， 标签2~ 标签6 应答， 同理可解码得EPC 数据为： “0$1$$$10”， 碰撞位有： D2， D3， D4， D6， 位。算法作以下的处理： 从4 个碰撞位随机选择一个， 如D3； 然后将上一次Request 命令中的参数10000000 的D3 位取反， 得下一次Request命令所需的参数： 10001000。
Step3： 阅读器发送Request （10001000） 命令。区域内的D3 和D7 都是0 的标签应答， 此时只有标签4 应答， 其他标签不响应， 在这种情况下没有碰撞位， 阅读器可以直接将收到的EPC 值用SELECT 命令发给标签4 并进行读写操作， 处理完成后执行Unselect 命令， 屏蔽掉标签4， 使它处于“休闲” 状态。算法再采用回溯策略， 从该节点的父节点获得下一次Request 命令所需的参数： 10000000。
Step4： 阅读器发送Request ( 1000 0000) 命令。区域内D7 位是0 的标签应答， 即标签2， 标签3， 标签5， 标签6 应答， 同理可解码得EPC 数据为： 0$101$10， 碰撞位有： D2， D6， 位， 此时只有两个碰撞位， 则读写器可依次通过SELECT 命令发送“00101010”，“00101110”， “01101010”， “01101110”， 从而完成标签5， 标签2， 标签6 的读写操作， 最后通过UNSELECT 命令将些三个标签置于“休闲” 状态。算法再采用回溯策略， 从该节点的父节点获得下一次Request 命令所需的参数： 00000000。
Step5： 阅读器发送Request(00000000)命令。区域内所有处于非“哑吧” 状态的标签应答， 即标签1 与标签3 应答， 同理可解码得EPC数据为： $0101010， 此时碰撞位只有D7 位。则读写器可依次通过SELECT命令发送00101010， 10101010， 从而完成标签3 和标签1 的读写操作， 最后通过UNSELECT 命令将标签3 和标签1 置于“休闲” 状态。算法再采用回溯策略， 从该节点的父节点获得下一次Request 命令所需的参数， 由于已到树根无父节点， 因此识别过程结束。图3 为识别读写全部标签的流程图：
1） 阅读器发Request （00000000） 命令， 要求区域内所有标签应答。
2） 检测有无碰撞发生。若无碰撞时， 可识别出一个单独的标签。标签值为应答时返回的EPC 值。处理完后， 再屏蔽掉它。
3） 若有碰撞， 可分两种情况， 如碰撞位>2， 则可从碰撞位中随机选择一位， 并由选中的那一位和上一次REQUEST 中的参数共同决定下一次Request 命令所需的参数， 具体如下： 在上一次REQUEST 命令中参数的基础上再对所选中的那一位取反， 即可得下一次REQUEST命令的参数。
4） 若碰撞位<=2 时， 可通过改变相应两位的数值即00， 01， 10， 11 的值以同时识别出4 个标签， 另外下一次Request 命令所需参数， 采用回溯策略， 从其父节点获得， 通过迂回方式直到执行Request(00000000)命令返回值碰撞位小于2 时读写结束。
4 系统的软件实现
以下程序为实现读写过程的子程序：
Push(EPC)： 将EPC 值入栈；
Pop()： 将栈顶元素弹出；
GetTop()： 返回栈顶元素；
StackEmpty()： 栈空返回true， 不空返回false；
Request(EPC)： 阅读器将EPC 发送给标签；
GetCollisionBitsCount_(EPC)： 返回EPC 值中碰撞位的数目；
RandomSelectCollisionBit(EPC)： 返回从EPC 中随机选择的一个碰撞位的下标；
ReverseBit(EPC， n)： 将EPC 的第n 位取反， 并返回取反后的EPC 值；
SetCollision(EPC， bit)： 将EPC 的碰撞位置bit 值， 而其他位不变， 并返回。
阅读器算法描述：
Push(00000000);
while(!stackEmpty())
{
Request(GetTop()); // 获得返回的EPC 值;
if(GetCollisionBitsCount(EPC)>2)
Push(ReverseBit(GetTop()， RandomSelectCollisionBit(EPC)));
else
{
pop();
Switch(GetCollisionBitsCount(EPC))
Case0:
Select(EPC);
ReadData(EPC);
Unselect(EPC);
break;
Case1:
EPC0=SetCollision(EPC， 0);
Select(EPC0);
ReadData(EPC0);
Unselect(EPC0);
EPC0=SetCollision(EPC,1);
Select(EPC0);
ReadData(EPC0);
Unselect(EPC0);
break;
Case2:
for(i=0;i<4， i++)
{
EPC0=SetCollision(EPC,i);
Select(EPC0);
ReadData(EPC0);
Unselect(EPC0);
}
break;
}
}
5 算法复杂度和通信信道分析
本文这种迂回式算法受到标签数量以及碰撞对数的限制， 假设n 个标签中这样无重叠的理想碰撞标签对(任意两组标签对中无相同的标签)有m （m≤n/2） 组， 则在最理想的情况下(这个要由好的随机算法提供)算法的总的询问次数为： R （n， m） =2 （n-m） -3。在本文基于迂回式的算法发送REQUEST 命令的次数为5 次（R （6， 2））， 而参考文献[5]中提出的算法的询问次数为7 次， 读写速度提高28%， 对于标签较多的环境中将会高效完成读写动作。
6 结语
通过本文对标签的处理过程可以看出读写过程实际上是请求与检测的过程重复进行， 当碰撞位小于等于2 时可以快速高效的识别出标签， 而当碰撞位大于2 时则通过屏蔽位的方式继续发送请求命令直到碰撞位小于等于2， 正是通过反复迂回的方式从而大大减小了请求次数，提高了读写的速度， 从而实现了高效率的控制。
