A Maximum-Weight-Independent-Set-Based Algorithm for Reader-Coverage Collision Avoidance Arrangement in RFID Networks

Bing Hong Liu, Ngoc Tu Nguyen, Van Trung Pham, Yu Huan Yeh

Research output: Contribution to journalArticlepeer-review

47 Scopus citations


Radio frequency identification (RFID) systems have been widely developed and applied in identification applications. In RFID systems, a tag can be read by a reader when the tag is within the reader's interrogation range. Reader deployment has received a great deal of attention for providing a certain service quality. Many studies have addressed deploying/activating readers such that all the tags in a field can be read. However, in a practical environment, tags cannot be read due to collisions. In addition, the number of tags read by a reader is often limited due to the constraints of processing time and link layer protocols. This motivated us to study the problem of activating readers and adjusting their interrogation ranges to cover maximum tags without collisions subject to the limited number of tags read by a reader, termed the reader-coverage collision avoidance arrangement (RCCAA) problem. In this paper, the RCCAA problem is shown to be NP-complete. In addition, an approximation algorithm, termed the maximum-weight-independent-set-based algorithm (MWISBA), is proposed for the RCCAA problem. The simulation results show that the MWISBA provides good performance for the RCCAA problem.

Original languageEnglish (US)
Article number7321778
Pages (from-to)1342-1350
Number of pages9
JournalIEEE Sensors Journal
Issue number5
StatePublished - Mar 1 2016

Bibliographical note

Funding Information:
This work was supported by the Ministry of Science and Technology under Grant MOST 103-2221-E-151-002 and Grant MOST 104-2221-E-151-014.

Publisher Copyright:
© 2015 IEEE.


  • NP-complete
  • Radio frequency identification
  • approximation algorithm
  • collision avoidance


Dive into the research topics of 'A Maximum-Weight-Independent-Set-Based Algorithm for Reader-Coverage Collision Avoidance Arrangement in RFID Networks'. Together they form a unique fingerprint.

Cite this