局部扭曲立方體在一維陣列光網絡中的路由與波長分配

蔡水英， 鐘一文

(福建農林大學計算機與信息學院, 福建 福州　350002)

?

局部扭曲立方體在一維陣列光網絡中的路由與波長分配

蔡水英， 鐘一文

(福建農林大學計算機與信息學院, 福建 福州350002)

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

關鍵詞：局部扭曲立方體; 一維陣列光網絡; 波分復用; 路由與波長分配; 最大導出子圖; 擁塞

0引言

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

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

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

1預備知識

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

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

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

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

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

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

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

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

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

在光網絡G2中按策略φ實現通信模式G1所需要的波長數記為λφ(G1, G2),BeauquierB等在1997年已經給出了所需波長數與擁塞的關系[13]:

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

2LTQn的最大導出子圖

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

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

假設當k=n-1時命題成立, 下證當k=n時, 命題亦成立.

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

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

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

證明當n=2時, 命題顯然成立.

假設當k=n-1時命題成立, 下證當k=n時, 命題亦成立. 討論m.

證畢.

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

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

3擁塞數

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

當1≤l≤2n-2時,

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

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

詳見圖2.

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

4最優波長數

根據引理3與定理2可得:

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

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

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

情況2x0=1. 當k=0時, 同情況1. 當k=1時, 由定義2可得:

當k≥2時, 同理可得:

證畢.

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

當n為奇數時:

當n為偶數時:

表在上的路由與波長分配

5結語

參考文獻：

[1] 唐矛寧. 丟失網絡若干問題的研究[D]. 上海: 上海大學, 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]. 重慶大學學報(自然科學版), 2006, 29(3): 69-75.

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

(責任編輯： 沈蕓)

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

文獻標識碼：A

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

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

收稿日期:2013-08-02

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

DOI:10.7631/issn.1000-2243.2016.02.0196