自适应多叉树防碰撞算法研究.doc

《自适应多叉树防碰撞算法研究.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、自适应多叉树防碰撞算法研究摘要该文提出了一种自适应多叉树防碰撞算法。新算法在动态二叉树和四叉树搜索算法的基础上，利用曼彻斯特编码可以准确识别碰撞位的特性，通过计算碰撞因子，估计标签数量，从而自适应地调整搜索叉数，即在标签数较多的节点上选择动态四叉树搜索，而在标签数较少时选择动态二叉树搜索。理论和仿真分析表明：新算法克服了动态二叉树和四叉树搜索算法的缺点，在减少碰撞时隙数的基础上，又减少了空闲时隙数，大幅度地提高了搜索效率和时隙的吞吐量，具有一定的创新性和适用性。关键词射频识别；防碰撞算法；多叉树搜索；中图分类号TP3

2、01.6文章标识码AAnAdaptiveAnti-collisionAlgorithmBasedonMulti-treeSearchAbstractAnewadaptiveanti-collisionalgorithmbasedonmulti-treesearchisproposedinthispaper.BecauseManchestercodecanidentifythepositionofcollision,thenewalgorithmcanadjustthenumberofsearchtreeadaptiv

3、elybyusingtheinformationofprobabilityofcollision.Thatistosay，whenthenumberoftagsislarge，thenewalgorithmusefour-treesearch.Conversely,thenewalgorithmusebinary-treesearch.Theoryandcomputersimulationsshowthatthenewanti-collisionalgorithmwhichovercomesthedisadvanta

4、gesofbinary-treeandfour-treealgorithmscandecreaseeffectivelycollisiontimeslotsandidletimeslotsandimprovethethroughputoftimeslots.KeywordsRadioFrequencyIdentification(RFID)；Anti-collisionalgorithm；Multi-treesearch；1引言射频识别（RFID）是20世纪90年代兴起并逐渐走向成熟的一种非接触式的自动识别技术，在物

5、流、跟踪、定位等领域已得到广泛应用。其中，用于解决读写器作用范围内多标签识别问题的防碰撞算法已成为该领域研究的热点之一。标签防碰撞算法主要解决在读写器有效通信范围内，多个标签同时与读写器进行通信的问题。常用的防碰撞算法一般可以分为两类，一种是基于时隙随机分配的ALOHA算法[1]，包括动态时隙ALOHA(DSA)算法[1]，分群时隙ALOHA算法(GSA)[2]和标签估计算法(TEM)[3]等。其特点是，算法简单，便于实现，适用于低成本RFID系统。但由于该类算法的时隙是随机分配的，即存在一定的可能性，某一标签在相当

6、长一段时间内无法识别，即“Tagstarvation”问题，所以这类方法被称为可能性方法。另一类是基于二叉树搜索(BS)算法[1]，包括动态二叉树搜索(DBS)算法[1]，自适应二叉树搜索算法(ABS)[4-6]和自适应查询树算法(AQS)[7]等。该类算法比较复杂，识别时间较长，但不存在“Tagstarvation”问题，故被称为确定性方法。值得注意的是，当待识别标签数量较多时，基于二叉树的搜索算法由于频频出现碰撞，且每次碰撞只产生两个分支，搜索效率较低。文献[8]为此提出了一种基于四叉树的搜索算法。虽然该算法在搜

7、索的初期可以有效地减少碰撞，但随着搜索范围和标签的数量的减小，会产生大量的空闲时隙，因此搜索效率并没有得到提高。本文在动态二叉树（DBS）和四叉树（DFS）搜索算法的基础上，利用曼彻斯特编码可以准确的识别碰撞位的特性，通过计算碰撞因子，估计标签数量，从而自适应地调整搜索叉1______________________高等学校博士学科点专向科研基金(20020358033)资助课题数，即在标签数量较多时选择动态四叉树搜索，而在标签数量较少时选择动态二叉树搜索。理论和仿真分析表明：新算法克服了动态二叉树和四叉树搜索算法的

8、缺点，在减少碰撞时隙数的基础上，又减少了空闲时隙数，大幅度地提高了搜索效率和时隙的吞吐量，具有一定的创新性和适用性。22防碰撞算法原理及相关的研究成果对于一个特定的RFID系统来说，任意一个RFID标签都有一个唯一确定的EPC（电子产品代码），读写器通过获取标签的EPC来确认标签的身份。当读写器作用范围内有多个未识别的标签时，每个标签都会响应读