基于编码分组的无线射频识别多标签防碰撞方法

朱纪铭，闫 述

（江苏大学 计算机科学与通信工程学院，江苏 镇江 212013）

目前，无线射频识别技术的应用仍然存在多标签碰撞问题［1］，解决的方法主要有基于时隙Aloha的随机型算法和基于二进制树的确定型算法.基于Aloha的防碰撞算法［2－3］又包括纯Aloha、时隙Aloha［4－8］等.Aloha算法简单易实现，但存在误判决问题，识别时间较长，信道利用率最大仅为36%，并存在“标签饥渴”等问题；二进制算法［9－10］的优点在于其识别率可达到100%，理论上只要时间足够多，二进制算法就能识别出全部的标签.二进制算法对碰撞的具体数据（碰撞的位数和位置）进行了一定的统计和处理，以此为依据来确定阅读器发出的下一次命令参数，因此在此基础上衍生出各种改进的二进制算法，但这些算法的不足在于其标签中须添加计数器、计时器、寄存器等，从而增加了标签的复杂度和功耗.为了解决这个问题，本研究拟从分析标签编码规则和对读写器要获取的标签种类两方面入手，对标签进行智能分组，从而减少标签碰撞，提高系统效率.

1 标签编码规则

从对标签编码系统构成的分析中得出一般性规律，以此规律作为标签分组的依据，现以EPC编码［11］为例.EPC的目标是为每一物理实体提供唯一标识，它是由一个头字段和另外3段数据（依次为EPC管理者、对象分类、序号）组成的一组数字，具体结构见表1.

1）头字段标识EPC的版本号中设计者采用版本号标识了EPC的结构，并给出EPC中编码的总位数和其他3部分中每个部分的位数.表1中3个64位的版本各有2位的版本号，96位版本和3个256位的版本则各有8位的版本号.3个64位的EPC的版本号只有2位，即01，10，11.为了与64位的EPC版本区别，所有长度大于64位的EPC版本号的最高两位必须为00，这样就定义了所有96位的EPC版本号开始的位序列是001.同样，所有长度大于96位的EPC版本号的前2位是000.

2）EPC管理者描述与此EPC相关的生产厂商的信息，例如“联想集团”.以EPC－64type 3为例，管理者编号长度为26，即可表达67 108 864个管理者.

表1 EPC标签编码规则Tab.1 Rule of electronic product code

3）对象分类记录产品精确类型的信息，例如“广东惠阳生产的ThinkPad SL410”（联想集团生产的一种笔记本电脑）.

4）序号是货品的唯一标识，它会准确地指明究竟是哪一台ThinkPad SL410.

由此可见，以EPC－64type 1编码为例，在64bit中包含着版本号（2bit）、管理者（21bit）、对象分类（17bit）、唯一序号（24bit）等信息.

2 编码分组理论

在RFID系统识别的过程中，对于读卡器而言，须识别的标签的编码无非是两种情况：未知或者已知部分编码（标签编码采用EPC－64编码规则）.

1）对于标签编码信息未知状态，分组识别流程如下，如某组中发生标签碰撞，则采用后退机制二叉树算法处理.

步骤1：读写器发出查询指令，要求标签返回前两位，根据返回信息以版本号分组；

步骤2：读写器发出查询指令，要求type为n（1～3）的标签返回X1—X2位数据（根据不同的type，标签分别返回相应位置的EPC管理者数据），对发生碰撞的标签进行处理后得到管理者名单，根据管理者名单进行分组；

步骤3：读写器发出查询指令，要求type为n，管理者为y的标签返回X3—X4位数据（根据不同的type，标签分别返回相应位置的对象分类数据），对发生碰撞的标签进行处理后得到该管理者的对象分类名单，根据对象分类名单进行分组；

步骤4：读写器发出查询指令，要求type为n，管理者为y的标签，对象分类为k的标签返回X5－X6位数据（根据不同的type，标签分别返回相应位置的序列号数据），对发生碰撞的标签进行处理后得到该分类的所有标签的数据；

步骤5：返回管理者层，对管理者为y的未处理的对象分类数据依据步骤4进行处理，从而获得管理者为y的所有标签的数据；

步骤6：返回type层，对未处理的管理者数据依据步骤2，3，4，5进行处理，得到采用该版本所有标签的数据；

步骤7：重复以上步骤，处理剩余标签.

2）很多情况下，标签编码信息是部分可知的，包括以下几种可能：①全部EPC管理者信息集合；②全部对象分类集合（对每个EPC管理者而言，其对象分类是有限的）；③特定对象分类以及子分类的编码（如不同公司生产的MP3电子产品，电子产品属于一个特定的对象分类，而MP3又属于电子产品类中的一个特定子分类，在同一种编码系统中，其编码结构应该是相同的）；④ 特定场合中的EPC管理者信息以及对象分类信息；⑤ 读写器要查询的标签种类信息.

通过以上分析，在读写器查询标签时就可以让包含着特定信息（编码）的标签响应查询指令，而不符合条件的标签保持沉默状态，从而大大减少查询的次数，也减少标签的碰撞.例如要统计某大型超市仓库中诺基亚品牌的N97还有多少台，读写器发出查询指令，命令编码中符合EPC管理者（诺基亚，编码已知）、对象分类（电子产品类，手机，型号N97）的标签传回序列号（24bit）.

3 模拟仿真分析

现有10个码长为16bit的标签，分别为①1000 0001 0100 0001，②1000 0001 0100 1000，③1000 0001 1001 0010，④1001 0001 0100 1000，⑤1001 0001 1001 0001，⑥1001 0001 1001 0011，⑦0100 0101 0010 0100，⑧0100 0101 0010 1011，⑨0100 0101 0011 1000，⑩0011 1000 1011 0101.编码符合以下规则（模仿EPC－64编码规则，精简码位）：

1）1～4位编码为管理者代码，其中联想集团代码为1000，海尔公司代码为1001，东方木业代码为0100，耐克公司代码为0011；

2）5～12位编码为对象分类代码，5～8位为对象代码，9～12位为分类代码，其中对象代码中电子类代码为0001，组合家具类代码为0101，鞋类代码为1000；分类代码中手机类代码为0100，笔记本类代码为1001，休闲类代码为1011，檀木类家具代码为0010，楠木类家具代码为0011；

3）13～16位编码为序列号代码，各公司自定义（相对于本公司，该序列号唯一）.根据编码规则可知，10个标签分别表示联想公司生产的手机2部、笔记本1台，海尔公司生产的手机1部、笔记本2台，东方实业生产的檀木组合家具2套、楠木组合家具1套，耐克公司生产的休闲鞋1双.

标签识别流程（发生标签碰撞均采用后退机制二叉树算法处理）如下：

3.1 无初始条件（识别所有标签）

第1步：读写器发出“Active”命令，所有标签激活；

第2步：读写器发出“Request”命令，要求每个标签传回1～4位数据（管理者代码），处理碰撞后得到管理者名单（1000，1001，0100，0011）；

第3步：读写器发出“Request”命令，要求1～4位编码为1000的标签传回5～12位数据（对象分类代码），标签①，②，③响应，处理碰撞后得到对象分类名单（0001 0100，0001 1001）；

第4步：读写器发出“Request”命令，要求5～12位编码为0001 0100的标签传回13～16位数据（序列号），标签①，②响应，处理碰撞后识别标签①，②；

第5步：读写器发出“Request”命令，要求5～12位编码为0001 1001的标签传回13～16位数据（序列号），标签③响应，无碰撞，直接识别；

第6步：重复步骤3～5，识别剩余管理组的所有标签.

3.2 有初始条件（有选择地识别标签）

情况一：查询联想集团的所有产品.

分析：联想集团的代码为1000，那么只须命令1～4位编码为1000的标签响应即可.

第1步：读写器发出“Active”命令，所有标签激活；

第2步：读写器发出“Request”命令，要求1～4位编码为1000的标签传回第5～12位数据（对象分类代码），标签①，②，③响应，处理碰撞后得到对象分类名单（0001 0100，0001 1001）；

第3步：读写器发出“Request”命令，要求5～12位编码为0001 0100的标签传回13～16位数据（序列号），标签①，②响应，处理碰撞后识别标签①，②；

第4步：读写器发出“Request”命令，要求5～12位编码为0001 1001的标签传回13～16位数据（序列号），标签③响应，无碰撞，直接识别.

情况二：查询手机类的所有产品.

分析：手机类的代码为0100，那么只须命令9～12位编码为0100的标签响应即可.

第1步：读写器发出“Active”命令，所有标签激活；

第2步：读写器发出“Request”命令，要求9～12位编码为0100的标签返回1～4位数据，标签①，②，④ 响应，处理碰撞后得到管理者名单（1000，1001）；

第3步：读写器发出“Request”命令，要求1～4位编码为1000的标签返回9～12位数据，标签①，②响应，处理碰撞后识别标签①，②；

第4步：读写器发出“Request”命令，要求1～4位编码为1001的标签返回9～12位数据，标签④响应，直接识别.

分析情况一、二的处理流程及处理结果，可以看出在有初始条件的情况下，符合初始条件的标签才响应读写器的查询命令.由此可知，基于编码分组的RFID防碰撞算法具有以下几个优点：①分组的依据是编码的标准，编码越精细，分组越精细；②根据编码的分组，每次标签传送数据时仅须传输数据的一部分，也就意味着每次处理碰撞时仅须处理传输的这部分数据，这不仅减少了数据的传输量，而且减少了碰撞的位数和次数，从而提高了处理的速度；③在有初始条件的情况下，查询前就已淘汰了不符合初始条件的标签，大大减少了通信量，降低了碰撞的可能，而且初始条件越苛刻，符合条件的标签就越少，识别的速度和效率就越高.

［1］FINKENZELLER K.Fundamentals and applications in contactless smart cards and identification［M］.England：RFID Handbook，2003：1－38.

［2］LEE S R，JOO S D，LEE Cw.An enhanced dynamic framed slotted ALOHA algorithm for RFID tag identification［C］／／Proceedings of the 2nd Annual International Conference on Mobile and Ubiquitous Systems：Networking and Services.Washington，DC，USA：IEEE，2005：166－172.

［3］WIESELTHIER J E，EPHREMIDES A，MICHAELS L A.An exact analysis and performance evaluation of framed ALOHA with capture［J］.IEEE Trans Commun，1989，37（2）：125－137.

［4］CHA J R，KIM J H.Novel anti－collision algorithms for fast object identification in RFID system ［C］／／Proceedings of the 11th International Conference on Parallel and Distributed Systems.Fukuoka：IEEE，2005：63－67.

［5］VOGT H.Multiple object identification with passive RFID tags［C］／／Proceedings of the IEEE International Conference on Systems，Man and Cybernetics.Tunisia：IEEE，2002，3：6－13.

［6］PANICHPAPIBOON S.Adaptive frame length selection scheme for RFID object identification［C］／／Proceedings of the IEEE 18th International Symposium on Personal，Indoor and Mobile Radio Communications.Athens：IEEE，2007：1－5.

［7］WANG Liu－chun，LIU Hai－cai.A novel anti－collision algorithm for EPC Gen2RFID systems［C］／／Proceedings of the 3rd International Symposium onwireless Communication Systems.Piscataway，NJ，USA：IEEE，2006：761－765.

［8］WALDROP J，ENGELS Dw，SARMA S E.Colorwave：an anticollision algorithm for the reader collision problem ［C］／／IEEE International Conference on Communications（ICC′03）.Piscataway，NJ，USA：IEEE，2003：1206－1210.

［9］CHOI H S，CHA J R，KIM J H.Fastwireless anti－collision algorithm in ubiquitous ID system ［C］／／Proceedings of the 60th Vehicular Technology Conference.Piscataway，NJ，USA：IEEE，2004，6：4589－4592.

［10］MYUNG J，LEEw，SRIVASTAVA J.Adaptive binary splitting for efficient RFID tag anti－collision ［J］.IEEE Commun Lett，2006，10（3）：144－146.

［11］EPC global.Tag data standards version 1.3 ［EB／OL］.（2006－03－08）［2011－02－24］.http：／／www.epcglobalinc.org／standards／tds／tds－1－3－standard－20060308.pdf.