Time slot allocation apparatus and method for preventing collisions between time slots in TDMA-based RFID network

• US 8,325,017 B2
• Filed: 11/16/2007
• Issued: 12/04/2012
• Est. Priority Date: 09/21/2007
• Status: Expired due to Fees

• Current Assignee: Geun-Sik Jo
• Original Assignee: INHA Industry Partnership Institute
• Inventors: Jo, Geun Sik, Park, Seung Bo, Yu, Young Hoon
• Primary Examiner(s): Zimmerman, Brian
• Assistant Examiner(s): Nguyen, An T
• Application Number:
  US12/064,739
• Publication Number:
  US 20100176926A1
• Time in Patent Office: 1,845 Days
• Field of Search: 340/1.1, 340/10.1, 340/10.2, 340/3.41, 340/572.1, 340/10, 340/670, 340/584, 370/321, 370/458
• US Class Current: 340/10.2
• CPC Class Codes: H04W 72/541 using the level of interference
• CPC Class Codes: H04W 72/563 of the wireless resources

Abstract

The present invention relates to a time slot allocation apparatus and method for preventing collisions between time slots in a TDMA-based RFID network. The time slot allocation apparatus allocates time slots, obtained by dividing a same frequency band into unit time slots, to RFID readers for reading identification codes of RFID tags (10) in the TDMA-based RFID network. A time slot allocation device (33a) allocates time slots required for communication with the RFID tags to a plurality of RFID readers (20) provided in the RFID network. A collision prevention device (33b) performs control such that the time slot allocation device allocates time slots to the plurality of RFID readers while distributing different and non-successive time slots to adjacent RFID readers, thus preventing collisions from occurring between time slots allocated to the RFID readers.

Claims

1. A time slot allocation apparatus for preventing collisions between time slots in a Time Division Multiple Access (TDMA)-based Radio Frequency Identification (RFID) network, the apparatus allocating time slots, obtained by dividing a same frequency band into unit time slots, to RFID readers for reading identification codes of RFID tags in the TDMA-based RFID network, comprising:

a time slot allocation device configured to allocate time slots required for communication with the RFID tags to a plurality of RFID readers provided in the RFID network; and

a collision prevention device configured to perform control such that the time slot allocation device allocates time slots to the plurality of RFID readers while distributing different and non-sequential time slots to adjacent RFID readers, thus preventing collisions from occurring between time slots allocated to the RFID readers,

wherein the collision prevention device perform the control by using a first constraint, a second constraint and a third constraint,

wherein the first constraint indicates that at least two RFID readers, which are sets of variables having time slots, don'"'"'t use the same time slot as long as the at least two RFID readers are not spaced sufficiently far apart among the at least two RFID readers,

wherein the second constraint indicates that non-sequential time slots are selected among time slots allocated to adjacent RFID readers,

wherein the third constraint indicates that time slots are selected non-sequentially but as adjacently as possible among time slots allocated to adjacent RFID readers, and

wherein the second constraint is given in the following;

|ts_i−

ts_j|≧

d(d≅

2)

where ts_i represents an arbitrary time slot allocated to an arbitrary RFID reader of the at least two RFID readers, ts_j represents a different time slot from the time slot ts_i that is allocated to another of the at least two RFID readers adjacent to the arbitrary RFID reader, and is non-sequential to the time slot ts_i, and d represents the number of time slots interposed between allocated time slots ts_i and ts_j.

2. The time slot allocation apparatus according to claim 1, wherein the collision prevention device is configured to perform control such that three to six time slots are interposed between the time slots allocated to the adjacent RFID readers in order to read each moving RFID tag.

3. The time slot allocation apparatus according to claim 1, wherein the collision prevention device is configured to perform control such that one to four time slots are interposed between time slots allocated to the adjacent RFID readers in order to eliminate temporal interference between the time slots.

4. The time slot allocation apparatus according to claim 1, wherein the collision prevention device is configured to enable a number of time slots allocated to all RFID readers provided in the RFID network to be minimized.

5. The time slot allocation apparatus according to claim 1, wherein both the time slot allocation device and the collision prevention device are provided in an RFID interface for connection to the RFID readers.

6. The time slot allocation apparatus according to claim 5, wherein the RFID interface is configured to control the RFID readers and collect identification codes of the RFID tags read by the RFID readers.

7. The time slot allocation apparatus according to claim 1, wherein each of the time slot allocation device and the collision prevention device further comprises an RFID reader management unit configured to allocate time slots to respective RFID readers using information about the RFID readers, which is input through an RFID interface for connection to the RFID readers.

8. The time slot allocation apparatus according to claim 7, wherein the RFID interface is configured to connect the RFID readers to respective components included in RFID middleware in which the RFID reader management unit is included.

9. The time slot allocation apparatus according to claim 8, wherein the RFID middleware comprises:

the RFID interface provided to connect the RFID readers to respective components included in the RFID middleware;

the RFID reader management unit connected through the RFID interface and configured to allocate time slots for communication to the RFID readers to prevent collisions from occurring between the time slots;

an RFID tag information management unit connected through the RFID interface and configured to collect and manage the identification codes of the RFID tags read by the RFID readers; and

an application interface provided to connect the RFID middleware to a central server for controlling the RFID network.

10. The time slot allocation apparatus according to claim 1, wherein no RFID reader is interposed between the arbitrary RFID reader and the RFID reader adjacent to the arbitrary RFID reader.

11. A time slot allocation method for preventing collisions between time slots in a Time Division Multiple Access (TDMA)-based Radio Frequency Identification (RFID) network, the method allocating time slots, obtained by dividing a same frequency band into unit time slots, to RFID readers for reading identification codes of RFID tags in the TDMA-based RFID network, comprising:

(a) allocating, using a time slot allocation device that allocates the time slots for communication with the RFID tags to a plurality of RFID readers provided in the RFID network, an arbitrary time slot to an arbitrary RFID reader; and

(b) allocating a time slot to an RFID reader adjacent to the arbitrary RFID reader using a collision prevention device to allocate the time slot that is different from the arbitrary time slot and is non-sequential to the arbitrary time slot to the adjacent RFID reader in order to eliminate temporal interference between respective RFID readers provided in the RFID network,

wherein allocating time slots to the arbitrary RFID reader and the adjacent RFID reader comprises allocating so that a number of time slots is interposed between the time slots allocated to the arbitrary RFID reader and the adjacent RFID reader in order to read a moving RFID tag,

wherein allocating time slots to the arbitrary RFID reader and the adjacent RFID reader further comprises using a first constraint, a second constraint and a third constraint,

wherein the first constraint indicates that at least two RFID readers do not use the same time slot as long as the at least two RFID readers are not spaced sufficiently far apart among the at least two RFID readers,

wherein the second constraint indicates that non-sequential time slots are selected among time slots allocated to adjacent RFID readers,

wherein the third constraint indicates that time slots are selected non-sequential but as adjacently as possible among time slots allocated to adjacent RFID readers, and

wherein the second constraint is given in the following;

|ts_i−

ts_j|≧

d(d≅

2)

where ts_i represents the arbitrary time slot allocated to the arbitrary RFID reader, ts_j represents the time slot allocated to the adjacent RFID reader, and d represents the number of time slots interposed between allocated time slots ts_i and ts_j.

12. The time slot allocation method according to claim 11, wherein the number of time slots is 3 to 6.

13. The time slot allocation method according to claim 11, further comprising repeating (a) and (b) until time slots are allocated to all RFID readers provided in the RFID network.

14. The time slot allocation method according to claim 11, wherein the collision prevention device enables the number of time slots allocated to all RFID readers provided in the RFID network to be minimized.

15. The time slot allocation method according to claim 11, wherein the non-successive time slot is a time slot implemented such that two to four time slots are interposed between the time slots allocated to the arbitrary RFID reader and the adjacent RFID reader in order to prevent temporal interference between the allocated time slots.