基于随机时隙的RFID读写器防冲突方法

张光山 张 烁 张有光

（北京航空航天大学 电子信息工程学院，北京100191）

无线射频识别系统中读写器和标签通信具有空间受限的特性.由于 RFID（Radio Frequency I－dentification）读写器的覆盖范围有限，在很多RFID系统应用中，需要RFID读写器能在一个大的范围内的任何地方都能读写标签，因此必须在整个范围内配置很多读写器，不可避免地存在读写器冲突问题.

随着RFID的广泛应用，读写器冲突问题得到重视并做了一些研究.文献［1］最早提出了RFID读写器冲突问题，并指出读写器冲突是一种类似于简单图着色问题.随后文献［2］提出了一种Colorwave读写器防冲突算法.Colorwave是一种基于时分多址原理的分布式防冲突算法，当网络中读写器的数量比较小时该方法是有效和可行的.文献［3］提出一种分布式颜色选择算法（DCS，Distributed Colour Selection），该算法的时隙数是固定的并且容易实现，然而当时隙数与读写器数不匹配时，算法性能将大大降低.文献［4］提出一种增强型PDCS（Probability DCS）算法，当读写器发生碰撞时则依据预先设定的概率阈值选择新的颜色，可降低碰撞概率，但概率阈值的选择会影响系统性能［5］.欧洲电信标准协会发布的EN 302 208标准［6］采用一种基于载波侦听多路访问（CSMA，Carrier Sense Multi－Access）原理的先侦听后发言的方法来减少读写器冲突情况.该方法尽管实现简单，但是可能导致某些读写器长时间无法获得信道.EPC Class I Gen2标准［7］阐述了采用频分多址原理来避免读写器冲突的算法，但是由于大部分的标签不具备频率分辨能力，因此仍然存在读写器冲突情况.Pulse算法［8］将读写器的通信信道分为控制信道和数据信道，由于该算法采用竞争检测机制，当有大量读写器同时竞争信道时，算法的访问延迟性能将大大降低.

传统基于时隙分配的防冲突方法可分为分布式与集中式时隙控制两种.第一种方法以Colorwave［2］等算法为代表，时隙分配过程以网络中的每个读写器为中心，各读写器之间相互反复通信协商来确定各自的工作时隙，发生冲突时往往通过增加新的时隙来解决，结果是时隙分配过程较长且需要的总时隙数目增多；第二种方法通过中央计算机运行优化算法来进行时隙分配求解，几乎不占用读写器资源，不过该方法的性能取决于所选择的优化算法的复杂度.

为了解决RFID网络中的协议冲突，本文在结合分布式和集中式时隙控制方法的基础上提出一种基于随机时隙并通过中央计算机协调的读写器防冲突方法.提出读写器根据当前利用率随机选择时隙，提高了各读写器读写的公平性；增加额外时隙使得读写器有更多机会读写标签，提升RFID系统的吞吐量.中央计算机负责同步和协调各读写器时隙，读写器根据邻近读写器工作和碰撞情况选择时隙执行读写操作，从而消除读写器之间的冲突情况.

1 多读写器防冲突方法

密集读写器环境是指在RFID系统中，在预定区域内部署多个RFID读写器，以满足对区域内的所有标签进行完全的高可靠的读写.

读写器网络通常包含多个读写器和一个中央计算机，读写器与中央计算机一般采用局域网或者无线局域网方式进行通讯连接.网络中每个读写器可能具有不同范围的读写区域，各读写器的读写区域可能有交集，即读写区域有相互重叠地方.另外由于RFID系统的非对称性，标签反射到读写器的信号能量很低，因此在一个很大的范围内都可能存在读写器到读写器的干扰即干扰范围远大于读写范围.

假定RFID系统中各读写器使用相同信道，读写器信标和忙信号的通信范围为读写器的干扰范围，中央计算机负责同步和协调各读写器.本文防冲突方法主要结合了分布式和集中式时隙分配的优缺点，具体流程如下：

1）中央计算机发送每轮回起始命令，并根据整个读写器网络规模，选择合适的总时隙数M并通知各个读写器.

2）读写器根据接收到的M值和各自的利用率随机选择合适的时隙.将M 个时隙n等分，其中n＜M，低利用率的读写器可以选择低时隙进行工作，提高了各读写器之间的公平性.设读写器ri工作次数为wi，轮回间隔为u和当前轮回间隔数为m，定义利用率li为

则读写器ri随机选择范围内的时隙值，其中%为求模运算，其中■·」和「·■分别为下取整数和上取整数.

3）中央计算机开始间隔发送M个时隙指令，时隙指令的时隙参数值是从0开始到M－1，协调同步各读写器.

4）读写器接收到的时隙参数值若等于自身随机选择的时隙值，则开始在该时隙进行操作.若之前收到其它邻近读写器发送的忙信号，则在该轮回不工作，否则发送信标并侦听.若读写器接收到邻近读写器发送的信标，则该读写器在该时隙停止工作，否则发送忙信号给邻近读写器并开始读写标签.

5）当中央计算机发送完M 个时隙指令，则开始发送额外时隙指令.若RFID系统中读写器都在读写标签或者不工作的读写器都接收到忙信号，则该时隙没有读写器工作.若存在空闲和没有接收到忙信号的读写器，则该读写器发送二次信标并侦听，若接收到邻近读写器的信标则该时隙不工作，否则开始读写标签.

6）当周期时间到，所有读写器停止读写标签，中央计算机根据当前网络的拓扑结构和规模选择新的时隙数并开始下一周期的操作.

2 性能分析

本节分析读写器的读写概率和在额外时隙发送二次信标的读写器个数.假设读写器ri有V个邻近读写器，选择第mi个时隙.令Pm（V，M，l，n）为读写器在第m个时隙有V个邻近读写器时读写标签的概率.对于任一时隙k（0≤k≤M－1），读写器存在3种情况：①没有邻近读写器选择该时隙；②至少有两个邻近读写器选择该时隙；③只有唯一个邻近读写器选择该时隙.

读写器ri在时隙mi若满足以下两个条件就可以读写标签：

1）对于k＝mi，满足情况①，设概率为P1；

2）对于∀k，0≤k≤mi－1，至少需要满足情况①或②，设概率为P2.

首先分析l＝1，n＝1的情况，设读写器等概率地选择M个时隙，则

当mi＝1，由于不可能收到其它读写器的忙信号，则读写器一定满足条件2）.另外由于读写器随机选择时隙，则读写器选择相同时隙的概率服从二项分布，则概率密度函数为

则

当mi＞2时，P2主要取决于前面时隙邻近读写器的读写情况.定义递推函数Q（V，r，mi）：对于∀k（0≤k≤mi－r－1）满足条件2），同时对于∀k（mi－r－1＜k＜mi－1）也满足条件2），而且对于k＝mi满足条件1），因此 P2＝Q（V，1，mi），则

其中Q（V，r，mi）为1.则读写器ri在该时隙读写标签的概率为

则读写器ri每轮回的读写标签概率为

当l≠1和n≠1，读写器的读写概率不仅与邻近读写器有关，还和利用率相关.设具有利用率为li的读写器ri有Vli个邻近读写器，则读写器具有最低利用率li＝0时对应的读写概率为

利用率为li＝1的读写器只有当最低利用率的读写器发生相互碰撞时才能读写标签，概率为

则利用率为l的读写器每轮回读写概率为

假设RFID系统中N个读写器，读写器ri在当前轮回读写标签的个数为ui，则每轮回RFID系统的吞吐量即所有读写器每轮回读写标签的总数为

从式（9）可知，最低利用率的读写器具有最高读写概率，并且随着利用率增加，读写概率急剧下降.下面分析每轮在额外时隙发送二次信标的读写器个数.

设每个读写器平均有V个邻近读写器，系统在时隙i空闲读写器个数为Ni和平均的空闲邻近读写器个数为Vi，并假设每时隙平均有个读写器发送信标.显然在时隙指令0时刻，N0＝N，V0＝V.由于每个读写器有N0－V0－1个读写器不在自己的干扰范围内，则时隙0读写器发送信标且没有受到邻近读写器干扰的概率为

平均邻近读写器为

对于第M个时隙指令，则有

可以看出在额外时隙有NM个读写器可以发送二次信标，因此添加额外时隙可以使得那些没有接收到忙信号和空闲的读写器有机会读写标签，进一步提高系统的吞吐量以及公平性．

3 仿真结果分析

对提出的防冲突方法进行仿真，并与传统的PDCS，Colorwave和Pulse算法进行比较．仿真参数设置：读写器的读写范围为2m和干扰范围8m［9］，读写器数量从10到50个或者500个，读写器部署范围为40m×40m到100m×100m，根据文献［10］，读写器在读写距离为2m的条件下在0．46s内可以读写7个标签．PDCS和Colorwave算法中交互信号的时间为1ms［10］，因此时隙长分别为0．461s，0．462s．对于Pulse算法，信标指令时间为5ms［8］．本文方法起始命令时间2．83ms，时隙指令时间为1ms，工作忙和信标信号时间为0．3ms［10］．根据文献［11］，Jain公平指数定义为

其中N为读写器数量和xi为第i个读写器的吞吐量，用于衡量各防冲突方法的公平性．

图1给出了不同的防冲突方法对应的吞吐量．吞吐量定义为RFID系统中所有读写器每秒钟读写标签的总数，好的防冲突方法可以保证读写器读写更多的标签即高的吞吐量．PDCS算法仿真时采用最优颜色数［3］，若不采用最优颜色值，系统性能将下降，概率值取为0．7．由图可知，本文的防冲突方法的吞吐量明显优于PDCS和Colorwave方法，并且逼近Pulse方法和理论值．

图1 不同防冲突方法的吞吐量对比仿真

图2为不同防冲突方法的Jain公平指数．Jain公平指数越高，说明该防冲突方法使得各读写器有更公平的机会读写标签．由图可知，本文的防冲突方法的公平性指数明显优于Colorwave和Pulse方法，不过低于PDCS算法．PDCS算法的性能取决于初始配置值，若不采用最优颜色值，系统公平性将下降．

图2 不同防冲突方法的Jain公平指数对比仿真

图3分析对比了不同利用率对应读写概率的仿真和理论曲线．仿真情况分两种：读写器个数N＝10和时隙数M＝14；N＝30和M＝32．由图可知，越低利用率的读写器读写标签的概率越高，而越高利用率的读写器读写标签的概率就很低，保证了各读写器之间的公平性．

图4分析对比了不同时隙下发送信标读写器的个数的仿真和理论曲线．从图中可以看出，随着时隙增加，发送信标的读写器在不断减少，但在额外时隙，发送信标的读写器明显增加，说明有较多的读写器没有接收到工作忙信号，可以发送二次信标信号，因此增加额外时隙可提高系统的吞吐量.

图3 读写概率仿真

图4 发送信标读写器的个数的仿真

4 结 束 语

本文提出了一种基于随机时隙并通过读写器协调的读写器防冲突方法.该方法结合了分布式和集中式防冲突方法的优缺点，中央计算机负责同步和协调各读写器时隙，读写器之间不需要同步，减少了读写器的负担；读写器根据当然利用率随机选择时隙，若读写器没有接收到忙信号且没收到邻近读写器的信标则在当前时隙工作，否则可在额外时隙发送二次信标，仿真结果表明该方法是可行的和可靠的.与现有的PDCS，Colorwave和Pulse算法相比较，本文提出的方法具有较好的吞吐量和公平性.

（

）

［1］Engels D W，Sarma S E.The reader collision problem［C］／／Proceedings of IEEE International Conference on Sysmtems Man and Cybernetics.Hammamet，Tunisia：IEEE ICSMC，2002：6－9

［2］Waldrop J，Engels D W，Sarma S E.Colorwave：an anticollision algortihm for the reader collision problem［C］／／Proceeding of 2003IEEE International Conference on Communication.Anchorage Alaska，USA：IEEE ICC，2003：1206－1210

［3］Waldrop J，Engels D W，Sarma S E.Colorwave：a MAC for RFID reader networks［C］／／Proceedings of IEEE Wireless Communic－ation and Networking Conference.New Orleans，Louisiana，USA：IEEE WCNC，2003：1701－1704

［4］Gandino F，Ferrero R，Montrucchio B.Probabilitic DCS：an RFID reader－to－reader anti－collision protocol［J］.Journal of Network Computing Applications，2011，34（3）：821－832

［5］Gandino F，Ferrero R，Montrucchio B.Introducing probability in RFID reader－to－reader anti－collsision［C］／／8th IEEE Internati－onal Symposium on Network Computing and Application.Cambridge，Massachusetts：IEEE ISNCA，2009：250－257

［6］ETSI EN 302 208.Electromagnetic ompatibility and radio spectrum matters［EB／OL］.Brussels：ETSI，2005［2008－6－8］.http：／／www.etsi.org

［7］EPCglobal.EPC radio－frequency identity protocols class－1 generation－2UHF RFID protocol for communications at 860MHz－960MHz［EB／OL］.Brussels：EPCglobal Inc，2005［2007－1－12］.http：／／www.epcglobalinc.org

［8］Birari S，Iyer S.Mitigating the reader collision problem in RFID networks with mobile readers［C］／／13th IEEE International Conference on Networks.Bombay，India：IEEE ICN，2005：463－468

［9］Eom J B，Yim S B，Lee T J.An efficient reader anticollision algorithm in dense RFID networks with mobile RFID readers［J］.IEEE Trans Ind Electron，2009，56（7）：2326－2336

［10］Buettner M，Werherall D.An empirical study of UHF RFID performance［C］／／Proceeding of ACM International Conference on Mobile Computing and Networking.New York，USA：ACM ICMCN，2008：223－234

［11］Renato Ferrero，Filippo Gandino.A fair and high throughput reader－to reader anticollision protocol in dense RFID networks［J］.IEEE Transactions on Industrial Informatics，2011，99（1）：1－9