一种基于Q学习的用于软件定义网络的路径选择方法

技术领域

本发明涉及一种通信技术领域，尤其涉及一种基于Q学习的用于软件定义网络的路径选择方法，它可以在已有虚拟网的基础上，发现最适合的服务路径满足服务请求。

背景技术

近年来，人们对网络中所获取的信息类型要求多元化，对网络中获取的信息质量和信息安全的需求也不断提高。各种网络中承载的信息量急剧膨胀，网络规模不断地扩大，接入到网络中的用户、应用和业务越来越多。网络的建设、扩展、优化以及安全等工作成为网络建设和维护的重要内容。然而，面对这些复杂多变的需求，原有的互联网架构愈来愈显得捉襟见肘，难以适应。在这种背景下，软件定义网络(software defined network，SDN)应运而生。软件定义网络是一种新型网络创新架构，通过将网络设备控制面与数据面分离开来，从而实现了网络流量的灵活控制，为核心网络及应用的创新提供了良好的平台。

软件定义网络由软件控制和硬件数据通道组成。软件控制包括管理以及路由协议等。软件定义网络提出了控制层面的抽象，它将网络中所有的网络设备视为被管理的资源，在抽象底层网络设备具体细节的同时为上层应用提供了统一的管理视图和编程接口。这样，用户能自行定义和设计智能化程度和复杂度较高算法来控制网络工作，定制开发各种应用程序，通过软件定义逻辑上的网络拓扑，以满足对网络资源的不同需求，而无需关心底层网络的物理拓扑结构，为网络设计规划与管理提供灵活和便利。

众所周知，选择适合的网络路径，可减少对网络资源的耗费，快速的完成网络服务。在网络中，如何选择最佳路径对整个网络服务的系统而言是非常重要的；而另一方面，两个主要的原因使得在软件定义网络中寻找路径也非易事：首先，软件定义网络中的服务请求与网络节点并不一一对应，因此在寻找路径的同时还需要将服务映射到网络节点；其次，网络中的设备和路径有可能是未知的，也有可能会发生动态变化。所以针对软件定义网络的特点，本技术领域的技术人员需要一种新的适于软件定义网络的网络路径选择方法，寻找资源耗费少，路径短的网络路径。

作为一种具有较高通用性的机器学习框架，强化学习得到了较为广泛的研究和应用。在强化学习框架中，用户给出问题的目标，智能体控制器(agent)选择某一个动作，实现与环境的交互，获得环境给出的奖赏作为强化信号，智能体控制器(agent)根据强化信号和环境当前状态再选择下一个动作，直到终止。智能体控制器(agent)的目标是在每个状态发现最优策略以使期望的奖赏之和最大。Q学习是强化学习的一种经典的算法，具有能感知环境的自治智能体控制器(agent)，可以通过不断地与环境交互进行动态学习，选择能达到其目标的最优动作，不必事先了解所要解决问题的所有细节，可以做到“边学边做，边做边学”。因此，Q学习适合解决带有动态性和未知性的网络路由选择问题。

发明内容

本发明目的是：一种基于Q学习的用于软件定义网络的路径选择方法，利用该方法，寻找路径短，消耗时间少，占有带宽资源少，适用于动态、复杂网络的网络路径，该路径能够在较少耗费资源的情况下，快速的完成网络服务，能适应网络的动态变化，而且尽量不影响虚拟网络完成其他服务请求。

本发明的技术方案是：一种基于Q学习的用于软件定义网络的路径选择方法，由软件定义网络基础设施层接收服务请求，软件定义网络控制器根据所需服务组件及组合方式构建虚拟网络，并分配适合的网络路径完成服务请求，最终达到终端，所述适合的网络路径通过强化学习中的Q学习方式获取，其方法步骤为：

⑴在已构建的虚拟网络上设定若干个服务节点P，对应每一个服务节点分配有相应的带宽资源B；

⑵将接收到的服务请求分列为可采取的动作a，根据ε-贪心(ε-greedy)策略尝试选择每一条可以到达终端的路径，即将每一个动作a经过相应的服务节点P后完成服务请求；

⑶上述每一次尝试均记录下来，并且记录相应的消耗时间，以及执行完成动作a后，每一服务节点P上的剩余带宽资源B，汇总为Q值表，同时该Q值表内的数据将被每一次的尝试数据所更新；

⑷根据Q值表中的记录数据，找出路径短，消耗时间少，占用带宽资源少的路径，即为适合的路径。

上文中，ε-贪心(ε-greedy)策略是强化学习算法中经常使用的一种策略，ε-贪心策略：随机选择一个实数ε(0<ε<1)作为探索因子，计算得到所有可行动作的个数m，每次以概率ε/m在当前可行动作集中随机选择一个动作，否则，以概率1-ε选择，到当前为止情况下，Q值表中最大的Q值所对应动作；根据这一方法，选择路径尝试，尽快找到适合的路径，即路径短，消耗时间少，占用带宽资源少的路径。由于采用了探索因子ε，因此可以增加新的尝试和探索，弥补了贪心策略在探索能力上的不足；同时因为ε值较小，选择其他动作的概率较小，选择Q值最大对应的最优动作的概率最大，因此ε-贪心(ε-greedy)策略能保证不会由于增加了探索而对最优动作的发现有太大的负面影响。

上述技术方案中，所述步骤⑶中，在Q值表中设置一立即奖赏参数r，当执行动作a消耗时间及占用的带宽资源B越少，为立即奖赏参数r加入奖励值，相反则为立即奖赏参数r减去惩罚值，根据立即奖赏参数r的数值大小，帮助ε-贪心(ε-greedy)策略选择最有可能成为适合的路径进行尝试。加入立即奖赏参数r，与ε-贪心(ε-greedy)策略相结合，通过立即奖赏按照折扣方式累加，获得累计奖赏Q值，最大化累计奖赏Q值，使得Q值表中的数据变化更为明显，突出适合的路径的优势，易于选出。

进一步的是，所述当执行转发任务，立即奖赏参数r＝带宽资源请求-带宽资源+计算资源请求-计算资源-服务点间的路径×路径长短的权重n，当无执行任务时，r＝计算资源请求。当执行服务路径倒数第二步时，如果动作a的下一个执行点是某一服务节点P而非终端时，r＝r-X；否则，如果动作a的下一个执行点是终端时，r＝r+X。X:任意取一数值，奖惩是否完成目标。

上述技术方案中，所述ε-贪心(ε-greedy)策略在与Q值表参数结合选择路径时，随机选择一个实数ε(0<ε<1)作为探索因子，计算得到所有可行动作的个数m，然后以ε/m的概率等概率地在可行动作集合中随机选择一个可行动作，或者以1-ε的概率选择，到当前为止情况下，Q值表中最大的Q值所对应的动作；所述可行动作为：网络可以满足的动作，包括带宽可以满足转发请求，计算资源可以满足处理请求；即带宽资源请求<带宽资源，计算资源请求<计算资源。

进一步的技术方案是，所述路径长短的权重n是确定路径长短与资源耗费之间相对于立即奖赏参数r重要性的系数，当路径长短对整个立即奖赏参数r更为重要时，权重n值较大，相反则较小。

上述技术方案中，所述步骤⑷中根据Q值表中数据对路径的选择方式：本次Q值表与上一次Q值表数据相比较，如果相差很小，则认为Q值表中所有的Q值收敛，选择最大Q值对应的具体动作a，选定该动作a对应的网络转发路径以及服务与路径的映射关系，即为所述适合的路径；否则，继续根据ε-贪心(ε-greedy)策略尝试选择每一条可以到达终端的路径。

上文中，所述本次Q值表与上一次Q值表数据相比较，变化不大，是指将本次Q值表中的每一个Q值与上一次Q值表对应的Q值相减，如果相减得到的差的绝对值均小于某个预先设定的，很小的阈值，则认为Q值表中所有的Q值收敛，根据最大Q选择相应的具体动作a，选定该动作a对应的网络转发路径以及服务与路径的映射关系，即为所述适合的路径；否则，继续将接收到的服务请求分列为可采取的动作a，根据ε-贪心(ε-greedy)策略尝试选择每一条可以到达终端的路径，即将每一个动作a经过相应的服务节点P后完成服务请求。

由于上述技术方案运用，本发明与现有技术相比具有下列优点：

1.本发明基于ε-贪心(ε-greedy)策略，尝试去发现每一条路径，记录每一次选择执行后虚拟网络中服务节点的资源消耗，以及时间消耗等参数值，建立Q值表，作为下一次ε-贪心(ε-greedy)策略选择路径的参考，从而可以发现一条转发路径短(消耗时间少)，资源耗费少(带宽占用少)的路径(即适合的路径)，这就能够使得虚拟网络在不调整的情况下，能适应网络的动态变化，同时尽可能多的满足其他服务请求。

2.增加立即奖赏r参数，与强化学习中的Q学习能够累计奖赏最大的特性结合，最快找出资源耗费少，路径短的网络路径，该路径能够在较少耗费资源的情况下，快速的完成网络服务，而且尽量不影响虚拟网络完成其他服务请求。

3.由于在Q学习方法基础上采用ε-贪心(ε-greedy)策略，引入了探索因子ε，可以增加新的尝试和探索，弥补了贪心策略在探索能力上的不足；同时因为ε值较小，选择其他动作的概率较小，选择Q值最大对应的最优动作的概率最大，因此ε-贪心(ε-greedy)策略能保证不会由于增加了探索而对最优动作的发现有太大的负面影响。

附图说明

图1是本发明实施例一中的布局示意图；

图2是本发明实施例一软件定义网络服务部署图。

具体实施方式

下面结合附图及实施例对本发明作进一步描述：

实施例一：参见图1、2所示，一种基于Q学习的用于软件定义网络的路径选择方法，由软件定义网络基础设施层接收服务请求，软件定义网络控制器根据所需服务组件及组合方式构建虚拟网络，并分配适合的网络路径完成服务请求，最终达到终端，所述适合的网络路径通过强化学习中的Q学习方式获取，其方法步骤为：

⑴在已构建的虚拟网络上设定若干个服务节点P，对应每一个服务节点分配有相应的带宽资源B；

⑵将接收到的服务请求分列为可采取的动作a，根据ε-贪心(ε-greedy)策略尝试选择每一条可以到达终端的路径，即将每一个动作a经过相应的服务节点P后完成服务请求；

⑶上述每一次尝试均记录下来，并且记录相应的消耗时间，以及执行完成动作a后，每一服务节点P上的剩余带宽资源B，汇总为Q值表，同时该Q值表内的数据将被每一次的尝试数据所更新；

⑷根据Q值表中的记录数据，找出路径短，消耗时间少，占用带宽资源少的路径，即为适合的路径。

所述步骤⑶中，在Q值表中设置一立即奖赏参数r，当执行动作a消耗时间及占用的带宽资源B越少，为立即奖赏参数r加入奖励值，相反则为立即奖赏参数r减去惩罚值，根据立即奖赏参数r的数值大小，帮助ε-贪心(ε-greedy)策略选择最有可能成为适合的路径进行尝试。

所述立即奖赏参数r＝带宽资源请求-带宽资源+计算资源请求-计算资源-服务点间的路径×路径长短的权重n，当无执行任务时，r＝计算资源请求；当在计划用时时间内，动作a的下一个执行点是某一服务节点P而非终端时，r＝r-1000；否则r＝r+1000。

所述ε-贪心(ε-greedy)策略在与Q值表参数结合选择路径时，随机选择一个实数ε(0<ε<1)作为探索因子，计算得到所有可行动作的个数m，然后以ε/m的概率等概率地在可行动作集合中选择一个可行动作，或者以1-ε的概率选择，到当前为止情况下，Q值表中最大的Q值所对应的动作；所述可行动作为：网络可以满足的动作，包括带宽可以满足转发请求，计算资源可以满足处理请求；即带宽资源请求<带宽资源，计算资源请求<计算资源。

所述路径长短的权重n是确定路径长短与资源耗费之间相对于立即奖赏参数r重要性的系数，当路径长短对整个立即奖赏参数r更为重要时，权重n值较大，相反则较小。

所述步骤⑷中根据Q值表中数据对路径的选择方式：本次Q值表与上一次Q值表数据相比较，如果相差很小，则认为Q值表中所有的Q值收敛，根据最大Q选择相应的具体动作a，选定该动作a对应的网络转发路径以及服务与路径的映射关系，即为所述适合的路径；否则，继续根据ε-贪心(ε-greedy)策略尝试选择每一条可以到达终端的路径。

参见图1所示，具体的方法步骤如下：

(1)初始化Q值表中的Q值(用Q(s,a)标识，表示s状态下，采用a动作的Q值)，学习步长α，折扣因子γ，探索因子ε，跳数权重n，变化阈值ξ；(s：服务节点状态，a：动作，执行的操作。)

⑵初始化状态s等于Ps，t←0，Q1(s,a)←Q(s,a)；(原终端表示服务请求的发起点)

⑶选择动作a，根据Q值表以及ε-贪心(ε-greedy)策略；

⑷执行动作a，得到立即奖赏。当转发数据，且下一个执行点是某一服务节点而非终端时，r←C(vP_i)-C(P_j)+B(vP_i-1,vP_i)-B(P_j-1,P_j)-L(P_j-1,P_j)×n-1000；当转发数据，且下一个执行点是终端时，r←C(vP_i)-C(P_j)+B(vP_i-1,vP_i)-B(P_j-1,P_j)-L(P_j-1,P_j)×n+1000；当不转发数据，且下一个执行点是某一服务节点而非终端时，r←C(vP_i)-1000；当不转发数据，且下一个执行点是终端时，r←C(vP_i)+1000；

⑸更新Q(s,a)←Q(s,a)+α[r+γmax_a′Q(s′,a′)-Q(s,a)]；max_a′Q(s′,a′)是采取了动作a′，得到的所有可能的状态s′，选择其中Q(s′，a′)最大的那个Q值；

⑹s←s'，t←t+1,下个状态s′，当s不是服务终端Pd，并且t小于虚拟服务路径长度k时，转步骤(3)；

⑺当Q值表中所有的Q1(s,a)-Q(s,a)的绝对值均小于ξ时，转向步骤(8)；否则，转向步骤(2)。

(8)返回Q值表中最大的Q值对应的动作。

状态s表示数据包所处虚拟网络节点如图1中的Ps，Pb，Pd等，动作a表示数据包根据服务请求可以采取的动作，比如在已完成服务请求vP1的情况下，数据包在节点Pb处可以采取向其他节点传输数据，也可以在Pb处完成下一个计算请求vP2。这样强化学习中的Q学习方法就可以发现一个好的服务路线，同时发现一个好的服务请求到虚拟网络的映射。

步骤(3)中，计算得到所有可行动作的个数m，然后在探索因子ε(0<ε<1)下以ε/m的概率等概率地在可行动作集合中选择一个可行动作(可行动作：网络可以满足的动作，如带宽可以满足转发请求，计算资源可以满足处理请求；即带宽请求B(vP_i-1,vP_i)<带宽资源B(P_j-1,P_j)，计算资源请求C(vP_i)<计算资源C(P_j))，或者以1-ε的概率选择最大的Q值所对应的动作。

步骤(4)中，当采取向其他服务节点转发数据的动作时，立即奖赏r＝带宽请求B(vP_i-1,vP_i)-带宽资源B(P_j-1,P_j)+计算资源请求C(vP_i)-计算资源C(P_j)-两个服务节点之间通信在物理层网路中转发的跳数L(P_j-1,P_j)×n(其中n表示路径长短的权重，这样可以在资源耗费和转发时间上做一个权衡，服务vP_i映射到节点P_j)；当不转发数据计算数据时，r＝计算资源请求C(vP_i)；当转发数据，且下一个执行点是某一服务节点而非终端时，r←C(vP_i)-C(P_j)+B(vP_i-1,vP_i)-B(P_j-1,P_j)-L(P_j-1,P_j)×n-1000；当转发数据，且下一个执行点是终端时，r←C(vP_i)-C(P_j)+B(vP_i-1,vP_i)-B(P_j-1,P_j)-L(P_j-1,P_j)×n+1000；当不转发数据，且下一个执行点是某一服务节点而非终端时，r←C(vP_i)-1000；当不转发数据，且下一个执行点是终端时，r←C(vP_i)+1000。强化学习中的Q学习的目标是最大化累计奖赏r，这样强化学习中的Q学习找到路径短的，耗费资源少的服务路径。

步骤(5)中，Q值表示长期的累计奖赏，当它很大时，说明在状态s的时候应该采取a动作，并且该动作可以使得服务路径可以很短，而且耗费更少地资源。

步骤(7)中，将这一轮Q值表格中的Q值与上一轮Q值表中的Q值相比，当变化不大时，说明Q值收敛，这样我们就可以根据最大Q值选着具体的动作a，这也就确定了网络转发路径以及服务与路径的映射关系。