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

doi:10.11959/j.issn.1000-436x.2021044

通信学报 ›› 2021, Vol. 42 ›› Issue (2): 72-80.doi: 10.11959/j.issn.1000-436x.2021044

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

王文鼐, 张延贺, 吴炜, 柏琛, 王斌

南京邮电大学通信与信息工程学院，江苏南京 210003

修回日期:2020-12-16 出版日期:2021-02-25 发布日期:2021-02-01
作者简介:王文鼐（1966- ），男，江苏南京人，博士，南京邮电大学教授、博士生导师，主要研究方向为通信网协议与无线通信技术。
张延贺（1994- ），男，山东枣庄人，南京邮电大学硕士生，主要研究方向为宽带无线通信技术。
吴炜（1993- ），女，江苏常州人，南京邮电大学博士生，主要研究方向为宽带无线通信技术。
柏琛（1995- ），男，江苏盐城人，南京邮电大学硕士生，主要研究方向为宽带无线通信技术。
王斌（1970- ），男，江西九江人，博士，南京邮电大学副教授、硕士生导师，主要研究方向为移动通信和下一代网络。
基金资助:
国家自然科学基金资助项目(61871234);国家自然科学基金资助项目(61475075)

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

Wennai WANG, Yanhe ZHANG, Wei WU, Chen BAI, Bin WANG

School of Telecommunications and Information Engineering, Nanjing University of Posts and Telecommunications, Nanjing 210003, China

Revised:2020-12-16 Online:2021-02-25 Published:2021-02-01
Supported by:
The National Natural Science Foundation of China(61871234);The National Natural Science Foundation of China(61475075)

摘要/Abstract

摘要：

分析传统分布式排队（DQ）的调度过程及退避树操作规则，设计了一种深度优先遍历的改进算法。结合完全二叉树特例分析和随机重构的一般性推算，对改进算法的系统吞吐性能进行了理论分析和仿真评估，给出了DQ帧争用时隙的最优配置条件和基于开源软件NS-3的扩展仿真。仿真结果表明，所提算法的最大吞吐量可稳定达到信道物理容量的70%。

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

Abstract:

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.

Key words: random multiple access, distributed queuing, exponential back-off tree, depth first searching, performance evaluation

中图分类号:

TN915

王文鼐, 张延贺, 吴炜, 柏琛, 王斌. 分布式排队中退避树的深度优先遍历算法[J]. 通信学报, 2021, 42(2): 72-80.

Wennai WANG, Yanhe ZHANG, Wei WU, Chen BAI, Bin WANG. Depth first traversal algorithm for the back-off tree of distributed queuing[J]. Journal on Communications, 2021, 42(2): 72-80.

图/表 9

图1

图2

图3

图4

图5

图6

图7

图8

表1

BFS和DFS算法下所有终端完成数据发送的总时长及加速因子计算结果"

K₀/个	T_BFS/s	T_DFS/s	$f = \frac{T_{BFS}}{T_{DFS}}$
16	8.15	8.59	0.95
32	15.60	16.10	0.97
64	30.61	30.57	1.00
128	60.30	58.84	1.03
256	119.85	114.88	1.04
512	238.37	226.04	1.06
1 024	475.13	448.03	1.06
2 048	946.53	890.68	1.06
4 096	1 891.09	1 775.33	1.07
8 192	3 772.36	3 545.94	1.06
16 384	7 537.00	7 085.29	1.06

表1

参考文献 10

[1]	XU W . Distributed queueing random access protocols for a broadcast channel[D]. Chicago:Illinois Institute of Technology, 1990.
[2]	XU W , CAMPBELL G . A distributed queueing random access protocol for a broadcast channel[J]. SIGCOMM Communications, 1993,23(4): 270-278.
[3]	LAYA A , ALONSO L , ALONSO-ZARATE J . Contention resolution queues for massive machine type communications in LTE[C]// 2015 IEEE 26th Annual International Symposium on Personal,Indoor,and Mobile Radio Communications. Piscataway:IEEE Press, 2015: 2314-2318.
[4]	XING S , WEN X , LU Z ,et al. A novel distributed queuing-based random access protocol for narrowband-IoT[C]// 2019 IEEE International Conference on Communications. Piscataway:IEEE Press, 2019: 1-7.
[5]	ALONSO L , FERRUS R , AGUSTI R . WLAN throughput improvement via distributed queuing MAC[J]. IEEE Communications Letters, 2005,9(4): 310-312.
[6]	ALONSO-ZARATE J , KARTSAKLI E , ALONSO L ,et al. Performance analysis of a cluster-based MAC protocol for wireless ad hoc networks[J]. EURASIP Journal on Wireless Communications and Networking, 2010:doi.org/10.1155/2010/25619.
[7]	ZHANG K , MARCHIORI A . Demo abstract:PlanIt and DQ-N for low-power wide-area networks[C]// 2017 IEEE/ACM Second International Conference on Internet-of-Things Design and Implementation. Piscataway:IEEE Press, 2017: 291-292.
[8]	WU W , LI Y , ZHANG Y ,et al. Distributed queueing-based random access protocol for LoRa networks[J]. IEEE Internet of Things Journal, 2020,7(1): 763-772.
[9]	LAYA A , KALALAS C , VAZQUEZ-GALLEGO F ,et al. Goodbye,ALOHA![J]. IEEE Access, 2016,4: 2029-2044.
[10]	徐秉铮 . 随机多址通信技术[J]. 通信学报, 1982,3(3): 78-84.
	XU B Z . Random access techniques[J]. Journal on Communications, 1982,3(3): 78-84.

[1]	黎赛, 杨亮, 崔琪楣, 于思源. RIS辅助的混合RF/THz系统性能分析[J]. 通信学报, 2022, 43(1): 49-58.
[2]	邓璐,贾焰,方滨兴,周斌,张涛,刘心. 分布式环境下话题发现算法性能分析[J]. 通信学报, 2018, 39(8): 176-184.
[3]	陆凤波,黄知涛,姜文利. 基于Fast-ICA的CDMA信号扩频序列盲估计及性能分析[J]. 通信学报, 2011, 32(8): 136-142.
[4]	鲁蔚锋,吴蒙. 两跳中继CDMA蜂窝系统的上行链路容量分析[J]. 通信学报, 2010, 31(9): 47-54.
[5]	喻莉,白云,朱光喜. 基于LFSN自相似流量模型的随机突发边界分析[J]. 通信学报, 2010, 31(5): 16-21.
[6]	丁洪伟,赵东风,黄毛毛. 新型随机多址接入无线传感器网络MAC控制协议与能量有效性分析[J]. 通信学报, 2010, 31(2): 51-57.
[7]	魏安全,沈连丰. 周期序列DSSS系统抗CW干扰性能分析[J]. 通信学报, 2007, 28(5): 1-6.
[8]	刘军,廖建新,朱晓民,王纯. 用于移动计算环境的口令认证协议研究[J]. 通信学报, 2007, 28(5): 36-42.
[9]	盛凌志,皇甫伟,雷文,吴志美. 多类别终端无线局域网实时业务性能研究[J]. 通信学报, 2006, 27(4): 16-22.
[10]	朱国东,宁红宙,刘云,何德全. PKI体系下的网络安全性能评估算法[J]. 通信学报, 2006, 27(3): 119-123.
[11]	朱巧明,刘钊,李培峰,王汝传. 基于随机高级Petri网的主动自调度集群系统的性能分析[J]. 通信学报, 2006, 27(12): 26-31.
[12]	张琳,秦家银. Turbo码在无信道状态信息的Nakagami衰落信道中的性能分析[J]. 通信学报, 2006, 27(12): 43-47.
[13]	刘彬彬,赵东风,丁洪伟. 基于概率检测的时隙式多通道随机多址无线通信网络协议分析[J]. 通信学报, 2006, 27(12): 70-75.
[14]	赵国生,王慧强,李明军. 可生存性网络的形式化建模与分析方法[J]. 通信学报, 2006, 27(11A): 48-52.
[15]	黄少滨,黄辉春,吴艳霞. TCP Vegas与TCP Reno混存网络环境性能分析及改进[J]. 通信学报, 2005, 26(1A): 31-33.

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

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

在线阅读

PDF下载

可视化

摘要/Abstract

引用本文

使用本文

图/表 9

参考文献 10

相关文章 15

Metrics

推荐阅读 0