防碰撞算法

ALOHA算法

ALOHA算法是一种随机接入方法，其基本思想是采取标签先发言的方式，当标签进入读写器的识别区域内时就自动向读写器发送其自身的ID号，在标签发送数据的过程中，若有其他标签也在发送数据，将会发生信号重叠，从而导致冲突。读写器检测接收到的信号有无冲突，一旦发生冲突，读写器就发送命令让标签停止发送，随机等待一段时间后再重新发送以减少冲突。

纯ALOHA算法

在纯ALOHA算法中，若读写器检测出信号存在相互干扰，读写器就会以向电子标签发出命令，令其停止向读写器传输信号；电子标签在接收到命令信号之后，就会停止发送信息，并会在接下来的一个随机时间段内进入到待命状态，只有当该时间段过去后，才会重新向读写器发送信息。各个电子标签待命时间片段长度是随机的，再次向读写器发送信号的时间也不相同，这样减少碰撞的可能性。

纯ALOHA算法虽然算法简单，易于实现。但对于同一个标签，如果连续多次发生碰撞，这将导致读写器出现错误判断认为这个标签不在自己的作用范围内，同时其冲突概率很大。

时隙ALOHA算法

时隙ALOHA算法把时间分成多个离散的时隙，每个时隙长度等于或稍大于一个帧，标签只能在每个时隙的开始处发送数据。这样标签要么成功发送，要么完全碰撞，避免了纯ALOHA算法中的部分碰撞冲突，碰撞周期减半，提高了信道利用率。时隙ALOHA算法需要读写器对其识别区域内的标签校准时间。时隙ALOHA算法是随机询问驱动的TDMA防冲撞算法。

图1 时隙ALOHA算法示意图

因为标签仅仅在确定的时隙中传输数据，所以该算法的冲撞发生频率仅仅是纯ALOHA算法的一半，但其系统的数据吞吐性能却会增加一倍。

帧时隙ALOHA算法

帧时隙算法中，时间被分成多个离散时隙，电子标签必须在时隙开始处才可以开始传输信息。读写器以一个帧为周期发送查询命令。当电子标签接收到读写器的请求命令时，每个标签通过随机挑选一个时隙发送信息给读写器。如果一个时隙只被唯一标签选中，则此时隙中标签传输的信息被读写器成功接收，标签被正确识别。如果有两个或两个以上的标签选择了同一时隙发送，则就会产生冲突，这些同时发送信息的标签就不能被读写器成功识别。整个算法的识别过程都会如此循环，一直到所有标签都被识别完成。

该算法的缺点是当标签数量远大于时隙个数时，读取标签的时间会大大增加；当标签个数远小于时隙个数时，会造成时隙浪费。

图2 帧时隙ALOHA算法

如图2所示，阅读器首先在第一帧内发送请求，5个标签随机选择时隙进行数据发送。可知标签1和标签3均选择时隙1，因此碰撞；标签2和标签4均选择时隙2，因此碰撞；而标签5选择时隙3，发送成功。在第二个帧中，阅读器又先发送请求，剩下的4个标签随机选择时隙进行数据发送。可知标签1和标签4均选择时隙2，因此碰撞；标签2选择时隙3，成功发送；标签3选择时隙1，成功发送。

动态帧时隙ALOHA算法

动态帧时隙ALOHA算法中一个帧内的时隙数目随着区域内标签数目动态改变，或增加时隙数以减少帧中的碰撞数目。步骤如下：

1. 进入识别状态，开始识别命令中包含了初始的时隙数$N$。
2. 由电子标签随机选择一个时隙，同时将自己的时隙计数器复位为1。
3. 当电子标签随机选择的时隙数与时隙计数器对应时，标签向读写器发送数据；若不相等，标签将保留自己的时隙数并等待下一个命令。
4. 当读写器检测到的时隙数量等于命令中规定的循环长度N时，本次循环结束，读写器转入步骤2，开始新的循环。

举一个例子用大白话解释。假设初始时隙数 N=4N = 4N=4，并且有3个电子标签参与通信：

1. 初始化。阅读器发送识别命令，指定时隙数$N=4$，每个电子标签随机选择一个时隙：标签A选择时隙3、标签B选择时隙1、标签C选择时隙3。
2. 时隙1：时隙计数器此时为1，标签B的选择时隙等于当前时隙计数器，因此标签B发送数据，标签A和标签C等待下一个时隙。
3. 时隙2：时隙计数器此时为2，没有标签选择时隙2，因此没有数据发送。
4. 时隙3：时隙计数器此时为3，标签A和标签C都选择了时隙3，发生碰撞，因此标签A和标签C都未成功发送数据。
5. 时隙4：时隙计数器此时为4，没有标签选择时隙4，因此没有数据发送。
6. 读写器检测到时隙数量达到$N=4$，本次循环结束。读写器转入新的循环，可以指定不同的时隙数，转入步骤2。

动态帧时隙ALOHA算法允许根据系统的需要动态地调整帧长度，由于读写器作用范围内的标签数量是未知的，而且在识别的过程中未被识别的标签数目是改变的，因此，如何估算标签数量以及合理地调整帧长度成为动态帧时隙ALOHA算法的关键。由理论推导可知，在标签数目和帧长度接近的情况下，系统的识别效率最高，也就是说标签的值就是帧长度的最佳选择。

在实际应用中，动态帧时隙算法是在每帧结束后，根据上一帧的反馈情况检测标签发生碰撞的次数（碰撞时隙数），电子标签被成功识别的次数（成功时隙数）和电子标签在某个时隙没有返回数据信息的次数（空闲时隙数）来估计当前未被正确识别的电子标签数目，然后选择最佳的下一帧的长度，把它的帧长度作为下一轮识别的帧长，直到读写器工作范围内的电子标签全部识别完毕。

二进制树型搜索算法

二进制树型搜索算法由读写器控制，基本思想是不断的将导致碰撞的电子标签进行划分，缩小下一步搜索的标签数量，直到只有一个电子标签进行回应。选用曼彻斯特编码可实现“二进制树型搜索”算法。

图3 二进制树型搜索算法过程

如图3所示，下面分析二进制树型搜索算法的过程：

1. 阅读器发送请求给电子标签，其中包含一个最大值，表示当前搜索范围的上限（11111111），即请求8位二进制数不大于11111111的所有标签响应。
2. 每个标签都根据自己的ID与请求中的掩码进行匹配。如果匹配成功，则发送自己的ID。在第一轮中，所有标签都匹配“11111111”，因此所有标签都尝试在同一时刻发送，这也就导致了冲突。
3. 第一次选择代：阅读器接收到多个标签的响应，检测到冲突。于是阅读器发出新的请求，限定范围更小。即请求限制“<=10111111”，此时标签1、2、3进行响应。
4. 第二次选择代：阅读器检测到冲突后限定更小的范围，即请求限制“<=10101111”，此时只有标签2可以响应。

编码与调制

信源编码方法

这里要介绍的四种编码方式分别为非归零编码（NRZ）、曼彻斯特编码、密勒编码和修正米勒编码。

图4 四种编码方式

1. 非归零编码：高1低0，编码容易实现，但没有检错功能，且无法判断一个码元的开始和结束，以至于收发双方难以保持同步。比如，发了一长串相同的电平，就无法看出1或0的个数了。
2. 曼彻斯特编码：将一个码元分成两个相等的间隔，前一个间隔为低电平后一个间隔为高电平表示码元1；码元0则正好相反。可以记忆为：前高后低表示1，前低后高表示0。也可以采用相反的规定该编码的特点是在每一个码元的中间出现电平跳变，位中间的跳变既作时钟信号（可用于同步）又作数据信号，但它所占的频带宽度是原始的基带宽度的两倍。每一个码元都被调成两个电平，所以数据传输速率只有调制速率的二分之一。
3. 密勒编码：对于原始符号“1”，用码元起始不跳变而中心点出现跳变来表示，即用10或01表示；对于原始符号“0”，则分成单个“0”还是连续“0”予以不同的处理：单个“0”时，保持“0”前的电平不变，即在码元边界处电平不跳变，在码元中间点电平也不跳变对于连续两个“0”，则使连续两个“0”的边界处发生电平跳变。
4. 修正密勒编码：每位数据中间有个窄脉冲表示“1”，数据中间没有窄脉冲表示“0”。当有连续的“0”时，从第二个“0”开始在数据的起始部分增加一个窄脉冲。该标准还规定起始位的开始处也有一个窄脉冲，而结束位用“0”表示。如果有两个连续的位开始和中间部分都没有窄脉冲，则表示无信息。

差错控制编码

奇偶校验法

在前面增加1位校验元，信息元的个数就是n-1位。对于奇校验码而言，使得“1”的个数为奇数；对于偶校验码而言，使得“1”的个数为偶数。如果接收方发现规则相同，那么就认为“没问题”。

以偶校验为例，事实上，如果序列“0101001”增加了校验码“1”成为序列“10101001”，最终传输过去的序列为“00001001”，“1”的个数仍然为偶数个，这样也是检验不出来的。

循环冗余校验

1. 首先准备待传送的有效数据，切割成等长的分组。

   ​ 每个组都加上冗余码构成帧再发送：双方商定r+1位的生成多项式，d位数据和r位0组成一个序列，跟生成多项式进行模2除法（异或），得到的余数就是r位FCS帧校验序列，最终发送的帧就是d位数据和r位FCS组成的序列。

   ​ 最后进行接收方检验：（d+r）位的数据和生成多项式进行模2除法，如果余数为0，则认为正确接收；如果余数不为0，则丢弃。

图5 CRC循环冗余码

要发送的数据是1101011011，采用CRC校验，生成多项式是10011，那么最终发送的数据应该是什么？

最终发送的数据是：要发送的数据+帧检验序列FCS

计算冗余码：

1. 加0：生成多项式是10011，表示成多项式为：$x^4+x^1+1$，阶为4，则加4个0。
2. 模2除法：数据加0后是“11010110110000”除以生成多项式“10011”（异或），商为“1100001”，余数为“1110”。
3. 得到的余数“1110”即为冗余码，也成为FCS检验序列，故最终发送的数据为“11010110111110”

图6 题目计算过程

接收端检错过程：

1. 把收到的每一个帧都除以同样的除数，然后检查得到的余数R。
2. 余数为0就判断没有错，不为0就判定有错，丢弃。

在数据链路层仅仅使用循环冗余检验CRC差错检测技术，只能做到对的无差错接收，即“凡是接收端数据链路层接受的帧，我们都能以非常接近于1的概率认为这些帧在传输过程中没有产生差错”。接收端丢弃的帧虽然曾收到了，但是最终还是因为有差错被丢。“凡是接收端数据链路层接收的帧均无差错”。

海明码

纠错编码相对于检错编码可以实现发现错误、找到位置和纠正错误。

两个合法编码(码字)的对应比特取值不同的比特数称为这两个码字的**海明距离(**码距)，一个有效编码集中,任意两个合法编码(码字)的海明距离的最小值称为该编码集的海明距离(码距)。

比如，“000”和“001”的海明编码为1；“000”、“001”、“010”、“011”的海明距离也是1，任意两个编码码距的最小值。

如果需要检测出$d$位错误的话，码距需要$d+1$位，如果需要纠正d位错误的话，码距需要$2d+1$位。

图7 海明码工作流程

1. 确定校验码位数$r$

   ​ 数据/信息有$m$位，冗余码/校验码有$r$位，那么校验码一共有$2^r$种取值，根据海明不等式$2^r\ge m+r+1$。

   ​ 例如，要发送的数据是“D=1100”，数据的位数$m=4$，满足不等式的最小$r$为3，也就是“D=1100”的海明码应该有$4+3=7$位，其中原数据4位，校验码3位。

2. 确定校验码和数据的位置

   ​ 校验码放在序号位$2^n$的位置，数据按序列填上。用二进制表示序号，校验码对应位置上二进制可转换成“x1x”、“1xx”的形式，即为校验码可校验的位，如图8所示。

   

   图8 求出校验码的过程

   ​ 以4号校验码为例，偶校验的意思是，让4、5、6、7位组成的“$x_{4}011$”出现偶数个1，因此$x_4$为0。因此，可以写出完整的海明码。

3. 检错并纠错

   ​ 假设接收方收到的数据为“1110001”，4号校验码负责4、5、6、7的校验：0、1、1、1，发现不对；2号校验码负责2、3、6、7的校验：0、0、1、1，发现正确；1号校验码负责1、3、5、7的校验：1、0、1、1，发现错误。因此，接收的数据是存在错误的。

   ​ 纠错方法一：找到不满足奇/偶校验的分组取交集，并与符合校验的分组取差集。发现5和7是交集，接着取差集的结果为5，故出错的位置是第5位。

   ​ 纠错方法二：把$x_4$、$x_2$、$x_1$写成矩阵的形式，然后横着进行异或，这里得到的结果是1、0、1，101对应的十进制数是5，因此是第5位发生了错误，过程如图9所示。

   

   图9 纠错方法二过程示意图

系统调制方法

1. 振幅键控（ASK）：ASK通过改变载波的幅度来表示不同的二进制位。假设“1”用高幅度表示，“0”用低幅度表示。用正弦波表示载波信号。
2. 移频键控（FSK）：FSK通过改变载波的频率来表示不同的二进制位。假设“1”用高频率表示，“0”用低频率表示。用正弦波表示载波信号。
3. 移相键控（PSK）：PSK通过改变载波的相位来表示不同的二进制位。假设“1”用0度相位表示，“0”用180度相位表示。用正弦波表示载波信号。

图10 数据“11010”的三种调制方法

典型电子标签S50卡

工作流程

图11 S50卡工作流程图

​ S50卡对存储器的操作：

1. READ 读块：读存储器的一个分组（数值块）。
2. WRITE 写块：写存储器的一个分组（数值块）。
3. INCREMENT 加值：增加存储器中一个分组的内容（数值块内的值），并将结果存入数据寄存器。这通常用于计数或增加某个值。
4. DECREMENT 减值：减少存储器中一个分组的内容（数值块内的值），并将结果存入数据寄存器。这用于减去某个值，类似于加值操作的逆操作。
5. TRANSFER 转存：将数据寄存器中的内容写入EEPROM的一个分组。此操作用于将暂存的数据存入EEPROM中，确保数据的持久化。
6. RESTORE 恢复：将存储器中一个分组的内容恢复到数据寄存器。这通常用于从EEPROM恢复某个分组的数据，以便进行进一步的处理。

​ 工作流程的步骤：

1. 卡呼叫：开始流程，通过防冲突循环获取卡号。
2. 选卡（激活）：选择并激活卡片。
3. 三轮认证（对指定扇区）：对指定扇区进行三轮认证以确保安全性。
4. 切换扇区/不切换扇区：根据需要选择是否切换扇区。
   • 不切换扇区：执行读块、写块、加值、减值、恢复操作，最后进行转存。
   • 切换扇区：返回进行三轮认证。

三次认证过程

1. 阅读器发送查询口令的命令给应答器，应答器作为应答响应传送所产生的一个随机数RB给阅读器。
2. 阅读器产生一个随机数RA，使用共享的密钥K和共同的加密算法EK，算出加密数据块TOKEN AB，并将TOKEN AB传送给应答器，TOKEN AB＝EK(RA,RB) 。
3. 应答器接受到TOKEN AB后，进行解密，将取得的随机数与原先发送的随机数RB进行比较，若一致，则阅读器获得了应答器的确认。
4. 应答器发送另一个加密数据块TOKEN BA给阅读器，TOKEN BA＝EK(RB1,RA)。
5. 阅读器接收到TOKEN BA并对其解密，若收到的随机数与原先发送的随机数RA相同，则完成了阅读器对应答器的认证。

标签存储结构

图12 标签存储器逻辑映射

1. 每个扇区由4块（块0、块1、块2、块3）组成（也有的将16个区的64个块按绝对地址编号为0～63）。
2. 第0扇区的块0（即绝对地址0块）都是一个特殊的块，该块存储了制造商代码，已经固化，不可更改。
3. 每个扇区的块0、块1、块2为数据块，用于存储数据，可以进行读写操作。
4. 每个区的块3为控制块，包括了密钥A、访问控制条件、密钥B。

图13 控制块的具体结构

1. 密钥A有6字节，访问控制条件有4字节，密钥B有6字节。
2. 由于每个区都有各自的密钥和访问条件，各区之间互不干扰，因此Mifare S50可作为多功能卡使用。
3. 每个区的密钥和访问控制条 件相互独立，可以根据实际 需要设定各自的密钥及访问控制条件。

已知存储控制字节为37 85 ac 69请写出每个块的存取控制位，并表述块0和块1的访问控制条件。

控制字节对应的二进制码为：

	7	6	5	4	3	2	1	0
Byte6	0	0	1	1	0	1	1	1
Byte7	1	0	0	0	0	1	0	1
Byte8	1	0	1	0	1	1	0	0
Byte9	0	1	1	0	1	0	0	1

上表中就是把十六进制的控制字节转换成二进制即可。

Byte 6、Byte 7 和 Byte 8用于指定每个块（Block）的访问条件，而Byte 9是校验字节，确保前三个字节的正确性。具体的访问控制规则由下表定义：

图14 访问控制规则

1. 确定各块的控制位。访问控制条件的定义可以用顺口溜记忆为687，反正反，0123。
2. 写出每个块对应的控制位：块0是000，块1是001，块2是010，块3是111。
3. 查找控制条件：块0验证密钥A或B正确后可读可写可加值可减值可转存可恢复。块1验证密钥A或B正确可读不可写不可加值，验证密钥A或B正确可减值可转存可恢复。

RFID基本概念

简述RFID工作流程（以无源标签为例）

1. 读写器通过天线发送一定频率的射频信号。
2. 信号到读写器天线的工作区时，电子标签天线产生足够的感应电流，电子标签获得能量被激活。
3. 电子标签将信息通过内置天线发送出去。
4. 读写器天线接收到从电子标签发送来的无线射频信号。
5. 读写器天线将无线射频信号传送到读写器。
6. 读写器对无线射频信号进行解调和解码，送到系统高层进行相关处理。
7. 系统高层根据逻辑运算判断该电子标签的合法性。
8. 系统高层针对不同的设定做出相应的处理，发出指令信号，控制执行机构的动作。

RFID常用的工作频率

图15 RFID常用的工作频率

1. 低频：

   ​ 低频RFID系统的工作频率为30～300 kHz，采用电磁感应方式来进行通信。低频信号穿透性好，抗金属和液体干扰能力强，但难以屏蔽外界的低频干扰信号。

   ​ 一般来说，低频RFID标签读取距离短于10 cm，读取距离跟标签大小成正比。

   ​ 低频RFID标签一般在出厂时就初始化好了不可更改的编码，不过一些低频标签也加入了写入和防碰撞功能。

   ​ 低频标签主要应用在动物追踪与识别、门禁管理、汽车流通管理、POS系统和其他封闭式追踪系统中。

   ​ 常用的低频标签一般具有以下性能：

   1. 通常都是近距离标签，距离为10 cm以下。

   2. 主要应用于短距离、数据量低的射频识别系统中。

   3. 价格很低，成本低廉。

   4. 一般为只读性，安全性不高，很容易复制完全相同的ID号，所以此类卡片一般用在安全性和成本要求不高的场合。

2. 高频：

   ​ **高频系统的工作频率为3～30 MHz，**射频识别常见的高频工作频率有6.75 MHz、13.56 MHz和27.125 MHz。

   ​ 高频系统也采用电磁感应方式来进行通信，具有良好的抗金属与液体干扰的性能，读取距离大多在1 m以内。

   ​ 高频RFID标签传输速度较高，但抗噪声干扰性较差，一般具备读写与防冲突功能。现在高频RFID标签是RFID领域中应用最广泛的，如证、卡、票领域（二代身份证、公共交通卡、门票等），其他的应用还包括供应链的个别物品追踪、门禁管理、图书馆、医药产业、智能货架等。

3. 超高频：

   ​ 被动式超高频RFID标签工作频率为860～960 MHz，主动式超高频RFID标签则工作在433 MHz。

   ​ 在超高频频段，各个国家都有自己规定的频率，我国一般以915 MHz为主。

   ​ 超高频的优点就是距离远，最远可以达到15 m。超高频RFID标签传输距离远，具备防碰撞性能，并且具有锁定与消除标签的功能。

   ​ 被动式超高频RFID标签有分别支持近场通信与远场通信两种。远场被动式UHF采用反向散射耦合方式进行通信，可以用蚀刻、印刷等工艺制作成不同的样式，其最大的优点是读写距离远，一般是3～5 m，最远可达10 m，但是由于抗金属与液体性差，所以较少用于单一物品的识别，主要应用于以箱或者托盘为单位的追踪管理、行李追踪、资产管理和防盗等场合。

   ​ 近场被动式UHF通信使用的天线与HF相类似，但线圈数量只需要一圈，而且采用的是电磁感应方式而非反向散射耦合方式，也具备HF的抗金属液体干扰的优点，其缺点是读取距离短，约为5 cm，近场UHF通信主要应用于单一物品识别追踪，以取代目前HF的应用。

4. 微波：

   ​ 微波RFID标签的主要工作频率为2.45 GHz，有些则为5.8 GHz，因为工作频率高，所以在各种频段的RFID标签中传输速度最大，但是抗金属液体能力最差。

   ​ 被动式微波RFID标签主要使用反向散射耦合方式进行通信，传输距离较远，如果要加大传输距离还可以改为主动式。由于传输速度快，微波RFID标签非常适合用于高速公路等收费系统。*

自动识别技术

自动识别通常是指采用机器进行识别的技术，其目的是提供个人、动物、货物、商品和图文等信息。

自动识别技术包括条形码、生物特征识别（具体的人脸识别、指纹识别等都给分）、射频识别。

二维码会不会取代RFID

二维码与一维条码一样，几乎是零成本的信息存储技术。

1. 二维码主要是通过将信息通过一定的算法转化成计算机容易识别的特殊图形，将这样的特殊图形在打印到物品上，因为打印或印刷一个特殊图形的成本仅仅在于标签本身的价值，所以成本接近零。
2. RFID技术在推广和使用上的瓶颈源于它的成本较高，对于一般的小商品而言，电子标签的价格要高于商品本身价格很多，因此一般的厂商或销售商都难以承受。目前，虽然采用了多种办法来降低标签的成本，但真正达到要让普通大众接受的价格，还需要很长的时间。

其次，从应用上来看，二维码在商品上使用，必须要通过扫码设备才能读取数据，如果要处理的商品较多，每个商品的二维码都要通过扫码设备才能读取信息。假如在大型仓库进行盘点，工人不得不拿着扫码设备爬上爬下的去找每个商品的二维码，费时费力。但是，在这方面，RFID就表现出很突出的优势，如果每个商品都装有RFID标签的话，那么工人只需在办公室里读取读写器上的数据就可以了，省时省力。

通过以上的比较，可以看出每种自动识别的技术都有一定应用优势和局限性，多种技术共存可以充分发挥它们的优势而且可以互相拟补它们的缺点。根据不同的使用环境和技术条件，结合被使用对象的特点，我们可以采用不同的识别技术。比如：目前RFID技术在车联网中有较出色的应用，而在移动电子商务中，二维码也已经取得不错的成绩。善用这些识别技术，能为我们的生产效率和生活水平带来很大的改变。尽早实现生活的“智能化”。
的二维码都要通过扫码设备才能读取信息。假如在大型仓库进行盘点，工人不得不拿着扫码设备爬上爬下的去找每个商品的二维码，费时费力。但是，在这方面，RFID就表现出很突出的优势，如果每个商品都装有RFID标签的话，那么工人只需在办公室里读取读写器上的数据就可以了，省时省力。

通过以上的比较，可以看出每种自动识别的技术都有一定应用优势和局限性，多种技术共存可以充分发挥它们的优势而且可以互相拟补它们的缺点。根据不同的使用环境和技术条件，结合被使用对象的特点，我们可以采用不同的识别技术。比如：目前RFID技术在车联网中有较出色的应用，而在移动电子商务中，二维码也已经取得不错的成绩。善用这些识别技术，能为我们的生产效率和生活水平带来很大的改变。尽早实现生活的“智能化”。