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

第４３卷第５期自动化仪表Ｖｏｌ４３Ｎｏ５

２０２２年５月ＰＲＯＣＥＳＳＡＵＴＯＭＡＴＩＯＮＩＮＳＴＲＵＭＥＮＴＡＴＩＯＮＭａｙ.２０２２

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

周东仿１ꎬ２

(１.上海出版印刷高等专科学校出版传媒研究院ꎬ上海２０００９３ꎻ２.苏州大学计算机科学与技术学院ꎬ江苏苏州２１５００６)

摘要:网络的哈密顿性质在信息通信领域中具有重要的应用ꎮ具有哈密顿性质的网络能够高效率地进行线性或循环通信ꎮ交换交

叉立方体(ＥＣＱ)网络是一种性能优良的互连网络ꎮ它既有较小的网络直径ꎬ又具有较低的构造成本ꎮ如果在ＥＣＱ网络的多播路由算

法中使用哈密顿性质ꎬ则能够有效地减少ＥＣＱ网络通信中的死锁和拥塞ꎮ对ＥＣＱ网络中嵌入哈密顿圈的构造算法进行了研究ꎮ首

先ꎬ给出了当ｓ≥３和ｔ≥３时ꎬＥＣＱ网络上从任意节点出发构造哈密顿圈的算法ꎮ然后ꎬ给出了当１≤ｓ≤２时ꎬＥＣＱ网络上哈密顿圈的

构造算法ꎮ最后ꎬ通过仿真试验验证了算法的正确性、有效性和高效性ꎮ本研究结果可为ＥＣＱ网络哈密顿性质的应用提供重要的理

论依据ꎮ

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

中图分类号:ＴＨ７０文献标志码:ＡＤＯＩ:１０.１６０８６/ｊ.ｃｎｋｉ.ｉｓｓｎ１０００￣０３８０.２０２１０６００６２

ＲｅｓｅａｒｃｈｏｎＥｆｆｉｃｉｅｎｔＡｌｇｏｒｉｔｈｍｆｏｒＥｍｂｅｄｄｉｎｇＨａｍｉｌｔｏｎｉａｎＣｉｒｃｌｅｓ

ｉｎＥＣＱＮｅｔｗｏｒｋｓ

ＺＨＯＵＤｏｎｇｆａｎｇ１ꎬ２

(１.ＳｈａｎｇｈａｉＲｅｓｅａｒｃｈＩｎｔｉｔｕｔｅｏｆＰｕｂｌｉｓｈｉｎｇａｎｄＭｅｄｉａꎬＳｈａｎｇｈａｉＰｕｂｌｉｓｈｉｎｇａｎｄＰｒｉｎｔｉｎｇＣｏｌｌｅｇｅꎬＳｈａｎｇｈａｉ２０００９３ꎬＣｈｉｎａꎻ

２.ＳｃｈｏｏｌｏｆＣｏｍｐｕｔｅｒＳｃｉｅｎｃｅａｎｄＴｅｃｈｎｏｌｏｇｙꎬＳｏｏｃｈｏｗＵｎｉｖｅｒｓｉｔｙꎬＳｕｚｈｏｕ２１５００６ꎬＣｈｉｎａ)

Ａｂｓｔｒａｃｔ:ＴｈｅＨａｍｉｌｔｏｎｉａｎｐｒｏｐｅｒｔｙｏｆｎｅｔｗｏｒｋｓｈａｓｉｍｐｏｒｔａｎｔａｐｐｌｉｃａｔｉｏｎｓｉｎｔｈｅｆｉｅｌｄｏｆｉｎｆｏｒｍａｔｉｏｎａｎｄｃｏｍｍｕｎｉｃａｔｉｏｎ.

ｎｅｔｗｏｒｋｓｗｉｔｈＨａｍｉｌｔｏｎｉａｎｐｒｏｐｅｒｔｙｃａｎｐｅｒｆｏｒｍｌｉｎｅａｒｏｒｃｙｃｌｉｃｃｏｍｍｕｎｉｃａｔｉｏｎｅｆｆｉｃｉｅｎｔｌｙ.Ｔｈｅｅｘｃｈａｎｇｅｄｃｒｏｓｓｃｕｂｅ(ＥＣＱ)

ｎｅｔｗｏｒｋｉｓａｎｉｎｔｅｒｃｏｎｎｅｃｔｉｏｎｎｅｔｗｏｒｋｗｉｔｈｅｘｃｅｌｌｅｎｔｐｅｒｆｏｒｍａｎｃｅꎬｗｈｉｃｈｈａｓｂｏｔｈｓｍａｌｌｎｅｔｗｏｒｋｄｉａｍｅｔｅｒａｎｄｌｏｗｃｏｎｓｔｒｕｃｔｉｏｎ

ｃｏｓｔ.ＩｆｔｈｅＨａｍｉｌｔｏｎｉａｎｐｒｏｐｅｒｔｙｉｓｕｓｅｄｉｎｔｈｅｍｕｌｔｉｃａｓｔｒｏｕｔｉｎｇａｌｇｏｒｉｔｈｍｏｆＥＣＱｎｅｔｗｏｒｋｓꎬｄｅａｄｌｏｃｋａｎｄｃｏｎｇｅｓｔｉｏｎｉｎＥＣＱ

ｎｅｔｗｏｒｋｃｏｍｍｕｎｉｃａｔｉｏｎｃａｎｂｅｅｆｆｅｃｔｉｖｅｌｙｒｅｄｕｃｅｄ.ＴｈｅｃｏｎｓｔｒｕｃｔｉｏｎａｌｇｏｒｉｔｈｍｆｏｒｅｍｂｅｄｄｉｎｇＨａｍｉｌｔｏｎｉａｎｃｉｒｃｌｅｓｉｎＥＣＱ

ｎｅｔｗｏｒｋｓｉｓｉｎｖｅｓｔｉｇａｔｅｄ.ＦｉｒｓｔｌｙꎬｔｈｅａｌｇｏｒｉｔｈｍｆｏｒｃｏｎｓｔｒｕｃｔｉｎｇＨａｍｉｌｔｏｎｉａｎｃｉｒｃｌｅｓｏｎＥＣＱｎｅｔｗｏｒｋｓｆｒｏｍａｎｙｎｏｄｅｗｈｅｎｓ