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

蔡水英， 鐘一文

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

?

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

蔡水英， 鐘一文

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

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

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

0引言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

證畢.

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

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

3擁塞數(shù)

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

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

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

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

詳見圖2.

由于雙向圖可以看成無(wú)向圖, 故有:

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

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

引理7如果x, y=Nk+1(x), r=Nk(y)及s=Nk+1(r)為L(zhǎng)TQn的四個(gè)點(diǎn), 則有x=Nk(s).

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

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

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

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

證畢.

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

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

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

表在上的路由與波長(zhǎng)分配

5結(jié)語(yǔ)

參考文獻(xiàn)：

[1] 唐矛寧. 丟失網(wǎng)絡(luò)若干問(wèn)題的研究[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] 蘇偉, 楊小帆, 唐榮旺, 等. 局部扭曲立方體單播容錯(cuò)路由算法[J]. 重慶大學(xué)學(xué)報(bào)(自然科學(xué)版), 2006, 29(3): 69-75.

[9] 唐榮旺, 楊小帆, 朱策, 等. 一種基于局部扭曲立方體的無(wú)死鎖路由算法[J]. 重慶大學(xué)學(xué)報(bào)(自然科學(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

中圖分類號(hào)：O157.6

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

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

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

收稿日期:2013-08-02

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

DOI:10.7631/issn.1000-2243.2016.02.0196