無(wú)線網(wǎng)絡(luò)中若干NP-難問(wèn)題的參數(shù)算法.pdf

1、隨著無(wú)線網(wǎng)絡(luò)設(shè)計(jì)的日趨復(fù)雜化，無(wú)線網(wǎng)絡(luò)應(yīng)用中不斷出現(xiàn)具有非常高復(fù)雜性的NP-難問(wèn)題。作為求解NP-難問(wèn)題的一種新思路，參數(shù)計(jì)算方法受到了人們的廣泛關(guān)注，并被成功應(yīng)用到諸多領(lǐng)域難解問(wèn)題的求解中。
　　本文以無(wú)線網(wǎng)絡(luò)中的最小能量組播路由、連通支配集、最大生命周期目標(biāo)覆蓋和完全p-支配集等NP-難問(wèn)題為研究對(duì)象，在深入挖掘問(wèn)題的參數(shù)特性基礎(chǔ)上，運(yùn)用參數(shù)計(jì)算理論和技術(shù)對(duì)它們進(jìn)行參數(shù)化建模、多變量參數(shù)復(fù)雜性分析和參數(shù)算法設(shè)計(jì)與實(shí)現(xiàn)。主要研究

2、工作包括:
　　對(duì)最小能量組播路由進(jìn)行了參數(shù)化分析、參數(shù)算法設(shè)計(jì)與實(shí)現(xiàn)。單源組播是實(shí)現(xiàn)從某個(gè)源節(jié)點(diǎn)到指定目標(biāo)節(jié)點(diǎn)進(jìn)行通信的高效機(jī)制。而小規(guī)模組播（目標(biāo)節(jié)點(diǎn)個(gè)數(shù)較少）在無(wú)線網(wǎng)絡(luò)中具有重要應(yīng)用。無(wú)線節(jié)點(diǎn)由電池供電，而限制網(wǎng)絡(luò)延時(shí)是網(wǎng)絡(luò)QoS的一個(gè)關(guān)鍵因素，因此設(shè)計(jì)能量有效且延時(shí)受限的組播至關(guān)重要。首先研究最小能量單源h-組播，即找到一顆能量代價(jià)最小的組播樹(shù)，要求在組播樹(shù)中從源節(jié)點(diǎn)到任一個(gè)目標(biāo)節(jié)點(diǎn)均存在一條長(zhǎng)度不超過(guò)h的路徑。將最小能量

3、單源辦-組播轉(zhuǎn)化為一個(gè)圖優(yōu)化問(wèn)題，然后基于動(dòng)態(tài)規(guī)劃技術(shù)，提出一個(gè)時(shí)間為O(3k·(n+m)·h+2k·（n+m）2·h）的精確算法DBMM，其中k為目標(biāo)節(jié)點(diǎn)個(gè)數(shù)，n和m分別為實(shí)例中頂點(diǎn)和邊的數(shù)目。實(shí)驗(yàn)表明，與現(xiàn)有啟發(fā)式或近似算法相比，算法DBMM可以節(jié)省的能量消耗在19％到42％之間，且在小規(guī)模組播場(chǎng)景下展現(xiàn)了較好的時(shí)間性能。在單源組播研究的基礎(chǔ)上，進(jìn)一步研究了多源組播和強(qiáng)連通組播。多源組播存在多個(gè)源節(jié)點(diǎn)，要求實(shí)現(xiàn)任一源節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的

4、通信，而強(qiáng)連通組播要求一組節(jié)點(diǎn)中任意一個(gè)節(jié)點(diǎn)均能實(shí)現(xiàn)到組中其它節(jié)點(diǎn)的通信。利用參數(shù)化規(guī)約，證明最小能量強(qiáng)連通h-組播以“目標(biāo)節(jié)點(diǎn)個(gè)數(shù)k”和“轉(zhuǎn)發(fā)節(jié)點(diǎn)個(gè)數(shù)k2”作為雙參數(shù)是W[1]-難的，而最小能量多源h-組播以k2為參數(shù)是W[2]-難的。最后利用多項(xiàng)式時(shí)間參數(shù)化轉(zhuǎn)換，證明最小能量單源h-組播問(wèn)題以（k,k2）作為雙參數(shù)不存在多項(xiàng)式核。
　　針對(duì)平面圖上連通支配集設(shè)計(jì)了降低問(wèn)題規(guī)模的核心化算法。連通支配集被用于構(gòu)建無(wú)線網(wǎng)絡(luò)中的虛擬骨

5、干網(wǎng)，從而為網(wǎng)絡(luò)中的廣播和路由等操作提供一個(gè)有效的通信基礎(chǔ)。首先通過(guò)對(duì)給定實(shí)例中頂點(diǎn)進(jìn)行著色，挖掘出圖中頂點(diǎn)之間的新的組合特性，進(jìn)而提出一系列高效的多項(xiàng)式時(shí)間局部簡(jiǎn)化規(guī)則。接著對(duì)區(qū)域分解技術(shù)進(jìn)行擴(kuò)展，將規(guī)約圖進(jìn)行區(qū)域數(shù)目不超過(guò)3k-6的極大區(qū)域分解（k為問(wèn)題解的大小），并將圖中區(qū)域按區(qū)域端點(diǎn)間的最短距離分成兩類(lèi):端點(diǎn)間的距離為1的區(qū)域、端點(diǎn)間的距離大于1的區(qū)域。通過(guò)充分利用問(wèn)題解的連通特性，證明了后一種類(lèi)型的區(qū)域的個(gè)數(shù)不超過(guò)2k-5。結(jié)

6、合著色規(guī)約規(guī)則與平面圖的性質(zhì)，證明了這兩種區(qū)域中頂點(diǎn)個(gè)數(shù)的上界分別是23和41。最后利用問(wèn)題解的連通特點(diǎn)及著色規(guī)則，證明位于區(qū)域以外的頂點(diǎn)個(gè)數(shù)也是有界的，從而得出一個(gè)大小為130k的線性核，這是當(dāng)前的最好結(jié)果。
　　研究了最大生命周期目標(biāo)覆蓋問(wèn)題的參數(shù)復(fù)雜性及參數(shù)算法設(shè)計(jì)。最大生命周期目標(biāo)覆蓋的主要任務(wù)是將傳感節(jié)點(diǎn)分組，并給每個(gè)組分配時(shí)間片，使得在滿(mǎn)足覆蓋需求的同時(shí)最大化網(wǎng)絡(luò)生命周期。為了深入理解問(wèn)題難解性根源，對(duì)兩類(lèi)目標(biāo)覆蓋問(wèn)題

7、進(jìn)行系統(tǒng)的參數(shù)復(fù)雜性分析:最大-最小目標(biāo)覆蓋和最大-個(gè)體目標(biāo)覆蓋。最大-最小目標(biāo)覆蓋要求每個(gè)組至少覆蓋k2個(gè)目標(biāo)節(jié)點(diǎn)，而最大-個(gè)體目標(biāo)覆蓋要求每個(gè)目標(biāo)節(jié)點(diǎn)至少被k3個(gè)組覆蓋。首先證明了最大-最小目標(biāo)覆蓋和最大-個(gè)體目標(biāo)覆蓋在以下特殊情況下仍是NP-難的:每個(gè)目標(biāo)節(jié)點(diǎn)至多被兩個(gè)傳感節(jié)點(diǎn)覆蓋，或者每個(gè)傳感節(jié)點(diǎn)至多可以覆蓋兩個(gè)目標(biāo)節(jié)點(diǎn)。因此，限制傳感節(jié)點(diǎn)的“度”或目標(biāo)節(jié)點(diǎn)的“度”不會(huì)降低問(wèn)題的難度。相反，限制目標(biāo)節(jié)點(diǎn)的個(gè)數(shù)可以降低這兩個(gè)問(wèn)題的

8、復(fù)雜性。也就是，最大-最小目標(biāo)覆蓋和最大-個(gè)體目標(biāo)覆蓋以“目標(biāo)節(jié)點(diǎn)個(gè)數(shù)”作為參數(shù)是固定參數(shù)可解的。接著研究了結(jié)構(gòu)參數(shù)“至少覆蓋兩個(gè)目標(biāo)節(jié)點(diǎn)的傳感節(jié)點(diǎn)個(gè)數(shù)k”?；谡麛?shù)線性規(guī)劃技術(shù)，證明了最大-最小目標(biāo)覆蓋和最大-個(gè)體目標(biāo)覆蓋關(guān)于參數(shù)k均是固定參數(shù)可解的。最后，利用圖著色技術(shù)，針對(duì)最大-最小目標(biāo)覆蓋提出了時(shí)間為O*((6.1k1k2)k1k2）的精確算法，其中k1表示劃分組的數(shù)目。
　　研究了完全p-支配集的參數(shù)復(fù)雜性及參數(shù)算法設(shè)計(jì)

9、。完全p-支配集被用于構(gòu)建無(wú)線節(jié)點(diǎn)的自我保護(hù)網(wǎng)絡(luò)，從而使無(wú)線節(jié)點(diǎn)能夠抵抗外部的攻擊。首先證明完全p-支配集在頂點(diǎn)最大度為3的UDG(unitdisk graph)上仍是Np-難的。為了深入理解完全p-支配集在UDG模型上的難解性根源，接著研究了完全p-支配集在UDG上的參數(shù)復(fù)雜性。利用k-團(tuán)問(wèn)題進(jìn)行參數(shù)化規(guī)約，證明完全p-支配集在UDG上是W[1]-難的，并發(fā)現(xiàn)了UDG上相交圓間的距離對(duì)問(wèn)題難度有根本性的影響。基于問(wèn)題難解性根源的分析，