關于有向環網平均直徑的研究

陳業斌，李穎，鄭嘯，陳濤

（1.安徽工業大學 計算機學院，安徽 馬鞍山 243002；2.馬鞍山師范高等專科學校 理工系，安徽 馬鞍山 243041）

1 引言

從目前網絡運營商為大用戶提供的光纖接入網狀況來看，對于某些大型用戶，比如電力、電信、有線電視等，其主干網大多以環型網絡的方式提供服務。其中，比較有代表性的有電力通信系統的SDH（synchronous digital hierarchy）環網、電信系統的以太環網和有線電視光纖網。

全光通信技術的發展為環型網絡在現實世界中的應用提供了可能和保障，環網的通信性能與其拓撲結構密切相關。一個結構不好的環網往往會出現信息傳輸延遲較大、通信效率和容錯效率低下等現象。為了更好地發揮環網在各行業的潛力，必須在設計其結構時對其進行優化。

環網技術要達到應用級要求，高可靠性是首先需要解決的問題。網絡的高可靠性與網絡的傳輸延遲密切相關。傳輸延遲是指信號從一個地方傳輸到另一個地方所需的時間，是指信號傳輸的群延時，即信號以群速通過一個物理連接所經歷的時間。在端到端通信連接中，產生延時的環節很多，主要是由傳輸媒質延時和網絡節點延時組成。光在纖芯中傳輸速率很快，因此，與網絡節點延時相比，傳輸媒質延時可以忽略不計。網絡節點延時是指信號通過若干網絡節點過程中的延時，這是造成信號傳輸延時的主要原因，這部分延時與傳輸距離無關，只與網絡系統中的節點多少以及網絡結構相關。

節點相同的環型網絡，由于其結構上的差異，其傳輸延遲有時相差很大。因此，對網絡結構的優化是一個比較重要的課題。以前人們往往用直徑去度量傳輸延遲。直徑可定義為任意 2個節點之間最短距離的最大值，而平均直徑定義為任意2個節點之間最短距離的平均值。因此，人們自然會產生這樣的疑問:就傳輸延遲而言，直徑與平均直徑哪個更具有代表性呢？直徑最小的網絡，其平均直徑是否也是最小值呢？本文將以環型網絡中的有向雙環網絡和有向三環網絡為基礎研究這個理論問題。

近年來，關于環型網絡的研究主要集中在雙環網絡和三環網絡上。研究的目標主要集中在網絡直徑、路由和構造最優網絡和容錯等問題上。Wong和 Coppersmith[1]證明了有向雙環網絡的直徑存在下界，該結論為研究緊優有向雙環網絡提供了理論依據。Chen[2,3]證明了有向雙環網絡最小路徑圖的存在，并給出L-型瓦的定義。有了最小路徑圖，直徑的計算變得更加容易。接下來，人們用數學的方法證明了大量緊優有向雙環網絡的存在[4～6]；方木云[7]用仿真的方法發現了大量緊優環網。2007年，GOMEZ[8]給出了有向雙環網絡的最優路由算法。有向雙環網絡能并行傳輸信息，為了衡量其并行傳輸能力，CHEN[9]給出了寬直徑對其并行傳輸的效率進行度量。能夠并行輸送信息的網絡一定具有容錯能力，DHARMASENA[10]和陳業斌[11]分別給出了有向雙環網絡容錯路由算法和容錯容直徑的計算方法。

就平均直徑而言，人們對其認識和研究還不夠深入，相關的結論也很少。2009年，方木云[12]對非單步長有向雙環網絡的平均直徑進行了研究，給出了平均直徑的計算公式:avg d(N;r,s)=從計算公式中不難發現，i從1變化到n?1只能得到n?1個 d，最后求平均值應該是除以 N?1，而不是除以N。當N的值較小時，其計算結果會存在較大的誤差。2011年，邊瓊芳[13]也對雙環網絡平均直徑進行了研究，但并沒有得出新的結論。

本文針對環型網絡這一較有代表性的網絡結構，針對目前應用較為廣泛的有向雙環網絡和有向三環網絡，就其平均直徑做如下研究。

1) 根據有向雙環網絡的最小路徑圖（L-型瓦），給出計算任意節點有向雙環網絡 G(N;r,s)平均直徑的計算公式及算法。

2) 根據有向三環網絡的最小路徑圖（T(N; s1, s2,s3)），給出計算任意節點有向三環網絡平均直徑的計算公式及算法。

3) 通過實驗分析有向環型網絡中直徑與平均直徑之間的關系，通過實驗數據對比分析平均直徑在有向環網傳輸效率上的代表性。

2 有向雙環網絡的平均直徑

有向雙環網絡的拓撲結構是一個如圖 1(a)所示的有向圖G(N;r,s)，其節點數N不小于4，r和s為網絡的步長，而且滿足關系式:1≤r ＜s ＜N（r,s為整數）[1]。L-型瓦是有向雙環網絡的最小路徑如圖 1(b)所示。L-型瓦通常是由 a、b、p和 q 4個參數所決定的L型區域（矩形為其特例），其中，a、b、p和 q都是整數，且 a,b≥2，0≤p＜a，0≤q＜b，記為L(N; a,b,p,q)[1]。當雙環網絡的3個參數N、r、s的最大公約數為1，即gcd(N;r,s)=1時，有向雙環網絡為一個強連通圖，下文中的研究都是在強連通圖的基礎上進行的。

定義1 對于任意給定N（N≥4）的有向雙環網絡G(N;r,s)，當r取某大于0的整數值，且滿足r＜ s ＜ N，s從r到N?1之間變化所得到的一組有向雙環網絡稱為有向雙環網絡的一個無限族。

圖1 G(12;2,5)的拓撲結構及其L-型瓦

定義 2 有向雙環網絡的直徑是指在有向雙環網絡中，任意2點之間最短距離的最大值，表示為 d(N;r,s)=max{du,v, (0≤u ≠ v≤N?1)}，其中，du,v指節點u到節點v的最短距離。

定義3 有向雙環網絡的平均直徑是指在有向雙環網絡中，一個節點到其他所有節點最短距離的平均值，表示為(N;r,s)=(0≤i ≠ j≤N?1)，其中，di,j指節點 i到節點 j的最短距離。

2009年，方木云[12]對非單位步長的平均直徑進行了研究，他的算法思想是在生成有向雙環網絡最小路徑圖—L-型瓦的過程中，利用相關參數來計算平均直徑，該算法的時間復雜度最高為 O(N2)。為了提高效率，本文將采用新的算法，無需繪制 L-型瓦，只要知道G(N; r, s)中的N、r和s的值，就能計算出L-型瓦的4個參數a、b、p和q，從而計算出有向雙環網絡的平均直徑。

2.1 平均直徑的計算公式

研究表明:在有向雙環網絡中，與距離相關的問題都可以利用有向雙環網絡的最小路徑圖—L-型瓦來得到[8]。根據有向雙環網絡直徑的定義，則d(N; r, s)=max{a+b?q?2, a+b?p?2}。有向雙環網絡的平均直徑(N; r, s)也可以從L-型瓦中得到，有向雙環網絡的平均直徑可以用 L-型瓦的 4個參數表示，如定理1所描述。

定理 1 令有向雙環網絡的最小路徑圖表示為L (N; a, b, p, q)，則其平均直徑(N;r,s)可分為2種情況。

證明 將 L-型瓦看作是由若干個單元格所組成的，每一個單元格放一個節點。因為有向雙環網絡的L-型瓦總體可分為2種情況:當ab=N時，L (N;a, b, p, q)為矩形；當 ab ＜ N 時，L (N; a, b, p, q)為“L”型。根據有向雙環網絡 G(N;r,s)的對稱性，節點u到節點v之間的距離等于節點0到節點v?u之間的距離，所以要研究有向雙環網絡中的平均距離，只要考慮L(N; a,b,p,q)中節點0到其他節點的平均距離。

1) 當ab=N時，p=q=0，此時，平均直徑d(N;r,s)可以看成是節點 0到剩下 N?1個節點距離的平均值。由于相連2個節點的距離為1，所以節點0到其他N?1個節點的平均距離為

2) 當ab＜N時，設節點0到邊長為a和b的大矩形的每個單元格的距離之和為φ，設節點0到邊長為p和q的小矩形的每個單元格的距離之和為δ，則有

2.2 計算平均直徑的算法

根據有向雙環網絡平均直徑的計算公式，要計算G(N;r,s)的平均直徑，必須先計算出L (N; a, b, p,q)的4個參數。為此給出2種直接計算L-型瓦4個參數的算法，當有向雙環網絡 G(N;r,s)的第一步長r=1時，使用算法1；否則使用算法2。

算法1 遞歸算法。

該算法的實現過程如下。

1) 令 l?1=N，l0（0≤l0≤N）為正整數且滿足:rl0+s≡0(mod N)；定義 li、qi為如下的遞歸式:li?2=qili?1+li(0≤li≤li?1, 1≤i≤m+1, lm+1=0)。

2) 定義 U?1=0，U0=1 且 Ui+1=qi+1Ui+Ui?1(0≤i≤m)。由定義可知li隨著i的增大不斷減小，直到lm+1=0為止；Ui隨著i的增大不斷增大，直到Um+1=N為止，于是有

4) L-型瓦的 4個參數分別為:a=lu?vlu+1，b=Uu+(v+1)Uu+1，p=lu?(v+1) lu+1，q=Uu?vUu+1。

5) 根據定理1計算d(N;r,s)。

算法2 同余方程算法。

該算法的實現過程如下。

1) 解同余方程:a=min{j|ks=jr(mod N), j ＞ k≥0, j=2,…,N?1}，q={k|ks=ar(mod N), k≥0}。算法思想是設計一個雙重循環，外循環j從2到N?1變化，內循環k從1到j?1變化，當ks(mod N)=jr(mod N)時，a=j，q=k。

2) 解同余方程:b=min{k|ks=jr(mod N), k≥j≥0, k=2,…,N?1}，p={j|bs=jr(mod N), j≥0}。算法思想是設計一個雙重循環，外循環k從2到N?1變化，內循環j從1到k?1變化，當ks(mod N)=jr(mod N)時，b=k，p=j。

3) 根據定理1計算d(N;r,s)。

3 有向三環網絡的平均直徑

與有向雙環網絡相比，有向三環網絡系統中的每個節點都多出一條有向邊，這無疑給實際的系統增加了成本，同時也增加了技術難度。人們之所以關注它，是因為與相同節點的有向雙環網絡相比，有向三環網絡的信息傳輸延遲相對較小，尤其是當節點數較大時更是如此。那么隨著節點數和邊數的增加，環型網絡的平均直徑又會發生怎樣的變化呢？下面將以有向三環網絡為代表，來研究其平均直徑的相關特性，并與有向雙環網絡的相關數據進行比較。

有向三環網絡的圖論模型是一個如圖2所示有向圖G(N; s1,s2,s3)[14]，其中，N、s1、s2和s3都是自然數，且滿足:N≥4，1≤s1≠ s2≠ s3＜ N。圖中有 N個節點，分別記為 0,1,2,…,N?1，有 3個步長，分別記為s1、s2和s3，每個節點v發出3條有向邊:v→v+s1(mod N)、v→v+s2(mod N)和 v→v+s3(mod N)，分別記為[+s1]邊、[+s2]邊和[+s3]邊。對于一個給定的 N、s1、s2、s3的有向三雙環網絡，其平均直徑是一定的。

現有的研究結果表明:超L-型瓦結構是三環網絡所對應的最小路徑圖之一[15]，它是一個三維立體圖形[16]，當網絡節點較大時，仿真試驗的效率不是很理想，其相關參數的計算比較復雜。2002年，侯新民等提出了利用圖層的方式來研究三環網絡[17]，該思想與超L-型瓦相比，雖然復雜度上大大降低了，但其只限于第一步長為單位步長的有向三環網絡，并不具有通用性。研究表明:利用樹型結構來研究有向環網，可使研究工作相對簡單化[18]。本文將有向三環網絡的空間結構映射為二維平面上的三叉樹結構，并證明三叉樹結構是有向三環網絡最小路徑圖的另一種表現形式。在此基礎上，進一步對三環網絡的平均直徑相關特性進行研究。

圖2 有向三環網絡G(12;1,3,4)的拓撲結構

3.1 構建最小路徑圖

定義4 對于任意給定N（N≥4）的有向三雙環網絡G(N;s1,s2,s3)，當s1和s2取大于0的整數值，且滿足 s1＜s2＜N，s3從 s2到 N?1之間變化；或當s1=1，s3=N?1，s2從s1到s3之間變化，所得到的一組有向三環網絡稱為有向三環網絡的一個無限族。

定義 5 三環網絡的直徑是指在三環網絡中，任意2點之間最短距離的最大值，表示為d(N; s1, s2,s3)=max{du,v, (0≤u ≠ v≤N?1)}，其中，du,v指節點u到節點v的最短距離。

定義 6 三環網絡的平均直徑是指在三環網絡中，一個節點到其他所有節點最短距離的平均值，表示為(N;s1,s2,s3)=(0≤i≠j≤N?1)，其中，di,j指節點i到節點j的最短距離。

由定義5和定義6可知，不論是計算有向三環網絡的直徑還是平均直徑，都必須求出有向三環網絡中任意2節點之間的最短距離，但從圖2所示的拓撲結構中顯然無法直接求出任意2節點之間的最短距離。為此，將三環網絡的拓撲結構映射為二維平面上等價的三叉樹結構，得到三環網絡的最小路徑圖。其映射方法如定義7。

定義7 有向三環網絡的等價樹T (N;s1,s2,s3)的構造方法如下。

1) 選節點0為三叉樹的根節點，其所對應的層數為第0層。

2) 分別以[+s1]邊、[+s2]邊和[+s3]邊為連線，以s1、s2、s3的值來構造三叉樹第1層上的節點。

3) 分別取第i（i≥1）層上的每一個節點v，分別以[+s1]邊、[+s2]邊和[+s3]邊為連線，以v+ s1(mod N)、v+s2(mod N)、v+s3(mod N)的值來構造三叉樹第i+1層上的節點；若新的節點在三叉樹中已經出現，則第i+1層上不再放置該節點。

4) 重復步驟3)，直到三叉樹中不再出現新的節點為止。

定義7所生成的圖形是一個三叉樹結構，有向三環網絡 G(12;1,3,4)所對應的三叉樹 T(12;1,3,4)結構如圖3所示。

圖3 三叉樹T(12;1,3,4)

定義8 若有向三環網絡G(N;s1,s2,s3)中的所有節點都在其等價的三叉樹T(N;s1,s2,s3)中出現，則稱此三叉樹為滿節點樹。

滿節點樹出現的充要條件是圖 G(N;s1,s2,s3)為強連通圖，此時N、s1、s2、s3必須滿足條件:gcd(N, s1,s2, s3) =1，即N、s1、s2、s34個數的最大公約數為1。下文所做的研究都是在滿節點樹的基礎上展開的。

根據有向三環網絡的對稱性，任意節點x到節點y之間的距離等于節點0到節點y ? x(x＜y)之間的距離。因此，研究三環網絡的相關問題，只需研究節點0到其他任意節點之間的相關問題。所以在三叉樹的根節點上放置了節點 0。于是，三環網絡的直徑可以重新表示為:d(N;s1,s2,s3)=max{d0,v,(0＜v≤N?1)}，平均直徑可以重新表示為:(N;s1,s2,s3)=(1≤i≤N?1)。

3.2 平均直徑的計算策略

研究表明:有向三環網絡的最小路徑圖可以表示為三叉樹結構，其平均直徑為三叉樹中根節點到其他節點的平均距離。其依據如下。

引理1 從三叉樹T(N;s1,s2,s3)的根節點(節點0)出發，必存在一條路徑p=m[+s1]+n[+s2]+k[+s3](m≥0, n≥0, k≥0，m、n、k不全為0)可以到達樹中的任意節點 v(v ≠ 0)。

證明 由定義7可知，除第0層外，其他層上的節點至少存在一個父節點，而它們共同的祖先是根節點(節點 0)，因此從根節點可以到達任意節點v(v ≠ 0)。由于樹中的任意節點 v(v ≠ 0)的值都必須滿足同余方程:v=ms1+ns2+ks3(mod N) (m≥0, n≥0,k≥0)，所以必存在一條從根節點到節點v(v ≠ 0)的路徑p, 且p=m[+s1]+n [+s2]+k [+s3](m≥0, n≥0, k≥0，m、n、k不全為0)。

引理2 在三叉樹T(N;s1,s2,s3)中，從根節點出發經過路徑p（p=m[+s1]+n [+s2]+k [+s3]）到達任意節點v(v ≠ 0)的路徑長度Lp=m+n+k，且Lp為2節點間最短路徑的長度。

證明 由三環網絡 G(N;s1,s2,s3)的拓撲結構可知，從節點0到任意節點v(v ≠ 0)都存在多條路徑。由引理1可知，在三叉樹T(N;s1,s2,s3)中，必存在一條路徑p=m[+s1]+n[+s2]+k[+s3](m≥0, n≥0, k≥0，m、n、k不全為0)，使得從根節點出發經過路徑p到達樹中任意節點v，其路徑p的長度為Lp=m+n+k。假定樹中存在路徑p '，使得從根節點出發經過路徑p'到達節點 v，其路徑長度 Lp'＜Lp，則節點 v 應該出現在更小的層上，后面的層上就不會再出現節點v。現在是在2層上都現出了節點v，這與定義7矛盾，假設不能成立。所以在樹T(N;s1,s2,s3)中，從根節點出發經過路徑p到達節點v的路徑長度Lp為根節點到任意節點v的最短路徑長度。

定理2 在三叉樹T(N;s1,s2,s3)中，節點v的層數l等于其最短路徑長度Lp。

證明 由引理 2可知，在等價樹 T(N;s1,s2,s3)中，根節點到任一層上節點v的路徑長度Lp等于其到節點v的最短路徑長度。令v=ms1+ns2+ks3(mod N) (m≥0, n≥0, k≥0，m、n、k不全為 0)，則最短路徑長度為 Lp=m+n+k。由定義 7可知，在樹T(N;s1,s2,s3)中，若節點v=ms1+ns2+ks3(mod N)，則從根節點開始共走m+n+k步到達v，而每走一步，層數就會增加一層，因此，節點 v所位于的層數l=m+n+k。于是得:節點v的層數l等于其最短路徑長度Lp。

定理 3 三叉樹 T(N;s1,s2,s3)是三環網絡 G(N;s1,s2,s3)所對應的最小路徑圖。

證明 由定理2可知，在三叉樹T(N;s1,s2,s3)中，節點v的層數l等于其最短路徑長度Lp。因此，根節點到任一層上節點距離都相等，且為最短距離。由于在三叉樹中不存在多余的重復節點，所以三叉樹 T(N;s1,s2,s3)是三環網絡 G(N;s1,s2,s3)所對應的最小路徑圖。

定理 4 有向三環網絡的平均直徑d(N;s1,s2,s3)等于其三叉樹T(N;s1,s2,s3)的層數l與每層節點總數nl積之和的平均值。即(N;s1,s2,s3)=(1≤l≤L)。

證明 根據平均直徑的定義和定理3可知，有向三環網絡的平均直徑可以看成是T(N;s1,s2,s3)中節點0到其他節點最短距離的平均值。首先，節點0到其他節點的路徑數共有N?1條；其次，設三叉樹T(N;s1,s2,s3)的層數l=1,2,3,…,L（L為最大層數），每層上的節點數為nl，則節點0到其他節點路徑的總長度為，所以(N;s1,s2,s3)=

3.3 計算平均直徑的算法

根據上文的分析可知，要計算有向三環網絡G(N;s1,s2,s3)的平均直徑，首先必須構造出相應的等價樹，得到其層數以及每層上的節點個數。其算法如下。

1) 定義3個線性表l、l1和l2，線性表l中首先放節點0作為根節點，線性表l1放3個節點s1、s2和s3作為樹的葉子節點，線性表l2置空。定義初始樹高:layer=1。定義樹中路徑總長度初值:sum=3。

2) 依次取線性表 l1中的每個節點 v，以v+s1(mod N)、v+s2(mod N)和 v+s3(mod N)來生成 3個新的葉子節點，若每個新的節點在樹中沒有出現過，則分別將其加入到l1和l2中。然后將節點v從l1移到l中。

3) 判斷線性表l2是否為空，若不為空，統計線性表 l2中葉子節點的個數放置到 k中，layer++，sum=sum+layer*k，將線性表l2置空，重復步驟2)，直到l2為空，即不再產生新的葉子節點為止。

4 實驗結果及分析

1974年，Wong C K和Coppersmith D 給出了有向雙環網絡G(N;r,s)直徑的下界:lb=?2[1],表示不小于x的最小整數。如果某G(N;r,s)的直徑取得最小值，即d(N;r,s)=?2，則稱該雙環網絡G(N;r,s)是最優雙環網絡。若最優環網的平均直徑也取最小值，此時的環網從傳輸效率上來看應該是最優中的優秀者，因此，將其定義為雙優網絡。雙優網絡也應該存在三環網絡的無限族中。

同一網絡的直徑與平均直徑之間是否存在一定的關系？有向環網的平均直徑是否可以代替直徑來表示網絡的傳輸效率？帶著這些問題，筆者利用Java作為前臺開發工具，SQL Server 2005作為后臺數據庫服務器，建立了有向環網仿真實驗平臺，對有向雙環網絡和三環網絡多個無限族進行了大量的實驗，實驗參數選取如下。

1) 節點數N是從4～1000中抽取出的一系列整數，其中，4～1000區間中的每一個N值都必須進行實驗，從1000～10000區間中取一個數作為起點（如1100），然后按循環變量加上某整數（如i+100）的數列選值。

2) 根據環網的對稱性，有向雙環網絡的第一步長r的變化范圍為1～N/2；第二步長s的變化范圍為r～N?1。有向三環網絡的第一步長s1選取為1，第二步長s2變化范圍為1～N?2，第三步長s3選取為N?1。這樣的取值可使得到的每一個無限族都很完整，容易發現數據的變化規律。

3) 存放到后臺數據庫中的參數有:節點值 N，步長r、s或（s1、s2、s3），直徑d，平均直徑d。

表1所示為有向雙環網絡G(50;1,s) 和有向三環網絡G(50;1,s,49) 2組無限族的直徑和平均直徑的部分實驗數據。為了簡化表中數據，分別用、、)和(50)來替代)、d()和()。根據實驗數據繪制的仿真圖如圖4和圖5所示。

表1 G(50;1,s)和G(50;1,s,49)的直徑和平均直徑對照

表1中的數據包括有向雙環網絡G(50;1,s)的第二步長s在2～49變化所得的無限族中直徑和平均直徑的值，還包括有向三環網絡G(50;1,s,49)的第二步長s在2～48變化所得的無限族中直徑和平均直徑的值。根據有向環網的對稱性，只取前一半數據來分析即可。

對于有向雙環網絡 G(50;1,s)，其直徑下界為lb=?2=?2=11，從表1中的數據可以看出 G(50;1,14)、G(50;1,15)、G(50;1,17)、G(50;1,19)、G(50;1,22)、G(50;1,23)的直徑都是 11，達到了下界值，根據定義這些都是最優雙環網絡。進一步分析可知，在該無限族中，平均直徑的最小值是5.9，對應的網絡分別是 G(50;1,15)、G(50;1,19)、G(50;1,22)。由此可見:平均直徑最小的有向雙環網絡一定是最優的，反之不然。另外，最優有向雙環網絡的平均直徑之間存在較大的差值:(50;1,17)?d(50;1,15)=8.82?5.9=2.92。從表中數據還可以看出相同有向雙環網絡的平均直徑約等于直徑的一半。

根據實驗數據分析得:有向三環網絡 G(N;s1,s2,s3)在 4≤N≤86的區間內滿足:d(N;s1,s2,s3)≥?1，當N＞86時，其下界的分布是一個分段函數，目前還沒能找到其分布規律。對于有向三環網絡G(50;1,s,49)，其直徑下界為lb=?1 =8，從表 1中的數據可以看出 G(50;1,8,49)、G(50; 1,10,49)、G(50;1,12,49)、G(50;1,14,49)、G(50;1,20,49)、G(50;1, 22,49)的直徑都是8，達到了下界值，它們都是最優網絡。進一步分析可知，在該無限族中，最小的平均直徑為d(50;1,20,49)=4.4。由此可知:平均直徑最小的有向三環網絡一定是最優的，反之不然。從表中數據還可以看出有向三環網絡的平均直徑約等于其直徑的一半。

圖4所示為有向雙環網絡無限族G(50;3,s)的直徑與平均直徑的分布，圖5所示為有向三環網絡無限族G(50;1,s,49)的直徑與平均直徑的分布。從圖4和圖5中可以看出:不論有向雙環網絡還是有向三環網絡，在一個無限族內，直徑和平均直徑的分布都呈軸對稱圖形；在一個無限族內，直徑到達下界的網絡個數往往要大于平均直徑達到最小值的網絡個數；在一個無限族內，平均直徑的變化規律與直徑大致相同，但又不完全相同。

圖4 G(50;1,s)無限族的直徑和平均直徑的分布

圖5 G(50;1,s,49)無限族的直徑和平均直徑的分布

5 結束語

通過對有向環網平均直徑的研究，筆者發現同一網絡的平均直徑與直徑之間存在著一定的關系:同一網絡的平均直徑約等于直徑的一半；在一個無限族中，當某網絡的直徑取得最小值時，其平均直徑不一定取得最小值，有時甚至相差很多；但平均直徑最小的網絡其直徑一定也取最小值，此時的網絡傳輸效率是最高的，因此，稱此類網絡為雙優網絡。以前在設計網絡結構時，通常只是用直徑的大小作為傳輸效率的衡量標準，研究表明就傳輸效率而言，平均直徑比直徑更具有參考價值。因此，平均直徑應該成為構造環型網絡重要的參考依據之一。

有向雙環網絡的直徑存在下界，有向三環網絡的直徑在一定的區間范圍內也存在下界。那么，有向環網的平均直徑是否也存在下界呢？它的存在對計算平均直徑的最小值有著一定的意義，這將成為下一個要攻克的難題。

[1]WONG C K, COPPERSMITH D.A combinatorial problem related to multimodule organizations[J].J Assoc Computer, 1974, 21(3):392-402.

[2]CHEN C Y, HWANG F K.The minimum distance diagram of double-loop networks[J].IEEE Transactions on Computers, 2000, 49(9):977-979.

[3]CHEN C Y, JAMES K L, TANG W H.An efficient algorithm to find a double-loop network that realizes a given L-shape[J].Theoretical Computer Science , 2006, 359(1-3):69-76.

[4]AGUILO F, FIOL M A.An efficient algorithm to find optimal double loop networks[J].Discrete Mathematics,1995,138(1-3):15-29.

[5]CHEN B X, XIAO W J.Optimal designs of directed double-loop networks[A].Lecture Notes in Computer Science (LNCS)[C].Berlin,Germany:Springer Verlag, 2004.19-24.

[6]周建欽.關于 K緊優雙環網絡[J].中國科學技術大學學報, 2005,35(6):738-742.ZHOU J Q.On K-tight optimal double-loop networks[J].Journal of University of Science and Technology of China, 2005,35(6):738-742.

[7]方木云,趙保華,屈玉貴.雙環網絡G(N;1,s)的L形瓦仿真算法[J].系統仿真學報.2005, 17(4):914-916.FANG M Y, ZHAO B H, QU Y G.An algorithm to simulate the L-shaped tile of double-loop networks G(N;1,s)[J].Journal of System Simulation, 2005,17(4):914-916.

[8]GOMEZ D, GUTIERREZ J, IBEAS A.Optimal routing in double loop networks[J].Theoretical Computer Science, 2007, 381(1-3):68-85.

[9]CHEN Y B, LI Y, WANG J K.On the wide diameter of directed double-loop network[J].Journal of Network and Computer Applications,2011, 34(2):692-696.

[10]DHARMASENA, HETTEHE P, XIN Y.An optimal fault-tolerant routing algorithm for weighted bidirectional double-loop networks[J].IEEE Transactions on Parallel & Distributed Systems, 2005, 16(9):841-852.

[11]陳業斌,王建堃,李穎.有向雙環網絡的容錯路由及容錯直徑[J].華中科技大學學報(自然科學版),2010,38(2):12-15.CHEN Y B, WANG J K, LI Y.Fault-tolerant routing and diameters of directed double-loop networks[J].Journal of Huazhong University of Science and Technology (Natural Science Edition), 2010,38(2):12-15.

[12]方木云, 湯紅霞.非單位步長雙環網絡平均直徑的研究[J].華中科技大學學報(自然科學版), 2009,37(6):12-15.FANG M Y, TANG H X.A survey on the average diameter of double-loop networks with non-unit step[J].Journal of Huazhong University of Science and Technology (Natural Science Edition), 2009,37(6):12-15.

[13]邊瓊芳,姜太平,劉輝等.雙環網絡平均直徑的研究[J].安徽工業大學學報(自然科學版),2011,28(3):277-281.BIAN Q F, JIANG T P, LIU H, et al.Survey on the average diameter of double-loop networks[J].J of Anhui University of Technology(Natural Science), 2011,28(3):277-281.

[14]AGUILO F, FIOL M A, GARCIA C.Triple-loop networks with small transmission delay[J].Discrete Math, 1997,15(4):3-16.

[15]CHEN C Y, HUNG C S, TANG W S.On the existence of hyper-L triple-loop networks[J].Discrete Math, 2006,306(12):1132-1138.

[16]邰偉鵬,方木云,徐宏.三環網絡 TL(N;1,s,s+1)超 L-型瓦仿真算法[J].華中科技大學(自然科學版), 2010,38(8):50-52.TAI W P, FANG M Y, XU H.Algorithm to simulate the hyper L-shaped tile for triple-loop networks TL(N;1,s,s+1)[J].Journal of Huazhong University of Science and Technology (Natural Science Edition), 2010,38(8):50-52.

[17]侯新民, 王天明.分布式三環網絡傳輸延遲[J].大連理工大學學報,2002,42(1):9-12.HOU X M, WANG T M.On the transmission delay of distributed triple loop networks[J].Journal of Dalian University of Technology, 2002,42(1):9-12.

[18]陳業斌.基于二叉樹的有向雙環網絡最短路徑算法[J].華中科技大學學報(自然科學版), 2009,37(4):78-81.CHEN Y B.Bintree-based shortest path algorithm of directed double-loop networks[J].Journal of Huazhong University of Science and Technology (Natural Science Edition), 2009,37(4):78-81.