近年來，無線網格網路變成一個新興技術。對於無線網格網路的效能、頻道配置與排程都是重要的設計問題。然而，大多數的研究著重在協議干擾模型(protocol interference model)下的問題。在本研究中，我們提出一個在實體干擾模型(physical interference model)下，多頻道多頻率的無線網格網路中考慮頻道配置與排程來最大化整個網路產能的演算法。這是一個集中式的演算法，我們使用拉格蘭氏鬆弛法(Lagrangian Relaxation)之演算法以簡化問題的限制並求解，並且發展一個經驗法則的符合限制演算法(feasible solution algorithm)調整被簡化的問題答案為符合原本限制的解。另外我們將蟻群演算法(Ant Colony Optimization)應用在頻道配置與頻道排程問題上，以另一種方式找尋所要的解。我們利用電腦模擬方式來驗證所提出的演算法，結果顯示我們所提出的演算法在無線網格網路的環境下可以有效找到近似最佳的頻道配置與排程。

In recent years, wireless mesh networks become emerging technologies for broadband wireless access. 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 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. We formulate the joint channel assignment and scheduling problem as an integer programming problem and use the Lagrangian relaxation and the subgradient approaches to develop Lagrangian heuristic. In addition, an ant colony optimization algorithm is presented for the joint channel assignment and scheduling problem. The results of computer simulations reveal that the proposed schemes can provide near-optimal solutions.

[1] P. Gupta and P. R. Kumar, “The Capacity of Wireless Networks,” IEEE Transactions on Information Theory, volume 46, pp. 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), Los Angeles, CA, US, Sept. 2006, pp. 2-13.
[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, March 2005, pp. 2223-2234.
[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, pp. 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), Cologne, Germany, 2005, pp. 73-87.
[6] J. Gronkvist, “Assignment Methods for Spatial Reuse TDMA,” In Proc. of the 1st ACM international symposium on Mobile ad hoc networking & computing, Boston, Massachusetts, November 20 2000, pp. 119-124.
[7] R. Bjorklund, P. Varbrand, and D. Yuan, “Resource Optimization of Spatial TDMA in Ad-Hoc Radio Networks: A column generation approach,” in Proc. of IEEE InfoCOM, vol.2, 2003, pp. 818-824.
[8] S. Ramanathan and E. L. Lloyd, “Scheduling Algorithms for Multihop Radio Networks,” IEEE/ACM Transactions on Networking, Vol.1, No.2, pp. 166-177, April 1993.
[9] S. Avallone and Ian F. Akylildiz, “A channel assignment algorithm for multi-radio wireless mesh networks,” Computer Communications, pp. 1343-1353, 26 January 2008.
[10] M. L. Fisher, “The Lagrangian Relaxation Method for Solving Integer Programming Problems,” Management Science Vol. 27, No. 1, pp. 1861-1871, U.S.A, January 1981.
[11] E. Kalvelagen, “Lagrangian Relaxation With Gams,” [online], Available: http://www.gams.com/, 20 December 2002.

[12] S.S.Sankar, S.G.Ponnambalam, V.Rathinavel and M.S.Visveshvaren, “Scheduling in Parallel Machine Shop: An Ant Colony Optimization Approach,” In Proc. of IEEE International Conference on Industrial Technology (ICIT 2005), 2005, pp. 276-280.
[13] M. Dorigo, V. Maniezzo and A. Colorni, "Ant System: Optimization by a Colony of Cooperating Agents," IEEE Transactions on Systems, Man, and Cybernetics–Part B, pp. 29-41, February 1996.
[14] G.Wang, W.Gong, B.DeRenzi and R.Kastner, “Ant Colony Optimizations for Resource and Timing Constrained Operation Scheduling,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Vol. 26, No. 6, pp.1010-1029, June 2007.