论文部分内容阅读
随着互联网的普及,越来越多的多媒体信息通过互联网传播,IPTV (Internet Protocol Television)直播服务就是其中一类。IPTV直播服务具有较高的服务质量(Quality of Service, QoS)需求。IP组播是一种有效的方式,但是IP组播的有限可用性驱使研究人员在应用层实现组播。在应用层组播中,组成员之间组织成一棵逻辑树,数据沿着逻辑树通过单播被传输至目的节点。应用层组播实现的IPTV直播服务能够被建模成为度约束的最小直径树问题(minimum diameter, degree-bounded spanning tree, MDDBST),该问题已经被证明为NP-C问题。应用层组播是一种P2P (Peer to Peer)形式。应用层节点没有底层物理网络的拓扑结构等信息,因而可能选择“远距离”的点建立连接,这将给物理网络带来许多不必要的流量。所以在应用层组播实现的IPTV直播服务中,应用层流量优化问题(application-layer traffic optimization, ALTO)应该被考虑,则IPTV直播服务变成结合ALTO问题的MDDBST问题。本文提出一个拓扑感知的基于生长森林的蚁群优化算法,该算法是一种格网优先的方式。首先我们将基于地理位置的Delaunay三角划分和基于RTT(Round-Trip-Time)的Binning策略相结合建立覆盖网络,地理位置和RTT都能够被用来评估底层物理网络,因为该覆盖网络是拓扑感知的；然后在该覆盖网络上利用基于生长森林的蚁群优化算法(Ant Colony Optimization algorithm based on Forest growth, ACOF)建立度约束的最小直径树。在ACOF中,蚂蚁之间通过信息素进行交流,蚂蚁的行为形成森林。初始时森林为空,蚂蚁的每一步通过探测信息素的浓度选择覆盖网络中的一条边,使森林生长。蚂蚁的最终目的是森林变成一颗包含所有组成员节点的树。在所有的蚂蚁建完树后,根据当前的局部最优树和全局最优树更新信息素。以上步骤被反复执行直到算法收敛。唯一遵循的原理是蚁群优化算法的正反馈机制。一系列仿真实验的结果展示了本文中的覆盖网络比随机网络和仅用Delaunay三角划分的覆盖网络有更好的拓扑接近性,ACOF算法比CT (Compact Tree)算法能够产生更少的流量和更短的时延直径。