[發明專利]基于MCDS近似算法的最小化資源消耗的組播路由方法

有效

• 申請號: 200910058410.0
• 申請日: 2009-02-20
• 公開（公告）號: CN101562780A
• 公開（公告）日: 2009-10-21
• 發明（設計）人: 林大澤;周賢偉;張永德;彭萊;吳敏;李永芳;汪林
• 申請（專利權）人: 西部礦業股份有限公司
• 主分類號: H04W4/06
• 分類號: H04W4/06;H04W8/08;H04W40/04;H04W84/18
• 代理公司: 西寧金語專利代理事務所
• 代理人: 哈慶華

技術領域

本發明屬于無線網絡通信中的路由優化技術，涉及到節省無線網絡中無線廣播發送的能量和帶寬資源消耗的問題，基于圖論中的MCDS(最小連通支配集)問題，提出了一種最小化網絡通信資源消耗的分布式組播樹的構建方法。

背景技術

無線Ad?hoc網絡由一些移動節點組成，這些節點通過它們之間的無線鏈路直接相連或是通過一系列中間節點的多跳鏈路相連。網絡的建立無須預先建立起來的基礎設施和中心控制節點的集中控制。Ad?hoc網絡具有的一些特殊性質需要特殊的算法和協議的支持，其特點包括動態拓撲、多跳通信、有限的資源(包括帶寬資源、CPU、電池能量資源)和有限的安全保證。這些特點使路由協議和算法的設計變得極具挑戰性。已經存在的路由協議可以被分為三種類型：先驗式、被動式和它們的混合方式。先驗式在每一個節點中需要保存網絡拓撲的全局信息，所以當需要時一條路由可以被很快的加入，這樣的協議具有很高的協議開銷和很低的升級開銷；被動的路由協議具有按需路由建立的特點，只有當需要時每一個主機才計算它到特定目的節點的路由，不影響到活動路由的拓撲變化不會引發路由維護機制的運行，所以通信開銷比起先驗式路由協議要少。第三種路由方式是混合式的，在某些節點中保存部分拓撲信息，路由選擇可由先驗的決定或運用被動的方式。我們發現在這些類型的路由協議中沒有一種可以避免泛洪這種通信方式。先驗式協議依靠泛洪來發布拓撲更新消息，被動式協議依靠它來進行路由發現。泛洪帶來一系列的廣播風暴問題，廣播風暴即指泛洪引起的過多的消息冗余、競爭和碰撞。這些帶來高協議開銷和對正在進行的通信造成干擾的后果。而另一方面，泛洪是一種非常不可靠的通信方式，這意味著在沒有碰撞的情況下并不是所有主機都能夠接受到廣播消息。在文獻“Enhancing?ad?hoc?routing?with?dynamicvirtual?infrastructures”中就指出中等稀疏圖中我們所能期待接收到廣播消息的節點個數僅僅占80％。在被動式協議中，由于泛洪的不可靠會影響最短路徑的選擇，或是找不到任何本來應該存在的路徑；在先驗式協議中會造成全局信息陳舊從而影響路由更新的正確性。

近幾年，在Ad?hoc網絡中建立類似于有線網絡中的骨干網絡的虛擬骨干結構的方法不斷提出。運行在這種虛擬骨干結構上的先驗式路由協議在這些虛擬的網絡中心節點中存儲路由信息，用于更新、修復路由，來管理控制全局網絡。部分被動式路由協議依靠虛擬骨干結構來代替路由發現中的全網泛洪機制，以此提高網絡的可靠性(碰撞的減少)和有效性(廣播次數的減少)。而Ad?hoc網的資源希缺的特征使得這些衡量網絡性能的指標的重要性顯得更為突出，提高這些指標的途徑就是減少虛擬骨干結構中的節點數目，由此找到一種在ad?hoc網中有效的建立虛擬骨干結構的方法是解決問題的關鍵。目前，已經提出了幾種在Ad?hoc網絡中建立連通控制集(CDS)的算法，其中較為典型的是文獻“Distributed?Construction?of?Connected?Dominating?Set?in?Wireless?AdHoc?Networks”公開的一種分布式連通控制集的構建方法。文獻中將在ad?hoc網絡中建立虛擬骨干結構的問題等價為單元圖中的連通控制集問題，從而在給定的節點集中尋找最小連通控制集(MCDS)。

發明內容

本發明要解決的技術問題是針對現有技術中存在的不足，提供一種用基于MCDS(最小連通控制集)算法的組播樹的構建方法，是對已有組播樹的優化重建。其中MCDS近似算法的分布式構建連通控制集(CDS)的方法分為兩步：①基于已建立好的組播樹找到一個最大獨立集(MIS)；②找到一些節點來連接所有的MIS節點，最終得到的黑節點集即近似MCDS。

本發明一種基于MCDS近似算法的最小化資源消耗的組播路由方法通過下述技術方案予以實現：本發明所述方法包括如下步驟：

1)構造MIS

在組播樹T上，樹中節點的級別(level)為該節點距離樹根的跳數；樹根的級別為0；我們定義節點的rank為二元組(level，id)；

IF?level_v＞level_u?THEN?rank_v＞rank_u，OR

IF?level_v＝level_u?AND?ID_v＞ID_u?THEN?rank_v＞rank_u