Abstract: The communication delay of traditional fixed-step undirected double-loop networks has been unable to break through the limited bound which is proposed by Wong and Coppersmith. In order to get lower communication delay, a new method is needed to construct undirected double-loop networks. In this paper, an algorithm that constructs undirected double-loop networks by random-step is proposed. In undirected double-loop networks, by comparing the simulation results of random-step diameter, average diameter and fixed-up limited bound of diameter, limited bound of average diameter respectively, the value of the random-step is much lower than that of the traditional fixed-step. The results show that algorithm of random-step undirected double-loop networks reduces the communication delay.

Key words: undirected double-loop networks, fixed-step, random-step, communication delay

摘要： 传统固定步长无向双环网络中通信延迟已经无法突破Wong和Coppersmith给出的下界，为获得更小的通信延迟，需要寻找新的无向双环网络构造方法。提出一种用随机步长来构造无向双环网络的算法，在无向双环网络中分别通过仿真实验对随机步长的直径、平均直径和固定步长的直径下界、平均直径下界比较，随机步长得到的值均远小于传统固定步长得到的值。结果表明：随机步长构造无向双环网络的算法降低了无向双环网络的通信延迟。

关键词: 无向双环网络, 固定步长, 随机步长, 通信延迟