本发明公开了一种基于强化学习的命名数据网络拥塞控制方法，属于网络信息传输通信技术领域。本方法从转发策略的角度出发，通过将路由节点转发兴趣包的过程映射为马尔可夫决策过程，以最小响应时间为目标，在考虑NDN中的网内缓存、多路径转发，并不对链路容量或数据包大小做任何假设的情况下，采用强化学习的方法求解最优策略。强化学习求解方法中，具体采用结合资格迹的Sarsa算法——Sarsa(λ)算法，以获得理论上良好的算法性能。本方法通过动态转发策略智能地选择转发端口，尽量避免向拥塞链路发送流量，以主动规避和缓解拥塞。
1.一种基于强化学习的命名数据网络拥塞控制方法，其特征在于，包括以下步骤：步骤1：对命名数据网络NDN建立强化学习模型，所述模型建立方法如下：
步骤1-1利用NDN中路由节点的学习和计算能力，将路由节点看作智能体agent；
步骤1-2将路由节点向不同的端口转发兴趣包的过程作为agent选择执行动作的过程，多个可转发的端口对应多个可执行的动作；
步骤1-3将兴趣包从一个路由节点通过选择端口转发到另一个路由节点的过程映射为agent将兴趣包从一个状态通过选择相应的动作转移到另一个状态的过程；
步骤1-4每个路由节点选择一个端口转发兴趣包后，将兴趣包传输到下一个路由节点的时间映射为环境反馈给agent的立即回报值r(s,a)，该时间通过相应的数据包返回时携带的时间戳信息计算得到；时间戳通过向数据包的结构中添加新的字段项以实现携带，记录的是数据包离开上一个节点的时间；此外，数据包还负责携带上游路由节点下一个状态的Q值返回，以完成当前状态的值函数更新；更新后的数据包，路由节点的FIB表中每一个前缀对应一个条目，条目中的每一个端口都有一个度量条目，能够存储标准化的度量信息；将Q值加入原有的度量条目中，数据包携带的以及更新的都为此Q值；
步骤1-5记状态空间为S＝{St0，St0+1，…，ST-1，ST}，其中，St0表示t0时刻agent的状态，ST表示T时刻agent的状态，状态指节点将兴趣包从当前节点发送到存储相应数据的节点；记动作集A＝{At0，At0+1，…，AT-1，AT}，表示不同状态下所选择的动作；一个状态的动作集记为A(s)＝{a1,a2,...,an-1,an}，表示兴趣包到达一个路由节点后可选的n个转发端口；数据包的时间戳记为tstamp，到达下游路由节点的时间记为tarrival，回报值ΔT＝tarrival-tstamp；路由节点为每一个前缀下的每一个转发端口维护一个动作值Q(s,a)，动作值更新公式如下：其中，s为agent的当前状态,a为当前状态下选择的动作，β为学习速率，δt为误差，ΔT为回报值，γ为折扣率，St为t时刻agent的状态，At表示t时刻agent的动作，Qt(s,a)为t时刻状态-动作对(s,a)的动作值，Et(s,a)为t时刻状态-动作对(s,a)的资格迹；
其中，s为agent的当前状态，a为当前状态下选择的动作，γ为折扣率，λ为迹衰减参数，St为t时刻agent的状态，At表示t时刻agent的动作，Qt(s,a)为t时刻状态-动作对(s,a)的动作值，Et(s,a)为t时刻状态-动作对(s,a)的资格迹；
步骤2、根据步骤1建立的强化学习模型，设计转发策略；
将数据包返回到该路由节点的时间记为RTTr，将RTTr作为转发策略的依据，采用结合资格迹的Sarsa(λ)算法求解最佳策略；
在更新策略的方法上，采用针对现有的动作值的贪婪策略：ε-greedy策略，即，以1-ε的概率选择最佳动作，以ε的概率选择其他非贪婪动作；
初始化阶段：获得初始Q值；当路由节点收到兴趣包后，向所有可转发的端口发送兴趣包，获得每个端口的初始Q值；
应用及持续探索阶段：根据初始化阶段得到的初始Q值，按照贪婪策略进行探索并持续更新Q值；当得到初始Q值后，路由节点依据ε-greedy策略进行探索；路由节点向端口转发兴趣包，以1-ε的概率选择最佳Q值端口，以ε的概率选择其他端口以保证持续性的探索，在数据包返回的过程中不断更新Q值；当端口超时后，将式(1)中的δt设置为一个不小于108的常量；
基于步骤2的转发策略，对命名数据网络NDN进行拥塞控制。
2.如权利要求1所述的一种基于强化学习的命名数据网络拥塞控制方法，其特征在于，步骤2所述转发策略的具体实施过程如下：步骤2-1：路由节点判断接收的包类型；若为兴趣包，转步骤2-2，若为数据包，转步骤2-
步骤2-2：重传机制判断是否延迟发送；是，则延迟发送，转步骤2-3；否则直接转步骤2-
步骤2-3：在FIB中查找可能的下一跳；若无下一跳，返回NACK-NOROUTE，结束；有，转步骤2-4；
步骤2-4：判断当前状态，若为初始化阶段，转步骤2-5；若为应用及持续探索阶段，转步骤2-6；
步骤2-5：向所有可转发的端口发送兴趣包，获得每个端口的初始Q值，结束；
步骤2-6：依据ε-greedy策略随机选择是否贪婪；若为贪婪，选择可能的下一跳中Q值最小的节点转发兴趣包；若为不贪婪，则在可能的下一跳中随机选择除Q值最小以外的节点转发兴趣包，结束；
步骤2-7：查询PIT表，若无对应条目，则丢弃该数据包，结束；否则根据NDN数据包的转发流程转发数据包，转步骤2-8；
步骤2-8：从数据包中提取并更新对应端口的Q值，结束。
一种基于强化学习的命名数据网络拥塞控制方法
技术领域
[0001] 本发明涉及一种网络拥塞控制方法，尤其涉及一种基于强化学习的命名数据网络拥塞控制方法，属于网络信息传输通信技术领域。
背景技术
[0002] 命名数据网络(Named Data Networking，NDN)作为面向未来的网络架构之一，通过利用名称寻址并加入内容存储器结构，从根本上解决了当今TCP/IP(Transmission Control Protocol/Internet Protocol，传输控制协议/因特网互联协议)网络中以主机为中心的通信模式和用户以内容为中心的网络需求之间的矛盾。
[0003] 拥塞的发生与网络自身的体系架构密切联系。拥塞控制机制的提出以特定的网络为前提。在TCP/IP中，连接是建立在端到端之间，两个通信的主机会形成一条固定的链路，拥塞控制可以只在终端进行。因此，在TCP中，通过重复ACK(Acknowledgement，确认字符)和超时机制检测拥塞，通过基于滑动窗口的AIMD(Additive Increase Multiplicative Decrease，和式增加，积式减少)减小客户端注入网络的流量。NDN中的节点设有持久性缓存，里面存储着代表不同兴趣对应内容的数据。因此，兴趣包对应的数据包可能会从不同的节点返回，这些节点的远近会对返回数据的RTT(Round-Trip Time，往返时延)估计造成很大的影响。因此，在NDN中，无法对一个数据包设置一个合适的RTT值，单纯的超时机制无法满足NDN中拥塞检测及控制的需求。
[0004] 强化学习又称增强学习，是一种为了理解和自动化目标导向的学习和决策制定而生的计算方法，是机器学习和智能控制领域中的主要方法之一。系统从环境给予的反馈中学习，以获得最大的奖励。强化学习主要在两方面区别于监督学习：
[0005] (1)试错学习：通过与环境的交互获得的反馈来获得好的策略；
[0006] (2)延迟回报：指导信号很少，真正的回报往往在最后一个状态之后才给出，所以涉及到最后一个状态之后的回报分配问题。
[0007] 由于NDN独特的通信模式，传统TCP/IP网络中对RTT的估计方法，在NDN中会由于缓存、多路径转发等因素无法准确使用，使得传统网络中的拥塞控制机制不能很好地适用于NDN。因此，在拓扑复杂和规模较大的NDN中，需要更加准确的网络层控制算法来支持拥塞控制。
[0008] 目前，现有的NDN拥塞控制算法存在对先验知识的依赖，对网络状态的变化不够敏感，难以适用于拓扑高度动态，存在链路延迟大误码率高等情况。
发明内容
[0009] 本发明的目的是为了克服现有NDN拥塞控制技术的缺陷，针对NDN特有的基于PULL的通信机制和以内容为中心的路由和转发策略，同时考虑节点内缓存的影响，提出一种基于强化学习的命名数据网络拥塞控制方法。
[0010] 本发明方法是通过下述技术方案实现的：
[0011] 一种基于强化学习的命名数据网络拥塞控制方法，包括以下步骤：
[0012] 步骤1：对命名数据网络NDN建立强化学习模型。
[0013] 所述模型建立方法如下：
[0014] 步骤1-1利用NDN中路由节点的学习和计算能力，将路由节点看作智能体agent；
[0015] 步骤1-2将路由节点向不同的端口转发兴趣包的过程作为agent选择执行动作的过程，多个可转发的端口对应多个可执行的动作；
[0016] 步骤1-3将兴趣包从一个路由节点通过选择端口转发到另一个路由节点的过程映射为agent将兴趣包从一个状态通过选择相应的动作转移到另一个状态的过程；
[0017] 步骤1-4每个路由节点选择一个端口转发兴趣包后，将兴趣包传输到下一个路由节点的时间映射为环境反馈给agent的立即回报值r(s,a)，该时间通过相应的数据包返回时携带的时间戳信息计算得到。时间戳通过向数据包的结构中添加新的字段项以实现携带，记录的是数据包离开上一个节点的时间。此外，数据包还负责携带上游路由节点下一个状态的Q值(Q值是强化学习中的一个专用术语，本发明中，Q值代表RTTr)返回，以完成当前状态的值函数更新。更新后的数据包，路由节点的FIB表中每一个前缀对应一个条目，条目中的每一个端口都有一个度量条目(如链路开销等)，可以存储标准化的度量信息。将Q值加入原有的度量条目中，数据包携带的以及更新的都为此Q值。
[0018] 步骤1-5记状态空间为S＝{St0，St0+1，…，ST-1，ST}，其中，St0表示t0时刻agent的状态，ST表示T时刻agent的状态，状态指节点将兴趣包从当前节点发送到存储相应数据的节点；记动作集A＝{At0，At0+1，…，AT-1，AT}，表示不同状态下所选择的动作；一个状态的动作集记为A(s)＝{a1,a2,...,an-1,an}，表示兴趣包到达一个路由节点后可选的n个转发端口；数据包的时间戳记为tstamp，到达下游路由节点的时间记为tarrival，回报值ΔT＝tarrival-tstamp；路由节点为每一个前缀下的每一个转发端口维护一个动作值Q(s,a)，动作值更新公式如下：
[0019]
[0020] 其中，s为agent的当前状态,a为当前状态下选择的动作，β为学习速率，δt为误差，ΔT为回报值，γ为折扣率，St为t时刻agent的状态，At表示t时刻agent的动作，Qt(s,a)为t时刻状态-动作对(s,a)的动作值，Et(s,a)为t时刻状态-动作对(s,a)的资格迹。
[0021]
[0022] 其中,s为agent的当前状态，a为当前状态下选择的动作，γ为折扣率，λ为迹衰减参数，St为t时刻agent的状态，At表示t时刻agent的动作，Qt(s,a)为t时刻状态-动作对(s,a)的动作值，Et(s,a)为t时刻状态-动作对(s,a)的资格迹。
[0023] 步骤2、根据步骤1建立的强化学习模型，设计转发策略。转发策略如下：
[0024] 将数据包返回到该路由节点的时间记为RTTr(RTT for router，长远回报)。在强化学习中，应用最广泛的是TD(Temporal Difference，时间差分)算法中的Q-learning策略。然而由于Watkins的Q(λ)算法具有截断有效序列的问题，而改进的Peng的Q(λ)算法很难实现，本发明使用Sarsa(λ)算法实现NDN中网络包的智能转发。
[0025] 将RTTr作为转发策略的依据，采用结合资格迹的Sarsa算法——Sarsa(λ)算法求解最佳策略。在更新策略的方法上，采用针对现有的动作值的贪婪策略：ε-greedy策略，即，以1-ε的概率选择最佳动作，以ε的概率选择其他非贪婪动作。转发策略分为初始化阶段和应用及持续探索阶段。
[0026] 初始化阶段：获得初始Q值。当路由节点收到兴趣包后，向所有可转发的端口发送兴趣包，获得每个端口的初始Q值；
[0027] 应用及持续探索阶段：根据初始化阶段得到的初始Q值，按照贪婪策略进行探索并持续更新Q值。当得到初始Q值后，路由节点依据ε-greedy策略进行探索。路由节点向端口转发兴趣包，以1-ε的概率选择最佳Q值端口，以ε的概率选择其他端口以保证持续性的探索，在数据包返回的过程中不断更新Q值。需要注意的是，RTTr越小越好，最佳Q值即为最小Q值。当端口超时后，将公式(1)中的δt设置为一个不小于108的常量，这样Q值会很大，作为超时的惩罚机制。
[0028] 基于步骤2的转发策略，对命名数据网络NDN进行拥塞控制。
[0029] 有益效果
[0030] 本发明方法，对比已有技术，能够以最小响应时间为目标，设计出有效的智能动态转发策略来解决NDN中的拥塞控制问题，很大程度上避免网络拥塞的发生，并在拥塞发生时及时地发现问题链路，选择网络环境良好的链路转发数据，具有在智能转发策略中能有效增加网络的数据递交率，减小丢包数量和网络平均时延的效果。
附图说明
[0031] 图1为NDN中原有数据包结构；
[0032] 图2为本发明修改后的数据包结构；
[0033] 图3为本发明修改后的FIB表项；
[0034] 图4为本发明实施例的网络拓扑图；
[0035] 图5为本发明实施方式使用的算法同其他算法的应用效果对比图。
具体实施方式
[0036] 下面结合附图和实施例对本发明方法做进一步详细说明。
[0037] 一种基于强化学习的命名数据网络拥塞控制方法，包括以下步骤：
[0038] 步骤1：对命名数据网络NDN建立强化学习模型。
[0039] 所述模型建立方法如下：
[0040] 步骤1-1利用NDN中路由节点的学习和计算能力，将路由节点看作智能体agent；
[0041] 步骤1-2将路由节点向不同的端口转发兴趣包的过程作为agent选择执行动作的过程，多个可转发的端口对应多个可执行的动作；
[0042] 步骤1-3将兴趣包从一个路由节点通过选择端口转发到另一个路由节点的过程映射为agent将兴趣包从一个状态通过选择相应的动作转移到另一个状态的过程；
[0043] 步骤1-4每个路由节点选择一个端口转发兴趣包后，将兴趣包传输到下一个路由节点的时间映射为环境反馈给agent的立即回报值r(s,a)，该时间通过相应的数据包返回时携带的时间戳信息计算得到。时间戳通过向数据包的结构中添加新的字段项以实现携带，记录的是数据包离开上一个节点的时间。此外，数据包还负责携带上游路由节点下一个状态的Q值返回，以完成当前状态的值函数更新。更新后的数据包结构如图2所示，路由节点的FIB表中每一个前缀对应一个条目，条目中的每一个端口都有一个度量条目(如链路开销等)，可以存储标准化的度量信息。将Q值加入原有的度量条目中，数据包携带的以及更新的都为此Q值。修改后的FIB表条目如图3所示。
[0044] 步骤1-5记状态空间为S＝{St0，St0+1，…，ST-1，ST}，其中，St0表示t0时刻agent的状态，ST表示T时刻agent的状态，状态指节点将兴趣包从当前节点发送到存储相应数据的节点；记动作集A＝{At0，At0+1，…，AT-1，AT}，表示不同状态下所选择的动作；一个状态的动作集记为A(s)＝{a1,a2,...,an-1,an}，表示兴趣包到达一个路由节点后可选的n个转发端口；数据包的时间戳记为tstamp，到达下游路由节点的时间记为tarrival，回报值ΔT＝tarrival-tstamp；路由节点为每一个前缀下的每一个转发端口维护一个动作值Q(s,a)，动作值更新公式如下：
[0045]
[0046] 其中，s为agent的当前状态,a为当前状态下选择的动作，β为学习速率，δt为误差，ΔT为回报值，γ为折扣率，St为t时刻agent的状态，At表示t时刻agent的动作，Qt(s,a)为t时刻状态-动作对(s,a)的动作值，Et(s,a)为t时刻状态-动作对(s,a)的资格迹。
[0047]
[0048] 其中,s为agent的当前状态，a为当前状态下选择的动作，γ为折扣率，λ为迹衰减参数，St为t时刻agent的状态，At表示t时刻agent的动作，Qt(s,a)为t时刻状态-动作对(s,a)的动作值，Et(s,a)为t时刻状态-动作对(s,a)的资格迹。
[0049] 步骤2、根据步骤1建立的强化学习模型，设计转发策略。转发策略如下：
[0050] 将数据包返回到该路由节点的时间记为RTTr(RTT for router，长远回报)。在强化学习中，应用最广泛的是TD(Temporal Difference，时间差分)算法中的Q-learning策略。然而由于Watkins的Q(λ)算法具有截断有效序列的问题，而改进的Peng的Q(λ)算法很难实现，本发明使用Sarsa(λ)算法实现NDN中网络包的智能转发。
[0051] 将RTTr作为转发策略的依据，采用结合资格迹的Sarsa算法——Sarsa(λ)算法求解最佳策略。在更新策略的方法上，采用针对现有的动作值的贪婪策略：ε-greedy策略，即，以1-ε的概率选择最佳动作，以ε的概率选择其他非贪婪动作。转发策略分为初始化阶段和应用及持续探索阶段。
[0052] 初始化阶段：获得初始Q值。当路由节点收到兴趣包后，向所有可转发的端口发送兴趣包，获得每个端口的初始Q值；
[0053] 应用及持续探索阶段：根据初始化阶段得到的初始Q值，按照贪婪策略进行探索并持续更新Q值。当得到初始Q值后，路由节点依据ε-greedy策略进行探索。路由节点向端口转发兴趣包，以1-ε的概率选择最佳Q值端口，以ε的概率选择其他端口以保证持续性的探索，在数据包返回的过程中不断更新Q值。需要注意的是，RTTr越小越好，最佳Q值即为最小Q值。当端口超时后，将公式(1)中的δt设置为一个不小于108的常量，这样Q值会很大，作为超时的惩罚机制。
[0054] 基于步骤2的转发策略，对命名数据网络NDN进行拥塞控制。
[0055] 步骤2所述转发策略的具体实施流程如下：
[0056] 步骤2-1：路由节点判断接收的包类型，若为兴趣包，转步骤2-2，若为数据包，转步骤2-7。
[0057] 步骤2-2：重传机制判断是否延迟发送，是则延迟发送，转步骤2-3；否则直接转步骤2-3。
[0058] 步骤2-3：在FIB中查找可能的下一跳，若无下一跳，返回NACK-NOROUTE(查找路由失败)，结束；有则转步骤2-4。
[0059] 步骤2-4：判断当前状态，若为初始化阶段，转步骤2-5；若为应用，即持续探索阶段，则-转步骤2-6。
[0060] 步骤2-5：向所有可转发的端口发送兴趣包，获得每个端口的初始Q值，结束。
[0061] 步骤2-6：依据ε-greedy策略随机选择是否贪婪，贪婪则选择可能的下一跳中Q值最小的节点转发兴趣包，不贪婪则在可能的下一跳中随机选择除Q值最小以外的节点转发兴趣包，结束。
[0062] 步骤2-7：查询PIT表，若无对应条目，则丢弃该数据包，结束；否则根据NDN数据包的转发流程转发数据包，转步骤2-8。
[0063] 步骤2-8：从数据包中提取并更新对应端口的Q值，结束。
[0064] 采用上述方法应用于NDN中，能够在很大程度上避免网络拥塞的发生。
[0065] 实施例
[0066] 本实施例的网络拓扑结构如图4所示。仿真设置中，共有9个网路节点，其中包括4个内容请求者、4个路由器(中间转发节点)和1个内容生产者。其中每条链路的带宽和延迟设置如表1所示。Router1和Router2分别有一条相对较好和相对较差的输出链路：Router1-Router4为较好的输出链路，相较Router1-Router3来说，此链路具有更大的带宽和更小的延迟，单位时间传输的数据更多。Router2对应的两条输出链路同理，但总体上优于Router1的输出链路。
[0067] 表1链路设置表
[0068]
[0069]
[0070] 本实施例将提出的智能转发策略与最佳路由算法Best Route、多路径转发算法Multicast以及请求转发算法(Request Forwarding)进行多方面的对比。仿真中，依次将上述算法记为SarsaLambda、BestRoute、Multicast和RFStrategy。SarsaLambda中，设学习速率β＝0.6，折扣率γ＝0.5，迹衰减参数λ＝0.5，概率ε＝0.05。
[0071] 进行平均时延的对比。平均时延即消费者发送兴趣包后，接收到数据包的平均响应时间，是网络服务质量的重要指标之一。平均时延随请求率的变化结果如图5所示。本发明基于Sarsa-lambda的转发策略以最小响应时间为目标，选择传输时延最小的路径转发兴趣包，使得最终的平均时延最小。图5中，请求率增大后，由于网络中数据包的大量增加，Multicast性能下降，其平均时延也增长较迅速，Sarsa-lambda的平均时延在整体上变为最优。RF在其选择端口的标准中，主要考虑数据包返回的比例而不是快慢，平均时延较高。Best Route不考虑链路时延的问题，时延最大。
