雙環Petersen網絡直徑公式及最優路由算法

魏葆雅，劉日華，陳寶興

1.漳州師范學院 計算機科學與工程系，福建 漳州 3630002.江西教育學院 數學與計算機科學系，南昌 330032

雙環Petersen網絡直徑公式及最優路由算法

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

1.漳州師范學院 計算機科學與工程系，福建 漳州 363000
2.江西教育學院 數學與計算機科學系，南昌 330032

1 引言

2 DLCPG（k）的直徑公式

從下面的定理1可以看出文獻[5]中的性質2有誤，性質2給出的雙環Petersen網絡DLCPG(k)的直徑為（其中為向上取整操作符）。

下面先給出同余方程的最小非負解與最小交叉解的定義。設s是一個整數，1≤s＜k。

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

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

（1）如果(a1，a2)是同余方程（1）的非負解，則u+v≤a1+a2。

（2）如果(a1，a2)是同余方程（1）的非負解，且(a1，a2)≠(u，v)，a1+a2=u+v，則u＞a1。

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

定義2設(u，v)是同余方程（1）的最小非負解。稱(-a1，a2)是同余方程（1）的交叉解，如果-a1+a2s≡0(modk)，a1≥0，a2≥0，(-a1，a2)≠(0，0)，且三個坐標點(-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)的最小非負解，且（-5，1），（-3，3），（-1，5），（-12，0），（-10，2），（-8，4），…是同余方程x+5y≡0(mod12)的交叉解，而（-1，5）是同余方程x+5y≡0(mod12)的最小交叉解。

引理1設s是一個大于或等于2的整數。

（1）當k=s2時，同余方程（1）的最小非負解與最小交叉解分別為(0，s)與(-s，1)。

（2）當s2＜k＜s2+s時，即k=s2+r，1≤r＜s，同余方程（1）的最小非負解與最小交叉解分別為(r，s)與(-s，1)。

（3）當k=s2+s時，同余方程（1）的最小非負解與最小交叉解分別為(0，s+1)與(-s，1)。

（4）當s2+s＜k＜s2+2s時，即k=s2+s+r，1≤r＜s，同余方程（1）的最小非負解與最小交叉解分別為(r，s+1)與(-s，1)。

（5）當k=s2+2s時，同余方程（1）的最小非負解與最小交叉解分別為(0，s+2)與(-s，1)。

證明 現在就情形（4）給予證明，其余類似可證。先證(r，s+1)是同余方程（1）的最小非負解。

設(p，q)是同余方程（1）的非負解，分3種情形討論：

（1）當 p＜r時，必有 q＞s+1（否則，0＜p+qs＜r+ (s+1)s=k，這與(p，q)是同余方程（1）的非負解矛盾）。因為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）當 p=r時，必有 q≥s+1（否則，0＜p+qs＜r+ (s+1)s=k，這與(p，q)是同余方程（1）的非負解矛盾）?？芍猵+q≥r+s+1。

（3）當 p＞r時，考慮4種子情形。

①當q=0時，有p=tk，t≥1，此時p+q＞r+s+1。

②當q=1時，有p=s2+r+tk，t≥0，此時p+q＞r+s+1。

③當1＜q＜s+1時，則必有 p≥s+r（否則，0＜p+qs＜ r+s+s×s=k，這與(p，q)是同余方程（1）的非負解矛盾）。因此有 p+q＞r+s+1。

④當q≥s+1時，有 p+q＞r+s+1。

由上可知當(p，q)≠(r，s+1)時，必有 p+q＞r+s+1。由定義可知(r，s+1)是同余方程（1）的最小非負解。

現證(-s，1)是同余方程（1）的最小交叉解。

設(-p，q)是同余方程（1）的交叉解，分3種情形討論：

（1）當q=0時，有 p=tk，t≥1，此時p+q＞s+1。

（2）當 q=1時，則由 -p+s≡0(modk)，可得 p-s≡0(modk)，即p=tk+s，t≥0，可知 p+q≥s+1。

（3）當q＞1時，考慮3種子情形。

①當p=0時，必有q≥s+2（否則，0＜-p+qs≤(s+1)s＜k，這與 (-p，q)是同余方程（1）的交叉解矛盾），此時p+q＞s+1。

②當1≤p＜s時，必有 q≥s+1（否則，0＜-p+qs≤-p+s×s＜r+s+s2=k，這與(-p，q)是同余方程（1）的交叉解矛盾），此時 p+q＞s+1。

③當 p≥s時，有 p+q＞s+1。

由上可知當(-p，q)≠(-s，1)時，必有 p+q＞s+1。由定義可知(-s，1)是同余方程（1）的最小交叉解。證畢。

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

推論 設k，s是正整數，s≥2，k=ps+q，p≥1，0≤q＜s。當s2≤k≤s2+2s時，同余方程（1）的最小非負解與最小交叉解分別為(q，p)與(-s，1)。

引理2設s是一個大于或等于2的整數。用d記雙環網絡G(k;±1，±s)的直徑。

（1）當k=s2時，d=s-1。

（4）當k=s2+s時，d=s。

（6）當k=s2+2s時，d=s。

證明 現在就情形（5）給予證明，其余類似可證。由引理1可知當k=s2+s+r，1≤r＜s，同余方程（1）的最小非負解與最小交叉解分別為(r，s+1)與(-s，1)。

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

定理1設s是一個大于或等于2的整數。用D記雙環Petersen網絡DLCPG(k)的直徑。

（1）當k=s2時，D=s+1。

（4）當k=s2+s時，D=s+2。

（6）當k=s2+2s時，D=s+2。

3 DLCPG（k）的最優單播路由算法

對于無向雙環網絡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)，且等式成立與路徑中邊的順序無關，故可將此路徑記為x1[+1]+x2[-1]+y1[+s]+y2[-s]。

性質1設 x1[+1]+x2[-1]+y1[+s]+y2[-s]是一條從i到j的最短路徑，則x1與x2至少有一個為0，y1與 y2至少有一個為0。

從性質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]。

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

利用文獻[1，7]所得的結論，直接給出無向雙環網絡G(k;±1，±s)的一個路由算法，此路由算法是最優的，文獻[1]已就其一般情形進行嚴格證明。欲求從節點i到節點j的最短路徑，只需求出從節點0到節點(j-i)(modk)的最短路徑。為討論方便起見，以下總設節點0為源節點。

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

這里[( x，y)]=([x]，[y])，[x]表示對x進行四舍五入得到的整數。

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

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

例1找出無向雙環網絡G(9 950;±1，±99)中從節點0到節點4408的最短路徑。

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

步驟2：

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

利用上面的路由算法Routing Algorithm forG(k; ±1，±s)，給出DLCPG(k)的一個最優路由算法。假設節點A(Ar，Ap)向節點B(Br，Bp)發送數據。

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

（2）ifAp=Bp，結束。

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

Else通過公共的相鄰節點進行通信。

因為雙環Petersen圖互聯網絡DLCPG(k)是雙環網絡與Petersen圖的笛卡爾積，且上面算法的第一步是雙環網絡G(k;±1，±s)的最優路由算法，第二步是Petersen圖的最優路由算法，所以所給的算法是DLCPG(k)網絡的一個最優路由算法。下面舉一例予以說明。

例2求 DLCPG(9 950)中從節點 (7，aaaaaa)到節點 (4415，baab00)的最短路徑（參見文獻[5]中圖2的Petersen圖）。

根據算法第一步，利用算法Routing Algorithm for G(k;±1，±s)，找出從雙環網絡G(9 950;±1，±99)中從0到4408的最短路徑為2[+1]-56[+99]。如此找到了從節點(7，aaaaaa)到節點(4415，aaaaaa)的最短路徑。

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

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

4 結論

本文給出了雙環Petersen圖互聯網DLCPG(k)的直徑顯式公式，并利用x+ys≡0(modk)的最小非負解與最小交叉解給出了網絡DLCPG(k)的一個簡單且最優的單播路由算法，并用例子予以說明。

[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]王雷，林亞平.基于超立方體環連接的Petersen圖互聯網絡研究[J].計算機學報，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]劉方愛，劉志勇，喬香珍.一種實用的互連網絡RP（k）及其路由算法[J].中國科學：F輯，2001，44（6）：461-473.

[5]王雷，林亞平，夏巍.雙環Petersen圖互聯網絡及路由算法[J].軟件學報，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]鐘瑋，陳寶興，朱素欽.無向雙環網絡的新直徑公式[J].計算機工程與應用，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

雙環Petersen圖互聯網絡DLCPG（k）是雙環網絡與Petersen圖的笛卡爾積，它具有良好的可擴展性、較短的網絡直徑和簡單的拓撲結構等特性。通過研究其拓撲結構，得到了DLCPG（k）直徑的顯式公式，并給出了該網絡的最優單播路由算法。

互聯網絡；直徑；雙環Petersen圖；最優路由

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.

國家自然科學基金（No.60973150）；福建省自然科學基金（No.2010J01354）。

魏葆雅（1981—），女，講師，主要研究領域為計算機網絡、算法設計與分析；劉日華（1963—），男，副教授，主要研究領域為算法設計與分析；陳寶興（1961—），男，博士，教授，主要研究領域為計算機網絡、算法設計與分析。E-mail：tinawby@hotmail.com

2012-07-20

2012-12-03

1002-8331（2013）05-0081-03