近年來，在多頻率的存取中無線網格網路變成一個新興技術。對於無線網格網路的效能路由、頻道配置與排程都是重要的設計問題。然而，大多數的研究著重在協議干擾模型(protocol interference model)下的問題。在這篇研究中，我們提出一個在實體干擾模型(physical interference model)下，多頻道多頻率的無線網格網路中同時考慮路由與頻道配置來最大化整個網路產能的演算法。這是一個集中式的演算法，分成兩個階段，分別是路由階段與頻道配置階段。在路由階段中，我們提出一個有效率地找出路由路徑的K條最短路徑負載平衡演算法(K-shortest paths load-balancing algorithm)。在頻道配置階段中，我們使用裝箱問題(bin-packing problem)的基本概念來配置頻道，並且發展一個經驗法則的最先遞減配置頻道配置演算法(heuristic first fit decreasing channel assignment)用來最大化整個網路產能。我們利用電腦模擬方式來驗證所提出的演算法，結果顯示我們所提出的演算法在無線網格網路的環境下具有良好的效能。

In recent years, wireless mesh networks become an emerging technology for broadband wireless access. Routing, channel assignment and scheduling are important design issues for performance of wireless mesh networks. However, most previous researches address these issues under the protocol interference model. In this research, we propose an algorithm to maximize overall network throughput under physical interference model in multi-channel multi-radio wireless mesh networks, which considers routing and channel assignment jointly. The proposed algorithm is a centralized algorithm and it consists of routing phase and channel assignment phase. In the routing phase, we present K-shortest paths load-balancing algorithm to search the routing paths efficiently. In the channel assignment phase, we use the basic concept of the well-known bin-packing problem to assign channels, and develop a heuristic first fit decreasing channel assignment (FFDCA) algorithm to maximize the overall network throughput. To evaluate the performance of the proposed algorithms, we perform computer simulation in the ns-2 simulator. The results of computer simulation reveal that the proposed scheme has excellent overall performance in wireless mesh networks.

[1]P. Gupta and P. R. Kumar. The Capacity of Wireless Networks. IEEE Transactions on Information Theory, volume 46, pages 388-404, March 2000.
[2]G. Brar, D. Blough and P. Santi. Computationally efficient scheduling with the physical interference model for throughput improvement in wireless mesh networks. In Proc. Twelfth ACM Annual International Conference on Mobile Computing and Networking (MOBICOM), pages 2-13, Los Angeles, CA, US, Sept. 2006.
[3]A. Raniwala and T. Chiueh. Architecture and Algorithms for an IEEE 802.11-based multi-channel wireless mesh network. In Proc. IEEE INFOCOM, volume 3, pages 2223- 2234, March 2005.
[4]A. Raniwala, K. Gopalan and T. Chiueh. Centralized channel assignment and routing algorithms for multi-channel wireless mesh networks. ACM Mobile Computing and Communications Review (MC2R), volume 8, pages 50–65, April 2004.
[5]M. Kodialam and T. Nandagopal. Characterizing the capacity region in multi-radio and multi-channel mesh networks. In Proc. Eleventh ACM Annual International Conference on Mobile Computing and Networking (MOBICOM), pages 73-87, Cologne, Germany, 2005.
[6]The network simulator NS-2, http://www.isi.edu/nsnam/ns/index.html.
[7]A new one for hyacinth for NS-2.29, http://my.opera.com/HenryFD/blog/show.dml/270422