以連通控制集做為無線感測網路虛擬骨幹之研究

Abstract

在無線感測網路中， 節點以及節點之間的連接關係可以用圖來表示， 如此一來，此圖的連通控制集就可以對應當成原本的無線感測網路的骨幹， 此一骨幹可用以提升訊息傳遞的效率。因此找出一個給定的圖的最小連通控制集 是許多學者們探討的問題， 文獻中已證明了找出一個給定的圖的最小連通控制集是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.