一種基于廣義Petersen圖的互聯網絡拓撲結構研究

李文升，岳孟田，李同勝，馮志芳

(廊坊師范學院理學院，河北廊坊 065000)

隨著并行處理規模的不斷擴大，為了進一步提高并行計算機的通信效率，人們一直在追求結構簡單，節點度小，網絡直徑小的并行計算機網絡模型。廣義Petersen 圖為3 正則圖，節點的度均為3，因而其可用于構造并行計算機互聯網絡模型。Ohring 等提出了一種k維FPN 網絡(Folded Petersen Network)。一個FPk網絡包括5k個節點，也就是k個Petersen 圖的笛卡爾積[1]。Das 等把Petersen 圖嵌入Hypercube 網絡,構造了一種HP 網絡(Hyper Petersen Network)。因為HP 網絡有非常小的直徑,所以有很好的通訊效率[2]。Ohring 等把Hypercube 與Petersen圖做笛卡爾積，構造了一種FPQn,k網絡并分析了其容錯性和可靠性,給出了路由算法[3]。劉宏英等[4]分析了RCP(n)互聯網絡并給出了基于該網絡的組播路由算法。劉方愛等和邢長明等分別構造了RP(k)和RPC(k)互聯網絡并給出了對應的路由算法[5-7]。主要構造了一類基于廣義Petersen 圖GP(n,k)的互聯網絡結構EGP(k3,k2,k)，并分析了EGP(k3,k2,k)的直徑和良好的通信性能。

1 預備知識

設G=(V,E) 為簡單連通無向圖。對任意的u,v∈V(G),dG(u,v)表示G中(u-v)最短路的長度，在不引起混淆的情況下，簡記為d(u,v)。對任意的v∈V(G)和S?V(G),頂點v到點集S的距離為d(v,S)=min{d(v,u)|u∈S}。對任意的S?V(G)和T?V(G),點集S到點集T的距離為d(S,T)=min{d(u,v)|u∈S,v∈T}。

定義1設n和k為兩個正整數，且n＞2k，廣義Petersen圖P(n,k)共含有2n個頂點，其頂點集為

V(P(n,k))={ui,wi|1≤i≤n}。

邊集為

E(P(n,k))={uiui+1,uiwi,wiwi+k|1≤i≤n,下標模n}[8]。

定義2設n,k,t為正整數，且n＞2k,k＞t，拓展的廣義Petersen 圖(Expended Generalized Petersen Graphs)EGP(n,k,t)共含有2n個頂點，其頂點集為

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,下標模}n。

EGP(n,k,t)的構造方法：對于P(n,t)，在頂點wi和wi+k間連接邊，其中i=pt,0≤p≤且p為整數，下標模n。

2 EGP(t3,t2,t)互聯網絡

討論一類特殊的EGP(n,k,t)，即EGP(t3,t2,t)(t≥2)網絡，設

則U,W,T為EGP(t3,t2,t)的三個圈，t=3 時的EGP(33,32,3)如圖1所示。

圖1 t=3 時的互聯網絡EGP(33,32,3)

此時EGP(33,32,3)的三個圈U,W,T(如圖2所示)具體為

圖2 EGP(33,32,3)中的三個圈U, W, T

引理1設v∈V(EGP(t3,t2,t))，則有d(v,U)≤1。

引理2設v∈V(U)=，

則有d(v,W)≤1+t/2。

證明對任意，不妨設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設v∈V(W)=，則有d(v,T)≤t/2。

證明對任意v∈，不妨設v=(0≤k≤t-1,0≤r≤t-1)。

（1）若r≤t/2，取路，

（2）若r＞t/2，取路，

綜上得證。

引理4設u,v∈V(T)=，則有d(u,v)≤t/2。

證明對任意

不妨設

（1）若q-p≤t/2，取路，

則d(u,v)≤q-p≤t/2。

（2）若q-p＞t/2，取路，

則d(u,v)≤[(t-1)-q]+(p+1)=t-(q-p)＜t/2，綜上得證。

定理1對于任意不小于3 的正整數t，EGP(t3,t2,t)網絡的直徑

diam(EGP(t3,t2,t))=+4。

證明對任意u,v∈V(EGP(t3,t2,t))，根據引理1，2，3，4可有

故EGP(t3,t2,t)網絡的直徑

綜上可有

通過表1，可以看到，EGP(k3,k2,k)網絡與RPC(k)網絡和RP(k)網絡的性能比較，連接度是相同的，但網絡直徑更小，優于文獻[5]中的RP(n)網絡的直徑，也優于[6]中的RPC(k)網絡的直徑。

表1 EGP(k3, k2, k)網絡與RPC(k)和RP(k)的性能比較

3 結論

在廣義Petersen 圖的基礎上進行擴展，通過對廣義Petersen 圖的重構形成了EGP(k3,k2,k)網絡。與其它基于Petersen圖構造的并行計算機互聯網絡(如RPC(k)網絡和RP(k)網絡)相比，EGP(k3,k2,k)網絡具有高度近正則性和小直徑特點，特別是網絡直徑方面，階為，優于RPC(k)網絡和RP(k)網絡的O(n)階網絡直徑值，表明構造的EGP(k3,k2,k)互聯網絡具有更好的通信性能。