Full metadata record
DC FieldValueLanguage
dc.contributor.author黃思綸en_US
dc.contributor.author陳秋媛en_US
dc.contributor.authorChen, Chiuyuanen_US
dc.date.accessioned2014-12-12T01:40:30Z-
dc.date.available2014-12-12T01:40:30Z-
dc.date.issued2009en_US
dc.identifier.urihttp://140.113.39.130/cdrfb3/record/nctu/#GT079722525en_US
dc.identifier.urihttp://hdl.handle.net/11536/45078-
dc.description.abstract在無線網路中,選出一些點來當做虛擬骨幹已經被探討超過二十年了。之前的許多研究都是在單位圓盤圖上,在這種模型中,所有的點的傳輸半徑都是相同的,而且兩點是相連的若且唯若這兩點的距離不超過一。先前的研究顯示連通控制集能夠當作虛擬骨幹來使用,在這方面已有許多的研究成果。在這篇論文中,我們提出了一個新的想法:有限制條件的連通控制集。這種連通控制集的特點就是:某些點基於特殊的理由,必須一定要在連通控制集中。例如,這些點的剩餘能源較多、或是落在比較重要的位置上。我們提出了一個適用於所有無線網路O(n)時間的演算法來建造有限制條件的連通控制集,這裡的n表示無線網路中的節點數。我們所提出的演算法的訊息複雜度是O(n),當無線網路是單位圓盤圖時,效益是8•(最小連通控制集的大小)+3•k,其中k是有限制條件的點數。zh_TW
dc.description.abstractIn 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.en_US
dc.language.isoen_USen_US
dc.subject虛擬骨幹zh_TW
dc.subject單位圓盤圖zh_TW
dc.subject連通控制集zh_TW
dc.subject有限制條件的連通控制集zh_TW
dc.subject近似演算法zh_TW
dc.subjectVirtual backboneen_US
dc.subjectUnit Disk Graphen_US
dc.subjectConnected dominating seten_US
dc.subjectConstrained connected dominating seten_US
dc.subjectApproximation algorithmen_US
dc.title一個用於無線網路中找出受限制的連通控制集的多項式時間近似演算法zh_TW
dc.titleA polynomial-time approximation algorithm for the constrained connected dominating set problem in wireless networksen_US
dc.typeThesisen_US
dc.contributor.department應用數學系所zh_TW
Appears in Collections:Thesis


Files in This Item:

  1. 252501.pdf

If it is a zip file, please download the file and unzip it, then open index.html in a browser to view the full text content.