基于WDM雙環(huán)網(wǎng)的波長分配及網(wǎng)絡(luò)嵌入算法研究.pdf

1、傳統(tǒng)的通信技術(shù)已經(jīng)很難滿足不斷增長的通信容量的要求.許多新的通信技術(shù)應(yīng)運而生,全光通信憑借其高帶寬、低延遲、抗干擾能力強(qiáng)等優(yōu)點成為最重要的通信技術(shù)之一.而基于波分復(fù)用(Wavelength Division Multiplexing,簡稱WDM)的全光網(wǎng)絡(luò)已成為通信網(wǎng)絡(luò)的重要研究方向,也是未來最具潛力的通信網(wǎng)絡(luò). 由于現(xiàn)實中的技術(shù)限制,波長成為全光網(wǎng)絡(luò)中最寶貴的資源.如果能夠充分利用單根光纖中可以同時傳輸多路波長信號的特性,把較為

2、復(fù)雜的通信模式嵌入在簡單的光互連網(wǎng)絡(luò)中,設(shè)計好的路由算法可以大大減少網(wǎng)絡(luò)中所需的波長數(shù),也可以通過優(yōu)化設(shè)計大大簡化互連網(wǎng)絡(luò)的結(jié)構(gòu).波長分配是光網(wǎng)絡(luò)設(shè)計的基本問題.設(shè)計波長分配算法是洞察光網(wǎng)絡(luò)通信能力的基本方法,可以提高光網(wǎng)絡(luò)中波長的利用率,改善整個網(wǎng)絡(luò)的性能.已經(jīng)證明該問題在大多數(shù)網(wǎng)絡(luò)結(jié)構(gòu)中是‘NP難的,所以對于這類問題具有重要的研究價值. 采用光互連網(wǎng)絡(luò)作為并行體系結(jié)構(gòu)的通信網(wǎng)絡(luò)是發(fā)展的必然趨勢.不同的并行算法具有不同的通信模式

3、,如何在光互連網(wǎng)上實現(xiàn)這些通信模式,是當(dāng)前一個頗受關(guān)注的研究領(lǐng)域.網(wǎng)絡(luò)嵌入是互連網(wǎng)絡(luò)研究的一個重要方向.高效的嵌入會提高并行程序的運行效率.因此互連網(wǎng)絡(luò)的嵌入問題也引起了研究者們的廣泛關(guān)注. 雙環(huán)網(wǎng)絡(luò)(Double-Loop Network,簡稱DLN)是一種重要的互連網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu).它具有對稱性、簡單性和可擴(kuò)展性等優(yōu)點,具有比環(huán)網(wǎng)更好的抗毀性能和更短的平均通信時間,在計算機(jī)互連網(wǎng)絡(luò)或分布式系統(tǒng)的拓?fù)浣Y(jié)構(gòu)中有很好的應(yīng)用前景.

4、本文討論了將幾個重要并行算法的通信模式嵌入在WDM雙環(huán)網(wǎng)上的波長分配問題,其中包括數(shù)值分析領(lǐng)域中最基本的矩陣乘問題、在數(shù)字信號處理及圖像處理等領(lǐng)域中廣泛應(yīng)用的快速傅立葉變換FFT、人工神經(jīng)網(wǎng)絡(luò)中的BP算法和Hopfield算法,并且討論了兩個網(wǎng)絡(luò)嵌入問題,其中包括雙環(huán)網(wǎng)嵌入RP(k)網(wǎng)絡(luò)和mesh嵌入雙環(huán)網(wǎng). 本文做的主要研究工作如下:(1)分析了并行矩陣乘算法中的ddd算法,基于WDM雙環(huán)網(wǎng),提出了一種嵌入算法MRDR,在此基礎(chǔ)

5、上分析了在WDM雙環(huán)網(wǎng)上實現(xiàn)并行矩陣乘的波長分配問題,得到在此算法中所需的最小波長數(shù)為2,并給出了理論證明.(2)分析了在數(shù)字信號處理、圖像處理等領(lǐng)域有著廣泛應(yīng)用的快速傅立葉變換(FFT),.基于WDM雙環(huán)網(wǎng),提出一種遞歸的嵌入算法FFT-DLN,針對四種基本嵌入算法生成法、對折嵌入算法、順序映射和逆序映射,得到在WDM雙環(huán)網(wǎng)上實現(xiàn)并行FFT的通信模式所需的波長數(shù)均為N/8(N≥8).通過分析發(fā)現(xiàn),對于相同規(guī)模的傅立葉變換,遞歸的對折嵌

6、入算法和逆序映射具有更短的執(zhí)行時間.(3)分析了在聯(lián)想記憶、模式識別等方面有著廣泛應(yīng)用的Hopfield.網(wǎng)絡(luò)模型.基于WDM雙環(huán)網(wǎng),討論了在其上實現(xiàn)Hopfield通信模式的波長分配問題,提出了一種路由策略及波長分配方案,在此基礎(chǔ)上給出了實現(xiàn)Hopfield算法所需的波長數(shù).(4)分析了人工神經(jīng)網(wǎng)絡(luò)中的并行BP算法.基于WDM雙環(huán)網(wǎng),討論了在其上實現(xiàn)并行BP算法的波長分配問題,提出了一種路由策略及波長分配方案并進(jìn)行了仿真實驗,對實驗結(jié)