[發明專利]基于標號優化的最小化帶寬消耗組播路由方法

有效

• 申請號: 200910058409.8
• 申請日: 2009-02-20
• 公開（公告）號: CN101483598A
• 公開（公告）日: 2009-07-15
• 發明（設計）人: 林大澤;周賢偉;張永德;林琳;肖云;溫海燕;劉煥德;劉麗麗
• 申請（專利權）人: 西部礦業股份有限公司
• 主分類號: H04L12/56
• 分類號: H04L12/56;H04L12/18
• 代理公司: 西寧金語專利代理事務所
• 代理人: 哈慶華

1.一種基于標號優化的最小化帶寬消耗組播路由方法，其特征在于：所述的方法是采用已有的方法先建立一棵組播樹，然后按照標號規則給樹中的節點進行標號，通過修改節點間鄰接關系的規則和修改標號規則來刪除轉發節點或將其變為葉子節點，以此來減少組播樹中的轉發節點個數，即給定網絡拓撲圖G，源節點s，目的節點集D＝{D₁，D₂，...，D_k}，通過本方法找到一棵以s為根的轉發節點數較少的組播樹，所述的方法包括如下步聚：

1)求出G中任一支撐樹，并將不是源節點和目的節點的葉子節點刪除，得到組播樹T，求出生成圖G_T＝G[V(T)]；

2)按標號規則對T中節點進行標號，分別求出2-節點、3-節點和4-節點的個數為N₂，N₃，N₄，總轉發節點數為FW＝N₂+N₃，l＝l+1；

3)對T中的4-節點，3-節點和2-節點，按照節點間鄰接關系進行修改；

4)根據修改標號的規則檢查T中的3-節點；

5)若FW＝N₂+N₃，l＝l+1；否則，l＝0；若l＝2，則當前組播樹和轉發節點數FW就是所述方法得到的結果；

所述的標號規則包括：

1)將源節點s標號為1；

2)將在T和G_T中均與一個葉子節點相鄰的節點標號為2；

3)將T中除標號為1和2的其它非葉子節點標號為3；

4)將T中的葉子節點標號為4；

所述的修改節點間鄰接關系規則包括：

1)對于T中與1-節點或2-節點相鄰的4-節點，刪除G_T中4-節點其它的關聯邊；

2)對于T中與3-節點相鄰的4-節點，分兩種情況：

a)若它在G_T中還與1-節點或2-節點相鄰，則修改T中4-節點的鄰節點為1-節點或2-節點，并刪除G_T中4-節點其它的關聯邊；

b)若T中與3-節點相鄰的4-節點在G_T中也只與3-節點相鄰，將當前在T中與之相鄰的3-節點度數減1，并分別計算在G_T中與之相鄰的其它3-節點在T中的度數，通過比較大小，在T中將4-節點與計算得到的度數最大的3-節點進行關聯；新邊在T中形成了包含4-節點的唯一的一個圈，刪除這個圈中4-節點的除新加入邊之外的另一條關聯邊，在G_T中刪除4-節點不在T中的其它關聯邊；

3)對于在T中只與3-節點和4-節點關聯的3-節點，分兩種情況：

a)若3-節點在T中不與1-節點或2-節點相鄰，但在G_T中卻與1-節點或2-節點相鄰，則在T中添加3-節點與1-節點或2-節點之間的一條關聯邊，這樣在T中形成了包含3-節點的唯一的一個圈，刪除圈中3-節點的除新添加邊之外的另一條關聯邊，同時在G_T中刪除3-節點不在T中的其它關聯邊；

b)或3-節點在G_T中也只與3-節點和4-節點相鄰，將當前在T中與之相鄰的3-節點度數減1，并分別計算在G_T中與之相鄰的其它3-節點在T中的度數，通過比較大小，在T中將3-節點與計算得到的度數最大的3-節點進行關聯；加入的新邊在T中形成了包含3-節點的唯一的一個圈，刪除圈中3-節點的除新添加邊之外的另一條關聯邊，同時在G_T中刪除3-節點不在T中的其它關聯邊；

4)對于在T中不與1-節點相鄰的2-節點，若在G_T中與1-節點相鄰，則在T中添加2-節點與1-節點的一條關聯邊，加入新邊在T中形成了包含2-節點的唯一的一個圈，刪除圈中2-節點的除新加入邊之外的另一條關聯邊，同時在G_T中刪除2-節點不在T中的其它關聯邊；

所述的修改標號規則包括：檢查當前T中的3-節點，分三種情況，

1)若3-節點變為葉子節點且是目的節點，將其標號改為4；

2)若3-節點變為葉子節點但不是目的節點，將其刪除；

3)若3-節點在T和G_T中均與一個葉子相鄰，將其標號改為2；

所述的修改T中3-節點后：

1)若修改滿足3-節點變為葉子節點且是目的節點，N₃＝N₃-1，N₄＝N₄+1；

2)若修改滿足3-節點變為葉子節點但不是目的節點，N₃＝N₃-1；

3)若修改滿足3-節點在T和G_T中均與一個葉子節點相鄰，N₃＝N₃-1，N₂＝N₂+1；

所述的標號為i(i＝1，2，3，4)的節點在不加區分的敘述中統稱為i-節點。