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.     

Optimal scheduling-based RFID reader-to-reader collision avoidance method using artificial immune system

In radio frequency identification (RFID) systems, communication signals from one desired reader is subject to interference from the other adjacent readers operating at the same time, so the reader-to-reader collision problem occurs. Many RFID reader collision avoidance methods have been developed, such as coverage-based methods, control mechanism-based methods and scheduling-based methods. In the scheduling-based methods, how to allocate frequency channels and time slots for the RFID reader network is emphasized. In this case, the RFID reader collision avoidance problem is transferred as an optimal scheduling problem, which can be solved by analytical methods and intelligent algorithms. Artificial Immune System (AIS) optimization is an emerging heuristic method derived from the human immune system. Due to its powerful global searching capability, AIS has been widely applied to scientific and engineering problems. This paper attempts to formulate the reader-to-reader collision problem (R2RCP) and its scheduling-based reader-to-reader collision avoidance model (R2RCAM), and proposes an improved AIS optimization for resource allocation (RA-AIS) in R2RCAM. Within the proposed RA-AIS optimization, the candidate antibody is constructed by using frequency channels and time slots, and in the mutation phase, the candidate antibody evolves dynamically according to its corresponding readers’ interfering power. The proposed RA-AIS optimization is examined on a series of numerical experiments to evaluate the effects of time slots, frequency channels, and transmitting power. Moreover, a group of comparative experiments are also arranged. The experimental results demonstrate that the proposed RA-AIS optimization is an effective method for R2RCAM, and performs better in searching the maximum interrogation area than other algorithms, such as random method (RM), genetic algorithm (GA), particle swarm optimization (PSO) and the canonical artificial immune system optimization (opt-aiNet).     

RFID数据流上多目标复杂事件检测

已有的RFID复杂事件处理技术主要关注于单个RFID对象的复杂事件检测和优化技术.实际上,很多RFID应用中往往需要同时检测多个同类型关联目标的复杂事件序列.研究了多个关联的RFID对象的复杂事件处理问题.通过扩展的事件语言和算子的语义以支持同类型多个RFID目标复杂事件查询的定义.通过模式的变换规则,将RFID应用中存在的各种非线性多目标复杂事件模式转换成线性模式,以便各种多目标模式在一个统一的框架下检测.提出了基于自动机NFA\\-{b2}的多目标复杂事件检测模型和多目标复杂事件检测算法.通过在多目标检测算法中使用关键节点下压和同位置约束置后优化策略,大大减少了单个类型上无用实例的数目和不同类型间模式匹配的搜索空间.与SASE算法的实验比较表明算法的正确性和高效性.     

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.     

Load balancing in large-scale RFID systems

A radio frequency identifier (RFID) system consists of inexpensive, uniquely-identifiable tags that are mounted on physical objects, and readers that track these tags (and hence these physical objects) through RF communication. For many performance measures in large-scale RFID systems, the set of tags to be monitored needs to be properly balanced among all readers. In this paper we, therefore, address this load balancing problem for readers — how should a given set of tags be assigned to readers such that the cost for monitoring tags across the different readers is balanced, while guaranteeing that each tag is monitored by at least one reader. We first present centralized solutions to two different variants of this load balancing problem: (i) min–max cost assignment (MCA), and (ii) min–max tag count assignment (MTA). We show that MCA, the generalized variant of the load balancing problem, is NP-hard and hence present a 2-approximation algorithm for it. We next present an optimal centralized solution for MTA, an important specialized variant of the problem. Subsequently, we present a localized distributed algorithm that is probabilistic in nature and closely matches the performance of the centralized algorithms. Finally we present detailed simulation results that illustrate the performance of the localized distributed approach, how it compares with the centralized optimal and near-optimal solutions, and how it adapts the solution with changes in tag distribution and reader topology. Our results demonstrate that our schemes achieve very good performance even in highly dynamic large-scale RFID systems.     

Optimal Period of Workload Redistribution for Dynamic Bulk Synchronous Computations in Heterogeneous Computing Systems

In dynamic bulk synchronous computations, processors may change their workloads from phase to phase. Such workload change will possibly increase the duration of a phase and the overall parallel execution time. Therefore, it is necessary to redistribute workload at runtime to reduce the parallel time. However, such workload redistribution at runtime can be expensive and the overhead of frequent runtime workload redistribution may exceed the benefit of workload redistribution and balancing. The problem of finding the optimal period of runtime workload redistribution for dynamic bulk synchronous computations is motivated by the combined consideration of parallel execution time and system overhead for workload redistribution and balancing. We develop an analytical method to solve the problem in heterogeneous computing systems. We also demonstrate numerical data of the analytical method and simulation results that verify the analytical data.     

移动机器人室内无源RFID定位方法及实现

为提高室内机器人的定位精度,提出一种无源RFID的室内移动机器人定位方法。RFID标签采用蜂窝排布模型,提高读卡器检测效率;对RSSI定位方法按工程实际提出了校正模型,同时针对多信标定位最优值寻优的问题,引入微分进化算法对位置坐标进行求解;在[(4×4) m2]场地内进行了验证,实验结果表明,较极大似然估计具有更高的定位精度,绝对误差小于10.16 cm;较标准遗传算法能够在更少的迭代步内获得最优值,平均节省37%的计算时间。     

分布式RFID复杂事件处理关键技术的研究

RFID复杂事件处理是RFID应用的一项关键技术。传统的集中式处理方式无法及时处理海量的实时RFID数据流,制约着RFID应用的大规模部署。研究了分布式RFID复杂事件处理技术。提出了分层的树形任务结构;建立基于效率-成本和延迟的模型来评价任务分解方案;设计动态规划算法来求解最优分解方案;实验验证了分布式处理的高效性和提出模型和算法的正确性。     

一种基于动态带宽分配的企业服务总线模型

现有的企业服务总线(ESB)系统在重载时会发生业务拥塞并导致服务质量下降。针对该问题,提出一种基于动态带宽分配的ESB模型。将总线上运行的各个业务流分为3种级别的业务类型。系统在运行时按业务类型优先级为业务流量动态分配带宽,以保证高优先级业务的带宽需求,减少拥塞的发生,提高系统的吞吐能力。实验结果证明了该模型的有效性。     

Energy-efficient real-time scheduling for two-type heterogeneous multiprocessors

We propose three novel mathematical optimization formulations that solve the same two-type heterogeneous multiprocessor scheduling problem for a real-time taskset with hard constraints. Our formulations are based on a global scheduling scheme and a fluid model. The first formulation is a mixed-integer nonlinear program, since the scheduling problem is intuitively considered as an assignment problem. However, by changing the scheduling problem to first determine a task workload partition and then to find the execution order of all tasks, the computation time can be significantly reduced. Specifically, the workload partitioning problem can be formulated as a continuous nonlinear program for a system with continuous operating frequency, and as a continuous linear program for a practical system with a discrete speed level set. The latter problem can therefore be solved by an interior point method to any accuracy in polynomial time. The task ordering problem can be solved by an algorithm with a complexity that is linear in the total number of tasks. The work is evaluated against existing global energy/feasibility optimal workload allocation formulations. The results illustrate that our algorithms are both feasibility optimal and energy optimal for both implicit and constrained deadline tasksets. Specifically, our algorithm can achieve up to 40% energy saving for some simulated tasksets with constrained deadlines. The benefit of our formulation compared with existing work is that our algorithms can solve a more general class of scheduling problems due to incorporating a scheduling dynamic model in the formulations and allowing for a time-varying speed profile.     

Fair multi-agent task allocation for large datasets analysis

MapReduce is a design pattern for processing large datasets distributed on a cluster. Its performances are linked to the data structure and the runtime environment. Indeed, data skew can yield an unfair task allocation, but even when the initial allocation produced by the partition function is well balanced, an unfair allocation can occur during the reduce phase due to the heterogeneous performance of nodes. For these reasons, we propose an adaptive multi-agent system. In our approach, the reducer agents interact during the job and the task reallocation is based on negotiation in order to decrease the workload of the most loaded reducer and so the runtime. In this paper, we propose and evaluate two negotiation strategies. Finally, we experiment our multi-agent system with real-world datasets over heterogeneous runtime environment.     

实时企业服务总线的研究与设计

针对现有企业服务总线在不同类型业务流竞争有限带宽资源时产生系统拥塞的问题,提出一种实时企业服务总线模型.对JBI标准进行了改进,增加了业务优先级和业务时间约束的语义,并加入流量控制和带宽分配组件.系统运行时能根据不同类型业务流带宽需求,按照业务类型优先级从高到低动态分配服务总线的业务流量带宽.仿真实验结果表明,该方法可以保证高优先级业务的带宽需求,减少因业务拥塞导致的服务质量下降,并进而提升系统整体的吞吐能力.     

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.     

A heuristic approach for allocation of data to RFID tags: A data allocation knapsack problem (DAKP)

Durable products and their components are increasingly being equipped with one of several forms of automatic identification technology such as radio frequency identification (RFID). This technology enables data collection, storage, and transmission of product information throughout its life cycle. Ideally all available relevant information could be stored on RFID tags with new information being added to the tags as it becomes available. However, because of the finite memory capacity of RFID tags along with the magnitude of potential lifecycle data, users need to be more selective in data allocation. In this research, the data allocation problem is modeled as a variant of the nonlinear knapsack problem. The objective is to determine the number of items to place on the tag such that the value of the “unexplained” data left off the tag is minimized. A binary encoded genetic algorithm is proposed and an extensive computational study is performed to illustrate the effectiveness of this approach. Additionally, we discuss some properties of the optimal solution which can be effective in solving more difficult problem instances.     

分布式RFID复杂事件处理技术的研究

目前RFID复杂事件处理技术的研究主要针对集中式的处理。集中式RFID复杂事件处理技术对于海量RFID数据的处理具有很多局限性,主要表现为网络通讯代价高和处理效率低。针对集中式RFID复杂事件处理存在的问题,本文研究了分布式环境下RFID复杂事件处理的关键算法,采用一种Pull(抽取)类型的数据通讯模型来降低通讯代价,在此基础上提出了两种分布式的RFID复杂事件处理算法。实验结果表明,本文提出的分布式RFID复杂事件处理算法比集中式复杂事件处理算法更有效。     

面向制造业的RFID复杂事件处理

在自动数据采集中,如何维持无线射频识别(RFID)技术对海量数据的处理效率极为重要。针对RFID数据的特点以及目前RFID数据处理方法的不足,提出一种基于复杂事件处理的RFID数据处理模型,并提供相关的定义,阐述其功能模块及解决方案。该模型实现了从大量的RFID原始数据中提取出对应用程序有意义的事件。最后以面向制造业的RFID应用为例对基于复杂事件处理技术的RFID数据处理模型进行了研究并说明了其应用优势。     

基于多级数据处理的RFID中间件开发

针对大规模无线射频识别(RFID)应用中产生的海量标签信息处理问题,设计一种基于多级数据处理的嵌入式RFID中间件系统。该系统包含数据采集和数据处理2个子系统,对海量标签信息进行分层过滤、分类、重组等操作,从中获得有价值的信息与事件,并以多种形式提供给用户。仿真实验结果表明,该系统可以在一定程度上提高数据处理的效率和准确性,进而提升大规模RFID应用的性能。     

Equilateral triangular patch antenna for UHF RFID applications

This article proposes an equilateral triangule‐shaped patch antenna for radio frequency identification (RFID) applications in the 900 MHz (902–928 MHz) ultra high frequency (UHF) band. To achieve optimal impedance matching and 10‐dB operating bandwidth at the desired band, the L‐shaped probe‐feed technique was used as the feeding structure of the proposed antenna. Furthermore, a near semicircular notch was also loaded into the patch so that good circularly polarized (CP) radiation can be generated from the proposed patch antenna. By simply shifting the position or radius of this notch, the CP frequency can be varied with ease. Here, 10‐dB impedance bandwidth and 3‐dB axial ratio bandwidth of 25 and 3% were achieved. Furthermore, stable gain variation of approximately 6 dBi was also exhibited across the RFID UHF band. © 2014 Wiley Periodicals, Inc. Int J RF and Microwave CAE 24:580–586, 2014.     

车联网中RFID模型

RFID模型是车联网仿真的基础和核心模型之一. 目前交通仿真模型不能满足车联网无线通信及协同交互等方面的需求、且缺少RFID模型. 为此, 建立了RFID系统的读写器和电子标签模型. 给出了读写器Agent和电子标签Agent结构及实现. 根据自动机理论, 建立了读写器、电子标签和主机之间通信时异构通信协议数据帧格式的有限状态机模型, 解决了异构数据帧统一处理问题. 作为模型应用和验证实例, 基于VC++ 2010平台, 开发了RFID交通数据采集读写器优化布设仿真软件. 结果表明, RFID模型较好地逼     

基于CEP的RFID数据处理模型研究

RFID数据处理技术是近年来射频识别技术应用研究的热点。本文针对RFID数据的特点以及目前RFID数据处理技术的不足,探讨了将复杂事件处理（CEP）技术应用于RFID数据处理的具体技术问题,提出一种基于CEP的RFID数据处理模型,重点对高速缓存cache、事件滤波器以及复杂事件构建器等关键技术进行了研究,对该处理模型的应用进行了讨论。