面向网络编码的组播路由优化问题研究

摘要

随着云计算、大数据等信息技术的迅猛发展，以软件定义网络、移动互联等为代表的互联网技术的演进日新月异，人们对多媒体应用的需求急剧增加。组播技术正好能较好地支撑具有实时的、高带宽的多媒体业务。而传统路由采用“存储-转发”模式传输数据，不能保证达到组播的最大吞吐量。与传统模式传输数据不同，网络编码采用“编码-转发”模式来传输数据，不仅能保证组播获得理论最大吞吐量，而且在节约能耗、提高数据安全性等方面优势显著，具有重要的理论价值和巨大的应用潜力。 然而，编码操作涉及复杂的数学运算，过多编码操作无疑会消耗大量的计算和存储资源，从而导致网络成本的增加。因此在保证组播数据速率的前提下，如何减少网络编码的操作次数来降低网络开销是一个极为重要的学术研究问题，该问题被称为网络编码资源优化问题（Network Coding Resource Minimization，NCRM）。另一方面，网络服务供应商希望最大化网络资源的利用率来节省成本，而负载均衡是衡量网络资源利用率的重要指标之一。在基于网络编码的组播通信过程中，在充分发挥网络编码优势的同时尽可能均衡网络负载，已成为网络领域的重要研究方向。该问题被称为网络编码组播负载均衡问题（Load Balancing in Network Coding Based Multicast，LBNCM）。 与传统优化算法相比，进化算法全局搜索能力强、实现简单、鲁棒性高，被广泛应用于工程实践中，尤其在解决组合优化问题和 NP-Hard 问题上优势明显，因此本文采用进化算法来解决NCRM和LBNCM问题。具体实施为以下三个方面： 1）针对静态网络环境下的NCRM 问题，本文提出一种改进型粒子群优化算法来解决。提出的贪婪初始化策略引导算法快速定位至可行解区域，采用路径重连局部搜索策略来进一步增强粒子群优化算法的局部搜索能力。实验表明，针对静态NCRM问题，本文提出的算法稳定性高、计算时间少以及能获得具有较少编码次数的组播子图。 2）研究了动态网络环境下的NCRM问题，并采用一种多智能体进化算法来解决。MAEA 中智能体之间信息的传递速度较快，当网络环境发生变化时，各个智能体间会迅速适应环境的变化。实验表明，与遗传算法、量子衍生进化算法、种群增量学习等算法相比，MAEA在网络环境变化之前能优化出较少的编码次数。 3）针对LBNCM问题，本文提出了一种改进的人工蜂群算法来解决。该算法整合了三种全新策略。引导型食物源初始化策略提供初始蜂群高蜜源量的食物源，基于蜜源库的侦查蜂选择策略用于进一步搜索高质量的解，概率分布模型搜索策略来增强种群多样性和避免早熟收敛。在12固定拓扑和12个随机生成的拓扑下的仿真实验表明，本文提出的算法能获得更小的适应度值，从而较好地均衡网络负载。

目录

第一个书签之前