文章目录
一、引言 （二）RFID技术
无线射频辨识即射频识别技术（Radio Frequency Identification，RFID），是手动辨识技术的一种，通过无线射频形式进行非接触单向数据通讯，利用无线射频方法对记录媒体（电子标签或射频卡）进行读写，从而达到辨识目标和数据交换的目的，其被觉得是21世纪最具发展潜力的信息技术之一。
无线射频识别技术通过无线电波不接触快速信息交换和储存技术，通过无线通讯结合数据访问技术，然后联接数据库系统，加以实现非接触式的双向通信，从而达到了辨识的目的，用于数据交换，串联起一个非常复杂的系统。在辨识系统中，通过电磁波实现电子标签的读写与通讯。根据通讯距离，可分为近场和远场，为此读/写设备和电子标签之间的数据交换方法也对应地被分为负载调制和反向散射调制。
（二）RFID多标签冲突问题
RFID读写器正常情况下一个时间点只能对磁场中的一张RFID卡进行读或写操作，但是实际应用中常常有当多张卡片同时步入读写器的射频场，读写器如何处理呢?读写器须要选出特定的一张卡片进行读或写操作，这就是标签防碰撞。
防碰撞机制是RFID技术中特有的问题。在接触式IC卡的操作中是不存在冲突的，因为接触式智能卡的读写器有一个专门的卡座，而且一个卡座只能插一张卡片，不存在读写器同时面对两张以上卡片的问题。常见的非接触式RFID卡中的防冲突机制主要有以下几种。
二、面向比特的防冲突机制
高频的ISO14443A使用这些防冲突机制，其原理是基于卡片有一个全球惟一的序列号。比如Mifare1卡，每张卡片有一个全球惟一的32位二进制序列号。显而易见，卡号的每一位上不是"1"就是"0"，而且因为是全世界惟一，所以任何两张卡片的序列号总有一位的值是不一样的，也就说总存在某一位，一张卡片上是"0"，而另一张卡片上是"1"。 当两张以上卡片同时步入射频场，读写器向射频场发出卡呼叫命令，问射频场中有没有卡片。这些卡片同时回答"有卡片"; 然后读写器发送防冲突命令"把大家的卡号告诉我"，收到命令后所有卡片同时回送自己的卡号。 可能这种卡片卡号的前几位都是一样的。比如前四位都是1010，第五位上有一张卡片是"0"而其他卡片是"1"，于是所有卡片在一起说自己的第五位卡号的时侯，由于有卡片说"0"，有卡片说"1"，读写器听下来发生了冲突。 读写器测量到冲突后，对射频场中的卡片说，让卡号前四位是"1010"，第五位是"1"的卡片继续说自己的卡号，其他的卡片不要发言了。 结果第五位是"1"的卡片继续发言，可能第五位是"1"的卡片不止一张，于是在这种卡片回送卡号的过程中又发生了冲突，读写器一直用前面的办法让冲突位是"1"的卡片继续发言，其他卡片严禁发言，最终经过多次的防冲突循环，当只剩下一张卡片的时侯，就没有冲突了，最后胜出的卡片把自己完整的卡号回献给读写器，读写器发出卡选择命令，这张卡片就被选中了，而其他卡片只有等待上次卡呼叫时才会再度参与防冲突过程。
上述防冲突过程中，当冲突发生时，读写器总是选择冲突位为"1"的卡片胜出，当然也可以指定冲突位为"0"的卡片胜出。 上述过程有点拟人化了，实际情况下读写器是如何晓得发生冲突了呢?在上面的数据编码中我们早已提及，卡片向读写器发送命令使用副扩频调制的曼侧斯特(Manchester)码，副扩频调制时隙的右半部份表示数据"0"，副扩频调制时隙的左半部份表示数据"1"，当发生冲突时，由于同时有卡片回送"0"和"1"，导致整个时隙都有副扩频调制，读写器收到这样的时隙，就晓得发生冲突了。 这种方式可以保证任何情况下都能选出一张卡片，即使把全世界同类型的所有卡片都用来防冲突，最多经过32个防冲突循环才能选出一张卡片。缺点是因为卡序列号全世界惟一，而卡号的宽度是固定的，所以某一类型的卡片的生产数目也是一定的，比如常见的Mifare1卡，由于只有4个字节的卡序列号，所以其生产数目最多为2的32次方，即4294967296张。
三、面向扩频的防冲突机制
ISO14443B中使用这些防冲突机制。这里的单播(timeslot)其实就是个序号。这个序号的取值范围由读写器指定，可能的范围有1-1、1-2、1-4、1-8、1-16。当两张以上卡片同时步入射频场，读写器向射频场发出卡呼叫命令，命令中指定了扩频的范围，让卡片在这个指定的范围内随机选择一个数作为自己的临时辨识号。然后读写器从1开始叫号，如果叫到某个号刚好只有一张卡片选择了这个号，则这张卡片被选中胜出。如果叫到的号没有卡片应答或则有少于一张卡片应答，则继续向上叫号。如果取值范围内的所有号都叫了一遍还没有选出一张卡片，则重新让卡片随机选择临时辨识号，直到叫出一张卡片为止。 这种办法不要求卡片有一个全球惟一序列号，所以卡片的生产数目没有限制，但是理论上存在一种可能，就是永远也选不出一张卡片来。 Felica采用的也是这些机制。
四、位和单播相结合的防冲突机制
ISO15693中使用这些机制。一方面每张卡片有一个7字节的全球惟一序列号，另一方面读写器在防冲突的过程中也使用扩频叫号的方法，不过这儿的号不是卡片随机选择的，而是卡片惟一序列号的一部分。 叫号的数值范围分为0-1和0-15两种。其大体过程是，当有多张卡片步入射频场，读写器发出清点恳求命令，假如指定卡片的叫号范围是0-15，则卡片序列号最低4位为0000的卡片回送自己的7字节序列号。如果没有冲突，卡片的序列号就被登记在PCD中。然后读写器发送一个帧结束标志，表示让卡片序列号最低4位为0001的卡片做出应答;之后读写器每发送一个帧结束标志，表示序列号的最低4位加1，直到最低4位为1111的卡片被要求应答。如果此过程中某一个卡片回送序列号时没有发生冲突，读写器就可选择此张卡片;如果巡检过程中没有卡片反应，表示射频场中没有卡片;如果有卡片反应的单播发生了冲突，比如最低4位是1010的卡片回送卡号时发生了冲突，则读写器在下一次防冲突循环中指定只有最低4位是1010的卡片参与防冲突，然后用卡片的5-8位作为单播，重复上面的巡检。如果被叫卡片的5-8位单播也相同，之后再用卡片的9-12位作为单播，重复上面的巡检，依次类推。读写器可以从高位起指定任意位数的序列号，让卡号高位和指定的高位序列号相同的卡片参与防冲突循环，卡片用指定号后面的一位或4位作为单播对读写器的叫号做出应答。由于卡片的序列号全球惟一，所以任何两张卡片总有某个连续的4位二进制数不一样，因而总能选出一张卡片。需要强调的是，当选取的单播数为1时，这种防冲突机制等同于面向比特的防冲突机制。
五、确定性标签防冲突算法 （一）简介
目前在给出的关于RFID系统的ISO/IEC标准中，应用的确定性标签防冲突算法如下：
在ISO 14443标准中，TYPE A中使用的是二进制树搜索算法。
在ISO 18000-３标准中，MODE２使用的是FTDMA算法。
在ISO 18000-６标准中，TYPEＢ使用的是二进制树搜索算法。
（二）二进制树型搜索算法（BS）
二进制树型搜索算法（Binary Search）属于时分多路算法的一种，按照递归的形式遇见有冲突发生就进行分枝，生两个子集。当这种分枝越来越细，直到最后分枝下边只有一个信息包或无剩余信息包。若在某扩频发生冲突，所有的包都不再占用信道，直到冲突问题解决。如同抛一枚硬币一样，这些信息包随机的分为两个分枝，在第一个分枝里，是抛０面的信息包，在接下来的扩频内，主要解决这种信息包发生的冲突，如果再度有冲突，则继续按前述分为两个分枝，过程不断重复，直到某个码元为空或是成功完成一次的数据传输rfid读写器的功能是什么，然后返回上一个分枝，这个过程遵守First-in Last-out的原则，先处理完成第一个分支，再来传输第二个分枝，也就是抛１面的信息包。
二进制搜索算法是借助逐渐降低发生冲突的位的方式来完成对标签的辨识的。阅读器必须才能准确地发觉发生冲突的位是该算法的前提条件。因此，在该算法中，标签的返回讯号的编码方法使用了Manchester编码。在Manchester编码方法中，每个讯号比特中间引入跳变来同时代表不同数值和同步信息。一个负电平到Ｊ下电平的跳变代表逻辑"Ｏ"，而一个正电平到负电平的跳变则代表逻辑"ｌ"。在数据传输过程中"没有变化＂的状态是不容许的。因此，当一个阅读器收到标签的返回讯号后，如果发觉个别位讯号的状态没有发生改变，那么阅读器才能够判定那些位一定发生了互相之间的冲突。
（三）基于位仲裁的二进制树算法（BBT）
在基于位仲裁（Bit Binary Tree）的二进制树算法中，所有的处于阅读器读写范围内的未被阅读器辨识的标签在开始时侯都处于激活状态（并不是指这种标签都是主动式标签，而是由阅读器发送命令激活）。所有的这种标签都将出席仲裁过程。但是在一个仲裁过程的进行当中，如果有新的标签进来，不出席本次仲裁的过程。但是，当这次仲裁过程结束后，这些新进来的标签可以出席下一个仲裁过程。一次完整的仲裁过程的定义是：从一次仲裁开始，到一个标签被阅读器所辨识的整个过程。算法的核心思想是：收到阅读器的读写讯号以后，在阅读器读写范围内的所有处于激活状态的标签都发送给阅读器一个位（Ｏ或则１，是标签辨识码（Ｄ）的一位，一般从低位开始）。阅读器收到标签返回讯号后，如果发觉没有冲突，也就是标签返回的都是０或则都是ｌ，阅读器将储存该位信息；而假如阅读器发觉标签返回讯号之间有冲突存在，即返回讯号中既有０也有１，阅读器将选择发送０的一组标签或则发送ｌ的那组标签继续本次仲裁的过程。一旦阅读器选了某组，另外一组在接下来的仲裁过程上将不苒发送讯号给阅读器。本次仲裁过程仍然持续到有某个标签被辨识。被辨识出的标签将不出席下边的仲裁过程。本次仲裁过程结束以后，如果仍有标签未被辨识，将开始一个新的仲裁过程。根据该算法的思想可知，该算法一次仲裁的重复次数与阅读器才能操作的标签数目不相关，仅与标签的ＩＤ的厚度相关。同时仲裁重复的次数与标签的数量有关。假定有珂个标签，每个标签的宽度是ｍ，那么算法须要的全部重复的次数，为 I=nmI = n * mI=nm 可以结合一个事例来说明该算法的执行过程。假定在阅读器读写范围内存在５个标签，它们的辨识码分别是０００００００１（标签１），００００１００１（标签２），００１０００１０（标签３），００１ｌ１０００（标签４），００１１１００１（标签５）。该算法的执行过程可以用2表示。
上图中，出现"？（Ｏ）“号的地方表示标签返回讯号在阅读器处发生了冲突，且冲突后，阅读器选择了发送讯号为０的那一组标签继续本次的仲裁过程。可以看见，５个标签的辨识过程用了５次仲裁过程。而每次仲裁过程，阅读器发送了８次寻问讯号。因此要辨识出这５个标签，阅读器总共发送了４０次寻问讯号，也就是算法总共重复了４０次（５Ｘ８位）。基于位仲裁的二进制树算法才能有效地解决标签之间的冲突问题，但是由算法的特性可以看出，该算法仅适合于标签数量比较少，并且标签的辨识码比较短的RFID系统。但在实际应用中，阅读器常常须要在很短的时间内辨识大量的标签，而且实际的标签的辨识码（ＥＰＣ码）很长（６４位、９６位或２５６位）。所以，该算法并不适合于实际的应用。上图中，出现”？（Ｏ）"号的地方表示标签返回讯号在阅读器处发生了冲突，且冲突后，阅读器选择了发送讯号为０的那一组标签继续本次的仲裁过程。可以看见，５个标签的辨识过程用了５次仲裁过程。而每次仲裁过程，阅读器发送了８次寻问讯号。因此要辨识出这５个标签，阅读器总共发送了４０次寻问讯号，也就是算法总共重复了４０次（５*８位）。基于位仲裁的二进制树算法才能有效地解决标签之间的冲突问题，但是由算法的特性可以看出，该算法仅适合于标签数量比较少，并且标签的辨识码比较短的RFID系统。但在实际应用中，阅读器常常须要在很短的时间内辨识大量的标签，而且实际的标签的辨识码（EPC码）很长（64位、96位或256位）。所以，该算法并不适合于实际的应用。
（四）修正的基于位仲裁的二进制树算法（MBBT）
修正的基于位仲裁的二进制树算法（Modified Bit Binary Tree）的算法原理基本上和基于位仲裁的二进制树算法的算法原理一样，除了一点不同，那就是当两个标签只有最后一位不同，其它位的值都相同的时侯，不需要再进行一次仲裁的过程，而可以直接同时辨识下来两个标签。 修正的基于位仲裁的二进制树算法的执行过程如图
由于标签４和标签５的辨识码不仅最后一位不同外，其它的诸位都相同。所以，在阅读器进行第４次仲裁过程后，可以同时辨识下来这两个标签，而不需要再执行一次仲裁的过程。图3中，识别这５个标签，算法重复的次数是３２次（４*８位）。由修正的基于位仲裁的二进制树算法的执行过程可知，在一些特殊的情况下，和基于位仲裁的二进制算法相比，该算法才能降低算法的重复次数，从而可以减少阅读器读写标签的时间。但是疗效不是很明显，仍须要进一步改进。
（五）动态二进制搜索算法（DBS）
通过研究二进制搜索算法可以发觉，阅读器每次传输的命令厚度都和标签的识别码一样，而且标签的回复讯号也须要把自己的识别码完整的传输给阅读器，不管是早已被辨识下来的位，还是未被辨识下来的位。如前所述，在实际应用中，标签的辨识码一般很长rfid读写器的功能是什么，所以根据二进制搜索算法要传输大量的数据。通过研究二进制搜索方式，研究者提出了动态二进制搜索算法（Dynamic Binary Search ）。该算法中，阅读器在恳求命令中只须要发送须要辨识的识别码的已知部份作为搜索条件，而应答器只须要传输未被辨识的部份。若标签Ｄ宽度为Ｍ bit，则用动态二进制搜索算法每次传送的Ｄ平均宽度为 L=(M+1)/2L = (M + 1) / 2L=(M+1)/2 若标签数为Ｎ个，采用二迸制搜索算法辨识Ｎ个ＩＤ为Ｍbit的标签所须要传输的总数据量（总迭代次数*标签ＩＤ宽度）为 S=MSUM(N)=M[∑i=1r1(i+1)2i1+(r+1)(N2i1)]S=M\bullet SUM(N)=M[\sum_{i=1}^{r-1}(i+1)2^{i-1} + (r+1)(N-2^{i-1})]S=MSUM(N)=M[i=1∑r1(i+1)2i1+(r+1)(N2i1)] 而动态二进制搜索算法需传输的总数据量为 S′=(M+1)[∑i=1r1+(r+1)(N2r1)]/2=S/2S' = (M+1)\bullet [\sum_{i=1}^{r-1}+(r+1)(N-2^{r-1})]/2 =S/2S′=(M+1)[i=1∑r1+(r+1)(N2r1)]/2=S/2
可见，通过这些简单的改动，动态二进制搜索算法要传输的数据数目和所需时间可以比二进制搜索算法降低50%。虽然动态二进制对原有的算法进行了修改后，效率提升了50%，但是这些算法在实际的应用中依然不能满足要求，只适用于少量的标签的应用中。
（六）基于退后索引的动态二进制搜索算法（BDBS）
基于退后索引的动态二进制搜索算法（Back-Off Dynamic Binary Search）算法是二进制搜索算法的另外一种改进算法。和二进制搜索算法相比，有以下两点不同：
当一个标签被辨识出以后，该算法的重复过程和二进制算法有所不同。阅读器下一过程开始所发送恳求命令中的参数和上一过程的倒数第二个恳求命令所发送恳求命令中的参数相同。然后是倒数第三个，第四个等等。该过程仍然反复，直到所有的标签都被辨识。
在第一次恳求命令中，阅读器发送"ＮＵＬＬ"，而不是最大的辨识码。在下一个恳求命令中，阅读器发送已知的位，而不是所有的位。和二进制搜索算法一样，阅读器也是从低位到高位开始搜索。如果标签的识别码的低位和阅读器发送的已知位相同，则标签响应阅读器。
六、随机标签防冲突算法 （一）简介
目前在给出的关于RFID系统的ISO国际标准中，应用的随机标签防冲突算法如下：
在ISO 14443标准中，TYPE Ｂ使用的是扩频ALOHA算法。
在ISO 15693标准中，使用的是扩频ALOHA算法。
在ISO 18000-3标准中，MODEｌ使用的是扩频ALOHA算法。
在ISO 18000-6标准中，TYPEＡ使用的是ALOHA算法。
（二）ALOHA算法和单播ALOHA算法
在RFID系统中，ALOHA算法主要是用在只读标签系统中。在RFID系统中，ALOHA算法是由标签驱动的随机ＴＤＭＡ过程。这就意味着一旦一个标签步入一个阅读器的读写范围，它将主动发送数据给阅读器。在这样一个系统中，标签和阅读器之间的通讯数据量比较小，主要是标签的辨识码。在ALOHA算法中，标签周期性的发送数据给阅读器。标签发送数据的时间是整个周期的一小部份。第一次发送数据给阅读器以后，标签要等待一段相当长的时间后才再一次发送数据给阅读器。通过这些方法，直到所有标签都完成发送数据给阅读器后，整个重复周期才停止。考虑ALOHA的这些工作机制可知，如果多个标签在同时发送它们的数据给阅读器，或者在一个标签正在发送它的数据给阅读器的过程中，另外的标签也开始发送过程，必然会导致标签之间的互相冲突。当阅读器读写区域内的标签数量极其多的时侯，这种冲突的概率会剧烈降低，导致系统的吞吐量大幅减弱。因此，该算法仅仅适用于标签的数量比较小，而且标签和阅读器之间的数据交换量也比较小的情况（如果标签和阅读器之间的数据交换量比较大的话，将会对标签辨识引起很大的信噪比）。而对于标签数量比较大，而且阅读器和标签之间的数据交换量比较大的情况，必须对ALOHA算法加以改进。时隙ALOHA算法正是基于这样一个思想而发展上去的。时隙ALOHA是第一个ALOHA的改进算法，该算法的吞吐量是ALOHA算法的吞吐量的两倍。在该算法中，标签只能在每位单播的开始发送数据给阅读器，时隙的多少和起始时间由阅读器所控制。很显然，和ALOHA算法不同，时隙ALOHA是一个随机的、由阅读器驱动的ＴＤＭＡ防冲突算法。因为标签只能在每位单播的起始发送数据，从而致使冲突发生的时间间隔只有ALOHA算法的一半。所以，该算法的吞吐量是ALOHA算法的两倍。表４表明了扩频ALOHA算法的执行过程。
“Downlink"表示"下行信道”，即从阅读器到标签的通讯；“Uplink"表示"上行信道”，即从标签到阅读器的通讯。从表４可以看出，标签ｌ在扩频ｌ和单播２中都发送其数据给阅读器。时隙１和单播２都发生了标签之间的互相冲突。在扩频３中只有标签５发送数据给阅读器，所以没有冲突发生，标签５发送数据成功。该过程重复执行到所有的标签都被阅读器所辨识为止。
（三）帧扩频ALOHA算法（FSA）
尽管扩频ALOHA算法比ALOHA算法的吞吐量提高了一倍，但是假如在阅读器的读写范围内的标签特别大的时侯，该算法的效率也会很快增加。帧扩频ALOHA是扩频ALOHA的一个改进算澍。和单播ALOHA算法相比，帧单播ALOHA算法的最大的不同之处就是，通信信道被分为若干个帧，每帧又分割为若干扩频。标签在一个数据帧之内只能选择一个扩频进行数据的传输。这就意味着在一个数据帧之内，一个标签最多只能传输一次。图5简略描述了帧扩频ALOHA算法的执行过程。
"Downlink"和"Uplink"的含意和表4相同。"Frame i"示阅读器发送的第ｉ个恳求命令帧。和单播ALOHA算法一样，帧扩频ALOHA算法将持续执行，直到所有的标签都被阅读器所辨识。
（四）动态帧扩频ALOHA算法（DFSA）
在FSA算法执行的过程中，阅读器所发送的所有的恳求命令帧的宽度都相同，即发送的每帧中的扩频的数量都相同（每个码元的宽度都是相同的，便于算法的操作）。这在很大程度上限制了FSA算法的效率，可以说是FSA算法的一个致命缺点。在实际的应用过程中，标签的数量往旧事先并不可知，这都会出现两种情况。一种情况是实际标签的数量远小于阅读器恳求命令帧中的扩频数量；另外一种情况和第一种情况相反，就是实际标签的数量大大大于阅读器恳求命令帧中的扩频数量。在第一种情况下，由于标签的数量太多，而阅读器恳求命令帧中的扩频数量太少，就必然会导致多个标签争用一个扩频的情况增多。这都会造成标签之间的互相冲突，从而促使有些标签在较长时间内还不能得到辨识，导致阅读器辨识全部标签的时间大大降低。在第二种情况下，由于标签的数量太少，而阅读器恳求命令帧中的扩频数量又太多，就会造成有很多剩余的扩频。从而造成因为不必要的时间浪费而致使阅读器辨识全部标签的时间减小。DFSA算法正是为了解决这样一个问题而提下来的。
七、总结
由于RFID技术具有其他手动辨识技术不可比拟的优点，近年来获得了广泛的关注。本论文从当前获得广泛应用的RFID系统出发，对RFID阅读器防冲突算法进行了较深入的思索和总结。
八、参考文献
