Coding for tag collision recovery

It has been recently observed that some information can be extracted from the received signal by the reader when the tag collision happens. Using the radio cross section (RCS) technique one can determine how many tags are backscattering simultaneously. Motivated by this technique we introduce the new notion of singulation code. In a singulation code, any two collection of codewords, of size up to some number s, have distinct vector-sums. We propose a new protocol for tag singulation problem using the singulation codes. Upper and lower bounds on the size of singulation codes are provided. It is shown that there exists families of singulation codes that guarantee any positive throughput, asymptotically, using the singulation coding protocol. Two explicit constructions of singulation codes, with low complexity encoding and decoding algorithms, are proposed. It is shown that these constructions are feasible to be implemented in RFID tags. The singulation protocol with these explicit constructions is compared with the randomized ALOHA based algorithm. It is shown that the time required for the tag identification with the proposed protocol is reduced by a factor of log s comparing to the randomized ALOHA based algorithm, where s is the number of tags to be identified. Other advantages of the proposed protocol are also discussed.