一种基于博弈论的网络控制系统调度方法

摘要

本发明公开了一种基于博弈论的网络控制系统调度方法，步骤为：构建NCSs调度方法的非合作博弈模型；确定NCSs中各控制回路的效用函数；寻找最优调度策略；分析Nash均衡点的存在性和唯一性；运用混合自适应遗传算法求解该Nash均衡点；NCSs中的调度器按照Nash均衡点处的最优调度策略重新为每个控制回路分配网络资源。采用上述技术方案，不依赖于现有的网络资源调度机制，为网络的服务优化提供了依据；可保证网络资源能够得到充分利用，而且也能够确保各个控制回路之间公平合理的竞争，避免资源分配出现过多或过少的现象，从而在一定程度上提高了网络资源利用率。

说明书

技术领域

本发明属于网络控制系统的技术领域，涉及网络资源调度方法，更具 体地说，本发明涉及一种基于博弈论的网络控制系统调度方法。

背景技术

随着计算机网络技术广泛地应用于自动控制领域，一种新的网络化、 节点智能化、信息综合化、分布式的控制系统——网络控制系统（Ne tworked Control Systems，NCSs）便应运而生了。网络化控制满足 了复杂大系统控制和远程控制系统的客观需求，是未来控制系统的发 展方向。由于NCSs是由控制和网络组成的系统，其性能不仅依赖于所 使用的控制策略，还依赖于网络中信息的调度策略。NCSs的调度是用 于规定系统中通过共享通信网络所传送的各种数据的次序和发送时刻 以及时间间隔。合理的网络调度能有效避免网络中各信息之间产生冲 突和拥塞现象，减小网络诱导时延，降低数据丢包率，进一步改善系 统控制性能，提高系统的稳定性。

综合研究现有网络调度的研究成果，从网络层次的角度可分为协议层 调度和应用层调度两类：

协议层调度一般是通过特定的网络协议来实现某些调度策略，因而只 适用于具有调度数据包功能的网络协议，且算法的灵活性较差。

网络应用层上的调度按其侧重点不同又可具体划分为网络优先级调度 与采样周期和采样时刻的调度。网络优先级调度就是规定通过网络连 接的各智能节点（控制器节点、传感器节点）发送数据的次序，其虽 然与具体的网络协议无关，但是必须在具有优先权的网络（如CAN、D eviceNet等）上实现。考虑到系 统的控制性能的优劣直接受到NCSs中各控制回路的采样周期的影响， 同时各控制回路的采样时刻也会影响到数据包对网络资源的争用，由 此便产生了相关的采样周期和采样时刻的调度策略。基于时间窗口的 环路采样时间调度方法是对系统中每个控制回路的采样时间进行调整 并应用于周期性服务网络；基于带宽管理的控制回路采样时间调度方 法是动态地计算各控制回路的采样周期，采样周期将随状态变量的变 化进行实时更新，且其带宽也随即动态更新分配。此外，基于先进控 制理论（如模糊控制、预测控制、自适应控制等）的反馈调度方法虽 能够使控制系统具有较高的控制性能，但其网络资源利用率往往都较 低。

在设计NCSs的资源调度方法时，目前大多数的研究虽然结合了控制效 果和共享资源利用情况并在这方面也取得了一定的成果，但是这些成 果仍远远不足以解决NCSs在实际应用中存在的问题，因此仍需要结合 新的理论知识来探索网络资源调度问题的解决方法。

发明内容

本发明提供一种基于博弈论的网络控制系统调度方法，其目的是合理 分配有限的网络资源（如带宽、缓冲区、频带宽度等）。

为了实现上述目的，本发明采取的技术方案为：

本发明所提供的基于博弈论的网络控制系统调度方法，其特征在于： 所述的该方法包括如下步骤：

步骤1：根据NCSs调度问题的特性及对NCSs的数学描述，构建NCSs调度 方法的非合作博弈模型；

步骤2：根据所述的非合作博弈模型并结合NCSs自身特性和相关的调度 参数，确定NCSs中各控制回路的效用函数；

步骤3：寻找最优调度策略，等价于查找博弈模型的Nash均衡点；根据 所 定义的效用函数，结合Nash均衡存在性的判定条件，分析Nash均衡点 的存在性和唯一性；

步骤4：在明确NCSs调度非合作博弈模型存在唯一的Nash均衡点后，运 用混合自适应遗传算法求解该Nash均衡点；

步骤5：NCSs中的调度器按照Nash均衡点处的最优调度策略重新为每个 控制回路分配网络资源。

本发明采用上述技术方案，不依赖于现有的网络资源调度机制，为网 络的服务优化提供了依据；所构建的NCSs调度非合作博弈模型能够很 好地反映NCSs中各控制回路的动态运行特征与相互竞争关系；在Nash 均衡点处分配网络资源可保证网络资源能够得到充分利用，而且也能 够确保各个控制回路之间公平合理的竞争，避免资源分配出现过多或 过少的现象，从而在一定程度上提高了网络资源利用率。

附图说明

下面是对本说明书附图作简要说明：

图1为含调度器的网络控制系统一般结构；

图2为Nash均衡的混合自适应遗传算法求解流程。

具体实施方式

下面对照附图，通过对实施例的描述，对本发明的具体实施方式作进 一步详细的说明，以帮助本领域的技术人员对本发明的发明构思、技 术方案有更完整、准确和深入的理解。

如图1、图2所示的本发明的技术方案，为一种基于博弈论的网络控制 系统调度方法。 图1给出了网络控制系统的一般结构。

网络控制系统的调度所解决的本质问题就是合理分配有限的网络资源 （如 带宽、缓冲区、频带宽度等）。如何有效地分配有限的网络资源，进 而最大限度地实现资源的潜在价值，这正是经济学研究得比较成熟的 问题。

NCSs中包含有多个控制回路，每个控制回路都是相对独立地共享一个 通信网络，即每个控制回路不知道网络中是否存在其他控制回路，也 无法获得其他控制回路的状态信息。各个控制回路在执行任务时都将 按照自己的需求占用网络资源，并尽可能地使自身达到最佳状态。在 网络资源受限的情况下，各个控制回路之间是通过竞争来抢夺网络资 源，特别是带宽资源；因此，NCSs中的各个控制回路之间就存在一个 非合作博弈过程。

为了实现合理分配有限的网络资源的发明目的，本发明采取的技术方 案为：

将微观经济学中的博弈理论引入到网络控制系统的网络调度中，提出 一种基于博弈论的网络控制系统调度方法。

本发明的基于博弈论的网络控制系统调度方法，包括如下步骤：

步骤1：根据NCSs调度问题的特性及对NCSs的数学描述，构建NCSs调度 方法的非合作博弈模型；

步骤2：根据所述的非合作博弈模型并结合NCSs自身特性和相关的调度 参数，确定NCSs中各控制回路的效用函数；

根据步骤1中构建的NCSs调度中的非合作博弈模型并结合NCSs自身特性 和相关的调度参数，定义NCSs中各控制回路的效用函数；

步骤3：寻找最优调度策略，等价于查找博弈模型的Nash均衡点；根据 所定义的效用函数，结合Nash均衡存在性的判定条件，分析Nash均衡 点的存在性和唯一性；

Nash均衡是博弈论中描述非合作博弈结果的重要手段，因此寻找最优 调度策略可等价于查找博弈模型的Nash均衡点。根据所定义的效用函 数结合Nash 均衡存在性的判定条件分析Nash均衡点的存在性和唯一性。

步骤4：在明确NCSs调度非合作博弈模型存在唯一的Nash均衡点后，运 用混合自适应遗传算法求解该Nash均衡点；

在步骤3中明确了NCSs调度非合作博弈模型存在唯一的Nash均衡点后， 运用混合自适应遗传算法求解该Nash均衡点；

步骤5：NCSs中的调度器按照Nash均衡点处的最优调度策略重新为每个 控制回路分配网络资源。

本发明所提出的网络控制系统调度方法不依赖于现有的网络资源调度 机制，为网络的服务优化提供了依据。所构建的NCSs调度非合作博弈 模型能够很好地反映NCSs中各控制回路的动态运行特征与相互竞争关 系；在Nash均衡点处分配网络资源可保证网络资源能够得到充分利用 ，而且也能够确保各个控制回路之间公平合理的竞争，避免资源分配 出现过多或过少的现象，从而在一定程度上提高了网络资源利用率。

网络控制系统一般包含有至少一个控制回路，每个控制回路由传感器 、控制器、执行器和被控对象组成，用于完成一系列的任务。多个相 互独立的控制回路通过中间共享的网络形成了各自的闭环回路，传感 器与控制器之间和控制器与执行器之间的数据均通过共享的网络来传 递。网络中的τ_ca和τ_sc分别表示控制器与执行器之间的传输时延、传 感器与控制器之间的传输时延。由于共享网络的资源有限，因此系统 在运行过程中不可避免地会存在信息时延、丢失和时序错乱等问题。 为了保证系统能够稳定地运行，就要对网络中传输的信息进行调度。 调度器用于分析系统信息，制定相应的决策，为各控制回路提供调度 信息，从而保证整个NCSs能够稳定高效地运行。

本发明提出的基于博弈论的网络控制系统调度方法，其具体实施步骤 如下：

首先，构建网络控制系统调度方法的非合作博弈模型。所述的构建NC Ss调度方法的非合作博弈模型的方法是：

设网络控制系统中共有n个控制回路，需要调度的回路集合为N={l_i|i ∈[1,n]}；

则NCSs网络调度的非合作博弈模型可定义为一个三元组，即G={N,S,U _i}，其中S是所有参与调度的控制回路的可行方案集S={s_i|s_i=(p_i,b_i),1≤i≤N}，p_i∈[p_i,min,p_i,max]是控制回路l_i（以下内容中涉及控制回路l _i时均简写为l_i）可用的数据传输速率，p_i,min是保证l_i能够正常工作的最 低数据传输速率，p_i,max是l_i最佳的数据传输速率；

b_i∈[p_i,min,B]是调度器预分配给l_i的带宽，B是NCSs的总带宽，显然p_i,max≤ B和成立，其中aB（0≤a≤1，为一比例系数）是调度器预留给其它信 息节点的带宽资源；

U_i为l_i的效用函数；

且U_i是一个从可选传输数据传输速率和带宽值集合S到实数集合R的映 射：U_i→R；

有且只有当时，l_i使用策略所取得的运行效率高于l_i使用策略s_i所 取得的运行效率。

其次，确定所建模型的效用函数的形式。所述的确定NCSs中各控制回 路的效用函数的形式：

基于所建的非合作博弈模型，各控制回路的效用函数U_i可表示如下：

$U_i\left(s_i\right)=\left(\begin{array}{c}\frac{[e_i^2-{(p_i-\overline{b_i})}^2]}{e_i^3}·\frac{{(b_i/\overline{b_i})}^{\upsilon }}{e^{\upsilon ·b_i/\bar{b}}},0\le b_i\le \overline{b_i}\\ [1-{\left(\frac{b_i-\overline{b_i}}{\overline{b_i}-p_{i,\max }}\right)}^{\omega }]\frac{[e_i^2-{({\beta }_i-\overline{b_i})}^2]}{e_i^3},{\bar{b}}_i\le b_i\le p_{i,\max }\end{array}\right)$

式中ν≥2为自然数和ω≥2为偶数，是根据具体的控制情况预先设定 的经验常量；

（α≥1）是l_i可使用的平均带宽值，是l_i可用数据传输速率与平均 带宽值之间的最大偏差；

当分配给l_i的带宽超过了其平均带宽值时，效用函数的值将呈现减小 的趋势，这就反映了当某个控制回路要求较多的带宽资源时，其所得 效用反而将越来越低，从而也保证了带宽资源分配的公平性。

再次，分析调度策略非合作博弈模型的Nash均衡点的存在性和唯一性 。所述的寻找最优调度策略，或查找非合作博弈模型的Nash均衡点的 存在性和唯一性的方法为：

基于非合作博弈模型的网络控制系统网络调度问题实际是一个满足一 定约束的最优化问题，即满足条件；

根据博弈理论该最优化问题的求解，便可转化为相对应的针对相关约 束的Nash均衡点的求解；

该Nash均衡可描述为，其中就是l_i的最佳策略组合，是除l_i之外的 所有其他控制回路的最优策略组合；

由于控制回路的策略组合S是非空的凸集，且为欧式空间的一个紧子集 ，另效用函数U_i对任意s_-i∈S_-i都是s_i的拟凹连续函数，因此根据Nash 均衡点存在性定理可知所建NCSs调度的非合作博弈模型存在唯一的Na sh均衡点。

最后，运用混合自适应遗传算法求解非合作博弈模型的Nash均衡点。 为实现对网络调度非合作博弈模型的Nash均衡点的有效求解，本发明 运用一种混合自适应遗传算法来完成对模型的求解操作。

所述的运用混合自适应遗传算法求解该Nash均衡点的方法是：

依据所建的非合作博弈模型确定遗传算法中的种群大小为m和个体的遗 传基因数为n，遗传基因将用实数表示，数值与NCSs中各控制回路中所 分配的带宽值对应，则种群中所有个体的遗传基因组为；根据效用函 数建立遗传算法的适应度函数为；

由此可知，若适应度函数值越大，就表示该组策略的效用函数之和越 大，则就越接近所建非合作博弈调度模型的Nash均衡点；

因此，此组遗传基因所描述的带宽分配策略就是网络带宽资源的最佳 分配方案；

最后，调度器依据此最佳带宽分配方案为各控制回路分配带宽值。

图2为该操作的流程图。

上面结合附图对本发明进行了示例性描述，显然本发明具体实现并不 受上述方式的限制，只要采用了本发明的方法构思和技术方案进行的 各种非实质性的改进，或未经改进将本发明的构思和技术方案直接应 用于其它场合的，均在本发明的保护范围之内。