陳業(yè)斌，李穎，鄭嘯，陳濤

（1.安徽工業(yè)大學(xué) 計算機學(xué)院，安徽 馬鞍山 243002；2.馬鞍山師范高等?？茖W(xué)校 理工系，安徽 馬鞍山 243041）

1 引言

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

全光通信技術(shù)的發(fā)展為環(huán)型網(wǎng)絡(luò)在現(xiàn)實世界中的應(yīng)用提供了可能和保障，環(huán)網(wǎng)的通信性能與其拓?fù)浣Y(jié)構(gòu)密切相關(guān)。一個結(jié)構(gòu)不好的環(huán)網(wǎng)往往會出現(xiàn)信息傳輸延遲較大、通信效率和容錯效率低下等現(xiàn)象。為了更好地發(fā)揮環(huán)網(wǎng)在各行業(yè)的潛力，必須在設(shè)計其結(jié)構(gòu)時對其進(jìn)行優(yōu)化。

環(huán)網(wǎng)技術(shù)要達(dá)到應(yīng)用級要求，高可靠性是首先需要解決的問題。網(wǎng)絡(luò)的高可靠性與網(wǎng)絡(luò)的傳輸延遲密切相關(guān)。傳輸延遲是指信號從一個地方傳輸?shù)搅硪粋€地方所需的時間，是指信號傳輸?shù)娜貉訒r，即信號以群速通過一個物理連接所經(jīng)歷的時間。在端到端通信連接中，產(chǎn)生延時的環(huán)節(jié)很多，主要是由傳輸媒質(zhì)延時和網(wǎng)絡(luò)節(jié)點延時組成。光在纖芯中傳輸速率很快，因此，與網(wǎng)絡(luò)節(jié)點延時相比，傳輸媒質(zhì)延時可以忽略不計。網(wǎng)絡(luò)節(jié)點延時是指信號通過若干網(wǎng)絡(luò)節(jié)點過程中的延時，這是造成信號傳輸延時的主要原因，這部分延時與傳輸距離無關(guān)，只與網(wǎng)絡(luò)系統(tǒng)中的節(jié)點多少以及網(wǎng)絡(luò)結(jié)構(gòu)相關(guān)。

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

近年來，關(guān)于環(huán)型網(wǎng)絡(luò)的研究主要集中在雙環(huán)網(wǎng)絡(luò)和三環(huán)網(wǎng)絡(luò)上。研究的目標(biāo)主要集中在網(wǎng)絡(luò)直徑、路由和構(gòu)造最優(yōu)網(wǎng)絡(luò)和容錯等問題上。Wong和 Coppersmith[1]證明了有向雙環(huán)網(wǎng)絡(luò)的直徑存在下界，該結(jié)論為研究緊優(yōu)有向雙環(huán)網(wǎng)絡(luò)提供了理論依據(jù)。Chen[2,3]證明了有向雙環(huán)網(wǎng)絡(luò)最小路徑圖的存在，并給出L-型瓦的定義。有了最小路徑圖，直徑的計算變得更加容易。接下來，人們用數(shù)學(xué)的方法證明了大量緊優(yōu)有向雙環(huán)網(wǎng)絡(luò)的存在[4～6]；方木云[7]用仿真的方法發(fā)現(xiàn)了大量緊優(yōu)環(huán)網(wǎng)。2007年，GOMEZ[8]給出了有向雙環(huán)網(wǎng)絡(luò)的最優(yōu)路由算法。有向雙環(huán)網(wǎng)絡(luò)能并行傳輸信息，為了衡量其并行傳輸能力，CHEN[9]給出了寬直徑對其并行傳輸?shù)男蔬M(jìn)行度量。能夠并行輸送信息的網(wǎng)絡(luò)一定具有容錯能力，DHARMASENA[10]和陳業(yè)斌[11]分別給出了有向雙環(huán)網(wǎng)絡(luò)容錯路由算法和容錯容直徑的計算方法。

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

本文針對環(huán)型網(wǎng)絡(luò)這一較有代表性的網(wǎng)絡(luò)結(jié)構(gòu)，針對目前應(yīng)用較為廣泛的有向雙環(huán)網(wǎng)絡(luò)和有向三環(huán)網(wǎng)絡(luò)，就其平均直徑做如下研究。

1) 根據(jù)有向雙環(huán)網(wǎng)絡(luò)的最小路徑圖（L-型瓦），給出計算任意節(jié)點有向雙環(huán)網(wǎng)絡(luò) G(N;r,s)平均直徑的計算公式及算法。

2) 根據(jù)有向三環(huán)網(wǎng)絡(luò)的最小路徑圖（T(N; s1, s2,s3)），給出計算任意節(jié)點有向三環(huán)網(wǎng)絡(luò)平均直徑的計算公式及算法。

3) 通過實驗分析有向環(huán)型網(wǎng)絡(luò)中直徑與平均直徑之間的關(guān)系，通過實驗數(shù)據(jù)對比分析平均直徑在有向環(huán)網(wǎng)傳輸效率上的代表性。

2 有向雙環(huán)網(wǎng)絡(luò)的平均直徑

有向雙環(huán)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)是一個如圖 1(a)所示的有向圖G(N;r,s)，其節(jié)點數(shù)N不小于4，r和s為網(wǎng)絡(luò)的步長，而且滿足關(guān)系式:1≤r ＜s ＜N（r,s為整數(shù)）[1]。L-型瓦是有向雙環(huán)網(wǎng)絡(luò)的最小路徑如圖 1(b)所示。L-型瓦通常是由 a、b、p和 q 4個參數(shù)所決定的L型區(qū)域（矩形為其特例），其中，a、b、p和 q都是整數(shù)，且 a,b≥2，0≤p＜a，0≤q＜b，記為L(N; a,b,p,q)[1]。當(dāng)雙環(huán)網(wǎng)絡(luò)的3個參數(shù)N、r、s的最大公約數(shù)為1，即gcd(N;r,s)=1時，有向雙環(huán)網(wǎng)絡(luò)為一個強連通圖，下文中的研究都是在強連通圖的基礎(chǔ)上進(jìn)行的。

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

圖1 G(12;2,5)的拓?fù)浣Y(jié)構(gòu)及其L-型瓦

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

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

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

2.1 平均直徑的計算公式

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

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

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

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

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

2.2 計算平均直徑的算法

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

算法1 遞歸算法。

該算法的實現(xiàn)過程如下。

1) 令 l?1=N，l0（0≤l0≤N）為正整數(shù)且滿足: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個參數(shù)分別為:a=lu?vlu+1，b=Uu+(v+1)Uu+1，p=lu?(v+1) lu+1，q=Uu?vUu+1。

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

算法2 同余方程算法。

該算法的實現(xiàn)過程如下。

1) 解同余方程:a=min{j|ks=jr(mod N), j ＞ k≥0, j=2,…,N?1}，q={k|ks=ar(mod N), k≥0}。算法思想是設(shè)計一個雙重循環(huán)，外循環(huán)j從2到N?1變化，內(nèi)循環(huán)k從1到j(luò)?1變化，當(dāng)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}。算法思想是設(shè)計一個雙重循環(huán)，外循環(huán)k從2到N?1變化，內(nèi)循環(huán)j從1到k?1變化，當(dāng)ks(mod N)=jr(mod N)時，b=k，p=j。

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

3 有向三環(huán)網(wǎng)絡(luò)的平均直徑

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

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

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

圖2 有向三環(huán)網(wǎng)絡(luò)G(12;1,3,4)的拓?fù)浣Y(jié)構(gòu)

3.1 構(gòu)建最小路徑圖

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

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

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

由定義5和定義6可知，不論是計算有向三環(huán)網(wǎng)絡(luò)的直徑還是平均直徑，都必須求出有向三環(huán)網(wǎng)絡(luò)中任意2節(jié)點之間的最短距離，但從圖2所示的拓?fù)浣Y(jié)構(gòu)中顯然無法直接求出任意2節(jié)點之間的最短距離。為此，將三環(huán)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)映射為二維平面上等價的三叉樹結(jié)構(gòu)，得到三環(huán)網(wǎng)絡(luò)的最小路徑圖。其映射方法如定義7。

定義7 有向三環(huán)網(wǎng)絡(luò)的等價樹T (N;s1,s2,s3)的構(gòu)造方法如下。

1) 選節(jié)點0為三叉樹的根節(jié)點，其所對應(yīng)的層數(shù)為第0層。

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

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

4) 重復(fù)步驟3)，直到三叉樹中不再出現(xiàn)新的節(jié)點為止。

定義7所生成的圖形是一個三叉樹結(jié)構(gòu)，有向三環(huán)網(wǎng)絡(luò) G(12;1,3,4)所對應(yīng)的三叉樹 T(12;1,3,4)結(jié)構(gòu)如圖3所示。

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

定義8 若有向三環(huán)網(wǎng)絡(luò)G(N;s1,s2,s3)中的所有節(jié)點都在其等價的三叉樹T(N;s1,s2,s3)中出現(xiàn)，則稱此三叉樹為滿節(jié)點樹。

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

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

3.2 平均直徑的計算策略

研究表明:有向三環(huán)網(wǎng)絡(luò)的最小路徑圖可以表示為三叉樹結(jié)構(gòu)，其平均直徑為三叉樹中根節(jié)點到其他節(jié)點的平均距離。其依據(jù)如下。

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

證明 由定義7可知，除第0層外，其他層上的節(jié)點至少存在一個父節(jié)點，而它們共同的祖先是根節(jié)點(節(jié)點 0)，因此從根節(jié)點可以到達(dá)任意節(jié)點v(v ≠ 0)。由于樹中的任意節(jié)點 v(v ≠ 0)的值都必須滿足同余方程:v=ms1+ns2+ks3(mod N) (m≥0, n≥0,k≥0)，所以必存在一條從根節(jié)點到節(jié)點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)中，從根節(jié)點出發(fā)經(jīng)過路徑p（p=m[+s1]+n [+s2]+k [+s3]）到達(dá)任意節(jié)點v(v ≠ 0)的路徑長度Lp=m+n+k，且Lp為2節(jié)點間最短路徑的長度。

證明 由三環(huán)網(wǎng)絡(luò) G(N;s1,s2,s3)的拓?fù)浣Y(jié)構(gòu)可知，從節(jié)點0到任意節(jié)點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)，使得從根節(jié)點出發(fā)經(jīng)過路徑p到達(dá)樹中任意節(jié)點v，其路徑p的長度為Lp=m+n+k。假定樹中存在路徑p '，使得從根節(jié)點出發(fā)經(jīng)過路徑p'到達(dá)節(jié)點 v，其路徑長度 Lp'＜Lp，則節(jié)點 v 應(yīng)該出現(xiàn)在更小的層上，后面的層上就不會再出現(xiàn)節(jié)點v?，F(xiàn)在是在2層上都現(xiàn)出了節(jié)點v，這與定義7矛盾，假設(shè)不能成立。所以在樹T(N;s1,s2,s3)中，從根節(jié)點出發(fā)經(jīng)過路徑p到達(dá)節(jié)點v的路徑長度Lp為根節(jié)點到任意節(jié)點v的最短路徑長度。

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

證明 由引理 2可知，在等價樹 T(N;s1,s2,s3)中，根節(jié)點到任一層上節(jié)點v的路徑長度Lp等于其到節(jié)點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)中，若節(jié)點v=ms1+ns2+ks3(mod N)，則從根節(jié)點開始共走m+n+k步到達(dá)v，而每走一步，層數(shù)就會增加一層，因此，節(jié)點 v所位于的層數(shù)l=m+n+k。于是得:節(jié)點v的層數(shù)l等于其最短路徑長度Lp。

定理 3 三叉樹 T(N;s1,s2,s3)是三環(huán)網(wǎng)絡(luò) G(N;s1,s2,s3)所對應(yīng)的最小路徑圖。

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

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

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

3.3 計算平均直徑的算法

根據(jù)上文的分析可知，要計算有向三環(huán)網(wǎng)絡(luò)G(N;s1,s2,s3)的平均直徑，首先必須構(gòu)造出相應(yīng)的等價樹，得到其層數(shù)以及每層上的節(jié)點個數(shù)。其算法如下。

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

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

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

4 實驗結(jié)果及分析

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

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

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

2) 根據(jù)環(huán)網(wǎng)的對稱性，有向雙環(huán)網(wǎng)絡(luò)的第一步長r的變化范圍為1～N/2；第二步長s的變化范圍為r～N?1。有向三環(huán)網(wǎng)絡(luò)的第一步長s1選取為1，第二步長s2變化范圍為1～N?2，第三步長s3選取為N?1。這樣的取值可使得到的每一個無限族都很完整，容易發(fā)現(xiàn)數(shù)據(jù)的變化規(guī)律。

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

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

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

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

對于有向雙環(huán)網(wǎng)絡(luò) G(50;1,s)，其直徑下界為lb=?2=?2=11，從表1中的數(shù)據(jù)可以看出 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，達(dá)到了下界值，根據(jù)定義這些都是最優(yōu)雙環(huán)網(wǎng)絡(luò)。進(jìn)一步分析可知，在該無限族中，平均直徑的最小值是5.9，對應(yīng)的網(wǎng)絡(luò)分別是 G(50;1,15)、G(50;1,19)、G(50;1,22)。由此可見:平均直徑最小的有向雙環(huán)網(wǎng)絡(luò)一定是最優(yōu)的，反之不然。另外，最優(yōu)有向雙環(huán)網(wǎng)絡(luò)的平均直徑之間存在較大的差值:(50;1,17)?d(50;1,15)=8.82?5.9=2.92。從表中數(shù)據(jù)還可以看出相同有向雙環(huán)網(wǎng)絡(luò)的平均直徑約等于直徑的一半。

根據(jù)實驗數(shù)據(jù)分析得:有向三環(huán)網(wǎng)絡(luò) G(N;s1,s2,s3)在 4≤N≤86的區(qū)間內(nèi)滿足:d(N;s1,s2,s3)≥?1，當(dāng)N＞86時，其下界的分布是一個分段函數(shù)，目前還沒能找到其分布規(guī)律。對于有向三環(huán)網(wǎng)絡(luò)G(50;1,s,49)，其直徑下界為lb=?1 =8，從表 1中的數(shù)據(jù)可以看出 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á)到了下界值，它們都是最優(yōu)網(wǎng)絡(luò)。進(jìn)一步分析可知，在該無限族中，最小的平均直徑為d(50;1,20,49)=4.4。由此可知:平均直徑最小的有向三環(huán)網(wǎng)絡(luò)一定是最優(yōu)的，反之不然。從表中數(shù)據(jù)還可以看出有向三環(huán)網(wǎng)絡(luò)的平均直徑約等于其直徑的一半。

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

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

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

5 結(jié)束語

通過對有向環(huán)網(wǎng)平均直徑的研究，筆者發(fā)現(xiàn)同一網(wǎng)絡(luò)的平均直徑與直徑之間存在著一定的關(guān)系:同一網(wǎng)絡(luò)的平均直徑約等于直徑的一半；在一個無限族中，當(dāng)某網(wǎng)絡(luò)的直徑取得最小值時，其平均直徑不一定取得最小值，有時甚至相差很多；但平均直徑最小的網(wǎng)絡(luò)其直徑一定也取最小值，此時的網(wǎng)絡(luò)傳輸效率是最高的，因此，稱此類網(wǎng)絡(luò)為雙優(yōu)網(wǎng)絡(luò)。以前在設(shè)計網(wǎng)絡(luò)結(jié)構(gòu)時，通常只是用直徑的大小作為傳輸效率的衡量標(biāo)準(zhǔn)，研究表明就傳輸效率而言，平均直徑比直徑更具有參考價值。因此，平均直徑應(yīng)該成為構(gòu)造環(huán)型網(wǎng)絡(luò)重要的參考依據(jù)之一。

有向雙環(huán)網(wǎng)絡(luò)的直徑存在下界，有向三環(huán)網(wǎng)絡(luò)的直徑在一定的區(qū)間范圍內(nèi)也存在下界。那么，有向環(huán)網(wǎng)的平均直徑是否也存在下界呢？它的存在對計算平均直徑的最小值有著一定的意義，這將成為下一個要攻克的難題。

[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]周建欽.關(guān)于 K緊優(yōu)雙環(huán)網(wǎng)絡(luò)[J].中國科學(xué)技術(shù)大學(xué)學(xué)報, 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]方木云,趙保華,屈玉貴.雙環(huán)網(wǎng)絡(luò)G(N;1,s)的L形瓦仿真算法[J].系統(tǒng)仿真學(xué)報.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]陳業(yè)斌,王建堃,李穎.有向雙環(huán)網(wǎng)絡(luò)的容錯路由及容錯直徑[J].華中科技大學(xué)學(xué)報(自然科學(xué)版),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]方木云, 湯紅霞.非單位步長雙環(huán)網(wǎng)絡(luò)平均直徑的研究[J].華中科技大學(xué)學(xué)報(自然科學(xué)版), 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]邊瓊芳,姜太平,劉輝等.雙環(huán)網(wǎng)絡(luò)平均直徑的研究[J].安徽工業(yè)大學(xué)學(xué)報(自然科學(xué)版),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]邰偉鵬,方木云,徐宏.三環(huán)網(wǎng)絡(luò) TL(N;1,s,s+1)超 L-型瓦仿真算法[J].華中科技大學(xué)(自然科學(xué)版), 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]侯新民, 王天明.分布式三環(huán)網(wǎng)絡(luò)傳輸延遲[J].大連理工大學(xué)學(xué)報,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]陳業(yè)斌.基于二叉樹的有向雙環(huán)網(wǎng)絡(luò)最短路徑算法[J].華中科技大學(xué)學(xué)報(自然科學(xué)版), 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.