针对射频识别系统中，基于树的防碰撞算法因存在较多空闲时隙和碰撞时隙导致系统效率低的问题，提出了基于冲突分段的动态树型防碰撞算法（DTCS）。新算法充分考虑随着搜索层数增加，碰撞节点内标签数量减少，标签未识别序列碰撞概率降低这一特点，有效利用冲突位分布信息，按规则提取每一碰撞节点标签查询段[N]，结合编码机制，确定查询前缀，优化查询命令。理论分析和仿真结果表明，新算法避免了空闲时隙，快速缩短了搜索深度，从而降低标签识别时延，系统吞吐率提高达0.649。
张荣华,张海鬧,杨大志,等:基于冲突分段的动态树型RFID防碰撞算法 2017,53(15)119 N当k>1时,段信息M包含两个碰撞位但不限制段(元,从根节点开熔查∠询堆栈Q,k=0,5=0 段内比特位数,初始化s=0,=0。提取杳询前缀段 步骤I初始化阅读器和 内比特位数,即N1=n,1n12…131(≤n-$),n,为第 步骤2阅读器发出查询命令Req( prefix),L作范 碰撞位。将碰撞位的二进制序列转换为相应的进制内与当前查询前级匹配的标签响应,并置标签状态标 制数h,根据2数值得4b进制序列B=bb志位F=1 再将转换后的序列回复给阅读器,通过曼彻斯特编码, 步骤3阅读器判断时隙状态。若为识別时隙,表明 阅读器能直观地识别出任意两位信息。例如碰撞位为有且仅有一个标签响应将EPC发送给阅读器后进入休眠 00和10时,通过编码,发送B1=00,B2=0100,阅读状态,不再参与标签竞争,并置标签状态标志位F=0, 器接收到碰撞信息0Q,根据和位发生碰撞,获跳转到步6若有多个标签响应,则碰时 知当前工作区域内仅存在00和10的序列,此时便唯 、步骤4检测标签未搜索序中发生碰撞的位数 确定了段信息Ⅺ,将其作为询前缀并入栈,更新当 如果不止Ibit发生冲突即k>1,按照段M1规则 前查洵位置和层数s=s+1,L=L+1,互提取前缀查询段,采用段内碰撞位编码机制,确定查询 1时,段信息N2…,根据碰撞前级段M,更新当前查淘位置和层数s=+ 位非0即1的原则确定查询段N2并入栈,此时s=n, L=L+1,k=0。此思想优化了阅读器套询命令,避免发生冲突k=1,将碰撞位分别置0和1,确定前级查询段 空闲时隙,采用逐层分段的枧制,极大缩短了搜家深度, N2,此时s=”,L=L+1,k=0;跳转至步骤5。 提高了识別效率 步骤5发送 Pushin)→Q,将查询前缀段入栈,读 DTCS算法流程如图1所示,主要步骤如下 取栈首前缀,返回步骤2继续搜索 步骤6判断查询堆栈Q是否为空,如果不是,返回 初始化 步骤2,否则,标签识别算法结束。 阅读器发送查询 举例说明识别标签的步骤。假设存在6个8位待识 命令 Rey prefix) 别的标签I分别为:Tag1(1000010),Tag2(01001101) 满足查询条件的标 Tag3(10010111),Tag4(11000100,Tag5(10000111 答应答,并置F=1 Tag6(1100010),具体搜索过程如图2和表1所示。 DASM算法 DTCS算法 检测未识别EPC 碰撞 中碰撞位效k 付隙状态? 识别 读取标签,然 后转休眠状 000 00101101011 00110010 000110 根据碰撞位分布提|提取N序列态,并置F-0 L=2 太太入太入 取查询前缀段N1 110/1100/0 将碰撞位分 读取栈首前 提取碰撞位并解码别置0和1,确〈排栈为空 人 缀并发送 定登询前缀 阅读器确定查 磁撞时隙 识别时隙 是 询前缀段信息 L-L+1(法结)将前段入栈 图2DASM和DTCS算法搜索流程 S=5+t,L=+1 k=0 由图2和表1可知识别实例中的6个标签,DASM k=0,!=0 算法搜索深度L=3,有5个碰撞节点,总共11个时隙 图1DTCS算法流程图 而DTCS算法最大搜索深度Ⅰ=2,没有空时隙,只有 表1对实例标镲的识别过程 查询次数阅读器查询命令搜索深度响应标签阅读器接收信息时隙状态Nts 堆栈内容 全部 碰撞 识别 1,3,5 碰撞 0x011x68000110,000111.01011l.1l 000110 识别 000111,010111,1l 0001lI 识别 01011 3 识别 4,6 碰撞 0001x0/6 8 OUU100,000110 000100 识别 000110 000110 2 识别 1202017,53(15) Computer Engineering and Applications计算机工程与应用 3个碰撞时隙,总共需要9个时隙。这是由于DASM通数量m-和未搜索序列长度m1-: 过阅读器首次查询获知k=6,将序列码固定分为3段, 定程度上提高了效率,但不够彻底。DTCS算法获取 m->m(1-4)1 (11) 每一碰撞节点冲突信息,动态更新查询段,极大提高标 1(1-4 签识别效率 32性能分析 假设RFID系统内有均匀分布的m个待识别标签, 其EPC序列长度为n。对于一棵完整的四叉树,在第l 第L-1层碰撞节点内标签的剩余碰撞位平均数为 层有4个节点,选择其中一个节点的概率为24E(的)=∑1--1 有z个在第层选择同一个节点响应的概率服从项 13) 分布P(x/m,DC少(-),由此可得: o、相据DTCS算法总搜层数为L,则E则表 空闲时隙概率 示取小于该值得最大整数)等于1或2,当E(k)-1时, P(/nD)=-py=(1-4 (1)即第L层采用二叉树询,故新算法的碰撞总时隙数为 别时隙概率: C(m)=>C(m,l)= P(1/m.O=m1-p)1=m=4y 碰撞时隙的概率: 411-(1-4y-m(1-4) 4 P(x>1/m,D=1-P(0/m,D)-P(1/m,D)= o2-Lyi_ 7 (1-2 1-(1-4y-m(1-4-1 (3) (14) 第l层识别时隙数Rm2 当[E1-1(k)=2时 R(m,)=m(1-4-)-1 (4) (m)=∑Cm,)= 第层碰撞时隙数C(m,D CmO=21(1-01-4-y-ma-4y (1-4m-m2(1-44y-1 (5) (15) 总的碰撞时隙数((m): 总时隙数 T(m=c(m)+m (16 Cm)=∑C(m 1,4)= 吞吐率定义为成功识别标签数占总时隙的比 例,即 41(1-(1-4 m1(1-4 n-1 (6) T(m) (17) 由 J DTCS算法采用逐层自适应分段查询,其实际 搜索层数将大大减少。设新算法总搜索层数为1,对于4算法仿真结果与分析 第l层碰撞节点内未搜索序列长度为n的m个待识别 标签,其某一比特位不发生碰撞的概率为p=11,则用QT算法、ASM算法、DASM算法、DTCS算法及尢空 有k比特位发生碰撞的概率服从二顶分布 闲时隙四叉树进行识别,取20次实验结果的平均值,从 时隙数和吞吐率两个方面,采用 Matlab对算法进行仿真 P,k=c (7)和性能比较,如图3~图5所示。 从图3,图4叮以得出,当标签数量较少时(约小于 第层未搜索序列碰撞位平均数E(k): 00 E()=P()=>kC(1-1 DTCS (8 由于每个标签选择碰撞节点的概率相等,则m和 70 -++DASM 多60无空闲时 n2分别为: 隙四义树 盅50 40 m-RO (9 (E1=1(k)-2)n (10) 0102030405060708090100 E-1(k) 标签数 出递推公式(7)~(10)得第L-1层碰撞节点内标签 图3五种算法碰撞时隙数比较 张荣华,张海鬧,杨大志,等:基于冲突分段的动态树型RFID防碰撞算法 2017,53(15)121 200H-A-ASM - E-DASM 150,无空闭时 吋隙四义树 隙四叉 100 0.5 只, 甲,田.只.册,,量,田., 0.2 102030405060708090100 5102030405060708090100 签数 标签数 4五种算法总时嗦数比较 图5五种算法奋吐率比较 15),ASM算法优于QT算法,DASM算法优于无空闲 industries[J]Journal of Engineering and Technology 时隙四叉树算法,这是由于ASM、DASM在读写器首次 Management,2012,29(1):152-167 査询时,获取标签碰撞比特位数k,构造矩阵,此时2] Lee s r,JosD, Lee C w.An enhanced dynamic 0<Hkn)k1,一定程度上缩短了搜索层数,减少了碰 framed slotted ALOHA algorithm for RFID tag identifi 撞时隙和总时隙数。随着标签数增加,ASM和QT, ation[C]//The Second Annual International Confer DASM和无空闲四叉树算法性能趋于致,此时每→比 on Mobile and Ubiquitous Systems: Networking 特位发碰撞的概率急剧增大,ASM只能逐位搜索,不 Services.IEEE. 2005: 166-17 能体现算法优势。DASM算法将ASM二义树改为四义 [3」韦冬雪,郑嘉利,黄庆欢捕获效应下基于反馈机制的RFID 树搜索,减少了碰撞时隙,同时采用前缀优化去除空闲 防碰撞算法[计算机工程与应用,2015,51(17):70-7 [4] Chen W TA feasible and easy-to-implement anticollision 时隙,总时隙也相对减少 algorithm for the EPCglobal CHF class-1 generation-2 DTCS算法考虑了随着层数增加,每·分叉下碰撞 RFid protocol. IEEE Transactions on Automation Science 节点内标签数量减少,未识别序列碰撞概率降低的特 ring,2014,11(2):485-491 点,采用逐层分段机制,缩短搜索深度。同时在四义树[5]suJ, Sheng z, Hong D, et al.An effective frame breaking 的基础上避免了空闲时隙(1.162m),性能大幅提升 olicy for dynamic framed slotted aloha in RFID[] 仿真结果表明其碰撞时隙约为0.54m,所需总时隙最 IEEE ComMunications Letters, 2016. 20(4): 692-695 少,约为1.54m,大约在154个时隙内能成功识别100个[6] Myung J,Leew, Srivastava j. Adaptive binary spilling 标签,系统效率更高。 for efficient RFID tag anti-collision[J].IEEE Communica 图5表明新方法的吞吐率最高约为0.649。DASM tions letters,2006,10(3):144-146 算法优于ASM算法,但都随着标签增加吞吐率下降。[71 yung J,Lew. srivastava. ag-splitting: Adaptive collision 因此从鉴别时延,吞吐率方面,都表明新方法性能更优, arbitration protocols for RFid tag identification.IEEE 将其应用到RFID系统中,在可读范围内能正确识别更 TransacTions on Parallel and Distributed Systems, 2007 18(6):763-775 多的标签信息。 [8]丁治国,朱学永,郭立,等.自适应多叉树防碰撞算法研 究[J自动化学报,2010,36(2):237-241 5结束语 [9]张学军,蔡文琦,王锁萍.改进型自适应多叉树防碰撞算法 提出了一种基于冲突分段的动态树型RFID防碰撞 研究[电子学报,2012,40(1):193-198 算法。阅读器发送查询命令,有且仅有一个标签响应,「0王雪,钱志鸿,刘晓慧,等.改进的树型结构RFD防碰撞 则识别该标签:如果发生碰撞,检测碰撞位分布,提取前 算法[通信学报,2015,36(7):129-137 缀杳询段根据碰撞位编码机制,阅读器解码出相应的[1] Zhang L, Zhang J,Iang. Assigned tree slotted Aloha 段信息,更新查询堆栈,继续遍历标签,直至堆栈为空 RFID Lag anti-collision protocols!. IEEE Transactions on 识别过程结束。理论分析和仿真结果表明,该方法逐层 Wireless Communications, 2013, 12(11): 5493-5505 提取碰撞位分布信息,以成段的形式确定查询堆栈元121 Zhang D, Wang X, Song x, et al.A novel approach to 素,优化阅读器命令,避免空闲时隙,同时缩短搜索深 mapped correlation of ID for RFID anti-collision [J].IEFF 度,从而降低系统时间复杂度,提高识别效率。进一步 Transactions on Services Computing, 2014, 7(4): 741-748 的研究将充分考虑标簦动态迁移时的止确识别问题,推 [13]」治国,郭立,刘琦.一种基亍搜宗矩阵的自适应防碰撞 算法[模式识别与人工智能,2008,21(4):476-481 动RFID技术在移动场景中的应用。 「14]石封茶,崔琛,余剑动态自适应搜索矩阵防碰撞算法研 究[电路与系统学报,2013,18(2):37-342 参考文献: [15 Hush DR, Wood C Analysis of tree algorithms for RFID [1 Zhu X, Mukhopadhyay s K, Kurata H. A review of RFID arbitration[C/iEEE International Symposium on Infor- technology and its managerial applications in different mation Theory, Cambridge, MA, LSA, 1998: 107-116