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

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

Abstract

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

CLC Number:

TN915

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.

Figures/Tables 9

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

References 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.

Metrics

Recommended 0

No Suggested Reading articles found!

[1]	Haitao ZHAO,Shishun GAO,Haijun WANG,Ting YONG,Jibo WEI. Evaluation method for autonomous communication and networking capability of UAV [J]. Journal on Communications, 2020, 41(8): 87-98.
[2]	Qi WANG,Jaffrès-Runser Katia,Yi SUN,Jun LI,Jun ZHANG,Bin DA,Zhong-cheng LI. Fundamental performance bounds for multi-performance criteria in wireless ad hoc networks [J]. Journal on Communications, 2015, 36(6): 1-140.
[3]	Guo-dong WANG,Yong-mao REN,Jun LI. Performance evaluation of TCP congestion control algorithms in fast long distance network [J]. Journal on Communications, 2014, 35(4): 81-90.
[4]	. Performance evaluation of TCP congestion control algorithms in fast long distance network [J]. Journal on Communications, 2014, 35(4): 10-90.
[5]	. Multi-dimension resource allocation algorithm based on QoS guarantee in dense WLAN [J]. Journal on Communications, 2014, 35(3): 17-156.
[6]	Qi ZHANG,Lin-jing ZHAO,Jian-dong LI. Multi-dimension resource allocation algorithm based on QoS guarantee in dense WLAN [J]. Journal on Communications, 2014, 35(3): 150-156.
[7]	Xing PU,Meng-xiao LIU,Rui-tao ZHOU,Jun JIN,Qiang GAO,Yuan-da CAO. Performance analysis of network I/O workloads based on multi-core system in virtualized cloud environment [J]. Journal on Communications, 2011, 32(9A): 139-145.
[8]	De-guang LE,Yong JIN,Dong-hui GUO,Jin-yi CHANG. Frame importance valuation cognition based error control mechanism on cognitive networks [J]. Journal on Communications, 2011, 32(11): 11-20.
[9]	Jun LI,Jun-de SONG. United vertical handoff decision strategy in heterogeneous wireless networks [J]. Journal on Communications, 2008, 29(3A): 70-76.
[10]	Dong-yan ZHANG,Ming-zeng HU,Hong-li ZHANG. Study on network performance evaluation method based on measurement [J]. Journal on Communications, 2006, 27(10): 74-79.
[11]	IQi-jin1 J,ONGYong-qiang D. Performance evaluation of AQM schemes: a comparative study [J]. Journal on Communications, 2005, 26(11): 100-105.

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

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 9

References 10

Related Articles 11

Metrics

Recommended 0