摘要
在射频识别系统中,防冲突技术是RFID技术必须解决的关键问题之一。针对查询树算法因逐位增加查询前缀而增加了阅读器时间复杂度和通信复杂度这一问题,给出了一种利用冲突位来更新查询前缀的改进算法———突跟踪树算法。通过构建冲突跟踪树,从理论上分析了改进算法的通信复杂度。在冲突位是连续的假设前提下,给出了计算阅读器通信复杂度的3个引理和一个定理,并对其做了详细证明。最后利用Matlab对相关算法性能进行了对比仿真。结果表明,在冲突位是连续的前提下,冲突跟踪树算法阅读器的通信复杂度优于查询树算法阅读器的通信复杂度,从而得出在一般情况下,冲突跟踪树算法更能有效改善阅读器的通信复杂度,节省系统的开销。
Anti - Collision is one of the key problems in RFID system. Aiming at the deficiency of Query Tree Algorithm that the complexities of query and communication are increased due to adding prefix seriatim, an improved algorithm called Collision Tracking Tree Algorithm is proposed, which updates query prefix using collision position. By designing the collision position tree, the communication complexity of this improved algorithm is analyzed theoretically. On the assumption that the collision bits are continuous, three lemmas and a theorem about the reader communication complexity are presented and proved in detail. Finally, the performance of the algorithm is simula- ted by using MATLAB. The simulation results show that the reader communication complexity of collision tracking tree algorithm is better than the query tree algorithm based on the assumption that the collision bits are continuous. So, in the normal instance using the proposed algorithm can reduce the complexity of communication and save costs of the system effectively.
出处
《空军工程大学学报（自然科学版）》
CSCD
北大核心
2009年第3期68-72,共5页
Journal of Air Force Engineering University(Natural Science Edition)
基金
陕西省自然科学基金资助项目(2006F13)
关键词
无线射频识别
防冲突
冲突跟踪树
通信复杂度
RFID
anti - collision
collision tracking tree
communication complexity
