針對多重天線架構下的無線網狀網路計算其輸出上限之演算法研究

Abstract

無線網狀網路是由網狀節點以及網狀用戶端所組成。網狀節點以無線方式彼此連結形成網狀骨幹網路以提供網狀用戶端存取網際網路資訊。在本篇論文中，我們針對沒有訊號干擾的情況之下，給定每一個網狀節點的位置以及每一個網狀節點所配置的天線個數計算從網狀用戶端到網際網路入口的最大網路輸出值。我們將這個最大網路輸出值定義成該網路的輸出上限值。在本篇論文中，我們提出了一個演算法來解網路輸出上限的問題。我們的方法是將上述的問題轉換成最大流量問題。如此一來就可以透過最大流量演算法來求解，所花的計算時間椱雜度和多項式成比例。除此之外，我們利用模擬的方法，探討不同的因素包括網狀節點所放置的位置、網狀閘道節點的個數以及網狀節點所配置的天線個數對輸出上限值的影響。

A wireless mesh network consists of mesh routers and mesh clients. Mesh routers form the wireless backbone through wireless links which provides mesh clients connecting to the wired Internet. In this thesis, we consider the following problem: given a deployment of mesh routers and the number of radio interfaces of each mesh router, what is the maximum throughput from mesh clients to the wired Internet under interference-free assumption. We define the maximum throughput of the problem as an upper bound of the throughput for the given wireless mesh network. The proposed problem is transformed into a maximum flow problem and then the problem can be solved by existing maximum flow algorithms. Therefore, an upper bound of the throughput for the given wireless mesh network can be obtained in polynomial time. The simulation results show that the upper bound of the throughput is affected by the deployment of mesh routers, the number of mesh routers which serve as gateway and the number of radio interfaces of each mesh router.