移動Ａｄ ｈｏｃ網絡中兩種構造最小連通支配集算法分析

[摘要] 移動自組網中節點移動是網絡快速變化的主要原因。快速變化的網絡拓撲給移動自組網，尤其是路由設計帶來了巨大挑戰。基于最小連通支配集算法是一種有效的分層路由算法，它將路由搜索集中在連通支配集內。詳細分析了兩種具有代表性的連通支配集算法，分別指出它們的不足之處，并進行了初步驗證。

[關鍵詞] 移動自組網 支配集 網關節點

一、引言

移動自組織網絡（簡稱Ad Hoc網絡或MANET）旨在建立一個可以即時展開、隨意通信并對網絡拓撲結構變化迅速做出反應的數據網絡[1]。這給路由設計帶來很大的難度。

最近提出的基于最小連通支配集(Minimum Connected Dominating Set， MCDS)的路由方法是一個很好的分層路由方法，它將路由過程簡化到一個由MCDS生成的較小的子網中。MCDS中的網關節點構成了高一級的虛擬骨干網，而每個網關節點在自己的簇中都起著控制中心的作用，用于路由分組和廣播路由信息。明顯地，這種方法的有效性很大程度上依賴于發現和維持一個MCDS及與之相應的子網的大小。不幸的是，對大部分圖來說，求一個MCDS的問題屬NP-C問題[2]，在實際應用中需要設計近似求解算法。目前已有的算法主要分兩類，集中式算法和分布式算法。集中式算法要求每個節點具有整個網絡的拓撲結構信息，因而不適合移動網絡多變的特點，可伸縮性差；分布式算法的主要思想是通過節點之間的局部交互操作在網絡中迅速構造一個虛擬骨干網(CDS)。

有關連通支配集的算法，國內外已經有許多人從事這一方向的研究。文獻[2 ]提出了一種適用于單向ad hoc 網絡的連通支配集算法(以后稱作UL－WMCDS算法)，它將主機的功率大小或在線時間的長短作為每個節點的權值，這種基于極大權的CDS的選擇確保了大部分合適的節點擔任網關節點的角色，使其能更好的協調管理網絡中所有其他節點，從而能保持CDS的相對穩固性。

二、UL-WMCDS算法分析[3]

文獻[3]指出由上述算法得到的網關節點集D是圖G的一個連通支配集。接著以一個圖例如圖1，來說明上述算法的執行過程，得到連通網關集D={3，4，5，6}。

圖1 單向ad hoc網絡的連通支配集圖2 權值改變的連通支配集

對于相同的網絡結構，即節點個數及邊的方向信息保持不變，但每個節點的權值信息改變，利用UL-WMCDS算法卻得到相同的支配集，即每個節點的權值對連通支配集的構造并沒有太大的影響。

如圖2，節點4的權值變為12，節點6的權值變為15，仍然得到連通網關集D={3，4，5，6}。只不過這時簇的結構發生改變，權值較小的節點4、6充當了網關節點，以節點4、6為骨干節點的簇分別只有4、6兩個節點。

三、PLA-CDS算法分析[4]

該算法是一種基于隊列選擇的移動自組網中電力及負荷感知的構造最小連通支配集算法。算法中將節點根據電力情況和負荷分為9個級別，并從隨機節點開始進行廣度優先的搜索或深度優先搜索，并通過對搜索結果執行精簡規則使得得到的結果是對應MANET的最小連通支配集。文獻[3]中綜合考慮了節點電力和負荷情況，能夠獲得最小連通支配集，但也略有不足，主要表現在：

1.該算法是一種非分布式的支配集構造算法，即需要一控制中心來存儲網絡中節點的電力及負荷信息，而不是通過節點的交互操作來構造CDS；

2.節點電力和負荷情況對支配節點搜索過程并沒有重要影響。如圖4，算法從節點1開始搜索，得到的連通支配集D＝{1，2，3，4，6，7}，實施精簡規則后，得到的最小連通支配集＝{3，4，7}，與圖3所得的最小連通支配集相同。

圖3 MANET的最小連通支配集圖4 不同搜索起點的連通支配集

四、結論

MANET是一個嶄新的研究領域，它的網絡特性――自組性、多跳性、節點的隨即移動性、分布式控制等給MANET路由問題研究帶來了極大的挑戰。詳細分析了兩種具有代表性的連通支配集算法：UL-WMCDS算法和PLA-CDS算法，分別指出它們的不足之處，并進行了初步驗證。

參考文獻：

[1]閻新芳:基于極大權的最小連通支配集啟發式算法[J].電子學報，2004，32(11):1774-1777

[2]Graey M L， Johnson D S. Computers and Intractability: A Guide to the Theory of NP-Completeness [M]. San Francisico: W H Free man.1979

[3]吳小艷聶欣:一種適用于單向ad hoc網絡的連通支配集算法[J].傳感技術學報，2006，19（3）：905-907

[4]朱藝華沈毅俊吳小艷:移動自組網電力及負荷感知的構造最小連通支配集算法[J].電子學報，2006，34(11）:2004-2007