光网络中基于人工鱼群算法的节点休眠技术

刘祥楼　王东雪　赵冬岩等

摘要：鉴于人工鱼群算法（AFSA）具有收敛速度快，易于寻址寻优等特点，在光网络节点休眠技术中引入人工鱼群算法。以光路由域中的网关节点作为研究对象，选用业务量作为搜索函数，执行算法中的各种寻址行为找到最优解，休眠不符合条件的节点，并根据传输的繁忙与空闲状态转换限定值，从而节约传输过程中的能耗。通过2组7个节点进行计算机仿真，并分别设定最大值的40%和50%为限定值，得到原始能耗与后期能耗的对比结果。由此可知，当限定值为最大值的40%时，2组数据均节能14%，当限定值为最大值50%时，能耗节约比例分别为28%和42%。证明该方法可有效节能。

关键词：网关节点； 业务量； 人工鱼群算法； 休眠

中图分类号： TN 929.14 文献标志码： A doi： 10.3969/j.issn.1005-5630.2015.01.005

Abstract：Because of many characteristics of artificial fish swarm algorithm （AFSA） such as easy implementation， rapid convergence， addressing and optimizing， we use AFSA in the optical network of the node hibernation technology for the first time in order to save the routing energy. We let the gateway node to be the research object， choose traffic load to be the search function， conduct the addressing behavior to find the best solution， and then make the node that do not match the solution hibernate so that energy saving can be achieved. This method can change the limitation between busy and free， which saves the energy with transmission ongoing. Simulation of two groups with seven nodes is carried out. We set 40% and 50% of the maximum as the limitation. To compare the energy with and without using the algorithm， we find that when the limitation is 40% of the maximum， the both groups save 14% energy， and when the limitation is 50% of the maximum， 28% and 41% energy is saved. It proves that the method can save energy efficiently.

Keywords：gateway node； traffic load； AFSA； hibernation

引 言

随着网络的发展，光网络的应用也越来越广泛，随之而来的能耗问题也日渐凸显，由于能耗的大量浪费导致的经济压力也在日益增大。所以，近来国内外已开始针对光网络节能问题进行研究[1]并初见成效，其中改进路由协议[2]，改变网络权值[3]，改善网络节点覆盖[4]，进行网络路径规划[5]等都是网络节能的热门方法。路由节能研究中的遗传算法、蚁群算法[6]、粒子群算法[7]等都是本领域的经典算法且应用领域日益广泛[8]。蚁群算法虽然运行简单，但是算法求解过程开销过大；遗传算法虽然能准确解决问题，但是编程复杂，其解码过程相对耗时费力；粒子群算法虽然求解简单且运算快但容易陷入局部最优解。蚁群算法和遗传算法的研究已经进入瓶颈阶段，突破性不大。鉴于人工鱼群算法在电力系统及运输系统优化中体现出运行简单、快速、准确等优点，本文将它独特的寻址寻优特性运用在节点休眠技术中，目的是改善网络节点的业务量负载，在网络工作状态下快速且准确地找到空闲的节点进行休眠，从而省去该节点的能耗，继而达到网络节能的效果。

1 光网络节能技术机理

1.1 节点休眠机理

网络节点处于休眠状态时保留正常工作时的数据，只是关闭了其中的显示设备和耗电的程序，从而达到节能效果。当网络节点需要工作而重新启动时，能快速进入工作状态，这是一种介于开启与关闭的中间状态。在网络中引入休眠状态，可以有以下四种方法：一是在网络设备中设置两种状态，复苏状态和休眠状态。设备在闲置时进入休眠状态，从而降低能耗。二是在网络层面，当网内业务负载较低时，使业务路由汇聚在少数的设备上，从而降低能耗。三是在网络协议层面，对因特网协议进行适当的修改，在业务量大的时候调用设备，在业务量相应少的时候使设备进行休眠，从而减少能耗。四是在网络路由层面，当传输数据量变少时，休眠承载业务量少的节点，从而达到节能效果，而本文采用的是此种方法。

1.2 人工鱼群算法机理

在一片水域中，鱼往往能自行或尾随其他鱼，找到营养物质多的地方，因而鱼生存数目最多的地方一般就是本水域中营养物质最多的地方。人工鱼群算法就是根据这一特点，通过构造人工鱼来模仿鱼群的觅食、聚群、追尾及随机行为，从而实现寻优。人工鱼觅食的路线如图1所示，图中X为一条人工鱼的位置，它的视野范围为V（V为图1大圆以内区域），Xa、Xb表示为视野范围内两条鱼的位置，位置Xv为X在某时刻视点所在的位置，如果该位置的食物浓度高于当前位置则考虑向前进一步，即为Xnext；若食物的浓度不及当前位置，则继续巡视视野内其他位置。巡视的次数越多，则对视野内的状态越了解，则对周围的环境有个立体的认知，有助于做出相应的判断与决策。而对于状态多或无限状态的环境，也不必全部遍历，允许一定的不确定性对于摆脱局部最优寻找全局最优是有帮助的。在图1中，位置X=（x1，x2，…，xn），位置Xv=（xv1，xv2，…，xvn），则该过程表示如下：

式中，r是[-1，1]区间的随机数，S为移动步长。由于环境中同伴的数目是有限的，因此在视野中感知同伴的位置，并相应地调整自身位置的方法与上式相似。假设在一个n维的目标搜索空间中，有N条组成一个群体的人工鱼，人工鱼个体的状态可表示为向量X=（x1，x2，…，xn），其中xi（i=1，2，…，n）为欲寻优的变量；人工鱼当前所在位置的食物浓度表示为Y=f（X），其中Y为目标函数；S为人工鱼移动步长。

鱼群行为可描述为四种：一是随机行为，即鱼在水中游动基本上是随机的，当发现食物时，会向食物逐渐增多的方向快速移动。二是觅食行为，即生物的一种最基本的行为，鱼趋向食物的一种活动，人工鱼Xi在其视野内随机选择一个状态Xj，分别计算它们的目标函数值进行比较，如果发现Yj大于Yi，则Xi向Xj的方向移动；否则，Xi继续在其视野内选择状态Xj，判断是否满足前进条件，反复尝试T次后，仍没有满足前进条件，则随机移动一步使Xi到达一个新的状态。三是聚群行为，即一种鱼类常见的现象，这是它们在进化过程中形成的生存模式，为了集体觅食和躲避敌害。四是追尾行为，即当鱼群中的一条鱼或几条鱼发现食物时，它们附近的鱼会尾随其后迅速游过去，进而导致更远的鱼也尾随过来。以上是鱼的四种典型行为，这些行为在不同时刻会相互转换，而转换一般是鱼通过对周围环境的认知来实现的。在解决优化问题时，可以选择最优的行为执行，也就是在当前状态下，哪种行为会达到最优的状态；也可以选择较优的行为，就是任选一种状态，只要朝向最优的状态即可。两种选择最后都会寻找到最优的结果。

1.3 网络节能机理

虽然人工鱼群算法可应用在网络传输中，但目前还没有节能上的应用，结合该算法寻址寻优的特性，在此选用这种算法进行光网节能。在光网络层面，业务量能直接显示出节点的利用率[9]，承载高业务量的节点在传输过程中起着较大的作用，而同一时段某些节点则承载着较少的业务量，且能根据时间段进行多次监测。在不同的时间段内，节点承载的业务量不同，则拟定业务量为搜索函数，选择业务量少的节点作为休眠的对象，能直接解决路由传输过程中的能耗问题，针对性强且具有灵活性。

根据研究，节点分为网关节点和域内节点。光路由域中网关节点和域内节点的分布如图2所示，网关节点的能耗远大于域内节点的能耗值，则在人工鱼群算法中只对网关节点进行计算。所以设定每个网关节点为一个个体，而每个包括节点的路由域为种群，此种算法就是针对种群中的个体进行筛选。人工鱼群算法的流程如图3所示，初始化鱼群时，需要确定算法中需要的参数，种群规模N，即在变量可行域内随机生成N个个体，设定人工鱼的可视域V，步长S，拥挤度因子δ，尝试次数T，且在给定的范围内随机产生数组代表人工鱼。本算法是要得到大于限定值的个体，则当鱼群得到新个体时，与限定值进行对比，若符合条件，则向着该个体前进，直至出现最优解，否则进行下一次寻找。最后当最优解达到满意度，算法结束。若想得到最优解的集合，则在执行算法后，可将最优解剔除，重新进行运算，再次得到最优解，多次执行后可得最优解集合。

2 实验仿真

人工鱼群算法是根据业务量的大小来决定休眠的节点，所以节点的业务量是重点。本文引用文献[10]中的数据，在其网络节点拓扑结果中取出2组数据进行仿真实验，每组数据各选取连续的7个节点，并对此数据进行业务量概率转换，具体数据参见表1和表2。表1为本次实验选取的2组实验数据，表2为进行业务量概率转换后的数据。从中可以看出在进行路由传输时，节点所带的业务量是不同的，而本文则利用这种不同选择了此种休眠技术。

本次实验进行了2次限定值的选取，当选取限定值为最大值的40%时，2组数据均有1个节点不符合限定值要求，则分别休眠该节点，参见图4（a）。由此可得到休眠后的能耗与原始能耗对比如图5（a）所示，从图中看出，进行休眠技术后的路由能耗少于原始能耗，比例均在14%左右。因为选的限定值不同则休眠节点的个数不同，此限定值可选择在传输较为繁忙的时候，大部分的节点进行工作，只有少数的节点休眠，不仅不影响传输速率也能节约传输过程中的能耗。图4（b）所示为限定条件定为最大值的50%，从图中可看出，在此限定条件下，数据1有2个节点不符合条件，而数据2则有3个节点，当对这些节点进行休眠处理后，得到的能耗对比如图5（b）所示。从图中可看出，数据1和数据2的能耗大幅度下降，数据1的能

耗相对于原始能耗下降28%左右，而数据2则下降42%左右。此限定值可选在传输较为空闲时，即使休眠的节点增多，但是总传输量少，所以也不会影响传输速率仍可保持传输流通畅。对比图4（a）、（b）可看出当限定值改变时选定的休眠节点个数不同，图5（a）、（b）显示出节约能耗的比例也大有不同，相较于之前的限定值，第二次实验的效果更突出，节能效果更为明显。由此可知，此种方法可达到预期节能效果，且根据需要可进行算法中参数的改变，具有灵活性。

3 结 论

人工鱼群算法是源于鱼的生物特性而研发出来的，具有可靠性。该方法相对原始的迭代方法而言，简单易行且可达到路由节能效果。本文实验选择节点较少，得到的效果相对明显。当该项技术应用到整个光网络中，由于节点数量大增，预期休眠效果或许不会如此凸显，但一定能够实现相对应的节能效果。实验表明：选取不同的限定值，节约的能耗会有所不同，在实际应用过程中，保证传输速率的前提下，可通过改变限定值，保证最大限度的节约能耗。在网络应用日益广泛的今天，本文提出的节能算法对光网节能有一定的参考价值。

参考文献：

[1] 秦建兵，王坤，周骏华.EPON网络中OAM子层的扩展[J].光学仪器，2005，27（5）：43-46.

[2] 任秀丽，梁宏伟，汪宇.基于多路径蚁群算法的无线传感器网络的路由[J].计算机科学，2009，36（4）：116-118.

[3] 姚明海.改进的遗传算法在优化BP网络权值中的应用[J].计算机工程与应用，2013，49（24）：49-54.

[4] 彭丽英.改进的蚁群算法网络节点覆盖优化研究[J].计算机仿真，2011，28（9）：251-255.

[5] 王沛栋.改进蚁群算法及在路径规划问题中的应用研究[D].青岛：中国海洋大学，2012：14-90.

[6] SHI L，YANG S P.Research and application of an improved ant colony algorithm[J].Applied Mechanics and Materials，2014，543：1864-1867.

[7] 谭德坤，王冠.基于反向学习粒子群算法的无线传感器网络路由优化[J].计算机测量与控制，2013，21（10）：2885-2887.

[8] 常欢，吕丽军，刘鑫，等.混入逃逸函数的遗传算法优化超大视场光学系统[J].光学仪器，2013，35（4）：27-33.

[9] 张力方.基于GMPLS的多层多域智能光网络若干关键技术研究[D].北京：北京邮电大学，2012：46-55.

[10] 任鹏.WDM光网络业务量疏导的鲁棒规划算法研究[D].成都：电子科技大学，2007：19-30.

（编辑：刘铁英）