一種面向網絡編碼組播樹的隨機拓撲生成算法

顧葉露， 劉曉紅， 曲志堅， 張愛鳳

(山東理工大學 計算機科學與技術學院， 山東 淄博 255049)

?

一種面向網絡編碼組播樹的隨機拓撲生成算法

顧葉露， 劉曉紅， 曲志堅， 張愛鳳

(山東理工大學 計算機科學與技術學院， 山東 淄博 255049)

摘要：為了建立滿足網絡編碼需求的組播樹，提出一種面向網絡編碼組播樹的隨機拓撲生成算法.首先依據總體布局隨機網絡拓撲生成算法，生成隨機的雛形網絡拓撲；然后結合網絡編碼組播樹的拓撲特性，對已生成的雛形網絡在孤點、連通性、度控制等方面進行修補，使最終生成的網絡拓撲滿足網絡編碼組播樹的拓撲要求.

關鍵詞：網絡編碼； 組播樹； 隨機拓撲

建立網絡編碼組播樹是實現網絡編碼組播要求的重要基礎，近年來研究人員在基于網絡編碼組播樹建樹和資源優化方面提出了許多重要算法.為對基于網絡編碼組播樹建樹和資源優化而提出的算法進行測試和評價，需要將所提出的算法應用于大量網絡拓撲結構. 以此來測試不同網絡結構下網絡編碼技術對網絡性能的影響.其中就有基于時延、時延抖動以及網絡編碼資源最小化等多目標約束條件，曲志堅等人在基于遺傳算法的網絡編碼方面做出了系列研究[1-2].

基于網絡編碼的組播跟傳統組播對網絡拓撲結構的需求有明顯的區別，導致現存的各種隨機拓撲生成方法無法直接使用.目前，對面向網絡編碼技術的隨機網絡拓撲生成算法大多是以經典的拓撲或在其基礎上稍加修改為藍本進行的[3].如蔡慧等人提出了一種基于K均值聚類的隨機網絡拓撲模型[4]，解決了在Waxman隨機網絡拓撲模型模擬過程中網絡節點疏密不當、節點難以控制、難以生成連通圖等缺點；姚文斌等人提出了一種基于總體布局的隨機網絡拓撲結構生成方法[5]，該方法生成的拓撲更接近真實網絡，突出模擬網絡的隨機性.但上述隨機拓撲生產算法都無法直接生成滿足網絡編碼需要的隨機網絡拓撲.

為了生成符合網絡編碼組播樹的網絡拓撲，提出了一種面向網絡編碼組播樹的隨機網絡拓撲生成算法，該算法基于總體布局隨機網絡拓撲生成算法，結合網絡編碼組播樹在拓撲模擬建模方面的特性要求,進而生成符合網絡編碼組播樹的拓撲結構.

1基于總體布局的隨機網絡拓撲生成算法

1.1算法梗概

基于總體布局的隨機網絡拓撲生成算法，可通過多次隨機過程模擬生成隨機網絡，每次產生的模擬網絡從頂點分布到模擬方式都不盡相同，符合真實網絡多樣性的特征，克服了隨機網絡拓撲很難貼近真實網絡的缺點.基于總體布局的隨機網絡拓撲生成算法流程如圖1所示.

圖1　基于總體布局的隨機網絡拓撲生成算法流程圖

實現隨機網絡雛形拓撲的過程如下.

(1)依據基于總體布局的隨機網絡拓撲生成算法，首先隨機生成拓撲節點數目M，并依次為每個生成的隨機節點從0到M-1進行標號.

(2)隨機生成拓撲連接數N，表示M個隨機節點中存在的連接的數目，其中N的取值范圍必須控制在1

(3)隨機生成N對隨機數對(Ai，Bi)，表示隨機生成了N條連接，其中每個隨機對表示節點Ai與節點Bi之間有一條邊直接關聯，其中Ai∈{0,1,2…M-2}，Bi∈{0,1,2…M-1}，且Ai從閉區間[0，M-2]范圍內隨機產生，Bi根據Ai產生的節點序號從閉區間[Ai+1，M-1] 的范圍內產生，這樣做的目的是防止重邊和自環問題的產生.

在圖論中，所謂自環就是兩個端點為同一頂點的邊.在隨機數對(Ai，Bi)的產生過程中，若Ai，Bi值的產生完全隨機，也就是任何兩個節點之間的連接是完全隨機的并且均在[0，M-1]的范圍內產生，有可能會在生成圖中產生自環.例如，Ai和Bi的隨機值為同一節點q，q∈{0,1,2…M-1}，即產生了(q，q)的連接，那么在生產的拓撲中節點q就會出現自環.

而重邊則是由于隨機拓撲為無向圖，因此在隨機數對(Ai，Bi)的產生過程中，當Ai和Bi的產生完成，在Ai+1和Bi+1的節點產生過程中，若與Ai和Bi產生的隨機節點相同，即有Ai=Bi，Ai+1=Bi+1，或者Ai=Bi+1且Ai+1=Bi的情況發生，已產生的節點連接就會在后面的隨機數對產生過程中重復連接，從而產生重邊問題.

(4)在隨機網絡拓撲隨機數對生成過程中，為避免重邊和自環的產生，在鄰接矩陣中只保留除去對角線元素外的右上三角部分，即，在產生的隨機數對(Ai，Bi)中只保留Ai

(5)根據生成的N對隨機數對，填充M*M階隨機拓撲的鄰接矩陣GMM，在矩陣中元素1代表相應的兩個節點有連接，元素0則表示兩個節點間無連接.

1.2面向網絡編碼組播樹的網絡拓撲特性探究

網絡編碼組播樹中從源節點到目的節點必須具有多條分離路徑.因此要求給定的網絡拓撲結構為連通圖且每個節點的度必須大于等于2.上述算法能夠生成較為隨機的網絡拓撲結構，但是生成的隨機網絡拓撲還存在一些無法滿足網絡編碼組播樹拓撲特性的問題.產生這些問題的主要原因是算法中的隨機生成數對(Ai，Bi)的隨機性，導致拓撲生成的過程中對于邊和點的約束不充分.

下面對存在的孤點問題、不連通問題、度不可控問題進行探討，其中描述的隨機網絡拓撲結構均以無向圖來表示.

(1)孤點問題.孤點是無向圖中度為0的節點，在無向圖中孤點不與其他任何節點相鄰接.上述算法容易產生孤點，對于基于網絡編碼的組播中仿真中，通常不希望孤點的存在.導致孤點存在的主要原因是在隨機數對產生過程中若不對Ai和Bi進行限制，Ai和Bi可能只在一個小范圍內產生，如果節點j(其中j∈{0,1,2……M-1})不在Ai和Bi產生的范圍內，將會導致結點j不與任何其他結點有連接成為孤點.

(2)不連通問題.在無向圖中，如果存在兩個節點沒有通路，則該圖為不連通圖.組播網絡仿真過程中希望所有的生產圖均為連通圖.但是，上述算法在拓撲生成過程中，因有連接的兩個節點(Ai，Bi)都是隨機產生的，因此在節點連接問題上很有可能產生多個小范圍的節點相互連接的問題，而在圖的總體上沒有聯通的情況，也就是生產的隨機拓撲可能存在不連通的問題.

(3)度不可控問題.為了滿足網絡編碼需求，組播樹中從源節點到目的節點必須具有多條分離路徑.這就要求給定的網絡拓撲結構是個連通圖且每個節點的度必須大于等于2.由于上述算法在產生隨機拓撲的過程中節點之間的相互連接是完全隨機的，有些節點可能只與剩余節點中的一個節點相連接或者不與其他任何節點相連(即上述孤點)，就會使拓撲中產生度為1或者0的節點，不符合網絡編碼組播樹對于節點度的要求.

總的來說，基于總體布局的隨機網絡拓撲生成算法，在雛形拓撲生成過程中，從頂點分布到連接方式都是隨機產生，符合真實網絡中拓撲結構多樣化的特性，更加貼近真實的網絡拓撲結構.也正由于拓撲生成方式的完全隨機，生成過程中必然會產生以上描述的各個問題，從而使得生成的網絡拓撲結構無法滿足網絡編碼組播樹的要求.因此，需要對上述算法進行改進，以生成滿足網絡編碼組播樹特定需求的隨機網絡.

2面向網絡編碼組播樹的隨機拓撲生成算法

在基于總體布局隨機網絡拓撲生成算法的要求下生成的雛形網絡，存在一些不符合基于網絡編碼組播樹對隨機拓撲特征需求的問題，因此本部分在總體布局隨機拓撲算法產生的雛形網絡的基礎上，針對存在的問題進行改進，使得算法生產的隨機網絡拓撲結構滿足基于網絡編碼組播對隨機網絡的結構要求，面向網絡編碼組播樹的隨機拓撲生成算法流程圖如圖2所示.

對于孤點問題、不連通問題、度不可控問題的解決方案為：

(1)解決孤點問題.對于孤點問題的解決，通過遍歷鄰接矩陣GMM，找到第i行和第i列均為0 的節點i，i即為孤點，然后將孤點i與除該節點以外的，度數最小的節點相連，也就是遵循度數最小節點優先選擇的原則，將有問題的節點與優先于度數最小的節點相連接，這樣就將孤點重新融入到已生成的隨機網絡拓撲圖當中.這樣做的同時也改變了某些節點的度數，為后續度不可控問題減少了工作量.

(2)解決不連通的問題.首先深度優先遍歷生成的整個雛形網絡拓撲圖，查找全局網絡拓撲的連通分量數目，如果連通分支數量大于1，則說明該拓撲圖為非連通圖.對于該問題，根據連通分量的數目將每個連通分量看作一個單獨節點，重復全局隨機生成連接的方式，生成各個連通分量間的拓撲連接，在兩個有連接的連通分量中，隨機產生連通分量內部具體節點對方的節點相連.

圖2　面向網絡編碼組播樹的隨機拓撲生成算法流程圖

(3) 解決度不可控問題.對產生的雛形隨機網絡拓撲圖中的每個節點的度數實時更新，記錄每個節點度數，若有節點不符合網絡編碼組播樹對于節點度數的要求，依據度數小節點優先選擇的原則，將不符合要求的節點，在本課題中即為節點度數不足2的節點，與除該節點外剩余節點中度數最小的節點相連，使得在改變自身節點度的同時，也在改變其他的節點的度數，為后續的重復操作減少了工作量.更新各節點度數，重復操作，直至每個節點的度數符合網絡編碼組播樹對節點度的要求，實現節點度的控制.

3仿真結果分析

為了驗證改進后算法的有效性，對算法進行了仿真實驗分析.本實驗使用C#語言在Visual Studio 2012開發環境下，基于面向網絡編碼組播樹的隨機拓撲生成算法設計實現了隨機網絡生成系統.為保證實驗結果的可視性和可參考性，本課題將M的隨機范圍限制在[5，40].

隨機生成的雛形隨機網絡中，隨機節點數M=15，隨機連接數N=29，雛形網絡拓撲如圖3(a)所示，在拓撲圖中可以看出，生成的隨機網絡拓撲圖中節點0、節點2、節點7度數不可控制，不符合網絡編碼組播樹對于網絡節點度數至少為2的要求.修補過程中，首先記錄度數不可控的節點，然后將除節點0以外的所有節點排序，找到度數最小的節點，將節點0與度數最小節點相連接，保證了節點0的度數至少為2，以此類推可使得節點2與節點7度數完全符合網絡編碼組播樹的需求，最終成形撲如圖3(b)所示.

(a) 雛形網絡拓撲　　　 (b)成形絡拓撲圖3　M=15，N=29的隨機網絡拓撲圖

如圖4(a)所示的雛形網絡拓撲中，隨機節點數M=14，隨機連接數N=18，存在孤點9，同時生成的拓撲圖因孤點9的存在,形成了具有兩個連通分量的非連通圖.對于孤點的處理，采取的措施是：將孤點9重新融入到由剩余節點形成的連通分量當中，在該連通分量當中尋找節點度數最小的節點，將其與孤點9相連.這樣操作不僅解決了孤點的問題同時也解決了非連通圖的問題.孤點問題解決之后，圖中還存在度數不可控的節點，操作過程與圖3的處理過程類似，在此不做贅述.最終成形拓撲如圖4(b)所示.

(a) 雛形網絡拓撲　　　　　　　 (b)成形絡拓撲圖4　M=14,N=18的隨機網絡拓撲圖

4結束語

面向網絡編碼組播樹的隨機拓撲生成算法在總體布局隨機網絡拓撲生成算法的基礎上，結合網絡編碼組播樹對于網絡拓撲的特殊要求改進基于總體布局隨機網絡拓撲生產算法.根據隨機網絡算法生成的雛形網絡，在滿足網絡編碼組播樹拓撲要求的條件下，對得到的雛形網絡進行修補，主要針對雛形網絡中的孤立點、不連通以及節點度不可控制等不滿足網絡編碼組播樹需求的特征進行修整，使得生成的隨機網絡更加符合網絡編碼組播樹的拓撲仿真需求.

參考文獻:

[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拓撲建模綜述[J].軟件學報,2004,15(8):1220-1226.

[4]蔡慧,劉洪波,韓國棟.基于K均值聚類的隨機網絡拓撲模型[J].計算機工程與設計,2009,30(5):1 089-1 091.

[5]姚文斌,韓司,姚翔.一種基于總體布局的隨機網絡拓撲結構生成:中國,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

中圖分類號：TP393.0

文獻標志碼：A

文章編號：1672-6197(2016)02-0001-04

作者簡介：顧葉露，女，jiangmi22@163.com； 通信作者： 劉曉紅,女，Liuxh88@tom.com

基金項目：國家自然科學基金項目(61473179);山東省自然科學基金項目(ZR2014FM007);山東省優秀中青年科學家科研獎勵基金項目(BS2013DX032);山東理工大學青年教師發展計劃項目

收稿日期：2015-03-19