【作者】 孙玲玲；

【导师】 贾智平；

【作者基本信息】 山东大学 ， 计算机系统结构， 2008， 硕士

【摘要】 随着Internet和宽带网络技术的日益发展,传统的以文字和图片为主的服务已不能满足用户的需要,具有视频和音频的多媒体服务成为主流。近几年嵌入式网络数字视频监控系统正在得到广泛应用。由于嵌入式网络数字视频监控系统传输的数据量大而系统资源有限,采用点对点的传输方式会增加服务器的负担,造成网络拥塞。而组播技术可以将相同的数据从嵌入式网络视频服务器同时并行地发送到接收者,大大节省了网络带宽,减少了数据冗余,即使用户数量成倍增加,主干网络带宽也不会随之增加。同时视频监控系统对信息传送的时延和时延抖动有严格的要求,要求传输的数据必须在一定的时延限制内到达所有的接收者,并且接收者之间的延迟差别也需在一定的范围内,即满足一定服务质量(QoS)的要求。因此在嵌入式网络数字视频监控系统中我们需要解决Qos组播路由问题。该问题的目标是寻找一棵满足QoS要求的组播树,使该树覆盖所有的组成员,同时使网络费用达到最小。遗传算法是近几年提出的一种模拟生物界自然选择和遗传机制,具有高度并行,群体寻优的新型最优化搜索算法,近年来已有一些学者采用遗传算法来求解QoS组播路由问题。本文在分析现有遗传算法的基础上,提出了两种改进的遗传算法。第一个改进算法针对遗传算法运行初期易陷入早熟,运行后期收敛缓慢的问题进行了改进,采用初始群体均衡生成法和自适应变异操作可以很好地抑制早熟现象,引入排序对适应度进行拉伸,从而加快了算法的收敛速度。仿真实验结果表明改进后的遗传算法收敛速度快,性能好,可以满足系统资源有限和实时性的要求。第二种改进算法是在分析了遗传算法和蚁群算法各自优缺点的基础上,将两种算法进行融合来求解QoS组播路由问题,算法的前一阶段利用遗传算法的快速性、随机性、全局收敛性产生后一阶段蚁群算法所需要的初始信息素,加快了蚁群算法利用正反馈特性进行搜索的速度。经融合后的算法,在时间效率上优于蚁群算法,在求解效率上优于遗传算法,形成了一种时间效率和求解效率都比较好的启发式算法。本文最后针对现有视频监控系统单播传输存在的问题,将组播技术应用到网络视频监控系统中,可以有效地节省网络资源,降低时延,减少网络堵塞的几率,较好地保证了数字视频传输的实时性和服务质量。更多还原

【Abstract】 With the development of Internet and broad band technology, traditional services for word and picture can not satisfy the need of users, media services with video and audio become main stream. In recent years, embedded network digital video monitor system is widely used. Because of large data and limit system resource, unicast will enhance the burden of server and lead to congestion. But multicast can transmit the same data from embedded network video server to the receivers parallelly so that it can save broad band and reduce data redundancy. At the same time, video monitor system has the strict request for delay and delay-jitter. The transmitted data must reach all receivers in limited time, and the delay difference between receivers also needs to be in a limited range, that is to say, satisfy the demand of QoS. Therefore we need to solve QoS multicast routing question in embedded network digital video monitor system. The goal of the question is to find a multicast tree satisfying the demand of QoS that overlay all group numbers and make the cost minimum.Genetic algorithm is a new global optimal algorithm simulating evolution and widely used to solve all kinds of NP-hard problems. In recent years some scholars have used genetic algorithm to solve QoS multicast routing question. This thesis analyses exist genetic algorithms and provides two kinds of improved genetic algorithm. The first improved algorithm analyses that the standard genetic algorithm is easy to get into prematurity, and at the end of the algorithm, it runs slowly. In order to overcome the phenomenon, we adopt initial population uniform building method and self-adaptive mutation to restrain prematurity and introduce ordering to scale fitness to improve convergence speed. Simulation shows that the improved algorithm is efficient and effective, and can find the best solution quickly. It can satisfy limited resource and real-time the system requests. The second improved algorithm mixes this two algorithms based on the strength and shortcoming of genetic algorithm and ant-colony algorithm to solve QoS multicast routing question. The first phase of the mixed algorithm makes use of the quickness, random and global convergence of genetic algorithm to produce the initial pheromone that is needed by the second phase of the mixed algorithm. The mixed algorithm is better than ant-colony algorithm in time efficiency and better than genetic algorithm in solution efficiency.Because of unicast problem in the existing video monitor system, this paper applies multicast technology to network video monitor system. By this way, we can save network resource effectively, reduce delay and decrease the probability of network congests to ensure real-time and quality of service of digital video transmission.更多还原