电力通信网络业务路由方法及设备

摘要

本发明公开了一种电力通信网络业务路由方法及装置，所述方法包括：A、根据网络优化目标生成目标优化函数；B、确定业务的起始节点，并将其作为当前节点；C、利用蚁群算法计算与当前节点相连的各条链路的转移概率，所述转移概率是根据当前各条链路上的信息素计算得到的；D、依据所述转移概率选择下一跳节点；E、判断选择的下一跳节点是否为所述业务的目的节点；如果是，则将选择的下一跳节点作为当前节点，并根据所述目标优化函数确定当前各条链路上的信息素，然后重复执行步骤C至步骤E；否则，根据业务的起始节点、以及选择的所有下一跳节点生成对应所述业务的路由。本发明可以保证电力通信网络中多业务路由的性能最优。

权利要求

1.一种电力通信网络业务路由方法，其特征在于，包括以下步骤：A、根据网络优化目标生成目标优化函数minC(G)＝CF(G)+CV(G)，其中，CF(G)为全网链路总建设成本，CV(G)为全网节点总建设成本；

B、确定业务的起始节点，并将其作为当前节点；

C、利用蚁群算法计算与当前节点相连的各条链路的转移概率，所述转移概率是根据当前各条链路上的信息素计算得到的；

D、依据所述转移概率选择下一跳节点；

E、判断选择的下一跳节点是否为所述业务的目的节点；如果是，则将选择的下一跳节点作为当前节点，并根据所述目标优化函数确定当前各条链路上的信息素，然后重复执行步骤C至步骤E；否则，根据业务的起始节点、以及选择的所有下一跳节点生成对应所述业务的路由。

2.根据权利要求1所述的方法，其特征在于，所述根据所述目标优化函数确定当前各条链路上的信息素包括：按以下公式计算信息素的增量：

其中，Δτk(i，j)表示第k只蚂蚁在本次循环中留在链路fij上的信息素的增量；Q是一个体现单位蚂蚁所留轨迹数量的常数；Gk表示第k只蚂蚁为当前业务计算出一条路由并分配资源后的网络拓扑，C(Gk)为当前网络拓扑Gk的目标优化函数；hk为第k只蚂蚁所选路由的跳数，f(hk)为信息素增量的加权函数，定义如下：其中，hD为采用Dijkstra算法为当前业务计算出的最短路由的跳数，hmax为预定阈值；

按以下公式调整途经各条链路上的信息素浓度：

τ′k(i，j)＝ρτk(i，j)+Δτk(i，j)，0≤ρ＜1，其中，τk(i，j)和τ′k(i，j)分别表示此次信息素更新前和更新后链路fij上的信息素浓度，ρ表示链路上信息素的持久性。

3.根据权利要求2所述的方法，其特征在于，所述hmax为当前业务源宿节点间最短路径跳数的3倍。

4.根据权利要求1所述的方法，其特征在于，所述根据所述目标优化函数确定当前各条链路上的信息素包括：按以下公式计算信息素的增量：

其中，Δτk(i，j)表示第k只蚂蚁在本次循环中留在链路fij上的信息素的增量；Q是一个体现单位蚂蚁所留轨迹数量的常数；Gk表示第k只蚂蚁为当前业务计算出一条路由并分配资源后的网络拓扑，C(Gk)为当前网络拓扑Gk的目标优化函数；

按以下公式调整途经各条链路上的信息素浓度：

其中，τk(i，j)和τ′k(i，j)分别表示此次信息素更新前和更新后链路fij上的信息素浓度，ρ表示链路上信息素的持久性，ω1和ω2为加权因子。

5.根据权利要求4所述的方法，其特征在于，所述方法还包括：当需要考虑全局搜索能力时，设定ω1＞ω2；

当需要考虑收敛速度时，设定ω1＜ω2。

6.根据权利要求2或4所述的方法，其特征在于，所述根据所述信息素计算与业务起始点相连的各条链路的转移概率包括：利用以下公式计算与业务起始点相连的各条链路的转移概率：

其中，pk(i，j)为蚂蚁k由i节点转移到j节点的转移概率，δij表示链路(i，j)的能见度，δij＝1/d(fij）,λ1表示选路时信息素浓度的相对重要性，λ2表示能见度的相对重要性，allowedk＝{0，1，2，…，|V|-1}-tabuk，为与节点i有直接相连链路并且蚂蚁还未经过的节点集合，tabuk为蚂蚁k的禁忌表。

7.一种电力通信网络业务路由装置，其特征在于，包括：

优化函数生成单元，用于根据网络优化目标生成目标优化函数minC(G)＝CF(G)+CV(G)，其中，CF(G)为全网链路总建设成本，CV(G)为全网节点总建设成本；

节点选择单元，用于确定业务的起始节点，并将其作为蚁群所在的当前节点；

信息素确定单元，用于根据所述目标优化函数确定各条链路上的信息素；

转移概率计算单元，利用蚁群算法计算与所述当前节点相连的各条链路的转移概率，所述转移概率是根据当前各条链路上的信息素计算得到的；

所述节点选择单元，还用于依据所述转移概率确定下一跳节点，并将其作为蚁群所在的当前节点；

路由生成单元，用于根据业务的起始节点、以及选择的所有下一跳节点生成对应所述业务的路由；

判断单元，用于判断所述节点选择单元选择的下一跳节点是否为所述业务的目的节点，如果否，则通知所述信息素确定单元根据所述目标优化函数确定当前各条链路上的信息素；如果是，则通知所述路由生成单元根据业务的起始节点、以及选择的所有下一跳节点生成对应所述业务的路由。

8.根据权利要求7所述的装置，其特征在于，所述信息素确定单元包括：第一增量计算子单元，用于按以下公式计算信息素的增量：

其中，Δτk(i，j)表示第k只蚂蚁在本次循环中留在链路fij上的信息素的增量；Q是一个体现单位蚂蚁所留轨迹数量的常数；Gk表示第k只蚂蚁为当前业务计算出一条路由并分配资源后的网络拓扑，C(Gk)为当前网络拓扑Gk的目标优化函数；hk为第k只蚂蚁所选路由的跳数，f(hk)为信息素增量的加权函数，定义如下：其中，hD为采用Dijkstra算法为当前业务计算出的最短路由的跳数，hmax为预定阈值；

第一信息素浓度调整子单元，用于按以下公式调整途经各条链路上的信息素浓度：τ′k(i，j)＝ρτk(i，j)+Δτk(i，j)，0≤ρ＜1，其中，τk(i，j)和τ′k(i，j)分别表示此次信息素更新前和更新后链路fij上的信息素浓度，ρ表示链路上信息素的持久性。

9.根据权利要求7所述的装置，其特征在于，所述信息素确定单元包括：第二增量确定子单元，用于按以下公式计算信息素的增量：

其中，Δτk(i，j)表示第k只蚂蚁在本次循环中留在链路fij上的信息素的增量；Q是一个体现单位蚂蚁所留轨迹数量的常数；Gk表示第k只蚂蚁为当前业务计算出一条路由并分配资源后的网络拓扑，C(Gk)为当前网络拓扑Gk的目标优化函数；

第二信息素浓度调整子单元，用于按以下公式调整途经各条链路上的信息素浓度：其中，τk(i，j)和τ′k(i，j)分别表示此次信息素更新前和更新后链路fij上的信息素浓度，ρ表示链路上信息素的持久性，ω1和ω2为加权因子。

10.根据权利要求8或9所述的装置，其特征在于，

所述转移概率计算单元，具体用于利用以下公式计算与业务起始点相连的各条链路的转移概率：其中，pk(i，j)为蚂蚁k由i节点转移到j节点的转移概率，δij表示链路(i，j)的能见度，δij＝1/d(fij)，λ1表示选路时信息素浓度的相对重要性，λ2表示能见度的相对重要性，allowedk＝{0，1，2，…，|V|-1}-tabuk，为与节点i有直接相连链路并且蚂蚁还未经过的节点集合，tabuk为蚂蚁k的禁忌表。

说明书

电力通信网络业务路由方法及设备

技术领域

[0001] 本发明涉及电力通信网络技术领域，具体涉及一种电力通信网络业务路由方法及设备。

背景技术

[0002] 电力通信网络中的业务路径规划是指在网络环境与业务矩阵确定的条件下，以一定的优化目标，为业务矩阵中的每个业务计算工作或者保护路由并合理配置资源，在满足业务需求的前提下最小化网络的建设成本。此问题本身是一个复杂的多目标优化问题，解决此问题的传统方法一般为整数线性规划法以及一些启发式方法。其中整数线性规划法具有较高的时间复杂度，因此在实际应用中逐渐被启发式算法取代。

[0003] 在对电力通信网络中的业务路径进行规划时，虽然可以借鉴现有通信网络中的业务规划方法，但这些方法都具有其局限性。比如，整数线性规划法缺乏对搜索空间的控制，所以时间复杂度相对较高，应用困难；而遗传算法所产生解代与代之间的相似度较高，因此容易陷入局部最优解；人工免疫算法的模型简单，易于实现，但性能和可移植性相对较弱；模拟退火算法的全局搜索能力较强，且能有效地跳出局部最优解，但计算量较大，算法时间复杂度较高，收敛速度较慢且存在容易丢失近似最优解的问题，因此往往无法满足网络需返回多条路由的要求。

发明内容

[0004] 本发明实施例提供一种电力通信网络业务路由方法及设备，以满足电力通信网络中多业务路由的并行计算，并保证工作路由的性能最优。

[0005] 为此，本发明实施例提供如下技术方案：

[0006] 一种电力通信网络业务路由方法，包括以下步骤：

[0007] A、根据网络优化目标生成目标优化函数；

[0008] B、确定业务的起始节点，并将其作为当前节点；

[0009] C、利用蚁群算法计算与当前节点相连的各条链路的转移概率，所述转移概率是根据当前各条链路上的信息素计算得到的；

[0010] D、依据所述转移概率选择下一跳节点；

[0011] E、判断选择的下一跳节点是否为所述业务的目的节点；如果是，则将选择的下一跳节点作为当前节点，并根据所述目标优化函数确定当前各条链路上的信息素，然后重复执行步骤C至步骤E；否则，根据业务的起始节点、以及选择的所有下一跳节点生成对应所述业务的路由。

[0012] 一种电力通信网络业务路由装置，包括：

[0013] 优化函数生成单元，用于根据网络优化目标生成目标优化函数；

[0014] 节点选择单元，用于确定业务的起始节点，并将其作为蚁群所在的当前节点；

[0015] 信息素确定单元，用于根据所述目标优化函数确定各条链路上的信息素；

[0016] 转移概率计算单元，利用蚁群算法计算与所述当前节点相连的各条链路的转移概率，所述转移概率是根据当前各条链路上的信息素计算得到的；

[0017] 所述节点选择单元，还用于依据所述转移概率确定下一跳节点，并将其作为蚁群所在的当前节点；

[0018] 路由生成单元，用于根据业务的起始节点、以及选择的所有下一跳节点生成对应所述业务的路由；

[0019] 判断单元，用于判断所述节点选择单元选择的下一跳节点是否为所述业务的目的节点，如果否，则通知所述信息素确定单元根据所述目标优化函数确定当前各条链路上的信息素；如果是，则通知所述路由生成单元根据业务的起始节点、以及选择的所有下一跳节点生成对应所述业务的路由。

[0020] 本发明实施例提供的电力通信网络业务路由方法及装置，借鉴蚁群算法的解搜索原理，根据网络优化目标生成目标优化函数；利用蚁群算法计算业务路由过程中，根据所述目标优化函数确定当前各条链路上的信息素，根据当前各条链路上的信息素，计算与当前节点相连的各条链路的转移概率，依据所述转移概率选择下一跳节点，实现电力通信网络中多业务路由的规划，并保证工作路由的性能最优。

附图说明

[0021] 图1是本发明实施例电力通信网络业务路由方法的流程图；

[0022] 图2是本发明实施例中利用蚁群算法生成业务路由的流程图；

[0023] 图3是本发明实施例电力通信网络业务路由装置的一种结构示意图。

具体实施方式

[0024] 为了使本技术领域的人员更好地理解本发明实施例的方案，下面结合附图和实施方式对本发明实施例作进一步的详细说明。

[0025] 下面首先对蚁群算法的基本原理作简单说明。

[0026] 蚁群算法是优化领域中新出现的一种仿生进化算法，该算法采用分布式并行计算机制，易与其他方法结合，具有较强的鲁棒性。蚁群算法包含两个基本阶段：适应阶段和协作阶段，在适应阶段，各候选根据积累的信息不断调整自身结构；在协作阶段，候选解之间通过信息交流，以期产生性能更好的解，这类似于学习自动机的学习机制。

[0027] 蚁群发现最短路径的原理和机制主要是根据一些局部信息并利用简单规则进行决策：首先，要让蚂蚁能够避开障碍物，其次，要让蚂蚁找到食物，就需要让他们遍历空间上的所有点；再次，如果要让蚂蚁找到最短的路径，那么需要计算所有可能的路径并且比较它们的大小。所基于的规则有：

[0028] 1、范围：蚂蚁观察到的范围是一个方格世界，蚂蚁有一个参数为速度半径(一般是3)，那么它能观察到的范围就是3*3个方格世界，并且能移动的距离也在这个范围之内。

[0029] 2、环境：蚂蚁所在的环境是一个虚拟的世界，其中有障碍物，有别的蚂蚁，还有信息素，信息素有两种，一种是找到食物的蚂蚁洒下的食物信息素，一种是找到窝的蚂蚁洒下的窝的信息素。每个蚂蚁都仅仅能感知它范围内的环境信息。环境以一定的速率让信息素消失。

[0030] 3、觅食规则：在每只蚂蚁能感知的范围内寻找是否有食物，如果有就直接过去。否则看是否有信息素，并且比较在能感知的范围内哪一点的信息素最多，这样，它就朝信息素多的地方走，并且每只蚂蚁多会以小概率犯错误，从而并不是往信息素最多的点移动。蚂蚁找窝的规则和上面一样，只不过它对窝的信息素做出反应，而对食物信息素没反应。

[0031] 4、移动规则：每只蚂蚁都朝向信息素最多的方向移，并且，当周围没有信息素指引的时候，蚂蚁会按照自己原来运动的方向惯性的运动下去，并且，在运动的方向有一个随机的小的扰动。为了防止蚂蚁原地转圈，它会记住最近刚走过了哪些点，如果发现要走的下一点已经在最近走过了，它就会尽量避开。

[0032] 5、避障规则：如果蚂蚁要移动的方向有障碍物挡住，它会随机的选择另一个方向，并且有信息素指引的话，它会按照觅食的规则行为。

[0033] 6、播撒信息素规则：每只蚂蚁在刚找到食物或者窝的时候撒发的信息素最多，并随着它走远的距离，播撒的信息素越来越少。

[0034] 本发明实施例电力通信网络业务路由方法，借鉴蚁群算法的解搜索原理，根据网络优化目标生成目标优化函数；根据所述目标优化函数确定各条链路上的信息素；根据所述信息素计算与业务起始点相连的各条链路的转移概率；并依据所述转移概率选择下一跳节点，实现电力通信网络中多业务路由的规划，并保证工作路由的性能最优。

[0035] 如图1所示，是本发明实施例电力通信网络业务路由方法的流程图，包括以下步骤：

[0036] 步骤101，根据网络优化目标生成目标优化函数。

[0037] 比如，以经济性为优化目标，则在建模(即生成优化函数)时需要考虑网络链路成本和网络节点成本。由于网络在正常情况下的运行和损耗费用与建设费用相比很小，在规划阶段一般可忽略，所以模型中主要考虑网络的建设成本。其中，链路成本与单位长度光纤的造价相关，节点成本与节点处交换设备的结构和设备单元造价相关。

[0038] 假定已知网络拓扑为有向图G(V，F)，其中V和F分别表示网络的节点集合和链路集合，|F|表示全网链路数。W表示单纤波长的集合，|W|表示单纤波长总数。C(G)表示全网总建设成本，CV(G)表示全网节点总建设成本，CF(G)表示全网链路总建设成本，则优化目标函数为minC(G)，则：

[0039] C(G)＝CF(G)+CV(G) (1)

[0040] 设 d(fij)表示光纤fij的长度，α为链路成本的权重因子，则CF(G)可表示为：

[0041]

[0042] 全网节点总建设成本CV(G)主要包括多路复用/解复用器成本、光交叉矩阵成本以及波长变换器成本，β、γ及η分别表示以上三项成本的权重因子。CV(G)可表示为：

[0043]

[0044] 其中，CVMUX(G)表示节点处多路复用/解复用器的总成本，多路复用/解复用器分为本地和非本地上下路波长的多路复用/解复用器。前者的个数与本地节点处的上下路业OXC务数以及单纤最大波长数有关，后者的个数与节点处的光纤端口数有关；CV (G)表示节点WC
处光交叉矩阵的成本；CV (G)表示节点处波长变换器的总成本。

[0045] 设 TUv表示在节点v处上路的业务数，即以节点v为源节点的业务数；TDvMUX表示在节点v处下路的业务数，即以节点v为宿节点的业务数，则CV (G)可表示为：

[0046]

[0047] 假设节点内的光交叉矩阵由2*2光开关级联组成，则节点v处输入/出端口数为OXCKv的光交叉连接设备需要由 个2*2光开关组成，则CV (G)可表示为：

[0048]

[0049] 假设网络具备全波长变换能力，节点处波长变换器的个数与本地下路和直通的业务数有关。用THv表示节点v处直通的业务数，则Cwc(G)可表示为：

[0050]

[0051] 综合上述各项成本，全网总建设成本函数为：

[0052]

[0053] 即以式(7)作为优化函数。当然，本发明实施例并不仅限于上述优化函数，根据应用环境及目的的不同，还可以根据实际需要生成其他优化函数。

[0054] 步骤102，确定业务的起始节点，并将其作为当前节点。

[0055] 步骤103，利用蚁群算法计算与当前节点相连的各条链路的转移概率，所述转移概率是根据当前各条链路上的信息素计算得到的。

[0056] 步骤104、依据所述转移概率选择下一跳节点。

[0057] 为业务计算路由时需避免路由环的产生，因此需要建立有效的禁忌表更新机制为蚁群的路径点选择提供严格的依据。

[0058] 假设蚁群的规模为m，fij∈F，i，j∈V，蚂蚁k(1≤k≤m)在节点i处选择下一跳的方向时，τk(i，j)表示链路(i，j)上残留的信息素浓度。δij表示链路(i，j)的能见度，δij＝1/d(fij)。λ1表示选路时信息素浓度的相对重要性(λ1≥0)，λ2表示能见度的相对重要性(λ2≥0)，定义pk(i，j)为蚂蚁k由i节点转移到j节点的转移概率，则：

[0059]

[0060] 其中，allowedk＝{0，1，2，…，|V|-1}-tabuk，为蚂蚁k当前可以选择作为下一跳节点的节点集合，即与节点i有直接相连链路并且蚂蚁还未经过的节点集合，tabuk为蚂蚁k的禁忌表。初始时刻，各条路径上的信息素浓度相等，为常数C，蚂蚁k在运动过程中依据各条相邻链路上的转移概率选择下一步的路线，并更新禁忌表。

[0061] 步骤105，判断选择的下一跳节点是否为所述业务的目的节点；如果是，则执行步骤107；否则执行步骤106。

[0062] 步骤106，将选择的下一跳节点作为当前节点，并根据所述目标优化函数确定当前各条链路上的信息素，然后返回步骤103。

[0063] 步骤107，根据业务的起始节点、以及选择的所有下一跳节点生成对应所述业务的路由。

[0064] 在本发明实施例中，将蚁群算法用于电力通信网络业务路径的规划中，蚂蚁不再单一根据所选路径的长度更新相应链路上的信息素浓度，而是根据此次算路结束后网络的优化目标来更新链路上的信息素浓度。

[0065] 具体地，可以根据当前网络的优化目标(比如全网建设总成本值)来决定信息素增量，并随着迭代次数的变化而变化，从而影响后续蚂蚁进程式的路径点选择。随着时间的推移，网络中残留的信息素会逐渐挥发，参数ρ(0≤ρ＜1)表示网络链路上信息素的持久性，则1-ρ表示信息素浓度的消逝程度。

[0066] 在本发明实施例中，可以利用改进的信息素增量调整方法和/或信息素更新方法来更新链路信息素。具体有以下三种方式：

[0067] 1.首先，按以下公式计算信息素的增量：

[0068]

[0069] 其中，Δτk(i，j)表示第k只蚂蚁在本次循环中留在链路fij上的信息素的增量；Q是一个体现单位蚂蚁所留轨迹数量的常数；Gk表示第k只蚂蚁为当前业务计算出一条路由并分配资源后的网络拓扑，C(Gk)为当前网络拓扑Gk的目标优化函数；hk为第k只蚂蚁所选路由的跳数，f(hk)为信息素增量的加权函数，定义如下：

[0070]

[0071] 其中，hD为采用Dijkstra算法为当前业务计算出的最短路由的跳数，hmax为预定阈值。

[0072] 通过加权处理，由蚁群算法计算出的跳数较小的路由所包含的各条链路将得到相对较多的信息素增益；而跳数较大的路由所包含的各条链路增加的信息素则相对较少。当某条路由的跳数超过阈值hmax时，该路由所包含的各条链路的信息素增量为零，这样有效地控制了单个蚂蚁进程计算出的路由的长度。路由跳数阈值hmax的取值可以参考网络的规模，比如，可以定义hmax为当前业务源宿节点间最短路径跳数的3倍，即hmax＝3hD。

[0073] 然后，按以下公式调整途经各条链路上的信息素浓度：

[0074] τ′k(i，j)＝ρτk(i，j)+Δτk(i，j)，0≤ρ＜1， (11)[0075] 其中，τk(i，j)和τ′k(i，j)分别表示此次信息素更新前和更新后链路fij上的信息素浓度，ρ表示链路上信息素的持久性。

[0076] 2.首先，按以下公式计算信息素的增量：

[0077]

[0078] 其中，Δτk(i，j)表示第k只蚂蚁在本次循环中留在链路fij上的信息素的增量；Q是一个体现单位蚂蚁所留轨迹数量的常数；Gk表示第k只蚂蚁为当前业务计算出一条路由并分配资源后的网络拓扑，C(Gk)为当前网络拓扑Gk的目标优化函数；

[0079] 然后，按以下公式调整途经各条链路上的信息素浓度：

[0080]

[0081] 其中，τk(i，j)和τ′k(i，j)分别表示此次信息素更新前和更新后链路fij上的信息素浓度，ρ表示链路上信息素的持久性，ω1和ω2为加权因子。

[0082] 3.按照上述公式(9)计算信息素的增量，并按照上述公式(13)调整途经各条链路上的信息素浓度。

[0083] 其中，ω1的作用是约束算法初期搜索较为盲目的阶段找到的较好解，使这些较好路径上的信息素增加较慢，防止算法过早陷入局部最优解，扩大了搜索范围；而在算法后期，由于幂函数的变化速度大于线性函数的变化速度，较好路径上的信息素变化速度也随之加快，从而加快了算法后期的收敛速度。ω2的作用是控制单次信息素的增加幅度。当目标函数值C(Gk)明显变化时，τk′(i，j)的变化将会更加明显，从而提高较好解包含链路上的信息素增量，动态的修正解搜索方向。如果使ω1＞ω2，则算法更关注全局搜索能力，避免过早收敛到局部最优解上；而如果使ω1＜ω2，则算法更关注收敛速度，出现较优解时能够更快的修正搜索方向并及时收敛。

[0084] 本发明实施例电力通信网络业务路由方法，借鉴蚁群算法的解搜索原理，根据网络优化目标生成目标优化函数；根据所述目标优化函数确定各条链路上的信息素；根据所述信息素计算与业务起始点相连的各条链路的转移概率；依据所述转移概率利用蚁群算法确定业务路由，实现电力通信网络中业务路由的规划。

[0085] 进一步地，本发明实施例对信息素增量的计算方法和信息素的更新机制进行了改进，在信息素增量的计算中考虑路由跳数对网络性能的影响，采用了基于跳数的信息素增量调整策略，并通过对每只蚂蚁所带来的信息素增量进行跳数加权，实现了对路由解空间搜索方向的动态调整；同时在更新链路信息素时，引入了两个大于1的加权指数，使得在运行初期搜索较为盲目的阶段约束较好解，防止过早收敛到局部最优解上，并扩大搜索空间，而在运行后期加大信息素增量的变化幅度，加快收敛，提高了解的搜索效率。

[0086] 如图2所示，是本发明实施例中利用蚁群算法生成业务路由的具体流程图。

[0087] 下面以一个业务为例进行说明，包括以下步骤：

[0088] 步骤201，输入新业务；

[0089] 步骤202，进行初始化，包括：整理网络拓扑数据，初始化蚁群参数，设置蚂蚁组数为Am，每组蚂蚁的个数为An，(m＝Am*An)，初始化业务链表Tc，节点链表Vc和链路链表Fc，各链表末尾位以空为结束；将链路链表Fc中所有链路的初始信息素浓度置为常数C(C＞0)，初始化信息素增量为0，初始化各蚂蚁的禁忌表tabuk为空(1≤k≤m)，设置蚁群组循环变量jant＝1，组内蚂蚁循环变量iant＝1。

[0090] 步骤203，将第k只蚂蚁置于当前业务的源节点s处，其中k＝An*(jant-1)+iant。

[0091] 步骤204，对于第k只蚂蚁按上述公式(8)计算与当前节点相邻链路的转移概率，并选择下一跳节点。

[0092] 步骤205，判断当前可转移节点集合是否为空，即是否allowedk＝Null；如果是，则执行步骤213；否则执行步骤206。

[0093] 步骤206，判断该节点是否为业务宿节点；如果是，则执行步骤207；否则执行步骤214。

[0094] 步骤207，当前蚂蚁k为当前业务选出一条路由，对该路由进行波长资源预分配后计算此时的目标函数值，并计算本条路由所经过链路的信息素增量。

[0095] 在分配波长资源时，可以采用首次命中策略(First Fit)，即按照光纤和波长编号的顺序，选择第一个存在空闲波长的光纤内的第一个空闲波长，分配给业务。

[0096] 步骤208，将组内蚂蚁循环变量加1，即iant＝iant+1。

[0097] 步骤209，判断组内蚂蚁循环变量是否大于本组蚂蚁个数，即判断是否iant＞An；如果是，则执行步骤210；否则执行步骤215。

[0098] 步骤210，本组蚂蚁循环结束，找出本组内为网络带来的信息素增量最大的那只蚂蚁所选定的路由，并根据公式(11)或公式(13)更新该路由所包含链路上的信息素浓度；并将蚁群组循环变量加1，即令jant＝jant+1，iant＝1。

[0099] 步骤211，判断蚁群组循环变量是否大于蚁群组数，即是否jant＞Am；如果是，则执行步骤212；否则执行步骤216。

[0100] 步骤212，蚂蚁循环结束，确定收敛到的路由即是当前业务最终路由，并利用首次命中策略为当前业务路由分配波长。

[0101] 在确定收敛到的路由时，可以通过比较所有成功计算出业务路由的蚂蚁各自留下信息素增量值来确定，具体地，可以选择留下信息素增量最大的那只蚂蚁所计算出的路由为当前业务的路由。

[0102] 步骤213，判断这只蚂蚁死亡，清空禁忌表tabuk，然后转至步骤208。

[0103] 步骤214，将当前节点与所选择的下一跳节点加入蚂蚁k携带的禁忌表tabuk中，蚂蚁k前进，然后返回步骤204。

[0104] 步骤215，清空禁忌表tabuk，释放网络中该业务预分配所占用的波长资源；然后返回步骤203，开始下一只蚂蚁的选路过程。

[0105] 步骤216，清空禁忌表tabuk，释放网络中该业务预分配所占用的波长资源，然后返回步骤203，开始下一组蚂蚁的循环。

[0106] 当然，如果有多个业务并发的情况，可以重复上述流程，实现为多个业务生成业务路由。

[0107] 可见，本发明实施例借鉴蚁群算法的解搜索原理，并提出改进的信息素更新机制，收敛速度快并可控，解空间搜索方向性强，适用于解决电力通信网的经济性规划问题。同时该方法具有相对较强的鲁棒性、正反馈性以及优良的分布式并行计算能力，能满足多条业务路由的并行计算，且其本身也具有与网络路由过程的高度相似性，因此易于移植实现。

[0108] 本领域普通技术人员可以理解实现上述实施例方法中的全部或部分步骤是可以通过程序来指令相关的硬件来完成，所述的程序可以存储于一计算机可读取存储介质中，所述的存储介质，如：ROM/RAM、磁碟、光盘等。

[0109] 相应地，本发明实施例还提供一种电力通信网络业务路由装置。如图3所示，是该装置的一种结构示意图。

[0110] 在该实施例中，所述装置包括：优化函数生成单元301，节点选择单元302，信息素确定单元303，转移概率计算单元304，路由生成单元305，判断单元306。其中：

[0111] 优化函数生成单元301，用于根据网络优化目标生成目标优化函数；

[0112] 节点选择单元302，用于确定业务的起始节点，并将其作为蚁群所在的当前节点；

[0113] 信息素确定单元303，用于根据所述目标优化函数确定各条链路上的信息素；

[0114] 转移概率计算单元304，利用蚁群算法计算与所述当前节点相连的各条链路的转移概率，所述转移概率是根据当前各条链路上的信息素计算得到的；

[0115] 所述节点选择单元302，还用于依据所述转移概率确定下一跳节点，并将其作为蚁群所在的当前节点；

[0116] 路由生成单元305，用于根据业务的起始节点、以及选择的所有下一跳节点生成对应所述业务的路由；

[0117] 判断单元306，用于判断所述节点选择单元302选择的下一跳节点是否为所述业务的目的节点，如果否，则通知所述信息素确定单元303根据所述目标优化函数确定当前各条链路上的信息素；如果是，则通知所述路由生成单元305根据业务的起始节点、以及选择的所有下一跳节点生成对应所述业务的路由。

[0118] 其中，优化函数生成单元301可以根据路径规划需要，可以以不同的网络优化目标生成相应的目标优化函数，比如，以经济性为优化目标时，需要在建模(即生成优化函数)时需要考虑网络链路成本和网络节点成本，在这种应用中，优化函数生成单元301具体可以按以下公式生成目标优化函数：minC(G)＝CF(G)+CV(G)，其中，CF(G)为全网链路总建设成本，CV(G)为全网节点总建设成本。具体过程如前面本发明实施例电力通信网络业务路由方法中的描述，在此不再赘述。

[0119] 在本发明实施例中，所述信息素确定单元303可以有多种实现方式，比如：

[0120] 所述信息素确定单元303的一种实施例包括：第一增量计算子单元和第一信息素浓度调整子单元。其中：

[0121] 所述第一增量计算子单元，用于按以下公式计算信息素的增量：

[0122]

[0123] 其中，Δτk(i，j)表示第k只蚂蚁在本次循环中留在链路fij上的信息素的增量；Q是一个体现单位蚂蚁所留轨迹数量的常数；Gk表示第k只蚂蚁为当前业务计算出一条路由并分配资源后的网络拓扑，C(Gk)为当前网络拓扑Gk的目标优化函数；hk为第k只蚂蚁所选路由的跳数，f(hk)为信息素增量的加权函数，定义如下：

[0124]

[0125] 其中，hD为采用Dijkstra算法为当前业务计算出的最短路由的跳数，hmax为预定阈值；

[0126] 所述第一信息素浓度调整子单元，用于按以下公式调整途经各条链路上的信息素浓度：

[0127] τ′k(i，j)＝ρτk(i，j)+Δτk(i，j)，0≤ρ＜1，

[0128] 其中，τk(i，j)和τ′k(i，j)分别表示此次信息素更新前和更新后链路fij上的信息素浓度，ρ表示链路上信息素的持久性。

[0129] 所述信息素确定单元303的一种实施例包括：第二增量计算子单元和第二信息素浓度调整子单元。其中：

[0130] 所述第二增量确定子单元，用于按以下公式计算信息素的增量：

[0131]

[0132] 其中，Δτk(i，j)表示第k只蚂蚁在本次循环中留在链路fij上的信息素的增量；Q是一个体现单位蚂蚁所留轨迹数量的常数；Gk表示第k只蚂蚁为当前业务计算出一条路由并分配资源后的网络拓扑，C(Gk)为当前网络拓扑Gk的目标优化函数；

[0133] 所述第二信息素浓度调整子单元，用于按以下公式调整途经各条链路上的信息素浓度：

[0134]

[0135] 其中，τk(i，j)和τ′k(i，j)分别表示此次信息素更新前和更新后链路fij上的信息素浓度，ρ表示链路上信息素的持久性，ω1和ω2为加权因子。

[0136] 当然，所述信息素确定单元303的另一种实施例还可以包括：所述第一增量计算子单元和所述第二信息素浓度调整子单元。

[0137] 在本发明实施例中，所述转移概率计算单元304，具体用于利用以下公式计算与业务起始点相连的各条链路的转移概率：

[0138] λ1≥0，λ2≥0,

[0139] 其中，pk(i，j)为蚂蚁k由i节点转移到j节点的转移概率，δij表示链路(i，j)的能见度，δij＝1/d(fij)，λ1表示选路时信息素浓度的相对重要性，λ3表示能见度的相对重要性，allowedk＝{0，1，2，…，|V|-1}-tabuk，为与节点i有直接相连链路并且蚂蚁还未经过的节点集合，tabuk为蚂蚁k的禁忌表。

[0140] 利用本发明实施例电力通信网络业务路由装置生成业务路由的详细过程可参照前面本发明实施例电力通信网络业务路由方法中的描述，在此不再赘述。

[0141] 本发明实施例电力通信网络业务路由装置，借鉴蚁群算法的解搜索原理，根据网络优化目标生成目标优化函数；根据所述目标优化函数确定各条链路上的信息素；根据所述信息素计算与业务起始点相连的各条链路的转移概率；并依据所述转移概率选择下一跳节点，实现电力通信网络中多业务路由的规划，并保证工作路由的性能最优。

[0142] 以上对本发明实施例进行了详细介绍，本文中应用了具体实施方式对本发明进行了阐述，以上实施例的说明只是用于帮助理解本发明的方法及设备；同时，对于本领域的一般技术人员，依据本发明的思想，在具体实施方式及应用范围上均会有改变之处，综上所述，本说明书内容不应理解为对本发明的限制。