無(wú)向雙環(huán)網(wǎng)絡(luò)的是優(yōu)設(shè)計(jì)研究

朱 琦

吉林工商學(xué)院信息工程學(xué)院，吉林長(zhǎng)春 136200

無(wú)向雙環(huán)網(wǎng)絡(luò)的節(jié)點(diǎn)故障出現(xiàn)在保證網(wǎng)絡(luò)節(jié)點(diǎn)間的路由是一個(gè)非常重要的問(wèn)題。如果按照最短的路徑訪問(wèn)方式而映射到直角坐標(biāo)系會(huì)形成最優(yōu)的路由構(gòu)圖CG(N; ±r，±s)，針對(duì)故障節(jié)點(diǎn)的封閉區(qū)和逃選區(qū)，仍然可以進(jìn)行最優(yōu)路由。

1 無(wú)向雙環(huán)網(wǎng)絡(luò)設(shè)計(jì)定理

我們來(lái)舉個(gè)例子，如果a=84,若b=89,u=102；v=68 的話，x=0;y 是基數(shù)并且滿足定理的條件，這時(shí)，x=0,y=3，b-a=5 ≠y,b-a=5 ≠y-2,所以，這樣的形式是不可成立的。

1）雙環(huán)網(wǎng)絡(luò)G（N；r，s）有N個(gè)結(jié)點(diǎn)0，1，2，…，N－1，而且是從每個(gè)結(jié)點(diǎn)i發(fā)出兩條有向邊i→i＋r（m odN）和i→i＋s（modN其中1≤r≠s〈N。有一個(gè)這樣的問(wèn)題：對(duì)于給定的N，如何選取r和s使得G（N；r，s）有最小的直徑呢，我們就根據(jù)r＝1的特殊情形想到一個(gè)方法，并且構(gòu)造出最小直徑是不會(huì)在r＝1的情況下達(dá)到的雙環(huán)網(wǎng)絡(luò)無(wú)限族，同時(shí)指出了錯(cuò)誤；

2）早在1987 年就有人證明一般的雙環(huán)網(wǎng)絡(luò)G（N;r,s）是成立的，而此時(shí)，大家通過(guò)網(wǎng)絡(luò)搜索發(fā)現(xiàn)到，N 是存在的，最小值竟然是450，事實(shí)上d1(450)=36，而且G（450；1,59）是優(yōu)的。有很多方法都可以構(gòu)造出含有奇異無(wú)線子族的緊優(yōu)雙環(huán)的網(wǎng)絡(luò)無(wú)線族是優(yōu)2 種情形發(fā)生的，第一種情況就是已經(jīng)知道某個(gè)奇異緊優(yōu)的雙環(huán)網(wǎng)絡(luò)G(No;ro,so)為了起始的元素緊優(yōu)的雙環(huán)網(wǎng)絡(luò)無(wú)線族，使之其中的一個(gè)奇異無(wú)限子族在起始元素未知的情況下構(gòu)造出一個(gè)含有奇異無(wú)限子族的緊優(yōu)雙環(huán)網(wǎng)絡(luò)無(wú)限族；

3）無(wú)向雙環(huán)網(wǎng)絡(luò)的構(gòu)造簡(jiǎn)單而且具有規(guī)則性、對(duì)稱性和可擴(kuò)性，所以在計(jì)算機(jī)互聯(lián)網(wǎng)可以得到廣泛的應(yīng)用，是非常重要的，它可以用直徑去度量，目前已經(jīng)找到了大量的含有緊優(yōu)的雙環(huán)網(wǎng)絡(luò)無(wú)限族，早在1993 年的時(shí)候，人們就提出關(guān)于給定的K ＞1 并且找出了無(wú)向緊優(yōu)雙環(huán)網(wǎng)絡(luò)的無(wú)限族，對(duì)給定的正整數(shù)n,給出了一個(gè)全新的算法用來(lái)無(wú)向雙環(huán)網(wǎng)絡(luò)的最優(yōu)步長(zhǎng)s,使之無(wú)向雙環(huán)網(wǎng)絡(luò)G(n；±1,±s)的直徑最短，無(wú)向雙環(huán)網(wǎng)絡(luò)G(2t2－B；±1,±s)及無(wú)向雙環(huán)網(wǎng)絡(luò)G(2t2－2；±1,±s)緊優(yōu)的充分必要條件；

4）有一種仿真算法：（1 小邊；s 為大邊；N 為節(jié)點(diǎn)數(shù))但是不足的是利用數(shù)據(jù)庫(kù)去采取中間的結(jié)果，N 很大的時(shí)候計(jì)算時(shí)間就會(huì)長(zhǎng)，不利于N 值緊優(yōu)雙環(huán)網(wǎng)絡(luò)的分析。針對(duì)這個(gè)問(wèn)題，應(yīng)該提出一個(gè)非常有效的仿真法，根據(jù)存取的結(jié)果，再加上這樣的算法很快會(huì)研究到G(N；±1,±s)緊優(yōu)分布的特性計(jì)算出了4 ≤N ≤1 000 當(dāng)中的任意節(jié)點(diǎn)數(shù)N 的緊優(yōu)無(wú)向雙環(huán)網(wǎng)絡(luò)個(gè)數(shù)n；仿真此時(shí)的n-N 緊優(yōu)分布率和n/(N-3)-N 緊優(yōu)分布率；計(jì)算4 ≤N ≤1 000 中不存在緊優(yōu)無(wú)向雙環(huán)網(wǎng)絡(luò)的N 值；

5）雙環(huán)網(wǎng)的尋徑是當(dāng)前關(guān)注較多的課題。主要是關(guān)于同一個(gè)雙環(huán)網(wǎng)在兩個(gè)不同節(jié)點(diǎn)間的運(yùn)算情況,其算法則需要完成的時(shí)間為O(△),其中△是該網(wǎng)絡(luò)的直徑。雙環(huán)網(wǎng)絡(luò)已經(jīng)是一個(gè)很重要的互聯(lián)網(wǎng)絡(luò)結(jié)構(gòu)了，最傳統(tǒng)的優(yōu)尋徑方法并沒(méi)有利用網(wǎng)絡(luò)中同一節(jié)點(diǎn)和不同節(jié)點(diǎn)的最短路徑之間的關(guān)系，所以給的算法不是最優(yōu)的，定義了雙環(huán)網(wǎng)絡(luò)的一種最短路徑—— [+ 1]邊優(yōu)先最短路徑，在這樣的形式下，最短的路徑形式已成為唯一，況且同一個(gè)源節(jié)點(diǎn)和不同目的節(jié)點(diǎn)的最短的路徑存在著遞推的聯(lián)系，并且給出了相應(yīng)的遞推公式。運(yùn)用這個(gè)公式，平均不到兩次的加法運(yùn)算和一次比較就能找到源節(jié)點(diǎn)至所有其它節(jié)點(diǎn)的最短路徑。再利用所得的結(jié)果，源節(jié)點(diǎn)只用儲(chǔ)很少的信息就能經(jīng)過(guò)簡(jiǎn)單的計(jì)算求得到其它節(jié)點(diǎn)的最短路徑。和傳統(tǒng)的方法比較起來(lái)，這種算法已經(jīng)提高了系統(tǒng)的尋徑效率設(shè)n=qh+r,這里1 ≤r ≤h-1,w=「(h-1)/(q+r)；

6）2hn.（雙環(huán)網(wǎng)絡(luò)),(hnD 是如下定義的有向圖：其結(jié)點(diǎn)集是}1,1,0{-=nZnL, 邊集是}10：)(mod),(mod1{-++=ninhiiniiE.設(shè)rhrqhwhrrqhn/)其中，源結(jié)點(diǎn)至目的結(jié)點(diǎn)最短路徑的算法，這樣的算法最多只要2 次的算術(shù)運(yùn)算和一次比較，各結(jié)點(diǎn)沒(méi)有必要先存儲(chǔ)網(wǎng)絡(luò)中其他信息，而是可以提出新的緊優(yōu)雙環(huán)網(wǎng)絡(luò)無(wú)限族的構(gòu)造方法，這種構(gòu)造不含k(0 ≤k ≤m)緊優(yōu)雙環(huán)網(wǎng)絡(luò)的無(wú)限族。從一個(gè)可以表現(xiàn)具體的實(shí)現(xiàn)L 形瓦出發(fā)，利用h 和y 互素條件，構(gòu)造就能實(shí)現(xiàn)L 形瓦的無(wú)限族，給出的7 緊優(yōu)、8 緊優(yōu)雙環(huán)網(wǎng)絡(luò)的無(wú)限族，并且解決好幾個(gè)關(guān)于緊優(yōu)雙環(huán)網(wǎng)絡(luò)無(wú)限族的公開(kāi)問(wèn)題，雙環(huán)網(wǎng)絡(luò)G(N ;r,s)有N 個(gè)結(jié)點(diǎn) 0,1,2，… ,N - 1,并從從每個(gè)結(jié)點(diǎn)i 發(fā)出兩條有向邊i →i +r(modN)和i →i+s(modN) ,其中 1 ≤r ≠s N。有一個(gè)問(wèn)題是對(duì)于給定的N，如何選取r 和s 使得G(N ;r,s)有最小直徑，這就可以在特殊計(jì)算環(huán)境下使用數(shù)值定義的方法。可以對(duì)最小直徑超出r=1 的的相關(guān)雙環(huán)網(wǎng)絡(luò)無(wú)限族進(jìn)行擴(kuò)大和利用；

7）先利用之前計(jì)算出來(lái)的L-形瓦的四個(gè)參數(shù)及同余方程s_1x+s_2y ≡1(mod n)的一個(gè)解，并且給出有向雙環(huán)網(wǎng)絡(luò)G(n；s_1，s_2)的時(shí)間復(fù)雜性作為常數(shù)的最優(yōu)路由算法。也就是說(shuō)，經(jīng)過(guò)常數(shù)時(shí)間的計(jì)算就可以得到任意兩點(diǎn)間的一條最短的路徑。如果n 是一個(gè)定值整數(shù)，使用數(shù)據(jù)算法對(duì)k-緊優(yōu)的雙環(huán)網(wǎng)絡(luò)G(n；1，s)進(jìn)行運(yùn)算，該種算法公式具有一定的時(shí)間復(fù)雜性O(shè)(k～(2.5)n～(0.25)log n)。利用已知變量L-形瓦的相關(guān)參數(shù)原理和同余方程s_1x+s_2y ≡1(mod n)得出一個(gè)最優(yōu)解，從而可以得知雙環(huán)網(wǎng)絡(luò)G(n；±s_1，±s_2)的時(shí)間復(fù)雜性計(jì)算的最優(yōu)時(shí)間計(jì)算方法。也可以通過(guò)基本常數(shù)運(yùn)算對(duì)兩個(gè)所求點(diǎn)的最短距離進(jìn)行精確化運(yùn)算。

2 結(jié)論

相信很多的企業(yè)在網(wǎng)絡(luò)方面還不是非常完善，目前，計(jì)算機(jī)雙環(huán)網(wǎng)絡(luò)已經(jīng)占據(jù)了不可替代的地位，而且聰明的人們還給出了交錯(cuò)群網(wǎng)絡(luò)AN_n 的一個(gè)最優(yōu)路由算法和洗牌交換置換網(wǎng)絡(luò)SEP_n 的全新路由運(yùn)算方法，并給出了SEP_n 直徑下的一個(gè)人新型發(fā)展途徑。

[1]李靜，王子瀟.最優(yōu)的雙環(huán)網(wǎng)絡(luò)無(wú)限族[J].中國(guó)科學(xué)，2010(4).

[2]沈康.關(guān)于雙環(huán)網(wǎng)絡(luò)的定理[J].中國(guó)科學(xué)技術(shù)學(xué)報(bào)，2012(8).

[3]徐嬌，汪斌，張國(guó)棟.仿真法[M].中國(guó)科學(xué)技術(shù)大學(xué)出版社，2011(7).