國立高雄大學圖資館 |

Language: English

Back

以賽局理論設計最大獨立集合自我穩定演算法 = A Game-theore...

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

以賽局理論設計最大獨立集合自我穩定演算法 = A Game-theoretic Approach to Self-Stabilizing Maximal Independent Set Algorithm

Record Type:	Language materials, printed : monographic
Paralel Title:	A Game-theoretic Approach to Self-Stabilizing Maximal Independent Set Algorithm
Author:	黃靖軺,
Secondary Intellectual Responsibility:	國立高雄大學
Place of Publication:	[高雄市]
Published:	撰者;
Year of Publication:	2014[民103]
Description:	57面圖，表 : 30公分;
Subject:	最大獨立集合
Subject:	Maximal Independent Set
Online resource:	http://handle.ncl.edu.tw/11296/ndltd/64538152023134070245
Notes:	105年10月25日公開
Notes:	參考書目：面44-46
Summary:	圖論中的最大獨立集合(maximal independent set)問題是從一個無向圖G中的節點集合V挑選部分的節點集合S，需滿足在S當中不存在任何兩節點相鄰且S不為其它任一獨立集合的子集合。本篇論文透過賽局理論(game theory)尋求較佳的最大獨立集合問題解，並且證明最大獨立集合賽局必定會收斂至納許均衡(Nash equilibrium)。我們接著將賽局設計轉換為在分散式系統中運作的自我穩定演算法。自我穩定(self-stabilization)的性質可以保證不論系統初始狀態為何，必定會在有限的時間內到達穩定的合法狀態，即最大獨立集合。為了使我們提出的方法能在無線網路中有效的實作，需另外再對演算法進行修改以克服環境上的差異。模擬實驗結果顯示我們提出的演算法有較好的效能表現，比先前的方法有較多的最大獨立集合節點數以及較短的收斂時間。 Given an undirected graph G = (V, E), S ⊆ V is an independent set if no nodes in S are adjacent to one another. An independent set S is maximal if no proper subset of S is an independent set. Maximal independent set problem is to find such a set S. This paper proposes a solution to this problem based on game theory. We turn the solution into a self-stabilizing algorithm running in distributed systems. The self-stability property ensures that system will enter legitimate system states in limited time regardless of initial configurations. We then convert the algorithm into a protocol for wireless networks. Simulation results indicate that the proposed approach performs better than previous work in terms of independent set size and convergence time.

以賽局理論設計最大獨立集合自我穩定演算法 = A Game-theoretic Approach to Self-Stabilizing Maximal Independent Set Algorithm
黃, 靖軺

以賽局理論設計最大獨立集合自我穩定演算法 = A Game-theoretic Approach to Self-Stabilizing Maximal Independent Set Algorithm / 黃靖軺撰 - [高雄市] : 撰者, 2014[民103]. - 57面 ; 圖，表 ; 30公分.
105年10月25日公開參考書目：面44-46.
最大獨立集合Maximal Independent Set

以賽局理論設計最大獨立集合自我穩定演算法 = A Game-theoretic Approach to Self-Stabilizing Maximal Independent Set Algorithm
LDR:02893nam0 2200289 450 001 430136
005 20161117141400.0
009 etd-0701114-003426
010 0 $b 精裝
010 0 $b 平裝
100 $a 20141027d2014 k y0chiy50 e
101 1 $a chi $d chi $d eng
102 $a tw
105 $a ak am 000yy
200 1 $a 以賽局理論設計最大獨立集合自我穩定演算法 $d A Game-theoretic Approach to Self-Stabilizing Maximal Independent Set Algorithm $z eng $f 黃靖軺撰
210 $a [高雄市] $c 撰者 $d 2014[民103]
215 0 $a 57面 $c 圖，表 $d 30公分
300 $a 105年10月25日公開
300 $a 參考書目：面44-46
314 $a 指導教授：嚴力行博士
328 $a 碩士論文--國立高雄大學資訊工程學系碩士班
330 $a 圖論中的最大獨立集合(maximal independent set)問題是從一個無向圖G中的節點集合V挑選部分的節點集合S，需滿足在S當中不存在任何兩節點相鄰且S不為其它任一獨立集合的子集合。本篇論文透過賽局理論(game theory)尋求較佳的最大獨立集合問題解，並且證明最大獨立集合賽局必定會收斂至納許均衡(Nash equilibrium)。我們接著將賽局設計轉換為在分散式系統中運作的自我穩定演算法。自我穩定(self-stabilization)的性質可以保證不論系統初始狀態為何，必定會在有限的時間內到達穩定的合法狀態，即最大獨立集合。為了使我們提出的方法能在無線網路中有效的實作，需另外再對演算法進行修改以克服環境上的差異。模擬實驗結果顯示我們提出的演算法有較好的效能表現，比先前的方法有較多的最大獨立集合節點數以及較短的收斂時間。 Given an undirected graph G = (V, E), S ⊆ V is an independent set if no nodes in S are adjacent to one another. An independent set S is maximal if no proper subset of S is an independent set. Maximal independent set problem is to find such a set S. This paper proposes a solution to this problem based on game theory. We turn the solution into a self-stabilizing algorithm running in distributed systems. The self-stability property ensures that system will enter legitimate system states in limited time regardless of initial configurations. We then convert the algorithm into a protocol for wireless networks. Simulation results indicate that the proposed approach performs better than previous work in terms of independent set size and convergence time.
510 1 $a A Game-theoretic Approach to Self-Stabilizing Maximal Independent Set Algorithm $z eng
610 # 0 $a 最大獨立集合 $a 賽局理論 $a 自我穩定演算法
610 # 1 $a Maximal Independent Set $a Game Theory $a Self-Stability
681 $a 008M/0019 $b 464103 4405 $v 2007年版
700 1 $a 黃 $b 靖軺 $4 撰 $3 673360
712 0 2 $a 國立高雄大學 $b 資訊工程學系碩士班 $3 353878
801 0 $a tw $b NUK $c 20161014 $g CCR
856 7 # $u http://handle.ncl.edu.tw/11296/ndltd/64538152023134070245 $2 http $z PDF全文