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

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

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

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

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

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

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

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

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

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