ＷＤＭ雙環網上Ｈｏｐｆｉｅｌｄ網的波長分配
2007-01-01 00:00:00夏磊劉方愛
計算機應用研究 2007年5期
摘要：基于WDM雙環網，討論了在其上實現Hopfield通信模式的波長分配問題，提出了一種路由策略及波長分配方案。在此基礎上給出了實現Hopfield算法所需的波長數。
關鍵詞：并行霍普菲爾德算法；波長分配；波分復用雙環網；網絡嵌入
中圖分類號：TP393文獻標志碼：A
文章編號：1001－3695(2007)05－0256－03
0引言
Hopfield神經網絡是人工神經網絡中應用最為廣泛的一種網絡模型。它已被應用于聯想記憶、優化計算、模式識別等眾多領域。采用并行的處理方式可以有效地縮短Hopfield網絡算法的求解時間，減少樣本的失敗率。
全光網絡(All Optical Network，AON)憑借光纖傳輸的高速率以及波分復用帶來的巨大信道容量，成為未來最具潛力的通信網絡，是一種重要的互聯網絡結構。其帶寬高、延遲低、傳輸速率快等優點在大規模并行計算中有著很好的應用前景。波長分配是全光網絡設計中的基本問題[1，2]。設計一種波長分配方案并對所需波長數進行優化是一個重要的研究課題。
雙環網絡(Double Loop Network，DLN)是一種重要的互聯網絡拓撲結構。它實質上是在環網拓撲基礎上構建的，具有對稱性、簡單性和可擴展性等優點，還有比環網更好的抗毀性能和更短的平均通信時間。其在計算機互聯網絡或分布式系統的拓撲結構中有很好的應用前景。近年來，對雙環網絡[3，4]的研究主要集中在尋找緊優雙環網絡無限族、對雙環網絡進行最優設計、尋徑策略和算法等領域。
1基礎知識
1．1WDM雙環網
WDM全光網絡的基本原理是波長路由通過光路來實現通信。光路是網絡節點間的全光通信信道，可以跨越多個光鏈路。波長選路光網絡中的基本問題是為每一個通信請求選擇一條合適的路由，并分配一個有效波長。為了避免不同光路間的信號干擾，要求經過同一光纖鏈路的不同光路必須分配不同的波長。因此路由和波長分配問題(Routing and Wavelength Assignment)成為WDM光網絡中最基本也是最重要的研究課題。近年來，WDM光網絡中的路由和波長分配問題(RWA)也一直是學者們討論的熱點問題，各種方法已被應用于解決RWA問題[5]。本文的討論都基于波長通道方式，即一條光路從輸入端口到輸出端口所經過的物理鏈路都分配相同的波長，即滿足波長連續性要求。
1．2波長分配
波長分配是光網絡設計的基本問題。該問題可以描述為[6]，給定一個通信集合C={(x，y)|x向y傳送信息}，要完成如下的分配任務：
(1) 為每一個通信(x，y)分配一條由x到y的路徑；在該路徑上指定一個波長。
(2)以上的波長分配需滿足，如果在某一物理連接上有多條路徑經過，那么它們使用互不相同的波長。
(3)分配的目標是最小化指定的波長數。
本文基于WDM雙環網絡，討論在其上實現Hopfield網絡的波長分配問題。
2Hopfield網絡與Cn通信模式
Hopfield人工神經網絡（圖2）是完全互連型的單層反饋遞歸網絡，每個神經元都與其他所有神經元相連，且是對稱連接，即Wij=Wji和Wii=0。若所有神經元同時更新，稱為全并行工作方式。該工作方式下通信最為復雜，本文主要討論這種情況下處理機間的通信情況。假設光網絡上的一個處理機節點即是一個神經元，在Hopfield算法的每次學習過程中，每個神經元既是輸出單元又是輸入單元，即任何兩個單元間都存在通信。該算法的通信模式為完全互連型的。可見，實現并行Hopfield算法的通信模式可以看做是完全圖結構，稱這種通信模式為Cn(Complete Graph)通信模式。以下給出該通信模式的定義。
在WDM雙環網上實現Cn通信模式，即將Cn通信模式嵌入到WDM雙環網中。用圖G(V，E)表示。其中V表示網絡中的處理機節點集合，E表示節點間的光纖鏈路集合。為討論方便，本文考慮無向的全光雙環網(G(n;r，s)：從任一節點i有且僅有一條指向節點及一條指向節點的弧)。在任意兩個節點i±r(mod n)間同時存在兩條有向光纖，分別支持兩個方向的通信。這樣在討論中可以不用考慮通信的方向問題。
3．1在WDM環網上實現Hopfield網絡的波長分配
為方便后面的討論，首先看一下Cn通信模式在WDM環網上的波長分配。文獻[6]中采用的具體路由方式如下：對于通信模式中的邊，采用最短路徑路由方式。若存在通信距離等于直徑的通信邊(i，j)(這種情況在n為偶數時出現)，則當i為奇數時，通信從處理機節點i到處理機節點j采用順時針路由方式；當i為偶數時，通信從處理機節點i到處理機節點j采用逆時針路由方式(文獻[6]中稱其為奇偶最短路徑映射)。波長分配滿足1.2節中所述要求。采用這種路由方式分配的波長有如下特點：當n為奇數時，波長平均分布在環中的各條光纖鏈路上；當n為偶數時，各條光纖鏈路上的波長數之差為0或1。總之不論n為何值，各條光纖鏈路上的波長數之差為0或1。
文獻[6]已經證明該結果。當n為奇數時，該波長分配算法所需的波長數為最優值；當n為偶數時，所得到的結果在節點數目不是很大時接近其下限。
3．2構造雙環網結構
構造n在不同情形下(本文討論限于節點個數n>5的情形)的雙環網結構，有如下定義：雙環網絡中[+1]邊組成一個環結構，稱其為外環；[+h]邊所組成的環稱為內環(h為步長值)；網絡中的節點沿著[+1]邊按順時針編號，在有n個節點的雙環網中，節點依次編號為0，1，2，…，n-1。
3．3Cn通信模式在WDM雙環網上的波長分配算法
根據前面所構造的雙環網結構，分別提出一種路由策略及波長分配算法，并給出采用這種策略所使用的波長數。由前面的定義，將雙環網絡劃分為共享節點的多個環結構，分別在這些環上進行路由和波長分配。
(1)當n為奇數時，構造的雙環網結構為G(n;1，n/2」)，網絡中的所有鏈路構成一個外環和一個內環。將n個節點分為兩組，即偶數編號的節點為一組和奇數編號的節點為一組，并且兩組的節點個數分別為（n+1）/2和（n-1）/2。偶數編號的節點之間在內環上進行通信；奇數編號的節點之間也在內環上進行通信；而偶數編號的節點與奇數編號的節點之間通過外環進行通信。在每一個環上通信時采用文獻[6]中提出的奇偶最短路徑策略。
(2)當n為偶數時，構造的雙環網絡結構為G(n;1，2)，網絡中所有的鏈路構成一個外環和兩個獨立(即無共享鏈路和節點)的內環。將n個節點分為兩組，即偶數編號的節點為一組和奇數編號的節點為一組，并且兩組的節點個數都為n/2。偶數編號的節點間在偶內環上進行通信；奇數編號的節點間在奇內環上進行通信；而偶數編號的節點與奇數編號的節點間通過外環進行通信。在每一個環上通信時采用文獻[6]中提出的奇偶最短路徑策略，波長分配也采用該文獻中的策略。
(1)當n為奇數時，按照前面所述的分組方式，每一組節點都幾乎均勻地分布在每一個環結構上。據3.1節中所述各條鏈路上所分配波長的特點可以得出，內環上所需的波長數為兩個分組所需波長數的總和；外環上所需的波長數為：（n2-1）/8-內環上所需的波長數。根據（n+1）/2和（n-1）/2的不同情形又分為兩種情況：
此時外環所用波長數為
(2)當n為偶數時，按照前面所述的分組方式，每一組節點都均勻地分布在每一個環結構上。據3.1節中所述各條鏈路上所分配波長的特點可以得出，兩個內環上所需的波長數相等，外環上所需的波長數為：（n2+2n）/8-兩個內環上的所需波長數。根據n/2的不同情形分為兩種情況：
①當n/2為偶數時，每一個內環所需波長數為
將本文結果與文獻[6]在環網上實現Hopfield網所需的波長數作比較（表1）。可以發現，雙環網上所需波長數近似為環網上的一半。盡管雙環網所使用的光纖數剛好是環網的兩倍，但因目前有限的技術水平導致波長資源的珍貴，這種代價是值得的。
4結束語
進一步的工作將繼續討論在其他步長值的雙環網上實現Hopfield算法所需的波長數。
參考文獻：
［1］LEE T， LEE K， PARK S. Optimal routing and wavelength assignment in WDM ring network[J].IEEE Journal on Selected Areas in Communications， 2000，18(10): 2146－2154.
［2］ZANG Hui， JASON J， MUKHERJEE P B. A review of routing and wavelength assignment approaches for wavelength－routed optical WDM networks[J].SPIE Optical Networks Magazine， 2000，1(1): 47－63.
［3］徐俊明.計算機互連雙環網絡的最優設計[J].中國科學:E輯，1999，29(3):272－278.
［4］陳協彬.步長有限制的雙環網絡的最優路由算法[J].計算機學報，2004，27(5):596－603.
［5］RAMASWAMI R， SIVARAJAN K. Routing and wavelength assignment in all－optical networks[J]. IEEE/ACM Transactions on Networking， 1995，3(5):489－500.
［6］陳亞文，劉方愛.WDM光網上的Hopfield網波長分配算法的實現[J].計算機工程，2005，31(3):131－133.
［7］陳亞文，劉方愛，張海波.并行BP算法在WDM環網上的波長分配[J].計算機工程與應用，2004，40(18):149－151.
注：“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”
