在计算机网络中，用户的数据要从一个终端发送到另一个终端，首先要确定传输路由。针对不同的通信方式，其确定路由的方式也不同。目前，而组播是网络的通信的主要方式之一。蚁群算法的基本原理是模仿自然界中真实蚁群的觅食行为。自然界中蚁群能通过相互协作找到从蚁巢到食物的最短路径，并且能随着环境变化(如突然出现障碍物)而变化，很快地重新找到最短路径
一、路由算法中的组播路由算法
随着互联网技术的发展和网络应用的普及，因特网上的用户数量持续呈爆炸性增长，网上的应用由传统的电子邮件转向FTP、WWW等多媒体业务。此外，基于因特网的新应用和业务也在不断地推出，如电子商务、IP电话、视频会议等。但是，要满足这些业务的需求，特别是要保证一些实时业务的带宽、时延等特殊需求，以目前因特网的“尽力而为”的服务模式是难于完成的。“尽力而为”服务模式的特点是对所有应用提供同种数据传输服务，对网络的资源缺乏有效的分配和管理，当网络负载较轻时，各个应用得到的传输服务质量尚可，但是随着用户数目的增多，网络的负载也将增加。此时，各种应用的行为表现为无序地竞争网络资源，造成网络资源的不合理占用，各种应用各为其利，其结果是服务质量互相恶化。
目前的因特网技术急需进行改进以提供有效的资源分配与管理。上面提到的新型网络应用，如视频会议、交互式游戏、声音/视频电话、实时多媒体播放、分布式计算、视频点播和远程教学等应用的特点是涉及多个成员的交互，本质上具有组播的特征。为了支持大量存在的此类应用，组播路由技术应运而生。
组播是一端节点将同一信息传送到多个目的端节点，参与组播的多个目的端点组成了一个组播组，每个端节点称为组播组成员。随着多媒体实时应用业务的出现和发展，使得组播组的规模、业务的特征和要求发生了很大变化，为了满足这种需求，有必要寻求网络层对组播通信的支持，使组播技术满足多媒体实时应用的要求。从而出现了以组播树(MULTICASTINGTREE)实现组播的方式。组播树是覆盖所有组播组成员的一棵生成树，组播树有以下两个优点：①信息以并行的方式沿着树枝发送到不同的组成员，降低了信息传递的时延；②网络中需要传送的复制信息最少，而且信息的复制只在树杈处进行，这样能够节省网络带宽资源，提高每次组播通信时的资源利用率，并能减少拥塞，降低网络负载。
二、蚁群优化算法
自然界常常是人类创新思想的源泉。自然界中蕴含的内在规律、生物的作息规则往往被借鉴，并诞生新的学科。许多这种在自然界启示下诞生的新学科新方法都在数学基础没有被完全证明的情况下，通过仿真实验验证了其有效性，因为神奇的生物界常常可以通过自身的演化解决许多在人类看来十分复杂的优化问题。蚁群算法属于仿生优化算法，具有鲁棒性强、全局搜索、并行分布式计算、易与其他方法结合等优点。
蚂蚁在寻找食物的过程中往往是随机选择路径的，但它们能感知当前地面上的信息素浓度，并倾向于往信息素浓度高的方向行进。信息素由蚂蚁自身释放，是实现蚁群内间接通信的物质。由于较短路径上蚂蚁的往返时间比较短，单位时间内经过该路径的蚂蚁多，所以信息素的积累速度比较长路径快。因此，当后续蚂蚁在路口时，就能感知先前蚂蚁留下的信息，并倾向于选择一条较短的路径前行。这种正反馈机制使得越来越多的蚂蚁在巢穴与食物之间的最短路径上行进。由于其他路径上的信息素会随着时间蒸发，最终所有的蚂蚁都在最优路径上行进。蚂蚁群体的这种自组织工作机制适应环境的能力特别强，假设最优路径上突然出现障碍物，蚁群也能够绕行并且很快重新探索出一条新的最优路径。
蚂蚁从每一个网络节点被释放，朝着期望的被选终节点梦动(释放遵循某个随机的或具体问题的时间表)。蚂蚁，像数据包一样，通过应用一种概率的转移规则，沿着网络移动并建立从源节点至终节点的路径。概率的转移规则充分利用了保持在与链路链接关联的信息素轨迹变量中的信息，和在一些情况下额外的局部信息。具体算法的启发法和信息结构用于评价已经找出的路径和设置蚂蚁释放的信息素量。在有向连接网络中，同一个话路的所有数据包沿着一条共同的路径传输，这条路径是由一个初步设置状态选出的。相反，在五连接或数据包中，同一话路的网络系统数据包可以沿着不同的路径传输。在沿着信道从源节点到终节点的每一个中间节点上，一个具体包转寄决策是由局部路由组件做出的。在两种类型的网络中，效果最好的路由，即没有保留任何外部资源(软件或硬件)的路由，都能够被传送。而且，在有向连接的网络系统中也可以进行资源的外部保留(软件或硬件)，通过这种方式，可以传送需要特殊特征(在带宽、延迟等方面)的服务。
三、组播路由算法的蚁群优化
1．生成备选路径集
用深度优先算法求出从源节点5到目的节点Di∈D(i＝l，2，…，m)满足时延约束的所有有效路径，组成备选路径集Ωi，一条有效路径可表示为P(5，Di)，则P(s，Di)的编码为{s，v1，…，vk，…，Di}，vk∈V，其中s，v1，…，vk，…，Di依次为从源节点s到目的节点Di所经过的节点编号，m为目的节点数目。深度优先搜索算法的基本思想是从源节点开始，随机选择一个没有访问过的邻节点，并判断从源节点到该节点的时延是否满足时延约束条件。如果满足，将该节点加入这条路径中，重复该过程，直到找到目的节点为止，则找到了一条有效路径，再从分支节点找出其他满足时延约束条件的路径，直到找到所有满足约束条件的路径，组成备选路径集。
2．适应度函数
适应度函数是蚁群算法进行选择路径的依据，也就是蚂蚁从备选路径集Ωi中选择第j条路径的概率
式1
式中， 是路径 上的分泌物强度，这表明某条路径上的分泌物强度越大，被选中的概率就越大。
3．蚁群算法信息
调整蚁群寻路时，按以下规则对路径进行信息调整：
(1)对蚂蚁所经过的路径进行分泌物强度调整，其中a是常量参数，l为该路径的代价， 为源点s到目的节点Di的路径上的分泌物强度，调整后
式2
该公式中信息的调整不是固定的，而是根据所选路径的代价来调整，增加信息调整的自适应性，同时也加快了收敛速度。
(2)当蚂蚁都走完一条路径时，对所有路径进行分泌物挥发调整，其中ρ是挥发度，其中Δ为各条路径上的初始信息强度
式3
(3)当蚂蚁都找所有目的节点，组成一棵组播树时，再按下式进行信息调整，即
式4
式中，B为常量参数，cost(T)为该组播树的代价，Pi(s,Di)是被选路径。
4.算法步骤
步骤1：生成备选路径集。用深度优先算法求出从源节点j到每个目的节点Di∈D(i＝1，2，…，n2)满足时延约束的有效路径，并组成备选路径集Ωi。
步骤2：初始化α、B、ρ、antnum和备选集中各条路径上的信息强度Δ。
步骤3：从源点发出antnum只蚂蚁，按式1计算路径集Ωi中每条路径的适应度，每只蚂蚁再按赌轮旋转规则从中选择一条路径，再按式2进行分泌物强度调整。
步骤4：当每只蚂蚁都完成一条路径选择后，按式3进行分泌物挥发性调整。
步骤5：重复执行步骤3和步骤4，直到蚂蚁找到所有目的节点的路径，每只蚂蚁寻找到的路径各组成一棵组播树。计算各组播树的代价(相同链路的代价只计算一次)，判断是否大多数蚂蚁收敛于同一组播树。如果是，则该组播树为最优路径，退出程序；否则，用最小代价的组播树代替最大代价的组播树，转步骤6执行。
步骤6：蚂蚁按原路返回，并按式4调整返回路径上分泌物强度，再转步骤3执行。
四、实验仿真
网络图是随机产生的网络拓扑结构，每对节点(u,v)之间的距离采用欧几里得距离d(u,v)，两个节点u，v之间存在边的概率由下面的公式5决定
式5
d(u,v)为节点u到节点v之间的欧几里得距离，参数α、β控制产生网络的(0，1)之间，α控制短边与长边的比例，β控制边的密度。α越大，则长边与短边的比值也越大；β越大，边越密集。n为网络图中节点数目，其中α＝0.2，β＝0.3。
首先分析算法的复杂度，从算法描述看，算法的复杂度由两部分决定。一是深度优先搜索算法的复杂度为O(n2)，则生成备选路径集时所用的复杂度O(n2)；进行蚁群寻路时的复杂度为O(nc?n2)，则总的复杂度为0(n2)，其中nc为循环次数，n为网络节点数。当问题规模比较大时，由于信息量的挥发系数ρ的存在，使那些从未被搜索到的解信息量会减小到接近于0，降低了算法的全局搜索能力；而且ρ过大时，当解的信息量增大时，以前搜索过的解被选择的可能性过大，也会影响到算法的全局搜索能力。通过减小ρ虽然可以提高算法的全局搜索能力，但又会使算法的收敛速度降低。蚂蚁数目越多，算法的全局搜索能力越强，但蚂蚁数目增大，会使算法的收敛速度减慢。而在相同的蚂蚁数目下，随问题规模的增加，算法的全局搜索能力降低。蚂蚁算法最大的缺陷是易陷入局部最优解和收敛速度慢。
参考文献：
[1] 王肖楠,程东年,张建辉. 基于蚁群优化的容错组播路由算法[J]. 信息工程大学学报,2010,11(4)：498-503.
[2] 郑啸,罗军舟,宋爱波. 基于Agent和蚁群算法的分布式服务发现[J]. 软件学报,2010,(8)：1795-1809.
[3] 郝晓青. 基于蚁群优化的无线传感器网络路由算法[J]. 电脑知识与技术：学术交流，2010,6(1)：34-36.
[4] 杨春勇,陈少平. 基于改进蚁群算法的网络负载均衡路由优化[J]. 计算机工程,2010,36(8)：4-6.
|
