自适应多叉树防碰撞算法研究

提出了一种自适应多叉树防碰撞算法. 新算法在动态二叉树和四叉树搜索算法的基础上, 利用曼彻斯特编码可以准确识别碰撞位的特性, 通过计算碰撞因子, 估计标签数量, 从而在标签数较多的分支内选择动态四叉树搜索, 反之选择动态二叉树搜索. 理论和仿真分析表明: 新算法克服了动态二叉树和四叉树搜索算法的缺点, 在减少碰撞时隙数的基础上, 又减少了空闲时隙数, 大幅度地提高了搜索效率和时隙的吞吐率, 具有一定的创新性和实用性.

An Adaptive Anti-collision Algorithm Based on Multi-tree Search

A new adaptive anti-collision algorithm based on multi-tree search is proposed in this paper. Based on the binary tree and quadtree search, the new algorithm taking advantage of the features of Manchester encoding computes the collision factor and estimates the number of the tags. That is to say, when the number of tags in branches is large, the new algorithm uses quadtree search, otherwise, binary tree search is used. Theoretic analysis and computer simulations show that the new anti-collision algorithm overcomes the disadvantages of binary tree and quadtree algorithms. It can decrease timeslots and improve the throughput of timeslots effectively.