法律状态公告日
法律状态信息
法律状态
2016-03-09
未缴年费专利权终止 IPC(主分类):H04W40/02 授权公告日:20100901 终止日期:20150121 申请日:20090121
专利权的终止
2010-09-01
授权
授权
2009-09-02
实质审查的生效
实质审查的生效
2009-07-08
公开
公开
技术领域
本发明属于网络技术领域，具体涉及一种基于蚂蚁算法的自组织QoS路由方法。
背景技术
随着自组织网络的逐步成熟，网络组织日趋多样化，网络规模日益扩大，服务质量(QoS)保证问题也变得越来越重要。QoS就是网络为用户传送端到端数据时必须满足的一套可测量的预先定义的基于端到端性能的服务质量，指标包括时延、时延抖动、可用带宽和分组丢包率等。由于自组织网络具有多跳性、动态拓扑、分布式、临时性、链路带宽受限、能量受限等特性，到现在并没有一套成熟的路由方法可以在自组织网络中稳定有效的传送QoS信息。
发明内容
针对现有技术存在的不足，本发明提供一种基于蚂蚁算法的自组织QoS路由方法。
1.蚁群算法
在20世纪90年代，意大利学者M.Dorigo、V.Maniezzo和A.Colorni等人从生物进化的机理中受到启发，通过模拟自然界蚂蚁寻径的行为，提出了一种全新的模拟进化算法——蚁群算法，并应用该算法求解旅行商问题、分配问题、作业调度问题等，取得了一系列较好的实验结果。
研究表明，自然界中的蚂蚁群落，具有应用留存信息素，在其蚁穴和食物源之间选取最短(最优)路径的能力。蚂蚁在一条路径上前进时，会留下挥发性的信息素，以吸引其他蚂蚁，后来的蚂蚁选择该路径的概率与当时这条路径上信息素的浓度成正比。由于在最短(最优)路径上信息素的浓度最大，吸引了更多的蚂蚁，使选择最短(最优)路径的蚂蚁数增加。正是由于这种正反馈方法的作用，最短(最优)路径将会很快被绝大多数蚂蚁发现和利用。
国内外学者一直非常关注蚁群算法的研究与发展，其中，蚂蚁网络(AntNet)算法就是从蚁群算法演化而来。在蚂蚁网络算法中，定义了两类移动agent：前向agent和后向agent，它们在路由表的建立、刷新过程中，承担不同的任务。前向agent负责收集记录当前网络的状态信息，它通过适当的数据结构来保存寻路中收集到的状态信息，并记录路径信息，网络中各个节点以一定的间隔发送前向agent来收集信息。当前向agent到达目的节点时，会触发产生一个后向agent，同时前向agent将收集到的信息传递给新产生的后向agent，该后向agent利用获得的网络信息对路由表进行修改。
路由的大体过程如下：
(1)从源节点以一定间隔向目的节点发送前向agent。
(2)前向agent记录路径，将经历过的节点保存起来，同时记录有关的网络状态信息。
(3)当前向agent到达目的节点时，触发产生一个继承前向agent相关信息的后向agent。
(4)后向agent沿着原路径的信息，从目的节点反向到达源节点，同时更新路由表中的信息。
(5)经过若干个agent寻路之后，路由表中将记录着从源节点到目的节点的最优路径。
2.小世界模型
著名的Stanley Milgram实验发现，通过平均6人次的熟人传递就可以把社会中任意两个人联系起来，这种现象称为小世界现象。Milgram的实验揭示了两个发现：(1)短链效应普遍存在；(2)人们可以找到短链。第(2)个发现说明，当网络呈现某种拓扑结构时，仅利用局部信息就可以有效地找到短链。这个发现为分布式路由提供了契机。
Watt和Strogatz提出的模型(简称WS模型)是一种常用的小世界模型：N个节点分布在一个圆环上，初始状态时，每个节点有k个连接，分别连向最近的k个点。然后，依次调整各节点的连接，以概率p随机地改变连接的终端，但避免连向节点本身。
记D(i，j)为节点i和j之间的最短距离，平均路径距离L的计算公式如下：
当p≈0时，
在小世界网络模型中，比较成熟的是乔恩·克莱因伯格(Jon Kleinberg)模型。该模型中定义了两种边：大量的local边(近邻)和少量的long-range边(远亲)。在n个结点的二维网格模型中(为一维结点数目)，模型证明了分布式路由算法链长上界为
小世界网络的特征：(1)不考虑网络拓扑结构，结点间有很小的平均距离；(2)有较大的相识系数。某结点，在其所有邻居中，邻居间的连边数占包括该节点在内的子网连边总数比例，称为相识系数。它反映了某结点邻居间的相识程度，它与网络规模无关且恒小于1。在社会学中，一个人在寻找另一个人的过程中，不仅会利用熟人来收集信息，也会通过熟人所属公司或社团的属性收集更多信息。比如，某人希望找人帮忙编一个程序，他会向熟人询问他们是否会编程，同时也会询问他们是否认识计算机系(相当于一个虚拟组织)的学生。
3.自组织QoS路由方法的设计
3.1 自组织网络模型
自组织网络模型可以表示为一个无向连通图G(V，E)，其中V是具有生物特性行为且具有转发和处理能力的智能节点的集合，表示网络中的路由器；E是边的集合，表示网络中的链路，如图3所示。
3.2 数学模型
3.2.1 单播数学模型
在单播QoS路由问题中，优化目标是：在满足用户QoS约束的情况下，最大化用户、网络运营商的效用和用户和网络提供商效用之和，使用户和网络提供商效用达到双赢。
则有：
UUP→max{UUP}
UNP→max{UNP}
UUP+UNP→max{UUP+UNP}
(组成员p所需分摊的组播树费用比<＝用户愿付费用上限)
UUP为路径或组播树上的用户效用，UNP则为网络提供商效用。
3.2.2 组播数学模型
在组播QoS路由中，优化目标是：在满足所有组成员端到端QoS约束的前提下，最大化用户、网络运营商的效用和用户和网络提供商效用之和。
则有：UUP→max{UUP}(UUp趋近于UUp的最大值)
UNP→max{UNP}
UUP+UNP→max{UUP+UNP}
使得满足
PayP≤p(组成员p所需分摊的组播树费用比<＝用户愿付费用上限)
UUP为路径或组播树上的用户效用，UNP则为网络提供商效用
UUT→max{UUT}
UNT→max{UNT}
UUT+UNT→max{UUT+UNT}
UUT路径或组播树上的用户效用，UNT则为网络提供商效用。
3.2.3 小世界行为
(1)小世界行为具有如下特性
(a)节点度数分配的高可变性可得到短路径和高聚簇系数；
(b)当节点度数可变性不是很高时，它单独不能引起小世界行为；
(c)偏好局部连接可以引起小世界行为，尤其是在路由器级的网络拓扑中；
自组织网络具有生物特性行为，节点是动态的，边也可以建立或是去除，所以节点度数是可变的。此外，自组织网络中节点间的交互都是局部的，也就是所谓的偏好局部连接。但是，由随机的网络演化成小世界行为明显的网络需要一个过程，在这期间可能不能直接地利用小世界特点进行路由。而且还有一点，现行的小世界网络模型中，节点之间的连接指的都是直接连接，也就是说节点度数的可变性也是指的与之直接有物理连接的边。在这里，可以用非直连边充当直连边来产生小世界行为从而得到相应的优点，自组织行为设计中提到的小世界边。
例如，节点A直接相连的节点有A1、A2、A3、A4，但是以A为源节点的路由已建立了几个，其目的节点分别是D1、D2、D3，从A到D1、D2、D3就分别存在小世界边。在计算A的度数时可以将这三条小世界边计算在内。在路由时也可以动态的将小世界有边选择性的看作为A的可选下一跳边，这样就实现了一种节点度数的可变性。
当然，把一段路径当成一条边来看虽然可以产生极为有利结果，也同时带来了一些问题，毕竟在路由的过程中处理一段路径和处理一条实际边的复杂程度是不完全相同的。
这种方式有时还会引发另一个问题，通过小世界边找到的路径虽说是经过步数很少，但路径实际跳数可能是很多的，也就不是一条很优的路径，如图4所示。
图4中S和M之间存在小世界边，M和D之间存在小世界边，则S到M到D只需经过两次寻路。实际上却要经过8跳，而S→A→B→D实际上只需要3跳，虽说要经过三次寻路。
为了避免多次引入小世界边寻路导致出现上面所述的问题，这里要限制在一次路由过程，仅能在最后一跳引入小世界边。也就是在当前节点仅引入可以直接到达目的节点的小世界边，而且还要限制小世界边的长度。
这样，就能大大降低上面描述的问题发生的概率。而且对于引入小世界边得到的路径，如果性能不好，则也会被优化算法逐渐淘汰掉。另外，在自组织网络的动态环境中，快速的达到次优往往比最优更有意义。
(2)在自组织网络中实现小世界行为
(a)利用小世界边
随着算法的运行，节点会积累下来一些小世界边。随着小世界边的增多，节点知道的可达节点也就越来越多，则在后面的路由过程中，就可以直接利用小世界边的可达性信息来加快路由过程。
由当前节点出发的小世界路径记录如表1所示。
表1 小世界边列表
初始化：每个节点都有一张这样的小世界路径表，初始时，表为空。
添加：由算法来完成，算法每成功找到一条路径，就将该路径相关信息加入到源节点小世界路径表中，其中“被采用计数”值为0。
计数：每当一条小世界边被成功采用到达目的节点后，就将小世界边的“被采用次数”项值加1。
更新：每隔时间Δtswp扫描一遍表中“被采用次数”项的值，删除那些值为0的行，然后将保留下来的各行的“被采用次数”值清零。
(b)节点路由成功率
是指节点总路由次数中成功的次数所占百分比。成功率较高的节点，在路由时更可信赖。
在每一个节点都设定两个计数器，rcs(成功路由次数计数器)，rct(节点总路由次数计数器)。当节点被采用到一次路由中去时，rct就增1，而当该次路由成功后，rcs就增1。这里，为保证时效性，rcs、rct值每隔一定周期Δtrc就清零。
计算节点i的路由成功率公式如下：
(c)根据地址结构：具有相同IP地址前缀的节点很有可能会位于临近的区域内，而且相同前缀部分越长，越可能位于更近的区域内，这里将地址的这种特性称为相近度。例如：202.118.1.64和202.118.1.206，相同的前缀部分为202.118.1，所以二者位于很近的区域内，二者的相近度较高。
计算可选下一跳节点的地址和本次路由目的地址的相近度，相近度越高，则下一跳节点越有可能找到目的节点，这也类似为下一跳节点对此次路由目的地址的熟悉程度。
两个地址相近度的计算采取下面的方法：将32位地址从左向右逐位扫描比较二进制位，如果相同就继续扫描，如果不同就结束，记录相同的位数Mik，则相近度Vi为：
该方法按如下步骤：
步骤A：接收到邻居路由器发送的数据报文；
步骤B：根据数据报文的目的地址是否为单播地址判断报文类型是否为单播报文；
其特征在于：根据步骤B是单播报文，则执行步骤C，否则执行步骤G；
步骤C：进入单播建模QoS路由方法；
步骤D：初始化路由器寄存器，发送前向蚂蚁agent寻路，调用蚂蚁算法，其中agent负责收集记录当前网络状态信息；
步骤E：考查路径评价值Jpath，找到符合用户请求的路径；
步骤F：转到步骤K；
步骤G：进入组播建模QoS路由方法，给定组播请求：
步骤H：初始化路由器寄存器，构建组播树；
步骤I：组播树费用分摊；
在形成组播树以后，由于所选边是选用用户共用的，所以资费也理所应当由选用用户共同分担，分摊的原则是：用户独自占用该条路径所需付的费用越高则用户在组播树付费中分摊的部分越大。
设定源节点到每一个组成员的路径所需付费的集合为：
WP＝{pay1，pay2，...，payn-1，payn}式中payn为每一个组成员的路径所需付费，n＝1，2，…，N，N属于自然数，则第i个组成员vi所需分摊的组播树费用比例为：
步骤J：计算组播树评价值JT，找出当前可行组播树；
步骤K：根据计算出的当前可行组播树将数据报文转发到下一跳路由器。
步骤D中调用蚂蚁算法包括：
步骤D1：初始化路由器寄存器，设置最多迭代次数TIN，已迭代次数IN＝0，初始化每次迭代发送的蚂蚁agent数量AN，已发送的agent数an＝0，路径评价值Jpath＝∞，可行路径为空；
步骤D2：IN←IN+1，源节点以间隔Δt发送AN个前向蚂蚁agent寻路，每发送一个agent就an←an+1，初始化每一个前向agent，其中：蚂蚁agent序号seq＝an；
步骤D3：前向agent记录路径，将经历过的节点保存起来，同时记录有关的网络状态信息，前向蚂蚁agent在源节点被发出后，在网络中的每一个经过的节点按下面步骤执行行为；
步骤D31：判断当前蚂蚁agent跳数是否超限，如果是，则蚂蚁agent死亡；
步骤D32：如果当前节点的直接下一跳节点有本次路由目的节点，则考察与该节点之间的边是否满足用户请求约束，如满足，则蚂蚁agent跳转到目的节点，转到步骤D35；
步骤D33：在当前节点实现小世界；
步骤D34：在当前节点进行下一跳选择；
步骤D341：在当前节点，将路由总次数计数器增加1；
步骤D342：实现小世界行为；
步骤D343：如果下一跳选择成功返回，则蚂蚁agent前行至该节点；
步骤D344：如果下一跳选择失败，蚂蚁agent死亡；
步骤D35：前向蚂蚁agent任务完成；
步骤D4：当前向agent到达目的节点时，触发产生一个继承前向agent相关信息的后向agent。后向agent沿着原路径的信息，从目的节点反向到达源节点，同时更新路由表中的信息；
步骤D41：在目的节点，根据前向蚂蚁agent信息，根据公式
步骤D42：后向agent按保存的路径信息，反向跳到上游节点，然后更新信息素表；在当前节点，蚂蚁将路由成功次数计数器增加1，如果蚂蚁agent在当前节点引入了小世界边，则更新小世界边表；
步骤D43：判断后向蚂蚁agent是否到达源节点，如果未到达，则跳转至步骤D42；
步骤D44：将后向蚂蚁agent携带路径的评价值和当前路径评价值进行比较，如果agent携带路径的评价值小于当前路径评价值，则将新路径保存为当前可行路径；
步骤D45：后向agent任务完成，调用蚁群算法结束。
步骤D33在当前节点实现小世界边包括：
步骤D331：判断当前agent是否正在使用小世界边，如果是，则直接取出小世界边作为下一跳节点；否则，跳转至步骤D333；
步骤D332：判断该下一跳节点能否满足用户请求约束，如果能，蚂蚁agent选择该节点作为下一跳节点，保存当前节点与该节点之间边的QoS信息和成本信息，蚂蚁agent在当前节点行为结束，然后前行至该下一跳节点；否则，蚂蚁agent死亡；
步骤D333：考察蚂蚁agent的序列号，判断该agent是否为本次迭代发送中的最后一个，如果不是，则跳转至步骤D34；
步骤D334：考察当前节点小世界边表，是否存在到达目的节点的小世界边，如果不存在，则跳转至步骤D34；
步骤D335：将小世界边存入蚂蚁agent，并设置蚂蚁agent使用小世界边，然后蚂蚁agent记录该节点地址，跳转至D331。
步骤D342实现小世界行为包括：
如果蚂蚁agent的序列号为偶数，则随机选择下一跳节点；否则，进行计算选择下一跳，计算对应边的用户满意度值计算公式：
步骤E考查路径评价值Jpath，找到符合用户请求的路径包括：
步骤E1：在源节点等待一段时间Δt后，考查路径评价值Jpath；
步骤E2：如果Jpath<∞，则算法成功找到符合用户请求的路径，在源节点将当前保留路径加入小世界表，转至步骤K；
步骤E3：如果Jpath＝∞，则判断IN是否小于TIN，如果是，则转至步骤D3，否则路由失败。
步骤H初始化路由器寄存器，构建组播树包括：
步骤H1：初始化路由器寄存器，设置迭代次数CN，已迭代次数cn＝0，组播树评价值Jtree＝∞，当前可行组播树为空；
步骤H2：将所有组成员按带宽请求由大到小排列，设定待处理组成员集合W＝{v1，v2，...，vn-1，vn}，vn为待处理组成员，n＝1，2，…，N，N属于自然数，已处理组成员集合A＝Φ，可行路径集合P＝Φ，其中Φ为空集合；
步骤H3：取vd∈W，利用基于蚂蚁网络的单播路由算法，由va向vd寻找一条满足成员vd请求约束的可行路径Pd，如果未找到，则此次构建组播树失败，跳转到步骤J3；
步骤H4：将节点vd从W删除，并加入A；
步骤H5：检查可行路径Pd上是否含有位于W中的组成员，如果没有，则跳转到步骤H7；
步骤H6：如果Pd上含有位于W中的组成员，判断这些组成员的请求约束能否在Pd得到满足，将能被满足的节点从W删除，并加入A；
步骤H7：将可行路径Pd加入集合P；
步骤H8：若集合W不为空，则跳转到步骤H1；
步骤H9：将可行路径中P中的路径拼成一棵组播树，在成树的过程中，每个组成员的请求约束都要被满足，并且不能出现环，否则，此次构建组播树失败，跳转至步骤J3。
步骤J计算组播树评价值JT，找出当前可行组播树包括：
步骤J1：根据公式计算组播树评价值JT；
步骤J2：如果JT<Jtree，Jtree为当前可行组播树的评价值，则用计算得到的组播树代替当前可行组播树，Jtree＝JT；
步骤J3：cn←cn+1，若cn<CN，跳转到步骤H；
步骤J4：判断Jtree<∞是否成立，如果成立，则算法成功，否则算法失败。
本发明设计了一种路由方法，该方法基于一种分布式的路由算法—蚂蚁网络算法进行算法设计。通过该路由方法在路由过程中可以有效的基于QoS请求对数据进行路由和转发。蚂蚁算法可以设计为在网络中逐跳寻路，本发明设计了这种算法的下一跳选择策略，并扩展支持QoS路由。为了降低路由时间，提高路由成功率，本文在算法中引入了小世界行为。同时引入了模糊数学知识描述不精确的链路参数，引入纳什(Nash)均衡、帕累托(Pareto)最优等微观经济学方法来进行链路策略选择。本发明对设计的自组织网络模型和自组织QoS路由方法在NS2平台上进行仿真，对路由方法进行实现。通过对仿真和实现进行性能评价，得出自组织网络模型较之传统网络模型具有很大的优越性，该设计的路由方法具有良好的性能和实用性。
附图说明
图1是本发明基于蚂蚁算法的自组织QoS路由方法步骤框图；
图2是本发明基于蚂蚁算法的自组织QoS路由方法具体流程图；
图3是自组织网络拓扑示意图；
图4是小世界边示意图；
图5是本发明实现平台示意图；
图6是本发明中国教育科研网络(CERNET)拓扑。
具体实施方式
本发明一种基于蚂蚁算法的自组织QoS路由方法，将蚂蚁算法嵌入到Quagga(Quagga是一款开源的路由软件，在Quagga上可以运行OSPF，BGP等路由协议)的开源路由程序中的源代码中，使用24台PC机作为原型路由器，其中4台作为应用服务器；24块英特尔(INTEL)网卡，24块普瑞尔(TP_LINK)网卡、26条网线。
原型路由器软件配置如下：LinuxFC7操作系统；使用Linux下GNU C扩展Quagga软件路由器中的ospf6d和bgpd两个守护进程，使用Liunx下GNU C编写与算法对接的接口模块，实现自组织网络中的自适应单播路由协议；使用Liunx下GNU C编写守护进程，扩展实现基于IPv6的自适应组播路由协议。网络拓扑结构如图5所示，20台原型路由器参照CERNET2网络结构部署，4台应用服务器与原型路由器直连。本发明已经实现了绑定算法所需要的协议支持，邻居信息的获取，网络状态信息的获取，路由agent的转发。在NS2(NS2是指NetworkSimulator version 2，是一种针对网络技术的源代码公开的、免费的软件模拟平台，研究人员使用它可以很容易的进行网络技术的开发，目前已成了学术界广泛使用的一种网络模拟软件)系统中，运行已实现的自组织网络仿真系统，进行实际数据发送测试，得到跟踪(trace)文件。Trace文件是NS2系统根据网络运行状态生成的数据包跟踪文件，每当链路或是队列中有一个数据包到达、离开或是丢弃时，都会被记录下来，连通当时的时间以及数据包的基本信息也同时被记录下来。
路由仿真系统建立在CERNET(中国教育科研网)拓扑上，如图6所示，拓扑的参数设定基本参照实际情形，具有一定的客观性。
在网络模型中，给定一个路由请求，分别运行本文的路由方法进行找路和加入路由表，然后再根据路由请求中设定的带宽值发送一段时间的数据包，得到trace文件。再使用NS2系统内置的距离向量(DV)路由协议，按同样的源、目的节点和带宽值发送相同时间的数据，得到trace文件。分别对得到的trace文件进行分析，得到数据传输路径的吞吐率、端到端延迟、抖动和丢包率，然后结合用户请求通过满意度公式计算用户端到端传输满意度。本发明如图1和图2所示，按如下步骤：
步骤A：接收到邻居路由器发送的数据报文；
步骤B：根据数据报文的目的地址是否为单播地址判断报文类型是否为单播报文；
其特征在于：根据步骤B是单播报文，则执行步骤C，否则执行步骤G；
步骤C：进入单播建模QoS路由方法；
步骤D：初始化路由器寄存器，发送前向蚂蚁agent寻路，调用蚂蚁算法，其中agent负责收集记录当前网络状态信息；
步骤E：考查路径评价值Jpath，找到符合用户请求的路径；
步骤F：转到步骤K；
步骤G：进入组播建模QoS路由方法，给定组播请求：
步骤H：初始化路由器寄存器，构建组播树；
步骤I：组播树费用分摊；
在形成组播树以后，由于所选边是选用用户共用的，所以资费也理所应当由选用用户共同分担，分摊的原则是：用户独自占用该条路径所需付的费用越高则用户在组播树付费中分摊的部分越大。
设定源节点到每一个组成员的路径所需付费的集合为：
WP＝{pay1，pay2，...，payn-1，payn}式中payn为每一个组成员的路径所需付费，n＝1，2，…，N，N属于自然数，则第i个组成员v1所需分摊的组播树费用比例为：
步骤J：计算组播树评价值JT，找出当前可行组播树；
步骤K：根据计算出的当前可行组播树将数据报文转发到下一跳路由器。
步骤D中调用蚂蚁算法包括：
步骤D1：初始化路由器寄存器，设置最多迭代次数TIN，已迭代次数IN＝0，初始化每次迭代发送的蚂蚁agent数量AN，已发送的agent数an＝0，路径评价值Jpath＝∞，可行路径为空；
步骤D2：IN←IN+1，源节点以间隔Δt发送AN个前向蚂蚁agent寻路，每发送一个agent就an←an+1，初始化每一个前向agent，其中：蚂蚁agent序号seq＝an；
步骤D3：前向agent记录路径，将经历过的节点保存起来，同时记录有关的网络状态信息，前向蚂蚁agent在源节点被发出后，在网络中的每一个经过的节点按下面步骤执行行为；
步骤D31：判断当前蚂蚁agent跳数是否超限，如果是，则蚂蚁agent死亡；
步骤D32：如果当前节点的直接下一跳节点有本次路由目的节点，则考察与该节点之间的边是否满足用户请求约束，如满足，则蚂蚁agent跳转到目的节点，转到步骤D35；
步骤D33：在当前节点实现小世界；
步骤D34：在当前节点进行下一跳选择；
步骤D341：在当前节点，将路由总次数计数器增加1；
步骤D342：实现小世界行为；
步骤D343：如果下一跳选择成功返回，则蚂蚁agent前行至该节点；
步骤D344：如果下一跳选择失败，蚂蚁agent死亡；
步骤D35：前向蚂蚁agent任务完成；
步骤D4：当前向agent到达目的节点时，触发产生一个继承前向agent相关信息的后向agent。后向agent沿着原路径的信息，从目的节点反向到达源节点，同时更新路由表中的信息；
步骤D41：在目的节点，根据前向蚂蚁agent信息，根据公式
步骤D42：后向agent按保存的路径信息，反向跳到上游节点，然后更新信息素表；在当前节点，蚂蚁将路由成功次数计数器增加1，如果蚂蚁agent在当前节点引入了小世界边，则更新小世界边表；
步骤D43：判断后向蚂蚁agent是否到达源节点，如果未到达，则跳转至步骤D42；
步骤D44：将后向蚂蚁agent携带路径的评价值和当前路径评价值进行比较，如果agent携带路径的评价值小于当前路径评价值，则将新路径保存为当前可行路径；
步骤D45：后向agent任务完成，调用蚁群算法结束。
步骤D33在当前节点实现小世界边包括：
步骤D331：判断当前agent是否正在使用小世界边，如果是，则直接取出小世界边作为下一跳节点；否则，跳转至步骤D333；
步骤D332：判断该下一跳节点能否满足用户请求约束，如果能，蚂蚁agent选择该节点作为下一跳节点，保存当前节点与该节点之间边的QoS信息和成本信息，蚂蚁agent在当前节点行为结束，然后前行至该下一跳节点；否则，蚂蚁agent死亡；
步骤D333：考察蚂蚁agent的序列号，判断该agent是否为本次迭代发送的个中的最后一个，如果不是，则跳转至步骤D34；
步骤D334：考察当前节点小世界边表，是否存在到达目的节点的小世界边，如果不存在，则跳转至步骤D34；
步骤D335：将小世界边存入蚂蚁agent，并设置蚂蚁agent使用小世界边，然后蚂蚁agent记录该节点地址，跳转至D331。
步骤D342实现小世界行为包括：
如果蚂蚁agent的序列号为偶数，则随机选择下一跳节点；否则，进行计算选择下一跳，计算对应边的用户满意度值计算公式：
步骤E考查路径评价值Jpath，找到符合用户请求的路径包括：
步骤E1：在源节点等待一段时间Δt后，考查路径评价值Jpath；
步骤E2：如果Jpath<∞，则算法成功找到符合用户请求的路径，在源节点将当前保留路径加入小世界表，转至步骤K；
步骤E3：如果Jpath＝∞，则判断IN是否小于TIN，如果是，则转至步骤D3，否则路由失败。
步骤H初始化路由器寄存器，构建组播树包括：
步骤H1：初始化路由器寄存器，设置迭代次数CN，已迭代次数cn＝0，组播树评价值Jtree＝∞，当前可行组播树为空；
步骤H2：将所有组成员按带宽请求由大到小排列，设定待处理组成员集合W＝{v1，v2，...，vn-1，vn}，vn为待处理组成员，n＝1，2，…，N，N属于自然数，已处理组成员集合A＝Φ，可行路径集合P＝Φ，其中Φ为空集合；
步骤H3：取vd∈W，利用基于蚂蚁网络的单播路由算法，由vs向vd寻找一条满足成员vd请求约束的可行路径Pd，如果未找到，则此次构建组播树失败，跳转到步骤J3；
步骤H4：将节点vd从W删除，并加入A；
步骤H5：检查可行路径Pd上是否含有位于W中的组成员，如果没有，则跳转到步骤H7；
步骤H6：如果Pd上含有位于W中的组成员，判断这些组成员的请求约束能否在Pd得到满足，将能被满足的节点从W删除，并加入A；
步骤H7：将可行路径Pd加入集合P；
步骤H8：若集合W不为空，则跳转到步骤H1；
步骤H9：将可行路径中P中的路径拼成一棵组播树，在成树的过程中，每个组成员的请求约束都要被满足，并且不能出现环，否则，此次构建组播树失败，跳转至步骤J3。
步骤J计算组播树评价值JT，找出当前可行组播树包括：
步骤J1：根据公式计算组播树评价值JT；
步骤J2：如果JT<Jtree，Jtree为当前可行组播树的评价值，则用计算得到的组播树代替当前可行组播树，Jtree＝JT；
步骤J3：cn←cn+1，若cn<CN，跳转到步骤H；
步骤J4：判断Jtree<∞是否成立，如果成立，则算法成功，否则算法失败。
使用本发明方法的结果如表2所示，
表2数据传输满意度
表2分别统计了不同网络负载下的满意度结果，负载很轻时两种路由方法的传输满意度相差无几，随着负载的加重，本文路由方法开始明显优于使用距离向量的(DV)方法，当负载很重时两种路由方法的传输满意度值又归于相近。
机译： 在自组织网络中使用基于活动检测的自组织路由算法的系统和方法
机译： 通过使用网关路由器的互连信息在域之间提供QOS路由的系统和一种能够设置QOS路由的方法
机译： 基于蚂蚁觅食算法的潜在购买力商业化的系统和方法
