一個用於無線網路中找出受限制的連通控制集的多項式時間近似演算法

Abstract

在無線網路中，選出一些點來當做虛擬骨幹已經被探討超過二十年了。之前的許多研究都是在單位圓盤圖上，在這種模型中，所有的點的傳輸半徑都是相同的，而且兩點是相連的若且唯若這兩點的距離不超過一。先前的研究顯示連通控制集能夠當作虛擬骨幹來使用，在這方面已有許多的研究成果。在這篇論文中，我們提出了一個新的想法：有限制條件的連通控制集。這種連通控制集的特點就是：某些點基於特殊的理由，必須一定要在連通控制集中。例如，這些點的剩餘能源較多、或是落在比較重要的位置上。我們提出了一個適用於所有無線網路O(n)時間的演算法來建造有限制條件的連通控制集，這裡的n表示無線網路中的節點數。我們所提出的演算法的訊息複雜度是O(n)，當無線網路是單位圓盤圖時，效益是8•(最小連通控制集的大小)+3•k，其中k是有限制條件的點數。

In wireless ad hoc networks, selecting a set of nodes to form a virtual backbone has been investigated for more than two decades. It has been shown that a connected dominating set (CDS) can be used as a virtual backbone. There are many results for finding CDSs. In this thesis, we propose a new idea: a constrained connected dominating set (CCDS), which is a CDS having the property that some specified nodes must be included in it due to some special reason. For example, the specified nodes could be nodes with more remaining energy or nodes located at important locations. We propose a polynomial-time algorithm for constructing a CCDS; our algorithm works for all wireless networks and the message complexity of it is linear. When the given wireless network is a Unit Disk Graph, the performance ratio of our algorithm is 8|MCDS| + 3k, where |MCDS| is the size of a minimum connected dominating set (MCDS) and k is the number of constrained nodes.