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

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

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

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

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

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

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

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

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

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