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

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

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

图 1

Fig. 1

图 1 人工鱼觅食的路线图Fig. 1 Route map of artificial fish

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

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

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

图 2

Fig. 2

图 2 光路由域中网关节点和域内节点Fig. 2 Gateway nodes and interior nodes in the routing domain

图 3

Fig. 3

图 3 人工鱼群算法流程图Fig. 3 Flow chart of AFSA

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

表 1(Table 1)

表 1 原始数据 Tab. 1 The original data 组名 业务量/Erlang 1 2 3 4 5 6 7 第一组 150 210 200 100 270 170 110 第二组 90 150 110 120 180 200 270

表 1 原始数据 Tab. 1 The original data

表 2(Table 2)

表 2 业务量概率 Tab. 2 The probability of traffic 组名 业务量/Erlang 1 2 3 4 5 6 7 第一组 0.124 0.174 0.165 0.083 0.223 0.141 0.091 第二组 0.08 0.134 0.098 0.107 0.16 0.178 0.241

表 2 业务量概率 Tab. 2 The probability of traffic

本次实验进行了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)显示出节约能耗的比例也大有不同,相较于之前的限定值,第二次实验的效果更突出,节能效果更为明显。由此可知,此种方法可达到预期节能效果,且根据需要可进行算法中参数的改变,具有灵活性。

图 4

Fig. 4

图 4 最优解Fig. 4 The best answer

图 5

Fig. 5

图 5 能耗对比图Fig. 5 The contrast of energy consumption

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