一個用於無線網路中找出最小權重獨立控制集的多項式時間近似方案

Abstract

在無線網路中，每一個節點的能力不一定相同，例如，電池的剩餘電量不一定相同，訊息傳遞所需的花費不一定相同，因此，一個常見的方式是利用點權重圖（也就是將無線網路所對應的圖的點加上權重）來描述網路的拓樸結構。一個點權重圖的最小權重獨立控制集，指的是一組既是獨立集也是控制集的最小權重點集合。在本論文中，我們針對具有多項式成長有界性質的點權重圖提出一個計算最小權重獨立控制集的多項式時間近似方案；具有多項式成長有界性質的圖包含了 著名的單位圓盤圖、單位圓球圖、和類單位圓盤圖。就我們所知，我們的多項式時間近似方案是第一個針對無線網路中最小權重獨立控制集問題的多項式時間近似方案。此外，當所有點的權重都一樣時，我們的多項式時間近似方案會是一個在具有多項式成長有界性質的圖中計算獨立控制集的多項式時間近似方案；值得一提的是：我們的多項式時間近似方案只需要一個階段，因此簡化了Hurink和Nieberg在文獻[15]中所提出需要兩個階段的多項式時間近似方案。

Due to different capabilities of nodes (for example, different remaining battery lives or different costs for transmitting a message) in a wireless network, it is desirable to model the underlying network topology by a node-weighted graph. A minimum-weighted independent dominating set of a node-weighted graph is a vertex subset with the minimum weight being both independent and dominating. In this thesis, we present a polynomial-time approximation scheme (PTAS) for computing a minimum-weighted independent dominating set in a node-weighted polynomially growth bounded graph, which is in a class of graphs that include the well-known unit disk graphs, unit ball graphs, and quasi unit disk graphs. To the best of our knowledge, our PTAS is the ?first PTAS for the minimum-weighted independent dominating set problem in wireless networks. Furthermore, when all the weights are identical, our PTAS turns out to be a simple 1-stage PTAS for computing an independent dominating set in a polynomially growth bounded graph and hence simplifies the 2-stage PTAS proposed by Hurink and Nieberg in [15].