Research On RFID Anti-collision Algorithm Based On Tree Structure In IoT

With the rapid development of information technology,Internet of Things(IOT)technology is becoming more and more important.Radio frequency identification technology(RFID)is an important key technology as the Internet of Things sensing layer acquisition and transmission of the massive data on the bottom.It has the advantages of fast reading speed,multi-target recognition,low cost,strong security of data transmission and non-line of sight.These advantages make the RFID technology have broader application prospects.In the future application environment of Internet of things,the need to perceive the underlying data must be massive and large-scale whereas communication channel resources are limited.With multiple tags to be identified within the scope of the reader's work,the tags compete for the same wireless channel to communicate with the reader,inevitably producing data collision problems.This scenario can affect the system's recognition speed and recognition efficiency seriously.The solution of the collision problem of label data is very important to improve the overall performance of RFID system,especially in the large-scale data environment of future Internet of Things application,and the importance of solving this problem is particularly prominent.Therefore,it is necessary to establish an effective and efficient anti-collision mechanism to solve the collision problem of multi-tags recognition.It has also become a hot research direction to domestic and foreign scholars.The tag anti-collision algorithm of RFID system has two main categories,one is uncertainty anti-collision algorithm based on ALOHA,and the other is deterministic anti-collision algorithm based on tree structure.In this thesis,we mainly study the determined anti-collision algorithm based on tree structure.When there is a large scale tags to be identified using the existing determined anti-collision algorithms,there have the problems that the search depth is too deep,the number of collision slots and the number of query slots are too many.So aiming at these problems,in this thesis we put forward a new effective tag anti-collision algorithm---Enhanced algorithm based on Bit-locking Back off(EBLBO).The specific improvements are reflected in the following three aspects:1.After locking the tags' collision sequence,a method that every three collision bits are identified together by a way is proposed,that is to say,using the octagonal search,to effectively reduce the number of collision slots and the identification delay for tags,and achieve the purpose of improving the system throughput.2.A method of collision prefix prediction is proposed to effectively eliminate the problem of increasing the idle time slot caused by the recognition of every three collision bits and to avoid the decrease of the system performance for tag identification which caused by idle time slot.3.Introduce the stack concept in the binary search tree algorithm.That is to say,it needs to maintain a collision stack in the reader to store the predicted collision prefix.When the reader needs to query,it will pop-up the top collision prefix of the stack in turns for query,to avoid the redundancy of back to the root node for query during the identification process.And the theoretical deduction and simulation of the proposed algorithm EBLBO are given in four aspects,such as the number of queries for the reader,the amount of data transmitted,the average recognition delay of the tag and the system throughput.The experimental results show that,using the new algorithm through these three improvements,compared with the original anti-collision algorithm Bit-locking Back off,the number of reader queries decrease by nearly 16.6%,and the system throughput increase by nearly 10% under large-scale tag recognition environment.What's more,the transmission data volume decrease by nearly 48% and the average tag recognition delay is reduced by 1.36 ms.So the new algorithm enhanced anti-collision algorithm based on Bit-locking Back off(EBLBO)can effectively reduce the number of collision slots and the number of query slots in the large-scale tag identification environment of Internet of Things.At the same time it can further reduce the amount of transmission data and identification delay,system throughput and system overall identification performance has been effectively improved.At the end of the thesis,we analyze and discuss the influence of the number of collision prefix prediction bits.Also we have given the relationship between the numbers of collision prefix prediction bits and the number of times to the reader query,the amount of transmission data,the average identification delay of the tag and the system throughput.At last the optimal numbers of collision prefix prediction bits are obtained when the performance of system identification is optimized.