最優(yōu)化網(wǎng)絡(luò)路由及常重復(fù)合碼.pdf

1、本文分兩部分,在第一部分中我們研究的對(duì)象是最優(yōu)化網(wǎng)絡(luò)路由,在第二部分中我們研究的是常重復(fù)合碼。 在網(wǎng)絡(luò)研究中,最優(yōu)化網(wǎng)絡(luò)路由現(xiàn)在已經(jīng)成為一個(gè)值得考慮而且已被很多人關(guān)注的問(wèn)題了。在最優(yōu)化網(wǎng)絡(luò)中,一個(gè)最優(yōu)的纖維能夠被利用到的最大的帶寬被分成很多通道,每個(gè)路由通道使用一個(gè)特定的波長(zhǎng)。任意兩個(gè)通道能使用同一個(gè)波長(zhǎng)當(dāng)且僅當(dāng)他們沒(méi)有相同的連接。關(guān)于我們所研究的最優(yōu)網(wǎng)絡(luò)我們用到多重分配波長(zhǎng)技術(shù),即被稱為WDM optical networks

2、。這個(gè)概念第一次由Alok Aggarwal,AmotzBar-Noy,Don Coppersmith,Rajiv Ramaswami,Raruch Schieber,Madhu Sudan提出。我們主要的工作就是要使得網(wǎng)絡(luò)中需要用到的波長(zhǎng)數(shù)最少。因?yàn)檫@個(gè)問(wèn)題的難度很大,所以到目前為止只得到了很少的結(jié)果。 本文主要用組合設(shè)計(jì)中的方法來(lái)研究n≥9時(shí)的在最優(yōu)化網(wǎng)絡(luò)中的路由。我們所做的工作以及得到的成果主要是以下三點(diǎn)： 1.我

3、們利用一個(gè)回溯算法得到了當(dāng)n=9和n=10的最優(yōu)解。 2.我們給出參考文獻(xiàn)[45]中構(gòu)造Steiner三元系大集的方法。這個(gè)方法在構(gòu)造Steiner三元系大集中起了非常大的作用。相信這個(gè)方法在這個(gè)問(wèn)題上也能發(fā)揮作用,我們希望利用這個(gè)方法能完美的解決這個(gè)問(wèn)題。 3.我們對(duì)這個(gè)問(wèn)題做了初步的研究,確定了一些必要條件并找到了幾個(gè)有用的HLESTS。 上面三點(diǎn)就是本論文的主要結(jié)果。當(dāng)然,有些結(jié)果還是可以進(jìn)行改進(jìn)的。比如,

4、我們采用現(xiàn)在的模型和算法無(wú)法找到當(dāng)h為偶數(shù)時(shí)在循環(huán)群下的EGDD(2,3,h3),但這并不意味著這個(gè)設(shè)計(jì)不存在。我們可以采用更加微妙的模式和更加高效率的算法進(jìn)行試驗(yàn)。這需要我們進(jìn)一步的研究和探討。在第二部分中,我們介紹了常重復(fù)合碼。常重復(fù)合碼是一種特殊的常重碼,是指在每個(gè)碼字中每個(gè)符號(hào)出現(xiàn)的次數(shù)是給定的。常重碼在編碼理論中有很重要的作用,二元常重碼已被很多人研究過(guò)了。常重復(fù)合碼包括重要的置換碼,而且由于它的廣泛應(yīng)用性,常重復(fù)合碼已被更多

5、的人所重視。我們主要是要研究(n,5,[3,1])3-碼。 在本文中,我們主要是用組合設(shè)計(jì)中的方法去研究常重復(fù)合碼。我們所做的工作以及得到的成果主要是以下三點(diǎn)： 1.我們對(duì)所要研究的這類碼字進(jìn)行分析得到一些必要條件并且利用一些算法直接構(gòu)造了一些最優(yōu)(n,5,[3,1])3-碼。 2.我們利用GDD和GDc進(jìn)行構(gòu)造(n,5,[3,1])3-碼,并且找了一系列的GDC。 3.我們構(gòu)造了一類最優(yōu)的(24t+1,

6、5,[3,1])3-碼,并且t≥1。我們還證明了個(gè)數(shù)為4的(6,5,[3,1])3-碼的最優(yōu)解是不存在的。 上面的三點(diǎn)就是本文第二部分所要介紹的主要內(nèi)容,我想這里還有很多地方可以改進(jìn)的。比如,由于我們的算法不夠優(yōu)秀,我們還不能證明一些碼的存在性。而且對(duì)于(9,5,[3,1])3-碼,我們通過(guò)計(jì)算機(jī)算法遍歷完也沒(méi)有解,但我們還不能從理論上證明是不存在的,我們可以采用更加微妙的模式和更加高效率的算法進(jìn)行試驗(yàn)。這需要我們進(jìn)一步的研究和