基于前缀匹配的二进制搜索算法及仿真  

Prefixes Matching Binary Searching Algorithm and Simulation

作　　者：王新锋[1,2] 刘建国[3] 蒋旭 杨磊[2] 杨会民 

机构地区：[1]63880部队 [2]军械工程学院计算机工程系 [3]军械工程学院装备指挥与管理系

出　　处：《系统仿真学报》2009年第13期4198-4201,共4页Journal of System Simulation

基　　金：国家自然科学基金(60372042)

摘　　要：针对射频识别系统(Radio Frequency Identification-RFID)中目标搜索算法直接影响标签功耗和搜索速度的特点,研究如何通过减少标签的平均响应次数,降低标签功耗。提出基于前缀匹配的二进制搜索(PMBS:Prefixes Matching Binary Searching)算法:由于标签ID由几个不同含义区间段组成,在识别标签ID中的前缀时,当前缀匹配数小于一定阈值时将忽略前缀中的剩余碰撞位,直接尝试以匹配前缀进行搜索,从而达到减少标签响应次数和总搜索次数的目的。仿真实验证明,当标签数从5至100变化时,标签平均响应次数平均降低25.3%,总搜索次数平均降低7.1%。Anti-collision algorithm effects tag power consumption and searching speed directly in RFID （Radio Frequency Identification） system. To reduce tag power consumption and searching times of jumping binary searching algorithm, the problem of how to reduce tag, s average response times was investigated. Since tag ID is composed by several subsections, PMBS （Prefixes Matching Binary Searching） algorithm is presented： During searching of prefixes of tag ID, when number of matching prefixes is lower than threshold, PMBS algorithm will try these prefixes to shorten searching collision bits of tag 1D. Simulation shows that PMBS can depress average tag response-time of jumping algorithm 25.3% on average, searching-time 7.1% on average.

关 键 词：射频识别 防碰撞 跳跃式算法 前缀匹配 

分 类 号：TP391.44[自动化与计算机技术—计算机应用技术]