CN103679092B - RFID Anti-collision Algorithm Based on Feedback Mechanism - Google Patents

Abstract

The present invention discloses a kind of RFID anti-collision algorithm based on feedback mechanism.This algorithm steps includes 1): label is randomly divided into 16 groups, and the label that group number is 0 is identified by read write line, and group number is all subtracted one by remaining group number label more than 0, then starts the next round identification to new 0 group of label.2): in group, use a point dimension recognizer.Being divided into one-dimensional by every for tag ID four, during the one-dimensional data of inquiry tag, number and position relationship according to 1 determine the value of enumerator, obtain label prefix, according to the corresponding label of label prefix identification by the value of detection collision situation sum counter.3): the identification information of 16 groups of labels is fed back, skip label is re-started packet, then use based on the random algorithm identifying that label ID information is fed back in group.The present invention accelerates label and produces processing speed when colliding, and decreases recognition time, is fed back by identified label information, improves the discrimination of label.

Description

RFID Anti-collision Algorithm Based on Feedback Mechanism

technical field

The invention belongs to the technical field of RFID (Radio Frequency Identification). It relates to an RFID anti-collision algorithm based on feedback mechanism under capture effect.

Background technique

Radio Frequency Identification (RFID) is an automatic identification technology widely used in logistics, military, transportation, medicine and other fields. A basic RFID system mainly includes readers, tags and antennas. Each tag has a unique ID number, and the tag communicates with the reader through radio frequency signals. All tags in the same RFID system work on the same channel. When there are multiple tags within the range of the reader, and there may be multiple tags communicating with the reader at the same time, a collision will occur between the tags , the reader cannot receive all the information at the same time, resulting in data loss, that is, a collision between tags occurs.

There are two main types of existing tag anti-collision algorithms: ALOHA-based random algorithms and tree-based deterministic algorithms. When multiple tags within the range of the reader respond, the tag closer to the reader may cover the signals of other tags because of its stronger signal, resulting in a capture effect. The ALOHA-based random algorithm sends data to the reader by randomly selecting time slots. Relatively speaking, the reliability of the entire system cannot be guaranteed, and the utilization rate of the channel is relatively low. The tree-based algorithm solves the conflict problem in labels in an orderly manner by dividing the conflicting nodes into two subsets of 0 and 1. However, a large number of collisions will be generated in the early stage of the recognition stage, and the handling of the capture effect is relatively poor. In practice, due to the phenomenon of missing tags caused by capture effect and channel interference, the existing two algorithms obviously cannot recognize all tags.

Contents of the invention

The main purpose of the present invention is to provide an RFID anti-collision algorithm based on a feedback mechanism under the capture effect to overcome the traditional anti-collision method with poor reliability and low channel utilization. Due to a large number of collisions, the distance between the tag and the reader is different etc. resulting in poor handling of the capture effect and inability to identify all tags.

The solution of the present invention is achieved by: a feedback mechanism-based RFID anti-collision algorithm, the algorithm stipulates that the tag object includes a random number generator TC, a counter GC, and a tag group number memory TG, and the reader object includes the current query dimension Number RN, group number GN, the algorithm steps also include:

Step 1) Tag grouping: the reader sends a Req(GN) command, initially GN=15, the tag uses the random number generator TC inside the tag to generate a random number between 0 and GN, and then saves the generated random number In the tag group number memory TG, the value of TG is the group number of the tag, and the tags are randomly divided into GN+1 groups, that is, 16 groups. After the identification of the group ", the remaining tags whose group numbers are greater than "0" will have their group numbers reduced by one, and then start the next round of identification of the new "0" group tags.

Step 2) Fractal dimension recognition within the tag group: first, the reader initializes the current query dimension RN, sends the query command Req(X, RN), assigns a value to GC according to the corresponding relationship between the tag prefix and the counter GC, and then the reader receives the data GC value, send the query command Request(X, RN, gc), and finally the reader detects the collision, obtains the command parameters according to the judgment relationship between the data collision and the tag prefix, and judges the stack.

Step 3) Tag feedback identification: first, the reader calculates [M/V], sets GN=[M/V] -1 and feeds back to the tag, and then the tag generates a random number between 0-GN as the tag group number, Stored in the tag group number memory TG, select the tag whose group number is 0 to respond, and finally detect the collision situation, and the algorithm ends.

As a further explanation of the present invention, the ID number of the tag is composed of binary bits that are not "0" or "1", and each tag divides its ID into one dimension every four binary bits from left to right.

As a further improvement of the present invention, the identification process steps of step 2) fractal dimension identification within the tag group include:

Step 2-1, the reader initializes the current query dimension RN=1, the query prefix X=null, when X is null, the tags with the group number 0 are all corresponding.

Step 2-2, send the query command Req(X, RN), inform the tag of RN, X, the tag detects the number and positional relationship of "1" in its RN, and assigns a value to GC according to the corresponding relationship between the tag prefix and the counter GC, And feed back the information sequence representing the GC value to the reader.

Step 2-3, the reader receives the data GC value, pushes the learned GC value, X, and RN into the stack, and obtains the top element of the stack.

Step 2-4, send the query command Request(X, RN, gc) to request the label whose prefix matches X and GC=gc to return the data of dimension RN and beyond.

Step 2-5: The reader detects the collision. If there is a collision and the RN is not the last dimension, then according to the judgment relationship between the data collision and the label prefix in the query dimension, the currently existing label prefix is obtained and the prefix, the current GC Value and query dimension RN=RN+1 are pushed onto the stack, get the top element of the stack, and return to step 2-2; if there is no collision or RN is the last dimension, directly identify the tag and mask it, then go to step 2-6.

Step 2-6, judge the stack, if the stack is empty, go to step 2-7; if it is not empty, adopt the back-off strategy, get the top element from the stack, and return to step 2-4.

Step 2-7, if the stack is empty, the group numbers of the remaining labels greater than "0" will be reduced by one, and the group number "0" of the missed-read label with the group number "0" will remain unchanged, and then the new If all the tag group numbers are "0" and the stack is empty, then end step 2).

As a further explanation of the present invention, the identification process steps of step 3) label feedback identification include:

Step 3-1, the reader uses the identified 16 groups of tag information to give feedback, find the maximum number M and the average number V of the identified tags in the 16 groups, and find [M/V], let GN=[M/ V] -1, send command Req(GN).

In step 3-2, the tag generates a random number between 0-[GN] as the tag group number and stores it in the tag group number memory TG, and the reader selects the tag whose group number is "0" to respond.

In step 3-3, the tag whose group number is "0" generates random numbers "0" and "1", and selects the tag whose random number is "0" to respond.

Step 3-4: Detect the collision. If there is a collision, the tag whose random number is not "0" will add one to its random number, and the tag with the random number "0" will regenerate the random numbers "0" and "1", and return Step 3-4, re-detect the collision situation; if only one tag responds, identify the tag and shield it, then feed back its ID to other tags, and go to step 3-5; if no tag responds, the reader requires no recognition The tag returns its random number, detects the received data, and if there is a tag response, go to step 3-5; if no tag returns its random number, go to step 3-6.

In step 3-5, the label whose random number is not "0" subtracts one from the random number, and returns to step 3-4.

Step 3-6, if the group number of all tags is "0", the entire identification process will end; otherwise, the group number of the tag whose group number is not "0" will be reduced by one, and then select the tag whose group number is "0" to respond and return to step 3- 3.

As a further limitation of the present invention, the corresponding relationship between the label prefix and the counter GC in step 2) is that when GC=1, the label prefix is 0001 0010 0100 1000; when GC=2, the label prefix is 1010 1001 1100; GC= When 3, the label prefix is 0111 1011 1110 1101; when GC=4, the label prefix is 0000 1111; when GC=5, the label prefix is 00110110 0101.

As a further limitation of the present invention, the judgment relationship between the data collision and the label prefix in the step 2) is:

In GC=1, only one binary bit is 1. If a certain bit collides, the collision position is 1, and the other positions are 0, and the label prefixes existing in the current query dimension are sequentially obtained.

In GC=3, only one binary bit is 0. If a certain bit collides, the collision position is 0, and the other positions are 1, and the label prefixes existing in the current query dimension are obtained in turn.

In GC=4, there are only labels whose prefixes are 0000 or 1111 in the current query dimension. If a collision occurs, it means that 0000 and 1111 exist at the same time.

In GC=2, the number of 1 is 2, but the leftmost bit is 1. If a certain bit collides, the corresponding collision position is set to 1, and the other positions are 0, and the label prefixes existing in the current query dimension are obtained in turn. .

In GC=5, the number of 1 is 2, but the leftmost bit is 0. If a certain bit collides, the corresponding collision position is set to 0, and the other positions are set to 1, and the label prefixes existing in the current query dimension are sequentially obtained.

The present invention has good effects and substantial progress: it reduces the excessive collisions at the initial stage of identification, and speeds up the processing speed when labels collide by performing fractal recognition on tags. Under the same conditions, the processing speed when tags collide The average increase is about 25%, and the recognition time is reduced by about 28% on average, which greatly reduces the recognition time; at the same time, the problem of missed reading of tags caused by capture effect and channel interference is considered, and the recognized tag information is fed back, and the recognition rate is improved on average. To more than 99%, greatly improving the recognition rate of the label.

Description of drawings

Fig. 1. The algorithm flow chart of tag grouping and fractal dimension recognition step within tag group in the present invention.

Fig. 2. Algorithm flow chart of tag feedback identification steps in the present invention.

detailed description

The present invention is described below in conjunction with the embodiments and accompanying drawings, and these descriptions are not intended to further limit the content of the present invention. The algorithm stipulates in the embodiment that the tag object includes a random number generator TC, a counter GC, and a tag group number storage TG, and the reader/writer object includes the current query dimension RN and the group number GN.

Example 1

(1) Step 1) Tag grouping: In order to reduce a large number of collisions caused by too many tags in the early stage of recognition, the tags are first randomly grouped. In the present invention, the reader sends the command Req(GN), GN=15, the tag uses the random number generator TC in the tag to generate a random number between 0 and 15, and then saves the generated random number in the tag group number In the memory TG, the value of TG is the group number where the tag is located. The reader selects the tag whose group number is 0 for identification.

(2) Step 2) Fractal dimension recognition within the label group: Use the fractal dimension recognition algorithm within the group. The specific process is shown in Figure 1, and the algorithm is divided into the following steps:

1) The tag ID consists of binary bits that are either 0 or 1, uniquely identifying a tag, and the left side is the high bit. First, the tag divides its ID into one dimension every four binary bits from the high bit to the low bit, so the tag can be divided into several dimensions, such as 1, 2, and 3 dimensions. For example, if the tag ID is 0100110001111110, it can be divided into four dimensions, where the 1st, 2nd, 3rd, and 4th dimensions are 0100, 1100, 0111, and 1110 respectively.

2) The reader initializes the current query dimension RN=1, and the query prefix X=null. When X=null, all tags whose group number is 0 respond.

3) Send the query command Req(X, RN) to inform the tag of X, RN; the reader is based on the number and position relationship of 1 in the RN dimension, and the corresponding relationship between the tag prefix in the query dimension and the counter GC (such as Table 1) Assign a value to the GC and feed back the information sequence representing the GC value to the reader.

① The relationship between the label prefix in the query dimension and GC is as follows: For example, if the RNth dimension data of the current query label, the number of 1s in the RNth dimension of the label is 1 and 3 respectively, then the corresponding GCs are 1 and 3 respectively; The number is 0 or 4, then GC=4; the number of 1 is 2 and the highest bit is 1, then GC=2; the number of 1 is 2 and the highest bit is 0, then GC=5.

②The rules for the tag to send the GC value to the reader are as follows: the tag expresses the GC value in binary with a length of 5, and uses the position of 1 to represent the GC value. If the tag's GC=4, the data sent by the tag is 01000.

Table 1. Correspondence between label prefixes in the query dimension and counter GC

GC=1 GC=2 GC=3 GC=4 GC=5 label prefix 0001 0010 0100 1000 1010 1001 1100 0111 1011 1110 1101 0000 1111 0011 0110 0101

4) The reader/writer receives the data, pushes the existing GC value, X, and RN into the stack, and obtains the top element of the stack.

5) Send the query command Request(X, RN, gc), requesting that the prefix matches X and the label with GC=gc returns the data of its RNth dimension and beyond; if X=0100, gc=3, RN=1, then It is required that the tag whose tag prefix is 0100 and whose counter GC=3 returns the data of the first dimension and beyond.

6) The reader detects the collision situation. If a collision occurs and RN is not the last dimension, then according to the judgment relationship between the data collision of the query dimension and the label prefix, the currently existing label prefix is obtained and the prefix, current GC value and query dimension RN=RN+1 is pushed into the stack. Get the top element of the stack, return 3); if there is no collision or RN is the last dimension, directly identify the label and mask it, and go to 7).

The judgment relationship between the data collision of the dimension and the label prefix is as follows:

A: In GC=1, only one binary bit is 1, so if a certain bit collides, the collision position is "1", and the other positions are "0", and the label prefixes existing in the current query dimension are sequentially obtained. For example, in GC=1, if the reader detects a collision bit as xxx0, it means that there are prefixes of 1000, 0100, and 0010.

B: Because only one binary bit is "0" in GC=3, if a certain bit collides, the collision position is "0", and the remaining positions are "1", and the tags existing in the current query dimension are obtained in turn prefix. For example, in GC=1, if the reader detects a collision bit as xxx0, it means that there are prefixes of 1000, 0100, and 0010.

C: In GC=4, because there are only labels whose prefixes are 0000 or 1111 in the current query dimension, if a collision occurs, that is, xxxx, it means that 0000 and 1111 exist at the same time.

D: The number of "1" in GC=2 and GC=5 is 2, the difference is that the highest bit is "0" or "1". In GC=2, the highest bit is "1", and because the number of "1" is 2, if a certain bit collides, the corresponding collision position is "1", and the other positions are "0". Get the tag prefixes that exist in the current query dimension in turn. For example, in GC=2, the data received by the reader is 1x0x, and the existing prefixes are 1100 and 1001.

E: In GC=5, the highest bit of the queried dimension is "0", because the number of "1" is 2, so if a certain bit collides, set the corresponding collision position to "0". ", the remaining positions are "1", and the currently existing prefixes are obtained in turn.

7) If the stack is empty, go to 8); if it is not empty, adopt the fallback strategy, get the top element from the stack, and return to 5).

8) If the stack is empty, the group number of the remaining tags greater than 0 will be reduced by one, and the group number "0" will remain unchanged for the tag whose group number is "0" that has been missed, and then the new 0 group tag will be Identify, return 2-2; if all tag group numbers are 0 and the stack is empty, then end the loop.

(3) Step 3) Label feedback identification, the specific process is shown in Figure 2, which specifically includes the following steps:

1) The reader uses the identified 16 groups of tag information to give feedback, and find the maximum number M and average number V of the identified tags in the 16 groups, and find [M/V], let GN=[M/V]- 1 and feedback to the tag, set GN=[M/V] -1, the reader sends the command Req(GN); for example, there are 6 tags that have not been recognized due to the capture effect or channel interference, and the reader finds out The ratio of M to V is 2, then GN=[M/V]-1=1 is fed back to the 6 unrecognized tags.

2) The tag generates a random number between 0 and GN, and stores the random number in TG as the group number, and selects the tag whose group number is 0 to respond; assuming that among the 6 tags, the group numbers of tagA, tagB, and tagC are all is "0", and the group numbers of tagD, tagE, and tagF are "1", then the three tags of tagA, tagB, and tagC will be recognized first.

3) The tag whose group number is 0 generates "0" and "1" random numbers, and selects the tag whose random number is "0" to respond; here tagA, tagB, and tagC generate "0" or "1" random numbers respectively, here Assuming that both tagA and tagB generate a random number "0", and tagC generates a random number "1", then tagA and tagB return their own IDs to the reader at the same time.

4) Detect the collision. If there is a collision, the tag whose random number is not "0" will add 1 to its random number, and the tag whose random number is "0" will regenerate "0" and "1" random numbers, and return 4), Re-detect the collision situation; if only one tag responds, identify the tag and shield it, then feed back its ID to other tags, go to 5); if no tag responds, the reader requires the unrecognized tag to return its random number, and detects For the received data, if there is a tag response, go to step 5); if no tag returns its random number, go to 6); here it is assumed that because tagA is closer to the reader, although the data is transmitted at the same time as tagB, but because tagA The signal of is stronger and covers the signal of tagB, so theoretically there should be a collision, but at this time it becomes a readable time slot. After the reader recognizes the information of tagA and shields it, it feeds back the ID of tagA to other tags. After receiving the feedback signal, tagB finds that its own ID does not match with it, and knows that its own information has been missed.

5) For tags whose random number is not "0", subtract one from the random number and return 4); here, the random number of tagB remains unchanged, the random number of tagC is subtracted by one, and then return to 4), the reader receives the data of tagB and tagC again , to detect collisions. It is assumed here that there is no interference or capture effect, and tagB and tagC collide. Because the random numbers are all "0", the random number "0" or "1" is regenerated. If tagB generates "0" and tagC generates "1", then the next time slot receives the information of tagB and recognizes it. After shielding, the random number of tagC is reduced by one, and then communicates with the reader.

6) If the group number of all tags is "0", the entire identification process will end; otherwise, the tag with a non-zero group number will subtract one from the group number, and then select a tag with a group number of "0" and return 3); here tagD, tagE, After the group number of tagF is reduced by one, the next round of identification of these three tags is started using the same method.

This embodiment reduces the excessive collisions generated at the initial stage of identification. By performing fractal identification on the tags, the processing speed when the tags collide is accelerated. Under the same conditions, the processing speed when the tags collide is increased by about 25% on average. The time is reduced by about 28% on average, which greatly reduces the recognition time; at the same time, the problem of missed reading of tags caused by capture effect and channel interference is considered, and the recognized tag information is fed back, and the recognition rate is increased to more than 99% on average, which is greatly improved. The recognition rate of the label has been significantly improved and substantive.

Finally, it should be noted that the above embodiments are only used to illustrate the technical solutions of the present invention rather than limit them. Although the present invention has been described in detail with reference to the embodiments, those skilled in the art should understand that modifications or equivalent replacements to the technical solutions of the present invention do not depart from the spirit and scope of the technical solutions of the present invention, and all of them should be included in the scope of the present invention. within the claims.

Claims (4)

1. An RFID anti-collision algorithm based on a feedback mechanism, the algorithm stipulates that the tag object includes a random number generator TC, a counter GC, and a tag group number storage TG, and the reader object includes a current query dimension RN, a group number GN, and It is characterized in that the algorithm steps also include: Step 1) Tag grouping: the reader sends the command Req(GN) to initialize the group number GN, and the tag uses the random number generator TC in the tag to generate a random number between 0 and GN, and then save the generated random number in In the tag group number memory TG, the value of TG is the group number where the tag is located, and the tags are randomly divided into GN+1 groups, and the reader recognizes the tag whose group number is "0", after completing the identification of the "0" group , the remaining tags whose group number is greater than "0" will reduce the group number by one, and then start the next round of identification of the new "0" group tag; Step 2) Fractal dimension recognition within the tag group: first, the reader initializes the current query dimension RN, sends the query command Req(X, RN), assigns a value to GC according to the corresponding relationship between the tag prefix and the counter GC, and then the reader receives the data GC value, send the query command Request(X, RN, gc), and finally the reader detects the collision situation, obtains the command parameters according to the judgment relationship between the data collision and the tag prefix, and judges the stack; Step 3) Tag feedback identification: First, the reader calculates [M/V] and feeds it back to the tag, so that GN=[M/V]-1, and then the tag generates a random number between 0-GN as the tag group number, Stored in the tag group number memory TG, select the tag whose group number is "0" to respond, and finally detect the collision situation, and the algorithm ends; The current query dimension RN is to divide every four digits of the tag ID into one dimension, and RN corresponds to the number of each dimension; The M in [M/V] is the maximum number M of identified tags in the 16 groups obtained by feedback based on the identified 16 groups of tag information, and V is obtained by feedback based on the identified 16 groups of tag information The average number V of identified labels in the 16 groups. 2. the RFID anti-collision algorithm based on feedback mechanism according to claim 1, is characterized in that, its ID number of described label is made up of the binary bit of non-"0" or "1", and each label uses its ID number Every four binary bits are divided into one dimension from left to right. 3. The RFID anti-collision algorithm based on feedback mechanism according to claim 1, characterized in that, when the corresponding relationship between the label prefix and the counter GC in the step 2) is GC=1, the label prefix is 0001 0010 0100 1000 ;When GC=2, the label prefix is 1010 1001 1100; when GC=3, the label prefix is 0111 1011 1110 1101; when GC=4, the label prefix is 0000 1111; when GC=5, the label prefix is 0011 0110 0101. 4. The RFID anti-collision algorithm based on a feedback mechanism according to claim 1, characterized in that the judgment relationship between the data collision and the tag prefix in the step 2) is: in GC=1, only one binary bit is " 1", if a collision occurs in a certain bit, the collision position is "1", and the other positions are "0", and the label prefixes existing in the current query dimension are obtained in turn; In GC=3, only one binary bit is "0", if a certain bit collides, the collision position is "0", and the other positions are "1", and the label prefixes existing in the current query dimension are obtained in turn; In GC=4, there are only labels whose prefixes are 0000 or 1111 in the current query dimension. If a collision occurs, it means that 0000 and 1111 exist at the same time; In GC=2, the number of 1s is 2, but the leftmost bit is "1". If a bit collides, the corresponding collision position is "1", and the other positions are "0", and the current query is obtained in turn. Label prefixes present in the dimension; In GC=5, the number of 1s is 2, but the leftmost bit is "0". If a certain bit collides, set the corresponding collision position to "0" and the other positions to "1" to obtain the current query dimension in turn. Label prefixes that exist in .