基于多生成樹(shù)的MCDS構(gòu)造算法

　　無(wú)線網(wǎng)絡(luò)沒(méi)有固定基礎(chǔ)設(shè)施，節(jié)點(diǎn)之間通過(guò)洪泛方式尋找路由路徑以及傳輸數(shù)據(jù)，往往導(dǎo)致嚴(yán)重的廣播風(fēng)暴以及通信干擾問(wèn)題。為了避免上述問(wèn)題，構(gòu)造連通支配集是解決方法之一。連通支配集構(gòu)造算法在網(wǎng)絡(luò)中選擇部分節(jié)點(diǎn)并組成連通支配子網(wǎng)，利用子網(wǎng)完成數(shù)據(jù)轉(zhuǎn)發(fā)和路徑發(fā)現(xiàn)。為了最小化廣播風(fēng)暴和通信干擾，需考慮如何構(gòu)造最小節(jié)點(diǎn)數(shù)目的連通支配集，即極小連通支配集，經(jīng)證明該問(wèn)題是一個(gè)NP問(wèn)題。為解決該問(wèn)題，需要設(shè)計(jì)近似算法，并驗(yàn)證算法的性能比以及消息復(fù)雜度和時(shí)間復(fù)雜度。