[0028] 下面根据附图详细说明本发明,本发明的目的和效果将变得更加明显。
[0029] 如图1、2所示,一种在OSPF(Open Shortest Path First开放式最短路径优先)协议中改进路由算法的网络级节能方法。通过将能耗因素加入到路由协议中,通过对OSPF协议中SPF算法的修改,使得路由器在执行Dijkstra算法时在产生的所有等价路径中选择能耗差最小的路由路径,在网络轻负载期间应用到大规模的网络时具有较为显著的节能效果。包括路由器在有无数据包经过时的能耗差,产生多条最短路径的改进Dijkstra算法。
[0030] 本发明解决其技术问题所采用的技术方案包括如下步骤:
[0031] 步骤1、在路由器中设置能耗因素值;能耗因素值用于记路由器的能耗,该能耗因素值Pm计算如下:
[0032] Pm(X)=Pt(X)-Pi(X)
[0033] 其中X代表路由器的型号,Pt有数据包经过时路由器的耗能,Pi为空闲状态的耗能。
[0034] 步骤2、通过对OSPF协议中SPF算法的修改,使得路由器在执行Dijkstra算法时产生的所有等价路径中选择能耗因素值总和最小的路由路径,具体修改如下:
[0035] 2-1.在优先队列类中定义一个代表能耗变量的能耗因素值Pm;
[0036] 2-2.在lsa头文件的Link类中添加变量l_fwdcst2,l_fwdcst2用于存储一条链路的forward cost2。
[0037] 2-3.初始化数据结构,清除候选列表,初始化最短路径树使其只包含树根;
[0038] 2-4.设V为新加入最短路径树的节点,扫描该初始节点V的所有邻居节点,并依次将扫描到的邻居节点W加入候选列表;
[0039] 2-5.判断邻居节点W是否在最短路径树上,如果邻居节点W的标记状态显示在最短路径树上,则检查该邻居节点W的下一个链接并计算链路代价总和值new_cost=V→cost0+tlp→l_fwdcst;节点能耗总值new_cost2=V→cost2+tlp→l_fwdcst2;
[0040] 2-6.若邻居节点W在最短路径树上,则继续判断该邻居节点W是否在候选列表中;
[0041] 2-6-1.若邻居节点W的标记状态显示在候选列表中,则判断所得的new_cost是否大于候选列表中该邻居节点W的链路代价值cost0,如果new_cost大于cost0,则继续检查该邻居节点W的下一个链接;如果new_cost小于cost0,则在候选列表中删除该邻居节点W;如果new_cost等于cost0,则判断到邻居节点W为止的节点能耗总值new_cost2是否小于该邻居节点W本身已有的节点能耗值cost2。如果new_cost2大于cost2,则直接使用所宣告的链接计算下一跳。如果new_cost2小于cost2,则对new_cost和new_cost2重新赋值,具体如下:new_cost=W→cost0,new_cost2=W→cost2。
[0042] 其中,V→cost0表示初始节点V的链路代价值,tlp→l_fwdcst表示邻居节点W的下一个链接的代价;V→cost2表示初始节点V的能耗值,l_fwdcst2表示邻居节点W的能耗值;W→cost0表示邻居节点W的链路代价值,W→cost2表示邻居节点W的能耗值;
[0043] 2-6-2.若该邻居节点W不在候选列表中,或new_cost小于W→cost0时,将W加入候选列表,使用所宣告的链接计算下一跳,并以此设定邻居节点W的下一跳值。
[0044] 2-7.如果候选列表为空,表明最短路径树就被构建完成,结束本次最短路径树构建。否则,在候选列表中选择最靠近树根的节点,将其加入最短路径树,同时在候选列表中删除该节点;
[0045] 2-8.递归调用步骤2-4~步骤2-6。
[0046] 如图1所示,本发明使用OSPF绿色路由器,且将路由器接口信息进行修改,接口将设置一个路由器能耗的参数(power margin of router),控制层面将使用改进的节能Dijkstra算法进行路由选择。
[0047] 如图2(a)-2(c)所示,选择路由器总能耗差最小的最短路径:在多条最短路径中选取最小总路由器能耗差的路径。如图2(c)所示,其中虚线路径为总能耗差最小的。