一种基于蚁群算法的QoS组播路由优化器及其实现方法
一种基于蚁群算法的QoS组播路由优化器及其实现方法
【技术领域】
[0001] 本发明属于网络通信技术领域，具体设及一种基于蚁群算法的QoS组播路由优化 器及其实现方法。
【背景技术】
[0002] 随着互联网的发展，接入互联网的用户业务也趋于多样化，并具有明确的QoS要 求，如何充分地利用网络资源来满足多样化的QoS需求，该就引出了网络的QoS问题。QoS 路由选择的任务就是要在源节点到目的节点找到一条具有足够资源的路径来满足端到端 服务质量。不同的业务有不同的QoS约束，如带宽、延迟等。近几年对多约束的QoS路由问 题进行大量的研究。
[0003] 组播是一点到多点或多点到多点的网络传输新技术。它有助于控制网络的流量， 减少主机的处理量。组播的一种实现方案是采用CBT(corebase化ree)技术，对整个组播 组生成一棵W组播核为根、包括所有组播组成员的最小组播生成树。但该方案在组播核附 近的链路上容易引起阻塞，且延迟较大。另一种方案是由每个组播组成员各自生成一棵最 小代价生成树，但是大多算法只考虑单棵生成树的带宽限制而不考虑整体带宽限制，QoS得 不到保障。对此，Wang基于KMB(Kou、Markowsky和Ber2man的组播最小代价生成树）算法 提出了带宽预留的组播路由算法。Wang对组播路由的算法进行改进，进一步降低了组播树 的总代价，提高了路由分配的成功率。W上的算法在求解实际问题时要么存储开销过大，要 么计算复杂效率较低，而且大多算法是将QoS路由的多个运算规则不同、数量级别不一致 的度量参数转化为一个目标函数进行优化，通过一个综合参数来表现多个约束的特性，W 多个约束度量参数为变量构建一个目标函数，并W此函数作为路由选择标准。但是多个运 算规则不同的约束参数混合后的合成约束参数运算规则不容易确定，很难表现所有约束参 数的特性，相反容易因混合而中和掉各自的作用。
【发明内容】
[0004]为了解决现有技术存在的不足，首先对带宽、延时、延时抖动和包丢失率约束W及 费用最小的QoS组播路由问题进行分析，抽象出QoS组播路由模型的基础上，提出一种基于 蚁群算法的QoS组播路由优化的求解方法，采用FPGA实现基于蚁群算法的QoS组播路由优 化器。
[0005]其技术方案为；
[0006] 一种基于蚁群算法的QoS组播路由优化器，包括系统控制模块、下步节点集查找 下模块、下一步节点选择模块、状态更新模块、信息素更新模块、最优组播树选择模块、多路 选择器和存储器模块；
[0007]所述下步节点集查找模块主要根据禁忌表和延时邻接矩阵完成妈蚁下一步可选 节点集合的查找；
[000引所述下一步节点选择模块主要用来计算妈蚁从当前节点到下步可选节点间的转 移概率，根据转移概率妈蚁选择出下一步节点；
[0009] 所述状态更新模块负责对妈蚁的路径、路径费用、路径延时和禁忌表进行更新；
[0010] 所述信息素更新模块是当群体中所有妈蚁都进行一次觅食后，根据妈蚁所走过的 路径进行所有路径上的信息素更新；
[0011] 所述最优组播树选择模块是从满足基本条件的组播树中选出一棵最优组播树；
[0012] 所述多路选择器在系统控制模块的控制下进行信号流的分配。
[0013] 优选地，所述存储器模块包括；延时邻接矩阵，由rom构成，内部保存着各个节点 间的延时信息；费用邻接矩阵，由rom构成，内部保存着各个节点间的费用信息；信息素存 储单元，由双口ram构成，内部保存着各个路径上妈蚁留下的信息；妈蚁路径存储单元，由 双口ram构成，内部保存着每代每只妈蚁觅食过程中所走过的路径；延时邻接矩阵，由双口 ram构成，内部保存着每代每只妈蚁觅食过程中所走过的路径上的总延时；妈蚁路径费用 存储单元，由双口ram构成，内部保存着每代每只妈蚁觅食过程中所走过的路径上的总费 用；组播树存储单元，由单口ram构成，内部保存着最优组播树的0、1矩阵。
[0014] 一种基于蚁群算法的QoS组播路由优化器的实现方法，包括W下步骤：
[00巧](1)系统上电后，当接收到外部复位信号W后，各模块开始对一些信号进行初始 化，包括迭代次数、计数器的初值、随机数初值的装载W及一些控制信号的初值设置等等， 该个过程统称为复位；
[0016] (2)在系统复位结束后，系统控制模块使能查找下一步节点集模块的启动信号 start3 ;该时查找下步节点集模块开始工作，在FPGA内部时钟的作用下，根据当前节点W 从延时邻接矩阵中读出从W到其它节点的延时信息，同时系统控制模块使多路选择器muxl 输出的时钟使能信号、读地址信号rad来自于下步节点集查找模块；根据延时信息下步节 点集查找模块可查找出妈蚁下一步走的节点集合（LJD)，并计算出可选节点的个数（len_ LJD);查找结束后产生一个结束信号over3通知系统控制模块查找操作结束；
[0017] (3)在有了妈蚁下步可选节点集合之后，系统将进入妈蚁下一步节点选择过程； 系统控制模块收到查找操作结束信号后，便使能下一步节点选择模块的启动信号startl， 系统进入下一步节点选择阶段；下一步节点选择模块通过muxl、mux3和mux4从delays、 cost和tau中读出当前节点w和可选节点集中各个节点间的延时，费用和信息素进行转移 概率计算，将计算得到的转移概率与随机数模块产生的随机数比较，便可确定妈蚁下一步 节点；该样就确定了妈蚁下一步节点n_w，并将其送入状态更新模块，同时产生一个结束信 号overl通知系统控制模块下一步节点选择操作结束；
[0018] (4)系统控制模块收到下一步节点选择操作结束信号后，便能使状态更新模块的 启动信号start2,系统进入妈蚁状态更新阶段；状态更新模块根据当前节点W和下一步节 点n_w将妈蚁行走路径，路径上的费用及延时更新后分别保存到routs,costs和delays 中，同时将禁忌表更新；更新结束后判断是否到达目的节点，若未到达则跳到第（2)步继续 查找，反之则启动下只妈蚁觅食；所有操作结束后便产生一个结束信号〇ver2通知系统控 制模块；
[0019] (5)当群体中所有妈蚁都觅食一次后，系统控制模块便启动信息素更新模块进行 信息素更新操作；信息素更新模块通过miDc5、mux6和皿1巧将妈蚁走过路径及路径上的延时 和费用读入信息素更新模块中，计算相关路径上的信息素增量；通过mux3将所有信息素读 入更新模块，进行信息素挥发计算，将挥发后剩余的信息素与信息素增量相加便是更新后 的信息素，然后通过皿1x2将更新后的信息素保存到tau中；信息素更新存储完后将迭代次 数计数器累加一，并判断是否满足迭代要求，未满足迭代要求返回到第（2)步继续妈蚁觅 食操作，反之进行最优组播树选择；
[0020] (6)当迭代结束后，系统进入最优组播树选择操作，本次操作主要是从所有的组播 树中选择出最优的，最优组播树选出后W〇、1矩阵形式存储于组播树存储器中。
[0021] 本发明的有益效果；本发明采用蚁群算法进行路由选择，可满足多QoS参数约束 组播路由问题求解，基于蚁群算法的QoS组播路由优化器有助于控制网络的流量，减少主 机的信息处理量，并能较好的满足多业务互联网对服务质量的要求。
【附图说明】
[0022] 图1为本发明的基于蚁群算法的QoS组播路由优化器系统结构框图；
[0023] 图2为本发明的基于蚁群算法的QoS组播路由优化器模块连接图。
【具体实施方式】
[0024] QoS组播路由的目的就是在分布的网络中寻找最优路径，要求从源节点出发，历经 所有的目的节点，并且满足所有的约束条件，达到花费最小或达到特定的服务水平。QoS组 播路由问题是NP完全问题。首先QoS路由的网络拓扑结构抽象为一个加权图模型G(V，E)， 其中V= {vi，V2,…，V。}是网络中的节点集合；E= {ei，e2,…，e。}是网络中为连接V中两 个节点的链路集合。设P(s，d)为从源节点S至端节点d的路径，T(s，M)为组播树，S为一 棵组播树的源节点（SGV)，M为该组播树的端节点或叶节点集（MC{V-;s}))。对于任一 链路eGE，定义5种度量，分别为代价函数cost(e);E-R+、剩余带宽函数bandwidth(e);E-R\链路延时函数delay(e);E-R+、延时抖动函数delay_jitter(e);E-R\丢包率函 数packet-loss(e);E-护，其中R+表示正实数集，R+表示非负实数集。
[0025] 给定源节点S和目的节点d，对于一个路由请求r，寻找从源节点S到目的节点d 的路径P(s，d)。路由算法如果能够找到一条具有较小费用的路径，同时满足公式（1)到公 式（4)条件，则此路由P(s，d)就可接受。
[0026] (1)在P(s，d)路由的每条链路（a,b)上，带宽约束为；
[0027] bandwidth(a,b) >B" (a,b)GP(S,d) (1)，
[002引 似在P(s，d)路由的端到端延时约束为：
[0029]
(2)
[0030] (3)在目的节点，端到端延时抖动约束为：
[0031]
(3)
[0032] (4)在P(s，d)路由的端到端丢包率约束为：
[003引（l-packet_loss(a,b)) >(l-Lf), (a,b)GPk,d)(4)，
[0034] 式中，Bf，町，Jt和Lf分别表示QoS要求的带宽、延时、抖动和丢包率约束。
[0035] 要将蚁群算法应用于QoS路由优化问题中，需要对网络模型进行调整，使其具有 妈蚁选路的基本特征。将网络中各节点路由表中的选路信息替换成信息素强度，即信息素 表。每个节点的信息素表与所有可能的目的节点相对应，信息素表给出了W某个节点为目 的节点时选择下一节点的概率。
[0036] 蚁群算法中妈蚁根据每条路径上的信息素强度和转移概率进行路径选择，当某些 路径上走过的妈蚁越来越多时，留下的信息素强度也越强，W致后来妈蚁选择该路径的概 率也越高，最终找到一条最优路线。基于蚁群算法的QoS组播路由中忽略带宽、延时抖动和 丢包率度量，故每条链路用二元组（cost,delay)表示，其中的元素分别表示链路的代价和 链路延时。蚁群算法转移概率如公式巧）。
[0037]
[003引式中，allowedk表示妈蚁k下一步允许选择的网络节点；n1ij= 1/cU，Cy表示节 点i到j的费用，n2。= 1/du，d。表示节点i到j的延时。a为信息启发式因子，P、丫 为自启发式因子，表示能见度的相对重要性，反映启发式信息在指导蚁群捜索过程中的相 对重要程度，其值越大，则该状态转移概率越接近于贪屯、规则。[0039]所W信息素T更新如公式化）、（7)、巧）、（9)所示，
[0040]TU(t+n) = (1-P)TU(1：)+ekATU(t)，PG(0,1) (6)，
[0041]
[0044] 式中，P表示信息素挥发系数，1-p则表示信息素残留因子；ATy(t)表示在本 次循环中路径ij上的信息素的增量，6k为信息素增量系数，bestC记录当前妈蚁路径的最 小费用，cost(e)为路径总费用，Q为常数。
[0045] 如图1所示，本实施例一种基于蚁群算法的QoS组播路由优化器主要由系统控制 模块、下步节点集查找下模块、下一步节点选择模块、状态更新模块、信息素更新模块、最优 组播树选择模块、多路选择器和存储器模块构成，各模块由FPGA实现。其中系统控制模块 负责调度各个模块使之相互协调，进行有序的工作；下步节点集查找模块主要根据禁忌表 和延时邻接矩阵完成妈蚁下一步可选节点集合的查找；下一步节点选择模块主要用来计算 妈蚁从当前节点到下步可选节点间的转移概率，根据转移概率妈蚁选择出下一步节点；状 态更新模块负责对妈蚁的路径、路径费用、路径延时和禁忌表进行更新；信息素更新模块 是当群体中所有妈蚁都进行一次觅食后，根据妈蚁所走过的路径进行所有路径上的信息素 更新；最优组播树选择模块是从满足基本条件的组播树中选出一棵最优的；存储器模块包 括延时邻接矩阵（delay)，由rom构成，内部保存着各个节点间的延时信息；费用邻接矩阵 (cost),由rom构成，内部保存着各个节点间的费用信息；信息素存储单元（tau)，由双口 ram构成，内部保存着各个路径上妈蚁留下的信息；妈蚁路径存储单元（routs)，由双口ram 构成，内部保存着每代每只妈蚁觅食过程中所走过的路径；延时邻接矩阵（delays)，由双 口ram构成，内部保存着每代每只妈蚁觅食过程中所走过的路径上的总延时；妈蚁路径费 用存储单元（costs),由双口ram构成，内部保存着每代每只妈蚁觅食过程中所走过的路径 上的总费用；组播树存储化est_tree)，由单口ram构成，内部保存着最优组播树的0、1矩 阵；多路选择器muxl~皿1巧在系统控制模块的控制下进行信号流的分配。
[0046] 本实施例各模块连接方式如图2所示，系统运行由时钟统一协调，其运行过程如 下：
[0047] (1)系统上电后，当接收到外部复位信号W后，各模块开始对一些信号进行初始 化，包括迭代次数、计数器的初值、随机数初值的装载W及一些控制信号的初值设置等等， 该个过程统称为复位；
[0048] (2)在系统复位结束后，系统控制模块使能查找下一步节点集模块的启动信号 start3。该时查找下步节点集模块开始工作，在FPGA内部时钟的作用下，根据当前节点W 从延时邻接矩阵中读出从W到其它节点的延时信息，同时系统控制模块使多路选择器muxl 输出的时钟使能信号、读地址信号rad来自于下步节点集查找模块。根据延时信息下步节 点集查找模块可查找出妈蚁下一步走的节点集合（LJD)，并计算出可选节点的个数（len_ LJD)。查找结束后产生一个结束信号over3通知系统控制模块查找操作结束。
[0049] (3)在有了妈蚁下步可选节点集合之后，系统将进入妈蚁下一步节点选择过程。 系统控制模块收到查找操作结束信号后，便使能下一步节点选择模块的启动信号startl， 系统进入下一步节点选择阶段。下一步节点选择模块通过muxl、mux3和mux4从delays、 cost和tau中读出当前节点w和可选节点集中各个节点间的延时，费用和信息素进行转移 概率计算，将计算得到的转移概率与随机数模块产生的随机数比较，便可确定妈蚁下一步 节点。该样就确定了妈蚁下一步节点n_w，并将其送入状态更新模块，同时产生一个结束信 号overl通知系统控制模块下一步节点选择操作结束。
[0050] (4)系统控制模块收到下一步节点选择操作结束信号后，便能使状态更新模块的 启动信号start2,系统进入妈蚁状态更新阶段。状态更新模块根据当前节点W和下一步节 点n_w将妈蚁行走路径，路径上的费用及延时更新后分别保存到routs,costs和delays 中，同时将禁忌表更新。更新结束后判断是否到达目的节点，若未到达则跳到第（2)步继续 查找，反之则启动下只妈蚁觅食。所有操作结束后便产生一个结束信号〇ver2通知系统控 制模块。
[0051] (5)当群体中所有妈蚁都觅食一次后，系统控制模块便启动信息素更新模块进行 信息素更新操作。信息素更新模块通过皿1巧、mux6和皿1巧将妈蚁走过路径及路径上的延 时和费用读入信息素更新模块中，计算相关路径上的信息素增量；通过mux3将所有信息素 读入更新模块，进行信息素挥发计算，将挥发后剩余的信息素与信息素增量相加便是更新 后的信息素，然后通过皿1x2将更新后的信息素保存到tau中。信息素更新存储完后将迭代 次数计数器累加一，并判断是否满足迭代要求，未满足迭代要求返回到第（2)步继续妈蚁 觅食操作，反之进行最优组播树选择。
[0化2] (6)当迭代结束后，系统进入最优组播树选择操作，本次操作主要是从所有的组播 树中选择出最优的，最优组播树选出后W〇、1矩阵形式存储于组播树存储器中。
[0053]W上所述，仅为本发明较佳的【具体实施方式】，本发明的保护范围不限于此，任何熟 悉本技术领域的技术人员在本发明披露的技术范围内，可显而易见地得到的技术方案的简 单变化或等效替换均落入本发明的保护范围内。
【主权项】
1. 一种基于蚁群算法的QoS组播路由优化器，其特征在于，包括系统控制模块、下步节 点集查找下模块、下一步节点选择模块、状态更新模块、信息素更新模块、最优组播树选择 模块、多路选择器和存储器模块； 所述下步节点集查找模块主要根据禁忌表和延时邻接矩阵完成蚂蚁下一步可选节点 集合的查找； 所述下一步节点选择模块主要用来计算蚂蚁从当前节点到下步可选节点间的转移概 率，根据转移概率蚂蚁选择出下一步节点； 所述状态更新模块负责对蚂蚁的路径、路径费用、路径延时和禁忌表进行更新； 所述信息素更新模块是当群体中所有蚂蚁都进行一次觅食后，根据蚂蚁所走过的路径 进行所有路径上的信息素更新； 所述最优组播树选择模块是从满足基本条件的组播树中选出一棵最优组播树； 所述多路选择器在系统控制模块的控制下进行信号流的分配。2. 根据权利要求1所述的基于蚁群算法的QoS组播路由优化器，其特征在于，所述存 储器模块包括：延时邻接矩阵，由rom构成，内部保存着各个节点间的延时信息；费用邻接 矩阵，由rom构成，内部保存着各个节点间的费用信息；信息素存储单元，由双口ram构成， 内部保存着各个路径上蚂蚁留下的信息；蚂蚁路径存储单元，由双口ram构成，内部保存着 每代每只蚂蚁觅食过程中所走过的路径；延时邻接矩阵，由双口ram构成，内部保存着每代 每只蚂蚁觅食过程中所走过的路径上的总延时；蚂蚁路径费用存储单元，由双口ram构成， 内部保存着每代每只蚂蚁觅食过程中所走过的路径上的总费用；组播树存储单元，由单口 ram构成，内部保存着最优组播树的0、1矩阵。3. -种基于蚁群算法的QoS组播路由优化器的实现方法，其特征在于，包括以下步骤： (1) 系统上电后，当接收到外部复位信号以后，各模块开始对一些信号进行初始化，包 括迭代次数、计数器的初值、随机数初值的装载以及一些控制信号的初值设置等等，这个过 程统称为复位； (2) 在系统复位结束后，系统控制模块使能查找下一步节点集模块的启动信号 start3 ;这时查找下步节点集模块开始工作，在FPGA内部时钟的作用下，根据当前节点w从 延时邻接矩阵中读出从w到其它节点的延时信息，同时系统控制模块使多路选择器muxl输 出的时钟使能信号、读地址信号rad来自于下步节点集查找模块；根据延时信息下步节点 集查找模块查找出蚂蚁下一步走的节点集合（LJD)，并计算出可选节点的个数（len_LJD); 查找结束后产生一个结束信号〇ver3通知系统控制模块查找操作结束； (3) 在有了蚂蚁下步可选节点集合之后，系统将进入蚂蚁下一步节点选择过程；系统 控制模块收到查找操作结束信号后，便使能下一步节点选择模块的启动信号startl，系统 进入下一步节点选择阶段；下一步节点选择模块通过muxl、mux3和mux4从delays、cost 和tau中读出当前节点w和可选节点集中各个节点间的延时，费用和信息素进行转移概率 计算，将计算得到的转移概率与随机数模块产生的随机数比较，便确定蚂蚁下一步节点；这 样就确定了蚂蚁下一步节点n_w，并将其送入状态更新模块，同时产生一个结束信号overl 通知系统控制模块下一步节点选择操作结束； (4) 系统控制模块收到下一步节点选择操作结束信号后，便能使状态更新模块的启动 信号start2,系统进入蚂蚁状态更新阶段；状态更新模块根据当前节点w和下一步节点n_w 将蚂蚁行走路径，路径上的费用及延时更新后分别保存到routs，costs和delays中，同时 将禁忌表更新；更新结束后判断是否到达目的节点，若未到达则跳到第（2)步继续查找，反 之则启动下只蚂蚁觅食；所有操作结束后便产生一个结束信号〇ver2通知系统控制模块； (5) 当群体中所有蚂蚁都觅食一次后，系统控制模块便启动信息素更新模块进行信息 素更新操作；信息素更新模块通过mUX5、mUX6和muX7将蚂蚁走过路径及路径上的延时和费 用读入信息素更新模块中，计算相关路径上的信息素增量；通过mux3将所有信息素读入更 新模块，进行信息素挥发计算，将挥发后剩余的信息素与信息素增量相加便是更新后的信 息素，然后通过mux2将更新后的信息素保存到tau中；信息素更新存储完后将迭代次数计 数器累加一，并判断是否满足迭代要求，未满足迭代要求返回到第（2)步继续蚂蚁觅食操 作，反之进行最优组播树选择； (6) 当迭代结束后，系统进入最优组播树选择操作，本次操作主要是从所有的组播树中 选择出最优的，最优组播树选出后以〇、1矩阵形式存储于组播树存储器中。
【专利摘要】本发明公开了一种基于蚁群算法的QoS组播路由优化器及其实现方法，该优化器包括系统控制模块、下步节点集查找下模块、下一步节点选择模块、状态更新模块、信息素更新模块、最优组播树选择模块、多路选择器和存储器模块。本发明采用蚁群算法进行路由选择，可满足多QoS参数约束组播路由问题求解，基于蚁群算法的QoS组播路由优化器有助于控制网络的流量，减少主机的信息处理量，并能较好的满足多业务互联网对服务质量的要求。
【IPC分类】H04L12/725, H04L12/761
【公开号】CN104901892
【申请号】CN201510306272
【发明人】曲立国, 黄友锐, 陈珍萍, 唐超礼, 徐善永
【申请人】安徽理工大学
【公开日】2015年9月9日
【申请日】2015年6月3日
【技术领域】
[0001] 本发明属于网络通信技术领域，具体设及一种基于蚁群算法的QoS组播路由优化 器及其实现方法。
【背景技术】
[0002] 随着互联网的发展，接入互联网的用户业务也趋于多样化，并具有明确的QoS要 求，如何充分地利用网络资源来满足多样化的QoS需求，该就引出了网络的QoS问题。QoS 路由选择的任务就是要在源节点到目的节点找到一条具有足够资源的路径来满足端到端 服务质量。不同的业务有不同的QoS约束，如带宽、延迟等。近几年对多约束的QoS路由问 题进行大量的研究。
[0003] 组播是一点到多点或多点到多点的网络传输新技术。它有助于控制网络的流量， 减少主机的处理量。组播的一种实现方案是采用CBT(corebase化ree)技术，对整个组播 组生成一棵W组播核为根、包括所有组播组成员的最小组播生成树。但该方案在组播核附 近的链路上容易引起阻塞，且延迟较大。另一种方案是由每个组播组成员各自生成一棵最 小代价生成树，但是大多算法只考虑单棵生成树的带宽限制而不考虑整体带宽限制，QoS得 不到保障。对此，Wang基于KMB(Kou、Markowsky和Ber2man的组播最小代价生成树）算法 提出了带宽预留的组播路由算法。Wang对组播路由的算法进行改进，进一步降低了组播树 的总代价，提高了路由分配的成功率。W上的算法在求解实际问题时要么存储开销过大，要 么计算复杂效率较低，而且大多算法是将QoS路由的多个运算规则不同、数量级别不一致 的度量参数转化为一个目标函数进行优化，通过一个综合参数来表现多个约束的特性，W 多个约束度量参数为变量构建一个目标函数，并W此函数作为路由选择标准。但是多个运 算规则不同的约束参数混合后的合成约束参数运算规则不容易确定，很难表现所有约束参 数的特性，相反容易因混合而中和掉各自的作用。
【发明内容】
[0004]为了解决现有技术存在的不足，首先对带宽、延时、延时抖动和包丢失率约束W及 费用最小的QoS组播路由问题进行分析，抽象出QoS组播路由模型的基础上，提出一种基于 蚁群算法的QoS组播路由优化的求解方法，采用FPGA实现基于蚁群算法的QoS组播路由优 化器。
[0005]其技术方案为；
[0006] 一种基于蚁群算法的QoS组播路由优化器，包括系统控制模块、下步节点集查找 下模块、下一步节点选择模块、状态更新模块、信息素更新模块、最优组播树选择模块、多路 选择器和存储器模块；
[0007]所述下步节点集查找模块主要根据禁忌表和延时邻接矩阵完成妈蚁下一步可选 节点集合的查找；
[000引所述下一步节点选择模块主要用来计算妈蚁从当前节点到下步可选节点间的转 移概率，根据转移概率妈蚁选择出下一步节点；
[0009] 所述状态更新模块负责对妈蚁的路径、路径费用、路径延时和禁忌表进行更新；
[0010] 所述信息素更新模块是当群体中所有妈蚁都进行一次觅食后，根据妈蚁所走过的 路径进行所有路径上的信息素更新；
[0011] 所述最优组播树选择模块是从满足基本条件的组播树中选出一棵最优组播树；
[0012] 所述多路选择器在系统控制模块的控制下进行信号流的分配。
[0013] 优选地，所述存储器模块包括；延时邻接矩阵，由rom构成，内部保存着各个节点 间的延时信息；费用邻接矩阵，由rom构成，内部保存着各个节点间的费用信息；信息素存 储单元，由双口ram构成，内部保存着各个路径上妈蚁留下的信息；妈蚁路径存储单元，由 双口ram构成，内部保存着每代每只妈蚁觅食过程中所走过的路径；延时邻接矩阵，由双口 ram构成，内部保存着每代每只妈蚁觅食过程中所走过的路径上的总延时；妈蚁路径费用 存储单元，由双口ram构成，内部保存着每代每只妈蚁觅食过程中所走过的路径上的总费 用；组播树存储单元，由单口ram构成，内部保存着最优组播树的0、1矩阵。
[0014] 一种基于蚁群算法的QoS组播路由优化器的实现方法，包括W下步骤：
[00巧](1)系统上电后，当接收到外部复位信号W后，各模块开始对一些信号进行初始 化，包括迭代次数、计数器的初值、随机数初值的装载W及一些控制信号的初值设置等等， 该个过程统称为复位；
[0016] (2)在系统复位结束后，系统控制模块使能查找下一步节点集模块的启动信号 start3 ;该时查找下步节点集模块开始工作，在FPGA内部时钟的作用下，根据当前节点W 从延时邻接矩阵中读出从W到其它节点的延时信息，同时系统控制模块使多路选择器muxl 输出的时钟使能信号、读地址信号rad来自于下步节点集查找模块；根据延时信息下步节 点集查找模块可查找出妈蚁下一步走的节点集合（LJD)，并计算出可选节点的个数（len_ LJD);查找结束后产生一个结束信号over3通知系统控制模块查找操作结束；
[0017] (3)在有了妈蚁下步可选节点集合之后，系统将进入妈蚁下一步节点选择过程； 系统控制模块收到查找操作结束信号后，便使能下一步节点选择模块的启动信号startl， 系统进入下一步节点选择阶段；下一步节点选择模块通过muxl、mux3和mux4从delays、 cost和tau中读出当前节点w和可选节点集中各个节点间的延时，费用和信息素进行转移 概率计算，将计算得到的转移概率与随机数模块产生的随机数比较，便可确定妈蚁下一步 节点；该样就确定了妈蚁下一步节点n_w，并将其送入状态更新模块，同时产生一个结束信 号overl通知系统控制模块下一步节点选择操作结束；
[0018] (4)系统控制模块收到下一步节点选择操作结束信号后，便能使状态更新模块的 启动信号start2,系统进入妈蚁状态更新阶段；状态更新模块根据当前节点W和下一步节 点n_w将妈蚁行走路径，路径上的费用及延时更新后分别保存到routs,costs和delays 中，同时将禁忌表更新；更新结束后判断是否到达目的节点，若未到达则跳到第（2)步继续 查找，反之则启动下只妈蚁觅食；所有操作结束后便产生一个结束信号〇ver2通知系统控 制模块；
[0019] (5)当群体中所有妈蚁都觅食一次后，系统控制模块便启动信息素更新模块进行 信息素更新操作；信息素更新模块通过miDc5、mux6和皿1巧将妈蚁走过路径及路径上的延时 和费用读入信息素更新模块中，计算相关路径上的信息素增量；通过mux3将所有信息素读 入更新模块，进行信息素挥发计算，将挥发后剩余的信息素与信息素增量相加便是更新后 的信息素，然后通过皿1x2将更新后的信息素保存到tau中；信息素更新存储完后将迭代次 数计数器累加一，并判断是否满足迭代要求，未满足迭代要求返回到第（2)步继续妈蚁觅 食操作，反之进行最优组播树选择；
[0020] (6)当迭代结束后，系统进入最优组播树选择操作，本次操作主要是从所有的组播 树中选择出最优的，最优组播树选出后W〇、1矩阵形式存储于组播树存储器中。
[0021] 本发明的有益效果；本发明采用蚁群算法进行路由选择，可满足多QoS参数约束 组播路由问题求解，基于蚁群算法的QoS组播路由优化器有助于控制网络的流量，减少主 机的信息处理量，并能较好的满足多业务互联网对服务质量的要求。
【附图说明】
[0022] 图1为本发明的基于蚁群算法的QoS组播路由优化器系统结构框图；
[0023] 图2为本发明的基于蚁群算法的QoS组播路由优化器模块连接图。
【具体实施方式】
[0024] QoS组播路由的目的就是在分布的网络中寻找最优路径，要求从源节点出发，历经 所有的目的节点，并且满足所有的约束条件，达到花费最小或达到特定的服务水平。QoS组 播路由问题是NP完全问题。首先QoS路由的网络拓扑结构抽象为一个加权图模型G(V，E)， 其中V= {vi，V2,…，V。}是网络中的节点集合；E= {ei，e2,…，e。}是网络中为连接V中两 个节点的链路集合。设P(s，d)为从源节点S至端节点d的路径，T(s，M)为组播树，S为一 棵组播树的源节点（SGV)，M为该组播树的端节点或叶节点集（MC{V-;s}))。对于任一 链路eGE，定义5种度量，分别为代价函数cost(e);E-R+、剩余带宽函数bandwidth(e);E-R\链路延时函数delay(e);E-R+、延时抖动函数delay_jitter(e);E-R\丢包率函 数packet-loss(e);E-护，其中R+表示正实数集，R+表示非负实数集。
[0025] 给定源节点S和目的节点d，对于一个路由请求r，寻找从源节点S到目的节点d 的路径P(s，d)。路由算法如果能够找到一条具有较小费用的路径，同时满足公式（1)到公 式（4)条件，则此路由P(s，d)就可接受。
[0026] (1)在P(s，d)路由的每条链路（a,b)上，带宽约束为；
[0027] bandwidth(a,b) >B" (a,b)GP(S,d) (1)，
[002引 似在P(s，d)路由的端到端延时约束为：
[0029]
(2)
[0030] (3)在目的节点，端到端延时抖动约束为：
[0031]
(3)
[0032] (4)在P(s，d)路由的端到端丢包率约束为：
[003引（l-packet_loss(a,b)) >(l-Lf), (a,b)GPk,d)(4)，
[0034] 式中，Bf，町，Jt和Lf分别表示QoS要求的带宽、延时、抖动和丢包率约束。
[0035] 要将蚁群算法应用于QoS路由优化问题中，需要对网络模型进行调整，使其具有 妈蚁选路的基本特征。将网络中各节点路由表中的选路信息替换成信息素强度，即信息素 表。每个节点的信息素表与所有可能的目的节点相对应，信息素表给出了W某个节点为目 的节点时选择下一节点的概率。
[0036] 蚁群算法中妈蚁根据每条路径上的信息素强度和转移概率进行路径选择，当某些 路径上走过的妈蚁越来越多时，留下的信息素强度也越强，W致后来妈蚁选择该路径的概 率也越高，最终找到一条最优路线。基于蚁群算法的QoS组播路由中忽略带宽、延时抖动和 丢包率度量，故每条链路用二元组（cost,delay)表示，其中的元素分别表示链路的代价和 链路延时。蚁群算法转移概率如公式巧）。
[0037]
[003引式中，allowedk表示妈蚁k下一步允许选择的网络节点；n1ij= 1/cU，Cy表示节 点i到j的费用，n2。= 1/du，d。表示节点i到j的延时。a为信息启发式因子，P、丫 为自启发式因子，表示能见度的相对重要性，反映启发式信息在指导蚁群捜索过程中的相 对重要程度，其值越大，则该状态转移概率越接近于贪屯、规则。[0039]所W信息素T更新如公式化）、（7)、巧）、（9)所示，
[0040]TU(t+n) = (1-P)TU(1：)+ekATU(t)，PG(0,1) (6)，
[0041]
[0044] 式中，P表示信息素挥发系数，1-p则表示信息素残留因子；ATy(t)表示在本 次循环中路径ij上的信息素的增量，6k为信息素增量系数，bestC记录当前妈蚁路径的最 小费用，cost(e)为路径总费用，Q为常数。
[0045] 如图1所示，本实施例一种基于蚁群算法的QoS组播路由优化器主要由系统控制 模块、下步节点集查找下模块、下一步节点选择模块、状态更新模块、信息素更新模块、最优 组播树选择模块、多路选择器和存储器模块构成，各模块由FPGA实现。其中系统控制模块 负责调度各个模块使之相互协调，进行有序的工作；下步节点集查找模块主要根据禁忌表 和延时邻接矩阵完成妈蚁下一步可选节点集合的查找；下一步节点选择模块主要用来计算 妈蚁从当前节点到下步可选节点间的转移概率，根据转移概率妈蚁选择出下一步节点；状 态更新模块负责对妈蚁的路径、路径费用、路径延时和禁忌表进行更新；信息素更新模块 是当群体中所有妈蚁都进行一次觅食后，根据妈蚁所走过的路径进行所有路径上的信息素 更新；最优组播树选择模块是从满足基本条件的组播树中选出一棵最优的；存储器模块包 括延时邻接矩阵（delay)，由rom构成，内部保存着各个节点间的延时信息；费用邻接矩阵 (cost),由rom构成，内部保存着各个节点间的费用信息；信息素存储单元（tau)，由双口 ram构成，内部保存着各个路径上妈蚁留下的信息；妈蚁路径存储单元（routs)，由双口ram 构成，内部保存着每代每只妈蚁觅食过程中所走过的路径；延时邻接矩阵（delays)，由双 口ram构成，内部保存着每代每只妈蚁觅食过程中所走过的路径上的总延时；妈蚁路径费 用存储单元（costs),由双口ram构成，内部保存着每代每只妈蚁觅食过程中所走过的路径 上的总费用；组播树存储化est_tree)，由单口ram构成，内部保存着最优组播树的0、1矩 阵；多路选择器muxl~皿1巧在系统控制模块的控制下进行信号流的分配。
[0046] 本实施例各模块连接方式如图2所示，系统运行由时钟统一协调，其运行过程如 下：
[0047] (1)系统上电后，当接收到外部复位信号W后，各模块开始对一些信号进行初始 化，包括迭代次数、计数器的初值、随机数初值的装载W及一些控制信号的初值设置等等， 该个过程统称为复位；
[0048] (2)在系统复位结束后，系统控制模块使能查找下一步节点集模块的启动信号 start3。该时查找下步节点集模块开始工作，在FPGA内部时钟的作用下，根据当前节点W 从延时邻接矩阵中读出从W到其它节点的延时信息，同时系统控制模块使多路选择器muxl 输出的时钟使能信号、读地址信号rad来自于下步节点集查找模块。根据延时信息下步节 点集查找模块可查找出妈蚁下一步走的节点集合（LJD)，并计算出可选节点的个数（len_ LJD)。查找结束后产生一个结束信号over3通知系统控制模块查找操作结束。
[0049] (3)在有了妈蚁下步可选节点集合之后，系统将进入妈蚁下一步节点选择过程。 系统控制模块收到查找操作结束信号后，便使能下一步节点选择模块的启动信号startl， 系统进入下一步节点选择阶段。下一步节点选择模块通过muxl、mux3和mux4从delays、 cost和tau中读出当前节点w和可选节点集中各个节点间的延时，费用和信息素进行转移 概率计算，将计算得到的转移概率与随机数模块产生的随机数比较，便可确定妈蚁下一步 节点。该样就确定了妈蚁下一步节点n_w，并将其送入状态更新模块，同时产生一个结束信 号overl通知系统控制模块下一步节点选择操作结束。
[0050] (4)系统控制模块收到下一步节点选择操作结束信号后，便能使状态更新模块的 启动信号start2,系统进入妈蚁状态更新阶段。状态更新模块根据当前节点W和下一步节 点n_w将妈蚁行走路径，路径上的费用及延时更新后分别保存到routs,costs和delays 中，同时将禁忌表更新。更新结束后判断是否到达目的节点，若未到达则跳到第（2)步继续 查找，反之则启动下只妈蚁觅食。所有操作结束后便产生一个结束信号〇ver2通知系统控 制模块。
[0051] (5)当群体中所有妈蚁都觅食一次后，系统控制模块便启动信息素更新模块进行 信息素更新操作。信息素更新模块通过皿1巧、mux6和皿1巧将妈蚁走过路径及路径上的延 时和费用读入信息素更新模块中，计算相关路径上的信息素增量；通过mux3将所有信息素 读入更新模块，进行信息素挥发计算，将挥发后剩余的信息素与信息素增量相加便是更新 后的信息素，然后通过皿1x2将更新后的信息素保存到tau中。信息素更新存储完后将迭代 次数计数器累加一，并判断是否满足迭代要求，未满足迭代要求返回到第（2)步继续妈蚁 觅食操作，反之进行最优组播树选择。
[0化2] (6)当迭代结束后，系统进入最优组播树选择操作，本次操作主要是从所有的组播 树中选择出最优的，最优组播树选出后W〇、1矩阵形式存储于组播树存储器中。
[0053]W上所述，仅为本发明较佳的【具体实施方式】，本发明的保护范围不限于此，任何熟 悉本技术领域的技术人员在本发明披露的技术范围内，可显而易见地得到的技术方案的简 单变化或等效替换均落入本发明的保护范围内。
【主权项】
1. 一种基于蚁群算法的QoS组播路由优化器，其特征在于，包括系统控制模块、下步节 点集查找下模块、下一步节点选择模块、状态更新模块、信息素更新模块、最优组播树选择 模块、多路选择器和存储器模块； 所述下步节点集查找模块主要根据禁忌表和延时邻接矩阵完成蚂蚁下一步可选节点 集合的查找； 所述下一步节点选择模块主要用来计算蚂蚁从当前节点到下步可选节点间的转移概 率，根据转移概率蚂蚁选择出下一步节点； 所述状态更新模块负责对蚂蚁的路径、路径费用、路径延时和禁忌表进行更新； 所述信息素更新模块是当群体中所有蚂蚁都进行一次觅食后，根据蚂蚁所走过的路径 进行所有路径上的信息素更新； 所述最优组播树选择模块是从满足基本条件的组播树中选出一棵最优组播树； 所述多路选择器在系统控制模块的控制下进行信号流的分配。2. 根据权利要求1所述的基于蚁群算法的QoS组播路由优化器，其特征在于，所述存 储器模块包括：延时邻接矩阵，由rom构成，内部保存着各个节点间的延时信息；费用邻接 矩阵，由rom构成，内部保存着各个节点间的费用信息；信息素存储单元，由双口ram构成， 内部保存着各个路径上蚂蚁留下的信息；蚂蚁路径存储单元，由双口ram构成，内部保存着 每代每只蚂蚁觅食过程中所走过的路径；延时邻接矩阵，由双口ram构成，内部保存着每代 每只蚂蚁觅食过程中所走过的路径上的总延时；蚂蚁路径费用存储单元，由双口ram构成， 内部保存着每代每只蚂蚁觅食过程中所走过的路径上的总费用；组播树存储单元，由单口 ram构成，内部保存着最优组播树的0、1矩阵。3. -种基于蚁群算法的QoS组播路由优化器的实现方法，其特征在于，包括以下步骤： (1) 系统上电后，当接收到外部复位信号以后，各模块开始对一些信号进行初始化，包 括迭代次数、计数器的初值、随机数初值的装载以及一些控制信号的初值设置等等，这个过 程统称为复位； (2) 在系统复位结束后，系统控制模块使能查找下一步节点集模块的启动信号 start3 ;这时查找下步节点集模块开始工作，在FPGA内部时钟的作用下，根据当前节点w从 延时邻接矩阵中读出从w到其它节点的延时信息，同时系统控制模块使多路选择器muxl输 出的时钟使能信号、读地址信号rad来自于下步节点集查找模块；根据延时信息下步节点 集查找模块查找出蚂蚁下一步走的节点集合（LJD)，并计算出可选节点的个数（len_LJD); 查找结束后产生一个结束信号〇ver3通知系统控制模块查找操作结束； (3) 在有了蚂蚁下步可选节点集合之后，系统将进入蚂蚁下一步节点选择过程；系统 控制模块收到查找操作结束信号后，便使能下一步节点选择模块的启动信号startl，系统 进入下一步节点选择阶段；下一步节点选择模块通过muxl、mux3和mux4从delays、cost 和tau中读出当前节点w和可选节点集中各个节点间的延时，费用和信息素进行转移概率 计算，将计算得到的转移概率与随机数模块产生的随机数比较，便确定蚂蚁下一步节点；这 样就确定了蚂蚁下一步节点n_w，并将其送入状态更新模块，同时产生一个结束信号overl 通知系统控制模块下一步节点选择操作结束； (4) 系统控制模块收到下一步节点选择操作结束信号后，便能使状态更新模块的启动 信号start2,系统进入蚂蚁状态更新阶段；状态更新模块根据当前节点w和下一步节点n_w 将蚂蚁行走路径，路径上的费用及延时更新后分别保存到routs，costs和delays中，同时 将禁忌表更新；更新结束后判断是否到达目的节点，若未到达则跳到第（2)步继续查找，反 之则启动下只蚂蚁觅食；所有操作结束后便产生一个结束信号〇ver2通知系统控制模块； (5) 当群体中所有蚂蚁都觅食一次后，系统控制模块便启动信息素更新模块进行信息 素更新操作；信息素更新模块通过mUX5、mUX6和muX7将蚂蚁走过路径及路径上的延时和费 用读入信息素更新模块中，计算相关路径上的信息素增量；通过mux3将所有信息素读入更 新模块，进行信息素挥发计算，将挥发后剩余的信息素与信息素增量相加便是更新后的信 息素，然后通过mux2将更新后的信息素保存到tau中；信息素更新存储完后将迭代次数计 数器累加一，并判断是否满足迭代要求，未满足迭代要求返回到第（2)步继续蚂蚁觅食操 作，反之进行最优组播树选择； (6) 当迭代结束后，系统进入最优组播树选择操作，本次操作主要是从所有的组播树中 选择出最优的，最优组播树选出后以〇、1矩阵形式存储于组播树存储器中。
【专利摘要】本发明公开了一种基于蚁群算法的QoS组播路由优化器及其实现方法，该优化器包括系统控制模块、下步节点集查找下模块、下一步节点选择模块、状态更新模块、信息素更新模块、最优组播树选择模块、多路选择器和存储器模块。本发明采用蚁群算法进行路由选择，可满足多QoS参数约束组播路由问题求解，基于蚁群算法的QoS组播路由优化器有助于控制网络的流量，减少主机的信息处理量，并能较好的满足多业务互联网对服务质量的要求。
【IPC分类】H04L12/725, H04L12/761
【公开号】CN104901892
【申请号】CN201510306272
【发明人】曲立国, 黄友锐, 陈珍萍, 唐超礼, 徐善永
【申请人】安徽理工大学
【公开日】2015年9月9日
【申请日】2015年6月3日
最新回复(0)