一種面向網(wǎng)絡(luò)編碼組播樹的隨機(jī)拓?fù)渖伤惴?/h1>
2016-03-17 03:17:52顧葉露劉曉紅曲志堅(jiān)張愛鳳
顧葉露， 劉曉紅， 曲志堅(jiān)， 張愛鳳
(山東理工大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院， 山東 淄博 255049)
?
一種面向網(wǎng)絡(luò)編碼組播樹的隨機(jī)拓?fù)渖伤惴?/p>
顧葉露， 劉曉紅， 曲志堅(jiān)， 張愛鳳
(山東理工大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院， 山東 淄博 255049)
摘要：為了建立滿足網(wǎng)絡(luò)編碼需求的組播樹，提出一種面向網(wǎng)絡(luò)編碼組播樹的隨機(jī)拓?fù)渖伤惴?首先依據(jù)總體布局隨機(jī)網(wǎng)絡(luò)拓?fù)渖伤惴?，生成隨機(jī)的雛形網(wǎng)絡(luò)拓?fù)洌蝗缓蠼Y(jié)合網(wǎng)絡(luò)編碼組播樹的拓?fù)涮匦?，?duì)已生成的雛形網(wǎng)絡(luò)在孤點(diǎn)、連通性、度控制等方面進(jìn)行修補(bǔ)，使最終生成的網(wǎng)絡(luò)拓?fù)錆M足網(wǎng)絡(luò)編碼組播樹的拓?fù)湟?
關(guān)鍵詞：網(wǎng)絡(luò)編碼； 組播樹； 隨機(jī)拓?fù)?/p>
建立網(wǎng)絡(luò)編碼組播樹是實(shí)現(xiàn)網(wǎng)絡(luò)編碼組播要求的重要基礎(chǔ)，近年來研究人員在基于網(wǎng)絡(luò)編碼組播樹建樹和資源優(yōu)化方面提出了許多重要算法.為對(duì)基于網(wǎng)絡(luò)編碼組播樹建樹和資源優(yōu)化而提出的算法進(jìn)行測試和評(píng)價(jià)，需要將所提出的算法應(yīng)用于大量網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu). 以此來測試不同網(wǎng)絡(luò)結(jié)構(gòu)下網(wǎng)絡(luò)編碼技術(shù)對(duì)網(wǎng)絡(luò)性能的影響.其中就有基于時(shí)延、時(shí)延抖動(dòng)以及網(wǎng)絡(luò)編碼資源最小化等多目標(biāo)約束條件，曲志堅(jiān)等人在基于遺傳算法的網(wǎng)絡(luò)編碼方面做出了系列研究[1-2].
基于網(wǎng)絡(luò)編碼的組播跟傳統(tǒng)組播對(duì)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的需求有明顯的區(qū)別，導(dǎo)致現(xiàn)存的各種隨機(jī)拓?fù)渖煞椒o法直接使用.目前，對(duì)面向網(wǎng)絡(luò)編碼技術(shù)的隨機(jī)網(wǎng)絡(luò)拓?fù)渖伤惴ù蠖嗍且越?jīng)典的拓?fù)浠蛟谄浠A(chǔ)上稍加修改為藍(lán)本進(jìn)行的[3].如蔡慧等人提出了一種基于K均值聚類的隨機(jī)網(wǎng)絡(luò)拓?fù)淠Ｐ蚚4]，解決了在Waxman隨機(jī)網(wǎng)絡(luò)拓?fù)淠Ｐ湍M過程中網(wǎng)絡(luò)節(jié)點(diǎn)疏密不當(dāng)、節(jié)點(diǎn)難以控制、難以生成連通圖等缺點(diǎn)；姚文斌等人提出了一種基于總體布局的隨機(jī)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)生成方法[5]，該方法生成的拓?fù)涓咏鎸?shí)網(wǎng)絡(luò)，突出模擬網(wǎng)絡(luò)的隨機(jī)性.但上述隨機(jī)拓?fù)渖a(chǎn)算法都無法直接生成滿足網(wǎng)絡(luò)編碼需要的隨機(jī)網(wǎng)絡(luò)拓?fù)?
為了生成符合網(wǎng)絡(luò)編碼組播樹的網(wǎng)絡(luò)拓?fù)?，提出了一種面向網(wǎng)絡(luò)編碼組播樹的隨機(jī)網(wǎng)絡(luò)拓?fù)渖伤惴ǎ撍惴ɑ诳傮w布局隨機(jī)網(wǎng)絡(luò)拓?fù)渖伤惴?，結(jié)合網(wǎng)絡(luò)編碼組播樹在拓?fù)淠M建模方面的特性要求,進(jìn)而生成符合網(wǎng)絡(luò)編碼組播樹的拓?fù)浣Y(jié)構(gòu).
1基于總體布局的隨機(jī)網(wǎng)絡(luò)拓?fù)渖伤惴?/p>
1.1算法梗概
基于總體布局的隨機(jī)網(wǎng)絡(luò)拓?fù)渖伤惴ǎ赏ㄟ^多次隨機(jī)過程模擬生成隨機(jī)網(wǎng)絡(luò)，每次產(chǎn)生的模擬網(wǎng)絡(luò)從頂點(diǎn)分布到模擬方式都不盡相同，符合真實(shí)網(wǎng)絡(luò)多樣性的特征，克服了隨機(jī)網(wǎng)絡(luò)拓?fù)浜茈y貼近真實(shí)網(wǎng)絡(luò)的缺點(diǎn).基于總體布局的隨機(jī)網(wǎng)絡(luò)拓?fù)渖伤惴鞒倘鐖D1所示.
圖1 基于總體布局的隨機(jī)網(wǎng)絡(luò)拓?fù)渖伤惴鞒虉D
實(shí)現(xiàn)隨機(jī)網(wǎng)絡(luò)雛形拓?fù)涞倪^程如下.
(1)依據(jù)基于總體布局的隨機(jī)網(wǎng)絡(luò)拓?fù)渖伤惴?，首先隨機(jī)生成拓?fù)涔?jié)點(diǎn)數(shù)目M，并依次為每個(gè)生成的隨機(jī)節(jié)點(diǎn)從0到M-1進(jìn)行標(biāo)號(hào).
(2)隨機(jī)生成拓?fù)溥B接數(shù)N，表示M個(gè)隨機(jī)節(jié)點(diǎn)中存在的連接的數(shù)目，其中N的取值范圍必須控制在1(3)隨機(jī)生成N對(duì)隨機(jī)數(shù)對(duì)(Ai，Bi)，表示隨機(jī)生成了N條連接，其中每個(gè)隨機(jī)對(duì)表示節(jié)點(diǎn)Ai與節(jié)點(diǎn)Bi之間有一條邊直接關(guān)聯(lián)，其中Ai∈{0,1,2…M-2}，Bi∈{0,1,2…M-1}，且Ai從閉區(qū)間[0，M-2]范圍內(nèi)隨機(jī)產(chǎn)生，Bi根據(jù)Ai產(chǎn)生的節(jié)點(diǎn)序號(hào)從閉區(qū)間[Ai+1，M-1] 的范圍內(nèi)產(chǎn)生，這樣做的目的是防止重邊和自環(huán)問題的產(chǎn)生.
在圖論中，所謂自環(huán)就是兩個(gè)端點(diǎn)為同一頂點(diǎn)的邊.在隨機(jī)數(shù)對(duì)(Ai，Bi)的產(chǎn)生過程中，若Ai，Bi值的產(chǎn)生完全隨機(jī)，也就是任何兩個(gè)節(jié)點(diǎn)之間的連接是完全隨機(jī)的并且均在[0，M-1]的范圍內(nèi)產(chǎn)生，有可能會(huì)在生成圖中產(chǎn)生自環(huán).例如，Ai和Bi的隨機(jī)值為同一節(jié)點(diǎn)q，q∈{0,1,2…M-1}，即產(chǎn)生了(q，q)的連接，那么在生產(chǎn)的拓?fù)渲泄?jié)點(diǎn)q就會(huì)出現(xiàn)自環(huán).
而重邊則是由于隨機(jī)拓?fù)錇闊o向圖，因此在隨機(jī)數(shù)對(duì)(Ai，Bi)的產(chǎn)生過程中，當(dāng)Ai和Bi的產(chǎn)生完成，在Ai+1和Bi+1的節(jié)點(diǎn)產(chǎn)生過程中，若與Ai和Bi產(chǎn)生的隨機(jī)節(jié)點(diǎn)相同，即有Ai=Bi，Ai+1=Bi+1，或者Ai=Bi+1且Ai+1=Bi的情況發(fā)生，已產(chǎn)生的節(jié)點(diǎn)連接就會(huì)在后面的隨機(jī)數(shù)對(duì)產(chǎn)生過程中重復(fù)連接，從而產(chǎn)生重邊問題.
(4)在隨機(jī)網(wǎng)絡(luò)拓?fù)潆S機(jī)數(shù)對(duì)生成過程中，為避免重邊和自環(huán)的產(chǎn)生，在鄰接矩陣中只保留除去對(duì)角線元素外的右上三角部分，即，在產(chǎn)生的隨機(jī)數(shù)對(duì)(Ai，Bi)中只保留Ai(5)根據(jù)生成的N對(duì)隨機(jī)數(shù)對(duì)，填充M*M階隨機(jī)拓?fù)涞泥徑泳仃嘒MM，在矩陣中元素1代表相應(yīng)的兩個(gè)節(jié)點(diǎn)有連接，元素0則表示兩個(gè)節(jié)點(diǎn)間無連接.
1.2面向網(wǎng)絡(luò)編碼組播樹的網(wǎng)絡(luò)拓?fù)涮匦蕴骄?/p>
網(wǎng)絡(luò)編碼組播樹中從源節(jié)點(diǎn)到目的節(jié)點(diǎn)必須具有多條分離路徑.因此要求給定的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)為連通圖且每個(gè)節(jié)點(diǎn)的度必須大于等于2.上述算法能夠生成較為隨機(jī)的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，但是生成的隨機(jī)網(wǎng)絡(luò)拓?fù)溥€存在一些無法滿足網(wǎng)絡(luò)編碼組播樹拓?fù)涮匦缘膯栴}.產(chǎn)生這些問題的主要原因是算法中的隨機(jī)生成數(shù)對(duì)(Ai，Bi)的隨機(jī)性，導(dǎo)致拓?fù)渖傻倪^程中對(duì)于邊和點(diǎn)的約束不充分.
下面對(duì)存在的孤點(diǎn)問題、不連通問題、度不可控問題進(jìn)行探討，其中描述的隨機(jī)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)均以無向圖來表示.
(1)孤點(diǎn)問題.孤點(diǎn)是無向圖中度為0的節(jié)點(diǎn)，在無向圖中孤點(diǎn)不與其他任何節(jié)點(diǎn)相鄰接.上述算法容易產(chǎn)生孤點(diǎn)，對(duì)于基于網(wǎng)絡(luò)編碼的組播中仿真中，通常不希望孤點(diǎn)的存在.導(dǎo)致孤點(diǎn)存在的主要原因是在隨機(jī)數(shù)對(duì)產(chǎn)生過程中若不對(duì)Ai和Bi進(jìn)行限制，Ai和Bi可能只在一個(gè)小范圍內(nèi)產(chǎn)生，如果節(jié)點(diǎn)j(其中j∈{0,1,2……M-1})不在Ai和Bi產(chǎn)生的范圍內(nèi)，將會(huì)導(dǎo)致結(jié)點(diǎn)j不與任何其他結(jié)點(diǎn)有連接成為孤點(diǎn).
(2)不連通問題.在無向圖中，如果存在兩個(gè)節(jié)點(diǎn)沒有通路，則該圖為不連通圖.組播網(wǎng)絡(luò)仿真過程中希望所有的生產(chǎn)圖均為連通圖.但是，上述算法在拓?fù)渖蛇^程中，因有連接的兩個(gè)節(jié)點(diǎn)(Ai，Bi)都是隨機(jī)產(chǎn)生的，因此在節(jié)點(diǎn)連接問題上很有可能產(chǎn)生多個(gè)小范圍的節(jié)點(diǎn)相互連接的問題，而在圖的總體上沒有聯(lián)通的情況，也就是生產(chǎn)的隨機(jī)拓?fù)淇赡艽嬖诓贿B通的問題.
(3)度不可控問題.為了滿足網(wǎng)絡(luò)編碼需求，組播樹中從源節(jié)點(diǎn)到目的節(jié)點(diǎn)必須具有多條分離路徑.這就要求給定的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)是個(gè)連通圖且每個(gè)節(jié)點(diǎn)的度必須大于等于2.由于上述算法在產(chǎn)生隨機(jī)拓?fù)涞倪^程中節(jié)點(diǎn)之間的相互連接是完全隨機(jī)的，有些節(jié)點(diǎn)可能只與剩余節(jié)點(diǎn)中的一個(gè)節(jié)點(diǎn)相連接或者不與其他任何節(jié)點(diǎn)相連(即上述孤點(diǎn))，就會(huì)使拓?fù)渲挟a(chǎn)生度為1或者0的節(jié)點(diǎn)，不符合網(wǎng)絡(luò)編碼組播樹對(duì)于節(jié)點(diǎn)度的要求.
總的來說，基于總體布局的隨機(jī)網(wǎng)絡(luò)拓?fù)渖伤惴?，在雛形拓?fù)渖蛇^程中，從頂點(diǎn)分布到連接方式都是隨機(jī)產(chǎn)生，符合真實(shí)網(wǎng)絡(luò)中拓?fù)浣Y(jié)構(gòu)多樣化的特性，更加貼近真實(shí)的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu).也正由于拓?fù)渖煞绞降耐耆S機(jī)，生成過程中必然會(huì)產(chǎn)生以上描述的各個(gè)問題，從而使得生成的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)無法滿足網(wǎng)絡(luò)編碼組播樹的要求.因此，需要對(duì)上述算法進(jìn)行改進(jìn)，以生成滿足網(wǎng)絡(luò)編碼組播樹特定需求的隨機(jī)網(wǎng)絡(luò).
2面向網(wǎng)絡(luò)編碼組播樹的隨機(jī)拓?fù)渖伤惴?/p>
在基于總體布局隨機(jī)網(wǎng)絡(luò)拓?fù)渖伤惴ǖ囊笙律傻碾r形網(wǎng)絡(luò)，存在一些不符合基于網(wǎng)絡(luò)編碼組播樹對(duì)隨機(jī)拓?fù)涮卣餍枨蟮膯栴}，因此本部分在總體布局隨機(jī)拓?fù)渌惴óa(chǎn)生的雛形網(wǎng)絡(luò)的基礎(chǔ)上，針對(duì)存在的問題進(jìn)行改進(jìn)，使得算法生產(chǎn)的隨機(jī)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)滿足基于網(wǎng)絡(luò)編碼組播對(duì)隨機(jī)網(wǎng)絡(luò)的結(jié)構(gòu)要求，面向網(wǎng)絡(luò)編碼組播樹的隨機(jī)拓?fù)渖伤惴鞒虉D如圖2所示.
對(duì)于孤點(diǎn)問題、不連通問題、度不可控問題的解決方案為：
(1)解決孤點(diǎn)問題.對(duì)于孤點(diǎn)問題的解決，通過遍歷鄰接矩陣GMM，找到第i行和第i列均為0 的節(jié)點(diǎn)i，i即為孤點(diǎn)，然后將孤點(diǎn)i與除該節(jié)點(diǎn)以外的，度數(shù)最小的節(jié)點(diǎn)相連，也就是遵循度數(shù)最小節(jié)點(diǎn)優(yōu)先選擇的原則，將有問題的節(jié)點(diǎn)與優(yōu)先于度數(shù)最小的節(jié)點(diǎn)相連接，這樣就將孤點(diǎn)重新融入到已生成的隨機(jī)網(wǎng)絡(luò)拓?fù)鋱D當(dāng)中.這樣做的同時(shí)也改變了某些節(jié)點(diǎn)的度數(shù)，為后續(xù)度不可控問題減少了工作量.
(2)解決不連通的問題.首先深度優(yōu)先遍歷生成的整個(gè)雛形網(wǎng)絡(luò)拓?fù)鋱D，查找全局網(wǎng)絡(luò)拓?fù)涞倪B通分量數(shù)目，如果連通分支數(shù)量大于1，則說明該拓?fù)鋱D為非連通圖.對(duì)于該問題，根據(jù)連通分量的數(shù)目將每個(gè)連通分量看作一個(gè)單獨(dú)節(jié)點(diǎn)，重復(fù)全局隨機(jī)生成連接的方式，生成各個(gè)連通分量間的拓?fù)溥B接，在兩個(gè)有連接的連通分量中，隨機(jī)產(chǎn)生連通分量內(nèi)部具體節(jié)點(diǎn)對(duì)方的節(jié)點(diǎn)相連.
圖2 面向網(wǎng)絡(luò)編碼組播樹的隨機(jī)拓?fù)渖伤惴鞒虉D
(3) 解決度不可控問題.對(duì)產(chǎn)生的雛形隨機(jī)網(wǎng)絡(luò)拓?fù)鋱D中的每個(gè)節(jié)點(diǎn)的度數(shù)實(shí)時(shí)更新，記錄每個(gè)節(jié)點(diǎn)度數(shù)，若有節(jié)點(diǎn)不符合網(wǎng)絡(luò)編碼組播樹對(duì)于節(jié)點(diǎn)度數(shù)的要求，依據(jù)度數(shù)小節(jié)點(diǎn)優(yōu)先選擇的原則，將不符合要求的節(jié)點(diǎn)，在本課題中即為節(jié)點(diǎn)度數(shù)不足2的節(jié)點(diǎn)，與除該節(jié)點(diǎn)外剩余節(jié)點(diǎn)中度數(shù)最小的節(jié)點(diǎn)相連，使得在改變自身節(jié)點(diǎn)度的同時(shí)，也在改變其他的節(jié)點(diǎn)的度數(shù)，為后續(xù)的重復(fù)操作減少了工作量.更新各節(jié)點(diǎn)度數(shù)，重復(fù)操作，直至每個(gè)節(jié)點(diǎn)的度數(shù)符合網(wǎng)絡(luò)編碼組播樹對(duì)節(jié)點(diǎn)度的要求，實(shí)現(xiàn)節(jié)點(diǎn)度的控制.
3仿真結(jié)果分析
為了驗(yàn)證改進(jìn)后算法的有效性，對(duì)算法進(jìn)行了仿真實(shí)驗(yàn)分析.本實(shí)驗(yàn)使用C#語言在Visual Studio 2012開發(fā)環(huán)境下，基于面向網(wǎng)絡(luò)編碼組播樹的隨機(jī)拓?fù)渖伤惴ㄔO(shè)計(jì)實(shí)現(xiàn)了隨機(jī)網(wǎng)絡(luò)生成系統(tǒng).為保證實(shí)驗(yàn)結(jié)果的可視性和可參考性，本課題將M的隨機(jī)范圍限制在[5，40].
隨機(jī)生成的雛形隨機(jī)網(wǎng)絡(luò)中，隨機(jī)節(jié)點(diǎn)數(shù)M=15，隨機(jī)連接數(shù)N=29，雛形網(wǎng)絡(luò)拓?fù)淙鐖D3(a)所示，在拓?fù)鋱D中可以看出，生成的隨機(jī)網(wǎng)絡(luò)拓?fù)鋱D中節(jié)點(diǎn)0、節(jié)點(diǎn)2、節(jié)點(diǎn)7度數(shù)不可控制，不符合網(wǎng)絡(luò)編碼組播樹對(duì)于網(wǎng)絡(luò)節(jié)點(diǎn)度數(shù)至少為2的要求.修補(bǔ)過程中，首先記錄度數(shù)不可控的節(jié)點(diǎn)，然后將除節(jié)點(diǎn)0以外的所有節(jié)點(diǎn)排序，找到度數(shù)最小的節(jié)點(diǎn)，將節(jié)點(diǎn)0與度數(shù)最小節(jié)點(diǎn)相連接，保證了節(jié)點(diǎn)0的度數(shù)至少為2，以此類推可使得節(jié)點(diǎn)2與節(jié)點(diǎn)7度數(shù)完全符合網(wǎng)絡(luò)編碼組播樹的需求，最終成形撲如圖3(b)所示.
(a) 雛形網(wǎng)絡(luò)拓?fù)洹 ?(b)成形絡(luò)拓?fù)鋱D3 M=15，N=29的隨機(jī)網(wǎng)絡(luò)拓?fù)鋱D
如圖4(a)所示的雛形網(wǎng)絡(luò)拓?fù)渲?，隨機(jī)節(jié)點(diǎn)數(shù)M=14，隨機(jī)連接數(shù)N=18，存在孤點(diǎn)9，同時(shí)生成的拓?fù)鋱D因孤點(diǎn)9的存在,形成了具有兩個(gè)連通分量的非連通圖.對(duì)于孤點(diǎn)的處理，采取的措施是：將孤點(diǎn)9重新融入到由剩余節(jié)點(diǎn)形成的連通分量當(dāng)中，在該連通分量當(dāng)中尋找節(jié)點(diǎn)度數(shù)最小的節(jié)點(diǎn)，將其與孤點(diǎn)9相連.這樣操作不僅解決了孤點(diǎn)的問題同時(shí)也解決了非連通圖的問題.孤點(diǎn)問題解決之后，圖中還存在度數(shù)不可控的節(jié)點(diǎn)，操作過程與圖3的處理過程類似，在此不做贅述.最終成形拓?fù)淙鐖D4(b)所示.
(a) 雛形網(wǎng)絡(luò)拓?fù)洹 ?(b)成形絡(luò)拓?fù)鋱D4 M=14,N=18的隨機(jī)網(wǎng)絡(luò)拓?fù)鋱D
4結(jié)束語
面向網(wǎng)絡(luò)編碼組播樹的隨機(jī)拓?fù)渖伤惴ㄔ诳傮w布局隨機(jī)網(wǎng)絡(luò)拓?fù)渖伤惴ǖ幕A(chǔ)上，結(jié)合網(wǎng)絡(luò)編碼組播樹對(duì)于網(wǎng)絡(luò)拓?fù)涞奶厥庖蟾倪M(jìn)基于總體布局隨機(jī)網(wǎng)絡(luò)拓?fù)渖a(chǎn)算法.根據(jù)隨機(jī)網(wǎng)絡(luò)算法生成的雛形網(wǎng)絡(luò)，在滿足網(wǎng)絡(luò)編碼組播樹拓?fù)湟蟮臈l件下，對(duì)得到的雛形網(wǎng)絡(luò)進(jìn)行修補(bǔ)，主要針對(duì)雛形網(wǎng)絡(luò)中的孤立點(diǎn)、不連通以及節(jié)點(diǎn)度不可控制等不滿足網(wǎng)絡(luò)編碼組播樹需求的特征進(jìn)行修整，使得生成的隨機(jī)網(wǎng)絡(luò)更加符合網(wǎng)絡(luò)編碼組播樹的拓?fù)浞抡嫘枨?
參考文獻(xiàn):
[1]Qu Z J, Liu X H, Huang J J, et al. Genetic local search algorithm for network coding resources minimization [C]// 2012 IEEE International Conference on Computer Science and Automation Engineering, 2012: 782-786.
[2]Qu Z J, Liu X H, Fu J. Genetic algorithm-based network coding resources optimization in multimedia network [C]//2012 International Conference on Systems and Informatics, 2012: 1 547-1 550.
[3] 張宇,張宏莉,方濱興.Internet拓?fù)浣＞C述[J].軟件學(xué)報(bào),2004,15(8):1220-1226.
[4]蔡慧,劉洪波,韓國棟.基于K均值聚類的隨機(jī)網(wǎng)絡(luò)拓?fù)淠Ｐ蚚J].計(jì)算機(jī)工程與設(shè)計(jì),2009,30(5):1 089-1 091.
[5]姚文斌,韓司,姚翔.一種基于總體布局的隨機(jī)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)生成:中國,103457860 A[P].2013-09-03.
(編輯：劉寶江)
Research on network coding based multicast-oriented random topology generation algorithm
GU Ye-lu, LIU Xiao-hong, QU Zhi-jian, ZHANG Ai-feng
(School of Computer Science and Technology, Shandong University of Technology, Zibo 255049, China)
Abstract:A novel random topology network algorithm was presented to meet the requirements for establishing the network coding based multicast tree. Firstly, a primitive random topology was generated according to the overall layout random topology network. Secondly, the obtained primitive random topology was repaired in terms of solitary point, network connectivity, degrees of each node to remove the negative effects of unsuitable for establishing network coding based multicast tree. Finally, the proposed algorithm was tested, and the results indicated that the generated random topology meet the requirements of establishing the network coding based multicast tree. The proposed algorithm can provide plenty of simulation resources for the network coding based multicast research.
Key words:network coding； multicast tree； random topology
中圖分類號(hào)：TP393.0
文獻(xiàn)標(biāo)志碼：A
文章編號(hào)：1672-6197(2016)02-0001-04
作者簡介：顧葉露，女，jiangmi22@163.com； 通信作者： 劉曉紅,女，Liuxh88@tom.com
基金項(xiàng)目：國家自然科學(xué)基金項(xiàng)目(61473179);山東省自然科學(xué)基金項(xiàng)目(ZR2014FM007);山東省優(yōu)秀中青年科學(xué)家科研獎(jiǎng)勵(lì)基金項(xiàng)目(BS2013DX032);山東理工大學(xué)青年教師發(fā)展計(jì)劃項(xiàng)目
收稿日期：2015-03-19
顧葉露， 劉曉紅， 曲志堅(jiān)， 張愛鳳
(山東理工大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院， 山東 淄博 255049)
?
一種面向網(wǎng)絡(luò)編碼組播樹的隨機(jī)拓?fù)渖伤惴?/p>
顧葉露， 劉曉紅， 曲志堅(jiān)， 張愛鳳
(山東理工大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院， 山東 淄博 255049)
摘要：為了建立滿足網(wǎng)絡(luò)編碼需求的組播樹，提出一種面向網(wǎng)絡(luò)編碼組播樹的隨機(jī)拓?fù)渖伤惴?首先依據(jù)總體布局隨機(jī)網(wǎng)絡(luò)拓?fù)渖伤惴?，生成隨機(jī)的雛形網(wǎng)絡(luò)拓?fù)洌蝗缓蠼Y(jié)合網(wǎng)絡(luò)編碼組播樹的拓?fù)涮匦?，?duì)已生成的雛形網(wǎng)絡(luò)在孤點(diǎn)、連通性、度控制等方面進(jìn)行修補(bǔ)，使最終生成的網(wǎng)絡(luò)拓?fù)錆M足網(wǎng)絡(luò)編碼組播樹的拓?fù)湟?
關(guān)鍵詞：網(wǎng)絡(luò)編碼； 組播樹； 隨機(jī)拓?fù)?/p>
建立網(wǎng)絡(luò)編碼組播樹是實(shí)現(xiàn)網(wǎng)絡(luò)編碼組播要求的重要基礎(chǔ)，近年來研究人員在基于網(wǎng)絡(luò)編碼組播樹建樹和資源優(yōu)化方面提出了許多重要算法.為對(duì)基于網(wǎng)絡(luò)編碼組播樹建樹和資源優(yōu)化而提出的算法進(jìn)行測試和評(píng)價(jià)，需要將所提出的算法應(yīng)用于大量網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu). 以此來測試不同網(wǎng)絡(luò)結(jié)構(gòu)下網(wǎng)絡(luò)編碼技術(shù)對(duì)網(wǎng)絡(luò)性能的影響.其中就有基于時(shí)延、時(shí)延抖動(dòng)以及網(wǎng)絡(luò)編碼資源最小化等多目標(biāo)約束條件，曲志堅(jiān)等人在基于遺傳算法的網(wǎng)絡(luò)編碼方面做出了系列研究[1-2].
基于網(wǎng)絡(luò)編碼的組播跟傳統(tǒng)組播對(duì)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的需求有明顯的區(qū)別，導(dǎo)致現(xiàn)存的各種隨機(jī)拓?fù)渖煞椒o法直接使用.目前，對(duì)面向網(wǎng)絡(luò)編碼技術(shù)的隨機(jī)網(wǎng)絡(luò)拓?fù)渖伤惴ù蠖嗍且越?jīng)典的拓?fù)浠蛟谄浠A(chǔ)上稍加修改為藍(lán)本進(jìn)行的[3].如蔡慧等人提出了一種基于K均值聚類的隨機(jī)網(wǎng)絡(luò)拓?fù)淠Ｐ蚚4]，解決了在Waxman隨機(jī)網(wǎng)絡(luò)拓?fù)淠Ｐ湍M過程中網(wǎng)絡(luò)節(jié)點(diǎn)疏密不當(dāng)、節(jié)點(diǎn)難以控制、難以生成連通圖等缺點(diǎn)；姚文斌等人提出了一種基于總體布局的隨機(jī)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)生成方法[5]，該方法生成的拓?fù)涓咏鎸?shí)網(wǎng)絡(luò)，突出模擬網(wǎng)絡(luò)的隨機(jī)性.但上述隨機(jī)拓?fù)渖a(chǎn)算法都無法直接生成滿足網(wǎng)絡(luò)編碼需要的隨機(jī)網(wǎng)絡(luò)拓?fù)?
為了生成符合網(wǎng)絡(luò)編碼組播樹的網(wǎng)絡(luò)拓?fù)?，提出了一種面向網(wǎng)絡(luò)編碼組播樹的隨機(jī)網(wǎng)絡(luò)拓?fù)渖伤惴ǎ撍惴ɑ诳傮w布局隨機(jī)網(wǎng)絡(luò)拓?fù)渖伤惴?，結(jié)合網(wǎng)絡(luò)編碼組播樹在拓?fù)淠M建模方面的特性要求,進(jìn)而生成符合網(wǎng)絡(luò)編碼組播樹的拓?fù)浣Y(jié)構(gòu).
1基于總體布局的隨機(jī)網(wǎng)絡(luò)拓?fù)渖伤惴?/p>
1.1算法梗概
基于總體布局的隨機(jī)網(wǎng)絡(luò)拓?fù)渖伤惴ǎ赏ㄟ^多次隨機(jī)過程模擬生成隨機(jī)網(wǎng)絡(luò)，每次產(chǎn)生的模擬網(wǎng)絡(luò)從頂點(diǎn)分布到模擬方式都不盡相同，符合真實(shí)網(wǎng)絡(luò)多樣性的特征，克服了隨機(jī)網(wǎng)絡(luò)拓?fù)浜茈y貼近真實(shí)網(wǎng)絡(luò)的缺點(diǎn).基于總體布局的隨機(jī)網(wǎng)絡(luò)拓?fù)渖伤惴鞒倘鐖D1所示.
圖1 基于總體布局的隨機(jī)網(wǎng)絡(luò)拓?fù)渖伤惴鞒虉D
實(shí)現(xiàn)隨機(jī)網(wǎng)絡(luò)雛形拓?fù)涞倪^程如下.
(1)依據(jù)基于總體布局的隨機(jī)網(wǎng)絡(luò)拓?fù)渖伤惴?，首先隨機(jī)生成拓?fù)涔?jié)點(diǎn)數(shù)目M，并依次為每個(gè)生成的隨機(jī)節(jié)點(diǎn)從0到M-1進(jìn)行標(biāo)號(hào).
(2)隨機(jī)生成拓?fù)溥B接數(shù)N，表示M個(gè)隨機(jī)節(jié)點(diǎn)中存在的連接的數(shù)目，其中N的取值范圍必須控制在1 (3)隨機(jī)生成N對(duì)隨機(jī)數(shù)對(duì)(Ai，Bi)，表示隨機(jī)生成了N條連接，其中每個(gè)隨機(jī)對(duì)表示節(jié)點(diǎn)Ai與節(jié)點(diǎn)Bi之間有一條邊直接關(guān)聯(lián)，其中Ai∈{0,1,2…M-2}，Bi∈{0,1,2…M-1}，且Ai從閉區(qū)間[0，M-2]范圍內(nèi)隨機(jī)產(chǎn)生，Bi根據(jù)Ai產(chǎn)生的節(jié)點(diǎn)序號(hào)從閉區(qū)間[Ai+1，M-1] 的范圍內(nèi)產(chǎn)生，這樣做的目的是防止重邊和自環(huán)問題的產(chǎn)生. 在圖論中，所謂自環(huán)就是兩個(gè)端點(diǎn)為同一頂點(diǎn)的邊.在隨機(jī)數(shù)對(duì)(Ai，Bi)的產(chǎn)生過程中，若Ai，Bi值的產(chǎn)生完全隨機(jī)，也就是任何兩個(gè)節(jié)點(diǎn)之間的連接是完全隨機(jī)的并且均在[0，M-1]的范圍內(nèi)產(chǎn)生，有可能會(huì)在生成圖中產(chǎn)生自環(huán).例如，Ai和Bi的隨機(jī)值為同一節(jié)點(diǎn)q，q∈{0,1,2…M-1}，即產(chǎn)生了(q，q)的連接，那么在生產(chǎn)的拓?fù)渲泄?jié)點(diǎn)q就會(huì)出現(xiàn)自環(huán). 而重邊則是由于隨機(jī)拓?fù)錇闊o向圖，因此在隨機(jī)數(shù)對(duì)(Ai，Bi)的產(chǎn)生過程中，當(dāng)Ai和Bi的產(chǎn)生完成，在Ai+1和Bi+1的節(jié)點(diǎn)產(chǎn)生過程中，若與Ai和Bi產(chǎn)生的隨機(jī)節(jié)點(diǎn)相同，即有Ai=Bi，Ai+1=Bi+1，或者Ai=Bi+1且Ai+1=Bi的情況發(fā)生，已產(chǎn)生的節(jié)點(diǎn)連接就會(huì)在后面的隨機(jī)數(shù)對(duì)產(chǎn)生過程中重復(fù)連接，從而產(chǎn)生重邊問題. (4)在隨機(jī)網(wǎng)絡(luò)拓?fù)潆S機(jī)數(shù)對(duì)生成過程中，為避免重邊和自環(huán)的產(chǎn)生，在鄰接矩陣中只保留除去對(duì)角線元素外的右上三角部分，即，在產(chǎn)生的隨機(jī)數(shù)對(duì)(Ai，Bi)中只保留Ai (5)根據(jù)生成的N對(duì)隨機(jī)數(shù)對(duì)，填充M*M階隨機(jī)拓?fù)涞泥徑泳仃嘒MM，在矩陣中元素1代表相應(yīng)的兩個(gè)節(jié)點(diǎn)有連接，元素0則表示兩個(gè)節(jié)點(diǎn)間無連接. 1.2面向網(wǎng)絡(luò)編碼組播樹的網(wǎng)絡(luò)拓?fù)涮匦蕴骄?/p> 網(wǎng)絡(luò)編碼組播樹中從源節(jié)點(diǎn)到目的節(jié)點(diǎn)必須具有多條分離路徑.因此要求給定的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)為連通圖且每個(gè)節(jié)點(diǎn)的度必須大于等于2.上述算法能夠生成較為隨機(jī)的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，但是生成的隨機(jī)網(wǎng)絡(luò)拓?fù)溥€存在一些無法滿足網(wǎng)絡(luò)編碼組播樹拓?fù)涮匦缘膯栴}.產(chǎn)生這些問題的主要原因是算法中的隨機(jī)生成數(shù)對(duì)(Ai，Bi)的隨機(jī)性，導(dǎo)致拓?fù)渖傻倪^程中對(duì)于邊和點(diǎn)的約束不充分. 下面對(duì)存在的孤點(diǎn)問題、不連通問題、度不可控問題進(jìn)行探討，其中描述的隨機(jī)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)均以無向圖來表示. (1)孤點(diǎn)問題.孤點(diǎn)是無向圖中度為0的節(jié)點(diǎn)，在無向圖中孤點(diǎn)不與其他任何節(jié)點(diǎn)相鄰接.上述算法容易產(chǎn)生孤點(diǎn)，對(duì)于基于網(wǎng)絡(luò)編碼的組播中仿真中，通常不希望孤點(diǎn)的存在.導(dǎo)致孤點(diǎn)存在的主要原因是在隨機(jī)數(shù)對(duì)產(chǎn)生過程中若不對(duì)Ai和Bi進(jìn)行限制，Ai和Bi可能只在一個(gè)小范圍內(nèi)產(chǎn)生，如果節(jié)點(diǎn)j(其中j∈{0,1,2……M-1})不在Ai和Bi產(chǎn)生的范圍內(nèi)，將會(huì)導(dǎo)致結(jié)點(diǎn)j不與任何其他結(jié)點(diǎn)有連接成為孤點(diǎn). (2)不連通問題.在無向圖中，如果存在兩個(gè)節(jié)點(diǎn)沒有通路，則該圖為不連通圖.組播網(wǎng)絡(luò)仿真過程中希望所有的生產(chǎn)圖均為連通圖.但是，上述算法在拓?fù)渖蛇^程中，因有連接的兩個(gè)節(jié)點(diǎn)(Ai，Bi)都是隨機(jī)產(chǎn)生的，因此在節(jié)點(diǎn)連接問題上很有可能產(chǎn)生多個(gè)小范圍的節(jié)點(diǎn)相互連接的問題，而在圖的總體上沒有聯(lián)通的情況，也就是生產(chǎn)的隨機(jī)拓?fù)淇赡艽嬖诓贿B通的問題. (3)度不可控問題.為了滿足網(wǎng)絡(luò)編碼需求，組播樹中從源節(jié)點(diǎn)到目的節(jié)點(diǎn)必須具有多條分離路徑.這就要求給定的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)是個(gè)連通圖且每個(gè)節(jié)點(diǎn)的度必須大于等于2.由于上述算法在產(chǎn)生隨機(jī)拓?fù)涞倪^程中節(jié)點(diǎn)之間的相互連接是完全隨機(jī)的，有些節(jié)點(diǎn)可能只與剩余節(jié)點(diǎn)中的一個(gè)節(jié)點(diǎn)相連接或者不與其他任何節(jié)點(diǎn)相連(即上述孤點(diǎn))，就會(huì)使拓?fù)渲挟a(chǎn)生度為1或者0的節(jié)點(diǎn)，不符合網(wǎng)絡(luò)編碼組播樹對(duì)于節(jié)點(diǎn)度的要求. 總的來說，基于總體布局的隨機(jī)網(wǎng)絡(luò)拓?fù)渖伤惴?，在雛形拓?fù)渖蛇^程中，從頂點(diǎn)分布到連接方式都是隨機(jī)產(chǎn)生，符合真實(shí)網(wǎng)絡(luò)中拓?fù)浣Y(jié)構(gòu)多樣化的特性，更加貼近真實(shí)的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu).也正由于拓?fù)渖煞绞降耐耆S機(jī)，生成過程中必然會(huì)產(chǎn)生以上描述的各個(gè)問題，從而使得生成的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)無法滿足網(wǎng)絡(luò)編碼組播樹的要求.因此，需要對(duì)上述算法進(jìn)行改進(jìn)，以生成滿足網(wǎng)絡(luò)編碼組播樹特定需求的隨機(jī)網(wǎng)絡(luò). 2面向網(wǎng)絡(luò)編碼組播樹的隨機(jī)拓?fù)渖伤惴?/p> 在基于總體布局隨機(jī)網(wǎng)絡(luò)拓?fù)渖伤惴ǖ囊笙律傻碾r形網(wǎng)絡(luò)，存在一些不符合基于網(wǎng)絡(luò)編碼組播樹對(duì)隨機(jī)拓?fù)涮卣餍枨蟮膯栴}，因此本部分在總體布局隨機(jī)拓?fù)渌惴óa(chǎn)生的雛形網(wǎng)絡(luò)的基礎(chǔ)上，針對(duì)存在的問題進(jìn)行改進(jìn)，使得算法生產(chǎn)的隨機(jī)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)滿足基于網(wǎng)絡(luò)編碼組播對(duì)隨機(jī)網(wǎng)絡(luò)的結(jié)構(gòu)要求，面向網(wǎng)絡(luò)編碼組播樹的隨機(jī)拓?fù)渖伤惴鞒虉D如圖2所示. 對(duì)于孤點(diǎn)問題、不連通問題、度不可控問題的解決方案為： (1)解決孤點(diǎn)問題.對(duì)于孤點(diǎn)問題的解決，通過遍歷鄰接矩陣GMM，找到第i行和第i列均為0 的節(jié)點(diǎn)i，i即為孤點(diǎn)，然后將孤點(diǎn)i與除該節(jié)點(diǎn)以外的，度數(shù)最小的節(jié)點(diǎn)相連，也就是遵循度數(shù)最小節(jié)點(diǎn)優(yōu)先選擇的原則，將有問題的節(jié)點(diǎn)與優(yōu)先于度數(shù)最小的節(jié)點(diǎn)相連接，這樣就將孤點(diǎn)重新融入到已生成的隨機(jī)網(wǎng)絡(luò)拓?fù)鋱D當(dāng)中.這樣做的同時(shí)也改變了某些節(jié)點(diǎn)的度數(shù)，為后續(xù)度不可控問題減少了工作量. (2)解決不連通的問題.首先深度優(yōu)先遍歷生成的整個(gè)雛形網(wǎng)絡(luò)拓?fù)鋱D，查找全局網(wǎng)絡(luò)拓?fù)涞倪B通分量數(shù)目，如果連通分支數(shù)量大于1，則說明該拓?fù)鋱D為非連通圖.對(duì)于該問題，根據(jù)連通分量的數(shù)目將每個(gè)連通分量看作一個(gè)單獨(dú)節(jié)點(diǎn)，重復(fù)全局隨機(jī)生成連接的方式，生成各個(gè)連通分量間的拓?fù)溥B接，在兩個(gè)有連接的連通分量中，隨機(jī)產(chǎn)生連通分量內(nèi)部具體節(jié)點(diǎn)對(duì)方的節(jié)點(diǎn)相連. 圖2 面向網(wǎng)絡(luò)編碼組播樹的隨機(jī)拓?fù)渖伤惴鞒虉D (3) 解決度不可控問題.對(duì)產(chǎn)生的雛形隨機(jī)網(wǎng)絡(luò)拓?fù)鋱D中的每個(gè)節(jié)點(diǎn)的度數(shù)實(shí)時(shí)更新，記錄每個(gè)節(jié)點(diǎn)度數(shù)，若有節(jié)點(diǎn)不符合網(wǎng)絡(luò)編碼組播樹對(duì)于節(jié)點(diǎn)度數(shù)的要求，依據(jù)度數(shù)小節(jié)點(diǎn)優(yōu)先選擇的原則，將不符合要求的節(jié)點(diǎn)，在本課題中即為節(jié)點(diǎn)度數(shù)不足2的節(jié)點(diǎn)，與除該節(jié)點(diǎn)外剩余節(jié)點(diǎn)中度數(shù)最小的節(jié)點(diǎn)相連，使得在改變自身節(jié)點(diǎn)度的同時(shí)，也在改變其他的節(jié)點(diǎn)的度數(shù)，為后續(xù)的重復(fù)操作減少了工作量.更新各節(jié)點(diǎn)度數(shù)，重復(fù)操作，直至每個(gè)節(jié)點(diǎn)的度數(shù)符合網(wǎng)絡(luò)編碼組播樹對(duì)節(jié)點(diǎn)度的要求，實(shí)現(xiàn)節(jié)點(diǎn)度的控制. 3仿真結(jié)果分析 為了驗(yàn)證改進(jìn)后算法的有效性，對(duì)算法進(jìn)行了仿真實(shí)驗(yàn)分析.本實(shí)驗(yàn)使用C#語言在Visual Studio 2012開發(fā)環(huán)境下，基于面向網(wǎng)絡(luò)編碼組播樹的隨機(jī)拓?fù)渖伤惴ㄔO(shè)計(jì)實(shí)現(xiàn)了隨機(jī)網(wǎng)絡(luò)生成系統(tǒng).為保證實(shí)驗(yàn)結(jié)果的可視性和可參考性，本課題將M的隨機(jī)范圍限制在[5，40]. 隨機(jī)生成的雛形隨機(jī)網(wǎng)絡(luò)中，隨機(jī)節(jié)點(diǎn)數(shù)M=15，隨機(jī)連接數(shù)N=29，雛形網(wǎng)絡(luò)拓?fù)淙鐖D3(a)所示，在拓?fù)鋱D中可以看出，生成的隨機(jī)網(wǎng)絡(luò)拓?fù)鋱D中節(jié)點(diǎn)0、節(jié)點(diǎn)2、節(jié)點(diǎn)7度數(shù)不可控制，不符合網(wǎng)絡(luò)編碼組播樹對(duì)于網(wǎng)絡(luò)節(jié)點(diǎn)度數(shù)至少為2的要求.修補(bǔ)過程中，首先記錄度數(shù)不可控的節(jié)點(diǎn)，然后將除節(jié)點(diǎn)0以外的所有節(jié)點(diǎn)排序，找到度數(shù)最小的節(jié)點(diǎn)，將節(jié)點(diǎn)0與度數(shù)最小節(jié)點(diǎn)相連接，保證了節(jié)點(diǎn)0的度數(shù)至少為2，以此類推可使得節(jié)點(diǎn)2與節(jié)點(diǎn)7度數(shù)完全符合網(wǎng)絡(luò)編碼組播樹的需求，最終成形撲如圖3(b)所示. (a) 雛形網(wǎng)絡(luò)拓?fù)洹 ?(b)成形絡(luò)拓?fù)鋱D3 M=15，N=29的隨機(jī)網(wǎng)絡(luò)拓?fù)鋱D 如圖4(a)所示的雛形網(wǎng)絡(luò)拓?fù)渲?，隨機(jī)節(jié)點(diǎn)數(shù)M=14，隨機(jī)連接數(shù)N=18，存在孤點(diǎn)9，同時(shí)生成的拓?fù)鋱D因孤點(diǎn)9的存在,形成了具有兩個(gè)連通分量的非連通圖.對(duì)于孤點(diǎn)的處理，采取的措施是：將孤點(diǎn)9重新融入到由剩余節(jié)點(diǎn)形成的連通分量當(dāng)中，在該連通分量當(dāng)中尋找節(jié)點(diǎn)度數(shù)最小的節(jié)點(diǎn)，將其與孤點(diǎn)9相連.這樣操作不僅解決了孤點(diǎn)的問題同時(shí)也解決了非連通圖的問題.孤點(diǎn)問題解決之后，圖中還存在度數(shù)不可控的節(jié)點(diǎn)，操作過程與圖3的處理過程類似，在此不做贅述.最終成形拓?fù)淙鐖D4(b)所示. (a) 雛形網(wǎng)絡(luò)拓?fù)洹 ?(b)成形絡(luò)拓?fù)鋱D4 M=14,N=18的隨機(jī)網(wǎng)絡(luò)拓?fù)鋱D 4結(jié)束語 面向網(wǎng)絡(luò)編碼組播樹的隨機(jī)拓?fù)渖伤惴ㄔ诳傮w布局隨機(jī)網(wǎng)絡(luò)拓?fù)渖伤惴ǖ幕A(chǔ)上，結(jié)合網(wǎng)絡(luò)編碼組播樹對(duì)于網(wǎng)絡(luò)拓?fù)涞奶厥庖蟾倪M(jìn)基于總體布局隨機(jī)網(wǎng)絡(luò)拓?fù)渖a(chǎn)算法.根據(jù)隨機(jī)網(wǎng)絡(luò)算法生成的雛形網(wǎng)絡(luò)，在滿足網(wǎng)絡(luò)編碼組播樹拓?fù)湟蟮臈l件下，對(duì)得到的雛形網(wǎng)絡(luò)進(jìn)行修補(bǔ)，主要針對(duì)雛形網(wǎng)絡(luò)中的孤立點(diǎn)、不連通以及節(jié)點(diǎn)度不可控制等不滿足網(wǎng)絡(luò)編碼組播樹需求的特征進(jìn)行修整，使得生成的隨機(jī)網(wǎng)絡(luò)更加符合網(wǎng)絡(luò)編碼組播樹的拓?fù)浞抡嫘枨? 參考文獻(xiàn): [1]Qu Z J, Liu X H, Huang J J, et al. Genetic local search algorithm for network coding resources minimization [C]// 2012 IEEE International Conference on Computer Science and Automation Engineering, 2012: 782-786. [2]Qu Z J, Liu X H, Fu J. Genetic algorithm-based network coding resources optimization in multimedia network [C]//2012 International Conference on Systems and Informatics, 2012: 1 547-1 550. [3] 張宇,張宏莉,方濱興.Internet拓?fù)浣＞C述[J].軟件學(xué)報(bào),2004,15(8):1220-1226. [4]蔡慧,劉洪波,韓國棟.基于K均值聚類的隨機(jī)網(wǎng)絡(luò)拓?fù)淠Ｐ蚚J].計(jì)算機(jī)工程與設(shè)計(jì),2009,30(5):1 089-1 091. [5]姚文斌,韓司,姚翔.一種基于總體布局的隨機(jī)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)生成:中國,103457860 A[P].2013-09-03. (編輯：劉寶江) Research on network coding based multicast-oriented random topology generation algorithm GU Ye-lu, LIU Xiao-hong, QU Zhi-jian, ZHANG Ai-feng (School of Computer Science and Technology, Shandong University of Technology, Zibo 255049, China) Abstract:A novel random topology network algorithm was presented to meet the requirements for establishing the network coding based multicast tree. Firstly, a primitive random topology was generated according to the overall layout random topology network. Secondly, the obtained primitive random topology was repaired in terms of solitary point, network connectivity, degrees of each node to remove the negative effects of unsuitable for establishing network coding based multicast tree. Finally, the proposed algorithm was tested, and the results indicated that the generated random topology meet the requirements of establishing the network coding based multicast tree. The proposed algorithm can provide plenty of simulation resources for the network coding based multicast research. Key words:network coding； multicast tree； random topology 中圖分類號(hào)：TP393.0 文獻(xiàn)標(biāo)志碼：A 文章編號(hào)：1672-6197(2016)02-0001-04 作者簡介：顧葉露，女，jiangmi22@163.com； 通信作者： 劉曉紅,女，Liuxh88@tom.com 基金項(xiàng)目：國家自然科學(xué)基金項(xiàng)目(61473179);山東省自然科學(xué)基金項(xiàng)目(ZR2014FM007);山東省優(yōu)秀中青年科學(xué)家科研獎(jiǎng)勵(lì)基金項(xiàng)目(BS2013DX032);山東理工大學(xué)青年教師發(fā)展計(jì)劃項(xiàng)目 收稿日期：2015-03-19
