[發(fā)明專利]基于標號優(yōu)化的最小化帶寬消耗組播路由方法

有效

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

技術領域

本發(fā)明涉及一種組播路由方法，特別是提供了一種基于標號優(yōu)化的組播樹的建立方法，通過該方法得到的組播樹帶寬消耗少，可以節(jié)省網(wǎng)絡帶寬資源。

背景技術

在對組播樹結(jié)構(gòu)的研究中，大家普遍認為，組播的帶寬消耗主要表現(xiàn)在節(jié)點對信息復制的份數(shù)上，也即表現(xiàn)在所建組播樹的總邊數(shù)上，要想最小化組播的帶寬消耗，就要最小化組播樹的邊數(shù)，也即最小化組播樹中引入的除源節(jié)點和目的節(jié)點之外的節(jié)點數(shù)，這就是網(wǎng)絡中的Steiner樹問題。然而，上述理論在有線網(wǎng)絡中是正確的，在無線網(wǎng)絡中的結(jié)果就有所不同了。文獻“Heuristicalgorithms?for?minimum?bandwidth?consumption?multicast?routing?inwireless?mesh?networks”提出，在無線網(wǎng)絡中，由于無線傳輸?shù)膹V播特性，組播的帶寬消耗主要依賴于組播樹中的轉(zhuǎn)發(fā)次數(shù)，也即依賴于組播樹中承擔轉(zhuǎn)發(fā)任務的節(jié)點個數(shù)，這樣一來，最小化帶寬消耗的目標就是要建立一棵轉(zhuǎn)發(fā)節(jié)點數(shù)最少的組播樹。這個問題用數(shù)學語言可以表述如下：在一個給定的網(wǎng)絡G中，對于源節(jié)點s和目的節(jié)點集D＝{D₁，D₂，…，D_k}，求一棵以s為根的組播樹T，使得且|{v∈V(T)/{s}|d(v)≥2}|最小。它已經(jīng)被證明是NP-完備的，

針對這個問題，目前主要是將這個問題轉(zhuǎn)化為最小連通控制集或Steiner樹問題進行研究。文獻“Routing?in?ad-hoc?networks?using?a?virtual?backbone”中的算法是點覆蓋的最早的分布式執(zhí)行算法，它首先從所有節(jié)點中選擇度最大的節(jié)點，標記為控制集節(jié)點，然后選擇在兩跳鄰居節(jié)點中未標記的鄰居節(jié)點數(shù)目最大的節(jié)點作為控制節(jié)點，將這些由不同的控制節(jié)點及其鄰居節(jié)點組成的部分看作是連通控制集的不同組件，重新對邊賦權(quán)為1或2，權(quán)值取決于該邊的端點有一個或兩個不在以上標記的控制集中。最后用MST(Minimum?Spanning?Tree)算法連接不同組件，得到的支撐樹中的轉(zhuǎn)發(fā)節(jié)點就是連接控制集節(jié)點。文獻“Oncalculating?connected?dominating?set?for?efficient?routing?in?ad-hocwireless?networks”中的算法首先找到一個連通控制集，然后從這個控制集中刪除本地多余節(jié)點。本地多余節(jié)點具有一個或兩個特殊的鄰居節(jié)點，它們比該本地多余節(jié)點的ID大，且能控制受該本地多余節(jié)點控制的所有節(jié)點。這種算法僅適用于非完全連通的單元盤ad?hoc網(wǎng)絡模型。文獻“Distributed?Heuristicsfor?Connected?Dominat?ing?Sets?in?Wireless?Ad?Hoc?Networks”的分布式算法分兩步執(zhí)行，先通過等級劃分和顏色標記建立一個最大獨立集，直到所有節(jié)點的顏色都被標記以后，將最大獨立集中的節(jié)點連接起來構(gòu)成連通控制集。文獻“Heuristic?algorithms?for?minimum?bandwidth?consumption?multicastrouting?in?wireless?mesh?networks”提出了一個集中式的貪婪啟發(fā)式算法，并給出了算法的分布式實現(xiàn)。該算法由兩部分組成：構(gòu)建一些費用低的子樹，將這些子樹的根節(jié)點按照MST算法連成一棵近似Steiner樹。其貪婪啟發(fā)式算法得到的組播樹的數(shù)據(jù)傳輸費用不超過Steiner啟發(fā)式算法得到的組播樹。

發(fā)明內(nèi)容

本發(fā)明要解決的技術問題是針對現(xiàn)有技術中存在的不足，提供一種基于標號優(yōu)化的最小化帶寬消耗組播路由方法，建立一棵組播樹，節(jié)省網(wǎng)絡帶寬消耗。

本發(fā)明基于標號優(yōu)化的最小化帶寬消耗組播路由方法通過下述技術方案予以實現(xiàn)：本發(fā)明的本質(zhì)是利用標號在已有的組播樹上進行優(yōu)化。本發(fā)明所述的方法是采用已有的方法先建立一棵組播樹，然后按照標號規(guī)則給樹中的節(jié)點進行標號，通過修改節(jié)點間鄰接關系的規(guī)則和修改標號規(guī)則來刪除轉(zhuǎn)發(fā)節(jié)點或?qū)⑵渥優(yōu)槿~子節(jié)點，以此來減少組播樹中的轉(zhuǎn)發(fā)節(jié)點個數(shù)，即給定網(wǎng)絡拓撲圖G，源節(jié)點s，目的節(jié)點集D＝{D₁，D₂，...，D_k}，通過本方法找到一棵以s為根的轉(zhuǎn)發(fā)節(jié)點數(shù)較少的組播樹，所述的方法包括如下步聚：

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