臺灣博碩士論文加值系統

在無線感測網路中，
節點以及節點之間的連接關係可以用圖來表示，
如此一來，此圖的連通控制集就可以對應當成原本的無線感測網路的骨幹，
此一骨幹可用以提升訊息傳遞的效率。因此找出一個給定的圖的最小連通控制集
是許多學者們探討的問題，
文獻中已證明了找出一個給定的圖的最小連通控制集是NP-難的問題，
於是退而求其次的有近似演算法的提出。
在1999年，Wu和Li提出了一個近似演算法 (為方便，稱其為Wu和Li的演算法)，
在2006年，Cokuslu等人提出了一個近似演算法 (為方便，稱其為Cokuslu的演算法)。
Cokuslu等人的文章中只分析了演算法的效益、訊息複雜度、以及時間複雜度，
並未證明演算法的正確性。
在這篇論文中，我們將證明Cokuslu的演算法的正確性，
換句話說，我們將證明Cokuslu的演算法所得的結果是一個連通控制集。
此外，我們還做了Wu和Li的演算法及Cokuslu的演算法的比較。

In a wireless sensor network, the relationship between nodes can be modeled by us-
ing a graph. Consequently, a connected dominating set of such a graph is usually used
to serve as a virtual backbone of the original wireless sensor network. Thus finding a
minimum connected dominating set of a graph becomes a problem discussed by many
researchers. It has been proven that this problem is NP-hard. Hence many researchers
consider finding approximation solutions instead of the optimal solution and many ap-
proximation algorithms have been proposed. In particular, in 1991, Wu and Li proposed
an approximation algorithm (call it Wu and Li’s algorithm for convenience). In 2006,
Cokuslu et al. proposed another approximation algorithm (call it Cokuslu’s algorithm for
convenience), which is an improvement of Wu and Li’s algorithm. Notice that Cokuslu
et al. only provided the performance, the time complexity, and the message complexity
analyses; they did not prove the correctness of their algorithm. In this thesis, we will
prove the correctness of Cokuslu’s algorithm (i.e., we will prove that Cokuslu’s algorithm
obtains a connected dominating set. Also, we will give a comparison between Wu and
Li’s algorithm and Cokuslu’s algorithm.

1. 簡介 1
2. 相關定義 3
3. 前人結果 5
4. Wu和Li的演算法以及Cokuslu的演算法 8
4.1 Wu和Li的演算法 8
4.2 Cokuslu的演算法 8
5. 證明Cokuslu的演算法的正確性 11
5.1 證明Cokuslu的演算法之輸出為控制集 11
5.2 證明Cokuslu的演算法所輸出的控制集為連通 12
6.結語 14
參考文獻 15
附錄 17

[1] Brent N. Clark, Charles J. Colbourn, David S. Johnson,
"Unit Disk Graphs",
Discrete Mathematics,
vol. 86, 1990, pp. 165--177.

[2] Xiuzhen Cheng, Ding-Zhu Du,
"Virtual Backbone-based Routing in Ad Hoc Wireless Networks",
Technical report, Department of Computer Science and Engineering,
University of Minnesota, 2002.

[3] Xiuzhen Cheng, Xiao Huang, Deying Li, Weili Wu, Ding-Zhu Du,
"A Polynomial Time Approximation Scheme for the Minimum Connected Dominating Set
in Ad Hoc Wireless Networks",
Networks,
vol. 42, 2003, pp. 202--208.

[4] Deniz Cokuslu, Kayhan Erciyes, Orhan Dagdeviren
"A Dominating Set Based Clustering Algorithm
for Mobile Ad Hoc Networks",
in Proc. ICCS 2006,
LNCS 3991, 2006, pp. 571-578.

[5] Michael R. Garey, David S. Johnson,
"Computers and Intractability: A Guide to the Theory of NP-Completeness",
W. H. Freeman, 1978.

[6] S. Guha, S. Khuller,
"Approximation Algorithms for Connected Dominating Sets",
Algorithmica,
vol. 20, 1998, pp. 374--387.

[7] Yingshu Li, My T. Thai, Feng Wang, Chih-Wei Yi, Peng-Jun Wan, Ding-Zhu Du,
"On Greedy Construction of Connected Dominating Sets in Wireless Networks",
Wireless Communications and Mobile Computing,
vol. 5, 2005, pp. 927--932.

[8] Madhav V. Marathe, Heinz Breu, Harry B, Hunt III, S. S. Ravi, Daniel J. Rosenkrantz, "Simple Heuristics for Unit Disk Graphs",
Networks,
vol. 25, 1995, pp. 56--89.

[9] Lu Ruan, Hongwei Du, Xiaohua Jia, Weili Wu, Yingshu Li, Ker-I Ko,
"A Greedy Approximation for Minimum Connected Dominating Sets",
Theoretical Computer Science,
vol. 329, 2004, pp.325--220.

[10] Peng-Jun Wan, Khaled M. Alzoubi, Ophir Frieder,
"Distributed Construction of Connected Dominating Set in Wireless Ad Hoc Networks",
Mobile Networks and Applications,
vol 9, 2004, pp. 141--149.

[11] Douglas B. West,
"Introduction to Graph Theory 2E",
Prentice Hall, 2001.

[12] Jie Wu and Hailan Li,
"On Calculating Connected Dominating Set for Efficient Routing in
Ad Hoc Wireless Networks",
Proceedings of the 3rd International Workshop On
Discrete Algorithms and Methods for Mobile Computing and Communications,
pp. 7--14, Seattle, USA, August 1999.