蔡水英， 鐘一文

(福建農(nóng)林大學(xué)計算機(jī)與信息學(xué)院, 福建 福州　350002)

?

局部扭曲立方體在一維陣列光網(wǎng)絡(luò)中的路由與波長分配

蔡水英， 鐘一文

(福建農(nóng)林大學(xué)計算機(jī)與信息學(xué)院, 福建 福州350002)

摘要：探討局部扭曲立方體LTQn通信模式在一維陣列波分復(fù)用光網(wǎng)絡(luò)中的路由與波長分配問題. 首先通過LTQn的最大導(dǎo)出子圖得到擁塞, 即所需要的最少波長數(shù); 其次給出一個路由與波長分配策略, 從而證明了最優(yōu)波長數(shù)為.

關(guān)鍵詞：局部扭曲立方體; 一維陣列光網(wǎng)絡(luò); 波分復(fù)用; 路由與波長分配; 最大導(dǎo)出子圖; 擁塞

0引言

波分復(fù)用(WDM)技術(shù)由于能充分挖掘光纖的可用帶寬以及低廉的成本, 已經(jīng)成為系統(tǒng)升級擴(kuò)容的主要手段. 在典型的WDM光網(wǎng)絡(luò)中, 每一個光纖鏈路可以同時傳輸一定數(shù)量的不同的波長, 并且每一個波長能獨立傳輸一定的數(shù)據(jù)流. 在WDM光網(wǎng)絡(luò)中的一條連接或者光路是一有序頂點對(x,y), 表示將一數(shù)據(jù)包從源節(jié)點x傳送到目標(biāo)節(jié)點y.

本研究所討論的WDM光網(wǎng)絡(luò)的路由與波長分配(RWA)問題， 是在滿足以下兩個限制條件情況下， 為通信模式的每一條連接尋找一條合適的路徑并為其分配波長, 且使得所需要的波長數(shù)最少: ①波長連續(xù)性的限制， 所選擇的路徑上所有鏈路使用相同的波長; ②不同波長的分配限制上， 使用同一條鏈路的所有光路必須使用不同的波長. 有效地解決RWA問題能夠提高波長信道的使用率, 降低光路的阻塞率和光路通信所需要的波長數(shù), 是光網(wǎng)絡(luò)研究的關(guān)鍵問題之一[1]. 目前, 在光網(wǎng)絡(luò)中實現(xiàn)各種通信模式的路由與波長分配問題已被廣泛研究[2-5].

n維局部扭曲立方體LTQn是由n維超立方體Qn變形而來. 一方面, 其頂點數(shù)及邊數(shù)與超立方體一致, 并保持了超立方體許多優(yōu)越的性質(zhì), 如對稱性、 遞歸性、 高度連通性、 正則性等; 另一方面, 其直徑大約只有超立方體的一半, 在最壞情況下能節(jié)省各處理器之間的通信延遲, 并且存在一條可以應(yīng)用于蟲孔多播路由算法的哈密頓路[6-7]. 局部扭曲立方體作為一種性能優(yōu)良的新型通信模式, 引起眾多學(xué)者的關(guān)注,已有不少相關(guān)的結(jié)果[8-10].

1預(yù)備知識

設(shè){0, 1}n是所有由0和1構(gòu)成的長度為n的二進(jìn)制串的集合. n維超方體Qn的兩個點x, y相連， 當(dāng)且僅當(dāng)x, y的二進(jìn)制串中只有一個比特位不同.

性質(zhì)1g(m)=d(m)2d(m)-1+g(m′)+m′=g(2d(m))+g(m′)+m′, m∈Z+.

性質(zhì)2對任意給定的非負(fù)整數(shù)m1, m2, 有g(shù)(m1+m2)≥g(m1)+g(m2)+min{m1, m2}.

引理2對任意整數(shù)n≥1, 0≤m≤2n, 都有εQn(m)=g(m).

下面給出n維局部扭曲立方體的相關(guān)知識.

定義1[6]n維局部扭曲立方體LTQn(n≥2), 可由下列步驟遞歸獲得:

1) LTQ2是由四個點和四條邊構(gòu)成的圖, 點分別標(biāo)記為00, 01, 10和11, 邊分別是{00, 01}, {01, 11}, {11, 10}和{10, 00};

2) 當(dāng)n≥3時,LTQn由兩個復(fù)制的LTQn-1按下面步驟獲得: 在其中一個LTQn-1的每個點的二進(jìn)制串標(biāo)號的前面添加0, 記為0LTQn-1; 在另一個LTQn-1的每個點的二進(jìn)制串標(biāo)號的前面添加1, 記為1LTQn-1; 而后用一條邊將0LTQn-1中的每個點x=0xn-2xn-3…x0與1LTQn-1中的對應(yīng)點y=1(xn-2+x0)xn-3…x0相連, 其中‘+’表示模2加.

局部扭曲立方體也可以由下面的定義獲得.

在光網(wǎng)絡(luò)G2中按策略φ實現(xiàn)通信模式G1所需要的波長數(shù)記為λφ(G1, G2),BeauquierB等在1997年已經(jīng)給出了所需波長數(shù)與擁塞的關(guān)系[13]:

引理3對?φ, 有λφ(G1, G2)≥Cong(G1, G2, φ)≥Cong(G1, G2).

2LTQn的最大導(dǎo)出子圖

對?V?V(LTQn), 定義Vp=V∩(pLTQn-1), 其中p=0或1.

引理4對任意整數(shù)n≥2, 0≤m≤2n, 都有εLTQn(m)≤g(m).

假設(shè)當(dāng)k=n-1時命題成立, 下證當(dāng)k=n時, 命題亦成立.

ε(V)=ε(V0)+ε(V1)+ε(V0, V1)≤ε(V0)+ε(V1)+min{m0, m1}

由V的任意性可知命題成立.

引理5對任意整數(shù)n≥2, 0≤m≤2n, 都有ε(Vm, n)=g(m).

證明當(dāng)n=2時, 命題顯然成立.

假設(shè)當(dāng)k=n-1時命題成立, 下證當(dāng)k=n時, 命題亦成立. 討論m.

證畢.

顯然, 由引理4與引理5可以得到:

定理1對任意整數(shù)n≥2, 0≤m≤2n, 都有εLTQn(m)=g(m).

3擁塞數(shù)

證明將LTQn中的點按自然數(shù)編號序列PNn依次嵌入到一維陣列Ln中, Ln中的邊從左到右依次標(biāo)號為1, 2, …, 2n-1, 標(biāo)號為l的邊記為el. 由引理5及定理1的證明可知, 對?el∈E(Ln), 都有Cong(LTQn, Ln,PNn, el)=minφCong(LTQn, Ln, φ, el).

當(dāng)1≤l≤2n-2時,

其中第二個等式由性質(zhì)1得到. 所以有:

其中:Cong(LTQ2, L2)=2,Cong(LTQ3, L3)=5,

詳見圖2.

由于雙向圖可以看成無向圖, 故有:

4最優(yōu)波長數(shù)

根據(jù)引理3與定理2可得:

引理7如果x, y=Nk+1(x), r=Nk(y)及s=Nk+1(r)為LTQn的四個點, 則有x=Nk(s).

證明設(shè)x=(xn-1xn-2…xk+1xkxk-1…x0), 分兩種情況討論.

情況1x0=0. 由定義2可得:

情況2x0=1. 當(dāng)k=0時, 同情況1. 當(dāng)k=1時, 由定義2可得:

當(dāng)k≥2時, 同理可得:

證畢.

下面給出一個路由與波長分配算法, 并證明了在該分配策略下所需的波長數(shù)達(dá)到最少.

當(dāng)n為奇數(shù)時:

當(dāng)n為偶數(shù)時:

表在上的路由與波長分配

5結(jié)語

參考文獻(xiàn)：

[1] 唐矛寧. 丟失網(wǎng)絡(luò)若干問題的研究[D]. 上海: 上海大學(xué), 2005.

[2] CHEN Y, SHEN H, LIU F. Wavelength assignment for realizing parallel FFT on regular optical networks[J]. The Journal of Supercomputing, 2006, 36(1): 3-16.

[3] CHEN Y, SHEN H. Routing and wavelength assignment for hypercube in array-based WDM optical networks[J]. Journal of Parallel and Distributed Computing, 2010, 70(1): 59-68.

[4] YU C, YANG X, YANG L,etal. Routing and wavelength assignment for 3-aryn-cube in array-based optical networks[J]. Information Processing Letters, 2012, 112(6): 252-256.

[5] CHEN Y, SHEN H, ZHANG H. Routing and wavelength assignment for hypercube communications embedded on optical chordal ring networks of degrees 3 and 4[J]. Computer Communications, 2011, 34(7): 875-882.

[6] YANG X, EVANS D J, MEGSON G M. The locally twisted cubes[J]. International Journal of Computer Mathematics, 2005, 82(4): 401-413.

[7] YANG X. Locally twisted cubes are 4-pancyclic[J]. Applied Mathematics Letters, 2004, 17(8): 919-925.

[8] 蘇偉, 楊小帆, 唐榮旺, 等. 局部扭曲立方體單播容錯路由算法[J]. 重慶大學(xué)學(xué)報(自然科學(xué)版), 2006, 29(3): 69-75.

[9] 唐榮旺, 楊小帆, 朱策, 等. 一種基于局部扭曲立方體的無死鎖路由算法[J]. 重慶大學(xué)學(xué)報(自然科學(xué)版), 2006, 29(4): 95-100.

[10] HSIEH S Y, TU C J. Constructing edge-disjoint spanning trees in locally twisted cubes[J]. Theoretical Computer Science, 2009, 410(8/9/10): 926-932.

[11] YANG X, EVANS D J, MEGSON G M. Maximum induced subgraph of a recursive circulant[J]. Information Processing Letters, 2005, 95(1): 293-298.

[12] ABDEL-GHAFFAR K A S. Maximum number of edges joining vertices on a cube[J]. Information Processing Letters, 2003, 87(5): 95-99.

[13] BEAUQUIER B, BERMOND J C, GARGANO L,etal. Graph problems arising from wavelength routing in all optical networks[C]//Proceedings of 2nd Workshop on Optics and Computer Science. Paris: Institut National De Recherche En Informatique Et En Automatique, 1997.

(責(zé)任編輯： 沈蕓)

Routing and wavelength assignment for locally twisted cube in linear array optical network

CAI Shuiying, ZHONG Yiwen

(College of Computer and Information, Fujian Agriculture and Forest University, Fuzhou, Fujian 350002, China)

Abstract:We focus on the problem of routing and wavelength assignment for locally twisted cube LTQn communication pattern in linear array wavelength division multiplexing optical network. First, we obtain the congestion which is the minimum number of required wavelengt-hs with the use of the maximum induced subgraph of LTQn. Second, by giving a routing and wav-elength assignment strategy, we show that the optimal number of wavelengths is .

Keywords:locally twisted cube; linear array optical network; wavelength division multiplexing; routing and wavelength assignment; maximum induced subgraph; congestion

中圖分類號：O157.6

文獻(xiàn)標(biāo)識碼：A

基金項目：福建省自然科學(xué)基金資助項目(2013J01216); 福建農(nóng)林大學(xué)青年教師科研基金資助項目(2010023)

通訊作者:蔡水英(1979-), 講師, 主要從事圖論及其應(yīng)用研究， hx0829@sina.com

收稿日期:2013-08-02

文章編號：1000-2243(2016)02-0196-06

DOI:10.7631/issn.1000-2243.2016.02.0196