RFID系统的关键技术之防碰撞机制分析与实现

1、防碰撞机制分析与实现防碰撞机制分析与实现教学设计教学设计信息技术学院信息技术学院 李斌李斌一一、教学内容的引入教学内容的引入二二、产生碰撞的原因产生碰撞的原因三三、标签的几种状态标签的几种状态四四、防碰撞机制的实现防碰撞机制的实现主要内容主要内容五五、读写器读写器防碰撞机制的实现防碰撞机制的实现一一、教学内容的引入教学内容的引入EPC class1 Gen2 Tag一一、教学内容的引入教学内容的引入1 1、ReservedReserved区：存储区：存储Kill PasswordKill Password（灭活口令）和（灭活口令）和Access PasswordAccess Password（

2、访（访问口令）。问口令）。 2 2、EPCEPC区：存储区：存储EPCEPC号码等。号码等。 3 3、TIDTID区：存储标签识别号码，每个区：存储标签识别号码，每个TIDTID号码应该是唯一的。号码应该是唯一的。 4 4、UserUser区：存储用户定义的数据。区：存储用户定义的数据。 HeaderFilter Value(Optional)Domain IdentifierEPCEPC编码结构编码结构Standard EPC Tag DataHeaderGeneralManagerNumberObject ClassSerial NumberGeneral Identifier (GID-

3、96)Header 8 bitsManufacture 28 bitsProduct 24 bitsSerial Number36 bits一一、教学内容的引入教学内容的引入1 1、上次我们实验中其读写距离是多少？、上次我们实验中其读写距离是多少？2 2、UHF EPC Gen2UHF EPC Gen2的标签有几种种状态？的标签有几种种状态？ 3、为什么每次读写的标签的数量会为什么每次读写的标签的数量会不一样？各组之间的读写器之间是否不一样？各组之间的读写器之间是否存在干扰？存在干扰？一一、教学内容的引入教学内容的引入问题探究问题探究二二、产生碰撞的原因产生碰撞的原因 在在RFID系统应用中，

4、因为多个读写器或多个标系统应用中，因为多个读写器或多个标签，造成的读写器之间或标签之间的相互干扰，签，造成的读写器之间或标签之间的相互干扰，统称为统称为碰撞碰撞。1、读写器碰撞、读写器碰撞2、标签碰撞、标签碰撞Data1Data5Data4Data3Data5Data4Data3Data2Data2Data1RFID数据碰撞示意图数据碰撞示意图二二、产生碰撞的原因产生碰撞的原因TimeTime完全碰撞完全碰撞Time读写器读写器TagATagB二二、产生碰撞的原因产生碰撞的原因R1RrRrReader2Reader1读写器读写器- -读写器频率干扰读写器频率干扰 R1R1为为Reader1Re

5、ader1的的干扰范围干扰范围 RrRr为为Reader1Reader1和和Reader2Reader2的读取范围的读取范围 从标签从标签T T反射到读写反射到读写器器Reader2Reader2的信号很容的信号很容易被从易被从Reader1Reader1发出的发出的信号干扰。信号干扰。Tag二二、产生碰撞的原因产生碰撞的原因Tag3Tag2Tag1Reader1Reader2多读写器一标签干扰多读写器一标签干扰 标签标签1 1接收到的信息为两个读写器发射信号接收到的信息为两个读写器发射信号的矢量和的矢量和, ,是一个未知信号。是一个未知信号。识别识别标签标签准备准备掉电掉电数据交互数据交互标

6、签的几种状态标签的几种状态三三、标签的几种状态标签的几种状态掉电掉电准备准备识别识别数据数据交互交互上电上电选择选择取消取消选择选择碰撞碰撞仲裁仲裁读操作读操作读操作读操作读操作读操作复位复位标签状态转换图标签状态转换图四四、防碰撞机制的实现防碰撞机制的实现三三、标签的几种状态标签的几种状态 如何解决碰撞如何解决碰撞的问题呢？的问题呢？四四、防碰撞机制的实现防碰撞机制的实现四四、防碰撞机制的实现防碰撞机制的实现读写器读写器Tag3Tag5Tag2Tag6Tag4Tag7Tag11 1、空分多址、空分多址SDMASDMA法法1、空间分割多重存取、空间分割多重存取ReaderTagTagTag四四

7、、防碰撞机制的实现防碰撞机制的实现 分离的空间范围分离的空间范围内重新使用确定的资源内重新使用确定的资源（通信容量）（通信容量）1、自适应、自适应SDMA，电子控，电子控制定向天线，天线的方向制定向天线，天线的方向直接对准某个标签直接对准某个标签2 2、减少单个读写、减少单个读写器的作用范围器的作用范围四四、防碰撞机制的实现防碰撞机制的实现读读写写器器Tag1Tag3Tag5Tag4Tag2阅读器广播命令阅读器广播命令阅读器读写区域阅读器读写区域f1f2f3f4f52、频分多址、频分多址FDMA法法2、频率分割多重存取、频率分割多重存取ReaderTagTagTaga ab bc cabc四四

8、、防碰撞机制的实现防碰撞机制的实现 把若干个使用不同载波频率的把若干个使用不同载波频率的传输通路同时供给通信用户使用传输通路同时供给通信用户使用。3、时间分割、时间分割TDMAa b cabcReaderTag1Tag2Tag3aabbcc四四、防碰撞机制的实现防碰撞机制的实现 TDMA TDMA是把整个可供使用的信是把整个可供使用的信道容量按时间分配给多个同户道容量按时间分配给多个同户的技术。的技术。掉电掉电准备准备识别识别数据数据交互交互上电上电选择选择取消取消选择选择碰撞碰撞仲裁仲裁读操作读操作读操作读操作读操作读操作复位复位标签状态转换图标签状态转换图四四、防碰撞机制的实现防碰撞机制的

9、实现四四、防碰撞机制的实现防碰撞机制的实现算法算法 ISO18000-6协议中使用的协议中使用的是一种是一种类二进制树形防碰撞算类二进制树形防碰撞算法法，通过标签内随机产生，通过标签内随机产生0、1及内置计数器实现标签的防碰及内置计数器实现标签的防碰撞。撞。防碰撞的基本算法防碰撞的基本算法四四、防碰撞机制的实现防碰撞机制的实现树分叉算法树分叉算法冲突节点冲突节点非冲突节点非冲突节点011011100101树分叉算法树分叉算法四四、防碰撞机制的实现防碰撞机制的实现基本思想是：基本思想是：将处于碰撞的标将处于碰撞的标签分成左右两个子集签分成左右两个子集0 0和和1 1，先，先查询子集查询子集0 0

10、，若没有碰撞，则，若没有碰撞，则正确识别标签，若仍有碰撞则正确识别标签，若仍有碰撞则分裂，把分裂，把1 1子集分成子集分成0000和和0101两两个子集，直到识别子集个子集，直到识别子集1 1中所中所有标签。有标签。（1 1）所有处于）所有处于“识别识别”状态且内部计数器为状态且内部计数器为0 0的应答器发送它们的识别码。的应答器发送它们的识别码。（2 2）当有一个以上的标签发送时，读写器因不能正确识别信号为发送）当有一个以上的标签发送时，读写器因不能正确识别信号为发送FAILFAIL指令指令。（3 3）所有接收到）所有接收到FAILFAIL指令且内部计数器不等于指令且内部计数器不等于0 0的

11、标签计数器加的标签计数器加1 1。所有接收所有接收到到FAILFAIL指令且内部计数器等于指令且内部计数器等于0 0的标签将产生一个的标签将产生一个1 1或者或者0 0的随机数，的随机数，如果是如果是1 1，则标签计数器加则标签计数器加1 1，如果是，如果是0 0，则标签计数器保持不变，并再次发送其识别码。，则标签计数器保持不变，并再次发送其识别码。四四、防碰撞机制的实现防碰撞机制的实现 所有接收到所有接收到FAILFAIL指令且内部计数器不等于指令且内部计数器不等于0 0的标签计数器加的标签计数器加1 1。所有接收到。所有接收到FAILFAIL指令且内部计数器等指令且内部计数器等0 0的标签

12、将产生一个的标签将产生一个1 1或者或者0 0的随机数，如果是的随机数，如果是1 1，则标，则标签计数器加签计数器加1 1，如果是，如果是0 0，则标签计数器保持不变，并再次发送其识别码。，则标签计数器保持不变，并再次发送其识别码。（4）a、若有一个以的标签发送，则重复步骤（若有一个以的标签发送，则重复步骤（2 2）;b;b、若只有一个发送，、若只有一个发送，则读写器发送包含识别码的则读写器发送包含识别码的“DATA_READDATA_READ”，指令，标签正确接收此指令进入，指令，标签正确接收此指令进入“数据交互数据交互”，通信完成后，发送，通信完成后，发送SUCCESSSUCCESS指令；

13、指令；C C、当标签没有被正确接收，、当标签没有被正确接收，则读写器将发送一个则读写器将发送一个RESENDRESEND指令。指令。（1 1）REQUEST请求(序列号)。此命令发送一序列号作为参数给射频卡。应答规则是，射频卡把自己的序列号与接收到的序列号比较，如果自身序列号小于或等于REQUEST指令序列号参数，则此射频卡回送其序列号给读写器。这样可以缩小预选的射频卡的范围；如果大于，则不响应。四四、防碰撞机制的实现防碰撞机制的实现 所有接收到所有接收到FAILFAIL指令且内部计数器不等于指令且内部计数器不等于0 0的标签计数器加的标签计数器加1 1。所有接收到。所有接收到FAILFAIL

14、指令且内部计数器等指令且内部计数器等0 0的标签将产生一个的标签将产生一个1 1或者或者0 0的随机数，如果是的随机数，如果是1 1，则标，则标签计数器加签计数器加1 1，如果是，如果是0 0，则标签计数器保持不变，并再次发送其识别码。，则标签计数器保持不变，并再次发送其识别码。 (2)SELECT(2)SELECT选择选择( (序列号序列号) )。用某个。用某个( (事先确定的事先确定的) )序列号序列号作为参数发送给射频卡。具有相同序列号的射频卡将以此作作为参数发送给射频卡。具有相同序列号的射频卡将以此作为执行其他命令为执行其他命令( (例如读出和写入数据例如读出和写入数据) )的切入开关

15、，即选择的切入开关，即选择这个射频卡。具有其他序列号的射频卡只对这个射频卡。具有其他序列号的射频卡只对REQUESTREQUEST命令应答。命令应答。 （3 3）READ-DATA读出数据。选中的射频卡将存储的数据发送给读写器。 四四、防碰撞机制的实现防碰撞机制的实现 (4)UNSELECT(4)UNSELECT 去选择去选择。取消一个事先选中的射频卡，射频卡进入。取消一个事先选中的射频卡，射频卡进入 无声无声 状态，在这种状态下射频卡完全是非激活的，对收到的状态，在这种状态下射频卡完全是非激活的，对收到的REQUESTREQUEST命命令不作应答。为了重新话化射频卡，必须先将射频卡移出读写器

16、的作用令不作应答。为了重新话化射频卡，必须先将射频卡移出读写器的作用范围再进入，以实行复位。范围再进入，以实行复位。 射频卡进入读写器的工作范围，读写器发出一个最大序列号让所有射射频卡进入读写器的工作范围，读写器发出一个最大序列号让所有射频卡响应；同一时刻开始传输它们的序列号到读写器的接收模块。频卡响应；同一时刻开始传输它们的序列号到读写器的接收模块。 读写器对比射频卡响应的序列号的相同位数上的数。读写器对比射频卡响应的序列号的相同位数上的数。出现不一致出现不一致的现象的现象即有的序列号该位即有的序列号该位为为0 0，而有的序列，而有的序列号该位为号该位为1 1 把有不一致位的数从最高位到低位

17、依次置把有不一致位的数从最高位到低位依次置O O再输出系列号，再输出系列号，即依次排除序列号大的数，至读写器对比射频卡响应的序列号即依次排除序列号大的数，至读写器对比射频卡响应的序列号的相同位数上的数完全一致时，说明无碰撞。的相同位数上的数完全一致时，说明无碰撞。选出序列号最小的数后，对该标签进行数据交换，然后使选出序列号最小的数后，对该标签进行数据交换，然后使该卡进入该卡进入“无声无声”状态。状态。YN四四、防碰撞机制的实现防碰撞机制的实现二进制搜索算法的工作流程是：二进制搜索算法的工作流程是：1 10 01 11 10 00 00 00 01 11 11 10 0?射频卡射频卡1射频卡射频

18、卡2读写器译码读写器译码四四、防碰撞机制的实现防碰撞机制的实现 在二进制搜索算法的实现中，起决定作用的是读写器所使用的信号编码在二进制搜索算法的实现中，起决定作用的是读写器所使用的信号编码必须能够确定碰撞的准确比特位置必须能够确定碰撞的准确比特位置。曼彻斯特码曼彻斯特码(Mancherster)(Mancherster)可在多卡同时可在多卡同时响应时，译出错误码字，可以按位识别出碰撞响应时，译出错误码字，可以按位识别出碰撞。这样可以根据碰撞的位置，。这样可以根据碰撞的位置，按一定法则重新搜索射频卡。按一定法则重新搜索射频卡。范例：二元搜寻算法范例：二元搜寻算法A:10100111B:10110

19、101C:10101111D:10111101R:11111111R:11111111送送REQUEST（11111111）命令，要求区）命令，要求区域内所有标签应答，根据曼彻斯特编码，域内所有标签应答，根据曼彻斯特编码，解码数据为解码数据为101?1?1,发生碰撞，算法做发生碰撞，算法做下如下，下如下，将碰撞的最高置将碰撞的最高置0，其它碰撞位，其它碰撞位置置1。得下次的。得下次的REQUEST(10101111)?R R表示阅表示阅读器读器四四、防碰撞机制的实现防碰撞机制的实现范例：二元搜寻算法范例：二元搜寻算法搜寻标签过程搜寻标签过程A:10100111C:10101111R:10101

20、111R:10101111 送送REQUESTREQUEST（1010111110101111）命令，标）命令，标签签A A和和C C应答。解码数据为应答。解码数据为1010?111,1010?111,发发生碰撞，算法做下如下，将碰撞的最高生碰撞，算法做下如下，将碰撞的最高置置0 0，其它碰撞位置，其它碰撞位置1 1。得。得1010011110100111?R R表示阅表示阅读器读器四四、防碰撞机制的实现防碰撞机制的实现范例：二元搜寻算法范例：二元搜寻算法A:10100111C:10101111R:10100111R:10100111 送送REQUESTREQUEST（101001111010

21、0111）命令，只）命令，只有标签有标签A A应答。解码数据为应答。解码数据为1010?111,1010?111,没没有发生碰撞，阅读器对标签有发生碰撞，阅读器对标签A A进行阅读进行阅读操作。操作。R R表示阅表示阅读器读器可以识可以识别别A四四、防碰撞机制的实现防碰撞机制的实现Improved Anti-collision Algorithm搜寻过程搜寻过程第一次搜寻第一次搜寻第二次搜寻第二次搜寻第三次搜寻第三次搜寻第四次搜寻第四次搜寻第五次搜寻第五次搜寻发送序号发送序号接收序号接收序号TagATagATagTagB BTagTagC CTagTagD D四四、防碰撞机制的实现防碰撞机制的

22、实现1010011110110101101011111011110111111111101?1?11010111110100111101011111010?1111010011110100111识别识别TagATagA10110101101011111011110111111111101?1?11010111110101111识别识别TagBTagBImproved Anti-collision Algorithm搜寻过程搜寻过程第六次搜寻第六次搜寻第七次搜寻第七次搜寻第八次搜寻第八次搜寻第九次搜寻第九次搜寻第十次搜寻第十次搜寻发送序号发送序号接收序号接收序号TagATagATagTagB B

23、TagTagC C TagTagD D四四、防碰撞机制的实现防碰撞机制的实现1011010110111101111111111011?10110110101101101011011110110111101识别识别TagCTagC识别识别TagDTagDRFIDRFID读写器防碰撞读写器防碰撞 1 1、RFIDRFID读写器冲突及解决途径读写器冲突及解决途径 v 密集读写器环境中的读写器冲突密集读写器环境中的读写器冲突 五、读写器防碰撞机制的实现五、读写器防碰撞机制的实现 密集读写器环境就是指在密集读写器环境就是指在RFIDRFID系统应用中，在预定区域系统应用中，在预定区域内部署多个内部署多个

24、RFIDRFID读写器，以满读写器，以满足对区域内的所有标签进行完足对区域内的所有标签进行完全的、高可靠的读取要求。系全的、高可靠的读取要求。系统网络中包含多个读写器和一统网络中包含多个读写器和一个中央计算机，读写器与中央个中央计算机，读写器与中央计算机之间一般采用局域网计算机之间一般采用局域网（LANLAN）或无线局域网（）或无线局域网（WLANWLAN）方式进行通信连接。方式进行通信连接。 密集读写器网络拓朴结构密集读写器网络拓朴结构v 分时传输解决读写器冲突分时传输解决读写器冲突 网络中的每个读写器通常具有不网络中的每个读写器通常具有不同范围的识读区域，各读写器的识同范围的识读区域，各读

25、写器的识读区域可能有交集，即识读区域有读区域可能有交集，即识读区域有相互重叠的部分。为了便于说明，相互重叠的部分。为了便于说明，用图用图7-17近似地描绘了密集读写器近似地描绘了密集读写器环境下的读写器冲突。每个圆圈代环境下的读写器冲突。每个圆圈代表一个读写器的识读区域（实际应表一个读写器的识读区域（实际应用中的识读区域可能为不规则形用中的识读区域可能为不规则形状），圆点代表相应的读写器。如状），圆点代表相应的读写器。如果两个读写器的识读区域有相互重果两个读写器的识读区域有相互重叠，如图叠，如图7-17中的中的R1和和R2，则当，则当R1、R2同时工作时，如果不采取同时工作时，如果不采取防冲突

26、措施，就会产生读写器冲突，防冲突措施，就会产生读写器冲突，甚至使整个甚至使整个RFID系统无法正常工作。系统无法正常工作。 五、读写器防碰撞机制的实现五、读写器防碰撞机制的实现密集环境下读写器冲突示意图密集环境下读写器冲突示意图v 分时传输解决读写器冲突分时传输解决读写器冲突 分布式时隙控制方法分布式时隙控制方法以防冲突算法以防冲突算法ColorwaveColorwave和和IRCMIRCM为为代表代表，时隙分配过程以网络中的每个读写器为中心，各读写，时隙分配过程以网络中的每个读写器为中心，各读写器之间相互反复通信协商来确定各自的工作时隙，发生冲突器之间相互反复通信协商来确定各自的工作时隙，发

27、生冲突时往往通过增加新的时隙来解决，结果使得时隙分配过程较时往往通过增加新的时隙来解决，结果使得时隙分配过程较长且需要的总时隙数目多；集中式时隙控制方法几乎不占用长且需要的总时隙数目多；集中式时隙控制方法几乎不占用读写器的资源，通过中央计算机或服务器运行优化算法进行读写器的资源，通过中央计算机或服务器运行优化算法进行时隙分配问题的求解。这种方法求解速度快且不占用读写器时隙分配问题的求解。这种方法求解速度快且不占用读写器资源。资源。 五、读写器防碰撞机制的实现五、读写器防碰撞机制的实现v平面图着色与读写器防冲突平面图着色与读写器防冲突 图图7-18 读写器冲突问题的平面读写器冲突问题的平面图图,

28、RFID读写器读写器冲突问题类似于一冲突问题类似于一个简单的平面图个简单的平面图G=(R，E)。顶点。顶点集合集合R是是RFID读写器集合，即读写器集合，即R=r1，r2，rn)。边集合。边集合E描描述了述了RFID系统中读写器之间的冲突系统中读写器之间的冲突关系。也就是说，如果读写器关系。也就是说，如果读写器Ri和和读写器读写器Rj的识读区域之间存在交集，的识读区域之间存在交集，就将顶点就将顶点ri和和rj用一个无向线段连接用一个无向线段连接起来。据此建立图起来。据此建立图7-17中的读写器中的读写器冲突问题的平面图冲突问题的平面图G=(R，E)如图如图7-18所示。所示。五、读写器防碰撞机

29、制的实现五、读写器防碰撞机制的实现读写器冲突的平面图读写器冲突的平面图v Hopfieid神经网络模型 nn阶对称矩阵 n4阶矩阵 五、读写器防碰撞机制的实现五、读写器防碰撞机制的实现读写器防冲突问题混沌神经网络模型读写器防冲突问题混沌神经网络模型 为了消除网络中的读写器冲突问题，必须使网络中存在冲突关系的读写器工作在不同的时隙。根据这样的约束要求，读写器防冲突神经网络的能量函数如下： 当神经网络的能量函数E的值等于0时，当前的输出矩阵v的值就是读写器防冲突神经网络的可行解。 五、读写器防碰撞机制的实现五、读写器防碰撞机制的实现读写器防冲突问题混沌神经网络模型读写器防冲突问题混沌神经网络模型二

30、维Hopfield神经网络能量函数的一般表达形式： 比较式(3)和式(4)，可以得到： 因此，读写器防冲突神经网络的微分方程为： 五、读写器防碰撞机制的实现五、读写器防碰撞机制的实现v基于退火策略的混沌神经网络模型 Hopfield神经网络模型可以收敛到一个稳定的平衡解，但会经常陷入局部最优 。因此，在上述建立的Hopfield神经网络模型基础上，本文通过引入混沌机制和模拟退火策略，为读写器防冲突建立基于退火策略的混沌神经网络模型如下： 当模拟温度衰减至趋近于0时，混沌状态消失，此后算法获得一个较好的初值，并按照Hopfield神经网络算法继续进行搜索并逐渐收敛于有效解。 五、读写器防碰撞机制的实现五、读写器防碰撞机制的实现v仿真流程仿真流程 采用MATLAB对基于退火策略的混沌神经网络读写器时隙分配算法进行仿真。仿真流程如下：步骤1：设置A，B，C，0，k，a，z(0)， ，Z (0) 等参数的值，如表1。实验中， (0)取0，1区间 的随机数。 步骤2：根据式(10)和(11)计算 (t)。 步骤3：根据式(3)计算能量函数 。 步骤4：根据式(12)计算Z (t+1)。 步骤5：判断能量函数 是否满足稳定条件。如果满足进行步骤6，否则进行步骤2。能量函数的稳定判据为：1) 的值在连续l0次