Premium
Optimal solution for data collision avoidance in radio frequency identification networks
Author(s) -
Nguyen NgocTu,
Leu Ming C.,
Zeadally Sherali,
Liu BingHong,
Chu ShaoI
Publication year - 2018
Publication title -
internet technology letters
Language(s) - English
Resource type - Journals
ISSN - 2476-1508
DOI - 10.1002/itl2.49
Subject(s) - radio frequency identification , computer science , collision problem , collision , identification (biology) , set (abstract data type) , graph , dynamic programming , range (aeronautics) , collision avoidance , linear programming , algorithm , theoretical computer science , computer security , botany , materials science , composite material , biology , programming language
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.