基于二分查找的动态帧时隙标签防冲突算法.pdf

第29卷第11期
计算机应用研究
Vol 29 No
2012年11月
Application Research of Computers
Nov.2012
基于二分查找的动态帧时隙标签防冲突算法
郭志涛,李玮玮',梁志刚,顾军华
(河北工业大学a,信息工程学院;b.计算机科学与软件学院,天津300401)
摘要:在动态帧时隙算法中,根据标签到达基本符合泊松分布的特点,同时在分析其斜率特点的基融上,结合
二分查找的思想,提出一种新颖的时隙调整算法,即基于二分查找的动态帧时标莶防冲突算法,快实现时隙
调整。仿真实验表明,该方法能够显著减少识别次数,提高单位时间的识别率
关键词:二分查找识别;射烦识别;动态帧时隙算法;防沖突
中图分类号:TP393;TP301.6文献标志码;A文章编号:1001-3695(2012)11-4287-03
doi:10.3969/j.issn.1001-3695.2012.11.073
Dynamic framed slotted tag anti-collision algorithm based on binary search
GUO Zhi-tao, LI Wei-wei, LIANG hi-gang GU Jun-hua
(a. noman Eng ig h l f mer f H i s of Techlogy Ti 300401.h)
Abstract Among the dynamic frame slotted algorithm, according to the characteristic of tags arriving in line with the Poisson
distribution, this paper analyzed slope apprentice, combined with the idea of binary search, and then proposed a new slot adjust
algor thm: dynamic frame slot tag anti-collision algorithm based on binary search: to achieve quick slot adjustment. Simulation
results show that the method can significantly reduce the number of recognition and improve the recognition rate.
Key words: binary search recognition; radio frequency identifiation: dynamic framed slotted algorithm(DFSA); anti-colli
ALOHA算法是一种时分多路的存取方式,它将传输时间1.1传统 ALOHA防冲突算法
划分为若干时隙,实现了交互计算机传输。标笭随机选择时隙
最初的P- ALOHA算法是最简单的也是最容易操作的方
进行数据传输,以突发脉冲序列方式接收和发送信号。
法。该方法中标签成功传输的条件是前后连续的两个时隙周
传统的动态帧时隙算法由最初的纯 ALOHA(P- ALOHA)
期内没有信道占用。标签传输可能发生成功传输、部分冲突、
演变而来,经历了时隙 ALOHA(S- ALOHA)算法,使识别率提
完全冲突三种状况。由于成功传输的情况大大牺牲了信道的
高了一倍,最终发展为动态帧时隙 ALOHA(DFSA)算法,识别
率有了进一步的提高。虽然 ALOHA算法进行了一系列的改利用率,从而使吞吐量(妇一化)的最大值大仅为0.18。
进和提高,但是标签的冲突问题依然是RFID系统中影响识别
S- ALOHA算法改进了P- ALOHA算法的这一缺点,采用
率的最主要问题,因此,如何更好地降低标签的冲突率依然是
种广播同步脉冲序列的方式进行标签数据传输,要求每个tag
只能在时隙的开始时刻进行数据通信,避免了部分冲突的情
目前亟待解决的问题。
泊松分布在以往帧时隙调整策略中主要的应用体现在标、况、这使得冲突周期缩短了一个时隙周期,归一化的吞吐量P
签数的估计中,目的是为了应用 Schout估计法来预测未识别和总负载C的关系由p=e°(P- ALOHA)改变为P=Ce,比
标签数,但是并没考虑泊松分布的斜率特点应用于时隙调整纯 ALOHA提高了1倍,其最大值大约为0.37。P- ALOHA和
中,选择Q值估算方法也只是着重应用于对时隙的分配上。
LOHA吞吐量对比关系如图1所示。
由于泊松分布的一个显著特点是在一个时间段内标签数量可
模拟 ALOHA算法
能会过快地增加或减少,传统帧时隙 ALOHA方法忽略了这一
云0.3
特点,所以存在调整方法灵敏度不高、调整速度慢的特点;另
外,标签随机选择时隙传输也在一定程度上增加了冲突的可能
性,成为影响识别效率的一个因素。本文针对这两种情况,通
0.15
过分析泊松分布的特点提出了基于二分査找的动态帧时隙标
005
签防冲突算法。
输入负载一平均数据包数/G
1动态帧时隙标签防冲突算法及存在问题分析
图1P- ALOHA和S- ALOHA吞吐量对比关系
动态帧时隙 ALOHA算法是对前两种方法的进一步改进。
该算法把一个时间段划分成若干个帧,每个帧再划分成若干个
收稿日期:2012-03-19;修回日期:2012-04-26基金项目:天津市应用基融及前沿技术研究计划基全资助项目( I CYBJCO020)
作者简介:郭志涛(1979-),男,河北唐山人,博士,主要研究方向为视頻识别、智能算法:李玮纬(1984-),女,河北邯郫人.硕士,主受研究方向
为智能信息处理(bddylww@126.com);梁志剛(1982-),男,博士,主要研究方向为智能信息处理;願军华(1966-),男,河北石家庄人,教投,主要研
究方向为智能信息处理、宽带网络应用技术、虚拟现实理论与方法
万方数据