《RFID包装系统中防冲突算法研究.docx》由会员分享，可在线阅读，更多相关《RFID包装系统中防冲突算法研究.docx（11页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、RFID包装系统中防冲突算法研究摘要：目的解决现阶段包装箱管理过程中RFID标签冲突的问题。方法在分析已有的解决标签冲突算法的基础上，采用多线程技术、后退式二进制防冲突算法和优化的数据结构等方法，设计并实现一种新的防冲突算法。RFID读写器发送一个三元组命令，RFID标签应答冲突位的信息，减少数据传输量;采用堆栈存储RFID读写器发送的命令，减少识别冲突的次数;利用多线程处理思想，对标签进行分类处理，缩短冲突处理的时间。结果经过仿真分析，这种并发执行的后退式二进制RFID防冲突算法效率可提高约51%。结论该算法解决了RFID标签冲突，提高了多标签情况下的读写效率，很好地解决了包装箱管理系统中R
2、FID标签的功能和性能的问题。在现代物流运输中，射频识别技术(RFID)被广泛应用于包装箱管理。RFID技术的使用可以对包装箱的装箱、运输、入库和储存等各个物流环节进行跟踪，实现包装箱的实时监控和管理。RFID可以无接触采集数据，是一种自动识别的通信技术。这种技术可以通过电磁波双向传输数据实现数据的通信。RFID标签、RFID读写器和中央信息处理器组成了RFID系统，其中RFID标签可以粘贴在包装箱上，可存储包装箱的具体信息，RFID标签具有唯一的编码，该编码可以作为包装箱的唯一标识;RFID读写器可以对包装箱上的RFID标签进行更改、写入和读取，将读取的RFID标签存储信息传输到中央处理器;
3、中央处理器可以对读取的RFID标签信息进行分析处理，实现对包装箱的管理。RFID包装箱技术存在多个RFID标签信息冲突的问题。RFID读写器向有效范围的RFID标签发出通信请求信号，所有包装箱上的RFID标签会同时返回标签信息至RFID读写器。RFID标签的通信使用共享的通信信道，因此多个RFID标签信息在同一信道中产生冲突。如何在避免冲突的条件下快速、正确地读出RFID标签信息，并高效地利用通信信道，是RFID应用在包装系统中主要需要研究和解决的问题之一。对于RFID系统中的信息冲突问题，一般采用时分多址(TDMA)的技术来解决。基于树的算法和基于ALOHA的算法是时分多址的两类主要算法7&
4、mdash;10。基于ALOHA算法的主要思想是发现冲突后，重新产生识别标签。当标签数量增加，冲突则呈线性增长，系统性能急剧下降。基于树的算法是一类确定性算法，例如查询树算法(QTA)，二进制搜索算法(BAS)等11—14。QTA算法需传输并检验标签前缀，信息处理速度较慢。BAS算法的主要思想是将读入的信息生成2个不相交的子集，循环处理，直到子集中只有唯一可识别的标签。当标签数量增大，也会产生大量标签的冲突，使系统效率降低。后退式二进制算法以BAS算法为基础，采用栈和后退原则减少冗余，提高系统的工作效率。以上2种算法虽然可以解决多个包装箱RFID标签的传输冲突问题，但随着同时读取包
5、装箱数量的增多，传输和处理的数据量也随之大量增加。为了解决冲突和效率的问题，这里将提出并发执行的后退式二进制RFID防冲突算法。算法基础1.1曼彻斯特编码多个同时读取的RFID标签信息在共享信道中产生冲突，首先应找到冲突产生的位置，曼彻斯特编码则是确定冲突位置的基础编码方式。曼彻斯特编码采用在一位传输周期中的电平跳变规则，正跳变为0，负跳变为1。例如有2个RFID标签(8bit)，信息分别为10010111(标签TagB)和10110011(标签TagA)。这2个标签在共享信道中同时被RFID读写器读出，则读出的信息为10X10X11(其中X为无电平)。由于TagA和TagB的第2位和第5位相
6、反，上升和下降电平相互抵消，可以说明第2位和第5位产生冲突，见图1。1.2后退式二进制RFID防冲突算法后退式二进制RFID防冲突算法识别RFID标签的步骤如下所述。1)RFID读写器广播发送同步信号及请求命令，将此命令入栈，便于下次命令的确定。各标签响应请求，并判断自己的ID是否小于等于S，S为RFID读写器的参数，表示该读写器能够读取的RFID标签的最大长度。如果小于等于S，则返回自身ID。2)读写器根据读回的信息，判断是否有标签产生冲突，如果没有冲突，转到步骤3);如果有冲突，将读回的序列的最高冲突位置;0”，其余冲突位置;1”，不冲突位保持读回序列的原状态。将修
7、改后的序列赋值给S，返回步骤1)。3)如没有冲突，证明已识别出一个RFID标签的ID，可对此标签执行操作。从栈中取出请求命令，确定下次命令的参数，返回步骤1)。1.3并发执行并发执行主要采用多线程技术实现，多线程技术可以同步运行多个独立的程序片段，这种并行可以提高系统的效率。RFID中央处理器可以采用多核处理器，采用多线程的编程方法，对BAS算法中生成的2个不相交的自己进行同步处理，既解决了冲突问题，又解决了效率问题。1.4定义命令为方便对算法进行描述，在不改变原RFID系统命令的前提下，定义请求命令Request(D，m，T)和应答命令Response(s)。其中Request命令中的D参数
8、为冲突最高位的编号(设RFID为8位ID，D为3位二进制数，如110表示冲突的最高位为D6位)，m为冲突位的参数(0/1)，T为线程编号(4线程，2位二进制表示00，01，10，11这4个线程的编号)。算法流程假设RFID标签编码为16位二进制数，现有20个待识别的标签，见表1。改进算法采用4个线程处理该算法，树中结点表示根据最高冲突位发出的不同请求命令。算法的流程如下所述。1)RFID读写器向可读标签发送同步信号，标签返回自身ID。RFID读回1?1?0?的二进制序列，判断D6，D5，D3，D1，D0发生冲突。RFID读写器将产生冲突的位置发送给RFID标签。2)根据最高冲突位和次高冲突位进
9、行分类，RFID标签根据自身ID的序列和产生冲突的位置，判断应进入哪个分类，由哪个线程进行处理。例如，可用最高冲突位D6与次高冲突位D5对标签进行分类，共分为4类，每类对应进入相应的线程中进行下一步处理，详细分类情况见表2。下面以线程1的流程说明算法的整个流程。3)RFID读写器发送Request(011，0，00)。其中，参数;011”表示标签的最高冲突位为D3位;参数;0”表示将最高冲突位置;0”参数;00”表示上述标签所属线程的标号为;00”，即线程1。满足上述条件的RFID标签(Tag1，Tag11)返回信息，发送命令Resp
10、onse(D1D0)，D1D0为其余冲突位的标签信息，即Tag1发送Response(01)，Tag11发送Response(10)。RFID读写器就收到Tag1与Tag11返回的叠加后的信息;?”，说明仍在D1与D0位存在冲突。将Request(011，0，00)命令入栈。4)RFID读写器发送Request(001，0，00)，此时满足其条件的标签只有Tag1，该标签发送命令Response(1)。RFID读写器收到;1”的信息，表示此时无冲突，表示识别了一个标签(Tag1)。Request(001，0，00)命令入栈。5)执行出栈，出栈的命令为Request(00
11、1，0，00)，将第2个参数;0”改为;1”。RFID读写器发送Request(001，1，00)，此时满足其条件的标签只有Tag11，该标签发送命令Response(0)。RFID读写器收到;0”的信息，表示此时无冲突，并识别了一个标签(Tag11)。6)执行出栈，出栈的命令为Request(011，0，00)，将第2个参数;0”改为;1”。RFID读写器发送Request(011，1，00)，此时满足其条件的标签有Tag4，Tag6和Tag8，标签分别发送命令Response(01)，Response(00)和Response(1
12、0)。RFID读写器收到;?”的信息，表示D1和D0存在冲突。7)RFID读写器发送Request(010，0，00)，此时满足其条件的标签有Tag4，Tag6，标签分别发送命令Response(1)和Response(0)。RFID读写器收到;?”，表示D0位存在冲突。此时只有一位冲突，表示D0位可有2种取值，识别了2个标签(Tag4，Tag6)。Request(010，0，00)命令入栈。8)执行出栈，出栈的命令为Request(010，0，00)，将第2个参数;0”改为;1”。RFID读写器发送Request(010，1，00)，此时满足其
13、条件的标签有Tag8，标签发送命令Response(0)。RFID读写器收到;0”的信息，表示此时无冲突，识别了一个标签(Tag8)。9)栈为空，该线程结束。线程2、线程3、线程4也采取同样的处理方式。算法相关问题说明1)Request命令入命令栈。由于算法中对树的操作是从左至右，所以按照命令中的m参数值确定是否命令入栈，m为;0”入栈，为;1”不入栈。2)出命令栈。由算法中的后退原则，识别出标签后，应后退查找树的结点。此时可执行出栈操作，并将出栈命令中的m由;0”置;1”，再执行下次搜索。3)多线程处理。如果RFID读写器是多频的，
14、并且CPU是多核处理器，则该多线程为;并行处理”如RFID是单频的，则需增加一个命令队列，暂时存储同时发出的Request命令，此时为;多线程处理”，可利用RFID读写器在处理信息的同时，读写RFID标签内容。这2种方式都可提高系统的效率。性能分析4.1BAS、后退式BAS和并发式BAS算法比较评估RFID系统防冲突算法的好坏，要看算法搜索完所有标签需要的查询次数和识别的时间。设RFID标签数量为N，RFID标签的编码长度为L，则BAS算法中RFID标签的编码长度为L;后退式BAS算法中，RFID标签的编码长度为log2L+1;在该算法Request命令中，D的长度与编
15、码长度有关，为log2L，m为1位，T与线程的数目(NT)有关，为log2NT。在该算法中发送的二进制编码长度为log2L+1+log2NT。BAS算法中，需循环搜索RFID标签，因此识别数量为N的标签查询次数为N(N+1)/2;后退式BAS算法识别数量为N的标签需要的查询次数为2N−1;文中算法采用并发执行后退式BAS，每个线程平均查询次数为(2N−1)/NT。BAS、后退式BAS、并发处理BAS算法的传输二进制数据长度分别为N(N+1)/2L，(2N−1)×(log2L+1)，(2N−1)/NT×(log2L+1+NT
16、)。以表1的20个标签为样本，比较BAS、后退式BAS和并发执行BAS算法的性能，比较指标见表3。随着标签数量、编码位数以及并发数的增加，文中算法的优势将越来越明显。对后退式BAS和并发执行BAS算法进行Matlab仿真，对RFID标签的编码为8位、64位，线程数为4和8的2种算法的吞吐量进行了比较，见图2。可以看出，新算法发送命令次数和数据量都大幅度减少，分析其原因应有以下两点：后退方式减少了命令的发送;命令的参数不是RFID标签的全部ID，而是冲突的位置及数值。当标签的ID位数越多，会越明显。各算法的执行时间比较见表4。其中RFID读写器发送1bit数据时间为t1，RFID标签应答1bit
17、数据时间为t2，RFID进行冲突处理1bit数据时间为t3。由表4可以看出，改进算法在速度上也得到了提高，分析其原因应有以下3点：并发执行处理，使冲突处理时间减少;命令传输的数据减少，识别数据的时间减少;处理冲突可与命令传输多线程处理，提高了运行的速度。4.2并发执行BAS算法与其他算法的效率比较算法的系统效率是比较算法好坏的标准之一，因此对ALOHA算法、QTA算法和BAS算法进行系统效率的比较。ALOHA算法的思想是发现冲突后，重新产生识别标签，当标签数量增加，冲突则呈线性增长，系统性能急剧下降。QTA算法需传输并检验标签前缀，信息处理速度较慢。BAS算法的思想是将读入的信息生成2个不相交
18、的子集，循环处理，直到子集中只有唯一可识别的标签。算法的系统效率定义如下：系统效率=(发送成功的标签信号/发送总标签信号)×100%。这几种算法的效率比较曲线见图3。可以看出，ALOHA算法的效率最低，随着阅读器数目的增多，冲突也随之增加，当阅读器数量达到64时，ALOHA算法的系统效率几乎为0;QTA算法虽然很好地避免了节点的冲突，但由于需要检查标签的前缀，当阅读器数目达到64时，系统效率约为40%;BAS算法将读入的信息分成2个不相交的子集，但单线程会造成系统空闲，当阅读器数目达到64时，系统效率约为67%;文中算法是在BAS算法的基础上，引入多线程后退式技术，使系统效率一直保持在90%左右。结语提出了并发执行的后退式防冲突算法，减少了命令传输数据的数量，缩短了读写器的识别时间，提高了包装系统的处理速度。并发执行的后退式防冲突算法融合了BAS算法思想，将读入的信息生成2个不相交的子集，循环处理，直到子集中只有唯一可识别的标签;进一步采用了多线程并发技术，对BAS算法中系统空闲时间进行有效的利用，提高了系统的工作效率。性能分析表明，该算法优于BAS算法和后退式BAS算法，更适用于包装标签ID长、标签数量大的情况。1