文 献 综 述 一、 概述 无线电频谱资源有限，为了防止不同通信之间产生的干扰并且有效利用无线电频谱资源，人们不得不对无线电通信进行管理：将一定频率一定时间内的频谱划分为一系列互不相交的无线信道，并将这些信道分配给不同的通信链路进行使用，以使得提高频谱资源利用率的同时降低相邻信道的干扰。

信道的划分方法有频分 (frequency division, FD)，时分 (time division, TD)，码分 (code division, CD)等，分配策略一般分为固定信道分配策略（Fixed Channel Allocation schemes, FCA schemes）,动态信道分配策略（Dynamic Channel Allocation schemes， DCA schemes）, 混合式信道分配策略（Hybrid Channel Allocation schemes， HCA）三类[1]，取决于信道分配在何时发生。

其中静态分配策略一经规划，网络信道分配不再变更，优点是实现简单，资源成本小，缺点是难以应对网络中的变化；动态分配策略通常有集中式与分布式，其中分布式通常由多agents系统实现，优点是能够应对网络情况的变化，缺点是实现复杂，且耗时较多；混合策略在以上两种策略优缺点中进行折中。

在只考虑相同信道干扰的情况下，信道分配问题等价于标准的图着色问题[2], [3], 这是一个NP-hard问题[4], [5]，难以在实际应用规模下求得精确解，同时信道分配问题事实上是一个有额外约束条件的图着色问题, 其常见的约束条件为： 1.信道干扰[6]： 同信道干扰（Co-Channel Interference ,CCI）， 相邻信道干扰(Adjacent Channel Interference , ACI) 同站干扰(Co-Site interference ,CCI) 2.带宽约束[7] 3.能量约束[8] 这些约束条件事实上在某种程度限制了解空间，一方面使得可行解更容易获得较优解，但同时也使得可行解更难以获得。

在实际应用中通过MAC协议的设计允许部分冲突的存在，人们针对该问题提出了很多近似算法，以期获得计算时间与解的好坏权衡的较满意的解[6]，这些方法包括图论算法[3], [9#8211;11]，基于博弈论的方法[12#8211;16]，禁忌搜索[17], [18]，模拟退火[19]，神经网络[20], [21]，遗传算法(经典遗传算法，混合遗传算法，岛屿遗传算法，遗传编程/超启发算法)[7], [8], [19], [22#8211;32]等。

随着网络技术的高速发展，无线设备覆盖率|、密度都呈现高速上升的趋势，无线服务的容量，所需带宽也越来越大，同时无线传感器由于硬件的限制，电量和计算能力都构成了约束，这些都使得无线传感器网络环境下的信道分配问题更加复杂，同时也使得信道分配的优化更具有意义。

二、 信道分配问题的演化求解 进化算法求解固定信道分配 进化算法是一种带有方向性的随机搜索算法，其将优化问题的解表示为一个群体中的个体，个体间通过信息传递（交叉算子，更好的解的信息更容易扩散到整个群体，解的好坏表示为适应度，适应度越高的个体越容易产生子代个体），随机改变部分解（变异算子）来实现带有方向性的搜索的同时又不缺乏探索能力，是一种通用型的最优化方法。

文献中对于经典遗传算法在求解固定信道分配问题中的改进主要在以下几个方面： 1. 适应度函数计算优化，降低算法运行时间，提高解对于多个约束条件的满足性 2. 改进解编码的设计，以增加求解路径中对于约束条件的满足性 3. 交叉算子的设计，改进算法的收敛性 4. 并行化，提高算法运行速度 5. 混合搜索算法设计，通过混合其他优化算法，改善遗传算法解的质量 遗传编程/超启发算法求解动态/混合信道分配策略 [30]利用遗传算法将信道分配策略本身表示为树结构进行优化，称为超启发算法，其实际上是遗传编程的一个特例，该文中从若干信道分配的启发式策略中提取出若干操作作为原子操作，通过遗传算法通过事先生成好的若干组数据集（如通信需求）来优化由原子操作构成的程序树，以期获得更好的启发式分配策略。

该方法有助于发现目前尚未发明的新的可用于该问题的启发算法。

三、 参考文献 [1] I. Katzel and M. Naghshineh, ”Channel Assignment Schemes for Cellular Mobile Telecommunication Systems: A Comprehensive Survery,” Personal Communications, IEEE, vol. 3, pp. 10#8211;31, 1996. [2] D. H. Smith, S. M. Allen, D. Maths, M. G. Cf, S. Hurley, W. J. Watkins, and P. O. Box, ”Frequency Assignment#8239;: Methods and Algorithms,” no. October, 1998. [3] J. van den Heuvel, R. a. Leese, and M. a. Shepherd, ”Graph labeling and radio channel assignment,” Journal of Graph Theory, vol. 29, no. 4, pp. 263#8211;283, Dec. 1998. [4] A. Gamst, ”Some lower bounds for a class of frequency assignment problems,” Vehicular Technology, IEEE Transactions on, vol. 35, no. 1, pp. 8#8211;14, 1986. [5] A. Mathematics, ”The NP-Completeness of Edge-Colouring,” vol. 10, no. 4, pp. 718#8211;720, 1981. [6] M. P. Mishra and P. C. Saxena, ”Survey of Channel Allocation Algorithms Research for Cellular Systems,” International Journal of Networks and Communications, vol. 2, no. 5, pp. 75#8211;104, Dec. 2012. [7] E. Park, Y. Kim, and B. Moon, ”Genetic search for fixed channel assignment problem with limited bandwidth,” Proceedings of the Genetic and #8230;, 2002. [8] S. Paper, M. Y. Elnainay, D. H. Friend, A. B. Mackenzie, and V. Tech, ”Channel Allocation Power Control for Dynamic Spectrum Cognitive Networks using a Localized Island Genetic Algorithm,” pp. 1#8211;5, 2008. [9] A. Mishra, S. Banerjee, and W. Arbaugh, ”Weighted coloring based channel assignment for WLANs,” ACM SIGMOBILE Mobile Computing and Communications Review, vol. 9, no. 3, p. 19, Jul. 2005. [10] C. McDiarmid and B. Reed, ”Channel assignment and weighted coloring,” Networks, vol. 36, no. 2, pp. 114#8211;117, Sep. 2000. [11] S. O. Krumke and S. S. Ravi, ”Models and Approximation Algorithms for Channel Assignment in Radio Networks,” vol. 0, pp. 1#8211;11, 2000. [12] I. J. Wassell, ”Application of game theory for distributed dynamic channel allocation,” Vehicular Technology Conference. IEEE 55th Vehicular Technology Conference. VTC Spring 2002 (Cat. No.02CH37367), vol. 1, pp. 404#8211;408, 2002. [13] J. Sun, E. Modiano, and L. Zheng, ”Wireless channel allocation using an auction algorithm,” Selected Areas in Communications, IEEE Journal on, vol. 24, no. 5, pp. 1085#8211;1096, 2006. [14] Q. Yu, J. Chen, Y. Fan, and X. S. Shen, ”Multi-Channel Assignment in Wireless Sensor Networks#8239;: A Game Theoretic Approach Multi-Channel Assignment in Wireless Sensor Networks#8239;: A Game Theoretic Approach,” no. November 2009, pp. 0#8211;21, 2010. [15] L. Gao and X. Wang, ”A game approach for multi-channel allocation in multi-hop wireless networks,” Proceedings of the 9th ACM international symposium on Mobile ad hoc networking and computing - MobiHoc #8217;08, p. 303, 2008. [16] J. Sun, E. Modiano, S. Member, and L. Zheng, ”Using an Auction Algorithm,” vol. 24, no. 5, pp. 1085#8211;1096, 2006. [17] F. F. Problem, R. Montemanni, J. N. J. Moon, and D. H. Smith, ”An Improved Tabu Search Algorithm for the,” vol. 52, no. 3, pp. 891#8211;901, 2003. [18] a. Capone and M. Trubian, ”Channel assignment problem in cellular systems: a new model and a tabu search algorithm,” IEEE Transactions on Vehicular Technology, vol. 48, no. 4, pp. 1252#8211;1260, Jul. 1999. [19] J. Chen, D. Seah, and W. Xu, ”Channel allocation for cellular networks using heuristic methods,” unpublished report, vol. 0, no. 1, pp. 1#8211;8, 1999. [20] D. Kunz, ”Channel assignment for cellular radio using neural networks,” Vehicular Technology, IEEE Transactions on, 1991. [21] J. Kim and S. Park, ”Cellular radio channel assignment using a modified Hopfield network,” #8230; , IEEE Transactions on, pp. 1#8211;27, 1997. [22] N. Karaoglu and B. Manderick, ”FAPSTER-a genetic algorithm for frequency assignment problem,” Proc. of the 2005 Genetic and Evolutionary #8230;, 2005. [23] J.-S. Kim, S. Park, P. Dowd, and N. Nasrabadi, ”Channel assignment in cellular radio using genetic algorithms,” Wireless Personal Communications, vol. 3, no. 3, pp. 273#8211;286, 1996. [24] M. Ryan, J. Debuse, G. Smith, and I. Whittley, ”A hybrid genetic algorithm for the fixed channel assignment problem,” GECCO#8217;99, 1999. [25] T. Lau and E. Tsang, ”Guided genetic algorithm and its application to radio link frequency assignment problems,” Constraints, 2001. [26] C. Y. Ngo and V. O. K. Li, ”Fixed channel assignment in cellular radio networks using a modified genetic algorithm,” IEEE Transactions on Vehicular Technology, vol. 47, no. 1, pp. 163#8211;172, 1998. [27] L. Wang, S. Arunkumaar, and W. Gu, ”Genetic algorithms for optimal channel assignment in mobile communications,” Neural Information Processing, #8230;, pp. 1#8211;33, 2002. [28] G. Vidyarthi, A. Ngom, and I. Stojmenovic, ”an Efficient Evolutionary Strategy in Wireless Mobile Networks,” vol. 54, no. 5, pp. 1887#8211;1895, 2005. [29] H. G. Sandalidis, S. Member, P. P. Stavroulakis, and J. Rodriguez-tellez, ”An Efficient Evolutionary Algorithm for Channel Resource Management in Cellular Mobile Systems,” vol. 2, no. 4, pp. 125#8211;137, 1998. [30] G. Kendall and M. Mohamad, ”Channel assignment optimisation using a hyper-heuristic,” Cybernetics and Intelligent Systems,IEEE Conference on, vol. 2, pp. 791#8211;796, 2004. [31] F. Luna and C. Est#233;banez, ”Optimization algorithms for large-scale real-world instances of the frequency assignment problem,” Soft Computing-A #8230;, pp. 1#8211;16, 2011. [32] F. Comellas and J. Oz, ”Graph Coloring Algorithms for Assignment Problems in Radio Networks,” vol. 56, pp. 49#8211;56, 1995.