ECQ网络中嵌入哈密顿圈的高效算法研究  

Research on Efficient Algorithm for Embedding Hamiltonian Circles in ECQ Networks

作　　者：周东仿 ZHOU Dongfang(Shanghai Research Intitute of Publishing and Media,Shanghai Publishing and Printing College,Shanghai 200093,China;School of Computer Science and Technology,Soochow University,Suzhou 215006,China)

机构地区：[1]上海出版印刷高等专科学校出版传媒研究院,上海200093 [2]苏州大学计算机科学与技术学院,江苏苏州215006

出　　处：《自动化仪表》2022年第5期15-19,共5页Process Automation Instrumentation

摘　　要：网络的哈密顿性质在信息通信领域中具有重要的应用。具有哈密顿性质的网络能够高效率地进行线性或循环通信。交换交叉立方体(ECQ)网络是一种性能优良的互连网络。它既有较小的网络直径,又具有较低的构造成本。如果在ECQ网络的多播路由算法中使用哈密顿性质,则能够有效地减少ECQ网络通信中的死锁和拥塞。对ECQ网络中嵌入哈密顿圈的构造算法进行了研究。首先,给出了当s≥3和t≥3时,ECQ网络上从任意节点出发构造哈密顿圈的算法。然后,给出了当1≤s≤2时,ECQ网络上哈密顿圈的构造算法。最后,通过仿真试验验证了算法的正确性、有效性和高效性。本研究结果可为ECQ网络哈密顿性质的应用提供重要的理论依据。The Hamiltonian property of networks has important applications in the field of information and communication.networks with Hamiltonian property can perform linear or cyclic communication efficiently.The exchanged cross cube(ECQ)network is an interconnection network with excellent performance,which has both small network diameter and low construction cost.If the Hamiltonian property is used in the multicast routing algorithm of ECQ networks,deadlock and congestion in ECQ network communication can be effectively reduced.The construction algorithm for embedding Hamiltonian circles in ECQ networks is investigated.Firstly,the algorithm for constructing Hamiltonian circles on ECQ networks from any node when s≥3 and t≥3 is given.Then,the algorithm for constructing Hamiltonian circles on ECQ networks when 1≤s≤2 is given.Finally,the correctness,effectiveness and efficiency of the algorithm are verified by simulation experiments.The results of this study can provide an important theoretical basis for the application of the Hamiltonian property of ECQ networks.

关 键 词：交换交叉立方体网络 互连网络 哈密顿圈 哈密顿性质 构造算法 网络通信 正确性 高效性 

分 类 号：TH70[机械工程—仪器科学与技术]