無(wú)線(xiàn)網(wǎng)絡(luò)中弱連通控制集構(gòu)造算法研究.pdf

1、近些年來(lái),無(wú)線(xiàn)網(wǎng)絡(luò)的應(yīng)用范圍越來(lái)越廣。而普通無(wú)線(xiàn)網(wǎng)絡(luò)如Ad-hoc網(wǎng)等都是無(wú)基礎(chǔ)設(shè)施通信網(wǎng)絡(luò),它們的這個(gè)特性使它有別于有線(xiàn)基礎(chǔ)設(shè)施網(wǎng)。有線(xiàn)網(wǎng)絡(luò)不受能源供應(yīng)限制,但在普通的無(wú)線(xiàn)網(wǎng)絡(luò)中節(jié)點(diǎn)的能量問(wèn)題是首要考慮的。所以在普通無(wú)線(xiàn)網(wǎng)絡(luò)中建立一個(gè)專(zhuān)門(mén)的骨干網(wǎng)來(lái)負(fù)責(zé)路由通信等功能,對(duì)只依靠電池供電的無(wú)線(xiàn)設(shè)備和無(wú)線(xiàn)網(wǎng)絡(luò)的發(fā)展來(lái)說(shuō)已經(jīng)變得十分重要。
　　 控制集(DS)已經(jīng)廣泛應(yīng)用于無(wú)線(xiàn)網(wǎng)絡(luò)的活動(dòng)節(jié)點(diǎn)集的選取以建立無(wú)線(xiàn)網(wǎng)絡(luò)中的虛擬骨干網(wǎng)絡(luò)。節(jié)點(diǎn)

2、之間都不連通的DS是個(gè)獨(dú)立集,為了使DS成為能擔(dān)當(dāng)無(wú)線(xiàn)網(wǎng)絡(luò)中拓?fù)淇刂?、搜索、廣播信息、節(jié)點(diǎn)覆蓋等多種任務(wù)的虛擬骨干網(wǎng),許多學(xué)者對(duì)應(yīng)用連通控制集(CDS)作為無(wú)線(xiàn)網(wǎng)絡(luò)虛擬骨干網(wǎng)的方法進(jìn)行了大量的研究。但是在構(gòu)造CDS的時(shí)候必須選取大量的連通節(jié)點(diǎn),以保證DS的連通性,整個(gè)網(wǎng)絡(luò)的活動(dòng)節(jié)點(diǎn)會(huì)因此而增加,網(wǎng)絡(luò)中能耗也相應(yīng)的增多。于是通過(guò)放松對(duì)DS連通性的要求以減少DS中節(jié)點(diǎn)的數(shù)量,弱連通控制集(WCDS)作為無(wú)線(xiàn)網(wǎng)絡(luò)的虛擬骨干網(wǎng)的方法被提出。

3、r>　　 本文在前人研究結(jié)果的基礎(chǔ)上,從集中式算法和分布式算法兩個(gè)方面出發(fā),提出了兩種在無(wú)線(xiàn)網(wǎng)絡(luò)中構(gòu)造WCDS的方法。在集中式算法方面,我們通過(guò)構(gòu)造邊控制集的方法來(lái)求解無(wú)線(xiàn)網(wǎng)絡(luò)中的WCDS,該算法的時(shí)間復(fù)雜度為O(|N|+|E|);同時(shí)在保證WCDS的控制性和弱連通性不變的情況下,給出了兩種修剪策略,以減小所求WCDS的規(guī)模。在分布式算法方面,本文又提出了一種基于時(shí)間競(jìng)爭(zhēng)機(jī)制的無(wú)線(xiàn)網(wǎng)絡(luò)WCDS構(gòu)造策略:本算法無(wú)需全局根節(jié)點(diǎn)的控制,通過(guò)