國立高雄大學圖資館 |

語系: 繁體中文

說明(常見問題)

圖資館首頁

登入

回首頁

切換: 標籤 | MARC模式 | ISBD

產生最小多支配集合的分散式自我穩定演算法 = Self-Stabiliz...

國立高雄大學資訊工程學系碩士班

產生最小多支配集合的分散式自我穩定演算法 = Self-Stabilizing Distributed Formation of Minimal Multi-Dominating Set

紀錄類型:	書目-語言資料,印刷品 : 單行本
並列題名:	Self-Stabilizing Distributed Formation of Minimal Multi-Dominating Set
作者:	陳宗隆,
其他團體作者:	國立高雄大學
出版地:	[高雄市]
出版者:	撰者;
出版年:	2013[民102]
面頁冊數:	77面圖,表 : 30公分;
標題:	最小多支配集合
標題:	Minimal Multi-Dominating Sets
電子資源:	http://handle.ncl.edu.tw/11296/ndltd/50922996673620786472
附註:	104年10月31日公開
附註:	參考書目：面65-68
摘要註:	在分散式系統中，有時候為了確立伺服器(servers)和客戶端(clients)之間的角色，我們會從網路中挑選出某些節點扮演伺服器(servers)的角色，負責提供某些服務(service)給鄰近的其他客戶(client)節點。如果我們希望在不影響client被server服務的程度下找出最小的伺服器節點集合，此問題變成支配集合(dominating set)問題，即由支配集合內的節點負責扮演伺服器的角色，來提供服務給鄰近的非支配集合節點。所謂支配集合是指從網路中的部份節點集合，這些節點稱為支配點(dominator)，滿足每一個非支配點(dominatee或non-dominator)至少鄰近一個支配點。為了增加整體網路的可靠度，學者進一步考慮k-支配集合問題(k-domination set problem)。此問題要求每一個非支配點其鄰近至少要有k個支配者存在，而k為一個大於等於1的整數。k-支配集合問題可進一步延伸為多支配集合問題(multi-domination set problem)，此問題要求每個節點i (可為支配點或非支配點)至少鄰近ki個支配者，而每個節點的ki可相異。當一個支配集合不存在子集合亦為滿足要求的支配集合，則此支配集合稱為最小支配集合。本篇論文提出了一個自我穩定的分散式演算法，在集中式的執行模型下可找出最小多支配集合。我們證明了此演算法的正確性，並且在多個具代表性的網路拓樸邏輯下，探討此演算法的效能並與前人的方法作比較。模擬實驗結果顯示與先前的方法相較之下，這個新的方法能夠找到較小的支配集合，故有助於某些分散式系統的應用。 In certain applications of distributed systems, some nodes are designated among others that play the roles of servers which provide desired service to other client nodes. If we want to find a set of nodes that cover all other nodes not in the set, the problem becomes identifying a dominating set. Formally, every node not in a dominating set should be adjacent to at least one node in the set. To increase the durability of service, researchers further consider k-dominating set problem, where every node not in a k-dominating set should be adjacent to at least k nodes in the set, where k >= 1 is an integer. This problem can be further extended to multi-dominating set problem, where the domination requirement k for every node can be different. A multi-dominating set is minimal if it does not contain any proper subset that is also a valid multi-dominating set. This thesis proposes a self-stabilizing distributed algorithm that finds a minimal dominating set under a central daemon. The correctness of this algorithm has been proven. We study the performance of the proposed algorithm and compare it with those of existing approaches under several representative topologies. Simulation results show that the proposed approach generally find a smaller set when compared with prior methods.

產生最小多支配集合的分散式自我穩定演算法 = Self-Stabilizing Distributed Formation of Minimal Multi-Dominating Set
陳, 宗隆

產生最小多支配集合的分散式自我穩定演算法 = Self-Stabilizing Distributed Formation of Minimal Multi-Dominating Set / 陳宗隆撰 - [高雄市] : 撰者, 2013[民102]. - 77面 ; 圖,表 ; 30公分.
104年10月31日公開參考書目：面65-68.
最小多支配集合Minimal Multi-Dominating Sets

產生最小多支配集合的分散式自我穩定演算法 = Self-Stabilizing Distributed Formation of Minimal Multi-Dominating Set
LDR:04272nam0a2200289 450 001 389684
005 20170214095523.0
009 389684
010 0 $b 精裝
010 0 $b 平裝
100 $a 20170214y2013 k y0chiy50 e
101 1 $a chi $d chi $d eng
102 $a tw
105 $a ak am 000yy
200 1 $a 產生最小多支配集合的分散式自我穩定演算法 $d Self-Stabilizing Distributed Formation of Minimal Multi-Dominating Set $z eng $f 陳宗隆撰
210 $a [高雄市] $c 撰者 $d 2013[民102]
215 0 $a 77面 $c 圖,表 $d 30公分
300 $a 104年10月31日公開
300 $a 參考書目：面65-68
314 $a 指導教授：嚴力行博士
328 $a 碩士論文--國立高雄大學資訊工程學系碩士班
330 $a 在分散式系統中，有時候為了確立伺服器(servers)和客戶端(clients)之間的角色，我們會從網路中挑選出某些節點扮演伺服器(servers)的角色，負責提供某些服務(service)給鄰近的其他客戶(client)節點。如果我們希望在不影響client被server服務的程度下找出最小的伺服器節點集合，此問題變成支配集合(dominating set)問題，即由支配集合內的節點負責扮演伺服器的角色，來提供服務給鄰近的非支配集合節點。所謂支配集合是指從網路中的部份節點集合，這些節點稱為支配點(dominator)，滿足每一個非支配點(dominatee或non-dominator)至少鄰近一個支配點。為了增加整體網路的可靠度，學者進一步考慮k-支配集合問題(k-domination set problem)。此問題要求每一個非支配點其鄰近至少要有k個支配者存在，而k為一個大於等於1的整數。k-支配集合問題可進一步延伸為多支配集合問題(multi-domination set problem)，此問題要求每個節點i (可為支配點或非支配點)至少鄰近ki個支配者，而每個節點的ki可相異。當一個支配集合不存在子集合亦為滿足要求的支配集合，則此支配集合稱為最小支配集合。本篇論文提出了一個自我穩定的分散式演算法，在集中式的執行模型下可找出最小多支配集合。我們證明了此演算法的正確性，並且在多個具代表性的網路拓樸邏輯下，探討此演算法的效能並與前人的方法作比較。模擬實驗結果顯示與先前的方法相較之下，這個新的方法能夠找到較小的支配集合，故有助於某些分散式系統的應用。 In certain applications of distributed systems, some nodes are designated among others that play the roles of servers which provide desired service to other client nodes. If we want to find a set of nodes that cover all other nodes not in the set, the problem becomes identifying a dominating set. Formally, every node not in a dominating set should be adjacent to at least one node in the set. To increase the durability of service, researchers further consider k-dominating set problem, where every node not in a k-dominating set should be adjacent to at least k nodes in the set, where k >= 1 is an integer. This problem can be further extended to multi-dominating set problem, where the domination requirement k for every node can be different. A multi-dominating set is minimal if it does not contain any proper subset that is also a valid multi-dominating set. This thesis proposes a self-stabilizing distributed algorithm that finds a minimal dominating set under a central daemon. The correctness of this algorithm has been proven. We study the performance of the proposed algorithm and compare it with those of existing approaches under several representative topologies. Simulation results show that the proposed approach generally find a smaller set when compared with prior methods.
510 1 $a Self-Stabilizing Distributed Formation of Minimal Multi-Dominating Set $z eng
610 0 $a 最小多支配集合 $a 最小k-支配集合 $a 最小支配集合 $a 自我穩定演算法 $a 賽局理論
610 1 $a Minimal Multi-Dominating Sets $a Minimal k-Dominating Sets $a Minimal Dominating Sets $a Self-Stabilizing Algorithms $a Game Theory
681 $a 008M/0019 $b 464103 7537 $v 2007年版
700 1 $a 陳 $b 宗隆 $4 撰 $3 614544
712 0 2 $a 國立高雄大學 $b 資訊工程學系碩士班 $3 353878
801 0 $a tw $b 國立高雄大學 $c 20151023 $g CCR
856 7 $z 電子資源 $2 http $u http://handle.ncl.edu.tw/11296/ndltd/50922996673620786472