圖論在無線網路上之應用

Abstract

我們可以用圖來做為一個無線網路的模型，在此模型下，每一個無線網路中的節點對 應到圖中的一個點，若兩個無線網路中的節點彼此在對方的傳輸範圍內，則它們在圖 中所對應的點有邊相連。在過去的十年中，圖論的一些理論確實被應用在解決無線網 路的問題上，其中最有名的例子當屬「以連通的控制集做為無線網路的虛擬骨幹」，因 此，若能使得連通的控制集中的點數愈少，就能使得對應的無線網路的虛擬骨幹中的 節點數愈少，也愈能減少無線網路的維護成本。然而，細數到底有多少圖論的理論已 被應用在解決無線網路的問題上時，就會知道這部份還有非常大的努力空間。本計畫 之目的即在於探討圖論在無線網路中的應用，希望能將更多的圖論的理論應用在解決 無線網路的問題以及設計有效率的演算法之上。

We can model a wireless network N by a graph G in such a way that each node in N corresponds to a vertex in G and two vertices in G are adjacent if and only if their corresponding nodes in N are within the transmission range of each other. In the past decade, some results of graph theory have been used to solve problems that arise in wireless networks. Perhaps the most well-known example is: using a connected dominating set of G as the virtual backbone of N, where N is a given wireless network and G is its corresponding graph model. Notice that if we minimize the number of vertices in a connected dominating set of G, then we reduce the number of nodes in the virtual backbone of N and consequently reduce the cost of maintaining the virtual backbone of N. However, only few results of graph theory have been applied to solve problems that arise in wireless networks. The purpose of this project is to investigate the application of graph theory to wireless networks and we wish to use graph theory to develop efficient algorithms for wireless networks.