第31卷Vo1.31第16期№l6计算机工程Co

mputerEngineering2005年8月August2005·开发研究与设计技术·文章编号:1o—3428(2伽5)16_.
17—02文献标识码tA中圈分类号TP301.
6基于修剪枝的二进制树形搜索反碰撞算法与实现余橙森,詹宜巨(1.
南昌大学计算机系,南昌330029;2.
广东工业大学自动化学院,广州510075;3.
中山大学工学院,广州510275)摘要:标签冲突是射频识别(RFID)技术的常见问题.
解决此问题的反碰撞算法有ALOHA算法、分隙ALOHA算法.
这些算法同时对大量标签操作时,效率较低.
本算法依据阅读器作用区域内,有限个标签的EPC代码构成的二进制树存在许多空闲结点,搜索时忽略空闲结点,可以高效地识别所有标签.
随后采用树的先序遍历思想予以实现,最终算法模拟表明:该算法对大量标签操作时效率稳定在46.
22%附近.
关奠词:修剪枝;二进制树;反碰撞;标签冲突;RFID;先序遍历ABinary--treeSearchingAnti--collisionAlgorithmBased0nPruningAwayBranchesandItsPracticeYUSongsen".
ZHANYiju(1.
Dept.
ofComputer,NanchangUniversity,Nanchang330029;2.
FacultyofAutomation,GuangdongUniversityofTechnology,Guangzhou510075;3.
FacultyofTechnology,SUNYAT-SENUniversity,Guangzhou510275)[Abstract]TagcollisionisacommonprobleminRFID.
Thereareseveralanti—collisionalgorithmstosolvethisproblem,suchasALOHA,SlottedALOHAandSOon.
But,theyareoftenlow—efficientwhenprocessingalotoftagsatthesametime.
Inthereader'Sprocessingarea.
thesearealotofidlenodesinthebinary—treethatarecomposedofalimitednumberoftags'EPC.
Ifthereaderignoresthemwhensearching,alltagsCanbeidentifiedwithhighefficiency.
Thisalgorithmcanbeputintopracticebasedonthepre—ordertraversingideaofthreadedtree.
Finally,algorithmsimulationindicatesthatitsefficiencyisstabilizedat46.
22%whenprocessinglargenumbersoftags.
[Keywords]Pruningawaybranches;Binary·-tree;Anti--collision;Tagscollision;RFID;Pre--ordertraversing物元网…的目的是将世界上的产品融入一个网络之中,在此基础上,可以有效地识别、追踪、管理、评价所有商品运行情况,从而在产品与用户、公司、企业、政府之间搭建一个新型、开放式的全球性网络平台.
为了很好地识别、追踪所有商品,物元网采用射频识别(RFID)技术来处理.
该技术由两部分组成:RFID标签和RFID阅读器.
RFID标签由一个附在天线上的微芯片构成,芯片中存储唯一的EPC(ElectronicProductCode)电子产品代码,用于标识单个商品.
RFID阅读器用来读取RFID标签中的EPC信息.
其工作原理为:RFID阅读器发送一段时间脉冲载波调制信号给RFID标签,利用电磁感应,标签内部对电容充电至2V,在该电压支持下将EPC信息调制发送回RFID阅读器.
问题在于:(1)当阅读器信号作用范围内存在多个标签,同一时刻有两个或者以上的标签向阅读器返回信息时,将产生冲突.
这一现象称为标签冲突.
解决冲突的算法称为反碰撞算法.
(2)粘贴标签的商品本身价值可能很低,标签的成本不能高于l美元,最好低于5美分.
(3)标签用于附着在各种各样的商品上,体积不能太大.
所以,如何快速、有效地识别区域内大批量的标签,是物元网研究的难点之一.
现在已有的反碰撞算法有随机问询的ALOHA算法、分隙ALOHA算法,信息的最佳利用率分别为l8.
4%、36.
8%,但随着标签数量的扩大,性能将急剧恶化J.
本文提出的基于修剪枝的二进制树形搜索反碰撞算法,考虑到:虽然所有标签的EPC代码可构成一个完全二叉树,但在阅读器有限的作用区域内,标签所形成的二进制树将存在许多空闲结点.
搜索时,忽略掉这些空闲结点,将能有效、快速地识别区域内的所有标签.
1算法约定为了便于描述以及实现该算法,提出以下几点约定.
(1)命令1)问询命令——call(EPC,m):阅读器发送该命令给区域内标签.
标签将自己EPC值的前m位和命令中EPC值的前m位相比较,若相符则应答,否则不应答.
参数m指相比较的位数,称为有效位数.
例如:假设区域内有3个标签,标签1的EPC值为:ol100001;标签2的EPC值为:00010100;标签3的EPC值为:00001101.
若阅读器发送call(00******,2)命令,标签2、3将应答,标签1不应答.
说明:EPC参数中的'*'表示无效位.
另外,刚开始阅读器若要求区域内所有标签应答,可采用call(**一*,0)命令.
2)选择命令——select(EPc):用某个(事先确定的)EPC作为参数发送给标签.
具有相同EPC值的标签将以此作为执行其他命令(如读出和写入数据)的切入开关,即选择这个标签.
基金项目:广州市重点科技攻关资助项目(2002Z3一D0151);江西省教育厅资助项目(赣教计字[2005130)作者筒介:余松森(1972一),男,博士生,研究方向:电子识别,控制网络及应用研究;詹宜巨,教授、博导定藕日囊:2004—06—28E-mail:yss8109@163.
com—_2l7一http://www.
paper.
edu.
cn3)读命令——ReaQ—Data:选中的标签将存储的数据发送给阅读器(在实际系统中,还有鉴别或写入等命令).
(2)时隙:从阅读器发送call命令开始,到标签应答返回信息为止这一段时间间隔称为一个时隙.
由定义可知,一个时隙包括两部分:call命令发送阶段,标签应答阶段.
根据区域内标签应答的情况,可分为3种时隙:1)碰撞时隙:标签应答阶段,区域内有两个或两个以上的标签应答.
2)有效时隙:标签应答阶段,区域内只有一个标签应答.
3)空闲时隙:标签应答阶段,区域内无标签应答.
(3)时隙数:阅读器为了识别区域内所有标签所消耗的总时隙个数.
针对n个标签,K位的EPC代码,阅读器为了识别它们所消耗的总时隙数可相应划分为:碰撞时隙数(collision—intervals),有效时隙数(effect—intervals),空闲时隙数(idle—intervals).
(4)算法效率评价指标为:有效时隙数与总时隙数的比率.
说明:识别出标签后对该标签处理所消耗的时间不计入总时隙数范围内.
2算法原理假设EPC代码为4位,阅读器作用区域内有3个标签,我们看阅读器如何利用该算法来识别它们.
算法如图1所示.
标签5olol标签6ollo标签ll:1o1/开始,lD2=0/D2l0一5Dl-zOJID0、6、、、lDl:l、DO,一标签5标签6标签田1基于修剪枝的二进树形反麓擅算法示意田开始,阅读器对区域内标签处于未知状态,发送call(****,0)命令,要求所有标签应答,详细执行过程如下:第1个时隙:阅读器发送call(****,O)命令;3个标签均应答,发生碰撞,为碰撞时隙;阅读器将EPC最高无效位置0,m加l为l;得到下一时隙所需的call(0***,1)命令.
第2个时隙:阅读器发送call(0***,1)命令;标签5、6应答,发生碰撞,为碰撞时隙;阅读器将EPC参数最高无效位置0,m加l为2;得到下一时隙所需的call(00**,2)命令.
第3个时隙:阅读器发送call(00**,2)命令;无标签应答,为空闲时隙;阅读器将EPC参数的有效位数据加l,m不变;得到下一时隙所需的call(0l**,2)命令.
第4个时隙:阅读器发送call(0l**,2)命令;标签5、6应答,发生碰撞,为碰撞时隙;阅读器将EPC参数最高无效位置0,m加l为3;得到下一时隙所需的call(0l0*,3)命令.
第5个时隙:阅读器发送call(0l0*,3)命令;标签5应答,为有效时隙.
阅读器可选中该标签,对其进行处理.
完后,阅读器将EPC参数的有效位数据加l,In不变;得到下一时隙所需的call(0Il*,3)命令.
第6个时隙:阅读器发送call(Ol1*,3)命令;标签6应答,为有效时隙.
阅读器可选中该标签,对其进行处理.
完后,阅读器将EPC参数的有效位数据加l,为100(0I1+1),将后面的2位'0'置一2l8一为无效位,m减2为1;得到下一时隙所需的call(1***,1)命令.
第7个时隙:阅读器发送call(1***,1)命令;标签Il应答,为有效时隙.
阅读器可选中该标签,对其进行处理.
完后,阅读器将EPC参数的有效位数据加l,超出EPC代码参数值范围.
意味着区域内所有标签已搜索完,结束.
由上例,可归纳出该算法要点如下:(1)剐开始,阅读器发送call(**…*,O)命令,要求区域内所有标签应答.
(2)阅读器等待标签响应,根据返回的信息识别出时隙的类型.
(3)若为碰撞时隙,将当前EPC参数的最高无效位置0,m加l,得到下一时隙所需call命令两参数.
(4)若为空闲时隙,意味着标签不属于以该EPC值为顶点的子树范围,可裁剪掉该子树.
(5)若为有效时隙,意味着识别出一个标签,阅读器可对该标签进行操作.
(6)若当前时隙为空闲或有效时隙,将当前EPC参数的有效位数据加l.
若超出EPC范围,算法结束.
否则,再判断有效位数据低位是否为0.
不为0时,m加1;若有k个0,则将这k个0置为无效位'x',m减去k;得到下一时隙call命令所属的两个参数.
3算法软件实现算法可采用树的先序遍历思想来实现,程序要点如下:置初值:EPC=**''**,m=O;dO{call(EPC,m);//阅读器问询Wait…//延时等待if为碰撞时隙将EPC最高无效位置0,m加l;//形成下一时隙call命令所//需两参数else{if为有效时隙{select(EPC);//选中该标签read—Data;//读数据}EPC参数的有效位数据加1;ifEPC值超出范围break;//结束ifEPC有效位数据低位为0,/形成下一时隙call命令两参数{检测低位'0'的个数k;将EPC有效位数据的k个'0'置为无效位;m减去k;ll}whiletrue4算法模拟结果以8位EPC代码的标签为例.
对每一组数据模拟运行500次,再取平均值,可得到测试结果如表l所示(其中,效率是指有效时隙数与总时隙数之比).
表1测试结果标签数5lol52o3o5o碰撞时隙数595l2592l9o52533637396oo34有效时隙数5lol52o3o5o空闲时隙数l9535925o56336839llo34总时隙数l2926l8439ol5l6727578l2lo68效率o3876o38l9o3836o387o3958o4l3标签数8ol28l6o2oo225255碰撞时隙数9l524l3797l67l262o2225442254有效时隙数8ol28l6o2oo225255空闲时隙数l2524lo9668l26372l442o总时隙数l84048276933352524o64445l8845o9效率o4347o4622o4773o492lo4979o.
5ol(下转第230页)系统实现了高速、灵活的基于FPGA内部的软FIFO链路处理器间通信网络.
FIFO链路网络允许板上的任何2个处理器间通过高速的32b宽FIFO缓冲接口传输数据.
6条链路的每一条均实现了数据发送和接收的各标准和中断控制的3232双向缓冲.
在200MHz主频的条件下,板上数据通信速率达到160Mb/s.
4FPGA内部软FIFO的实现与仿真现场可编程门阵列FPGA(FieldProgrammableGateArray)是在专用ASIC的基础上发展出来的,它克服了专用ASIC不够灵活的缺点.
与其它中小规模集成电路相比,它有很强的灵活性,即其内部的具体逻辑功能可以根据需要配置,对电路的修改和维护很方便.
目前,FPGA的容量已经跨过了百万门级,使得FPGA成为解决系统级设计的重要选择方案之一.
现在FPGA已经成为多种数字信号处理(DSP)应用的强有力的解决方案.
由于可编程方案的灵活性,DSP系统设计可以适应Et益变化的标准、协议和性能需求,FPGA相对于多个DSP处理器,具有集成优势和更低的系统成本.
甚高速集成电路硬件描述语言VHDL(Veryhighspeedintegratedcircuithardwaredescriptionlanguage)广泛用于描述数字系统的结构、行为、功能和接El.
它的语言形式和描述风格与句法是十分类似于一般的计算机高级语言.
笔者利用Altera公司stratix系列的cyclone器件现场用VHDL编程连接多个DSP,解决了多DSP间的互相通信问题,在QuartusII4.
0环境中仿真,得到了很不错的效果.
部分程序和仿真结果分别如以下程序和图4所示.
部分VHDL程序:FIF0lT02:FIFO32TO32PORTMAPrwrclk=>FIFOlTO2WE.
rdreq=>FIFO1TO2RREQ,rdclk=>FIFOlTO2RE.
wrreq=>FIFOlTO2WREQ,data=>FIFO1TO2DATAIN.
rdempty=>FIF0lTO2EMPTYwrfuII=>FIFOlTO2FULL.
q=>FIFOlTO2DATAOUT):PROCESS—FIFO—DSP1一TO—DSP2FIFOlTO2WRITE:PROCESS(FIFOlTO2WE)BEGIN(上接第218页)由表1可以看出,该算法和ALOHA算法有很大的不同.
在ALOHA算法中,随着区域内标签数的增加,算法的性能急剧下降.
而本算法显示,随着区域内标签数的增加,效率不但没有恶化,反而不断提高,最终逼近50.
1%.
在中等规模数量的标签中,譬如128个标签,效率也可以达到46.
22%.
5结论本文详细阐述了基于修剪枝的二进制树形反碰撞算法,并给出其软件实现.
由测试结果看出,该算法彻底解决了阅读器作用范围内多标签冲突问题,在中等规模数量的标签中,—.
23一IFfFIFO1TO2WREQ='1ANDFIFO1TO3FuLL='0')THENFIF01TO2DATAIN<:DSP1DATA:ENDIF;ENDPROCESSFIF01TO2WRITE;FIF01T02READ:PR0CESS(FIFO1TO2RE1BEGINIFfFIFOITO2RREQ='1'ANDFIFO1TO2EMPTY=0')THENDSP2DATA<=FIFOlTO2DATAOUT:ELSEDSP2DATA<="ZZZZZZZZZZZZZZZZZZ.
ENDIF;ENDPROCESSFIF01T02READ:TmB13啦5roInt"l】Iht|丌d59319ust啪0u伽0s600nsM00T200Ⅱ仰0嘲0M蛳0As1¨Ⅱj12廿0田PI^DD&瞄田时j^∞E璐·kiP']r____]广_]厂_]r__广_].
-]r_]广口~H]0tJA∞脚X∞脚X∞脚X∞姗9X∞∞X∞瑚lX∞腻X∞脚X∞咖田时Ⅱ·t∞脚X∞脚X∞脚X∞姗9X∞∞Y∞删∞腻Y∞脚Y∞咖、日D&1111∞1曰吲^DD&瞄e1111∞j]厂-]厂_]r_]广-]__]几r--广田~tgP2M]'kⅡⅡ日^·txIxxxIxIx堕0日m"Ⅲ∞口盔田时3"哪、ts∞口盔kiD*图4部分仿真结果参考文献l王念旭.
DSP基础与应用系统设计[M].
北京:北京航空航天大学出版社,20002孙广彬.
FPGA内部时钟系统间的FIFO数据接171[J】.
郑州大学学报(理学版),2003,35(2):383宋伯炜.
实现异步FIFO的一种方法[J】.
工业控制计算机,2003,16(1):614林明权.
VHDL数字控制系统设计范例[M].
北京:电子工业出版社,2003性能稳定在46.
22%附近.
这对于射频识别技术的广泛应用、物元网的发展有极其重要的现实意义.
参考文献lMelonS.
TowardAGlobal"InternetofThings".
http://www.
develo·pers.
sun.
com,2003-11-112KalinowskiR,LatteuxM,SimpwtD.
AnAdaptiveAnti.
collisionProtocolforSmartLabels.
http://www.
1ift.
fr/~simplot/recherch/articles,20013严蔚敏,吴伟民.
数据结构.
北京:清华大学出版社,1994