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

魏葆雅，劉日華，陳寶興

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