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

[摘要] 移動(dòng)自組網(wǎng)中節(jié)點(diǎn)移動(dòng)是網(wǎng)絡(luò)快速變化的主要原因。快速變化的網(wǎng)絡(luò)拓?fù)浣o移動(dòng)自組網(wǎng)，尤其是路由設(shè)計(jì)帶來(lái)了巨大挑戰(zhàn)。基于最小連通支配集算法是一種有效的分層路由算法，它將路由搜索集中在連通支配集內(nèi)。詳細(xì)分析了兩種具有代表性的連通支配集算法，分別指出它們的不足之處，并進(jìn)行了初步驗(yàn)證。

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

一、引言

移動(dòng)自組織網(wǎng)絡(luò)（簡(jiǎn)稱(chēng)Ad Hoc網(wǎng)絡(luò)或MANET）旨在建立一個(gè)可以即時(shí)展開(kāi)、隨意通信并對(duì)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)變化迅速做出反應(yīng)的數(shù)據(jù)網(wǎng)絡(luò)[1]。這給路由設(shè)計(jì)帶來(lái)很大的難度。

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

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

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

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

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

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

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

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

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

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

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

圖3 MANET的最小連通支配集圖4 不同搜索起點(diǎn)的連通支配集

四、結(jié)論

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

參考文獻(xiàn)：

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

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