Optimal Solution for Data Collision Avoidance in Radio Frequency Identification Networks


When data collisions happen in radio frequency identification (RFID) networks, inaccurate tag's information or the communication between the RFID reader and the RFID tag occur. Although recent technological advances have improved the inquiry capacity performance of RFID readers, the performance of RFID networks can still be affected by collisions. We propose a novel solution that helps select RFID readers which have the appropriate interrogation range to enable the highest number of tags to be read without collisions (often referred to as the reader‐tag‐data collision avoidance [RTDCA] problem). To solve the RTDCA problem, we introduce a relative collision graph to transform the original problem into one that involves finding the maximum weight independent set. We then formulate the RTDCA problem using a mathematical model. To solve the RTDCA problem by using a linear programming model requires an exponential number of variables which cannot be solved in polynomial time. Our proposed solution makes use of dynamic programming with path decomposition to determine the optimal number of RFID tags that can be read without data collisions.


Mechanical and Aerospace Engineering

Research Center/Lab(s)

Intelligent Systems Center


May/June 2018 issue

Keywords and Phrases

Collision Avoidance; Mathematical Programming; Maximum Number of Read Tags; Optimal Solution; Radio Frequency Identification

International Standard Serial Number (ISSN)


Document Type

Article - Journal

Document Version


File Type





© 2005 John Wiley & Sons, All rights reserved.

Publication Date

01 May 2018