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

無效

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

1.一種結合Waxman模型與域模型的隨機網絡拓撲建立的方法，其生成 過程為：

1)進行區域劃分，人為地將整個區域劃分為幾個小的區域，在此為了編 程生成簡便，采用將大區域進行等分的方式進行了生成，注意在分割 的時候，如果采用等分，不宜將子網劃分的過小，否則分域效果將不 明顯，一般劃為4-8個為宜；

2)隨機生成一對隨機數，這個隨機數是獨立生成的，但需要預先知道整 個隨機數的取值范圍，此范圍是子區域的范圍，隨機生成的數對代表 著節點在子網中的位置坐標并按照生成的先后順序給每個節點進行編 號；

3)在域內采用Waxman方式，確定拓撲連接；

4)根據域內拓撲連接情況，確定出網絡的鄰接矩陣；如子網內若有N個 節點，便確定一個N*N的矩陣，有連接便記做1，沒有連接記做0；然 后進行對每一行或者每一列求和，得出每個節點的度，其和記做 sum_i；按照以下規則進行域內修補：

i.sum_i＞＝a，不做任何處理

ii.sum_i＜a，進行隨機修補

其中a表示從源節點到目的節點發送a路獨立的信息流；

5)隨機修補方法：

i.對需要修補的節點，隨機選擇除了這個節點的其余節點， 而后進行相連；

ii.連接后進行鄰接矩陣的改變與節點度數值的改變；

6)修補后再進行鄰接矩陣的判定，當每個節點都能滿足條件sum_i＞＝a 的時候，域內生成就到此結束；

7)改變子區域的坐標取值范圍，重復以上2-6步，進行其他域的網絡生 成；

8)待生成完所有子域之后，再進行區域之間的連接，區域之間的連接類 似于區域內的修補，把每個子區域看作是一個小的節點，每個“節點” 之間的度也要保證大于a，這樣就可以保證位于任意兩個子域內的任 何節點之間都可以進行實現至少a條獨立路徑的通信，這樣給要實現 網絡編碼提供了條件；

9)在區域之間進行連接之后，進行修補，此時采用的方法類似在原來域 內節點之間的鄰接矩陣的方法進行判定，同樣當其鄰接矩陣滿足每個 子區域對外至少有a條路徑的時侯生成結束。