[發明專利]一種適合于網絡編碼的隨機網絡拓撲生成方法

無效

• 申請號: 200910084855.6
• 申請日: 2009-05-26
• 公開（公告）號: CN101577655A
• 公開（公告）日: 2009-11-11
• 發明（設計）人: 柏琳;荊震
• 申請（專利權）人: 北京郵電大學
• 主分類號: H04L12/28
• 分類號: H04L12/28;H04L12/56
• 代理公司: 暫無信息
• 代理人: 暫無信息

技術領域

本發明結合了不同的隨機網絡拓撲生成方式，針對于網絡編碼技術 要求，提出了一種適合于網絡編碼技術仿真的隨機網絡拓撲生成方式。 屬于網絡技術領域。

背景技術

網絡編碼是一種融合編碼和路由的信息交換技術，在傳統存貯轉發的路 由方法基礎上，通過允許對接受的多個數據包進行編碼信息融合的方式，增 加單次傳輸的信息量，提高網絡整體性能。

隨著網絡編碼技術的發展，對于網絡編碼技術和性能的仿真顯得越來越 重要。由于網絡的多樣性和復雜性，對于網絡研究者來說，網絡模擬需要提 供足夠多的多樣性的“場景”，來進行運行，得到不同網絡情況下的仿真的 結果。若單純地以一些著名的網絡為基礎，或在這些基礎上進行稍微的改變 來進行網絡仿真，這些不能動態地反映網絡現在與將來的情況。而隨機網絡 是比較好的一種選擇，它既能較好的模擬網絡的性能參數，又可以模擬更多 不同的網絡的結構。如果能采用隨機網絡作為網絡編碼技術的仿真網絡，對 于網絡編碼技術的研究具有重要意義。

現有最常用隨機拓撲生成方法是基于Waxman模型的，Waxman算法提出 假設網絡規模節點數n，然后按照如下公式進行概率p_e是一種來決定兩個節 點u，v間是否存在一條直接相連的鏈路。概率計算公式：

pe=(u,v)=β*exp-l(u,v)L*α]]>

其中，參數l(u，v)為之間u，v的幾何距離，L為拓撲圖中所有節點距離的最大 值，α，β是調節網絡特性的參數，為(0，1]區間的實數；α控制網絡中長邊與短邊的 比例，β控制網絡的度數，選擇適當的α，β值能使得生成的隨機網絡更接近現實 網絡。

雖然Waxman模型和其改進型都在試圖接近實際網絡，但現在的網絡是 個分域的結構。Waxman模型仍存在以下缺點：

1.不能很好的模仿出網絡真實的分層分域結構。

2.生成的隨機網絡不能保證具有連通性。

3.即使生成了連通網絡，也不能保證其最小割為a(至少為2)，以保 證能夠進行網絡編碼操作。

針對這幾點缺點，此方案將分域模型與Waxman模型進行了融合，并且 針對于網絡編碼技術的網絡特點進行了修補，使得整個網絡結構既具有隨機 性，又可以滿足進行網絡編碼仿真的要求。

發明內容

本發明所要解決的問題是，實現一種可以進行網絡編碼仿真的具有分域 的隨機網絡拓撲。

本方案提出了一種結合了域空間模型和Waxman模型。先將要生成的網 絡區域進行區域分割，分割成幾個位置不同的域，在每個域內采用Waxman 方法進行隨機拓撲生成，之后再進行域內修補以規避Waxman生成模型出現 的孤點。生成各個域內的網絡之后，再進行域間連接，當出現不符合網絡編 碼的要求的時候，在進行網間修補，以保證任意兩個域中的兩個節點之間都 能作為信源和信宿，進行網絡編碼技術仿真。

這樣的生成方式能夠保證生成的隨機網絡，具有分域的結構，而且生成 的網絡達到了網絡編碼技術的仿真的要求。

方案的具體實現方法是：在實現隨機拓撲上，融合了Waxman模型和域 模型兩種方案，并以局部隨機修補的方式進行了拓撲的調整，生成出適合于 仿真網絡編碼的隨機拓撲網絡。

整個隨機網絡拓撲的生成流程是這樣：

1.將整個區域劃分成若干域

2.在域內采用Waxman模型生成子網

3.進行域內的修補，在域內消除孤點

4.進行域間的連接

5.域間的連接修補

附圖說明