基于蚁群算法的Qos技术在网络教学中的应用分析

王新 刘永山 朱代春

摘要：随着Internet技术的发展，网络化教学也逐渐进入我们的视野。依托网络化教学平台，具有实时、同步、异地、交互的特点也越来越受到大家的欢迎。针对在教学过程中出现的问题，利用蚁群算法的Qos（Quality of Service）技术解决在视频播放、视频下载、交互沟通等过程中出现的延时、延时抖动、丢包率问题，寻求各个节点之间的合理优化的路径，满足客户要求，提高服务质量。通过计算机仿真解决TSP（Travelling Salesman Problem）问题，在大量实验结果中，分析找到满足约束条件下，从路由源节点到目标节点之间的最优路径。

关键词：蚁群算法；Qos；计算机仿真；网络教学

中图分类号：TP391 文献标识码：A 文章编号：1009-3044（2018）32-0051-03

Abstract： With the development of Internet technology， network teaching has gradually come into our vision. relying on the network teaching platform， has the characteristics of real-time， synchronization， remote， interactive， more and more popular. Aiming at the problems in the teaching process， the Quality of Service （Qos） technology is used to solve the problems such as delay， delay-jitter and packet-loss rate in the process of video playing， video download， interactive communication and so on. Travelling Salesman Problem （TSP） problem is solved by computer simulation. In a large number of experimental results， the optimal path is found to meet the constraints， from which the routing source node to the target node.

Key words： ant colony algorithm；Qos； computer simulation；network teaching

网络教学[1]是从美国推出的“网络日”活动而来，主要目的是争取在2000年，教室和图书馆都可以连接internet，使公众可以得到技术文化教育的权利。目前为止，已形成一个覆盖全国教育机构的网络，将近100多所大学将利用Internet开展远程教育，大约70%的高等院校提供网络教育。英国推出“全国学习网计划” 目标是2002年所有小学全部可以上网学习。同时制订了网络教育计划和相关的实施细则。远程教育将主要依赖Internet，不仅基础教育，专业培训也可以在网络上实现。国内的网络教学首先清华、北邮、湖南大学、浙大四所大学开始，到2015年为止，已有90多所大学有权进行学历教学，实现60个网络教学平台，尤其最近几年发展迅速，可以看出网络教学正被公众认可接受。但是在网络教学中也出现了各种问题，我们主要从网络技术方面分析，提出通过Qos（Quality of Service）技术找到一条有足够资源的可行路径，提高网络的利用率，实现可用资源的优化。目前的路由采用FCFS协议，它不能满足多媒体的数据传输。研究人员提出了群智能蚁群算法[2]，人工鱼群算法[3]，智能水滴算法[4]等解决组合优化问题，蚁群算法通过信息素更新规则解决了求解速度慢、收敛和停滞问题。人工鱼群算法不需要特殊信息，收敛速度比较快，适合解决实时性问题。智能水滴算法应用还不广泛，主要用于TSP和无人机航迹方面。Qos路由分：单播、组播、广播、选播四种，我们主要研究改进的蚁群算法在Qos网络路由中的应用，并与基本的蚁群算法，人工鱼群算法，智能水滴算法做比较。本文提到的数学模型以及网络图都是基于单播的理论基础

1 Qos网络路由模型的建立

网络路由主要是基于数据为中心的路由和基于搜索查询的路由[5]，我们主要讨论数据为中心的路由问题。通常情况是一个节点感应到数据后，需要向一个或几个汇聚节点传输，这种数据定向的扩散过程可以通过蚁群算法模拟。

下面我们给出网络模型[G=（V，E）]，[V]是所有节点的集合，[E]是所有节点间通信链路的集合，我们的目的是找到一条从源点[S∈V]到目标节点[M∈V]的最优有效路径，并且要满足约束条件（如带宽、时延、时延抖动、丢包率）。蚁群算法有两种数据传输，一种是实时数据称后蚂蚁（Backward Ants）负责传输数据；一种是非实时数据称前蚂蚁（Forward Ants），负责寻路。在某个节点接收到数据后会产生[K]个前蚂蚁向相邻节点移动，它移动到下一个节点的概率。

但是蚁群算法在运算过程中有几个问题需要解决。

1.1 初始条件下节点寻路问题

初始条件下节点寻路的选择概率大体相同，导致前蚂蚁寻路時间较长。我们采用基于已知位置的蚁群Qos路由算法来解决初始化问题，从而提高蚁群的收敛速度。

1.2 初始条件下蚂蚁数量问题

针对蚁群算法中初始条件下前蚂蚁数量较少的，导致前期算法收敛性、稳定性和寻路质量不理想的问题，我们采用提高局部信息素挥发速度[4]的办法，将公式3做如下修改。

其中[Di]表示第i只蚂蚁找到的路径时延，如不满足Qos约束条件则不更新，反之加强。ANTNUM是前蚂蚁数量，[Emin]是最小剩余能量节点的剩余能量，[E]是初始能量。将前蚂蚁的数量引入到信息素挥发因子中，目的是通过信息素挥发速度提高算法的收敛性，引入剩余能量概念到信息素挥发因子中，可以有效均衡能量消耗。

1.3 当链路出现拥塞时，采用拥塞规避原则

拥塞规避[6]首先要计算数据队列的平均长度。并且根据上限、下限的阀值来预判拥塞状态，如果将要发生拥塞，预判到的节点马上向所有经过该拥塞链路的目标节点发送拥塞信息，经过此路径的蚂蚁重新寻求一条路径以绕过该节点，同时更新节点和链路信息，以确保存在一条非拥塞路径。从而实现流量的分散，缓解拥塞状态。当拥塞节点恢复状态，再将路由切回原状态。

1.4 信息素更新规则的调整

信息素在蚁群算法的非常重要，蚂蚁在循环搜索过程中，在经过路径上留下的信息量的大小是寻求全局最优解的关键。针对基本蚁群算法收敛速度慢，容易进入局部最优的问题，修改了信息素更新规则。

公式[Q']是常数，[Lk]是路径长度，[minlength]是最短的路径长度，R是参数。修改的目的是针对不同质量的解，它的信息素增量是不同的，优解的信息素增量较大，加快收敛速度，从而降低算法的花费。

1.5 负载均衡的Qos路由

目前，Qos路由算法主要是预计算和在线计算[7]。预计算根据已有的路由表，在请求到达时快速找到可行路径，缺点路由表较大，可扩展性不强。在线计算是请求到达时根据网络状态计算可行路径，缺点延迟较高，路由器负载较大。负载均衡的Qos路由，目的就是在满足服务质量的前提下，提高网络使用率。我们给出一个既考虑路径的质量还能兼顾网络使用率的评估参数。

2 计算机仿真与结果分析

计算机仿真实验采用文献[8]中使用的网络拓扑结构。

运行结果如表1所示，它们在相同的网络结构和约束条件下，都能找到最优路径，解决复杂的组合优化问题。但是从算法的运行时间和寻找最优路径的成功率来看改进的蚁群算法运行时间更短，成功率更高，路径也合理，能够有效地节省网络资源。主要原因是改进初始条件下前蚂蚁数量和寻址概率相同的问题，提高了蚁群算法在前期的收敛速度，同时规避了图2中基本蚁群算法在节点8和节点15出现拥塞现象，而改进的蚁群算法负载更均衡，使用网络资源更合理。

3 结论

改进的蚁群算法有效的解决网络路由问题，有很强的寻路能力，负载更均衡，避免了拥塞状态。解决了网络教学中视频闪断，传输中断，因带宽、时延导致的丢包率问题。将本文中讨论的网络技术应用到网络教学中，可以充分发挥教学和网络资源结合的优势，提高公众学习能力。因本文主要针对Qos单播情况下的研究，同时也为其它播放方式的研究提供了一定的基础。

参考文献：

[1] 寇媛媛.网络教学平台的发展现状及趋势[J].电子信息工程，2011（8）：123-125.

[2] 胡琼琼.群智能优化算法在Qos网络路由优化中的应用[D].陕西师范大学，2010：35-40.

[3] 魏星，李志远，陈艳.基于蚁群和鱼群的混合优化光网络动态RWA算法[J].光通信技术，2015（3）：17-19.

[4] 赵莉，丁海军.智能水滴算法求解TSP问题的研究[J].云南民族大学学报，2015.24（1）：62-65.

[5] 胡琼琼.群智能优化算法在Qos网络路由优化中的应用[D].陕西师范大学，2010，5：35-40.

[6] 万博，卢昱.基于改进的蚁群算法的拥塞规避Qos路由算法[J].计算机工程，2011，37（20）.

[7] 柯宗武.无线多媒体传感器网络QoS路由算法研究[D].武漢理工大学，2009：52-54.

[8] 古明家，宣士斌.基于自适应变异蚁群算法的Qos路由算法[J].计算机工程，2009，35（23）：209-211.

【通联编辑：王力】