Journal of Computer Applications ›› 2012, Vol. 32 ›› Issue (11): 3089-3091.DOI: 10.3724/SP.J.1087.2012.03089

Previous Articles     Next Articles

Enhanced binary search algorithm based on stack storage

YUAN Zheng-wu1,2,DUAN Li-dan2   

  1. 1.
    2. College of Computer Science and Technology, Chongqing University of Posts and Telecommunications, Chongqing 400065, China;
  • Received:2012-05-16 Revised:2012-06-19 Online:2012-11-12 Published:2012-11-01
  • Contact: DUAN Li-dan

改进的基于堆栈存储的二进制搜索算法

袁正午1,2,段莉丹1   

  1. 1. 重庆邮电大学 计算机科学与技术学院,重庆 400065
    2. 重庆邮电大学中韩合作GIS研究所
  • 通讯作者: 段莉丹
  • 作者简介:袁正午(1968-),男,湖南益阳人,教授,博士,CCF会员,主要研究方向:LBS、移动定位、射线跟踪、GIS系统集成;段莉丹(1988-),女,河南安阳人,硕士研究生,主要研究方向:RFID、空间定位、射线跟踪。
  • 基金资助:
    重庆市教委2011年科学技术研究项目(KJ110514);重庆邮电大学计算机学院“云计算”专项(JK-Y-2010001)

Abstract: In the RFID system, the tags collision resulting from the data transaction between several tags and the reader at the same time is unavoidable. Focusing on the tags collision problem of the RFID system, analyzing the theories of binary, dynamic binary and retrusive binary algorithm, and considering the identifying times and the bits of transmitting data together, an improved algorithm which effectively reduced the times of identification and transmission of redundant information via preprocessing the tags’ ID and setting the stack on reader was presented. The simulation results indicate that this algorithm can obtain a better performance in terms of timesefficiency and bitsefficiency.

Key words: Radio Frequency Identification (RFID) system, tag, anticollision, binary algorithm, stack

摘要: 针对无线射频识别(RFID)系统中的标签防碰撞问题,详细分析典型的二进制算法、动态二进制算法及后退式二进制算法的原理,同时考虑识别次数和传输位数这两方面的性能,提出了一种快速高效的防碰撞算法。通过对标签进行预处理以及在阅读器中设置堆栈,有效地减少碰撞算法中的识别次数和传输冗余信息。仿真结果表明该算法在次数效率和位数效率性能上有较大的提高。

关键词: 无线射频识别系统, 标签, 防碰撞, 二进制算法, 堆栈

CLC Number: