關(guān)于有向環(huán)網(wǎng)平均直徑的研究

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

（1.安徽工業(yè)大學(xué) 計(jì)算機(jī)學(xué)院，安徽 馬鞍山 243002；2.馬鞍山師范高等專科學(xué)校 理工系，安徽 馬鞍山 243041）

1 引言

從目前網(wǎng)絡(luò)運(yùn)營(yíng)商為大用戶提供的光纖接入網(wǎng)狀況來(lái)看，對(duì)于某些大型用戶，比如電力、電信、有線電視等，其主干網(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)實(shí)世界中的應(yīng)用提供了可能和保障，環(huán)網(wǎng)的通信性能與其拓?fù)浣Y(jié)構(gòu)密切相關(guān)。一個(gè)結(jié)構(gòu)不好的環(huán)網(wǎng)往往會(huì)出現(xiàn)信息傳輸延遲較大、通信效率和容錯(cuò)效率低下等現(xiàn)象。為了更好地發(fā)揮環(huán)網(wǎng)在各行業(yè)的潛力，必須在設(shè)計(jì)其結(jié)構(gòu)時(shí)對(duì)其進(jìn)行優(yōu)化。

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

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

近年來(lái)，關(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ò)和容錯(cuò)等問(wèn)題上。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-型瓦的定義。有了最小路徑圖，直徑的計(jì)算變得更加容易。接下來(lái)，人們用數(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]給出了寬直徑對(duì)其并行傳輸?shù)男蔬M(jìn)行度量。能夠并行輸送信息的網(wǎng)絡(luò)一定具有容錯(cuò)能力，DHARMASENA[10]和陳業(yè)斌[11]分別給出了有向雙環(huán)網(wǎng)絡(luò)容錯(cuò)路由算法和容錯(cuò)容直徑的計(jì)算方法。

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

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

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

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

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

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

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

定義1 對(duì)于任意給定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ò)的一個(gè)無(wú)限族。

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

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

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

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

2.1 平均直徑的計(jì)算公式

研究表明:在有向雙環(huán)網(wǎng)絡(luò)中，與距離相關(guān)的問(wèn)題都可以利用有向雙環(huán)網(wǎng)絡(luò)的最小路徑圖—L-型瓦來(lái)得到[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個(gè)參數(shù)表示，如定理1所描述。

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

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

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

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

2.2 計(jì)算平均直徑的算法

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

算法1 遞歸算法。

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

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個(gè)參數(shù)分別為:a=lu?vlu+1，b=Uu+(v+1)Uu+1，p=lu?(v+1) lu+1，q=Uu?vUu+1。

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

算法2 同余方程算法。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

根據(jù)有向三環(huán)網(wǎng)絡(luò)的對(duì)稱性，任意節(jié)點(diǎn)x到節(jié)點(diǎn)y之間的距離等于節(jié)點(diǎn)0到節(jié)點(diǎn)y ? x(x＜y)之間的距離。因此，研究三環(huán)網(wǎng)絡(luò)的相關(guān)問(wèn)題，只需研究節(jié)點(diǎn)0到其他任意節(jié)點(diǎn)之間的相關(guān)問(wèn)題。所以在三叉樹(shù)的根節(jié)點(diǎn)上放置了節(jié)點(diǎn) 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 平均直徑的計(jì)算策略

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

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

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

引理2 在三叉樹(shù)T(N;s1,s2,s3)中，從根節(jié)點(diǎn)出發(fā)經(jīng)過(guò)路徑p（p=m[+s1]+n [+s2]+k [+s3]）到達(dá)任意節(jié)點(diǎn)v(v ≠ 0)的路徑長(zhǎng)度Lp=m+n+k，且Lp為2節(jié)點(diǎn)間最短路徑的長(zhǎng)度。

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

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

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

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

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

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

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

3.3 計(jì)算平均直徑的算法

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

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

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

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

4 實(shí)驗(yàn)結(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)的平均直徑也取最小值，此時(shí)的環(huán)網(wǎng)從傳輸效率上來(lái)看應(yīng)該是最優(yōu)中的優(yōu)秀者，因此，將其定義為雙優(yōu)網(wǎng)絡(luò)。雙優(yōu)網(wǎng)絡(luò)也應(yīng)該存在三環(huán)網(wǎng)絡(luò)的無(wú)限族中。

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

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

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

3) 存放到后臺(tái)數(shù)據(jù)庫(kù)中的參數(shù)有:節(jié)點(diǎn)值 N，步長(zhǎng)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組無(wú)限族的直徑和平均直徑的部分實(shí)驗(yàn)數(shù)據(jù)。為了簡(jiǎn)化表中數(shù)據(jù)，分別用、、)和(50)來(lái)替代)、d()和()。根據(jù)實(shí)驗(yàn)數(shù)據(jù)繪制的仿真圖如圖4和圖5所示。

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

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

對(duì)于有向雙環(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)一步分析可知，在該無(wú)限族中，平均直徑的最小值是5.9，對(duì)應(yīng)的網(wǎng)絡(luò)分別是 G(50;1,15)、G(50;1,19)、G(50;1,22)。由此可見(jiàn):平均直徑最小的有向雙環(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í)驗(yàn)數(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í)，其下界的分布是一個(gè)分段函數(shù)，目前還沒(méi)能找到其分布規(guī)律。對(duì)于有向三環(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)一步分析可知，在該無(wú)限族中，最小的平均直徑為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ò)無(wú)限族G(50;3,s)的直徑與平均直徑的分布，圖5所示為有向三環(huán)網(wǎng)絡(luò)無(wú)限族G(50;1,s,49)的直徑與平均直徑的分布。從圖4和圖5中可以看出:不論有向雙環(huán)網(wǎng)絡(luò)還是有向三環(huán)網(wǎng)絡(luò)，在一個(gè)無(wú)限族內(nèi)，直徑和平均直徑的分布都呈軸對(duì)稱圖形；在一個(gè)無(wú)限族內(nèi)，直徑到達(dá)下界的網(wǎng)絡(luò)個(gè)數(shù)往往要大于平均直徑達(dá)到最小值的網(wǎng)絡(luò)個(gè)數(shù)；在一個(gè)無(wú)限族內(nèi)，平均直徑的變化規(guī)律與直徑大致相同，但又不完全相同。

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

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

5 結(jié)束語(yǔ)

通過(guò)對(duì)有向環(huán)網(wǎng)平均直徑的研究，筆者發(fā)現(xiàn)同一網(wǎng)絡(luò)的平均直徑與直徑之間存在著一定的關(guān)系:同一網(wǎng)絡(luò)的平均直徑約等于直徑的一半；在一個(gè)無(wú)限族中，當(dāng)某網(wǎng)絡(luò)的直徑取得最小值時(shí)，其平均直徑不一定取得最小值，有時(shí)甚至相差很多；但平均直徑最小的網(wǎng)絡(luò)其直徑一定也取最小值，此時(shí)的網(wǎng)絡(luò)傳輸效率是最高的，因此，稱此類網(wǎng)絡(luò)為雙優(yōu)網(wǎng)絡(luò)。以前在設(shè)計(jì)網(wǎng)絡(luò)結(jié)構(gòu)時(shí)，通常只是用直徑的大小作為傳輸效率的衡量標(biāo)準(zhǔn)，研究表明就傳輸效率而言，平均直徑比直徑更具有參考價(jià)值。因此，平均直徑應(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)的平均直徑是否也存在下界呢？它的存在對(duì)計(jì)算平均直徑的最小值有著一定的意義，這將成為下一個(gè)要攻克的難題。

[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].中國(guó)科學(xué)技術(shù)大學(xué)學(xué)報(bào), 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é)報(bào).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ò)的容錯(cuò)路由及容錯(cuò)直徑[J].華中科技大學(xué)學(xué)報(bào)(自然科學(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]方木云, 湯紅霞.非單位步長(zhǎng)雙環(huán)網(wǎng)絡(luò)平均直徑的研究[J].華中科技大學(xué)學(xué)報(bào)(自然科學(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é)報(bào)(自然科學(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é)報(bào),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è)斌.基于二叉樹(shù)的有向雙環(huán)網(wǎng)絡(luò)最短路徑算法[J].華中科技大學(xué)學(xué)報(bào)(自然科學(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.