| 标题 | 基于物理层网络编码的RFID标签防冲突算法研究 |
| 范文 | 王翠香++邵星 摘 要：针对二进制搜索树算法在解决射频识别系统多标签冲突时读写速率低的问题，提出一种基于物理层网络编码的射频识别标签防冲突算法PNBA。PNBA算法将传统防冲突算法丢弃的多标签冲突信息压栈保存，引入物理层网络编码技术，结合栈顶信息和已识别标签信息，通过物理层网络编码的解码运算得到未被读取的标签信息，减少读写器和标签之间的交互次数，提高多标签的识别速率。理论分析和MATLAB仿真表明，PNBA算法与现有二进制搜索算法相比，能够减少读写读取次数，提高系统读写速率。在标签数目为100时，其读取次数比基本二进制搜索树算法低83%，比后退二进制搜索树算法低43%，读取次数效率达0.93。 关键词：射频识别；标签防冲突算法；物理层网络编码；二进制搜索树算法 DOIDOI：10.11907/rjdk.1511164 中图分类号：TP312 文献标识码：A 文章编号文章编号：1672-7800（2015）012-0053-03 基金项目基金项目：国家自然科学基金项目（61502411）；江苏省自然科学基金项目（BK20150432）；江苏省高校自然科学研究面上项目（15KJB520034）；盐城工学院人才引进项目（2014038）；江苏省科技支撑计划项目（BY201410829，BE2014679） 作者简介作者简介：王翠香（1982-），女，山东新泰人，硕士，盐城工学院信息工程学院助教，研究方向为无线传感器网络、网络编码；邵星（1985-），男，江苏宿迁人，博士，盐城工学院信息工程学院讲师，研究方向为网络编码、无线多跳网络路由、云计算。 0 引言 射频识别（Radio Frequency Identification，RFID）[1]作为一种自动识别技术，不需要被识别物体在识别物体视距范围内即可工作，具有准确率高、读取距离远、存储数据量大、耐用性强等特点。作为物联网的关键技术之一，射频识别技术广泛应用于仓储物流、物品追踪、身份识别、门禁控制等领域。 一套典型的RFID系统[1]由一个阅读器和一些标签组成。标签用于记录和存储物品信息，阅读器用于读写标签内信息。当多个标签处于一个阅读器的工作范围内，且使用同一通信频率同时向阅读器返回信息时，将产生标签信号传输的干扰。当阅读器检测到信号发生干扰时，将无法正确读取标签内信息，称为RFID系统的多标签冲突问题[2]。该问题将严重制约RFID系统读写效率。因此，研究并解决RFID系统的多标签冲突问题具有重要意义。 1 相关工作与动机 目前已提出一些用于解决RFID系统的多标签冲突协议，主要分为两类[3]：基于ALOHA的算法和基于二进制搜索树的算法。 基于ALOHA的算法思想简单，但无法确保标签在一定时间内被读取，一些标签可能长时间无法被读取，出现“标签饥饿”问题；基于二进制搜索树的算法，在发生标签碰撞时，不断将标签分为2组，直到阅读器能够无碰撞地读取所有标签信息为止。典型算法有基本二进制搜索树算法（Binary Search Tree，BST）[4]、动态二进制搜索树算法（Dynamic Binary Search Tree，DBST）[5]、后退二进制搜索树算法（Regressive-style Binary Search Tree，RBST）[6]。基于二进制搜索树的算法是一种确定性算法，能够避免“标签饥饿”问题，因此越来越受到研究领域的重视。 二进制搜索算法中，阅读器在检测到发生碰撞后，简单地将冲突信息丢弃。但该冲突信息包含有多标签信息，如能加以利用，则可以减少读写次数，进一步提高二进制树搜索算法的性能。 近年来出现的网络编码技术[7]，给RFID阅读器利用多标签冲突信号、提高读写效率带来了可能。网络编码允许网络中的中间节点对接收到的数据进行编码后转发。物理层网络编码[8]则是在物理层进行数据编码，利用电磁波的叠加特性，将无线电磁波在空间的自然叠加看作信号的编码过程，即等效为物理层的网络编码过程。在接收端通过译码获取所需信息，可减少数据传输时间，提高传输效率。 而RFID系统中多标签冲突发生时，冲突信号是多个标签信号的叠加，正是一种物理层网络编码运算。物理层网络编码的技术特点，使其适合于处理RFID系统中多标签的应答信号叠加时产生的冲突问题。 为此，本文提出一种基于物理层网络编码的二进制算法（Physical layer Network coding based Binary Algorithm，PNBA）来解决射频识别中的多标签冲突问题。与现有的射频识别标签防冲突算法相比，PNBA算法的创新性在于其引入了物理层网络编码，将传统方法中丢弃不用的多标签叠加冲突信息利用起来，分析和利用其中的有用信息，提高射频识别系统对多标签的识别速度和运算开销。仿真结果表明，PNBA算法在标签数目为100时，其识别次数比BST低83%，比RBST低43%，其读取次数效率达到0.93。 2 PNBA算法 2.1 PNBA算法冲突位识别 PNBA算法采用曼彻斯特码，以识别出接收到的信号是否发生了多标签冲突，并能定位到具体哪些位发生了冲突。PNBA算法在识别冲突时，将检查叠加信号的解调信号。如果该位前半周期或后半周期为零电平，则该位未发生冲突。如果该位前半周期和后半周期都为非零电平，则该位发生冲突，用“X”表示。 2.2 PNBA算法相关约定 在给出PNBA算法详细流程前，首先给出PNBA算法用到的相关概念和符号。 请求命令——REQ（RSN）：请求命令发送一个参考序列号RSN（Reference Sequence Number），序列号大于RSN的标签不应答，小于等于RSN的标签应答，以减小待识别标签数量，即减小冲突范围。 选择命令——SEL（RSN）：序列号与RSN相同的标签，被阅读器选择，为进行后续的读写操作等作准备。 读取命令——RD-DATA：阅读器读取被选择命令选定的标签返回的序列号数据。 休眠命令——UNSEL（RSN）：将序列号与RSN相同的标签置位休眠状态，不再响应阅读器的任何命令。 阅读器堆栈——为了保持冲突信息，阅读器在识别标签过程中维护一个堆栈结构，用于保存接收到的多个标签的叠加冲突信息。 2.3 PNBA算法流程 PNBA算法将物理层网络编码引入到射频识别标签防冲突方法中，分析和利用被传统防冲突方法丢弃的冲突信息，提高标签识别效率，具体包括以下步骤： 步骤1：初始化参考序列号RSN，将其每一位设置为1，例如电子标签的序列号为8位，则参考序列号初始化为11111111，初始化后退变量i为0。 步骤2：读写器执行读请求命令REQ（REQuset），所选标签组中标签序列号小于等于参考序列号的电子标签应答，并传回该标签序列号。 步骤3：按照曼彻斯特码编码原理，读写器对接收到的信号进行解调、译码并检测是否发生冲突：如果某个码元的前半周期和后半周期都为非零电平，则表明该码元产生冲突，将该冲突信号对应的冲突解调信号压入冲突解调信号堆栈，然后找出最高的冲突比特位，将译码信号的最高冲突比特位设置为0，低于该位的设置为1，高于该位的保持不变，然后以此作为下一次请求命令 REQ的参照序列号，执行步骤2；如果每个码元的前半周期和后半周期中，其中一个为高电平，另外一个为低电平，则没有产生冲突，读写器能识别该标签信息，执行步骤4。 步骤4：对选中的标签，读写器执行读出数据命令RD-DATA（ReaD-Data）来读取标签数据并保存，接着执行去选择命令 UNSEL（UNSELect），使标签进入“休眠”状态。 步骤5：判断冲突解调信号堆栈是否为空，如果为空，表示所有标签信息都已得到，则算法结束。否则读写器将已读取到的标签数据与冲突解调信号堆栈栈顶存储的冲突解调信号作减法运算，执行i=i+1运算：如果无法得到无冲突的编码信号，即运算结果始终存在冲突，执行步骤6；如可以得到无冲突的编码信号，则得到1个未读取标签信息，将该标签信息存储，然后读写器执行去选择命令UNSEL，使该标签进入“休眠”状态，冲突解调信号堆栈的栈顶元素出栈，重复步骤5；如果得到信号为全低电平，表明该冲突信号内所有标签信息都已解码得到，将冲突解调信号堆栈栈顶元素出栈，重复步骤5。 步骤6：将倒数第i次读写器与标签交互所用的参考序列号作为下一次请求命令 REQ 的参照序列号，将i重新设置为0，然后执行步骤7。 步骤7：返回步骤2，直到识别出所有标签为止。 PNBA算法流程如图1所示。 图1 PNBA算法流程 3 PNBA算法仿真分析 为了分析PNBA算法的性能，使用MATLAB对BST、DBST、RBST和PNBA算法进行了仿真。 图2给出了待识别标签数目为5～100时，4种算法分别需要的读取次数。由图2可知，BST和DBST所需的读取次数一致。RBST的读取次数与BST和DBST相比，有了较大幅度降低，且随着标签数目增加，优势越发明显。在标签数目在5～25范围内，PNBA算法和RBST算法较为接近；待识别标签数目大于25以后，PNBA所需的读取次数明显低于RBST，且随着标签数目增加，其与RBST相比优势越大；在标签数目为100时，PNBA算法比RBST算法低45%。 图2 不同标签数目时各算法所需读取次数比较 图3给出了待识别标签数目为5～100时，4种算法读取次数效率的比较。所谓读取次数效率，为标签个数除以所需的读取次数。从图3可以看到，PNBA算法的读取次数效率明显高于其它3种算法。当标签数目在5～40范围内时，BST和DBST的读写次数效率逐步降低至0.2，PNBA算法逐步增加至0.8，而RBST一直维持在0.5；标签数目大于40以后，BST、DBST、PNBA的读取次数效率变化较为缓慢，BST和DBST维持在0.16～0.19之间，PNBA维持在0.89～0.93之间，RBST一直维持在0.5。 4 结语 本文提出基于物理层网络编码的二进制算法PNBA来解决射频识别中的多标签冲突问题。PNBA依托物理 层网络编码技术，利用多标签冲突信号中的信息，能够减少识别次数，提高识别效率。多个标签非严格同步情况下，冲突信息的解码将是本文下一步的研究工作。 图3 不同标签数目时各算法读取次数效率比较 参考文献参考文献： [1] ROBERT C M.Radio frequency identification（RFID）[J].Computer and Security，2006，25（1）：18-26. [2] QIAN ZHIHONG，WANG XUE.An overview of anti-collision protocol for radio frequency identification device[J].China Communications，2014，11（11）：44-59. [3] ZHU LEI，SHING TAK，YUM PETER，et al. A critical survey and analysis of RFID anti-collision mechanisms[J]. IEEE Communications Magazine，2011，49（5）：214-221. [4] WALDROP JAMES，ENGELS DANIEL W，SARMA SANJAY E.An anti-collision algorithm for the reader collision problem[C].2003 IEEE International Conference on Communications，Piscataway，2003：1206-1210. [5] LI BINGZHANG，JING ZHENGJUN，LUO YE. A RFID anti-collision searching algorithm based on regressive-style binary system[J]. Computer Applications and Software，2009，26（12）：96-98. [6] LAW CHING，LEE KAYI，SIU KAI-YEUNG. Efficient memory-less protocol for tag identification[C].2000 4th International Workshop on DIALM，NewYork：ACM Press，2000：75-84. [7] AHLSWEDE RUDOLF，CAI NING，LI SHUOYENROBERT，et al.Network information flow[J].IEEE Transactions on Information Theory，2000，46（4）：1204-1216. [8] ZHANG SHENGLI，LIEW SOUNG CHANG，LAM PATRICK P. Hot topic： physical-layer network coding[C].The 12th Annual International Conference on Mobile Computing and Networking，NewYork：ACM Press，2006：358-365. （责任编辑：黄 健） |
| 随便看 |
|
科学优质学术资源、百科知识分享平台，免费提供知识科普、生活经验分享、中外学术论文、各类范文、学术文献、教学资料、学术期刊、会议、报纸、杂志、工具书等各类资源检索、在线阅读和软件app下载服务。