分布式排队中退避树的深度优先遍历算法  

Depth first traversal algorithm for the back-off tree of distributed queuing

作　　者：王文鼐[1] 张延贺 吴炜 柏琛 王斌[1] WANG Wennai;ZHANG Yanhe;WU Wei;BAI Chen;WANG Bin(School of Telecommunications and Information Engineering,Nanjing University of Posts and Telecommunications,Nanjing 210003,China)

机构地区：[1]南京邮电大学通信与信息工程学院,江苏南京210003

出　　处：《通信学报》2021年第2期72-80,共9页Journal on Communications

基　　金：国家自然科学基金资助项目(No.61871234,No.61475075)。

摘　　要：分析传统分布式排队(DQ)的调度过程及退避树操作规则,设计了一种深度优先遍历的改进算法。结合完全二叉树特例分析和随机重构的一般性推算,对改进算法的系统吞吐性能进行了理论分析和仿真评估,给出了DQ帧争用时隙的最优配置条件和基于开源软件NS-3的扩展仿真。仿真结果表明,所提算法的最大吞吐量可稳定达到信道物理容量的70%。An analytic model was provided for the conventional distributed queueing(DQ)and its back-off tree operations,followed by a design of improving algorithm based on depth first traversal.Combing the specific analysis of complete binary tree with generalized extension by random tree reconstruction,the performance of proposed algorithm was evaluated on the throughput in both theory and simulation experiment.A theoretic optimal solution of contention slots of DQ frame and a brief description of simulation extension based on the open source NS-3 were presented.The simulation results show that the maximum stationary throughput by the proposed algorithm reaches 70%of the physical capacity of channel.

关 键 词：随机多址接入 分布式排队 指数退避树 深度优先搜索 性能分析 

分 类 号：TN915[电子电信—通信与信息系统]