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

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

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

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

4、本文討論了將幾個(gè)重要并行算法的通信模式嵌入在WDM雙環(huán)網(wǎng)上的波長(zhǎng)分配問(wèn)題,其中包括數(shù)值分析領(lǐng)域中最基本的矩陣乘問(wèn)題、在數(shù)字信號(hào)處理及圖像處理等領(lǐng)域中廣泛應(yīng)用的快速傅立葉變換FFT、人工神經(jīng)網(wǎng)絡(luò)中的BP算法和Hopfield算法,并且討論了兩個(gè)網(wǎng)絡(luò)嵌入問(wèn)題,其中包括雙環(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)上實(shí)現(xiàn)并行矩陣乘的波長(zhǎng)分配問(wèn)題,得到在此算法中所需的最小波長(zhǎng)數(shù)為2,并給出了理論證明.(2)分析了在數(shù)字信號(hào)處理、圖像處理等領(lǐng)域有著廣泛應(yīng)用的快速傅立葉變換(FFT),.基于WDM雙環(huán)網(wǎng),提出一種遞歸的嵌入算法FFT-DLN,針對(duì)四種基本嵌入算法生成法、對(duì)折嵌入算法、順序映射和逆序映射,得到在WDM雙環(huán)網(wǎng)上實(shí)現(xiàn)并行FFT的通信模式所需的波長(zhǎng)數(shù)均為N/8(N≥8).通過(guò)分析發(fā)現(xiàn),對(duì)于相同規(guī)模的傅立葉變換,遞歸的對(duì)折嵌

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