Petersen圖互聯(lián)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)研究范文

本站小編為你精心準(zhǔn)備了Petersen圖互聯(lián)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)研究參考范文，愿這些范文能點(diǎn)燃您思維的火花，激發(fā)您的寫作靈感。歡迎深入閱讀并收藏。

摘要:設(shè)計(jì)了一種基于廣義petersen圖的互聯(lián)網(wǎng)絡(luò)拓?fù)?/a>結(jié)構(gòu)，分析證明了該互聯(lián)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)該結(jié)構(gòu)的直徑。通過(guò)分析比較，得出設(shè)計(jì)的互聯(lián)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)具有小連通度和小直徑的特點(diǎn)。

關(guān)鍵詞:互聯(lián)網(wǎng)絡(luò);廣義Petersen圖;網(wǎng)絡(luò)直徑

一個(gè)FPk網(wǎng)絡(luò)包括5k個(gè)節(jié)點(diǎn)，也就是k個(gè)Petersen圖的笛卡爾積[1]。Das等把Petersen圖嵌入Hypercube網(wǎng)絡(luò),構(gòu)造了一種HP網(wǎng)絡(luò)(HyperPe⁃tersenNetwork)。因?yàn)镠P網(wǎng)絡(luò)有非常小的直徑,所以有很好的通訊效率[2]。Ohring等把Hypercube與Petersen圖做笛卡爾積，構(gòu)造了一種FPQn,k網(wǎng)絡(luò)并分析了其容錯(cuò)性和可靠性,給出了路由算法[3]。劉宏英等[4]分析了RCP(n)互聯(lián)網(wǎng)絡(luò)并給出了基于該網(wǎng)絡(luò)的組播路由算法。劉方愛(ài)等和邢長(zhǎng)明等分別構(gòu)造了RP(k)和RPC(k)互聯(lián)網(wǎng)絡(luò)并給出了對(duì)應(yīng)的路由算法[5-7]。主要構(gòu)造了一類基于廣義Petersen圖GP(n,k)的互聯(lián)網(wǎng)絡(luò)結(jié)構(gòu)EGP(k3,k2,k)，并分析了EGP(k3,k2,k)的直徑和良好的通信性能。

1預(yù)備知識(shí)

設(shè)G=(V,E)為簡(jiǎn)單連通無(wú)向圖。對(duì)任意的u,v∈V(G),dG(u,v)表示G中(u-v)最短路的長(zhǎng)度，在不引起混淆的情況下，簡(jiǎn)記為d(u,v)。對(duì)任意的v∈V(G)和S⊆V(G),頂點(diǎn)v到點(diǎn)集S的距離為d(v,S)=min{d(v,u)|u∈S}。對(duì)任意的S⊆V(G)和T⊆V(G),點(diǎn)集S到點(diǎn)集T的距離為d(S,T)=min{d(u,v)|u∈S,v∈T}。定義1設(shè)n和k為兩個(gè)正整數(shù)，且n>2k，廣義Petersen圖P(n,k)共含有2n個(gè)頂點(diǎn)，其頂點(diǎn)集為V(P(n,k))={ui,wi|1≤i≤n}。邊集為E(P(n,k))={uiui+1,uiwi,wiwi+k|1≤i≤n,下標(biāo)模n}[8]。定義2設(shè)n,k,t為正整數(shù)，且n>2k,k>t，拓展的廣義Petersen圖(ExpendedGeneralizedPetersenGraphs)EGP(n,k,t)共含有2n個(gè)頂點(diǎn)，其頂點(diǎn)集為V(EGP(n,k,t))={ui,wi|1≤i≤n},邊集為E(EGP(n,k,t))={uiui+1,uiwi,wiwi+k,wiwi+t|1≤ i ≤ n,下標(biāo)模n}。EGP(n,k,t)的構(gòu)造方法：對(duì)于P(n,t)，在頂點(diǎn)wi和wi+k間連接邊，其中i=pt,0≤p≤éùnt且p為整數(shù)，下標(biāo)模n。

2EGP(t3,t2,t)互聯(lián)網(wǎng)絡(luò)

討論一類特殊的EGP(n,k,t)，即EGP(t3,t2,t)(t≥2)網(wǎng)絡(luò)，設(shè)U=u0u1u2⋯ut3-1u0,W=w0wtw2t⋯wt3-tw0,T=w0wt2w2t2⋯wt3-t2w0。則U,W,T為EGP(t3,t2,t)的三個(gè)圈，t=3時(shí)的EGP(33,32,3)如圖1所示。此時(shí)EGP(33,32,3)的三個(gè)圈U,W,T(如圖2所示)具體為U=u0u1u2⋯u26u0,W=w0w3w6⋯w24w0,T=w0w9w18w0。引理1設(shè)v∈V(EGP(t3,t2,t))，則有d(v,U)≤1。引理2設(shè)v∈V(U)={u0,u1,...,ut3-1}，則有d(v,W)≤1+t/2。證明對(duì)任意v∈{u0,u1,...,ut3-1}，不妨設(shè)v=ukt+r(0≤k≤t2-1,0≤r≤t-1)。（1）若r≤t/2，取(ukt-ukt+r)路，P=uktukt+1ukt+2⋯ukt+r，則d(v,ukt)≤t/2，可得d(v,W)≤d(v,ukt)+d(ukt,wkt)≤t/2+1。（2）若r>t/2，取(ukt+r-u(k+1)t-1)路，P=ukt+rukt+r+1ukt+r+2⋯u(k+1)t，則d(v,u(k+1)t)≤t/2，可得d(v,W)≤d(v,u(k+1)t)+d(u(k+1)t,w(k+1)t)≤t/2+1，綜上得證。引理3設(shè)v∈V(W)={w0,wt,w2t,⋯,wt3-t}，則有d(v,T)≤t/2。證明對(duì)任意v∈{w0,wt,w2t,⋯wt3-t}，不妨設(shè)v=wkt2+rt(0≤k≤t-1,0≤r≤t-1)。（1）若r≤t/2，取(wkt2-wkt2+rt)路，P=wkt2wkt2+twkt2+2t⋯wkt2+rt，則d(v,wkt2)≤t/2，故d(v,T)≤d(v,wkt2)≤t/2。（2）若r>t/2，取(wkt2+rt-w(k+1)t2)路，P=wkt2+rtwkt2+(r+1)twkt2+(r+2)t⋯w(k+1)t2，則d(v,w(k+1)t2)≤t-r≤t/2，故d(v,T)≤d(v,w(k+1)t2)≤t/2，綜上得證。引理4設(shè)u,v∈V(T)={w0,wt2,w2t2,⋯,wt3-t2}，則有d(u,v)≤t/2。證明對(duì)任意u,v∈V(T)={w0,wt2,w2t2,⋯,wt3-t2}，不妨設(shè)u=wpt2,v=wqt2(0≤p,q≤t-1且p≤q)。（1）若q-p≤t/2，取(wpt2-wqt2)路，P=wpt2w(p+1)t2w(p+2)t2⋯wqt2，則d(u,v)≤q-p≤t/2。（2）若q-p>t/2，取(wqt2-wpt2)路，P=wqt2w(q+1)t2w(q+2)t2⋯wt3-t2w0wt2w2t2⋯wpt2，則d(u,v)≤[(t-1)-q]+(p+1)=t-(q-p)<t/2，綜上得證。定理1對(duì)于任意不小于3的正整數(shù)t，EGP(t3,t2,t)網(wǎng)絡(luò)的直徑diam(EGP(t3,t2,t))=5êëúût2+4。證明對(duì)任意u,v∈V(EGP(t3,t2,t))，根據(jù)引理1，2，3，4可有d(u,v)≤d(u,U)+d(U,W)+d(W,T)+t/2+d(W,T)+d(U,W)+d(v,U)≤1+æèçöø÷êëúût2+1+êëúût2+êëúût2+æèçöø÷êëúût2+1+1=5êëúût2+4，故EGP(t3,t2,t)網(wǎng)絡(luò)的直徑diam(EGP(t3,t2,t))≤5êëúût2+4。另一方面，取u=wët2û，v=wët2ût2+ët2û，則d(u,v)=5êëúût2+4，故diam(EGP(t3,t2,t))≥5êëúût2+4，綜上可有diam(EGP(t3,t2,t))=5êëúût2+4。通過(guò)表1，可以看到，EGP(k3,k2,k)網(wǎng)絡(luò)與RPC(k)網(wǎng)絡(luò)和RP(k)網(wǎng)絡(luò)的性能比較，連接度是相同的，但網(wǎng)絡(luò)直徑更小，優(yōu)于文獻(xiàn)[5]中的RP(n)網(wǎng)絡(luò)的直徑，也優(yōu)于[6]中的RPC(k)網(wǎng)絡(luò)的直徑。

3結(jié)論

在廣義Petersen圖的基礎(chǔ)上進(jìn)行擴(kuò)展，通過(guò)對(duì)廣義Petersen圖的重構(gòu)形成了EGP(k3,k2,k)網(wǎng)絡(luò)。與其它基于Petersen圖構(gòu)造的并行計(jì)算機(jī)互聯(lián)網(wǎng)絡(luò)(如RPC(k)網(wǎng)絡(luò)和RP(k)網(wǎng)絡(luò))相比，EGP(k3,k2,k)網(wǎng)絡(luò)具有高度近正則性和小直徑特點(diǎn)，特別是網(wǎng)絡(luò)直徑方面，階為O(n3)，優(yōu)于RPC(k)網(wǎng)絡(luò)和RP(k)網(wǎng)絡(luò)的O(n)階網(wǎng)絡(luò)直徑值，表明構(gòu)造的EGP(k3,k2,k)互聯(lián)網(wǎng)絡(luò)具有更好的通信性能。

作者：李文升 岳孟田 李同勝 馮志芳 單位：廊坊師范學(xué)院理學(xué)院