移動Ａｄ ｈｏｃ網(wǎng)絡中兩種構(gòu)造最小連通支配集算法分析

[摘要] 移動自組網(wǎng)中節(jié)點移動是網(wǎng)絡快速變化的主要原因?？焖僮兓木W(wǎng)絡拓撲給移動自組網(wǎng)，尤其是路由設計帶來了巨大挑戰(zhàn)?；谧钚∵B通支配集算法是一種有效的分層路由算法，它將路由搜索集中在連通支配集內(nèi)。詳細分析了兩種具有代表性的連通支配集算法，分別指出它們的不足之處，并進行了初步驗證。

[關(guān)鍵詞] 移動自組網(wǎng) 支配集 網(wǎng)關(guān)節(jié)點

一、引言

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

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

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

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

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

圖1 單向ad hoc網(wǎng)絡的連通支配集圖2 權(quán)值改變的連通支配集

對于相同的網(wǎng)絡結(jié)構(gòu)，即節(jié)點個數(shù)及邊的方向信息保持不變，但每個節(jié)點的權(quán)值信息改變，利用UL-WMCDS算法卻得到相同的支配集，即每個節(jié)點的權(quán)值對連通支配集的構(gòu)造并沒有太大的影響。

如圖2，節(jié)點4的權(quán)值變?yōu)?2，節(jié)點6的權(quán)值變?yōu)?5，仍然得到連通網(wǎng)關(guān)集D={3，4，5，6}。只不過這時簇的結(jié)構(gòu)發(fā)生改變，權(quán)值較小的節(jié)點4、6充當了網(wǎng)關(guān)節(jié)點，以節(jié)點4、6為骨干節(jié)點的簇分別只有4、6兩個節(jié)點。

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

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

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

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

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

四、結(jié)論

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

參考文獻：

[1]閻新芳:基于極大權(quán)的最小連通支配集啟發(fā)式算法[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網(wǎng)絡的連通支配集算法[J].傳感技術(shù)學報，2006，19（3）：905-907

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