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

An Upper Bound of the Throughput for Multi-Radio Wireless Mesh Networks

黃淑盈(Shu-Ying Huang)

指導教授 ： 簡榮宏

國立交通大學/資訊學院/網路工程研究所/碩士(2009年)

https://doi.org/10.6842/NCTU.2009.01017

摘要

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

關鍵字

無線網狀網路 ； 最大流量

並列摘要

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.

並列關鍵字

Wireless Mesh Network ； Maximum Flow

參考文獻

[1] I.F. Akyildiz, X. Wang, and W. Wang, “Wireless mesh networks: a survey,” Elsevier Computer Networks, vol. 47, pp. 445-487, March 2005.

[2] S. Avallone and I. F. Akylildiz, “A channel assignment algorithm for multi-radio wireless mesh networks,” Computer Communications, vol. 31, pp. 1343-1353, May 2008.

[3] S. Avallone, I.F. Akyildiz and G. Ventre, “A Channel and Rate Assignment Algorithm and a Layer-2.5 Forwarding Paradigm for Multi-Radio Wireless Mesh Networks,” IEEE/ACM Transactions on Networking, vol. 17, pp. 267-280, Feb. 2009.

[4] A. Raniwala, K. Gopalan, and T.C. Chiueh, “Centralized Channel Assignment and Routing Algorithms for Multi-Channel Wireless Mesh Networks,” ACM SIGMOBILE Mobile Computing and Communications Review, vol. 8, pp. 50–65, April 2004.

[5] M. Kodialam, T. Nandagopal, “Characterizing the capacity region in multi-radio multi-channel wireless mesh networks,” Proceedings of the 11th annual international conference on Mobile computing and networking, pp. 73–87, 2005.