近年來，無線網格網路變成一個新興技術。對於無線網格網路的效能、頻道配置與排程都是重要的設計問題。在無線網格網路下，因為CSMA/CA的機制花費太多的負擔不再符合需求，取而代之的是spatial TDMA的機制。Spatial TDMA機制在無線網格網路下能使系統效能有所提升，因此我們採用spatial TDMA的機制當作我們的研究範疇。再者，過去大部分的研究注重在協議干擾模型(protocol interference model)下的議題。但是在許多的研究中能夠發現實體干擾模型(physical interference model)在正確性的表現上是遠比干擾模型(protocol interference model)來的高。實體干擾模型(physical interference model)能夠正確的模擬相互干擾的關係並且藉此關係有效的增加空間的重覆使用。在本研究中，我們提出集中式的方案來對付實體干擾模型下(physical interference model)，多頻道多頻率的無線網格網路中頻道分配跟排程的問題。我們先將此問題公式化並且使用混合進化演算法來解此問題。此外，我們利用圖形著色演算法另外發展出一個能在常數時間內對付頻道分配跟排程問題的啟發式演算法。結果顯示我們所提出的演算法在無線網格網路的環境下可以有效找到近似最佳的頻道配置與排程。

In recent years, wireless mesh networks become an emerging technology for broadband wireless access. Channel assignment and scheduling are important design issues for performance of wireless mesh networks. In wireless mesh networks, CSMA/CA mechanism incurs high overheads. The spatial TDMA mechanism can increase system performance and throughput. Therefore we use the spatial TDMA mechanism as our research aspect. Moreover, most previous researches address the issue under the protocol interference model. However, the physical interference model can provide the precise the interference relations and increase the spatial reuse in TDMA scheduling. In this research, we propose centralized schemes to address the problem of joint channel assignment and scheduling under the physical interference model for multi-channel multi-radio wireless mesh networks. First, we formulate the joint channel assignment and scheduling problem and use the hybrid evolutionary algorithm to solve the problem. In addition, we propose a new heuristic based on the popular graph coloring algorithm to solve the joint the channel assignment and scheduling problem. The results of computer simulations reveal that the proposed schemes can provide a near-optimal solution.

[1]Patrik Bjorklund, Peter Varbrand and Di Yuan. “Resource Optimization of Spatial TDMA in Ad Hoc Radio Networks: A Column Generation Approach,” IEEE INFOCOM’03, vol. 2, pages: 818 – 824, March 2003.
[2]Jian Tang, Guoliang Xue, Chandler, C. and Weiyi Zhang. “Link scheduling with power control for throughput enhancement in multi-hop wireless networks,” IEEE Trans. Commun., vol. 55, pages: 733 – 742, May 2006.
[3] 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, Sept. 2006.
[4]A. Raniwala and T. Chiueh, “Architecture and Algorithms for an IEEE 802.11-based multi-channel wireless mesh network,” In Proc. IEEE INFOCOM, vol. 3, pages: 2223 – 2234, March 2005.
[5]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), vol. 8, pages: 50 - 65, April 2004.
[6]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, 2005.
[7]Daniel Brlaz cole Polytechnique Fdrale de Lausanne, Lausanne, SwitzerlanC. “New Methods to Color the Vertices of a Graph,” Communication of ACM, vol. 22, pages: 251 – 256, April 1979.
[8]Galinier P., Hao J-K., “Hybrid Evolutionary Algorithm for Graph Coloring,” Journal of Combinatorial Optimization, vol. 3, pages: 379 – 397, December 1999.
[9]Ephremides, A. Truong, T.V., “Scheduling broadcasts in multi-hop radio networks,” IEEE Trans. Commun., vol. 38, pages: 456 – 460, April 1990.
[10]Jihui Zhang, Haitao Wuz, Qian Zhangz, Bo Li, “Joint Routing and Scheduling in Multi-radio Multi-channel Multi-hop Wireless Networks,” Broadband Networks, 2005 2nd International Conference on, vol. 1, pages: 631 – 640, Oct 2005.
[11]Albert Y. Zomaya, Chris Ward, and Ben Macey.“Genetic Scheduling for Parallel Processor Systems: Comparative Studies and Performance Issues,” IEEE Transactions on Parallel and Distributed Systems, vol. 10, pages: 795-812, Aug 1999.
[12]Giuseppe Bianchi.“Performance Analysis of the IEEE 802.11 Distributed Coordination Function,” Selected Areas in Communications, IEEE Journal on, vol. 18, Pages: 535 – 547, March 2000.
[13]Jingpu Shi, Theodoros Salonidis, and Edward W. Knightly.“Starvation mitigation through multi-channel coordination in CSMA multi-hop wireless networks,” ACM MobiHoc'06, pages: 214 - 225 , May 2006.
[14]Weizhao Wang, Yu Wang, XiangYang Li, WenZhan Song, Ophir Frieder. “Efficient Interference-Aware TDMA Link Scheduling for Static Wireless Networks,” Mobile Computing and Networking, pages: 262 - 273 , 2006.
[15]S. Ramanathan, Errol L. Lloyd.“Scheduling algorithms for multi-hop radio networks,” Networking, IEEE/ACM Transactions on, vol. 22, pages: 211 - 222 ,October 1992.
[16] J. Gronkvist. “Traffic controlled spatial reuse tdma in multi-hop radio networks,” Personal, Indoor and Mobile Radio Communications. The Ninth IEEE International Symposium on , vol. 1, pages: 1203 – 1207, Sept. 1998.
[17]P. Gupta and P. R. Kumar, “The Capacity of Wireless Networks,” Information Theory, IEEE Transactions on, volume 46, pages: 388-404, March 2000.
[18] Kassotakis, I.E., Markaki, M.E. and Vasilakos, A.V. “A hybrid genetic approach for channel reuse in multiple accesstelecommunication networks,” Selected Areas in Communications, IEEE Journal on, volume 18, pages: 234-243, Feb. 2000.
[19] Topcuoglu, H.R., Demiroz, B. and Kandemir, M. “Solving the Register Allocation Problem for Embedded Systems Using a Hybrid Evolutionary Algorithm,” Evolutionary Computation, IEEE Transactions on, volume: 11, pages: 620-634, Oct. 2007.