Comparative performance analysis of various artificial immune networks applied to RFID reader-to-reader collision avoidance

Within a radio frequency identification (RFID) system, the reader-to-reader collision problem may occur when a group of readers operate simultaneously. The scheduling-based family, as one branch of RIFD reader collision avoidance methods, focuses on the allocation of time slots and frequency channels to RFID readers. Generally, the RFID reader-to-reader collision avoidance model can be translated as an optimization problem related with the communication resource allocation by maximizing the total effective interrogation area. Artificial immune networks are emerging heuristic evolutionary algorithms, which have been broadly applied to scientific computing and engineering applications. Since the first version of artificial immune networks for optimization occurred, a series of revised or derived artificial immune networks have been developed which aim at capturing more accurate solutions at higher convergence speed. For the RFID reader-to-reader collision avoidance model, this paper attempts to investigate the performance of six artificial immune networks in allocating communication resources to multiple readers. By following the spirits of artificial immune networks, the corresponding major immune operators are redesigned to satisfy the practice of RFID systems. By taking into account the effects of time slots and frequency channels, respectively, two groups of simulation experiments are arranged to examine the effectiveness of different artificial immune networks in optimizing the total effective interrogation area. Besides, a group of examination is executed to investigate the performance of six algorithms in solving different dimensionality of solution space in reader collision avoidance model. Meanwhile, a single group of simulation experiments are arranged to examine the computational efficiency of six artificial immune networks. The results demonstrate that six artificial immune networks perform well in searching the maximum total effective interrogation and are suitable to solve the RFID reader-to-reader collision avoidance model.     

Artificial immune network-based anti-collision algorithm for dense RFID readers

Radio frequency identification (RFID) is faced with reader-to-reader collision problem when multiple readers are deployed densely. In scheduling-based methods, the reader-to-reader collision problem can be often mitigated from the viewpoint of optimized resource allocation to readers, which aims at maximizing the total effective interrogation area of an RFID reader network. This paper formulates a reader-to-reader anti-collision model with respect to physical positions, time slots, frequency channels and transmitting power, and thus proposes an artificial immune network with hybrid encoding for resource allocation (AINetHE-RA) to solve this model. In AINetHE-RA, a candidate antibody consists of a location segment, a channel segment and a power segment, where time slots are hidden in the last two segments. According to their respective properties, the location segment and the power segment are encoded by using real number; while the channel segment is encoded by integer number. This is the hybrid encoding format in essence. Correspondingly, in the mutation operator, different mutation strategies are designed for three segments, respectively, which make AINetHE-RA solve this reader-to-reader anti-collision model efficiently. In simulation experiments, the effects of such parameters as time slots, frequency channels, power values and locations are first investigated, and the total effective interrogation area and the number of identified tags are evaluated for the single and multiple density tag distribution. Especially, as an industrial example of non-uniform random tag distribution, the simple sectionalized warehouse management is considered to evaluate the performance of AINetHE-RA. The simulation results demonstrate that the proposed AINetHE-RA algorithm is effective and efficient in mitigating the reader-to-reader collision problem in dense RFID networks and outperforms such methods as GA-RA, PSO-GA and opt-aiNet-RA in finding the optimal resource allocation schemes.     

RFID reader-to-reader collision avoidance model with multiple-density tag distribution solved by artificial immune network optimization

Radio frequency identification (RFID) is an emerging non-contact technique where readers read data from or write data to tags by using radio frequency signals. When multiple readers transmit and/or receive signals simultaneously in a dense RFID system, some reader collision problems occur. Typically, in a modern warehouse management system, the warehouse space is partitioned into blocks for storing different goods items on which RFID tags are affixed. The goods items with the equal size are placed in the same block. Because the sizes of goods items are possibly different among blocks, the density values of tags that are affixed on the goods items are different from each other. In this case, tags in each block are distributed randomly and uniformly while tags in the whole warehouse space (i.e., all blocks are considered as a whole) follow a non-uniformly random distribution. For the sake of academic research, this situation is defined as a multiple-density tag distribution. From the viewpoint of resource scheduling, this article establishes an RFID reader-to-reader collision avoidance model with multiple-density tag distribution (R2RCAM-MTD), where the number of queryable tags is used as the evaluation index. Correspondingly, an improved artificial immune network (AINet-MTD) is used as an optimization method to solve R2RCAM-MTD. In the simulation experiments, four cases with different blocks in a warehouse management system are considered as testbeds to evaluate the effectiveness of R2RCAM-MTD and the computational accuracy of AINet-MTD. The effects of time slots and frequency channels are investigated, and some comparative results are obtained from the proposed AINet-MTD algorithm and the other existing algorithms. Further, the identified tags and the operating readers are graphically illustrated. The simulation results indicate that R2RCAM-MTD is effective for reader-to-reader collision problems, and the proposed AINet-MTD algorithm is more efficient in searching the global optimal solution of R2RCAM-MTD than the existing algorithms such as genetic algorithm (RA-GA), particle swarm optimization (PSO), artificial immune network for optimization (opt-aiNet) and artificial immune system for resource allocation (RA-AIS).     

RFID reader anti-collision algorithm using adaptive hierarchical artificial immune system

In a radio-frequency identification (RFID) system, if a group of readers transmit and/or receive signals at the same time, they will probably interfere with each other, so that the resulting reader collision problems (e.g., reader-to-reader collision, reader-to-tag collision) will happen. Generally, the reader-to-reader collision can be mitigated by maximizing the tag identification capability, which is related to frequencies and time slots, so it can be transferred as a resource scheduling problem by optimizing the tag identification capability. Artificial immune system is an emerging heuristic evolutionary method which is widely applied to scientific researches and engineering problems. This paper formulates a reader-to-reader anti-collision model from the viewpoint of resource scheduling and proposes an adaptive hierarchical artificial immune system (RA-AHAIS) to solve this optimization problem. A series of simulation experiments are arranged to analyzing the effects of time slots and frequency. Further simulation experiments are made to compare such performance indices as number of identified tags between the proposed RA-AHIAS and the other existing algorithms. The numerical simulation results indicate that this proposed RA-AHAIS is an effective reader-to-reader anti-collision method, and performs better in tag identification capability and computational efficiency than the other methods, such as genetic algorithm (RA-GA), particle swarm optimization (RA-PSO) and artificial immune system for resource allocation (RA-AIS).     

A centralized and aligned scheduler for passive RFID dense reader environments working under EPCglobal standard

Passive RFID systems with several reader stations densely allocated close to each other are susceptible to reader collision problems. They are characterized by reader-to-tag and reader-to-reader interferences. Both degrade the system performance, decreasing the number of tags identified per time unit. Although some proposals have been suggested to avoid/handle these collisions, most of them require extra hardware, do not make an efficient use of the network resources and are not compatible with the current standards and regulations. This paper proposes a centralized and aligned scheduler that optimizes the distribution of network resources (frequencies and time slots) among the readers in the network. Those readers with unidentified tags in their target region will have higher priority for receiving resources. The optimization problem is formulated as a Mixture Integer Programming problem. Results show that the method proposed provides higher network throughput and fairness than the EPCglobal Class-1 Gen-2 standard for dense reader environments. In addition, unlike previous works, the scheduling algorithm presented is compatible with EPCglobal standard and the European regulation, and can be implemented in real RFID systems with fixed and mobile readers.     

基于神经网络图着色的阅读器防冲突算法

阅读器冲突问题严重影响了RFID系统的性能,降低了识别率。使用图着色方法将频率或时隙等资源合理分配,可以防止阅读器冲突的发生。但是图着色问题是一个NP难题,利用神经网络良好的非线性逼近能力,提出基于神经网络图着色的阅读器防冲突算法。分析了阅读器冲突类型及解决方法,给出了算法的详细步骤、公式推导和能量函数,并通过计算机仿真验证了算法的有效性。     

一种基于跳频预约模式的RFID读写器网络MAC协议

在大量RFID读写器应用场合,会产生读写器冲突问题,从而影响整个系统的读取率.为了解决读写器冲突问题,提出了一个建立在慢跳频扩频(FHSS)上的MAC协议.该协议采用阅读器同步机制,读写器首先通过不同的时隙竞争预约信道,成功后使用与该时隙对应的频率进行通信,并通知相邻读写器,避免了相邻读写器同时与同一个标签通信,避免了读写器-标签冲突;采用读写器通信和标签通信按频谱分开的机制,使得读写器和标签之间不会产生频率冲突;采用多个频率跳频机制,避免了读写器频率冲突.对该协议进行的分析表明,在读写器负载较大及读写器平均通信时间较长时,该协议的系统输出较高.     

基于图论的射频识别阅读器防碰撞算法

射频识别（RFID）系统的运行往往需要多个阅读器,以保证覆盖整个目标区域。在密集的阅读器的环境中,由于阅读器之间存在相互干扰,会影响整个RFID系统的工作效率,降低识别效率。针对上述问题,提出一种新的基于图论的阅读器防碰撞算法。首先把阅读器网络看成简单图,以时隙对阅读器分组,同时隙阅读器为一组,相邻阅读器分配不同的时隙,以解决阅读器因读取范围交叉重叠而引起的干扰;同时考虑组内阅读器的频率干扰问题,同样以频率对组内阅读器再分组,同频率阅读器为一组,相邻阅读器分配不同频率,以解决因干扰范围过大而引起的频率碰撞问题;然后根据分组信息,中央服务器通过配置命令将时隙和频率资源调度分配给每个阅读器;最后通过时序命令控制每组阅读器的工作顺序。仿真结果显示,相比邻近友好型防碰撞（NFRA）算法,该算法平均工作效率提升了6.5个百分点;阅读器数量为1000时系统工作效率提升了9.5个百分点。新算法能优化给定时间内工作阅读器的数量,减少闲置等待的阅读器数量。     

A maximum likelihood-based distributed protocol for passive RFID dense reader environments

In passive RFID Dense Reader Environments, a large number of passive RFID readers coexist in a single facility. Dense environments are particularly susceptible to reader-to-tag and reader-to-reader collisions. Both may degrade the system performance, decreasing the number of identified tags per time unit. Some proposals have been suggested to avoid or handle these collisions, but requiring extra hardware or making a non-efficient use of the network resources. This paper proposes MALICO, a distributed mechanism-based protocol that exploits a maximum-likelihood estimator to improve the performance of the well-known Colorwave protocol. Using the derivation of the joint occupancy distribution of urns and balls via a bivariate inclusion and exclusion formula, MALICO permits every reader to estimate the number of neighboring readers (potential colliding readers). This information helps readers to schedule the identification time with the aim at decreasing collision probability among neighboring readers. MALICO provides higher throughput than the distributed state-of-the-art proposals for dense reader environments and can be implemented in real RFID systems without extra hardware.     

基于IRCM的抗阅读器冲突协议

在射频识别技术RFID（Radio Frequency Identification）技术的应用中,不同阅读器的信号之间互相干扰造成的阅读器冲突问题是制约系统性能的主要瓶颈之一,尤其在阅读器密集分布和移动的环境中,问题更为突出。结合现有多种抗冲突方法的优点,提出一种针对多信道的、阅读器密集分布的RFID系统的基于IRCM的抗冲突协议。仿真表明在多信道、阅读器密集分布的RFID系统中该协议能显著提高系统效率。     

一种基于ALOHA的改进RFID防碰撞算法

标签碰撞是无线射频识别(RFID)技术中的常见问题,它使得系统效率降低。ALOHA算法是解决此类问题的重要方法,提出了一种基于ALOHA的改进防碰撞算法,并分别给出了应用该方法处理碰撞时,阅读器和标签各自需要执行的程序步骤。仿真结果表明,该算法具有较高的效率,尤其在标签数量较大时相比动态帧时隙算法(DFSA)消耗时隙更少。     

RFID系统标签防碰撞的研究与改进

RFID系统中标签碰撞是一个常见问题。为解决该问题,基于Gen-2协议提出了一种改进算法,该算法考虑到阅读器对碰撞时隙和空闲时隙的响应时间不同,运用两个不同的C值动态调整Q值,并在碰撞的情况下对时隙进行局部调整,减少了标签的识别通信次数,提高了系统吞吐率,并通过仿真得到验证。     

Micro genetic algorithm with spatial crossover and correction schemes for constrained three-dimensional reader network planning

Due to the fast growing electronic commerce, the constrained three-dimensional reader network planning (C3DRNP) of the radio frequency identification (RFID) system for large warehouses is a subject that is worthy of study. A micro genetic algorithm (mGA) with novel spatial crossover and correction schemes is proposed to cope with this C3DRNP problem. The proposed algorithm is computationally efficient, which allows a frequent replacement of the RFID readers in the network to account for the fast turnaround time of the stored objects in the warehouse, and guarantees 100% tag coverage to avoid missing the records of the objects.The proposed algorithm is tested and compared with the existing methods such as the particle swarm optimization (PSO) method and the conventional GA (CGA) on solving several C3DRNP problems with various network sizes. The comparison results demonstrate the computational efficiency of the mGA and the effectiveness of the novel spatial crossover and correction schemes in searching the solution.     

RFID防碰撞算法研究

针对射频识别系统中的标签碰撞问题,在基于后退式二进制搜索算法的基础上提出一种改进算法。该算法结合动态调整算法并引入分组策略实现仅有两位碰撞即可识别标签,从而减少了搜索次数。该算法还引入堆栈存放阅读器接收到的ID数据,阅读器发送的序列号参数只是最高碰撞位信息,使得通信量减少。仿真结果表明,该算法能减少搜索次数,降低阅读器与标签之间的通信量,提高识别效率。     

RFID系统识读器冲突问题研究

介绍RFID系统中识读器的冲突问题,并提出随着时间分配频率给无线射频识别（RFID）识读器的方法,以便减少它们之间的干扰。我们通过图色的方法建立了问题模型及其相应的变量表达式。     

一种井下RFID定位系统的读卡器防碰撞算法

随着技术的进步,RFID(射频识别)已在煤矿进下定位里得到了应用。由于频率资源有限,读卡器间往往存在频率干扰,将导致RFID定位系统出现读卡器碰撞的问题。分析了读卡器碰撞的两种情形,提出了基于Q学习的仿碰撞算法,并进行了仿真测试。测试结果表明,读卡器碰状问题得到了有效控制,也说明提出的防碰撞算法是有效、可行的。     

一种改进的四叉树RFID防碰撞算法

针对随机ALOHA算法效率较低,确定性树型方法要求区域内标签数量不变的问题,提出一种改进的四叉树RFID防碰撞算法。在阅读器阅读范围内的标签根据不同的问询命令修改自身应答概率进行分组。阅读器采用比较碰撞位的四叉树算法识别应答概率为1的标签。通过公式推导证明了算法采用四叉树识别的合理性。实例说明和仿真结果显示,该算法能减少阅读器和标签之间的查询次数和通信量,有效提高阅读器的识别效率。     

An anti‐collision algorithm based on balanced incomplete block design in RFID systems

An important challenge in radio frequency identification (RFID) systems is the collision concern. When an interrogator send a request, it has several tags to answer to in its transmission range, and a tag collision has occurred. The interrogator must be able to recognize tags as rapidly as possible. A collision problem is a power‐consuming occurrence that diminishes the operation of RFID structure. This article proposes a tag anti‐collision power‐clustering RFID algorithm for all tag identification. The tags are boundaries into the several power level clusters based on distances of the reader. Specifically, in the proposed algorithm, tags and readers use of balanced incomplete blocks design (BIBD) to reach a fast identification. In a BIBD matrix, any two columns intersect exactly in one component that makes it possible for easy transmission of any two tags via the tag's identification in their read cycles. The aim of this article is to propose a joint organization that while decreases power consumption increases the working lifetime of RFID structure. The reader can get each tag ID by distinguishing each unit of BIBD symbols, one by one. The use of proposed algorithm brings about a great improvement in the power consumption and identification time.     

Efficient tag detection in RFID systems

Recent technological advances have motivated large-scale deployment of RFID systems. However, a number of critical design issues relating to efficient detection of tags remain unresolved. In this paper, we address three important problems associated with tag detection in RFID systems: (i) accurately detecting RFID tags in the presence of reader interference (reader collision avoidance problem); (ii) eliminating redundant tag reports by multiple readers (optimal tag reporting problem); and (iii) minimizing redundant reports from multiple readers by identifying a minimal set of readers that cover all tags present in the system (optimal tag coverage problem). The underlying difficulties associated with these problems arise from the lack of collision detection mechanisms, the potential inability of RFID readers to relay packets generated by other readers, and severe resource constraints on RFID tags. In this paper we present a randomized, distributed and localized Reader Collision Avoidance (RCA) algorithm and provide detailed probabilistic analysis to establish the accuracy and the efficiency of this algorithm. Then, we prove that the optimal tag coverage problem is NP-hard even with global knowledge of reader and tag locations. We develop a distributed and localized Redundant Reader Elimination (RRE) algorithm, that efficiently identifies redundant readers and avoids redundant reporting by multiple readers. In addition to rigorous analysis of performance and accuracy, we provide results from elaborate simulations for a wide range of system parameters, demonstrating the correctness and efficiency of the proposed algorithms under various scenarios.     

一种新的RFID标签数目估算方法

动态帧时隙ALOHA反碰撞算法中帧长度调整的关键在于对阅读器读写范围内标签数目的估算。通过模拟帧时隙ALOHA算法得到了不同帧长度时标签数目与碰撞时隙数目的关系曲线。创建了碰撞时隙中的平均标签数目e和碰撞时隙所占比例P_C之间关系的数学表达式,该表达式对所有的帧长度都适用。在此基础上提出了一种新的RFID标签数目估算方法。该方法计算量小,不需要预先建立和存储查找表,有利于提高RFID系统的实时响应速度和降低硬件成本。 MATLAB仿真表明,提出的标签数目估算方法比现有的方法估算准确度有较大提高。