关于有向环网平均直径的研究  

On the average diameter of directed loop networks

作　　者：陈业斌[1] 李颖[2] 郑啸[1] 陈涛[1] 

机构地区：[1]安徽工业大学计算机学院,安徽马鞍山243002 [2]马鞍山师范高等专科学校理工系,安徽马鞍山243041

出　　处：《通信学报》2013年第2期138-146,共9页Journal on Communications

基　　金：国家杰出青年科学基金资助项目(61003311);安徽省教育厅自然科学研究重点基金资助项目(KJ2012A262;KJ2013A058);国际科技合作基金资助项目(2011DFB61530)~~

摘　　要：根据有向双环网络平均直径与其最小路径图(L-型瓦)4个几何参数(a、b、p和q)之间的关系,提供了平均直径的计算公式,并提供了快速计算平均直径的算法。提供了构造有向三环网络的最小路径图(等价树)的新方法,研究了三环网络的任意2点之间的最短路径与等价树的层之间的关系,给出了三环网络平均直径的计算公式和算法。实验结果表明:同一网络的平均直径约为直径的一半;在一个无限族中,直径达到最小值时平均直径不一定为最小值,但平均直径为最小值时直径一定为最小值。研究表明平均直径比直径更能准确地反映环网的传输效率,所以平均直径应成为设计最优网络重要的依据之一。The formula of average diameter about directed double-loop networks was presented according to the rela- tionship between average diameter and four geometric parameters （a, b, p and q） of its minimum distance diagram （L-shaped tile）, and a rapid algorithm to compute the average diameter was presented. A novel method to construct the minimum distance diagram （equivalent tree） of triple loop networks was presented, and the relationships between the layer of the equivalent tree and the shortest path of any two points in triple loop networks was studied, and a formula and a algorithm to compute its average diameter was provided. The experimental results show that average diameter ap- proaches to a half of the diameter at the same network, in one infinite family, the diameter must obtain minimum value when average diameter obtains minimum value, but the inverse is not. Studies show that average diameter is the better parameter to measure transmission efficiency about loop networks instead of diameter, so average diameter should be- come one of important bases to design the optimal networks.

关 键 词：平均直径 直径 双环网络 三环网络 L-型瓦 最短路径 最小路径图 

分 类 号：TP393.01[自动化与计算机技术—计算机应用技术]