基于灰狼算法的无线网络组播路由优化*

(中国西南电子技术研究所，成都 610036)

0 引 言

组播路由问题实际上就是在给定的网络拓扑下，设定源节点和目的节点，找出包含源和目的节点的一颗组播树，并且组播树满足约束条件(如链路带宽)，使组播树的开销最短[1-2]。相关学者的大量研究已经证明了组播路由问题是一个NPC(Non-deterministic Polynomial Complete)问题，该问题通常无法直接求得最好结果[3]。在前人研究工作中，早期研究人员侧重于寻找组播树的最短路径，提出了一些基于数学的优化方法，例如Lu等人[4]提出了基于最小生成树的动态贪婪算法,通过该算法产生的多播树的性能在合理的范围之内。这些算法基本上只针对一种QoS约束，应用面较窄。国内外学者结合实际问题，常用一些元启发式算法来求解，以得到一个较优的近似解，例如遗传算法(Genetic Algorithm，GA)、粒子群算法(Particle Swarm Optimization，PSO)等。Chakraborty等人[5]采用了差分进化算法解决了无线网络中多通道情况下的最小代价组播树的构造问题。文献[6]提出一种时延敏感网络下的组播路由算法，通过预处理子图的方式降低计算复杂度，并且缩短组播路径的计算时间。文献[7]基于图论方案建模网络拓扑，提出了一种基于局部邻居信息感知的分布式组播路由算法，并通过真实示例分析验证该算法能够取得良好的性能。文献[8]以最小化多个组播树在共享链路上的组播路由时延为目标，提出了一种基于最短路径树的组播路由算法,致力于降低智能电网应用中多条组播消息同时传输的时延。文献[9]提出了一种在满足带宽约束条件下以最小化能量消耗为目标的组播路由算法，减少维护组播路径状态信息的开销，并设计休眠算法关闭未参与组播路由的节点。……