基于二叉树分解的自适应防碰撞算法

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

1、第31卷第6期电子与信息学报Vol.31No.62009年6月JournalofElectronics&InformationTechnologyJun.2009基于二叉树分解的自适应防碰撞算法①②②①②丁治国郭立朱学永汪赵华①(解放军电子工程学院网络中心合肥230037)②(中国科学技术大学电子科学与技术系合肥230027)摘要：该文提出了一种基于二叉树分解的自适应防碰撞算法。新算法利用标签EPC的唯一性，通过时隙分配估计标签的分布情况，对发生碰撞的时隙进行二叉树搜索，从而将一个庞大且复杂的二叉树分解成多个简单的小子二叉树，简化了搜索流程。通过引入碰撞堆

2、栈，并根据时隙状态自适应得调整搜索路径，从而进一步减少搜索的时隙数及提高了时隙的吞吐量。理论和仿真实验证明了新算法的有效性，即在待识别的标签数量较多时，可有效的减少识别时间，提高搜索效率。关键词：射频识别；防碰撞算法；二叉树分解；碰撞堆栈中图分类号：TN91文献标识码：A文章编号：1009-5896(2009)06-1395-05AnAdaptiveAnti-collisionAlgorithmBasedonBinary-TreeDisassembly①②②①②DingZhi-guoGuoLiZhuXue-yongWangZhao-hua①(Centero

3、fNetwork,ElectronicEngineeringInstitutePLA,Hefei,230037,China)②(DepartmentofElectronicScienceandTechnology,USTC,Hefei,230027,China)Abstract:Anewadaptiveanti-collisionalgorithmbasedonbinary-treedisassemblyisproposedinthispaper.Inordertoenhancethesearchefficiency,abigandcomplexbinar

4、y-treeisdisassembledtoseveralsmallandsimplebinary-treesbyestimatingthedistributingoftags.Theintroductionofthecollisionstack,aswellasadjustingthesearchpathsadaptivelybasedonthestateofslots,theperformanceofthenewalgorithmisimprovedfurther,includingreducingthesearchtimeslotsandimprov

5、ingthethroughputoftimeslots.Theoryandcomputersimulationsshowthatthenewanti-collisionalgorithmispractical,especiallywhenthenumberoftagsislarge.Keywords:RadioFrequencyIDentification(RFID);Anti-collisionalgorithm；Binary-treedisassembly;Collisionstack1引言[46]−[7]叉树搜索算法(ABS)，自适应查询树算法(AQ

6、S)、返回[8][9]式搜索算法(BackTrack)和后退索引搜索算法等。该类算射频识别(RFID)是20世纪90年代兴起并逐渐走向成熟法比较复杂，识别时间较长，但不存在“tagstarvation”问的一种非接触式的自动识别技术，在物流、跟踪、定位等领题，又被称为确定性方法。域已得到广泛应用。其中，用于解决读写器作用范围内多标本文提出了一种基于二叉树分解的自适应防碰撞算法。签识别问题的防碰撞算法已成为该领域研究的热点之一。新算法在二叉树搜索算法的基础上，利用标签EPC标签防碰撞算法主要解决在读写器有效通信范围内，多(ElectronicProductC

7、ode，即电子产品代码)的唯一性，通个标签同时与读写器进行通信的问题。常用的防碰撞算法一过时隙分配估计标签的分布情况，对发生碰撞的时隙进行二般可以分为两类，一种是基于时隙随机分配的ALOHA算叉树搜索，从而将一个庞大且复杂的二叉树分解成多个简单[1][1]法，包括动态时隙ALOHA(DSA)算法，分群时隙ALOHA的小子二叉树，简化了搜索流程。通过引入碰撞堆栈，并根[2][3]算法(GSA)和标签估计算法(TEM)等。其特点是，算法据时隙状态自适应地调整搜索路径，从而进一步减少搜索的简单，便于实现，适用于低成本RFID系统。但由于该类算时隙数及提高了时隙的

8、吞吐量。理论和仿真实验证明了新算法的时隙是随机分配的，即存在一定的