论文部分内容阅读
网络编码技术最早于2000年由Ahlswede和李硕彦等学者提出,并证明理论上的组播速率上限是可达的。然而,编码操作必然会增加编码节点的计算量和处理时延,导致组播成本增加。另一方面,在源信息组播过程中,为了确保组播的有效性和组播用户间的公平性,端到端的时延限制和组播用户间的时延差约束成为两个非常重要的衡量指标。因此,在基于组播速率,端到端延时限制和组播目的节点间时延差约束等QoS要求的基础上,如何构建一棵编码节点数量尽可能少的网络编码组播树是一个极具现实意义的问题。本文主要针对组播网络中的编码资源优化问题进行研究,并首次综合考虑组播速率要求、端到端延时和组播用户间时延差约束等多个QoS要求；构建了针对该问题的数学优化模型,提出一种基于路由的整数编码遗传算法REGA (Routing-based Encoding Genetic Algorithm, REGA),同时本文还考虑了REGA算法的特例情况SREGA (Simple Routing-based Encoding Genetic Algorithm, SREGA)算法,该算法取消了时延约束以解决不带QoS限制的编码资源优化问题。基于路由的整数编码方式有两个显著的优点：1). REGA算法中的编码染色体长度仅取决于目的节点数目,相比于传统的基于潜在编码节点辅助链路状态的二进制编码方式,编码长度更短,算法运行过程中计算量更小；2).在染色体编码过程中,REGA算法提前考虑到组播速率的要求和端到端的时延约束限制,每一个染色体均代表一棵满足组播速率要求的组播树,并在一定程度上满足时延的限制,相比于传统的二进制编码方式,算法搜索解空间更小,更容易搜索到最优解；最后在多种拓扑情况下,本文分别对SREGA算法和REGA算法进行仿真研究。结果表明在不考虑时延约束情况下,相比于其他已发表算法,SREGA算法具有收敛速度快和全局搜索能力强的特点；另外在引入时延约束的情况下,REGA算法也明显优于已发表的算法,在解决基于组播速率要求、端到端时延和组播用户间延时差等QoS要求下的网络编码资源优化问题时具有更优的性能。