一种基于SDN集中控制的骨干网能耗优化方法

摘要

本发明是一种基于SDN集中控制的骨干网能耗优化方法，涉及IP骨干网节能技术领域。本发明将IP骨干网络抽象为无向加权图，获得无向图中执行move机制的所有move过程，确定获得的所有move过程的兼容矩阵C，C中元素用于标识一个move过程在执行后另一个move过程是否仍可被执行；本发明基于开放最短路径优先协议，将在保证用户QoS的基础上找出尽量多的可睡链路的问题，抽象为一个满足背包条件最大团问题；求解最大团问题，将获得的可睡链路置于睡眠态。本发明在节能的同时尽量少地改变网络拓扑，降低了计算复杂度，减少了由于执行节能策略造成的网络重计算所需时间，网络响应时间比现有策略大大减小。

权利要求

1.一种基于软件定义网络SDN集中控制的骨干网能耗优化方法，将IP骨干网络抽象为无向加权图G(V,E,W)，V为网络中节点集合，E为网络中节点间链路集合，W为节点间链路上对应的权值；其特征在于，进行下面步骤：第一步，依据规则1～3获得无向图G中执行move机制的所有move过程；

规则1：move过程的入口节点和出口节点必须邻接；规则2：一个入口节点只能属于一个move过程；规则3：如果一个节点成为一个move过程的出口节点，那么这个节点的最短路径树将不能再发生改变；

一个move过程具有一个入口节点和一个出口节点，设入口节点vi、出口节点vj，运行move机制，获得可睡链路；move机制实现过程为：首先，通过OSPF路由协议计算入口节点和出口节点的最短路径树spt(vi)、spt(vj)；然后，比较spt(vi)和spt(vj)获得入口节点的修改路径树mpt(vi)；最后，比较spt(vi)与mpt(vi)得到可睡链路；vi、vj分别为E中第i个、第j个节点；

第二步，确定第一步获得的所有move过程的兼容矩阵C；矩阵C中元素cij用于标识第i个move过程movei和第j个move过程movej是否兼容，若二者兼容cij值为1，否则值为0；

若movei被执行后，movej仍可以被执行，则movei和movej兼容；

第三步，根据兼容矩阵C获得无向图H(M,F)；M表示第一步获得的所有move过程，每个move过程为一个节点，设共有K个move过程，K为正整数且K≤||E||，||E||表示E中链路总数；F表示move过程之间的兼容关系，用连接边来表示，两个move过程相连表示兼容，不相连表示不兼容；用 表示两个move过程之间不兼容，则得到H的补图将问题：在保证用户QoS的基础上，找出尽量多的可睡链路；抽象为如下满足背包条件最大团问题，表示如下：其中，qi表示第i个move过程的可睡链路数量，xi表示第i个move过程是否执行，(i,j)表示第i个move过程和第j个move过程不兼容，(MPT(i))min表示第i个move过程的修改路径树的链路权值和在可选的move过程中最小；

第四步，求解所述的最大团问题，将获得的可睡链路置于睡眠态；

求解最大团问题的实现步骤如下：

步骤4.1，输入无向加权图G(V,E,W)，寻找运行初始节点im，节点im是所有网络节点中相邻链接点最多的节点；

步骤4.2，以im为入口节点，找到所有以im为入口节点的move过程，从中选取修改路径树的链路权值和最小的move过程，作为第一个move过程放入到解集 中；

move过程的修改路径树是指该move过程的入口节点的修改路径树；

步骤4.3，更新入口节点集合及出口节点集合；

对于刚放入解集 的move过程，在入口节点集合中去除该move过程的入口节点及出口节点，在出口节点集合中，去除该move过程的入口节点、出口节点以及该move过程的锁节点集；入口节点集合和出口节点集合初始都包含无向图G中所有节点；

在一个move过程中，对于一个节点，如果至少有一条经过该节点的路径发生改变，则该节点为与该move过程相关锁节点；某move过程的锁节点集就是所有与该move过程相关锁节点的集合；

步骤4.4，寻找所有与刚放入解集 的move过程兼容的move过程，从中选择修改路径树的链路权值和最小的move过程，放入解集步骤4.5，判断出口节点集合是否为空，若是，则输出解集 根据解集 获得可睡链路；

若不为空，则转至步骤4.3继续执行。

2.根据权利要求1所述的一种基于软件定义网络SDN集中控制的骨干网能耗优化方法，其特征在于，所述的第二步中，判断movei和movej是否兼容的具体方法是：(1)确定movei和movej的锁节点集；

在一个move过程中，对于一个节点，如果至少有一条经过该节点的路径发生改变，则该节点为与该move过程相关锁节点；某move过程的锁节点集就是所有与该move过程相关锁节点的集合；

(2)当且仅当movei的出口节点不在movej的锁节点集，movej的出口节点不在movei的锁节点集中，则movei和movej兼容；否则，movei和movej不兼容。

说明书

一种基于SDN集中控制的骨干网能耗优化方法

技术领域

[0001] 本发明涉及IP骨干网节能技术领域，具体是指一种基于SDN(Software Defined Networks，软件定义网络)集中控制的骨干网能耗优化方法。

背景技术

[0002] 统计表明，全球能耗8％来自ICT(Information Communication Technology，信息通信技术)。ICT能耗15％来自网络。近年来，随着移动互联网、物联网及云计算技术普及，IP骨干网能耗激增，IP骨干网能耗问题亟待解决。运营商为满足日益增长用户需要，必须部署足够密集网络用来应对高峰期用户QoS(Quality of Service，服务质量)。研究发现，网络负载在时间维度上具有明显的不均衡性，且网络负载高峰期是短暂，可预测的。因此，在通常情况下，IP骨干网平稳期是可预测、长期存在的。这使得IP骨干网节能成为可能。

[0003] 当前大部分骨干网以OSPF(Open Shortest Path First，开放最短路径优先)作为路由协议，因此目前绝大多数节能路由策略基于OSPF协议。据节能策略与OSPF协议对应关系，节能策略可分为两类：覆盖型；集成型。覆盖型节能策略与OSPF路由协议完全独立。这类路由节能策略存在重大缺陷：运行时会大范围改变网络拓扑，造成积网络拓扑大面积重计算，导致网络暂时瘫痪。集成型路由策略集成在OSPF路由协议中，与OSPF一体，不但节能，而且运行时尽量减少对网络拓扑的改变，不会引发网络暂时瘫痪问题。

[0004] 现有基于OSPF提出的启发式算法，通过遍历所有可能拆除链路的组合来找寻可能的次优解(参考文件1：Energy management in IP traffic engineering with shortest path routing,E. Amaldi,A.Capone,L.Gianoli,and L.Macetti,2011)。如图1所示，流程为：(1)根据输入的网络拓扑遍历所有的节点，网络拓扑用无向图G(V,E,W)表示，V为网络节点集合，E为网络拓扑中连接边集合，W为表示链路上对应的权值向量。(2)分别结算节点与其邻居节点的 SPT(Shortest Path Tree，最短路径树)，通过对比两者SPT可以找到这个节点对能够关闭的链路，同时检查约束条件，将不满足者去除。(3)找到所有可能的节点对后，将具有相同的两个节点的重复节点对去除。(4)随机以某个节点对为起点，根据其相兼容的其他节点对的集合一步一步找出所有互相兼容的节点对集合。(5)输出结果。该算法基于OSPF协议，通过对比相邻节点的SPT来找到满足约束的可睡链路来达到节能的目的，然而该算法需要遍历所有节点，并计算所有可能的节点对，这样会大大提升计算复杂度。同时该算法仅仅只考虑了链路的可拆除性，而没有对拆除链路后对网络造成的影响加以限制，例如网络拓扑改变过大，网络响应时间增加等等。

[0005] 近年来，SDN的兴起，开始改变网络被动性的现状。SND网络架构，与架构静态、控制转发耦合、管理复杂传统网络架构相比，SDN类型网络架构中控制、转发有效解耦。原网络节点中控制部分被分离出来，集中置于网络控制器中。相对传统网络架构静态、难于控制管理、数据平面与控制平面耦合的问题，SDN网络架构中，数据平面与控制平面分离。具有如下明显特性：灵活性，新拓扑或功能以软件形式实现，使用标准程序设计语言及统一操作系统；易部署性，在向实际网络或网络试验床上部署功能性协议时，不再需要重新编码和配置；交互性，真实网络中，对其进行实时管理控制；可扩展性，成千上万交换机组成的网络，通过便携式电脑即可对其协议环境进行扩展；易共享性，原有协议可以更方便共享。

发明内容

[0006] 本发明针对基于OSPF算法计算复杂度高、存在网络拓扑改变过大，网络响应时间增加的问题，提出了一种基于SDN集中控制的骨干网能耗优化方法。本发明在有效保证用户QoS (主要侧重于网络响应时间)基础上，找出尽量多可睡链路将其置于睡眠态，达到有效节能目的。本发明方法设计的节能路由策略属于集成型，即在修改OSPF协议基础上得到，同时选用SDN作为网络架构。

[0007] 本发明提供的基于SDN集中控制的骨干网能耗优化方法，将IP骨干网络抽象为无向加权图G(V,E,W)，V为网络中节点集合，E为网络中节点间链路集合，W为节点间链路上对应的权值。

[0008] 第一步，依据规则1～3获得无向图G中执行move机制的所有move过程；规则1：move 过程的入口节点和出口节点必须邻接；规则2：一个入口节点只能属于一个move过程；规则 3：如果一个节点成为一个move过程的出口节点，那么这个节点的最短路径树将不能再发生改变。

[0009] 一个move过程具有一个入口节点和一个出口节点，设入口节点vi、出口节点vj，运行 move机制，获得可睡链路；move机制实现过程为：首先，通过OSPF路由协议计算入口节点和出口节点的最短路径树spt(vi)、spt(vj)；然后，比较spt(vi)和spt(vj)获得入口节点的修改路径树mpt(vi)；最后，比较spt(vi)与mpt(vi)得到可睡链路。vi、vj分别为E中第i个、第 j个节点。

[0010] 第二步，确定第一步获得的所有move过程的兼容矩阵C；矩阵C中元素cij用于标识第i 个move过程movei和第j个move过程movej是否兼容，若二者兼容cij值为1，否则值为0。

[0011] 若movei被执行后，movej仍可以被执行，则movei和movej兼容；

[0012] 第三步，根据兼容矩阵C获得无向图H(M,F)；M表示第一步获得的所有move过程，每个move过程为一个节点，设共有K个move过程，K为正整数且K≤||E||，||E||表示E中链路总数；F表示move过程之间的兼容关系，用连接边来表示，两个move过程相连表示兼容，不相连表示不兼容；用 表示两个move过程之间不兼容，则得到H的补图

[0013] 将问题：在保证用户QoS的基础上，找出尽量多的可睡链路；抽象为如下满足背包条件最大团问题，表示如下：

[0014]

[0015] 其中，qi表示第i个move过程的可睡链路数量，xi表示第i个move过程是否执行，(i,j) 表示第i个move过程和第j个move过程不兼容，(MPT(i))min表示第i个move过程的修改路径树的链路权值和在可选的move过程中最小。

[0016] 第四步，求解所述的最大团问题，将获得的可睡链路置于睡眠态。

[0017] 所述的第二步中，判断movei和movej是否兼容的具体方法是：

[0018] (1)确定movei和movej的锁节点集；

[0019] 在一个move过程中，对于一个节点，如果至少有一条经过该节点的路径发生改变，则该节点为与该move过程相关锁节点；某move过程的锁节点集就是所有与该move过程相关锁节点的集合；

[0020] (2)当且仅当movei的出口节点不在movej的锁节点集，movej的出口节点不在movei的锁节点集中，则movei和movej兼容；否则，movei和movej不兼容。

[0021] 所述的第四步中求解最大团问题的实现步骤如下：

[0022] 步骤4.1，输入无向加权图G(V,E,W)，寻找运行初始节点im，节点im是所有网络节点中相邻链接点最多的节点；

[0023] 步骤4.2，以im为入口节点，找到所有以im为入口节点的move过程，从中选取修改路径树的链路权值和最小的move过程，作为第一个move过程放入到解集 中；

[0024] move过程的修改路径树是指该move过程的入口节点的修改路径树；

[0025] 步骤4.3，更新入口节点集合及出口节点集合；

[0026] 对于刚放入解集 的move过程，在入口节点集合中去除该move过程的入口节点及出口节点，在出口节点集合中，去除该move过程的入口节点、出口节点以及该move过程的锁节点集；入口节点集合和出口节点集合初始都包含无向图G中所有节点；

[0027] 步骤4.4，寻找所有与刚放入解集 的move过程兼容的move过程，从中选择修改路径树的链路权值和最小的move过程，放入解集

[0028] 步骤4.5，判断出口节点集合是否为空，若是，则输出解集 根据解集 获得可睡链路；若不为空，则转至步骤4.3继续执行。

[0029] 相对于现有技术，本发明的优点和积极效果在于：本发明的骨干网能耗优化方法主要针对IP骨干网，属于集成于OSPF路由协议中的IP层节能路由策略，策略运行时段为骨干网可预测平稳时段，充分考虑QoS(网络响应时间)。通过对现有方法加以改进，降低了计算复杂度，同时充分考虑了拆除链路所带来的网络拓扑的改变以及网络相应时间的增加，提出了相应的解决机制，在保证了服务质量的情况下运行本发明方法，网络响应时间比现有策略大大减小，网络拓扑的改变也比现有策略少，随着网络复杂度的提升，这种改进的优势会更加显著。

附图说明

[0030] 图1是现有基于OSPF提出的启发式算法流程示意图；

[0031] 图2是IP骨干网节能策略整体架构示意图；

[0032] 图3是本发明实施例所用的网络拓扑结构示意图；

[0033] 图4是本发明实施例中R1的最短路径树；

[0034] 图5是本发明实施例中R8的最短路径树；

[0035] 图6是本发明实施例中R8的修改路径树；

[0036] 图7是本发明实施例中R2的最短路径树；

[0037] 图8是本发明实施例中R3的最短路径树；

[0038] 图9是本发明实施例中R3的修改路径树；

[0039] 图10是本发明基于SDN集中控制的骨干网能耗优化方法的流程示意图。

具体实施方式

[0040] 下面将结合附图和实施例对本发明作进一步的详细说明。

[0041] 本发明方法采用SDN网络架构，IP骨干网整体架构如图2所示，分为应用层、控制层和数据层，IP骨干网的网络节点位于数据层。原网络节点中控制部分被分离出来，集中置于网络控制器中。本发明的SDN网络结构中，每个网络节点都和网络控制器连通，使得网络控制器可以方便及时地感知网络状态。该网络架构还可以通过网络控制器根据全网状态及时制定有效策略来控制整个骨干网络节点，方便节能路由策略部署。

[0042] 首先，将研究对象IP骨干网络抽象为无向加权图：G(V,E,W)。无向加权图G表示双向加权图。其中V表示网络节点集合，E表示网络拓扑中节点间链路集合，W表示链路上对应权值，为网络响应时间，其表达式如下：

[0043] V＝{vi,1≤i≤n}         (1)

[0044] E＝{ei,1≤i≤m}         (2)

[0045] W＝{w(ei),1≤i≤m}      (3)

[0046] 公式(1)中，n表示网络拓扑所有网络节点数量，vi表示第i个网络节点。其中m表示该网络拓扑所有可用链路数量，ei表示网络拓扑第i条可用链路，表示某两个节点之间直接有连接边相连。w(ei)表示第i条链路ei的权值，也就是第i条链路的网络响应时间。

[0047] IP骨干网采用OSPF路由协议，设OSPF路由协议中求得最短路径树集合SPT为：

[0048] SPT＝{spt(vi),1≤i≤n}         (4)

[0049] 其中，spt(vi)表示第i个网络节点对应的最短路径树。设网络中活动链路集合EA为：

[0050] EA＝SPT＝{spt(vi),1≤i≤n}         (5)

[0051] 本发明基于开放最短路径优先协议，将骨干网能耗优化问题抽象为图论中最大团问题，在节能的同时尽量少改变网络拓扑，从而减少由于执行节能策略造成的网络重计算所需时间，使得该策略实用性更强。

[0052] 下面集合图3所示的网络示例说明本发明的能耗优化方法。图3的示例中，包含11个节点R1-R11，节点间连接链路的权值如图中边上数字所示，为网络响应时间，单位是毫秒。

[0053] 首先，说明本发明所用到的出口机制——移除机制(move机制)。执行move机制的过程称为move过程，在确定出口节点及入口节点后，运行move机制，获得可睡链路。下面选择R1为出口节点，R8为入口节点作为例子说明move机制。

[0054] 第一步：通过OSPF路由协议计算节点R1及R8的最短路径树。通过spt(R1)得到R1最短路径树，如图4所示；通过spt(R8)得到R8最短路径树，如图5所示。

[0055] 第二步：通过比较spt(R1)与spt(R8)可以得到入口节点R8的修改路径树mpt(R8)，如图6 所示。

[0056] move机制在参考文件2(An OSPF-integrated routing strategy for QoS-aware energy saving in IP backbone networks；A.Cianfrani,Y.Eramo,M.Listanti,et aI.,IEEE Transactions on Network and Service Management,vol.9,no.3,pp.254-267,2009.)中记载，其中得到修改路径树的方法是：以入口节点(此处为R1)的最短路径树为基础，将入口节点与出口节点间的线路连接方向调换一下，即可得到出口节点(此处为R8)的修改路径树。

[0057] 比较spt(R8)与mpt(R8)可以得到可睡链路{(R7,R8)}。这个过程就是move(R8,R1)执行过程。

[0058] 执行move过程是在保证网络连通的前提下，获得尽可能多的可睡链路。这些可睡链路就是本发明方法中要找的可以转化到睡眠态的目标链路。MOVE为图G中所有可能执行move 过程的集合，以获得可睡链路，如下所示：

[0059] MOVE＝{move(vi,vj),1≤i≤n,1≤j≤n,i≠j}       (6)

[0060] 其中，一个move(vi,vj)为一个move过程，move(vi,vj)是将vi作为入口节点、vj作为出口节点，运行move机制以获得可睡链路esleep(move(vi,vj))；vj表示网络中第j个网络节点。设可睡链路集合为Esleep，可以表示为：

[0061] Esleep＝{esleep(move(vi,vj),1≤i≤n,1≤j≤n,i≠j)}         (7)[0062] 由(7)可知，Esleep是由图G中所有可能move执行过程中获得的所有可睡链路组成。本发明方法的节能策略就是在保证QoS(网络响应时间)基础上，找出一系列可以顺序执行move 过程，使得到的可睡眠链路数量最多。

[0063] 为使本发明的节能策略更加可行、符合实际，引用如下几个规则：

[0064] 规则1：对一个move(vi,vj),1≤i≤n,1≤j≤n,i≠j,vi∈V,vj∈V，入口节点和出口节点必须邻接，即vi和vj有邻接边直接相连。该规则是为了在move机制执行过程中，尽可能少改变网络拓扑。

[0065] 规则2：一个入口节点只能属于一个move过程。设置该规则的目的是：在该策略的执行过程中不可避免要导致路径改变，该规则可以保证策略执行中，路径改变但不会导致环路发生。

[0066] 规则3：如果一个节点成为一个move过程的出口节点，那么这个节点的最短路径树将不能再发生改变。设置该规则目的是保证一系列move过程执行完成后，网络拓扑无环，同时保证move过程之间的兼容性。

[0067] 下面为关于move过程相关的三个定义说明。

[0068] 定义1：锁节点。对于一个move(vi,vj),1≤i≤n,1≤j≤n,i≠j,vi∈V,vj∈V，在move(vi,vj) 执行过程中，对于一个节点，如果至少有一条经过该节点的路径发生改变，则该节点为与 move(vi,vj)相关锁节点。

[0069] vblock＝{vk,Esleep∈SPT(vk),vk∈V,vk≠vi,vk≠vj}      (8)

[0070] vblock表示锁节点，SPT(vk)表示节点vk的最短路径树，Esleep∈SPT(vk)表示在move过程中可睡链路存在于节点vk的最短路径树中。

[0071] 定义2：锁节点集。所有与move(vi,vj)相关锁节点表示为集合Bn(move(vi,vj))，如下：

[0072] Bn(move(vi,vj))＝{vblock,vblock∈V,block in[1,n]}    (9)

[0073] 定义3：move过程兼容性。假设有两个move过程，move1(vi,vj)与move2(vk,vl)，其中， vi∈V,vk∈V,vj∈V,vl∈V,1≤i≤n,1≤j≤n,1≤k≤n,1≤l≤n,i≠j≠k≠l；vi,vk为对应move过程的入口节点；vj,vl为对应move过程的出口节点。move1(vi,vj)、move2(vk,vl)分别可简写为move1、move2。

[0074] move1(vi,vj)与move2(vk,vl)兼容的直观定义为：在move1(vi,vj)被执行后，move2(vk,vl)仍可以被执行。对应数学表达式为：

[0075]

[0076] 由式(10)可知，move1(vi,vj)与move2(vk,vl)兼容，当且仅当move1(vi,vj)出口节点vj不在 move2(vk,vl)锁节点集Bn(move2(vk,vl))中；move2(vk,vl)出口节点vl不在move1(vi,vj)锁节点集 Bn(move1(vi,vj))中。由定义易知move1与move2兼容性具有对称性，即如果move1∝move2，那么move2∝move1。

[0077] 下面结合图3所示示例说明具体判断两个move兼容性方法。设move1为move(R8,R1)； move2为move(R3,R2)。首先，求出入口R3及出口R2最短路径树。通过spt(R2)得到出口R2 最短路径树，如图7所示。通过spt(R3)得到R3最短路径树，如图8所示。其次，通过比较 spt(R2)与spt(R3)可以得到入口R3的修改路径树mpt(R3)，如图9所示。

[0078] 对两个move过程进行比较，判断它们之间兼容性。

[0079] 首先，由Esleep定义可知:

[0080] Esleep(move1)＝Esleep(move(R8,R1))＝{(R8,R7)}       (11)

[0081] Esleep(move2)＝Esleep(move(R3,R2))＝{(R3,R11)}      (12)

[0082] 其次，由Bn定义可知：

[0083] Bn(move1)＝Bn(move(R8,R1))＝{R10}                   (13)

[0084]

[0085] 根据(13)、(14)及move定义易知：move1 出口R1 ∉Bn(move2) 同时，move2 出口根据move兼容性定义可知move1∝move2，move1与move2兼容。

[0086] 下面说明本发明提供的基于SDN集中控制的骨干网能耗优化方法。

[0087] 第一步，依据上面规则1～3，获得无向图G中执行move机制的所有可能的move过程。

[0088] 第二步，计算出无向图G(V,E,W)中所有可能move过程的兼容矩阵C，如下：

[0089] C＝{cij,1≤i≤L,1≤j≤L,L＝||E||,cij＝0if movei not∝movej,cij＝1if movei∝movej}   (15)

[0090] 公式(15)中，L表示网络中可用链路的数量，movei、movej分别表示第i个move过程、第j个move过程，cij用来标识movei和movej是否兼容，若二者兼容则cij值为1，否则值为 0。只有在极端条件下才有可能move过程数量和可用链路的数量相等，即通过move可以睡眠网络中的所有链路，L是个i、j可取的上限数字。

[0091] 根据上面定义，若movei被执行后，movej仍可以被执行，则movei和movej兼容。具体判断过程可以是：根据公式(8)和(9)的定义确定movei和movej的锁节点集；根据公式(10)的定义判断movei和movej是否兼容。当且仅当movei的出口节点不在movej的锁节点集，movej的出口节点不在movei的锁节点集中，则movei和movej兼容；否则，movei和movej不兼容。

[0092] 第三步，将本发明要解决的问题：在保证用户QoS的基础上，找出尽量多的可睡链路；抽象为一个满足背包条件最大团问题。

[0093] 在获得兼容矩阵C的基础上，可以得到一个无向图H：

[0094] H＝H(M,F)              (16)

[0095] 其中，M表示图G中第一步得到的所有可能move过程，设得到K个move过程，K为正整数，可取的最大值为L。F表示move过程之间的兼容关系，用连接边来表示。F根据矩阵C来获得，两个move过程相连表示兼容，不相连表示不兼容。通过图来将原来用数字表示的问题转化成为寻找最大团的问题。用 表示两个move过程之间不兼容。这样将会得到H 的补图[0096]

[0097] 如果考虑QoS(时延)，本发明方法要解决的问题被抽象为一个满足背包条件最大团问题，定义如下：

[0098]

[0099] 其中，i表示第i个move过程，qi表示第i个move过程能睡眠的链路数量，xi表示第i个 move过程是否执行，xj表示第j个move过程是否执行，(MPT(i))min表示第i个move过程的修改路径树的链路权值和在可选的move过程中最小。MPT(i)表示第i个move过程的修改路径树的链路权值和。(i,j)表示第i个节点和第j个在补图 中互联，第二行表示不兼容的两个 move过程无法同时执行。

[0100] 对于一个move过程，修改路径树MPT是指入口节点的修改路径树，出口节点的路径树并未改变，因此一个move过程的修改路径树是指该move过程中入口节点的修改路径树。

[0101] 第四步，求解所述的最大团问题，将获得的可睡链路置于睡眠态。

[0102] 本发明核心问题可由(20)直接解出。而该问题为最大团问题，同时也是一个NP-hard问题。而满足背包条件的最大团问题仍是一个NP-hard问题。因此最优解不能直接求得。本发明以此为理论依据，提供了如图10所示的方法求得该问题次优解。

[0103] 步骤4.1，输入无向加权图G(V,E,W)。寻找策略运行初始节点im，im是所有网络节点中，相邻链接点最多的节点。

[0104] 步骤4.2，以im为入口节点；找到所有可能的以im为入口节点的move过程。从中找到修改路径树的链路权值和最小的move过程作为第一个move过程，放入到解集 中。在初始情况中可能有很多个可以执行的move，为保证QoS，则选择MPT权值和最小的作为算法的起点。

[0105] 设刚放入解集 的move过程为当前move过程

[0106] 步骤4.3，更新入口节点集合及出口节点集合。对于刚放入解集 的move过程，在入口节点集合中去除该move过程的入口节点及出口节点。在出口节点集合中，去除该move过程的入口节点、出口节点以及该move过程的锁节点集。

[0107] 入口节点集合和出口节点集合初始都包含无向图G中所有节点。

[0108] 步骤4.4，找所有与刚放入解集 的move过程兼容的move过程。再从中选择修改路径树的链路权值和最小的move过程，放入解集

[0109] 步骤4.5，判断出口节点集合是否为空，若出口节点集合不为空，则跳转步骤4.3继续执行。若出口节点集合为空，则结束算法并输出解集

[0110] 根据所得到的解集 可获取可睡链路，从而进一步来设置网络路由，以达到节省网络能源的目的。