• <tr id="yyy80"></tr>
  • <sup id="yyy80"></sup>
  • <tfoot id="yyy80"><noscript id="yyy80"></noscript></tfoot>
  • 99热精品在线国产_美女午夜性视频免费_国产精品国产高清国产av_av欧美777_自拍偷自拍亚洲精品老妇_亚洲熟女精品中文字幕_www日本黄色视频网_国产精品野战在线观看 ?

    雙環(huán)Petersen網(wǎng)絡(luò)直徑公式及最優(yōu)路由算法

    2013-07-11 09:35:50魏葆雅劉日華陳寶興
    計算機工程與應(yīng)用 2013年5期
    關(guān)鍵詞:互聯(lián)網(wǎng)絡(luò)雙環(huán)路由

    魏葆雅,劉日華,陳寶興

    1.漳州師范學(xué)院 計算機科學(xué)與工程系,福建 漳州 3630002.江西教育學(xué)院 數(shù)學(xué)與計算機科學(xué)系,南昌 330032

    雙環(huán)Petersen網(wǎng)絡(luò)直徑公式及最優(yōu)路由算法

    魏葆雅1,劉日華2,陳寶興1

    1.漳州師范學(xué)院 計算機科學(xué)與工程系,福建 漳州 363000
    2.江西教育學(xué)院 數(shù)學(xué)與計算機科學(xué)系,南昌 330032

    1 引言

    2 DLCPG(k)的直徑公式

    從下面的定理1可以看出文獻(xiàn)[5]中的性質(zhì)2有誤,性質(zhì)2給出的雙環(huán)Petersen網(wǎng)絡(luò)DLCPG(k)的直徑為(其中為向上取整操作符)。

    下面先給出同余方程的最小非負(fù)解與最小交叉解的定義。設(shè)s是一個整數(shù),1≤s<k。

    定義1稱(a1,a2)是同余方程

    的非負(fù)解,如果a1+a2s≡0(modk),a1≥0,a2≥0且(a1,a2)≠(0,0)。稱(u,v)是同余方程(1)的最小非負(fù)解,如果(u,v)是同余方程(1)的非負(fù)解且滿足以下條件:

    (1)如果(a1,a2)是同余方程(1)的非負(fù)解,則u+v≤a1+a2。

    (2)如果(a1,a2)是同余方程(1)的非負(fù)解,且(a1,a2)≠(u,v),a1+a2=u+v,則u>a1。

    例如,容易驗證(4,1),(2,3),(0,5),(8,2),(4,6),…是同余方程 x+6y≡0(mod10)的非負(fù)解,而(4,1)是方程x+6y≡0(mod10)的最小非負(fù)解。

    定義2設(shè)(u,v)是同余方程(1)的最小非負(fù)解。稱(-a1,a2)是同余方程(1)的交叉解,如果-a1+a2s≡0(modk),a1≥0,a2≥0,(-a1,a2)≠(0,0),且三個坐標(biāo)點(-a1,a2),(0,0),(u,v)不在同一直線上。稱(-a,b)是同余方程(1)的最小交叉解,如果(-a,b)是同余方程(1)的交叉解且滿足以下條件:

    (1)如果(-a1,a2)是同余方程(1)的交叉解,則a+b≤a1+a2。

    (2)如果(-a1,a2)是同余方程(1)的交叉解,且(-a1,a2)≠(-a,b),a1+a2=a+b,則b>a2。

    例如,容易驗證(2,2)是同余方程x+5y≡0(mod12)的最小非負(fù)解,且(-5,1),(-3,3),(-1,5),(-12,0),(-10,2),(-8,4),…是同余方程x+5y≡0(mod12)的交叉解,而(-1,5)是同余方程x+5y≡0(mod12)的最小交叉解。

    引理1設(shè)s是一個大于或等于2的整數(shù)。

    (1)當(dāng)k=s2時,同余方程(1)的最小非負(fù)解與最小交叉解分別為(0,s)與(-s,1)。

    (2)當(dāng)s2<k<s2+s時,即k=s2+r,1≤r<s,同余方程(1)的最小非負(fù)解與最小交叉解分別為(r,s)與(-s,1)。

    (3)當(dāng)k=s2+s時,同余方程(1)的最小非負(fù)解與最小交叉解分別為(0,s+1)與(-s,1)。

    (4)當(dāng)s2+s<k<s2+2s時,即k=s2+s+r,1≤r<s,同余方程(1)的最小非負(fù)解與最小交叉解分別為(r,s+1)與(-s,1)。

    (5)當(dāng)k=s2+2s時,同余方程(1)的最小非負(fù)解與最小交叉解分別為(0,s+2)與(-s,1)。

    證明 現(xiàn)在就情形(4)給予證明,其余類似可證。先證(r,s+1)是同余方程(1)的最小非負(fù)解。

    設(shè)(p,q)是同余方程(1)的非負(fù)解,分3種情形討論:

    (1)當(dāng) p<r時,必有 q>s+1(否則,0<p+qs<r+ (s+1)s=k,這與(p,q)是同余方程(1)的非負(fù)解矛盾)。因為s+p-r+(q-s-2)s≡0(modk)且0<s+p-r<s,所以有q-s-2>s??芍?p+q≥q>2s+2>r+s+1。

    (2)當(dāng) p=r時,必有 q≥s+1(否則,0<p+qs<r+ (s+1)s=k,這與(p,q)是同余方程(1)的非負(fù)解矛盾)??芍猵+q≥r+s+1。

    (3)當(dāng) p>r時,考慮4種子情形。

    ①當(dāng)q=0時,有p=tk,t≥1,此時p+q>r+s+1。

    ②當(dāng)q=1時,有p=s2+r+tk,t≥0,此時p+q>r+s+1。

    ③當(dāng)1<q<s+1時,則必有 p≥s+r(否則,0<p+qs< r+s+s×s=k,這與(p,q)是同余方程(1)的非負(fù)解矛盾)。因此有 p+q>r+s+1。

    ④當(dāng)q≥s+1時,有 p+q>r+s+1。

    由上可知當(dāng)(p,q)≠(r,s+1)時,必有 p+q>r+s+1。由定義可知(r,s+1)是同余方程(1)的最小非負(fù)解。

    現(xiàn)證(-s,1)是同余方程(1)的最小交叉解。

    設(shè)(-p,q)是同余方程(1)的交叉解,分3種情形討論:

    (1)當(dāng)q=0時,有 p=tk,t≥1,此時p+q>s+1。

    (2)當(dāng) q=1時,則由 -p+s≡0(modk),可得 p-s≡0(modk),即p=tk+s,t≥0,可知 p+q≥s+1。

    (3)當(dāng)q>1時,考慮3種子情形。

    ①當(dāng)p=0時,必有q≥s+2(否則,0<-p+qs≤(s+1)s<k,這與 (-p,q)是同余方程(1)的交叉解矛盾),此時p+q>s+1。

    ②當(dāng)1≤p<s時,必有 q≥s+1(否則,0<-p+qs≤-p+s×s<r+s+s2=k,這與(-p,q)是同余方程(1)的交叉解矛盾),此時 p+q>s+1。

    ③當(dāng) p≥s時,有 p+q>s+1。

    由上可知當(dāng)(-p,q)≠(-s,1)時,必有 p+q>s+1。由定義可知(-s,1)是同余方程(1)的最小交叉解。證畢。

    由引理1可得下面的推論。

    推論 設(shè)k,s是正整數(shù),s≥2,k=ps+q,p≥1,0≤q<s。當(dāng)s2≤k≤s2+2s時,同余方程(1)的最小非負(fù)解與最小交叉解分別為(q,p)與(-s,1)。

    引理2設(shè)s是一個大于或等于2的整數(shù)。用d記雙環(huán)網(wǎng)絡(luò)G(k;±1,±s)的直徑。

    (1)當(dāng)k=s2時,d=s-1。

    (4)當(dāng)k=s2+s時,d=s。

    (6)當(dāng)k=s2+2s時,d=s。

    證明 現(xiàn)在就情形(5)給予證明,其余類似可證。由引理1可知當(dāng)k=s2+s+r,1≤r<s,同余方程(1)的最小非負(fù)解與最小交叉解分別為(r,s+1)與(-s,1)。

    由引理2可得下面的定理1。

    定理1設(shè)s是一個大于或等于2的整數(shù)。用D記雙環(huán)Petersen網(wǎng)絡(luò)DLCPG(k)的直徑。

    (1)當(dāng)k=s2時,D=s+1。

    (4)當(dāng)k=s2+s時,D=s+2。

    (6)當(dāng)k=s2+2s時,D=s+2。

    3 DLCPG(k)的最優(yōu)單播路由算法

    對于無向雙環(huán)網(wǎng)絡(luò)G(k;±1,±s),從點i到點(i+1)(modk)的邊稱為[+1]邊,點i到點(i-1)(modk)的邊稱為[-1]邊,點i到點(i+s)(modk)的邊稱為[+s]邊,點i到點(i-s)(modk)的邊稱為[-s]邊。若一條從點i到點 j的路徑,它包含x1條[+1]邊,x2條[-1]邊,y1條[+s]邊,y2條[-s]邊,則有j≡(i+x1-x2+y1s-y2s)(modk),且等式成立與路徑中邊的順序無關(guān),故可將此路徑記為x1[+1]+x2[-1]+y1[+s]+y2[-s]。

    性質(zhì)1設(shè) x1[+1]+x2[-1]+y1[+s]+y2[-s]是一條從i到j(luò)的最短路徑,則x1與x2至少有一個為0,y1與 y2至少有一個為0。

    從性質(zhì)1知從i到 j的最短路徑使用的邊僅含[+1]邊與[+s]邊,或僅含[-1]邊與[+s]邊,或僅含[+1]邊與[-s]邊,或僅含[-1]邊與[-s]邊。為了方便起見,把路徑x1[±1]+ x2[±s]用(±x1)[+1]+(±x2)[+s]表示。比如用6[+1]+(-3)[+7]表示6[+1]+3[-7]。

    路由算法是影響計算機網(wǎng)絡(luò)通信的重要因素。文獻(xiàn)[5]給出了DLCPG(k)的單播路由算法,然而此算法所找到的路徑一般情況下并不是最短的。例如:按照文獻(xiàn)[5]的算法(2),2),無向雙環(huán)網(wǎng)絡(luò)G(9 950;±1,±99)中從節(jié)點0到節(jié)點4408應(yīng)走的路徑為(-47)[+1]+45[+99],其路徑長度為92。事實上按照下面所給的算法Routing Algorithm for G(k;±1,±s),找到的最短路徑為2[+1]+56[-99],其長度為58。

    利用文獻(xiàn)[1,7]所得的結(jié)論,直接給出無向雙環(huán)網(wǎng)絡(luò)G(k;±1,±s)的一個路由算法,此路由算法是最優(yōu)的,文獻(xiàn)[1]已就其一般情形進(jìn)行嚴(yán)格證明。欲求從節(jié)點i到節(jié)點j的最短路徑,只需求出從節(jié)點0到節(jié)點(j-i)(modk)的最短路徑。為討論方便起見,以下總設(shè)節(jié)點0為源節(jié)點。

    Routing Algorithm forG(k;±1,±s):利用引理1,可以得到同余式x+ys≡0(modk)的最小非負(fù)解(u,v)與最小交叉解(-a,b)。下面的算法將給出從0到t的最短路徑。

    這里[( x,y)]=([x],[y]),[x]表示對x進(jìn)行四舍五入得到的整數(shù)。

    步驟2 P1:=a1[+1]+b1[+s]

    P1,P2,P3,P4,P5這5條路徑中的最短者就是從節(jié)點0到節(jié)點t的最短路徑。

    例1找出無向雙環(huán)網(wǎng)絡(luò)G(9 950;±1,±99)中從節(jié)點0到節(jié)點4408的最短路徑。

    因為9 950=992+99+50,利用引理1,(4)的結(jié)論:同余方程(1)的最小非負(fù)解與最小交叉解分別為(50,100)與(-99,1)。由算法的步驟1:

    步驟2:

    所以從節(jié)點0到節(jié)點4408的最短路徑為P2=2[+1]-56[+99],其長度為58。

    利用上面的路由算法Routing Algorithm forG(k; ±1,±s),給出DLCPG(k)的一個最優(yōu)路由算法。假設(shè)節(jié)點A(Ar,Ap)向節(jié)點B(Br,Bp)發(fā)送數(shù)據(jù)。

    {利用上面的算法Routing Algorithm forG(k;±1,±s),找出從0到(Br-Ar)(mod k)的最短路徑,即可找到從A(Ar,Ap)到節(jié)點C(Br,Ap)的最短路徑。}

    (2)ifAp=Bp,結(jié)束。

    Else ifC(Br,Ap)與B(Br,Bp)是相鄰節(jié)點,可以直接通信。

    Else通過公共的相鄰節(jié)點進(jìn)行通信。

    因為雙環(huán)Petersen圖互聯(lián)網(wǎng)絡(luò)DLCPG(k)是雙環(huán)網(wǎng)絡(luò)與Petersen圖的笛卡爾積,且上面算法的第一步是雙環(huán)網(wǎng)絡(luò)G(k;±1,±s)的最優(yōu)路由算法,第二步是Petersen圖的最優(yōu)路由算法,所以所給的算法是DLCPG(k)網(wǎng)絡(luò)的一個最優(yōu)路由算法。下面舉一例予以說明。

    例2求 DLCPG(9 950)中從節(jié)點 (7,aaaaaa)到節(jié)點 (4415,baab00)的最短路徑(參見文獻(xiàn)[5]中圖2的Petersen圖)。

    根據(jù)算法第一步,利用算法Routing Algorithm for G(k;±1,±s),找出從雙環(huán)網(wǎng)絡(luò)G(9 950;±1,±99)中從0到4408的最短路徑為2[+1]-56[+99]。如此找到了從節(jié)點(7,aaaaaa)到節(jié)點(4415,aaaaaa)的最短路徑。

    此時節(jié)點 (4415,aaaaaa)與 (4415,baab00)在同一Petersen圖。因為aaaaaa≠baab00,從Petersen圖知baaa00 是aaaaaa與baab00的公共鄰點,所以有(4415,aaaaaa)—>(4415,baaa00)—>(4415,baab00)。

    綜上可知從節(jié)點(7,v1)到節(jié)點(4415,u2)的最短路徑為:(7,aaaaaa)—>(8,aaaaaa)—>(9,aaaaaa)—>(9860,aaaaaa)—>(9761,aaaaaa)—>(9662,aaaaaa)—>…—>(4415,aaaaaa)—>(4415,baaa00)—>(4415,baab00),路徑長度為60。

    4 結(jié)論

    本文給出了雙環(huán)Petersen圖互聯(lián)網(wǎng)DLCPG(k)的直徑顯式公式,并利用x+ys≡0(modk)的最小非負(fù)解與最小交叉解給出了網(wǎng)絡(luò)DLCPG(k)的一個簡單且最優(yōu)的單播路由算法,并用例子予以說明。

    [1]Chen B X,Meng J X,Xiao W J.A constant time optimal routing algorithm for undirected double-loop networks[C]// MSN'05.Berlin:Springer-Verlag,2005,3794:308-316.

    [2]王雷,林亞平.基于超立方體環(huán)連接的Petersen圖互聯(lián)網(wǎng)絡(luò)研究[J].計算機學(xué)報,2005,28(3):409-413.

    [3]OhringS,DasS K.FoldedPetersencubenetworks:new competitors for the hypercubes[J].IEEE Transactions on Parallel and Distributed Systems,1996,7(2):151-168.

    [4]劉方愛,劉志勇,喬香珍.一種實用的互連網(wǎng)絡(luò)RP(k)及其路由算法[J].中國科學(xué):F輯,2001,44(6):461-473.

    [5]王雷,林亞平,夏巍.雙環(huán)Petersen圖互聯(lián)網(wǎng)絡(luò)及路由算法[J].軟件學(xué)報,2006,17(5):1115-1123.

    [6]Chen B X,Meng J X,Xiao W J.A diameter formula for an undirected double-loop network[J].Ars Combinatoria,2009,90:395-404.

    [7]鐘瑋,陳寶興,朱素欽.無向雙環(huán)網(wǎng)絡(luò)的新直徑公式[J].計算機工程與應(yīng)用,2010,46(32):84-87.

    WEI Baoya1,LIU Rihua2,CHEN Baoxing1

    1.Department of Computer Science and Engineering,Zhangzhou Normal University,Zhangzhou,Fujian 363000,China
    2.Department of Mathematics and Computer Science,Jiangxi Institute of Education,Nanchang 330032,China

    The Double-Loops Connected Petersen Graph network DLCPG(k)is Cartesian product of a double-loop network and the Petersen graph.It has good extensibility,short diameter and simple topology structure.By studying its topology structure,the diameter formula of DLCPG(k)is obtained,and a simple and optimal routing algorithm for the DLCPG(k)is given.

    interconnection networks;diameter;double-loops connected Petersen graph;optimal routing

    雙環(huán)Petersen圖互聯(lián)網(wǎng)絡(luò)DLCPG(k)是雙環(huán)網(wǎng)絡(luò)與Petersen圖的笛卡爾積,它具有良好的可擴展性、較短的網(wǎng)絡(luò)直徑和簡單的拓?fù)浣Y(jié)構(gòu)等特性。通過研究其拓?fù)浣Y(jié)構(gòu),得到了DLCPG(k)直徑的顯式公式,并給出了該網(wǎng)絡(luò)的最優(yōu)單播路由算法。

    互聯(lián)網(wǎng)絡(luò);直徑;雙環(huán)Petersen圖;最優(yōu)路由

    A

    TP393

    10.3778/j.issn.1002-8331.1207-0295

    WEI Baoya,LIU Rihua,CHEN Baoxing.Diameter formula and optimal routing algorithm for double-loops Petersen networks.Computer Engineering and Applications,2013,49(5):81-83.

    國家自然科學(xué)基金(No.60973150);福建省自然科學(xué)基金(No.2010J01354)。

    魏葆雅(1981—),女,講師,主要研究領(lǐng)域為計算機網(wǎng)絡(luò)、算法設(shè)計與分析;劉日華(1963—),男,副教授,主要研究領(lǐng)域為算法設(shè)計與分析;陳寶興(1961—),男,博士,教授,主要研究領(lǐng)域為計算機網(wǎng)絡(luò)、算法設(shè)計與分析。E-mail:tinawby@hotmail.com

    2012-07-20

    2012-12-03

    1002-8331(2013)05-0081-03

    猜你喜歡
    互聯(lián)網(wǎng)絡(luò)雙環(huán)路由
    聲 明
    鐵道建筑(2022年8期)2022-12-06 09:46:34
    聲 明
    鐵道建筑(2022年4期)2022-12-01 11:49:18
    聲 明
    鐵道建筑(2021年12期)2021-12-05 10:01:47
    探究路由與環(huán)路的問題
    “單環(huán)學(xué)習(xí)”與“雙環(huán)學(xué)習(xí)”
    電流雙環(huán)控制的LCL單相并網(wǎng)逆變器逆變研究
    聚丙烯成核劑雙環(huán)[2.2.1]-庚烷-2,3-二羧酸鈉的合成
    雙環(huán)法結(jié)合雙“V”形乳腺切除法在乳房肥大整形術(shù)中的應(yīng)用
    PRIME和G3-PLC路由機制對比
    WSN中基于等高度路由的源位置隱私保護(hù)
    計算機工程(2014年6期)2014-02-28 01:25:54
    长宁县| 思茅市| 大渡口区| 叶城县| 凯里市| 勐海县| 涿州市| 赫章县| 灌云县| 化隆| 大庆市| 仁布县| 濮阳市| 化隆| 和平区| 陈巴尔虎旗| 通许县| 顺义区| 临沭县| 通道| 扶风县| 贵港市| 淮南市| 平陆县| 宝鸡市| 固安县| 麟游县| 绥棱县| 贵德县| 仙桃市| 浦东新区| 阿合奇县| 巴马| 漾濞| 湖口县| 合水县| 泸州市| 邯郸市| 从化市| 通渭县| 秦安县|